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

樹(shù)模型主要用來(lái)做分類(lèi)。最簡(jiǎn)單的一種叫做決策樹(shù),，決策樹(shù)是一個(gè)非常接近人類(lèi)思維的模型,。 它形象的說(shuō)就是一個(gè)調(diào)查問(wèn)卷， 把一個(gè)最終的決策轉(zhuǎn)化為個(gè)若干問(wèn)題,， 每一步得到一個(gè)答案,， 按照答案的正否來(lái)決定下一個(gè)問(wèn)題是什么，如此形成一個(gè)樹(shù)結(jié)構(gòu),， 最后形成一個(gè)分類(lèi)器。 比如經(jīng)常被舉出的例子,， 你要買(mǎi)電腦,， 要根據(jù)很多特征挑選電腦，比如cpu,，gpu,，硬盤(pán)，內(nèi)存等,， 你一定會(huì)問(wèn)你自己一系列問(wèn)題,， 我要買(mǎi)那款cpu，gpu,， 硬盤(pán),， 內(nèi)存等，最后做出決策,。決策樹(shù)要做的是把這個(gè)過(guò)程自動(dòng)化,，最后給我們我們希望的判定結(jié)果。

在一棵決策樹(shù)上，其中的節(jié)點(diǎn)可以分成根節(jié)點(diǎn)（藍(lán)色） 決策節(jié)點(diǎn)（紅色）和終止節(jié)點(diǎn)（綠色）,，而圖中的方框里包含的即是一顆子樹(shù),，這么看來(lái)，樹(shù)模型是不是特別好理解,？樹(shù)模型的第二個(gè)好處是可以方便的探索數(shù)據(jù)中那些維度更加重要（對(duì)做出正確的預(yù)測(cè)貢獻(xiàn)更大）,，比如上述的買(mǎi)電腦的例子，你會(huì)發(fā)現(xiàn)對(duì)于大多數(shù)人來(lái)說(shuō),，CPU的型號(hào)最關(guān)鍵,。樹(shù)模型的第三個(gè)好處是不怎么需要做數(shù)據(jù)清洗和補(bǔ)全，還用買(mǎi)電腦的例子,，假設(shè)你拿到的數(shù)據(jù)部分中沒(méi)有告訴GPU的型號(hào),，你不必要丟掉這部分?jǐn)?shù)據(jù)，進(jìn)入到相應(yīng)的子樹(shù)里,，隨機(jī)的讓這條數(shù)據(jù)進(jìn)入一個(gè)終止節(jié)點(diǎn)就好了,，這樣，你便能夠利用缺失的數(shù)據(jù)了,。

談起樹(shù)模型,，就要說(shuō)起基尼系數(shù)，這個(gè)指數(shù)最常見(jiàn)的場(chǎng)景是描述貧富差距,，但也可以用來(lái)指導(dǎo)樹(shù)模型在那里分叉,。假設(shè)一顆最簡(jiǎn)單做二分類(lèi)問(wèn)題的決策樹(shù)，拿到的數(shù)據(jù)分為兩種特征,，一個(gè)是性別,，一個(gè)是班級(jí)，預(yù)測(cè)學(xué)生們?cè)覆辉复虬迩?，下面的圖是兩種不同的樹(shù)模型,，用性別來(lái)分，10個(gè)女生中有2個(gè)愿意打球,，而20個(gè)男生中有13個(gè)愿意打球,，而用班級(jí)分，效果則沒(méi)有那么好,，具體怎么計(jì)算了,，先從左到右依次計(jì)算每個(gè)終止節(jié)點(diǎn)的基尼系數(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,，之后對(duì)每棵樹(shù)的基尼系數(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（按班級(jí)分），因此在該例子中,，性別是一個(gè)更好的特征,。

理解決策樹(shù)的下一個(gè)重要的概念是信息增益,，信息可以看成是減少了多少系統(tǒng)中的無(wú)序，而描述系統(tǒng)的無(wú)序程度,，可以用信息熵,，對(duì)于二分類(lèi)問(wèn)題，計(jì)算公式是  ,。

對(duì)于每一次樹(shù)上的分叉,，先算下父節(jié)點(diǎn)的熵，再計(jì)算下子節(jié)點(diǎn)的熵的加權(quán)平均,，就可以計(jì)算出決策樹(shù)中的一個(gè)決策節(jié)點(diǎn)帶來(lái)了多少信息增益了,。

信息熵公式告訴我們的是，我們每次對(duì)所有特征都掃描一遍,，選擇那個(gè)讓我們的信息增長(zhǎng)最大的特征,。 依次在這個(gè)特征的每個(gè)可能取值下，我們?cè)趯ふ业诙€(gè)關(guān)鍵特征,，列出第二個(gè)特征選的可能取值并尋找第三個(gè)特征依次類(lèi)推,。 再對(duì)每一分支的操作里， 如果我們發(fā)現(xiàn)在某個(gè)特征組合下的樣本均為一類(lèi),， 則停止分叉的過(guò)程,。 整個(gè)操作過(guò)程形似尋找一顆不斷分叉的樹(shù)木， 故名決策樹(shù),。

決策樹(shù)能夠處理特征之間的互相影響,， 因?yàn)樘卣髦g的互相影響，我們并不像簡(jiǎn)單貝葉斯那樣并列的處理這些特征,。 例如某個(gè)特征可能在某個(gè)條件下式好的,， 但在另外條件下就是壞的或者沒(méi)影響。 比如說(shuō)找對(duì)象,，你只在對(duì)方漂亮的時(shí)候才care他學(xué)歷,。 我會(huì)根據(jù)之前問(wèn)過(guò)的問(wèn)題的答案來(lái)選擇下一步問(wèn)什么樣的問(wèn)題， 如此,， 我就能很好的處理特征之間的關(guān)聯(lián)。

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

訓(xùn)練集D （x1,，y1）….

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

函數(shù)treegenerate 

1,   生成結(jié)點(diǎn)node A（任選一個(gè)特征）

2,， 判斷D在A中樣本是否都屬于類(lèi)型C,，是則A標(biāo)記為C類(lèi)葉結(jié)點(diǎn)， 結(jié)束

3,， 判斷A為空或D在A樣本取值同（x相同而非y）,，將node 標(biāo)記為樣本多數(shù)分類(lèi)的葉結(jié)點(diǎn)（max numbers）,，結(jié)束

終止條件不成立則: 

從A中選擇最優(yōu)劃分屬性a*,   

循環(huán):

對(duì)A*上的每一個(gè)值a*做如下處理：

If a*上的樣本為空，則a*為葉節(jié)點(diǎn) （該值下用于判斷的樣本不足,，判定為A*中樣本最多的類(lèi)）,，

如果支點(diǎn)上的樣本集為D**  

如果存在某個(gè)位置，使得D**為空,，

則A*為葉節(jié)點(diǎn),，

否則，以a*為分支節(jié)點(diǎn),，回到第一句     

接下來(lái)我們看一看更為復(fù)雜的情況,，比如我們拿到的數(shù)據(jù)特征不是兩個(gè)，而是一百個(gè),，那么問(wèn)題來(lái)了,，我們的決策樹(shù)也要100層那么深嗎？如果真的這么深,，那么這個(gè)模型很容易過(guò)擬合的,，任何一顆決策樹(shù)的都應(yīng)該有終止條件，例如樹(shù)最深多少層,，每個(gè)節(jié)點(diǎn)最少要有多少樣本,，最多有多少個(gè)終止節(jié)點(diǎn)等，這些和終止條件有關(guān)的超參數(shù)設(shè)置決定了模型會(huì)不會(huì)過(guò)擬合,。

下面我們從一棵樹(shù)過(guò)度到一群數(shù),，也就是機(jī)器學(xué)習(xí)中常用的bagging，將原來(lái)的訓(xùn)練數(shù)據(jù)集分成多份,，每一份分別訓(xùn)練一個(gè)分類(lèi)器,，最后再讓這些分類(lèi)器進(jìn)行投票表決。

而隨機(jī)森林,，就是使用bagging技巧加持的決策樹(shù),，是不是很簡(jiǎn)單？相比于決策樹(shù),，隨機(jī)森林的可解釋性差一些,，另外對(duì)于標(biāo)簽為連續(xù)的回歸問(wèn)題，隨機(jī)森林所采取的求多個(gè)樹(shù)的平均數(shù)的策略會(huì)導(dǎo)致結(jié)果的不穩(wěn)定,。

