這可能是你看過的最用心的【決策樹演算法】介紹文章

02-09

決策樹演算法是一個非常常用且優秀的機器學習演算法，它易於理解、可解釋性強，它不需要很多訓練樣本就可以構建一個模型；目前有許多大放異彩的樹提升演算法系統都是基於決策樹構造的，比如我們前面介紹的XGBoost,lightGBM,當然還有沒介紹的Adaboost，隨機森林,GBDT等。本文帶你走入決策樹演算法。

怎麼淺顯的解釋決策樹呢？一個簡單的栗子，如果你是女性，你面臨這一個擇偶的問題，前面有一些男性，於是你在心裡做了一些「決策」來決定選擇誰，把你的決策結果畫下來就是一顆樹了，如下圖

僅做栗子講解，沒有任何其他意思

實際上，上圖的決策過程只是某一個人的決策過程，一般的，一個機器學習演算法需要很多樣本（也就是很多人的決策過程）來進行學習，這樣學習出來的決策樹就可以套用到其他女性身上了，之後就可以依據決策樹來預測這個「其他」的女性是否會嫁給某位男性，我們稱對「其他」女性的決策結果做預測叫做模型的泛化，而我們在學習決策樹的時候，其目的就是學一顆泛化能力最強的樹。從上面的圖可以看出，男性的特徵有三個：高否，富否，帥否，而學習的樹有根節點有中間節點有樹葉，那麼憑什麼就把富否當做根節點，把高否當做最下面的節點呢？跟著我來，慢慢走近真像！

1、屬性劃分選擇

1.1、信息熵

信息熵（information entropy）是度量樣本集合純度的一種常用指標，假如這裡一對男性，裡面有你想嫁的有你不想嫁的，而當這堆男性中如果有且僅有你想嫁的或者不想嫁的，那麼我們就說這個數據集純度很高，因為他們都屬於同一類。

假如樣本集合D中第k類樣本所佔比例為 $p_k$ （k=1,2,...,|y|），則數據集合D的信息熵為：

$Ent(D)=-sum_{k=1}^{|y|}{p_k log_2p_k}$

由上式知道，信息熵的值越小，樣本集合D的純度越高。

1.2、信息增益

信息熵和屬性選擇又有什麼關係呢？已知我們有高，富，帥三個屬性，他們的取值為{0，1}，都是離散屬性，現在我們試著依次對這三個屬性進行劃分，最後計算它們劃分後的信息增益，最後再根據三種劃分的信息增益的大小來確定採用哪個屬性進行劃分。

信息增益的定義如下：

$Gain(D,a) = Ent(D)-sum_{v=1}^{V}{frac{|D^v|}{|D|}Ent(D^v)}$

這裡a表述某個屬性，Gain(D,a)就是對屬性a劃分的信息增益，|D|表示數據集合樣本的總體數量，v={1,2,...,V},表示屬性a的V個取值， $|D^v|$ 表示屬性a取值為v時的樣本集合的子集；一般而言，信息增益越大，那麼意味著使用屬性a來劃分所獲得的「純度提升」越大。因此，遍歷所有屬性分別計算信息增益，信息增益最大的那個屬性將作為劃分屬性。

ID3決策樹演算法的屬性劃分就是使用的信息增益。

1.3、增益率

事實上，根據信息增益的公式可以看出，當v的取值越多時，也就是當a的取值越多，那麼信息增益Gain(D,a)的取值將會越大，也就是說使用信息增益來選擇劃分屬性時，它偏向於選擇那些取值多的屬性進行劃分，顯然這樣的劃分不具有良好的泛化能力。於是有了使用增益率來選擇劃分屬性。增益率定義如下：

$Gain\_ratio=frac{Gain(D,a)}{IV(a)}, where IV(a)=-sum_{v=1}^{V}{frac{|D^v|}{D}log_2frac{|D^v|}{D}}$

IV（a）稱為屬性a的「固有值」，屬性a 的取值數目越多，則其越大，這樣就平衡了信息增益對取值較多的屬性的偏好；然而增益率又會對取值數目較少的屬性有偏好，因此又有一個「啟發式」的規則：先從候選劃分屬性中找出信息增益高於平均水平的屬性，再從中選擇增益率最高的。

C4.5決策樹演算法採用增益率指標選擇劃分屬性。

1.4、gini指數

