1.算法概述

決策樹算法是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過(guò)構(gòu)成決策樹來(lái)求取凈現(xiàn)值的期望值大于等于零的概率，評(píng)價(jià)項(xiàng)目風(fēng)險(xiǎn)，判斷其可行性的決策分析方法。

分類算法是利用訓(xùn)練樣本集獲得分類函數(shù)即分類模型(分類器)，從而實(shí)現(xiàn)將數(shù)據(jù)集中的樣本劃分到各個(gè)類中。分類模型通過(guò)學(xué)習(xí)訓(xùn)練樣本中屬性集與類別之間的潛在關(guān)系，并以此為依據(jù)對(duì)新樣本屬于哪一類進(jìn)行預(yù)測(cè)。

決策樹算法是直觀運(yùn)用概率分析的一種圖解法，是一種十分常用的分類方法，屬于有監(jiān)督學(xué)習(xí)。

決策樹是一種樹形結(jié)構(gòu)，其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉子結(jié)點(diǎn)代表一種類別。

決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)，它采用自頂向下的遞歸方法，其基本思想是以信息熵為度量構(gòu)造一顆熵值下降最快的樹，到葉子結(jié)點(diǎn)處的熵值為零，此時(shí)每個(gè)葉子節(jié)點(diǎn)中的實(shí)例都屬于同一類。

決策樹學(xué)習(xí)算法的最大優(yōu)點(diǎn)是，它可以自學(xué)習(xí)，在學(xué)習(xí)的過(guò)程中不需要使用者了解過(guò)多的背景知識(shí)，只需要對(duì)訓(xùn)練實(shí)例進(jìn)行較好的標(biāo)注，就能夠進(jìn)行學(xué)習(xí)。

2.算法種類

ID3算法

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

C4.5算法

• C4.5算法使用信息增益率代替信息增益，進(jìn)行特征選擇，克服了信息增益選擇特征時(shí)偏向于特征值個(gè)數(shù)較多的不足。
• C4.5算法具體算法步驟與ID3類似。
• C4.5能夠完成對(duì)連續(xù)屬性的離散化處理，能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。

C5.0算法

• C5.0算法是Quinlan在C4.5算法的基礎(chǔ)上提出的商用改進(jìn)版本，目的是對(duì)含有大量數(shù)據(jù)的數(shù)據(jù)集進(jìn)行分析。
• C5.0算法與C4.5算法相比有以下優(yōu)勢(shì)：
  • 決策樹構(gòu)建時(shí)間要比C4.5算法快上數(shù)倍，同時(shí)生成的決策樹規(guī)模也更小，擁有更少的葉子結(jié)點(diǎn)數(shù)
  • 使用了提升法(boosting)，組合多個(gè)決策樹來(lái)做出分類，使準(zhǔn)確率大大提高
  • 提供可選項(xiàng)由使用者視情況決定，例如是否考慮樣本的權(quán)重、樣本錯(cuò)誤分類成本等
    

CART算法

• CART決策樹的生成就是遞歸地構(gòu)建二叉決策樹的過(guò)程。
• CART用基尼系數(shù)最小化準(zhǔn)則來(lái)進(jìn)行特征選擇，生成二叉樹。
• Gini系數(shù)計(jì)算公式：

3.算法示例

在機(jī)器學(xué)習(xí)中，決策樹是一種預(yù)測(cè)模型，它代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。

決策樹的目的是擬合一個(gè)可以通過(guò)指定輸入值預(yù)測(cè)最終輸出值得模型。

4.決策樹構(gòu)建示例

描述

分析

計(jì)算

結(jié)論

5.算法實(shí)現(xiàn)步驟

選擇屬性是構(gòu)建一顆決策樹非常關(guān)鍵的一步，被選擇的屬性會(huì)成為決策樹的一個(gè)節(jié)點(diǎn)，并且不斷遞歸地選擇最優(yōu)的屬性就可以最終構(gòu)建決策樹。

計(jì)算數(shù)據(jù)集S中的每個(gè)屬性的熵 H(xi)選取數(shù)據(jù)集S中熵值最?。ɑ蛘咝畔⒃鲆孀畲?，兩者等價(jià)）的屬性在決策樹上生成該屬性節(jié)點(diǎn)使用剩余結(jié)點(diǎn)重復(fù)以上步驟生成決策樹的屬性節(jié)點(diǎn)

 6.算法相關(guān)概念

熵

