學習筆記之——決策樹

決策樹（Decision Tree）應該算是機器學習（Machine Learning）中最簡單的分類模型之一，而且由於決策樹邏輯規則清晰，它的可解釋性比較強。在實務中，決策樹通常是分類學習模型的第一選擇。

決策樹有三種演算法，分別為ID3、C4.5和CART（Classification and Regreesion Tree），區別主要在於節點分裂時基於的標準不同。ID3的分裂標準是讓分裂前後數據集的信息熵（Entropy）差異，即信息增益最大化。信息熵的概念來源於資訊理論，由數學家香農（Shannon）提出，用來刻畫系統的不確定性。系統的熵值越大，則系統不確定性越大。C4.5是ID3的升級版，刻畫標準由信息增益改成信息增益率，來修正ID3通常傾向於選擇特徵取值較多的特徵進行分類的問題。

現在機器學習中流行的決策樹演算法是CART。由名字可以看出，CART既可以用來做回歸，也可以用來做分類。我們這裡只討論用CART來學習分類器。實際上，CART的回歸功能也是可以用來分類的，在集成學習（Ensemble Learning）中GBDT（Gradient Boosting Decision Tree）模型正是用回歸的CART作為基學習器，這個原理類似邏輯回歸（Logistic Regression）。CART決策樹是一個二叉樹，比較直觀易解釋，它的分裂標準是使分裂前後基尼係數（Gini Index）差值最大。基尼係數跟信息熵的性質基本相似，也是刻畫系統不確定性和純度的量。

CART決策樹生成流程大致如下：

1、計算訓練數據集的基尼係數；

2、計算每個屬性分裂後訓練數據集的基尼係數，選擇差異最大的分裂特徵和分裂值；

3、重複上述過程，直到達到停止標準，比如葉子節點包含樣本不得低於某個設定值等等。

看這個樹的生成流程，應該就能看出決策樹為什麼受歡迎了。跟其他分類演算法比，決策樹實現過程非常簡單，沒有什麼特別的假設或者複雜的運算。

在Matlab用UCI中的紅酒數據集Wine（http://archive.ics.uci.edu/ml/datasets/wine）來試試CART決策樹。Wine數據集是義大利同一地區三類不同的紅酒，共有178個觀測，13個關於紅酒的特徵（Alcohol,Malic acid,Ash,Alcalinity of ash,Magnesium,Total phenols,Flavanoids,Nonflavanoidphenols,Proanthocyanins,Colorintensity,Hue,OD280/OD315 of diluted wines,Proline，我也不知道怎麼翻譯，懂紅酒的朋友應該知道），以及13個特徵相對應的紅酒分類（1類、2類和3類）。現在要做的就是，從這個歷史數據集，找出將紅酒分類的規則。這樣，當新產出一隻紅酒，根據這隻紅酒的13個特徵取值，就可以根據規則判斷出這隻紅酒屬於1類酒、2類酒還是3類酒。

初步得到的CART決策樹如下（做了一個簡單的限制，每個父節點包含樣本數不小於10），可以看到，得到的決策樹還是比較簡單的，分類規則也是非常清晰的。同時，可以看到13個特徵並沒有全部用到，而是很自然地選擇出了相對重要的特徵進行分類。

CART決策樹模型有個比較突出的問題，就是很容易過擬合（Over fitting）。所謂過擬合就是模型太聽話了，照單全收訓練集的信息，包括噪音，對訓練集擬合地很好，甚至好過頭了。這會導致訓練出來的模型用來對新數據進行分類預測時，效果卻不是很好，即泛化能力比較弱。這也契合過猶不及的思想，太好了就會被發好人卡。具體到CART決策樹，就需要對生成的決策樹進行剪枝，一是使模型變得更為簡單，二是提高模型的泛化能力。

CART決策樹剪枝用的CCP方法（Cost-Complexity Pruning）。CCP大致的思想是計算剪去某段子樹時，在錯誤率和複雜度之間做一個平衡，從中找到綜合影響最小的一段子樹剪去，照此規則依次剪下去，直至只剩根節點，這就形成了一列供選擇剪枝的樹。接著，可以用交叉驗證（cross-validation）方法，在這一列樹中找到最優的樹，這裡用k-fold交叉驗證。最優樹的選擇一般有兩個標準，一是使交叉誤差最小，二是1-SE（1-standard error）原則，即選擇在最小交叉誤差的1個標準誤範圍內的樹。根據我個人的使用經驗，我的建議是最好放寬一點，使用1-SE原則。據此，可以計算出最佳子樹bestlevel為2，最優CART決策樹具體如下：

至此，可用得到最優決策樹分類器對紅酒進行分類。

La Fin.

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！