Python機器學習算法之決策樹算法的實現與優缺點

1.算法概述

決策樹算法是在已知各種情況發生概率的基礎上,通過構成決策樹來求取凈現值的期望值大於等於零的概率,評價項目風險,判斷其可行性的決策分析方法。

分類算法是利用訓練樣本集獲得分類函數即分類模型(分類器),從而實現將數據集中的樣本劃分到各個類中。分類模型通過學習訓練樣本中屬性集與類別之間的潛在關系,並以此為依據對新樣本屬於哪一類進行預測。

決策樹算法是直觀運用概率分析的一種圖解法,是一種十分常用的分類方法,屬於有監督學習。

決策樹是一種樹形結構,其中每個內部結點表示在一個屬性上的測試,每個分支代表一個測試輸出,每個葉子結點代表一種類別。

決策樹學習是以實例為基礎的歸納學習,它采用自頂向下的遞歸方法,其基本思想是以信息熵為度量構造一顆熵值下降最快的樹,到葉子結點處的熵值為零,此時每個葉子節點中的實例都屬於同一類。

決策樹學習算法的最大優點是,它可以自學習,在學習的過程中不需要使用者瞭解過多的背景知識,隻需要對訓練實例進行較好的標註,就能夠進行學習。

2.算法種類

ID3算法

  • ID3算法中根據信息論的信息增益評估和選擇特征。每次選擇信息增益最大的候選特征,作為判斷模塊。
  • 信息增益與屬性的值域大小成正比。屬性取值種類越多,越有可能成為分裂屬性。
  • ID3也不能處理連續分佈的數據。

C4.5算法

  • C4.5算法使用信息增益率代替信息增益,進行特征選擇,克服瞭信息增益選擇特征時偏向於特征值個數較多的不足。
  • C4.5算法具體算法步驟與ID3類似。
  • C4.5能夠完成對連續屬性的離散化處理,能夠對不完整數據進行處理。

C5.0算法

  • C5.0算法是Quinlan在C4.5算法的基礎上提出的商用改進版本,目的是對含有大量數據的數據集進行分析。
  • C5.0算法與C4.5算法相比有以下優勢:
    • 決策樹構建時間要比C4.5算法快上數倍,同時生成的決策樹規模也更小,擁有更少的葉子結點數
    • 使用瞭提升法(boosting),組合多個決策樹來做出分類,使準確率大大提高
    • 提供可選項由使用者視情況決定,例如是否考慮樣本的權重、樣本錯誤分類成本等

CART算法

  • CART決策樹的生成就是遞歸地構建二叉決策樹的過程。
  • CART用基尼系數最小化準則來進行特征選擇,生成二叉樹。
  • Gini系數計算公式:

3.算法示例

在機器學習中,決策樹是一種預測模型,它代表的是對象屬性與對象值之間的一種映射關系。

決策樹的目的是擬合一個可以通過指定輸入值預測最終輸出值得模型。

4.決策樹構建示例

描述

分析

計算

結論

5.算法實現步驟

選擇屬性是構建一顆決策樹非常關鍵的一步,被選擇的屬性會成為決策樹的一個節點,並且不斷遞歸地選擇最優的屬性就可以最終構建決策樹。

計算數據集S中的每個屬性的熵 H(xi)選取數據集S中熵值最小(或者信息增益最大,兩者等價)的屬性在決策樹上生成該屬性節點使用剩餘結點重復以上步驟生成決策樹的屬性節點

 6.算法相關概念

1948年,香農提出瞭“信息熵”的概念,熵是接收的每條信息中所包含信息的平均量,是不確定性的量度,而不是確定性的量度,因為越隨機的信源的熵越大。熵被定義為概率分佈的對數的相反數。

信息熵的公式:

信息增益

“信息增益”是用來衡量一個屬性區分數據樣本的能力,當使用某一個屬性作為一棵決策樹的根節點時,該屬性的信息增益量就越大。決策樹會選擇最大化信息增益來對結點進行劃分。

7.算法實現代碼

import numpy as np
import math
from collections import Counter

