決策樹演算法的Python實現

01-27

一.決策樹的基本思想

決策樹是一種基本的分類與回歸方法，它可以看作if-then規則的集合，也可以認為是定義在特徵空間與類空間上的條件概率分布。

將決策樹轉換成if-then規則的過程如下：

由決策樹的根節點到葉節點的每一條路徑構建一條規則；
路徑內部結點的特徵對應規則的條件；
葉節點的類對應規則的結論.

決策樹的路徑具有一個重要的性質：互斥且完備,即每一個樣本均被且只能被一條路徑所覆蓋。

決策樹學習演算法主要由三部分構成：

特徵選擇
決策樹生成
決策樹的剪枝

下面，從這三方面進行理論介紹，並提供相應的Python代碼實現。

二. 決策樹的特徵選擇

如果利用一個特徵進行分類的結果與隨機分類的結果無異，則可以認為這個特徵是不具備分類能力的。把這樣的特徵去掉，對決策樹的分類精度應該影響不大。

而我們應該基於什麼準則來判定一個特徵的分類能力呢？

這時候，需要引入一個概念：信息增益.

信息增益

在介紹信息增益之前，先了解一個概念：熵(entropy).

熵(entropy)

在資訊理論與概率論中，熵(entropy)用於表示**隨機變數不確定性的度量**。

設X是一個有限狀態的離散型隨機變數，其概率分布為

$P(X = x_i) = p_i, i=1,2,cdots,n$

則隨機變數 $X$ 的熵定義為

$H(X)= - sum_{i=1}^{n} p_{i}log(p_i)$

熵越大，則隨機變數的不確定性越大。

當隨機變數只有0,1兩種取值時，假設 $P(X=1)=p$ ,則有

$H(X)=-plog(p)-(1-p)log(1-p)$

從而有，

$frac{partial H(X)}{partial p} = -log(frac{p}{1-p})$

(圖1 概率P與熵的關係)

從而可知，當p=0.5時，熵取值最大，隨機變數不確定性最大。

條件熵(conditional entropy)

隨機變數 $X$ 給定的條件下，隨機變數 $Y$ 的條件熵 $H(Y|X)$ 定義為：

$H(Y|X) = sum_{i=1}^{n}p_i H(Y|X=x_i)$

其中， $p_i = P(X = x_i)$ 。

信息增益(information gain)

信息增益表示的是：得知特徵X的信息而使得類Y的信息的不確定性減少的程度。

具體定義如下。

特徵A對訓練數據集D的信息增益 $g(D,A)$ 定義為集合D的經驗熵 $H(D)$ 與特徵A給定條件下D的經驗條件熵 $H(D|A)$ 之差，即

$g(D,A)=H(D)-H(D|A)$

一般地，熵 $H(Y)$ 與條件熵 $H(Y|X)$ 之差稱為互信息(mutual information).

根據信息增益準則進行特徵選擇的方法是：對訓練數據集D，計算其每個特徵的信息增益，並比它們的大小，從而選擇信息增益最大的特徵。

假設訓練數據集為D，樣本容量為|D|,有 $k$ 個類別 $C_k,|C_k|$ 為類別 $C_k$ 的樣本個數。某一特徵 $A$ 有n個不同的取值 ${a_1,a_2,cdots,a_n}$ 。根據特徵A的取值可將數據集D劃分為n個子集 $D_1,D_2,cdots,D_n$ , $|D_i|$ 為 $D_i$ 的樣本個數。並記子集 $D_i$ 中屬於類

$C_k$ 的樣本的集合為 $D_{ik},|D_{ik}|$ 為 $D_{ik}$ 的樣本個數。

則信息增益的演算法如下：

- 輸入：訓練數據集D和特徵A；

- 輸出：特徵A對訓練數據集D的信息增益 $g(D,A)$ .

- (1) 計算數據集D的經驗熵 $H(D)$ .

$H(D) = - sum_{k=1}^{K}frac{|C_k|}{|D|}logfrac{|C_k|}{|D|}$

- (2) 計算特徵A對數據集D的經驗條件熵 $H(D|A).$ .

