決策樹

目錄

• 介紹
• 熵
• ID3
• • 計算資訊熵
  • 計算資訊增益
• C4.5
• • 計算屬性分裂資訊度量
  • 計算資訊增益率
• CART
• 剪枝
• • 預剪枝
  • 後剪枝
• 優缺點對比

介紹

決策樹(DecisionTree）是在已知各種情況發生機率的基礎上，通過構成決策樹來求取淨現值的期望值大于等于零的機率，評價項目風險，判斷其可行性的決策分析方法，是直覺運用機率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝幹，故稱決策樹。

常見的決策樹算法有ID3、C4.5以及CART。但在讨論這些之前，我們先了解一下熵的概念。

熵

熵 這個概念最早起源于實體學，在實體學中是用來度量熱力學系統的無序程度；而在資訊學裡，熵則是對不确定性的度量。1948年，香農引入了資訊熵，将其定義為離散随機事件出現的機率。一個系統越是有序，資訊熵越低，反之一個系統越是混亂，它的資訊熵就越高。

假設一個随機變量 X X X 的取值為 X = { x 1 , x 2 , . . . , x n } X = \{x_1, x_2, ..., x_n\} X={x1​,x2​,...,xn​}，每一種值取到的機率分别為 { p 1 , p 2 , . . . , p n } \{p_1, p_2, ..., p_n\} {p1​,p2​,...,pn​}，那麼熵的定義為 H ( X ) = − ∑ i = 1 n p i l o g 2 p i H(X) = - \sum_{i=1}^n p_i log_2 p_i H(X)=−i=1∑n​pi​log2​pi​

對于分類模型來說，類别 C C C 是變量，它的取值為 C 1 , C 2 , . . . , C n C_1, C_2, ..., C_n C1​,C2​,...,Cn​，而每個類别出現的機率分别為 P ( C 1 ) , P ( C 2 ) , . . . , P ( C n ) P(C_1), P(C_2), ..., P(C_n) P(C1​),P(C2​),...,P(Cn​), 這裡 n 是類别的總數，此時分類模型的熵就可以表示為 H ( C ) = − ∑ i = 1 n P ( C i ) l o g 2 P ( C n ) H(C) = -\sum_{i=1}^n P(C_i) log_2 P(C_n) H(C)=−i=1∑n​P(Ci​)log2​P(Cn​)

這是一家高爾夫球俱樂部的曆史資料，裡面記錄了不同天氣狀況使用者來打高爾夫球的曆史記錄。我們要做的是通過建構決策樹來預測使用者是否會來打高爾夫球。

日期	天氣	溫度	濕度	風速	活動
1	晴	炎熱	高	弱	取消
2	晴	炎熱	高	強	取消
3	陰	炎熱	高	弱	進行
4	雨	适中	高	弱	進行
5	雨	寒冷	正常	弱	進行
6	雨	寒冷	正常	強	取消
7	陰	寒冷	正常	強	進行
8	晴	适中	高	弱	取消
9	晴	寒冷	正常	弱	進行
10	雨	适中	正常	弱	進行
11	晴	适中	正常	強	進行
12	陰	适中	高	強	進行
13	陰	炎熱	正常	弱	進行
14	雨	适中	高	強	取消

ID3

ID3 (Iterative Dichotomiser 3)，即疊代二叉樹 3代。核心思想就是以資訊增益來度量屬性，優先選擇資訊增益最大的屬性進行分裂。

計算資訊熵

資料集中共14個樣本，活動 (Label) 包含9個正例和5個負例，目前屬性的資訊熵計算如下

E n t r o p y ( S ) = − 9 14 l o g 2 9 14 − 5 14 l o g 2 5 14 = 0.94 Entropy(S) = -\frac{9}{14}log_2\frac{9}{14} - \frac{5}{14}log_2\frac{5}{14} = 0.94 Entropy(S)=−149​log2​149​−145​log2​145​=0.94

以 天氣 為例，各分支的資訊熵計算如下

E n t r o p y ( 晴 ) = − 2 5 l o g 2 2 5 − 3 5 l o g 2 3 5 = 0.97 Entropy(晴) = -\frac{2}{5}log_2\frac{2}{5} - \frac{3}{5}log_2\frac{3}{5} = 0.97 Entropy(晴)=−52​log2​52​−53​log2​53​=0.97

E n t r o p y ( 陰 ) = − 4 4 l o g 2 4 4 − 0 ⋅ l o g 2 ⋅ 0 = 0 Entropy(陰) = -\frac{4}{4}log_2\frac{4}{4} - 0·log_2·0 = 0 Entropy(陰)=−44​log2​44​−0⋅log2​⋅0=0

E n t r o p y ( 雨 ) = − 3 5 l o g 2 3 5 − 2 5 l o g 2 2 5 = 0.97 Entropy(雨) = -\frac{3}{5}log_2\frac{3}{5} - \frac{2}{5}log_2\frac{2}{5} = 0.97 Entropy(雨)=−53​log2​53​−52​log2​52​=0.97

天氣 的資訊熵

E n t r o p y ( 天 氣 ) = 5 14 ⋅ 0.97 + 4 14 ⋅ 0 + 5 14 ⋅ 0.97 = 0.694 Entropy(天氣) = \frac{5}{14}·0.97 + \frac{4}{14}·0 + \frac{5}{14}·0.97 = 0.694 Entropy(天氣)=145​⋅0.97+144​⋅0+145​⋅0.97=0.694

同理，其他幾個屬性的資訊熵

E n t r o p y ( 溫 度 ) = 0.911 Entropy(溫度) = 0.911 Entropy(溫度)=0.911

E n t r o p y ( 濕 度 ) = 0.789 Entropy(濕度) = 0.789 Entropy(濕度)=0.789

E n t r o p y ( 風 速 ) = 0.892 Entropy(風速) = 0.892 Entropy(風速)=0.892

計算資訊增益

資訊增益的計算公式

I G ( S ∣ T ) = E n t r o p y ( S ) − ∑ v a l u e ( T ) ∣ S v ∣ S E n t r o p y ( S v ) IG(S|T) = Entropy(S) - \sum_{value(T)} \frac{|S_v|}{S} Entropy(S_v) IG(S∣T)=Entropy(S)−value(T)∑​S∣Sv​∣​Entropy(Sv​)

I G ( 天 氣 ) = E n t r o p y ( S ) − E n t r o p y ( 天 氣 ) = 0.94 − 0.694 = 0.246 IG(天氣) = Entropy(S) - Entropy(天氣) = 0.94 - 0.694 = 0.246 IG(天氣)=Entropy(S)−Entropy(天氣)=0.94−0.694=0.246

I G ( 溫 度 ) = E n t r o p y ( S ) − E n t r o p y ( 溫 度 ) = 0.94 − 0.911 = 0.029 IG(溫度) = Entropy(S) - Entropy(溫度) = 0.94 - 0.911 = 0.029 IG(溫度)=Entropy(S)−Entropy(溫度)=0.94−0.911=0.029

I G ( 濕 度 ) = E n t r o p y ( S ) − E n t r o p y ( 濕 度 ) = 0.94 − 0.789 = 0.15 IG(濕度) = Entropy(S) - Entropy(濕度) = 0.94 - 0.789 = 0.15 IG(濕度)=Entropy(S)−Entropy(濕度)=0.94−0.789=0.15

I G ( 風 速 ) = E n t r o p y ( S ) − E n t r o p y ( 風 速 ) = 0.94 − 0.892 = 0.048 IG(風速) = Entropy(S) - Entropy(風速) = 0.94 - 0.892 = 0.048 IG(風速)=Entropy(S)−Entropy(風速)=0.94−0.892=0.048

在決策樹的每一個非葉子結點劃分之前，先計算每一個屬性所帶來的資訊增益，優先選擇最大資訊增益的屬性來劃分。資訊增益越大，區分樣本的能力越強，越具有代表性。

C4.5

假設，每個屬性中的每種類别都隻有一個樣本，那屬性的資訊熵就等于零，繼續使用資訊增益就無法選擇出有效分類特征。是以，C4.5在ID3的基礎上做出了改進，使用資訊增益率對屬性進行分裂，以減少資訊增益容易選擇特征值多的屬性的缺點。

計算屬性分裂資訊度量

H ( 天 氣 ) = − 5 14 l o g 2 5 14 − 5 14 l o g 2 5 14 − 4 14 l o g 2 4 14 = 1.577 H(天氣) = -\frac{5}{14}log_2\frac{5}{14} -\frac{5}{14}log_2\frac{5}{14} -\frac{4}{14}log_2\frac{4}{14} = 1.577 H(天氣)=−145​log2​145​−145​log2​145​−144​log2​144​=1.577

H ( 溫 度 ) = − 4 14 l o g 2 4 14 − 6 14 l o g 2 6 14 − 4 14 l o g 2 4 14 = 1.556 H(溫度) = -\frac{4}{14}log_2\frac{4}{14} -\frac{6}{14}log_2\frac{6}{14} -\frac{4}{14}log_2\frac{4}{14} = 1.556 H(溫度)=−144​log2​144​−146​log2​146​−144​log2​144​=1.556

H ( 濕 度 ) = − 7 14 l o g 2 7 14 − 7 14 l o g 2 7 14 = 1.0 H(濕度) = -\frac{7}{14}log_2\frac{7}{14} -\frac{7}{14}log_2\frac{7}{14} = 1.0 H(濕度)=−147​log2​147​−147​log2​147​=1.0

H ( 風 速 ) = − 6 14 l o g 2 6 14 − 8 14 l o g 2 8 14 = 0.048 H(風速) = -\frac{6}{14}log_2\frac{6}{14} -\frac{8}{14}log_2\frac{8}{14} = 0.048 H(風速)=−146​log2​146​−148​log2​148​=0.048

計算資訊增益率

I G R ( 天 氣 ) = I G ( 天 氣 ) / H ( 天 氣 ) = 0.246 / 1.577 = 0.155 IGR(天氣) = IG(天氣) / H(天氣) = 0.246 / 1.577 = 0.155 IGR(天氣)=IG(天氣)/H(天氣)=0.246/1.577=0.155

I G R ( 溫 度 ) = I G ( 溫 度 ) / H ( 溫 度 ) = 0.029 / 1.556 = 0.0186 IGR(溫度) = IG(溫度) / H(溫度) = 0.029 / 1.556 = 0.0186 IGR(溫度)=IG(溫度)/H(溫度)=0.029/1.556=0.0186

I G R ( 濕 度 ) = I G ( 濕 度 ) / H ( 濕 度 ) = 0.151 / 1.0 = 0.151 IGR(濕度) = IG(濕度) / H(濕度) = 0.151 / 1.0 = 0.151 IGR(濕度)=IG(濕度)/H(濕度)=0.151/1.0=0.151

I G R ( 風 速 ) = I G ( 風 速 ) / H ( 風 速 ) = 0.048 / 0.985 = 0.048 IGR(風速) = IG(風速) / H(風速) = 0.048 / 0.985 = 0.048 IGR(風速)=IG(風速)/H(風速)=0.048/0.985=0.048

C4.5有效克服了ID3中存在的多值屬性的問題，計算每一個屬性所帶來的資訊增益率，優先選擇最大資訊增益率的屬性來劃分。資訊增益率越大，區分樣本的能力越強，越具有代表性。

CART

無論是 ID3 還是 C4.5，都是基于熵的模型，裡面會涉及到大量的對數運算，我們能否在此基礎上進行簡化，節省運算時間？于是就有了 GINI指數。

GINI指數公式

G I N I ( D ) = ∑ i = 1 k p k ⋅ ( 1 − p k ) = 1 − ∑ i = 1 k p k 2 GINI(D) = \sum_{i=1}^k p_k·(1 - p_k) = 1 - \sum_{i=1}^k p_k^2 GINI(D)=i=1∑k​pk​⋅(1−pk​)=1−i=1∑k​pk2​

基尼指數的意義是從資料集D中随機抽取樣本類别辨別不一緻的機率，基尼指數越小，資料集的純度越高。

以 天氣 為例，各分支的GINI指數計算如下

G i n i ( 晴 ) = 1 − ( 2 5 2 + 3 5 2 ) = 0.48 Gini(晴) = 1 - (\frac{2}{5}^2 + \frac{3}{5}^2) = 0.48 Gini(晴)=1−(52​2+53​2)=0.48

G i n i ( 陰 ) = 1 − ( 4 4 2 + 0 0 2 ) = 0 Gini(陰) = 1 - (\frac{4}{4}^2 + \frac{0}{0}^2) = 0 Gini(陰)=1−(44​2+00​2)=0

G i n i ( 雨 ) = 1 − ( 3 5 2 + 2 5 2 ) = 0.48 Gini(雨) = 1 - (\frac{3}{5}^2 + \frac{2}{5}^2) = 0.48 Gini(雨)=1−(53​2+52​2)=0.48

天氣 的GINI指數

G i n i ( 天 氣 ) = 5 14 ⋅ 0.48 + 4 14 ⋅ 0 + 5 14 ⋅ 0.48 = 0.342 Gini(天氣) = \frac{5}{14}·0.48 + \frac{4}{14}·0 + \frac{5}{14}·0.48 = 0.342 Gini(天氣)=145​⋅0.48+144​⋅0+145​⋅0.48=0.342

同理，其他幾個屬性的GINI指數

G i n i ( 溫 度 ) = 0.439 Gini(溫度) = 0.439 Gini(溫度)=0.439

G i n i ( 濕 度 ) = 0.367 Gini(濕度) = 0.367 Gini(濕度)=0.367

G i n i ( 風 速 ) = 0.428 Gini(風速) = 0.428 Gini(風速)=0.428

Gini系數越小，屬性的純度越高。

剪枝

決策樹的基本剪枝政策有 預剪枝 (Pre-Pruning) 和 後剪枝 (Post-Pruning) 。首先将資料集劃分成訓練集和驗證集，訓練集用來決定樹生成過程中每個結點劃分所選擇的屬性；驗證集在預剪枝中用于決定該結點是否有必要依據該屬性進行展開，在後剪枝中用于判斷該結點是否需要進行剪枝。

預剪枝

在每一次實際對結點進行劃分之前，先采用驗證集的資料來驗證如果劃分是否能提高劃分的準确性。如果不能，就把結點标記為葉結點并退出進一步劃分；如果可以就繼續遞歸生成節點。

後剪枝

後剪枝則是先從訓練集生成一顆完整的決策樹，然後自底向上地對非葉結點進行考察，若将該結點對應的子樹替換為葉結點能帶來泛化性能提升，則将該子樹替換為葉結點。

優缺點對比

算法	支援模型	樹結構	特征選擇	連續值處理	缺失值處理	剪枝	分類變量	樣本量
ID3	分類	多叉樹	資訊增益	不支援	不支援	不支援	分類變量	已退出舞台
C4.5	分類	多叉樹	資訊增益率	支援	支援	支援	連續變量和分類變量	小樣本
CART	分類、回歸	二叉樹	GINI系數/均方差	支援	支援	支援	連續變量和分類變量	大樣本