AI - Ch14 機器學習(2), 決策樹 Decision Tree

決策樹 (Decision Tree)
決策樹是用來處理分類問題的樹狀結構，使用方法為:選出分類能力最好的屬性做為樹的內部節點，將內部節點的所有不同資料產生出對應的分支，遞迴重複上面的過程直到滿足終止條件，ID3、C4.5 、C5.0、CHAID及CART是決策樹演算法的代表。

決策樹圖示

每個內部節點表示一個評估欄位
每個分枝代表一個可能的欄位輸出結果
每個樹葉節點代表不同分類的類別標記

欄位屬性

分類樹：分析是當預計結果可能為離散類型（例如三個種類的花，輸贏等）使用的概念。可分割出不同值域的分支，每個分支的表示亦可以以子集合的型態表示。
回歸樹：分析是當局域結果可能為實數（例如房價，患者住院時間等）使用的概念。可採用離散化的方式，將資料分割成許多區間，但是仍需要保持資料的順序性。
CART分析結合上述二者的概念。CART是Classification And Regression Trees的縮寫。

常用的屬性選擇指標有

資訊獲利 (Information Gain) – ID3、C4.5、C5.0
吉尼係數 (Gini Index) – CART
χ2獨立性檢定 – CHAID

ID3、C4.5和C5.0

ID3 演算法 (Iterative Dichotomiser 3)
ID3在建構決策樹過程中，以資訊獲利(Information Gain)為準則，並選擇最大的資訊獲利值作為分類屬性。這個算法是建立在奧卡姆剃刀的基礎上：越是小型的決策樹越優於大的決策樹。儘管如此，該算法也不是總是生成最小的樹形結構，而是一個啟發式算法。另外，C4.5算法是ID3的升級版。

以熵為基礎 (詳見熵)

$ H(S) = - \sum_{x \in X} p(x) \log_{2} p(x) $

資訊獲利 (Information Gain)

$IG(A,S) = H(S) - \sum_{t \in T} p(t)H(t)$

這個ID3算法可以歸納為以下幾點：

使用屬性計算與之相關的樣本熵值
選取其中熵值最小的屬性(資訊獲利最大)
生成包含該屬性的節點
遞迴直到終止

C4.5 演算法
C4.5演算法利用屬性的獲利比率(Gain Ratio)克服問題，獲利比率是資訊獲利正規化後的結果。求算某屬性A的獲利比率時除資訊獲利外，尚需計算該屬性的分割資訊值(Split Information) :

$SplitInfo_A(S) = \sum_{t \in T} \frac{|S_j|}{|S|} \times log_2{\frac{|S_j|}{|S|}}$

C4.5的改善：

對連續屬性的處理
改善ID3傾向選擇擁有許多不同數值但不具意義的屬性：之所以使用獲利比率(Gain Ratio)，是因為ID3演算法所使用的資訊獲利會傾向選擇擁有許多不同數值的屬性，例如：若依學生學號(獨一無二的屬性)進行分割，會產生出許多分支，且每一個分支都是很單一的結果，其資訊獲利會最大。但這個屬性對於建立決策樹是沒有意義的。

C5.0 演算法
C5.0 是 C4.5的商業改進版，可應用於海量資料集合上之分類。主要在執行準確度和記憶體耗用方面做了改進。因其採用Boosting方式來提高模型準確率，且佔用系統資源與記憶體較少，所以計算速度較快。其所使用的演算法沒有被公開。

C5.0 的優點：

C5.0模型在面對遺漏值時非常穩定。
C5.0模型不需要很長的訓練次數。
C5.0模型比較其他類型的模型易於理解。
C5.0的增強技術提高分類的精度。

[例題]

A data set has 4 Boolean variables. What is the maximum number of leaves in a decision tree? __$2^4$__
To each leaf in the decision, the number of corresponding rule is __1__
If a decision tree achieves 100% accuracy on the training set, then it will also get 100% accuracy on the test set? __No__
Using information gain to pick attributes, decision tree learning can be considered A* search algorithm. __No__
A decision tree can describe any Boolean function? __Yes__

[tiny lab 1] ID3 和 C4.5 - Information gain 與 Gain ratio

14個範例資料中，關於風力的資料 :

Wind = weak 有8筆資料 (weak),其中有6個正例與2個反例 [6+, 2-]
Wind = strong 有6筆資料 (strong) ,其中有3個正例與3個反例 [3+, 3-]

#先計算分割前的熵
entropy_before <- (-9/14)*log2(9/14) + (-5/14)*log2(5/14)

#再計算分割後的熵加權平均
gain_wind <- 8/14*( (-6/8)*log2(6/8) + (-2/8)*log2(2/8) ) +
             6/14*( (-3/6)*log2(3/6) + (-3/6)*log2(3/6) )
#前後熵差值便是information gain
info_gain <- entropy_before - gain_wind
print(info_gain)   #ans = 0.04812703

#再計算 split information
split_info <- (-8/14)*log2(8/14) +  (-6/14) * log2(6/14)

#information gain除split information便是gain ratio
gain_ratio <- info_gain / split_info
print(gain_ratio)   #ans = 0.04884862

熵 (Entropy)
在資訊理論中，熵被用來衡量一個隨機變數出現的期望值。它代表了在被接收之前，訊號傳輸過程中損失的資訊量，又被稱為資訊熵。熵是對不確定性的測量。在資訊界，熵越高則能傳輸越多的資訊，熵越低則意味著傳輸的資訊越少。

如果有一枚理想的硬幣，其出現正面和反面的機會相等，則拋硬幣事件的熵等於其能夠達到的最大值。我們無法知道下一個硬幣拋擲的結果是什麼，因此每一次拋硬幣都是不可預測的。

使用一枚正常硬幣進行拋擲，這個事件的熵是一位元，若進行n次獨立實驗，則熵為n，因為可以用長度為n的位元流表示。但是如果一枚硬幣的兩面完全相同，那個這個系列拋硬幣事件的熵等於零，因為結果能被準確預測。(所以在分類上熵很低表示是一個好的特徵)

[感覺] 硬幣有正反面才能「攜帶」訊息，如正面的話午餐吃牛肉麵，背面則吃滷肉飯，都是一樣圖案就「攜帶」不了訊息。

熵的定義
夏農把隨機變量 $X$ 的熵值 $Η$ 定義如下，其值域為 $\{x_1,...,x_n\}$

$H(X) = \mathrm{E}[\mathrm{I}(X)] = \mathrm{E}[-\ln(\mathrm{P}(X))]$

其中， $P$ 為 $X$ 的機率質量函數，$E$ 為期望函數，而 $I(X)$ 是 $X$ 的資訊量， $I(X)$ 本身是個隨機變數。當取自有限的樣本時，熵的公式可以表示為：

$H(X) = \sum_{i} {\mathrm{P}(x_i)\,\mathrm{I}(x_i)} = -\sum_{i} {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)}$

因此熵實際是對隨機變量的位元量和發生機率相乘再總和的數學期望。

[例題1]
假設一個隨機變量X，取三種可能值 $x_1, x_2, x_3$ ，機率分別為 $\frac{1}{2}, \frac{1}{4}, \frac{1}{4} $，那麼編碼平均位元長度是：$ \frac{1}{2} \times 1 + \frac{1}{4} \times 2 + \frac{1}{4} \times 2 = \frac{3}{2} = \frac{3}{2}$。

[例題2]
如英語有26個字母，假如每個字母在文章中出現次數平均的話，每個字母的訊息量為：

$I_e = -\log_2 {1\over 26} = 4.7$

而漢字常用的有2500個，假如每個漢字在文章中出現次數平均的話，每個漢字的資訊量為：

$I_e = -\log_2 {1\over 2500} = 11.3$

實際上每個字母和每個漢字在文章中出現的次數並不平均，比方說較少見字母（如z）和罕用漢字就具有相對高的資訊量。但上述計算提供了以下概念：使用書寫單元越多的文字，每個單元所包含的訊息量越大。熵是整個系統的平均消息量，即：

$H_s = \sum_{i=1}^n p_i I_e = -\sum_{i=1}^n p_i \log_2 p_i$

如果兩個系統具有同樣大的消息量，如一篇用不同文字寫的同一文章，由於漢字的資訊量較大，中文文章應用的漢字就比英文文章使用的字母要少。所以漢字印刷的文章要比其他應用總體數量少的字母印刷的文章要短。即使一個漢字占用兩個字母的空間，漢字印刷的文章也要比英文字母印刷的用紙少。

CART (Classification and Regression Tree)
由Friedman等人於1980年代提出，是一種產生二元樹的技術，以吉尼係數(Gini index)做為選擇屬性的依據。CART與ID3、C4.5、C5.0演算法的最大相異之處是，其在每一個節點上都是採用二分法，也就是一次只能夠有兩個子節點，ID3、C4.5、C5.0則在每一個節點上可以產生不同數量的分枝。

計算上和ID3非常相似，只是評估函數替換，熵換成吉尼係數、資訊獲利換成吉尼獲利，並挑選獲利最大做分割：

吉尼係數 Gini index
假設資料集合$S$包含$n$個類別，則吉尼係數$Gini(S)$定義為：

$Gini(S) = 1 - \sum_{n \in S} p_i^2$

吉尼獲利 Gini gain
$S$用屬性$A$來分割成數個$S_i$ ，則吉尼獲利$GiniGain(A,S)$可表示為：

$GiniGain(A,S) = Gini(S) − Gini(A,S) = Gini(S) - \sum_{n \in S}\frac{|S_n|}{|S|}Gini(S_n)$

[tiny lab 2] CART - Gini index

與上一個tinylab相同資料，14個範例資料中，關於風力的資料 :

Wind = weak 有8筆資料 (weak),其中有6個正例與2個反例 [6+, 2-]
Wind = strong 有6筆資料 (strong) ,其中有3個正例與3個反例 [3+, 3-]

Gini_before <- 1- ( (9/14)^2 + (5/14)^2 )
print(Gini_before)    #ans = 0.4285714

Gini_weak <- 1- ( (6/8)^2 + (2/8)^2 )
Gini_strong <- 1- ( (3/6)^2 + (3/6)^2 )

Gini_after <- (8/14)*Gini_weak + (6/14)*Gini_strong
print(Gini_after)    #ans = 0.4285714

Gini_gain <- Gini_after - Gini_before
print(Gini_gain)    #ans = -0.03061224, 
#此例中分割完反而更差了

決策樹學習的常見問題

避免過度適配資料
過度配適是指模型對於範例的過度訓練，導致模型記住的不是訓練資料的一般特性，反而是訓練資料的局部特性。對測試樣本的分類將會變得很不精確。

[注意] 通常過度適配發生在訓練範例含有雜訊和離異值時，但當訓練數據沒有雜訊時，過度適配也有可能發生，特別是當訓練範例的數量太少，使得某一些屬性「恰巧」可以很好地分割目前的訓練範例，但卻與實際的狀況並無太多關係。

修剪決策樹移除不可信賴的分支

事前修剪 (Prepruning) : 透過決策樹不再增長的方式來達到修剪的目的。選擇一個合適的臨界值往往很困難。
事後修剪 (Postpruning) :

子樹置換 (Subtree Replacement)：選擇某個子樹，並用單個樹葉來置換它。
子樹提升 (Subtree Raising)

合併連續值屬性
透過動態地定義新的離散值屬性來實現，即先把連續值屬性的值域分割為離散的區間集合，或設定門檻值以進行二分法。

屬性選擇指標的其他度量標準

訊息獲利 : 趨向於包含多個值的屬性
獲利比率 : 會產生不平均的分割，也就是分割的一邊會非常小於另一邊
吉尼係數 : 傾向於包含多個值的屬性，當類別個數很多時會有困難，傾向那些會導致平衡切割並且兩邊均為純粹的測試

尚有其他的度量標準，也都各有利弊。

References

交大胡毓志教授人工智慧講義

Wiki - 熵 (資訊理論)
https://zh.wikipedia.org/wiki/熵_(信息论)

Wiki - ID3 algorithm
https://en.wikipedia.org/wiki/ID3_algorithm

決策樹學習 - 國立聯合大學資訊管理學系陳士杰教師
http://sjchen.im.nuu.edu.tw/MachineLearning/final/CLS_DT.pdf

Pages

2015年6月17日星期三