最直覺的分類--決策樹

大家好! 採礦貓又來了，之前向各位介紹過的SVM分類演算法是否非常有趣呢? 本周貓大將為您說明另一種分類演算法，更直觀、更簡單，就是Decision Tree！下列介紹將會帶著讀者們一起了解決策樹的原理及應用。

決策樹是什麼？

樹，是由樹枝、樹葉、及樹幹所構成的，要讓一棵樹長的好看，就必須修剪樹枝、樹葉；決策樹亦是。決策樹是用來處理分類問題的樹狀結構，構成決策樹的元件是節點與分支，其中節點又分為三種類型：

決策節點：通常用矩形框來表示
機會節點：通常用圓圈來表示
終結點：通常用三角形來表示

在Data mining中，決策樹經常被使用，其不僅可以分析數據，也可以做預測。決策樹模型代表的是資料中的「屬性」與「值」之間的映射關係。

內部節點：表示一個評估欄位。
分枝：代表不同可能的欄位輸出結果。
葉節點：對應從根節點到該葉節點歷經的「路徑」所表示之對象的「值」。

建立決策樹

要從現有的資料中建立一顆決策樹，通常採用由上而下(Top-Down)，以遞迴的方式建立。唯一的要求是，資料的屬性必須是「類別型態」，若是連續型數據，必須先離散化過後才可以開始建立決策樹。
運作期間有時會發生過度遷就 (over-fitting) 的問題-即出現決策樹只對某一訓練資料集有效；若更換另一組訓練資料集，則預測結果會產生錯誤。發生這種情況可能是「雜訊」或「特例」所造成的，或是「分支太多」而必須適當修剪。修剪的方式分為以下兩種：

預先修剪：分支過程中進行品質量測
事後修剪：先讓決策樹自由發展，再將多餘分支修剪

決策樹如何運作?

決策樹的本質是一種貪婪演算法(Greedy Algorithm)，一開始所有的訓練樣本(Training Set)都在根節點，並以計算過後各屬性的統計性測量（例如資訊獲利）當作基礎，挑選最好的屬性來當作分割點，反覆地將樣本分隔開來。一直到以下條件發生，我們就停止分支：

某個分支子集合內的所有樣本都屬於同一個類別時。
可能所有的屬性都用完了，用多數投票法以樣本數較多類別來代表此葉節點。
選取屬性後，發生某個分支完全沒有測試樣本的情況。

但是，屬性不能亂選，必須經過仔細的計算。屬性選取、量測的方法有很多，首先，我們利用ID3演算法計算出資訊獲利，再用以下的Splitting Rule分割：
Kolmogorov-Smirnov statistic
Basic impurity index
Gini index
Entropy index
Maximize half-sum of squares

雖然方法很多，但是目的都是一致的：對目標類嘗試進行最佳的分割。從根到葉子節點都有一條路徑，這條路徑就是一條“規則”。

資訊獲利(Information Gain): 由 Quinlan 於 1979 年提出，藉由測量樣本特
徵在文件中出現與否，去計算其資訊位元數值並用以預測分類。在決策樹中，簡單來說，此數值可以代表從這個屬性中獲得的有效資訊。

小故事時間

最近，貓大的朋友小咪吃到了一種非常美味可口的飼料，想推薦給其他貓咪們。由於不確定牠們的主人願不願意購買這種飼料，於是貓大蒐集了許多朋友的資料，來建立一個決策樹模型讓貓朋友們使用，以預測主人是否會想要購買這種飼料。以下是貓大所蒐集的資料，僅需重複的兩步驟就可以建立出決策樹模型。接下來，讓我們一起建立出決策樹模型吧喵！

STEP 1. 利用ID3演算法將三個屬性的資訊獲利計算出來

假設P→會買飼料；N→不會買飼料
以16筆顧客資料中，曾購買NB有4筆，未曾買NB有12筆
I (p, n) = I (4,12) =0.8113
依照年齡將16位顧客分成兩群組：

小於30歲：曾買飼料有1筆，未買有5筆。
大於或等於30歲：曾買飼料有3筆，未買有7筆。

同理
Gain (婚姻) = I (4,12) - (I (3,4) +I (1,8)) =0.0972
Gain (收入) = I (4,12) - (I (1,5) +I (2,5) +I (1,2) ) =0.0177

經過計算發現婚姻屬性的資訊獲利最大，因此選擇婚姻作為第一個分類的依據。接下來根據婚姻的屬性值將資料樣本分成單身以及已婚兩個子集合分別考慮。用同樣的方法來分別決定左右分支下一個要選取的屬性。

STEP 2：決定如何分割

選出屬性後，接下來要決定如何分割，選定其中一種Splitting Rule作為計算方法，就可以分割了！以Gini Index為例，Gini的特性如下：

假設所有的屬性都是連續型數值型態。
假設每個屬性都存在數個可能的切割值。
適用於連續性的數值型態屬性。
可能需要其他工具(例如分群)，來得到可能的分群值。
可修改用在類別型態的屬性。

假設資料集合 S 包含 n 個類別，吉尼係數 Gini(S) 定義為：

（Pj為在S中的值組屬於類別j的機率。）

利用屬性A分割資料集合 S 為 S1 與 S2 (二元分割)。則根據此一分割要件的吉尼係數GiniA(S)為：

其中， S1 與 S2 是針對欄位 A 內的不同數值所構成的兩組資料子集合。

不純度的降低值為:

挑選擁有最大不純度的降低值、或吉尼係數GiniA(S)最小的屬性作為分割屬性。

若人數分類表如下，則我們將分割點設為收入30000。

Gini(收入 < =30k) =1-(1/16)-(5/16)=0.898
Gini(收入 >=30k) =1-(3/16) -(7/16) =0.773
Gini’’(30)=6/16 *Gini(收入 <30k) + 10/16 *Gini(收入>=30k)=0.820
Gini(收入 <40k) =1-(2/16) -(7/16) =0.793
Gini(收入>=40k) =1-(2/16) -(5/16) =0.887
Gini’’ (40)=9/16 *(收入 <40k )+7/16*Gini(收入 >=40k)=0.834
因為Gini’’(30)<Gini’’(40)，因此將分割點設定在收入三萬元比設定在收入四萬元好。

同理，若年齡分類表如下
Gini(年齡<25) =1-(0/16)-(3/16)=0.965
Gini(年齡>=25) =1-(4/16) -(9/16) =0.621
Gini’ (25)=3/16 Gini(年齡<25 )+13/16 Gini(年齡>=25)=0.686
Gini(年齡<35) =1-(1/16) -(7/16) =0.805
Gini(年齡>=35) =1-(3/16) -(5/16) =0.867
Gini’(35)=8/16 Gini(年齡<35)+8/16 Gini(年齡 >=35)=0.836
因為Gini’ (25) <Gini’(35)，因此將分割點設定在年齡25比設定在年齡35好