決策樹之ID3和C4.5

一、決策樹

一種樹狀分類結構模型，是一種通過對變數值拆分建立起來的分類規則，又利用樹形圖分割形成的概念路徑的數據分析技術。

二、決策樹的兩個關鍵步驟

三、決策樹的構建步驟

註：

⑴第一步中：先找出各個可以作為分類變數的自變數的所有可能的劃分條件，再對每一個自變數比較各個劃分下所得到的兩個分支的差異大小，差異最大的劃分條件作為該自變數的最優劃分。

⑵第二步中：①剪枝很有可能剪掉的就是雜訊和離群點，但是在金融風控領域中這些離群點才更有可能使我們關注的對象。②數據是在一直持續劃分直至在一個分區中特徵無區別，因此決策樹很容易出現過度擬合的現象。③對於大規模的數據量，可以使用預剪枝的方法，來對決策樹進行剪枝。

什麼叫過度擬合？來複習一下。

在學習期間，它可能包含了訓練數據中的某些特定的異常，這些異常不會在一般數據集中出現。

⑶第四步中：可以利用混淆矩陣、ROC曲線、AUC值等等模型評估指標來對我們的模型進行評估。

四、演算法的理論知識介紹

下面我們對ID3演算法、C4.5演算法以及CART演算法進行理論上的分享。我們用用的是韓家煒老師書中的一個小案例。

為了在敘述演算法的時候方便，我們用A來表示age變數，用D來表示最後的類別class。

1、ID3演算法

在演算法中，最主要的就是信息增益，選擇具有最高信息增益的屬性作為節點N的分裂屬性，該屬性使得結果分區對元組分類所需要的信息量最小。屬性A的信息增益表示如下：

大家現在是不是對公式有點暈，我們以上面的例子來看一下屬性A的信息增益：

⑴首先給出信息熵的定義：

某一信源發出某一消息所含有的信息量，用平均自信息量表示，一般選用以

2、為底表示

用下圖對概率和信息的關係進行表示：

不確定性越大，比如概率都是0.5(類似於拋硬幣)，所含有的信息量越大。

⑵下面給出對D中元組分類所需要的期望信息：

Info(D)=-[(5/14)*log(5/14)+ (9/14)*log(9/14)

⑶下面給出Infoa(D)(上面公式的第二項的解釋)，它是基於屬性A對D的元組進行分類所需要的期望信息，需要的信息越小，分區的純度越高。

太書面話了，白話來一下，按照上面說的信息量，假如A自帶的信息越少，就表明用A這個變數來對元組進行區分越容易，那麼說這也印證了上面的一句話：選擇具有最高信息增益的屬性作為節點N的分裂屬性，曉得了吧！

下面我們來計算Infoa(D)：首先我們觀察上面的表格，可以用下面的表格表示相關信息

首先我們先看公式中的每一個Dj，young有5個元組，middle_aged有4個元組，senior有5個元組，下面我們再來看young下面有3個no，2個yes；middle_aged下面全部是yes，senior下面有3個yes，2個no。

所以Infoa(D)的計算為：

Infoa(D)=(5/14)*[-2/5log(2/5)- 3/5log(3/5)]+ (4/14)*[-0/4log(0/4)- 4/4log(4/4)]+(5/14)*[-2/5log(2/5)- 3/5log(3/5)]

註：我們是不是發現按照age分類，我們已經把middle_aged全部分為了yes。

⑷上面的變數，比如age，是通過泛化，將連續的數值變數變成了離散的分類變數，在處理連續值的時候，我們可以讓值遞增排序，每對相鄰值得中點作為分類點，這樣如果有x個值，就有可能有x-1個可能的劃分，再從中尋找最優的劃分。

⑸ ID3演算法的總結

2、C4.5演算法

選擇具有最高信息增益率的屬性作為節點N的分裂屬性，這樣避免了偏袒的可能性。

即：在ID3演算法的基礎上除以否個變數的熵。

註： C4.5演算法傾向於產生不平衡的劃分，其中的一個分區比其他分區小得多。

五、ID3演算法的演示

1、首先，我們計算上面4個變數的信息增益，其中：age變數的為0.246，income變數的為0.029，student變數的為0.151，credit_rating變數的為0.048，因此第一次選擇我們選擇age變數來進行樹的分叉。

2、機智的你肯定已經發現對於左邊的表格，下一次用student來進行分叉，對於右邊的表格，用credit_rating來進行分叉，中間的表格已經搞定了吧！

-----------------------------------

作者：張龍祥

專欄：張小胖專欄

大家也可以加小編微信：tswenqu （備註:知乎），進R語言中文社區 交流群，可以跟各位老師互相交流