# 創建數據
def create_data():
    X1 = np.random.rand(50, 1)*100
    X2 = np.random.rand(50, 1)*100
    X3 = np.random.rand(50, 1)*100
    
    def f(x):
        return 2 if x > 70 else 1 if x > 40 else 0
    
    y = X1 + X2 + X3
    Y = y > 150
    Y = Y + 0
    r = map(f, X1)
    X1 = list(r)
    
    r = map(f, X2)
    X2 = list(r)
    
    r = map(f, X3)
    X3 = list(r)
    x = np.c_[X1, X2, X3, Y]
    return x, ['courseA', 'courseB', 'courseC']


# 計算集合信息熵的函數
def calculate_info_entropy(dataset):
    n = len(dataset)
    # 我們用Counter統計一下Y的數量
    labels = Counter(dataset[:, -1])
    entropy = 0.0
    # 套用信息熵公式
    for k, v in labels.items():
        prob = v / n
        entropy -= prob * math.log(prob, 2)
    return entropy

# 實現拆分函數
def split_dataset(dataset, idx):
  	# idx是要拆分的特征下標
    splitData = defaultdict(list)
    for data in dataset:
      	# 這裡刪除瞭idx這個特征的取值,因為用不到瞭
        splitData[data[idx]].append(np.delete(data, idx))
    return list(splitData.values()), list(splitData.keys())

# 實現特征的選擇函數
def choose_feature_to_split(dataset):
    n = len(dataset[0])-1
    m = len(dataset)
    # 切分之前的信息熵
    entropy = calculate_info_entropy(dataset)
    bestGain = 0.0
    feature = -1
    for i in range(n):
      	# 根據特征i切分
        split_data, _ = split_dataset(dataset, i)
        new_entropy = 0.0
        # 計算切分後的信息熵
        for data in split_data:
            prob = len(data) / m
            new_entropy += prob * calculate_info_entropy(data)
        # 獲取信息增益
        gain = entropy - new_entropy
        if gain > bestGain:
            bestGain = gain
            feature = i
    return feature

# 決策樹創建函數
def create_decision_tree(dataset, feature_names):
    dataset = np.array(dataset)
    counter = Counter(dataset[:, -1])
    # 如果數據集值剩下瞭一類,直接返回
    if len(counter) == 1:
        return dataset[0, -1]
    
    # 如果所有特征都已經切分完瞭,也直接返回
    if len(dataset[0]) == 1:
        return counter.most_common(1)[0][0]
    
    # 尋找最佳切分的特征
    fidx = choose_feature_to_split(dataset)
    fname = feature_names[fidx]
    
    node = {fname: {}}
    feature_names.remove(fname)
    
    # 遞歸調用,對每一個切分出來的取值遞歸建樹
    split_data, vals = split_dataset(dataset, fidx)
    for data, val in zip(split_data, vals):
        node[fname][val] = create_decision_tree(data, feature_names[:])
    return node

# 決策樹節點預測函數
def classify(node, feature_names, data):
  	# 獲取當前節點判斷的特征
    key = list(node.keys())[0]
    node = node[key]
    idx = feature_names.index(key)
    
    # 根據特征進行遞歸
    pred = None
    for key in node:
      	# 找到瞭對應的分叉
        if data[idx] == key:
          	# 如果再往下依然還有子樹,那麼則遞歸,否則返回結果
            if isinstance(node[key], dict):
                pred = classify(node[key], feature_names, data)
            else:
                pred = node[key]
                
    # 如果沒有對應的分叉,則找到一個分叉返回
    if pred is None:
        for key in node:
            if not isinstance(node[key], dict):
                pred = node[key]
                break
    return pred

8.算法優缺點

 優點:小規模數據集有效

缺點

  • 處理連續變量不好
  • 類別比較多時,錯誤增加得比較快
  • 不能處理大量數據

9.算法優化

決策樹算法是一種非常經典的算法,其訓練過程中主要依靠獲得數據間的熵及信息增益作為劃分依據,分類效果較好。但一般情況下我們訓練決策樹均是在數據量較小的數據集進行,當訓練分類器所用的訓練數據足夠大時,決策樹會出現樹身過高、擬合效果差等問題。因此,如何高效準確的構建決策樹成為模式識別領域的一項研究熱點。

使用增量訓練的方式迭代訓練決策樹
融合Bagging與Boosting技術訓練多棵決策樹
對於波動不大、方差較小的數據集, 可以探尋一種比較穩定的分裂準則作為解決辦法

總結

到此這篇關於Python機器學習算法之決策樹算法的文章就介紹到這瞭,更多相關Python決策樹算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: