? 之前泛泛看了下了Random Forest和決策樹，現在落實到一個具體決策樹算法：CART(Classification and Regression Tree)。

? CART是1984年由Breiman, Friedman, Olshen, Stone提出的一個決策樹算法，雖然不是第一個機器學習領域的決策樹，但卻是第一個有著復雜的統計學和概率論理論保證的決策樹(這些話太學術了，引自參考文獻[2])。

? CART是一個二叉決策樹，亦即決策樹的每個內部節點(決策節點)最多有兩個分支。因為之前有 博文 介紹過ID3和C4.5算法，所以這里只從確定最佳分裂屬性和剪枝兩方面介紹CART。

? 1. 確定最佳分裂屬性(和最佳分裂點)

? 我們這里只考慮連續值的情況。對于每個輸入屬性的每個可能的分裂點(分裂點即相鄰兩個連續值的中點)，我們計算每個劃分 Gini指標 ： ，然后對該分裂點的兩個劃分的Gini指標求加權和。我們選取Gini指標最小的那個輸入屬性的分裂點進行劃分。

? 按照以上規則生成一個完全增長的決策樹，不需要任何停止條件。

? 2. 剪枝

? 因為上一步生成的決策樹是沒有停止條件的，所以這個決策樹可能會非常大，對訓練數據很可能會過度擬合，所以需要對決策樹進行后剪枝。

? CART算法采用的是 Cost-Complexy剪枝 :

? 我們用 來衡量一棵子樹的代價復雜度。其中R(T)代表將這個子樹替換為葉子節點后所帶來的誤差的增加，number-of-leaves為子樹T的葉子節點的個數，α不是一個常數，而是一個從0開始增大到無窮大的數。對于決策樹T，我們在α不是一個常數，而是一個從0開始增大到無窮大的數。逐步增加的過程中，每次選擇使Rα最小的子樹，并將之替換為一個葉子節點，對替換后的樹迭代執行以上步驟。

? 上述過程可能略顯復雜，我們可以用另外一個等價的剪枝方法來得到相同的結果： Weakest-Link-Pruning ：

? (1)對于所有的子樹STi，我們試圖用合適的葉子節點來代替STi，然后計算增加的誤差E與STi的葉子節點的比值。我們選擇比值最小的那個子樹STj，用合適的葉子節點代替之。

? (2)重復迭代以上步驟，每次都替換掉一棵子樹。我們會得到從完全增長的樹T0到只有根節點一個決策節點的樹Tn的一系列決策樹：T0,T1,.....Tn。然后我們用獨立的驗證集(我們可以從可用數據集中抽取三分之一作為驗證集，剩下的三分之二作為訓練集)來驗證各個決策樹的分類準確性。選取準確性最高的決策樹為最終的CART決策樹。

參考文獻：

[1] CART算法學習及實現

[2] 機器學習十大算法：CART

[3] Complexity-Based Evaluation Of Rule-Based Expert Systems

?

機器學習-CART決策樹