$H(D|A) = sum_{i=1}^{n}frac{|D_i|}{|D|}H(D_i) = sum_{i=1}^{n}frac{|D_i|}{|D|}sum_{k=1}^{K}frac{|D_{ik}|}{D_i}logfrac{|D_{ik}|}{D_i}$

- (3) 計算信息增益

$g(D,A)=H(D)-H(D|A)$

信息增益比(information gain ratio)

以信息增益作為特徵選擇準則，會存在偏向於選擇取值較多的特徵的問題。可以採用信息增益比對這一問題進行校正。

特徵A對訓練數據集D的信息增益比定義為其信息增益與訓練集D關於特徵A的值的熵之比，即

$g_{R}(D|A) = frac{g(D,A)}{H_{A}(D)}$

其中， $H_{A}(D)=-sum_{i=1}^{n}frac{|D_i|}{|D|}logfrac{|D_i|}{|D|}$ .

```pythonn# 對y的各種可能的取值出現的個數進行計數.。其他函數利用該函數來計算數據集和的混雜程度ndef uniquecounts(rows):n results = {}n for row in rows:n #計數結果在最後一列n r = row[len(row)-1]n if r not in results:results[r] = 0n results[r]+=1n return results # 返回一個字典nnn# 熵nnndef entropy(rows):n from math import logn log2 = lambda x:log(x)/log(2)n results = uniquecounts(rows)n #開始計算熵的值n ent = 0.0n for r in results.keys():n p = float(results[r])/len(rows)n ent = ent - p*log2(p)n return entn```n

三.決策樹的生成

決策樹的生成演算法有很多變形，這裡介紹幾種經典的實現演算法：ID3演算法，C4.5演算法和CART演算法。這些演算法的主要區別在於分類結點上特徵選擇的選取標準不同。下面詳細了解一下演算法的具體實現過程。

ID3演算法

ID3演算法的核心是在決策樹的各個結點上應用信息增益準則進行特徵選擇。具體做法是：

從根節點開始，對結點計算所有可能特徵的信息增益，選擇信息增益最大的特徵作為結點的特徵，並由該特徵的不同取值構建子節點；
對子節點遞歸地調用以上方法，構建決策樹；
直到所有特徵的信息增益均很小或者沒有特徵可選時為止。

C4.5演算法

C4.5演算法與ID3演算法的區別主要在於它在生產決策樹的過程中，使用信息增益比來進行特徵選擇。

CART演算法

分類與回歸樹（classification and regression tree,CART）與C4.5演算法一樣，由ID3演算法演化而來。CART假設決策樹是一個二叉樹，它通過遞歸地二分每個特徵，將特徵空間劃分為有限個單元，並在這些單元上確定預測的概率分布。

CART演算法中，對於回歸樹，採用的是平方誤差最小化準則；對於分類樹，採用基尼指數最小化準則。

平方誤差最小化

假設已將輸入空間劃分為M個單元 $R_1,R_2,...,R_M$ ,並且在每個單元 $R_m$ 上有一個固定的輸出值 $c_m$ ，於是回歸樹可以表示為

$f(x)=sum_{m=1}^{M}c_{m}I(xin R_m)$

當輸入空間的劃分確定時，可以用平方誤差 $sum_{x_i in R_m}(y_i - f(x_i))^2$ 來表示回歸樹對於訓練數據的預測誤差。

基尼指數

分類問題中，假設有K個類別，樣本點屬於第 $k$ 類的概率為 $p_k$ ,則概率分布的基尼指數定義為

$Gini(p)=sum_{k=1}^{K}p_{k}(1-p_k)=1-sum_{k=1}^{K}p_{k}^{2}$

