1、算法簡(jiǎn)介

1-1、算法思路

決策樹(shù)是一種非參數(shù)的監(jiān)督學(xué)習(xí)方法，用于分類和回歸。它是一種特殊的樹(shù)形結(jié)構(gòu)，一般由節(jié)點(diǎn)和有向邊組成。節(jié)點(diǎn)表示特征或者標(biāo)簽值。而有向邊包含有判斷條件。如1-2圖示，這是判斷是否錄用機(jī)器學(xué)習(xí)工程師的一種決策路徑。

可以看出在每個(gè)特征上都做了一個(gè)分割，分割后的子節(jié)點(diǎn)或成為新的父節(jié)點(diǎn)，或成為最終的葉子節(jié)點(diǎn)。這里要引出兩個(gè)重要的問(wèn)題，每個(gè)節(jié)點(diǎn)在哪個(gè)特征上做劃分？某個(gè)特征在哪個(gè)值上做劃分？

解決這兩個(gè)問(wèn)題要引入一個(gè)新的知識(shí)點(diǎn)--信息熵。熵在信息論中代表隨機(jī)變量不確定度的度量，也就是熵越大，數(shù)據(jù)的不確定性越高；也就是熵越小，數(shù)據(jù)的不確定性越低。有了這個(gè)知識(shí)點(diǎn)后，就可以解決上邊的兩個(gè)問(wèn)題了，遍歷特征后，再遍歷該特征上的每一種劃分方式，選出信息熵最低的特征值。

循環(huán)往復(fù)，選擇出信息熵最低的特征值的過(guò)程，就是訓(xùn)練的過(guò)程。

1-2、圖示

決策樹(shù)

1-3、算法流程

1--- 遍歷所有的特征，在每個(gè)特征上遍歷所有的劃分方式，求出遍歷后的最小信息熵對(duì)應(yīng)的特征及特征值，該特征作為根節(jié)點(diǎn)，特征值作為判斷條件；

2--- 將節(jié)點(diǎn)劃分，作為其子節(jié)點(diǎn)，如劃分成A和B；

3--- 此時(shí)對(duì)A、B求信息熵，如果信息熵足夠?。ń咏?）的部分，則可以停止求解，直接作為葉子結(jié)點(diǎn)，也就是標(biāo)簽；信息熵比較大的話，則執(zhí)行步驟1，求出的特征作為新的節(jié)點(diǎn)。循環(huán)往復(fù)。

1-4、優(yōu)缺點(diǎn)

1-4-1、優(yōu)點(diǎn)

簡(jiǎn)單易懂，可解釋性強(qiáng)，且構(gòu)造的樹(shù)能夠可視化。
只需要較少的數(shù)據(jù)準(zhǔn)備，而其他一些技術(shù)常常需要做數(shù)據(jù)標(biāo)準(zhǔn)化、啞變量的創(chuàng)建等等數(shù)據(jù)準(zhǔn)備工作。
使用成本低，一旦創(chuàng)建了樹(shù)，對(duì)目標(biāo)變量的決策所需要消耗的時(shí)間很少。
能夠同時(shí)處理數(shù)值和分類變量，其他的一些技術(shù)往往只能處理特定數(shù)據(jù)類型的變量。
能處理多輸出問(wèn)題。
可使用統(tǒng)計(jì)檢驗(yàn)來(lái)驗(yàn)證模型，從而可保證模型的可靠性。

1-4-2、缺點(diǎn)

容易出現(xiàn)過(guò)擬合，特別是在構(gòu)造了過(guò)于復(fù)雜的樹(shù)的情況下。
不夠穩(wěn)定，哪怕是訓(xùn)練數(shù)據(jù)出現(xiàn)了一點(diǎn)小的變化，最后生成的樹(shù)也可能千差萬(wàn)別。
訓(xùn)練尋找一個(gè)最優(yōu)的決策樹(shù)是一個(gè)NP完全問(wèn)題，因此決策樹(shù)的構(gòu)造算法也多使用貪心算法，得到的往往是一個(gè)局部最優(yōu)結(jié)果。
對(duì)于異或、多路復(fù)用等問(wèn)題，決策樹(shù)表現(xiàn)一般，因?yàn)闆Q策樹(shù)很難去表達(dá)它們

2、實(shí)踐

2-1、采用bobo老師創(chuàng)建簡(jiǎn)單測(cè)試用例

import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from collections import Counter
from math import log

iris = datasets.load_iris()
X = iris.data[:,2:] #只取出后兩個(gè)feature
y = iris.target #只取出所有類

def split(X, y, d, value):
    index_a = (X[:,d] <= value)# 在第 d 個(gè)維度數(shù)據(jù)上  值小于value的索引
    index_b = (X[:,d] > value)# 在第 d 個(gè)維度數(shù)據(jù)上  值小于value的索引
    return X[index_a], X[index_b], y[index_a], y[index_b]

def entropy(y):
    counter = Counter(y)
    res = 0.0
    for num in counter.values():
        p = num / len(y)
        res += -p * log(p)
    return res

def try_split(X, y):
    
    best_entropy = float('inf')
    best_d, best_v = -1, -1
    for d in range(X.shape[1]):# 遍歷所有維度
        sorted_index = np.argsort(X[:,d]) # 當(dāng)前維度數(shù)據(jù)從小到大的索引
        for i in range(1, len(X)):# 遍歷所有數(shù)據(jù) 求出按前后兩個(gè)值的平均值來(lái)劃分的熵值 
            if X[sorted_index[i], d] != X[sorted_index[i-1], d]:
                v = (X[sorted_index[i], d] + X[sorted_index[i-1], d])/2
                X_l, X_r, y_l, y_r = split(X, y, d, v)
                p_l, p_r = len(X_l) / len(X), len(X_r) / len(X) # 分為兩部分 每部分的概率為->這部分的數(shù)據(jù)數(shù)目/數(shù)據(jù)總數(shù)
                e = p_l * entropy(y_l) + p_r * entropy(y_r)
                if e < best_entropy:
                    best_entropy, best_d, best_v = e, d, v
                
    return best_entropy, best_d, best_v

best_entropy, best_d, best_v = try_split(X, y)
print("best_entropy =", best_entropy)
# best_entropy = 0.46209812037329684
print("best_d =", best_d)
# best_d = 0
print("best_v =", best_v)
# best_v = 2.45

X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
entropy(y1_l)
# 0.0
entropy(y1_r)
# 0.6931471805599453

best_entropy2, best_d2, best_v2 = try_split(X1_r, y1_r)
print("best_entropy =", best_entropy2)
# best_entropy = 0.2147644654371359
print("best_d =", best_d2)
# best_d = 1
print("best_v =", best_v2)
# best_v = 1.75

X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)
entropy(y2_l)
# 0.30849545083110386
entropy(y2_r)
# 0.10473243910508653