樹模型是機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)，除了深度學(xué)習(xí)之外，使用的最為廣泛，也是變種特別多的一種模型了，樹模型的好處是其很容易理解，且相對不容易過擬合，訓(xùn)練時對資源的消耗也更少。最常用樹模型包括決策樹，隨機(jī)森林及XGBoost而在去年，南大的周志華教授提出了deep forest，一種借鑒深度學(xué)習(xí)的樹模型，樹模型還有其他的更為冷門的變種，例如正則化貪心森林和。這篇文章將始簡單的介紹下上述的幾種樹模型的原理，樹模型是最容易理解的，請您放心，本文只有一個公式，是關(guān)于信息熵的。
樹模型主要用來做分類。最簡單的一種叫做決策樹，決策樹是一個非常接近人類思維的模型。 它形象的說就是一個調(diào)查問卷， 把一個最終的決策轉(zhuǎn)化為個若干問題， 每一步得到一個答案， 按照答案的正否來決定下一個問題是什么，如此形成一個樹結(jié)構(gòu)， 最后形成一個分類器。 比如經(jīng)常被舉出的例子， 你要買電腦， 要根據(jù)很多特征挑選電腦，比如cpu，gpu，硬盤，內(nèi)存等， 你一定會問你自己一系列問題， 我要買那款cpu，gpu， 硬盤， 內(nèi)存等，最后做出決策。決策樹要做的是把這個過程自動化，最后給我們我們希望的判定結(jié)果。
Cpu
Gpu
內(nèi)存
決策
高
中
低
買
高
高
中
買
高
中
低
不買
在一棵決策樹上，其中的節(jié)點可以分成根節(jié)點（藍(lán)色） 決策節(jié)點（紅色）和終止節(jié)點（綠色），而圖中的方框里包含的即是一顆子樹，這么看來，樹模型是不是特別好理解？樹模型的第二個好處是可以方便的探索數(shù)據(jù)中那些維度更加重要（對做出正確的預(yù)測貢獻(xiàn)更大），比如上述的買電腦的例子，你會發(fā)現(xiàn)對于大多數(shù)人來說，CPU的型號最關(guān)鍵。樹模型的第三個好處是不怎么需要做數(shù)據(jù)清洗和補(bǔ)全，還用買電腦的例子，假設(shè)你拿到的數(shù)據(jù)部分中沒有告訴GPU的型號，你不必要丟掉這部分?jǐn)?shù)據(jù)，進(jìn)入到相應(yīng)的子樹里，隨機(jī)的讓這條數(shù)據(jù)進(jìn)入一個終止節(jié)點就好了，這樣，你便能夠利用缺失的數(shù)據(jù)了。
談起樹模型，就要說起基尼系數(shù)，這個指數(shù)最常見的場景是描述貧富差距，但也可以用來指導(dǎo)樹模型在那里分叉。假設(shè)一顆最簡單做二分類問題的決策樹，拿到的數(shù)據(jù)分為兩種特征，一個是性別，一個是班級，預(yù)測學(xué)生們愿不愿打板球，下面的圖是兩種不同的樹模型，用性別來分，10個女生中有2個愿意打球，而20個男生中有13個愿意打球，而用班級分，效果則沒有那么好，具體怎么計算了，先從左到右依次計算每個終止節(jié)點的基尼系數(shù)，(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，之后對每棵樹的基尼系數(shù)進(jìn)行加權(quán)平均 ：10/30)*0.68+(20/30)*0.55 = 0.59（按性別分），(14/30)*0.51+(16/30)*0.51 = 0.51（按班級分），因此在該例子中，性別是一個更好的特征。
理解決策樹的下一個重要的概念是信息增益，信息可以看成是減少了多少系統(tǒng)中的無序，而描述系統(tǒng)的無序程度，可以用信息熵，對于二分類問題，計算公式是
。
對于每一次樹上的分叉，先算下父節(jié)點的熵，再計算下子節(jié)點的熵的加權(quán)平均，就可以計算出決策樹中的一個決策節(jié)點帶來了多少信息增益了。
信息熵公式告訴我們的是，我們每次對所有特征都掃描一遍，選擇那個讓我們的信息增長最大的特征。 依次在這個特征的每個可能取值下，我們在尋找第二個關(guān)鍵特征，列出第二個特征選的可能取值并尋找第三個特征依次類推。 再對每一分支的操作里， 如果我們發(fā)現(xiàn)在某個特征組合下的樣本均為一類， 則停止分叉的過程。 整個操作過程形似尋找一顆不斷分叉的樹木， 故名決策樹。
決策樹能夠處理特征之間的互相影響， 因為特征之間的互相影響，我們并不像簡單貝葉斯那樣并列的處理這些特征。 例如某個特征可能在某個條件下式好的， 但在另外條件下就是壞的或者沒影響。 比如說找對象，你只在對方漂亮的時候才care他學(xué)歷。 我會根據(jù)之前問過的問題的答案來選擇下一步問什么樣的問題， 如此， 我就能很好的處理特征之間的關(guān)聯(lián)。
我們把這樣的思維步驟寫成偽代碼， 大概是這樣的 :
訓(xùn)練集D （x1，y1）….
屬性 A attribute （a1，a2…..）
函數(shù)treegenerate
1, 生成結(jié)點node A（任選一個特征）
2， 判斷D在A中樣本是否都屬于類型C，是則A標(biāo)記為C類葉結(jié)點， 結(jié)束
3， 判斷A為空或D在A樣本取值同（x相同而非y），將node 標(biāo)記為樣本多數(shù)分類的葉結(jié)點（max numbers），結(jié)束
終止條件不成立則:
從A中選擇最優(yōu)劃分屬性a*,
循環(huán):
對A*上的每一個值a*做如下處理：
If a*上的樣本為空，則a*為葉節(jié)點 （該值下用于判斷的樣本不足，判定為A*中樣本最多的類），
如果支點上的樣本集為D**
如果存在某個位置，使得D**為空，
則A*為葉節(jié)點，
否則，以a*為分支節(jié)點，回到第一句
接下來我們看一看更為復(fù)雜的情況，比如我們拿到的數(shù)據(jù)特征不是兩個，而是一百個，那么問題來了，我們的決策樹也要100層那么深嗎？如果真的這么深，那么這個模型很容易過擬合的，任何一顆決策樹的都應(yīng)該有終止條件，例如樹最深多少層，每個節(jié)點最少要有多少樣本，最多有多少個終止節(jié)點等，這些和終止條件有關(guān)的超參數(shù)設(shè)置決定了模型會不會過擬合。
下面我們從一棵樹過度到一群數(shù)，也就是機(jī)器學(xué)習(xí)中常用的bagging，將原來的訓(xùn)練數(shù)據(jù)集分成多份，每一份分別訓(xùn)練一個分類器，最后再讓這些分類器進(jìn)行投票表決。
而隨機(jī)森林，就是使用bagging技巧加持的決策樹，是不是很簡單？相比于決策樹，隨機(jī)森林的可解釋性差一些，另外對于標(biāo)簽為連續(xù)的回歸問題，隨機(jī)森林所采取的求多個樹的平均數(shù)的策略會導(dǎo)致結(jié)果的不穩(wěn)定。
隨機(jī)森林是將訓(xùn)練數(shù)據(jù)隨機(jī)的分成很多類，分別訓(xùn)練很多分類器，再將這些分類器聚合起來，而boosting則不講訓(xùn)練數(shù)據(jù)分類，而是將弱分類器聚合起來，下圖的上半部分可以看成描述了三個弱分類器，每一個都有分錯的，而將他們集合起來，可以得出一個準(zhǔn)確率比每一個弱分類器都高的分類模型。
你需要做的是將第一個分類器分類分錯的部分交給第二個分類器，再將第二個分類器分錯的部分交給第三個分類器，如下圖依次所示
最終得到了我們看到的強(qiáng)分類器。
總結(jié)來看，begging類似于蟻群的智慧，沒有一只螞蟻知道全部的信息，但利用螞蟻的集合，可以實現(xiàn)集愚成智，而boosting則是三個臭皮匠，勝過諸葛亮。Boost方法包含的非線性變換比較多，表達(dá)能力強(qiáng)，而且不需要做復(fù)雜的特征工程和特征變換。但不同于隨機(jī)森林，它是一個串行過程，不好并行化，而且計算復(fù)雜度高。
XGBoost 是 Extreme Gradient Boosting （極端梯度上升）的縮寫，是當(dāng)下最常用的樹模型了，是上圖描述的Boosting Tree的一種高效實現(xiàn)，在R，Python等常用的語言下都有對應(yīng)的包，它把樹模型復(fù)雜度作為正則項加到優(yōu)化目標(biāo)中，從而避免了過于復(fù)雜而容易過擬合的模型。
在Boost方法中，每一個被錯誤分類的樣本的權(quán)值會增加，以強(qiáng)調(diào)最困難的情況，從而使得接下來的模型能集中注意力來處理這些錯誤的樣本，然而這種方法把基于學(xué)習(xí)器的決策樹視為一個黑盒子，沒有利用樹結(jié)構(gòu)本身。而Regularized Greedy Forest正則化貪心森林(RGF)會在當(dāng)前森林某一步的結(jié)構(gòu)變化后，依次調(diào)整整個森林中所有決策樹對應(yīng)的“葉子”的權(quán)重，使損失函數(shù)最小化。例如下圖我們從原來的森林中發(fā)下右下的節(jié)點可以分叉，我們做的不止是將分叉后的樹加入森林，而且對森林中已有的樹中的對應(yīng)節(jié)點也進(jìn)行類似的分叉操作。
類似boost，RGF中每個節(jié)點的權(quán)重也要不斷優(yōu)化，但不同的是，RGF不需要在梯度下降決策樹設(shè)置所需的樹尺寸（tree size）參數(shù)（例如，樹的數(shù)量，最大深度）?？偨Y(jié)一下RGF是另一種樹集成技術(shù)，它類似梯度下降算法，可用于有效建模非線性關(guān)系。
下面說說去年周志華教授提出深度森林deep forest，也叫做 gcForest，這也是一種基于決策樹的集成方法，下圖中每一層包括兩個隨機(jī)森林（藍(lán)色）和兩個complete random forests（黑色），所謂complete random forest，指的是其中的1000棵決策樹的每個節(jié)點都隨機(jī)的選擇一個特征作為分裂特征，不斷增長整棵樹，直到剩余所有樣本屬于同一類，或樣本數(shù)量少于10。
至于每一層的輸出，也不是傳統(tǒng)決策樹的一個標(biāo)簽，而是一個向量。圖中的每一個森林對每個輸入樣本都有一個輸出，對應(yīng)建立該決策樹時，落在該葉子節(jié)點中的樣本集合中各個類別的樣本所占的比例，如下圖所示，將多顆樹的結(jié)果求平均，得出這一層的輸出。為了避免過擬合，每個森林中 class vector 的產(chǎn)生采用了 k 折交叉驗證的方法，隨機(jī)的將k分之一的訓(xùn)練樣本丟出去，再對k次訓(xùn)練的結(jié)果求平均值。
deep forest還采取了類似卷積神經(jīng)網(wǎng)絡(luò)的滑動窗口，如下圖所示，原始樣本的為400維，定義一個大小為100的滑動窗口，將滑動窗口從原特征上依次滑過，每次移動一步，每次窗口滑動獲取的100個特征作為一個新的實例，等效于在400維特征上每相鄰100維的特征摘出來作為一個特征實例，得到301個新的特征實例（400 - 300 + 1）。
深度森林的源代碼也在Github上有開源版，總結(jié)一下，深度森林具有比肩深度神經(jīng)網(wǎng)絡(luò)的潛力，例如可以層次化的進(jìn)行特征提取及使用預(yù)訓(xùn)練模型進(jìn)行遷移學(xué)習(xí)，相比于深度學(xué)習(xí)，其具有少得多的超參數(shù)，并且對參數(shù)設(shè)置不太敏感，且在小數(shù)據(jù)集上，例如手寫數(shù)字識別中，表現(xiàn)的不比CNN差。深度森林的數(shù)據(jù)處理流如下圖所示。
總結(jié)下，樹模型作為一個常見的白盒模型，不管數(shù)據(jù)集的大小，不管是連續(xù)的回歸問題還是分類問題都適用。它不怎么需要進(jìn)行數(shù)據(jù)預(yù)處理，例如補(bǔ)全缺失值，去除異常點。樹模型可以針對特征按照重要性進(jìn)行排序，從而構(gòu)造新的特征或從中選出子集來壓縮數(shù)據(jù)。樹模型可以通過統(tǒng)計的方式去驗證模型的準(zhǔn)確值，判斷訓(xùn)練的進(jìn)展，相比機(jī)器學(xué)習(xí)的模型，需要調(diào)整的超參數(shù)也更少。但和神經(jīng)網(wǎng)絡(luò)一樣，樹模型也不夠健壯，如同圖像上只需要改變幾個像素點就可以改變模型的結(jié)果，樹模型中輸入數(shù)據(jù)的微小變化也可能會顯著改變模型的結(jié)果。樹模型也有過擬合的危險，通過剪紙purning，即先讓樹長的深一些，再去除那些不帶來信息增益的分叉，留下那些最初的信息增益為負(fù)，但整體的信息增益為正的節(jié)點，可以組織樹模型的過擬合。