```pythonn#定義節點的屬性nclass decisionnode:n def __init__(self,col = -1,value = None, results = None, tb = None,fb = None):n self.col = col # col是待檢驗的判斷條件所對應的列索引值n self.value = value # value對應於為了使結果為True，當前列必須匹配的值n self.results = results #保存的是針對當前分支的結果，它是一個字典n self.tb = tb ## desision node,對應於結果為true時，樹上相對於當前節點的子樹上的節點n self.fb = fb ## desision node,對應於結果為true時，樹上相對於當前節點的子樹上的節點nnnn# 基尼不純度nnn# 隨機放置的數據項出現於錯誤分類中的概率ndef giniimpurity(rows):n total = len(rows)n counts = uniquecounts(rows)n imp =0n for k1 in counts:n p1 = float(counts[k1])/totaln for k2 in counts: # 這個循環是否可以用（1-p1）替換？n if k1 == k2: continuen p2 = float(counts[k2])/totaln imp+=p1*p2n return impnnn# 改進giniimpuritynnndef giniimpurity_2(rows):n total = len(rows)n counts = uniquecounts(rows)n imp = 0n for k1 in counts.keys():n p1 = float(counts[k1])/totaln imp+= p1*(1-p1)n return impnnnn#在某一列上對數據集進行拆分。可應用於數值型或因子型變數ndef divideset(rows,column,value):n #定義一個函數，判斷當前數據行屬於第一組還是第二組n split_function = Nonen if isinstance(value,int) or isinstance(value,float):n split_function = lambda row:row[column] >= valuen else:n split_function = lambda row:row[column]==valuen # 將數據集拆分成兩個集合，並返回n set1 = [row for row in rows if split_function(row)]n set2 = [row for row in rows if not split_function(row)]n return(set1,set2)nnn# 以遞歸方式構造樹nndef buildtree(rows,scoref = entropy):n if len(rows)==0 : return decisionnode()n current_score = scoref(rows)n n # 定義一些變數以記錄最佳拆分條件n best_gain = 0.0n best_criteria = Nonen best_sets = Nonen n column_count = len(rows[0]) - 1n for col in range(0,column_count):n #在當前列中生成一個由不同值構成的序列n column_values = {}n for row in rows:n column_values[row[col]] = 1 # 初始化n #根據這一列中的每個值，嘗試對數據集進行拆分n for value in column_values.keys():n (set1,set2) = divideset(rows,col,value)n n # 信息增益n p = float(len(set1))/len(rows)n gain = current_score - p*scoref(set1) - (1-p)*scoref(set2)n if gain>best_gain and len(set1)>0 and len(set2)>0:n best_gain = gainn best_criteria = (col,value)n best_sets = (set1,set2)n n #創建子分支n if best_gain>0:n trueBranch = buildtree(best_sets[0]) #遞歸調用n falseBranch = buildtree(best_sets[1])n return decisionnode(col = best_criteria[0],value = best_criteria[1],n tb = trueBranch,fb = falseBranch)n else:n return decisionnode(results = uniquecounts(rows))nn# 決策樹的顯示ndef printtree(tree,indent = ):n # 是否是葉節點n if tree.results!=None:n print str(tree.results)n else:n # 列印判斷條件n print str(tree.col)+":"+str(tree.value)+"? "n #列印分支n print indent+"T->",n printtree(tree.tb,indent+" ")n print indent+"F->",n printtree(tree.fb,indent+" ")nnn# 對新的觀測數據進行分類nnndef classify(observation,tree):n if tree.results!= None:n return tree.resultsn else:n v = observation[tree.col]n branch = Nonen if isinstance(v,int) or isinstance(v,float):n if v>= tree.value: branch = tree.tbn else: branch = tree.fbn else:n if v==tree.value : branch = tree.tbn else: branch = tree.fbn return classify(observation,branch)n```n

```pythonn# testnnnmy_data=[[slashdot,USA,yes,18,None],n [google,France,yes,23,Premium],n [digg,USA,yes,24,Basic],n [kiwitobes,France,yes,23,Basic],n [google,UK,no,21,Premium],n [(direct),New Zealand,no,12,None],n [(direct),UK,no,21,Basic],n [google,USA,no,24,Premium],n [slashdot,France,yes,19,None],n [digg,USA,no,18,None],n [google,UK,no,18,None],n [kiwitobes,UK,no,19,None],n [digg,New Zealand,yes,12,Basic],n [slashdot,UK,no,21,None],n [google,UK,yes,18,Basic],n [kiwitobes,France,yes,19,Basic]]nnnndivideset(my_data,2,yes)nnnginiimpurity(my_data)nnnginiimpurity_2(my_data)nnntree = buildtree(my_data)nnnprinttree(tree = tree)nnnclassify([(direct),USA,yes,5],tree)n```n