隨機(jī)森林是將訓(xùn)練數(shù)據(jù)隨機(jī)的分成很多類(lèi),，分別訓(xùn)練很多分類(lèi)器，再將這些分類(lèi)器聚合起來(lái),，而boosting則不講訓(xùn)練數(shù)據(jù)分類(lèi),，而是將弱分類(lèi)器聚合起來(lái)，下圖的上半部分可以看成描述了三個(gè)弱分類(lèi)器,，每一個(gè)都有分錯(cuò)的,，而將他們集合起來(lái),，可以得出一個(gè)準(zhǔn)確率比每一個(gè)弱分類(lèi)器都高的分類(lèi)模型。

你需要做的是將第一個(gè)分類(lèi)器分類(lèi)分錯(cuò)的部分交給第二個(gè)分類(lèi)器,，再將第二個(gè)分類(lèi)器分錯(cuò)的部分交給第三個(gè)分類(lèi)器,，如下圖依次所示

最終得到了我們看到的強(qiáng)分類(lèi)器。

總結(jié)來(lái)看,，begging類(lèi)似于蟻群的智慧,，沒(méi)有一只螞蟻知道全部的信息，但利用螞蟻的集合,，可以實(shí)現(xiàn)集愚成智,，而boosting則是三個(gè)臭皮匠，勝過(guò)諸葛亮,。Boost方法包含的非線性變換比較多,，表達(dá)能力強(qiáng)，而且不需要做復(fù)雜的特征工程和特征變換,。但不同于隨機(jī)森林,，它是一個(gè)串行過(guò)程，不好并行化,，而且計(jì)算復(fù)雜度高,。

XGBoost 是 Extreme Gradient Boosting （極端梯度上升）的縮寫(xiě)，是當(dāng)下最常用的樹(shù)模型了,，是上圖描述的Boosting  Tree的一種高效實(shí)現(xiàn),，在R，Python等常用的語(yǔ)言下都有對(duì)應(yīng)的包,，它把樹(shù)模型復(fù)雜度作為正則項(xiàng)加到優(yōu)化目標(biāo)中,，從而避免了過(guò)于復(fù)雜而容易過(guò)擬合的模型。

在Boost方法中,，每一個(gè)被錯(cuò)誤分類(lèi)的樣本的權(quán)值會(huì)增加,，以強(qiáng)調(diào)最困難的情況，從而使得接下來(lái)的模型能集中注意力來(lái)處理這些錯(cuò)誤的樣本,，然而這種方法把基于學(xué)習(xí)器的決策樹(shù)視為一個(gè)黑盒子,，沒(méi)有利用樹(shù)結(jié)構(gòu)本身。而Regularized Greedy Forest正則化貪心森林(RGF)會(huì)在當(dāng)前森林某一步的結(jié)構(gòu)變化后,，依次調(diào)整整個(gè)森林中所有決策樹(shù)對(duì)應(yīng)的“葉子”的權(quán)重,，使損失函數(shù)最小化。例如下圖我們從原來(lái)的森林中發(fā)下右下的節(jié)點(diǎn)可以分叉,，我們做的不止是將分叉后的樹(shù)加入森林,，而且對(duì)森林中已有的樹(shù)中的對(duì)應(yīng)節(jié)點(diǎn)也進(jìn)行類(lèi)似的分叉操作,。

類(lèi)似boost,，RGF中每個(gè)節(jié)點(diǎn)的權(quán)重也要不斷優(yōu)化,，但不同的是，RGF不需要在梯度下降決策樹(shù)設(shè)置所需的樹(shù)尺寸（tree size）參數(shù)（例如,，樹(shù)的數(shù)量,，最大深度）?？偨Y(jié)一下RGF是另一種樹(shù)集成技術(shù),，它類(lèi)似梯度下降算法，可用于有效建模非線性關(guān)系,。

