? 既然上次講到了隨機森林，而隨機森林是由多棵決策樹構成的，現在就回頭仔細看看決策樹。

? 博客園中已經有介紹決策樹的非常好的 博文 。其中詳細介紹了ID3，C4.5決策樹的構造，這篇博文主要關注在樹的每個節點如何確定 最佳分裂屬性 和 剪枝 。

? 1.確定最佳分裂屬性

? 一般介紹決策樹都是以ID3(Quinlan 1986)為例。ID3算法使用的是信息增益，信息增益的具體細節我不再贅述。在決策樹的節點N上，ID3算法選取在該節點對應的訓練樣例集合D上用輸入屬性進行分類后信息增益最大的輸入屬性。信息增益的定義為： 。其中S為節點N上的訓練樣例集合，A為某個輸入屬性。對于所有在節點N上可用的輸入屬性，我們選取信息增益值最大的屬性進行分裂。因為上式中第一項對于所有輸入屬性都是一樣的，所以第二項越小，信息增益值越大。

? 其實，除了信息增益（亦即熵值）之外，還有許多其他方法用來確定最佳分裂屬性。他們都統稱為不純性度量（impurity measure）。使用某個屬性對訓練樣例集進行劃分，如果劃分后每個分支內的所有樣例都屬于同一類，則稱該劃分是純的，如果每個劃分里的樣例屬于很多不同的類，則稱該劃分是不純的。

? 我們用不純性度量來衡量用某個屬性劃分訓練樣例的純潔度，度量值越高表示劃分越不純（因為這是不純性度量，不是純性度量），我們在每個節點上進行分裂時盡量選取不純度低的輸入屬性。上述的熵值可以用作不純性度量，熵值越小，信息增益越大，不純度越小，這種劃分越好。除了熵值之外，還可以采用以下幾種不純度度量方法（僅表示一個劃分內的不純度度量，對于整體劃分的不純度度量可用各劃分的不純度度量值的加權和即可）：

? (1) Gini指數： ，其中fi為該劃分中屬于i分類的訓練樣例的比率，Gini系數是Breiman于1984年提出來的，主要用在CART(Classfication and Regression Tree)中。

? (2)誤分類誤差：1-max(f1,f2,...,fm)。

? 2.剪枝

? 在創建決策樹的過程中，停止分裂的條件是 (1) 該節點處所有的樣例都屬于同一類別 或者 (2) 沒有可以用的輸入屬性。

? 但是按照這樣的停止條件訓練出來的決策樹往往會過度擬合(overfit)訓練數據，亦即該模型對于訓練數據有非常高的分類準確率，但是對于新的數據，分類的準確率較差。有兩種方法可以用來避免過度擬合：

? (1) 及早停止樹增長，亦即先剪枝(prepruning)。

? 比如，如果決策樹中一個節點的訓練樣例的數目小于整個訓練集的某個百分比(如5%)，則該節點不進行分裂，而是對該節點訓練樣例進行"多數表決"。因為基于較少實例的決策樹會導致較大方差，從而導致較大泛化誤差(Generalization Error)。

? (2)后剪枝(postpruning)。

? 后剪枝的方法很多，這里只介紹訓練和驗證集法的一個變種：

? 首先讓決策樹完全增長，然后我們找出過分擬合的子樹并剪裁掉。具體的做法是：我們從之前的訓練數據中取出一部分作為驗證集，其余的還是作訓練集。用訓練集訓練處一個完全增長的決策樹，然后對于決策樹中的每個子樹，我們都用包含該子樹的所有訓練樣例的葉節點來代替，該葉節點的分類為"多數表決"的結果。我們用驗證集來測試替換前后分類性能的變化。如果替換后分類準確性有所上升，則我們有理由認為之前的那個子樹過于復雜，對于訓練集中的訓練樣例過度擬合，所以將之替換為葉節點。否則不予替換。

? 通常的做法是將可用訓練樣例的三分之二作為訓練集，剩余的三分之一作為驗證集。

? 兩種剪枝方法比較，先剪枝比較快，可以再構建決策樹的同時進行。而后剪枝比較慢，要在構造完決策樹之后對于每一個子樹進行替換和驗證，但是其準確性比先剪枝要高。

?

參考文獻：

[1] ?算法雜貨鋪——分類算法之決策樹(Decision tree)

[2] 機器學習 Tom M. Mitchell

[3] 機器學習導論 Ethern Alpaydin

機器學習-決策樹