聊聊機器學習中的那些樹

03-03

樹模型是機器學習領域內，除了深度學習之外，使用的最為廣泛，也是變種特別多的一種模型了，樹模型的好處是其很容易理解，且相對不容易過擬合，訓練時對資源的消耗也更少。最常用樹模型包括決策樹，隨機森林及XGBoost。而在去年，南大的周志華教授提出了deep forest，一種借鑒深度學習的樹模型，樹模型還有其他的更為冷門的變種，例如正則化貪心森林和。這篇文章將始簡單的介紹下上述的幾種樹模型的原理，樹模型是最容易理解的，請您放心，本文只有一個公式，是關於信息熵的。

樹模型主要用來做分類。最簡單的一種叫做決策樹，決策樹是一個非常接近人類思維的模型。它形象的說就是一個調查問卷，把一個最終的決策轉化為個若干問題，每一步得到一個答案，按照答案的正否來決定下一個問題是什麼，如此形成一個樹結構，最後形成一個分類器。比如經常被舉出的例子，你要買電腦，要根據很多特徵挑選電腦，比如cpu，gpu，硬碟，內存等，你一定會問你自己一系列問題，我要買那款cpu，gpu，硬碟，內存等，最後做出決策。決策樹要做的是把這個過程自動化，最後給我們我們希望的判定結果。

在一棵決策樹上，其中的節點可以分成根節點（藍色）決策節點（紅色）和終止節點（綠色），而圖中的方框里包含的即是一顆子樹，這麼看來，樹模型是不是特別好理解？樹模型的第二個好處是可以方便的探索數據中那些維度更加重要（對做出正確的預測貢獻更大），比如上述的買電腦的例子，你會發現對於大多數人來說，CPU的型號最關鍵。樹模型的第三個好處是不怎麼需要做數據清洗和補全，還用買電腦的例子，假設你拿到的數據部分中沒有告訴GPU的型號，你不必要丟掉這部分數據，進入到相應的子樹里，隨機的讓這條數據進入一個終止節點就好了，這樣，你便能夠利用缺失的數據了。

談起樹模型，就要說起基尼係數，這個指數最常見的場景是描述貧富差距，但也可以用來指導樹模型在那裡分叉。假設一顆最簡單做二分類問題的決策樹，拿到的數據分為兩種特徵，一個是性別，一個是班級，預測學生們願不願打板球，下面的圖是兩種不同的樹模型，用性別來分，10個女生中有2個願意打球，而20個男生中有13個願意打球，而用班級分，效果則沒有那麼好，具體怎麼計算了，先從左到右依次計算每個終止節點的基尼係數，(0.2)*(0.2)+(0.8)*(0.8)=0.68 (0.65)*(0.65)+(0.35)*(0.35)=0.55 (0.43)*(0.43)+(0.57)*(0.57)=0.51 (0.56)*(0.56)+(0.44)*(0.44)=0.51，之後對每棵樹的基尼係數進行加權平均：10/30)*0.68+(20/30)*0.55 = 0.59（按性別分），(14/30)*0.51+(16/30)*0.51 = 0.51（按班級分），因此在該例子中，性別是一個更好的特徵。

理解決策樹的下一個重要的概念是信息增益，信息可以看成是減少了多少系統中的無序，而描述系統的無序程度，可以用信息熵，對於二分類問題，計算公式是

對於每一次樹上的分叉，先算下父節點的熵，再計算下子節點的熵的加權平均，就可以計算出決策樹中的一個決策節點帶來了多少信息增益了。

信息熵公式告訴我們的是，我們每次對所有特徵都掃描一遍，選擇那個讓我們的信息增長最大的特徵。依次在這個特徵的每個可能取值下，我們在尋找第二個關鍵特徵，列出第二個特徵選的可能取值並尋找第三個特徵依次類推。再對每一分支的操作里，如果我們發現在某個特徵組合下的樣本均為一類，則停止分叉的過程。整個操作過程形似尋找一顆不斷分叉的樹木，故名決策樹。

決策樹能夠處理特徵之間的互相影響，因為特徵之間的互相影響，我們並不像簡單貝葉斯那樣並列的處理這些特徵。例如某個特徵可能在某個條件下式好的，但在另外條件下就是壞的或者沒影響。比如說找對象，你只在對方漂亮的時候才care他學歷。我會根據之前問過的問題的答案來選擇下一步問什麼樣的問題，如此，我就能很好的處理特徵之間的關聯。

我們把這樣的思維步驟寫成偽代碼，大概是這樣的 :

訓練集D （x1，y1）….

屬性 A attribute （a1，a2…..）

函數treegenerate

1, 生成結點node A（任選一個特徵）

2，判斷D在A中樣本是否都屬於類型C，是則A標記為C類葉結點，結束

3，判斷A為空或D在A樣本取值同（x相同而非y），將node 標記為樣本多數分類的葉結點（max numbers），結束

終止條件不成立則:

從A中選擇最優劃分屬性a*,

循環:

對A*上的每一個值a*做如下處理：

If a*上的樣本為空，則a*為葉節點（該值下用於判斷的樣本不足，判定為A*中樣本最多的類），

如果支點上的樣本集為D**

如果存在某個位置，使得D**為空，

則A*為葉節點，

否則，以a*為分支節點，回到第一句

接下來我們看一看更為複雜的情況，比如我們拿到的數據特徵不是兩個，而是一百個，那麼問題來了，我們的決策樹也要100層那麼深嗎？如果真的這麼深，那麼這個模型很容易過擬合的，任何一顆決策樹的都應該有終止條件，例如樹最深多少層，每個節點最少要有多少樣本，最多有多少個終止節點等，這些和終止條件有關的超參數設置決定了模型會不會過擬合。

下面我們從一棵樹過度到一群數，也就是機器學習中常用的begging，將原來的訓練數據集分成多份，每一份分別訓練一個分類器，最後再讓這些分類器進行投票表決。

而隨機森林，就是使用bagging技巧加持的決策樹，是不是很簡單？相比於決策樹，隨機森林的可解釋性差一些，另外對於標籤為連續的回歸問題，隨機森林所採取的求多個樹的平均數的策略會導致結果的不穩定。

隨機森林是將訓練數據隨機的分成很多類，分別訓練很多分類器，再將這些分類器聚合起來，而boosting則不講訓練數據分類，而是將弱分類器聚合起來，下圖的上半部分可以看成描述了三個弱分類器，每一個都有分錯的，而將他們集合起來，可以得出一個準確率比每一個弱分類器都高的分類模型。

你需要做的是將第一個分類器分類分錯的部分交給第二個分類器，再將第二個分類器分錯的部分交給第三個分類器，如下圖依次所示

最終得到了我們看到的強分類器。

總結來看，bagging類似於蟻群的智慧，沒有一隻螞蟻知道全部的信息，但利用螞蟻的集合，可以實現集愚成智，而boosting則是三個臭皮匠，勝過諸葛亮。Boost方法包含的非線性變換比較多，表達能力強，而且不需要做複雜的特徵工程和特徵變換。但不同於隨機森林，它是一個串列過程，不好並行化，而且計算複雜度高。

XGBoost 是 Extreme Gradient Boosting （極端梯度上升）的縮寫，是當下最常用的樹模型了，是上圖描述的Boosting Tree的一種高效實現，在R，Python等常用的語言下都有對應的包，它把樹模型複雜度作為正則項加到優化目標中，從而避免了過於複雜而容易過擬合的模型。

在Boost方法中，每一個被錯誤分類的樣本的權值會增加，以強調最困難的情況，從而使得接下來的模型能集中注意力來處理這些錯誤的樣本，然而這種方法把基於學習器的決策樹視為一個黑盒子，沒有利用樹結構本身。而Regularized Greedy Forest正則化貪心森林(RGF)會在當前森林某一步的結構變化後，依次調整整個森林中所有決策樹對應的「葉子」的權重，使損失函數最小化。例如下圖我們從原來的森林中發下右下的節點可以分叉，我們做的不止是將分叉後的樹加入森林，而且對森林中已有的樹中的對應節點也進行類似的分叉操作。

類似boost，RGF中每個節點的權重也要不斷優化，但不同的是，RGF不需要在梯度下降決策樹設置所需的樹尺寸（tree size）參數（例如，樹的數量，最大深度）。總結一下RGF是另一種樹集成技術，它類似梯度下降演算法，可用於有效建模非線性關係。

下面說說去年周志華教授提出深度森林deep forest，也叫做 gcForest，這也是一種基於決策樹的集成方法，下圖中每一層包括兩個隨機森林（藍色）和兩個complete random forests（黑色），所謂complete random forest，指的是其中的1000棵決策樹的每個節點都隨機的選擇一個特徵作為分裂特徵，不斷增長整棵樹，直到剩餘所有樣本屬於同一類，或樣本數量少於10。

至於每一層的輸出，也不是傳統決策樹的一個標籤，而是一個向量。圖中的每一個森林對每個輸入樣本都有一個輸出，對應建立該決策樹時，落在該葉子節點中的樣本集合中各個類別的樣本所佔的比例，如下圖所示，將多顆樹的結果求平均，得出這一層的輸出。為了避免過擬合，每個森林中 class vector 的產生採用了 k 折交叉驗證的方法，隨機的將k分之一的訓練樣本丟出去，再對k次訓練的結果求平均值。

deep forest還採取了類似卷積神經網路的滑動窗口，如下圖所示，原始樣本的為400維，定義一個大小為100的滑動窗口，將滑動窗口從原特徵上依次滑過，每次移動一步，每次窗口滑動獲取的100個特徵作為一個新的實例，等效於在400維特徵上每相鄰100維的特徵摘出來作為一個特徵實例，得到301個新的特徵實例（400 - 300 + 1）。

深度森林的源代碼也在Github上有開源版，總結一下，深度森林具有比肩深度神經網路的潛力，例如可以層次化的進行特徵提取及使用預訓練模型進行遷移學習，相比於深度學習，其具有少得多的超參數，並且對參數設置不太敏感，且在小數據集上，例如手寫數字識別中，表現的不比CNN差。深度森林的數據處理流如下圖所示。

總結下，樹模型作為一個常見的白盒模型，不管數據集的大小，不管是連續的回歸問題還是分類問題都適用。它不怎麼需要進行數據預處理，例如補全缺失值，去除異常點。樹模型可以針對特徵按照重要性進行排序，從而構造新的特徵或從中選出子集來壓縮數據。樹模型可以通過統計的方式去驗證模型的準確值，判斷訓練的進展，相比機器學習的模型，需要調整的超參數也更少。但和神經網路一樣，樹模型也不夠健壯，如同圖像上只需要改變幾個像素點就可以改變模型的結果，樹模型中輸入數據的微小變化也可能會顯著改變模型的結果。樹模型也有過擬合的危險，通過剪紙purning，即先讓樹長的深一些，再去除那些不帶來信息增益的分叉，留下那些最初的信息增益為負，但整體的信息增益為正的節點，可以組織樹模型的過擬合。