1948年，香農(nóng)提出了“信息熵”的概念，熵是接收的每條信息中所包含信息的平均量，是不確定性的量度，而不是確定性的量度，因?yàn)樵诫S機(jī)的信源的熵越大。熵被定義為概率分布的對(duì)數(shù)的相反數(shù)。

信息熵的公式：

信息增益

“信息增益”是用來(lái)衡量一個(gè)屬性區(qū)分?jǐn)?shù)據(jù)樣本的能力，當(dāng)使用某一個(gè)屬性作為一棵決策樹的根節(jié)點(diǎn)時(shí)，該屬性的信息增益量就越大。決策樹會(huì)選擇最大化信息增益來(lái)對(duì)結(jié)點(diǎn)進(jìn)行劃分。

7.算法實(shí)現(xiàn)代碼

import numpy as np
import math
from collections import Counter

# 創(chuàng)建數(shù)據(jù)
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']


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

# 實(shí)現(xiàn)拆分函數(shù)
def split_dataset(dataset, idx):
  	# idx是要拆分的特征下標(biāo)
    splitData = defaultdict(list)
    for data in dataset:
      	# 這里刪除了idx這個(gè)特征的取值，因?yàn)橛貌坏搅?
        splitData[data[idx]].append(np.delete(data, idx))
    return list(splitData.values()), list(splitData.keys())

# 實(shí)現(xiàn)特征的選擇函數(shù)
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):
      	# 根據(jù)特征i切分
        split_data, _ = split_dataset(dataset, i)
        new_entropy = 0.0
        # 計(jì)算切分后的信息熵
        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

# 決策樹創(chuàng)建函數(shù)
def create_decision_tree(dataset, feature_names):
    dataset = np.array(dataset)
    counter = Counter(dataset[:, -1])
    # 如果數(shù)據(jù)集值剩下了一類，直接返回
    if len(counter) == 1:
        return dataset[0, -1]
    
    # 如果所有特征都已經(jīng)切分完了，也直接返回
    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)
    
    # 遞歸調(diào)用，對(duì)每一個(gè)切分出來(lái)的取值遞歸建樹
    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

# 決策樹節(jié)點(diǎn)預(yù)測(cè)函數(shù)
def classify(node, feature_names, data):
  	# 獲取當(dāng)前節(jié)點(diǎn)判斷的特征
    key = list(node.keys())[0]
    node = node[key]
    idx = feature_names.index(key)
    
    # 根據(jù)特征進(jìn)行遞歸
    pred = None
    for key in node:
      	# 找到了對(duì)應(yīng)的分叉
        if data[idx] == key:
          	# 如果再往下依然還有子樹，那么則遞歸，否則返回結(jié)果
            if isinstance(node[key], dict):
                pred = classify(node[key], feature_names, data)
            else:
                pred = node[key]
                
    # 如果沒有對(duì)應(yīng)的分叉，則找到一個(gè)分叉返回
    if pred is None:
        for key in node:
            if not isinstance(node[key], dict):
                pred = node[key]
                break
    return pred

8.算法優(yōu)缺點(diǎn)

 優(yōu)點(diǎn)：小規(guī)模數(shù)據(jù)集有效

缺點(diǎn)

• 處理連續(xù)變量不好
• 類別比較多時(shí)，錯(cuò)誤增加得比較快
• 不能處理大量數(shù)據(jù)

9.算法優(yōu)化

決策樹算法是一種非常經(jīng)典的算法，其訓(xùn)練過(guò)程中主要依靠獲得數(shù)據(jù)間的熵及信息增益作為劃分依據(jù)，分類效果較好。但一般情況下我們訓(xùn)練決策樹均是在數(shù)據(jù)量較小的數(shù)據(jù)集進(jìn)行，當(dāng)訓(xùn)練分類器所用的訓(xùn)練數(shù)據(jù)足夠大時(shí)，決策樹會(huì)出現(xiàn)樹身過(guò)高、擬合效果差等問(wèn)題。因此，如何高效準(zhǔn)確的構(gòu)建決策樹成為模式識(shí)別領(lǐng)域的一項(xiàng)研究熱點(diǎn)。

使用增量訓(xùn)練的方式迭代訓(xùn)練決策樹
融合Bagging與Boosting技術(shù)訓(xùn)練多棵決策樹
對(duì)于波動(dòng)不大、方差較小的數(shù)據(jù)集， 可以探尋一種比較穩(wěn)定的分裂準(zhǔn)則作為解決辦法

總結(jié)

到此這篇關(guān)于Python機(jī)器學(xué)習(xí)算法之決策樹算法的文章就介紹到這了,更多相關(guān)Python決策樹算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論