下面說(shuō)說(shuō)去年周志華教授提出深度森林deep forest,，也叫做 gcForest，這也是一種基于決策樹(shù)的集成方法,，下圖中每一層包括兩個(gè)隨機(jī)森林（藍(lán)色）和兩個(gè)complete random forests（黑色）,，所謂complete random forest，指的是其中的1000棵決策樹(shù)的每個(gè)節(jié)點(diǎn)都隨機(jī)的選擇一個(gè)特征作為分裂特征,，不斷增長(zhǎng)整棵樹(shù),，直到剩余所有樣本屬于同一類(lèi)，或樣本數(shù)量少于10,。

至于每一層的輸出,，也不是傳統(tǒng)決策樹(shù)的一個(gè)標(biāo)簽，而是一個(gè)向量,。圖中的每一個(gè)森林對(duì)每個(gè)輸入樣本都有一個(gè)輸出,，對(duì)應(yīng)建立該決策樹(shù)時(shí)，落在該葉子節(jié)點(diǎn)中的樣本集合中各個(gè)類(lèi)別的樣本所占的比例,，如下圖所示,，將多顆樹(shù)的結(jié)果求平均，得出這一層的輸出,。為了避免過(guò)擬合,，每個(gè)森林中 class vector 的產(chǎn)生采用了 k 折交叉驗(yàn)證的方法，隨機(jī)的將k分之一的訓(xùn)練樣本丟出去,，再對(duì)k次訓(xùn)練的結(jié)果求平均值,。

deep forest還采取了類(lèi)似卷積神經(jīng)網(wǎng)絡(luò)的滑動(dòng)窗口，如下圖所示,，原始樣本的為400維,，定義一個(gè)大小為100的滑動(dòng)窗口，將滑動(dòng)窗口從原特征上依次滑過(guò),，每次移動(dòng)一步,，每次窗口滑動(dòng)獲取的100個(gè)特征作為一個(gè)新的實(shí)例，等效于在400維特征上每相鄰100維的特征摘出來(lái)作為一個(gè)特征實(shí)例,，得到301個(gè)新的特征實(shí)例（400 - 300 + 1）,。

深度森林的源代碼也在Github上有開(kāi)源版,，總結(jié)一下，深度森林具有比肩深度神經(jīng)網(wǎng)絡(luò)的潛力,，例如可以層次化的進(jìn)行特征提取及使用預(yù)訓(xùn)練模型進(jìn)行遷移學(xué)習(xí),，相比于深度學(xué)習(xí)，其具有少得多的超參數(shù),，并且對(duì)參數(shù)設(shè)置不太敏感,，且在小數(shù)據(jù)集上，例如手寫(xiě)數(shù)字識(shí)別中,，表現(xiàn)的不比CNN差,。深度森林的數(shù)據(jù)處理流如下圖所示。

總結(jié)下,，樹(shù)模型作為一個(gè)常見(jiàn)的白盒模型,，不管數(shù)據(jù)集的大小，不管是連續(xù)的回歸問(wèn)題還是分類(lèi)問(wèn)題都適用,。它不怎么需要進(jìn)行數(shù)據(jù)預(yù)處理,，例如補(bǔ)全缺失值，去除異常點(diǎn),。樹(shù)模型可以針對(duì)特征按照重要性進(jìn)行排序,，從而構(gòu)造新的特征或從中選出子集來(lái)壓縮數(shù)據(jù)。樹(shù)模型可以通過(guò)統(tǒng)計(jì)的方式去驗(yàn)證模型的準(zhǔn)確值,，判斷訓(xùn)練的進(jìn)展,，相比機(jī)器學(xué)習(xí)的模型，需要調(diào)整的超參數(shù)也更少,。但和神經(jīng)網(wǎng)絡(luò)一樣,，樹(shù)模型也不夠健壯，如同圖像上只需要改變幾個(gè)像素點(diǎn)就可以改變模型的結(jié)果,，樹(shù)模型中輸入數(shù)據(jù)的微小變化也可能會(huì)顯著改變模型的結(jié)果,。樹(shù)模型也有過(guò)擬合的危險(xiǎn)，通過(guò)剪紙purning,，即先讓樹(shù)長(zhǎng)的深一些,，再去除那些不帶來(lái)信息增益的分叉，留下那些最初的信息增益為負(fù),，但整體的信息增益為正的節(jié)點(diǎn),，可以組織樹(shù)模型的過(guò)擬合。