0:google?

T-> 3:21?

T-> {Premium: 3}

F-> 2:yes?

T-> {Basic: 1}

F-> {None: 1}

F-> 0:slashdot?

T-> {None: 3}

F-> 2:yes?

T-> {Basic: 4}

F-> 3:21?

T-> {Basic: 1}

F-> {None: 3}

Out[3]:

{Basic: 4}n

四.決策樹的剪枝

如果對訓練集建立完整的決策樹，會使得模型過於針對訓練數據，擬合了大部分的雜訊，即出現過度擬合的現象。為了避免這個問題，有兩種解決的辦法：

當熵減少的數量小於某一個閾值時，就停止分支的創建。這是一種貪心演算法。
先創建完整的決策樹，然後再嘗試消除多餘的節點，也就是採用減枝的方法。

方法1存在一個潛在的問題：有可能某一次分支的創建不會令熵有太大的下降，但是隨後的子分支卻有可能會使得熵大幅降低。因此，我們更傾向於採用剪枝的方法。

決策樹的剪枝通過極小化決策樹整體的損失函數來實現。在提高信息增益的基礎上，通過對模型的複雜度T施加懲罰，便得到了損失函數的定義：

$C_{alpha}(T) = sum_{t=1}^{|T|}N_{t}H_{t}(T)+alpha |T|$

$alpha$ 的大小反映了對模型訓練集擬合度和模型複雜度的折衷考慮。剪枝的過程就是當 $alpha$ 確定時，選擇損失函數最小的模型。

具體的演算法如下：

1. 計算每個節點的經驗熵；

2. 遞歸地從樹的葉節點向上回縮，如果將某一個父節點的所有葉節點合併，能夠使得其損失函數減小，則進行剪枝，將父節點變成新的葉節點；

3. 返回2，直到不能繼續合併。

```pythonnnn# 決策樹的剪枝nnndef prune(tree,mingain):n # 如果分支不是葉節點，則對其進行剪枝n if tree.tb.results == None:n prune(tree.tb,mingain)n if tree.fb.results == None:n prune(tree.fb,mingain)n # 如果兩個子分支都是葉節點，判斷是否能夠合併n if tree.tb.results !=None and tree.fb.results !=None:n #構造合併後的數據集n tb,fb = [],[]n for v,c in tree.tb.results.items():n tb+=[[v]]*cn for v,c in tree.fb.results.items():n fb+=[[v]]*cn #檢查熵的減少量n delta = entropy(tb+fb)-(entropy(tb)+entropy(fb)/2)n if delta < mingain:n # 合併分支n tree.tb,tree.fb = None,Nonen tree.results = uniquecounts(tb+fb)n# testntree = buildtree(my_data,scoref = giniimpurity)nprune(tree,0.1)nprinttree(tree)n```n

{None: 7, Premium: 3, Basic: 6}

五.決策樹的優缺點分析

優點

- 易於理解和解釋，甚至比線性回歸更直觀；
- 與人類做決策思考的思維習慣契合；
- 模型可以通過樹的形式進行可視化展示；
- 可以直接處理非數值型數據，不需要進行啞變數的轉化，甚至可以直接處理含缺失值的數據；

缺點

- 對於有大量數值型輸入和輸出的問題，決策樹未必是一個好的選擇；
- 特別是當數值型變數之間存在許多錯綜複雜的關係，如金融數據分析；
- 決定分類的因素取決於更多變數的複雜組合時；
- 模型不夠穩健，某一個節點的小小變化可能導致整個樹會有很大的不同。

六. 深入學習

- Bagging
- 隨機森林(Random Forest)
- Boosting

七. 參考文獻

- 『集體編程智慧』，第七章
- 『統計學習方法』，第五章
- 『Data Science from Scratch』，第17章
- 『An Introduction to Statistical Learning』，第八章