洪衛

決策樹

　　前幾天學習了《機器學習》的前三章，前三章介紹機器學習的基礎知識，接下來，第四章到第十章介紹一些經典而常用的機器學習方法，這部分算是具體的應用篇，第四章介紹了一類機器學習方法——決策樹。

3.1 基本流程

　　決策樹（decision tree）是一類常見的機器學習方法。以二分類任務為例，我們希望從給定訓練數據集學得一個模型用以對新示例進行分類，這個把樣本分類的任務，可看作對“當前樣本屬于正類嘛？”這個問題的“決策”或“判定”過程。顧名思義，決策樹，就是基于樹結構來進行決策的。例如我們對一個好西瓜的判定過程，如下圖：

　　顯然，決策的最終結論是我們的判斷結果：“是”或者“不是”好瓜。一般的，1、一顆決策樹包含一個根結點、若干個內部結點和若干個葉結點；2、葉結點對應決策結果，其他每個結點則對應一個屬性測試；3、每個結點包含的樣本集合根據屬性測試的結果被劃分到子結點中；4、根結點包含樣本全集。 從根結點到每個葉結點的路徑對應了一個判定測試序列。決策樹學習，目的是產生一棵泛化能力強，即處理未見示例能力強的決策樹，其基本流程遵循簡單且直觀的“分而治之（divide-and-conquer）”策略，算法如下：

　　顯然，決策樹的生成是一個遞歸過程。決策樹算法中，有三種情形會導致遞歸返回：（1）當前結點包含的樣本全屬于同一類別，無需劃分；（2）當前屬性集為空，或者所有樣本在所有屬性上取值相同，無法劃分；（3）當前結點包含樣本集合為空，不能劃分。（在第（2）中情形下，把當前結點標記為葉結點，并將其類別設定為該結點所含樣本最多的類別；在第（3）中情形下，同樣把當前結點標記為葉結點，但將其類別設定為父結點所含樣本最多的類別。這兩種情形處理的實質是不同的，（2）是在利用當前結點的后驗分布，而（3）則把父結點的樣本分布作為當前結點的先驗分布。）

4.2 劃分選擇

　　有算法流程看出，決策樹學習關鍵在第8行，即如何選擇最優劃分屬性，一般而言，隨著劃分過程進行，我們希望決策樹的分支結點所包含的樣本盡可能屬于同一類別，即結點的“純度（purity）”越來越高。

　　4.2.1 信息增益 　

　　“信息熵（information entropy）”是度量樣本集合純度最常用的一種指標。我們假定當前樣本集合D中第k類樣本所占的比例為pk（k=1,2，…，|y|），則D的信息熵定義為：

Ent(D)的值越小，D的純度越高（理想情況就是Ent(D)的值小到0，相當于pk=1，這樣的話D中樣本就全屬于同一類）
　　假定離散屬性a有V個可能的取值{a1, a2, …, aV}，若使用a來樣本集D進行劃分，則產生V個分支結點，其中v個分支結點包含D中所有在屬性a上取值為aV的樣本。根據信息熵定義式計算出Dv的信息熵，在考慮到不同的分支結點的樣本數不同，給分支結點賦予權重|Dv|/|D|，即樣本數越多的分支結點的影響越大，于是可計算出用屬性a對樣本集D進行劃分所取得的“信息增益（information gain）”：

　　所以，信息增益越大，則意味著使用屬性a來進行劃分所獲得的“純度提升”越大，因此，我們可用信息增益來進行決策樹的劃分屬性選擇，即在算法流程4.2圖中第8行選擇屬性。著名的ID3（Iterative Dichotomiser迭代二分器）決策樹學習算法[Quinlan, 1986]就是以信息增益為準則來選擇劃分屬性的。

　　以表4.1中的西瓜數據集2.0為例：

　　該數據集包含17個訓練樣例，用以學習一棵能夠預測沒剝開的是不是好瓜的決策樹。顯然，|y| = 2。在決策樹學習開始時，根結點包含D中的所有樣例，其中正例占p1 = 8/17 ，反例占p2 = 9/17。于是，根據信息熵定義式計算出根結點的信息熵為：