樣本集合數據集的純度除了可以用熵來衡量外，也可以用基尼值來度量：

$Gini(D)=sum_{k=1}^{|y|}{sum_{k e k}^{}{p_kp_{k}}}=1-sum_{k=1}^{|y|}{p_k^2}$

基尼值反映了從數據集中隨機抽取兩個樣本，其類別標記不一致的概率，因此基尼值越小，則數據集純度越高。

對屬性a進行劃分，則屬性a的基尼指數定義為：

$Gini\_index(D,a)=sum_{v=1}^{V}{frac{|D^v|}{|D|}Gini(D^v)}$

因此，在選擇劃分屬性時，應該選擇那個使得劃分之後基尼指數最小的屬性作為劃分屬性。

CART使用基尼指數作為屬性劃分指標。

那麼到底使用基尼指數還是熵來進行屬性劃分選擇呢？其實大部分時候它們兩種屬性劃分選擇方式所生產的決策樹基本相同，但gini值的計算更快一些，因此在sklrean中默認的劃分方式就是gini指數，默認的決策樹是CART樹；但是gini指數的劃分趨向於孤立數據集中數量多的類，將它們分到一個樹葉中，而熵偏向於構建一顆平衡的樹，也就是數量多的類可能分散到不同的葉子中去了。

2、決策樹的正則化

使用一個訓練樣本集合來生成一個決策樹，如果不做任何限制，讓決策樹隨意生長，那麼決策樹將擬合所有訓練樣本使得訓練正確率達到100%；毫無疑問這是沒有意義的，因為它完全過擬合了，這樣的決策樹不具有泛化能力。那麼決策樹是怎樣來防止過擬合呢？一般的措施是將生產的決策樹進行剪枝，預剪枝或者後剪枝。

預剪枝是指在決策樹生成過程中，對每個結點在劃分前先進行估計，若當前結點的劃分不能帶來決策樹泛化能力（在訓練時加入驗證集隨時進行泛化驗證）的提升，則停止劃分並將當前結點標記為葉節點；後剪枝則是先從訓練集中生成一顆完整的樹，然後自底向上對非葉節點進行考察，若該節點對應的子樹替換為葉節點能夠提升泛化能力，則進行剪枝將該子樹替換為葉節點，否則不剪枝。

很明顯，預剪枝技術抑制了很多分支的展開，這降低過擬合的同時還減少了訓練時間，但是卻存在欠擬合的風險；預剪枝基於「貪心」策略，往往可以達到局部最優解卻不能達到全局最優解，也就是說預剪枝生成的決策樹不一定是最佳的決策樹。XGBoost和lightGBM使用的樹就是預剪枝的CART決策樹，這能保證他們的訓練速度較快，但是準確率如何保證呢？你知道嗎，我們大概在講隨機森林的時候再提這點。。

後剪枝技術通常比預剪枝保留了更多的分支，它是自底向上的剪枝，因此它的欠擬合風險較小，泛化能力往往優於預剪枝，然而因為總是要完全生長一棵樹，這就要花費很多時間訓練了，數據集規模大、維度高時並不適用實際應用。

在sklearn中，決策樹通常是通過設置超參數來進行正則化的。

from sklearn.datasets import load_irisfrom sklearn.tree import DecisionTreeClassifieriris = load_iris()X = iris.data[:, 2:] # petal length and width y = iris.targettree_clf = DecisionTreeClassifier(max_depth=2)tree_clf.fit(X, y)

上述代碼中通過設置max_depth來限制決策樹的層數，這在一定程度上防止了過擬合，這也是一種預剪枝的方案。

上式是CART決策樹的損失函數，決策樹遞歸生長，當生長到最大深度或者不能再通過分裂節點達到減少數據純度的時候，遞歸過程就結束。

根據不同決策樹演算法，防止過擬合的參數有一些不同，但max_depth是通用的；其他的一些參數：

min_samples_split：節點在分裂之前必須具有的最小樣本數。也就是，如果該節點上的樣本數量小於參數設置的數目時，不管怎樣，這個節點也不再分裂。

min_samples_leaf：葉節點必須擁有的最少樣本數。如果分裂一個節點生成一些葉子，而某個葉子上的樣本數量少於參數設置的值時，將不將這些樣本單獨作為一個葉子。