　　然后我們計算出當前屬性集合{色澤，根蒂，敲聲，紋理，臍部，觸感}中每個屬性的信息增益。以屬性“色澤”為例，他有三個可能的取值：{青綠，烏黑，淺白}。若使用該屬性對D進行劃分，這可以劃分為三個子集，分別記為：D1(色澤=青綠)，D2(色澤=烏黑)，D3(色澤=淺白)。子集D1包含編號{1,4,6,10,13,17}的樣例，其中正例占p1 = 3/6 ，反例占p2 = 3/6，同理寫出D2、D3的樣例編號，計算出對應正例，反例比例，就可以根據信息熵定義式算出用“色澤”劃分之后所得到的3個分支結點的信息熵：

　　根據信息增益計算式算出各屬性信息增益：

　　類似的我們可以計算出其他屬性的信息增益：

　　顯然，屬性“紋理”的信息熵最大，于是它被選為劃分屬性。基于“紋理”對根結點進行劃分，進而繼續算出其他各屬性信息增益：

可看出，“根蒂”、“臍部”、“觸感”3個屬性均取得了最大的信息增益，可任意選其中一個最為下一步劃分屬性，類似的，對每個分子結點進行上述操作，最終得到決策樹如圖4.4所示：

　　4.2.2 增益率

　　在上面的劃分中嗎，我們沒有將“編號”這一欄作為劃分屬性，如果以編號作為屬性劃分樣本，將產生17個分支，每個分支結點僅含一個樣本，分支結點的純度最大。然而，這樣決策樹顯然不具有泛化能力，無法對新樣本進行有效預測。
實際上，信息增益準則對可取值數目較多的屬性有所偏好，為減少這種偏好可能帶來的不利影響，著名的C4.5決策樹算法[Quinlan, 1993]不直接使用信息增益，而是使用“增益率（gain ratio）”來選擇最優劃分屬性，增益率定義為：

其中

稱為屬性a的“固有值（intrinsic value）”[Quinlan, 1993].屬性a的可能取值數目越多（即V越大），則IV(a)的值越大。
　　需注意的是，增益率準則對可取值數目較少的屬性有所偏好，因此，C4.5算法并不是直接選擇增益率最大的候選劃分屬性，而是使用了一個啟發式[Quinlan, 1993]：先從候選劃分屬性中找出信息增益高于平均水平的屬性，再從中選擇增益率最高的。

　　4.2.3 基尼指數

　　CART（Classification and Rgression Tree）決策樹[Breiman et al. , 1984]使用“基尼指數（Gini index）”來選擇劃分屬性，與4.1采用相同的符號，數據集D的純度可用基尼值來度量：　　Gini(D)反映了從數據集D中隨機抽取兩個樣本，其類別標記不一致的概率，因此，Gini(D)越小，則數據集D的純度越高。屬性a的基尼指數定義為：

 　　于是，我們在候選屬性集合A中，選擇那個使得劃分后基尼指數最小的屬性作為最優劃分屬性，即

4.3 剪枝處理 　　

　　剪枝（pruning）是決策樹學習算法對付“過擬合”的主要手段。在決策樹學習中，為了盡可能正確分類訓練樣本，結點劃分過程將不斷重復，有時會造成決策樹分支過多，這時就可能因為訓練樣本學得“太好了”，以至于把訓練樣本集自身的一些特點當作所有數據都具有的一般性質而導致過擬合，因此，可通過主動去掉一些分支來降低過擬合的風險。
決策樹剪枝的基本策略有“預剪枝（prepruning）”和“后剪枝（post-pruning）”[Quinlan, 1993]

　　4.3.1 預剪枝

　　4.3.2 后剪枝

4.4 連續與缺失值

　　4.4.1 連續值處理
　　4.4.2 缺失值處理

4.5 多變量決策樹

　?。ㄎ赐甏m）