min_weight_fraction_leaf：和上面一個參數差不多，但表示為加權實例總數的一小部分。

max_leaf_nodes：葉子節點的最大數量。

max_features：對每一個節點評估是否分裂所需要的最少特徵數量。

上圖展示了使用min_samples_leaf參數限制和不限制所生產的決策樹，很顯然，第一個不做限制的決策樹過擬合了。

3、回歸決策樹

以上內容基本在講分類決策樹，決策樹除了可以用來做分類任務還可以用來做回歸任務。

from sklearn.tree import DecisionTreeRegressor tree_reg = DecisionTreeRegressor(max_depth=2)tree_reg.fit(X, y)

上述代碼生成了一顆深度為2的回歸決策樹，

從上圖可以看出，回歸決策樹將訓練數據集按照儘可能的緊密的將其劃分為不同區域（黑色實線和虛線），對摸一個實例的預測值就是這個區域中所有值的平均值（紅色線條）。

在分類任務重，決策樹劃分屬性是最小化數據集的不純度，而在回歸任務重，演算法劃分屬性的原則是最小化MSE：

和分類一樣，回歸也可能過擬合，如下圖所示，左邊是不對決策樹進行任何限制，右邊設置參數min_samples_leaf為10，很顯然右邊的模型更好一點。

4、連續值和缺失值處理

在擇偶三連那個例子中我們使用的屬性取值都是離散的，且數據都是完整的，那麼當數據是連續的，或者有確實值，那麼該怎麼辦呢？

4.1、連續值處理

在lightGBM中，我們介紹了，它通過直方圖演算法將連續變數映射成一個個的bins，然後將bins看做離散變數再逐一計算那個分裂節點最優。而一般的決策樹處理連續變數卻是只將連續變數做離散二值化。給定樣本集合D和連續屬性a，如果a的取值有n個不同的取值，分別為 ${a^1,a^2,...,a^n}$ ，那麼基於劃分點t可以將數據集D劃分為 $D_t^-,D_t^+$ ，他們分別包含那些屬性a上取值不大於t的樣本和大於t的樣本。因此對連續屬性a我們有n-1個候選劃分節點：

$T_a={frac{a^i+a^{i+1}}{2}|1ll ill n-1}$

信息增益為：

$Gain(D,a)=max_{tin T_a} Gain(D,a,t)=max_{tin T_a} Ent(D)-sum_{lambdain T_a}^{}{frac{|D^lambda|}{|D|}Ent(D_t^lambda)}$

這樣，可以在連續取值中選擇一個最佳分裂節點。與離散屬性不同，若當前結點劃分屬性為連續值，該屬性還可以作為其後代節點的劃分屬性。

4.2、缺失值處理

很多演算法要求訓練數據集不能有缺失值，所以有了各種插值方法，但是決策樹可以很好的「包容」缺失值，不必要事先對缺失值做任何處理。在介紹XGB時，我們說過它是可以自動默認將有缺失值的屬性進行劃分的，不記得的話建議回去翻一翻哦。

那麼在一般決策樹中，演算法是如何處理缺失值的呢？即如何在屬性缺失的情況下進行劃分屬性選擇？給定劃分屬性，若樣本在該屬性上的值缺失，如何對樣本進行劃分？

上面兩張照片來自周志華的《機器學習》。

5、多變數決策樹

決策樹有很多優勢，但是也有他的限制。決策樹形成的分類邊界有一個明顯的特點，就是軸平行，它的分類邊界由若干個與坐標軸平行的分段組成。雖然他的可解釋性很好，但是在真實分類邊界比較複雜時，必須使用多段劃分才能獲得較好近似，如下圖所示：

這樣勢必增加了模型的複雜度，在預測時，預測時間開銷就比較大。

而多變數決策樹能很好的解決這個問題，它的決策節點不再是針對某個屬性，而是對屬性的線性組合，也就是每個節點是一個形如 $sum_{i=1}^{d}{w_ia_i=t}$ 的線性分類器。（由於這部分我並沒有動手去實現或者使用過現成的以實現演算法，所以就講到這裡了。。。如果有了解的朋友歡迎指點- -）。

參考資料：

周志華，《機器學習》
李航，《統計學習方法》
Aure?lien Ge?ron，《 Hands-On Machine Learning with Scikit-Learn and TensorFlow》

未經授權，請勿轉載