本文僅為簡(jiǎn)單梳理樹(shù)模型升級(jí)過(guò)程，盡量少牽扯到數(shù)學(xué)公式，用大白話來(lái)理解。

預(yù)備知識(shí)

熵，熵用來(lái)描述事件的不確定性，越隨機(jī)熵值越大。

如何理解不確定性呢？假設(shè)現(xiàn)在有一個(gè)伯努利分布，p(0) = p(1) = 1/2，則這個(gè)分布的不確定性是最大的，因?yàn)槲覀兂闃拥臅r(shí)候完全無(wú)法確定抽樣出來(lái)的那個(gè)數(shù)值的概率更大，兩者都是1/2，所以不確定性在這里可以理解為某個(gè)事件發(fā)生的概率。我們?cè)賮?lái)看看熵值的公式：

對(duì)于一個(gè)伯努利其熵值為：
H(p) = -p(p)log(p) - (1-p)log(1-p)

為了驗(yàn)證我們上面提到的伯努利分布的某個(gè)事件發(fā)生概率為1/2時(shí)熵最大，將p=1/2代入上式得到的熵值與p=4/5時(shí)的熵值進(jìn)行比較即可，可以得到
H(p=1/2) > H(p=4/5)。

當(dāng)P等于4/5時(shí)，我們有很大的概率（80%）可以確定事件會(huì)發(fā)生，而p=1/2時(shí)，則完全無(wú)法確定事件是否會(huì)發(fā)生，因?yàn)榘l(fā)生不發(fā)生的概率相等，這就是事件發(fā)生的不確定性。也即熵值H(p=1/2) > H(p=4/5)可以得出p=4/5時(shí)，不確定性更小，能更方便的猜出事件是否會(huì)發(fā)生。

交叉熵
在深度學(xué)習(xí)中，最常見(jiàn)的loss函數(shù)即是交叉熵?fù)p失函數(shù)。我們從不確定性角度來(lái)理解交叉熵?fù)p失函數(shù)：我們訓(xùn)練模型的目標(biāo)是要使得loss變小，即事件發(fā)生的不確定性變小，不確定性小就表示模型更能猜出正確類(lèi)別了。

決策樹(shù)

樹(shù)模型作為一種簡(jiǎn)單易理解的方式，其訓(xùn)練過(guò)程即是通過(guò)簡(jiǎn)單if/else來(lái)將所有的樣本劃分到其對(duì)應(yīng)的葉子中。

ID3決策樹(shù)

ID3決策樹(shù)使用信息增益來(lái)作為特征選擇標(biāo)準(zhǔn)，每次選擇信息增益最大的特征。需要注意的是ID3是一顆多叉樹(shù)，因此他總是傾向于選擇特征值更多的特征來(lái)進(jìn)行分裂。如何理解呢？

一個(gè)極端的例子，假設(shè)我們以人的DNA為特征來(lái)對(duì)訓(xùn)練集中的人群進(jìn)行分類(lèi)，毫無(wú)疑問(wèn)的，只需要這一個(gè)特征（每個(gè)樣本一個(gè)特征值）且只要這一次分裂就可以將所有人分開(kāi)，因?yàn)槊總€(gè)人的DNA是唯一的，因此每一個(gè)人都是一個(gè)葉子結(jié)點(diǎn)。但是這個(gè)時(shí)候如果我們想要預(yù)測(cè)測(cè)試集怎么辦？測(cè)試集中的人群DNA在訓(xùn)練集中沒(méi)出現(xiàn)過(guò)，因此模型無(wú)法對(duì)測(cè)試集進(jìn)行正確預(yù)測(cè)。也就是發(fā)生了我們常常說(shuō)的過(guò)擬合現(xiàn)象。

白話信息增益：信息增益可以理解為在得知了額外的信息后事件發(fā)生不確定性的減少量。譬如我們想知道明天是否會(huì)下雨，如果我們?cè)谝粋€(gè)黑房子里面則什么信息都收不到，但是當(dāng)我們走出房門(mén)，發(fā)現(xiàn)天氣悶熱，螞蟻搬家蛇過(guò)道這些額外信息（即特征）后我們就可以很大概率說(shuō)明天會(huì)下雨了。同時(shí)我們也知道了特朗普競(jìng)選總統(tǒng)失?。ㄌ卣鳎沁@個(gè)對(duì)于明天是否下雨是無(wú)關(guān)的，無(wú)法幫助我們確定明天是否會(huì)下雨，也即沒(méi)有什么信息增益。

ID3小總結(jié)：

• ID3決策樹(shù)為多叉樹(shù)，因此每個(gè)特征只使用一次，因?yàn)橐淮尉蛯⒛芊珠_(kāi)的樣本全部分開(kāi)了；
• ID3決策樹(shù)偏好值更多的特征，因此更容易發(fā)生過(guò)擬合現(xiàn)象；
• 沒(méi)有剪枝，容易過(guò)擬合；
• 無(wú)法處理缺失值；
• 只能處理離散值；

C4.5決策樹(shù)

C4.5決策樹(shù)針對(duì)ID3決策樹(shù)偏好值多的缺點(diǎn)進(jìn)行改進(jìn)，引入了信息增益比來(lái)作為分裂標(biāo)準(zhǔn)。

C4.5相較于ID3的改進(jìn)有：

• 1、使用信息增益比來(lái)作為分裂標(biāo)準(zhǔn)，此時(shí)又會(huì)導(dǎo)致另一個(gè)問(wèn)題——更加傾向于值更少的特征，值更少（熵更小，即計(jì)算信息增益比的分母更小）；
• 2、能處理連續(xù)數(shù)據(jù)，具體方法為：遍歷所有值，以每個(gè)值來(lái)作為分割點(diǎn)將所有樣本分為兩類(lèi)，找到信息增益比最大的點(diǎn)；
• 3、可以處理缺失值，具體地，僅使用非缺失樣本來(lái)計(jì)算特征的信息增益，并將信息增益乘以缺失率以降低顯示出缺失的影響，而對(duì)于缺失樣本則是將缺失樣本以某個(gè)概率分到子節(jié)點(diǎn)；
• 4、添加了剪枝來(lái)防止過(guò)擬合，有兩種剪枝策略：
  • 預(yù)剪枝：在建樹(shù)的過(guò)程中如果分裂后的準(zhǔn)確率變低了，則停止分裂。這是一種貪心算法，可能得不到全局最優(yōu)解；
  • 后剪枝：在完成建樹(shù)后，依次刪掉葉子節(jié)點(diǎn)并求準(zhǔn)確率，最后通過(guò)比較就能得到最好的樹(shù)。能得到全局最優(yōu)解，但是算法復(fù)雜度較大；

C4.5樹(shù)仍然使用的是多叉樹(shù)，因此每個(gè)特征僅使用一次，在后續(xù)分裂中不再使用。且只能用于分類(lèi)。

CART決策樹(shù)

CART決策樹(shù)相對(duì)于C4.5樹(shù)進(jìn)行了改進(jìn)：

• CART決策樹(shù)使用二叉樹(shù)，效率高，且特征可以重復(fù)使用；
• 使用gini系數(shù)來(lái)最為分裂標(biāo)準(zhǔn)，計(jì)算復(fù)雜度大大降低；
• 缺失值處理：分裂時(shí)仍然是僅考慮CART樹(shù)并通過(guò)乘以一個(gè)系數(shù)來(lái)顯示缺失值的影響；而對(duì)于缺失值如何劃分到子節(jié)點(diǎn)，則是使用了一種較為復(fù)雜的代理分裂的策略，簡(jiǎn)單理解即是對(duì)于這些缺失的樣本選擇別的特征來(lái)計(jì)算gini增益，如果又碰到了缺失，就需要再次找代理特征。。。；
• 對(duì)于回歸問(wèn)題，使用最小方差（也即均方誤差）和來(lái)作為分裂標(biāo)準(zhǔn)；
• 使用代價(jià)復(fù)雜度剪枝策略，即不僅考慮了準(zhǔn)確率，還將樹(shù)的復(fù)雜度考慮進(jìn)去了。

隨機(jī)森林（Random Forest）

隨機(jī)森林屬于bagging算法，有兩個(gè)隨機(jī)過(guò)程：

• 1、對(duì)于每顆子樹(shù)，有放回的隨機(jī)選擇N個(gè)樣本（即bootstrap抽樣）；
• 2、在每個(gè)結(jié)點(diǎn)分裂時(shí)，先隨機(jī)選擇m個(gè)特征，然后按照某個(gè)分裂標(biāo)準(zhǔn)從這些特征中選擇分裂特征；

預(yù)測(cè)時(shí)，分類(lèi)問(wèn)題投票，回歸問(wèn)題求平均。

優(yōu)點(diǎn)：

• 效果挺好；
• 速度快，易并行；
• 能處理高維數(shù)據(jù)，不用作特征選擇；

梯度提升樹(shù)（Gradient Boosting Decision Tree）

梯度提升樹(shù)由多個(gè)回歸決策樹(shù)串聯(lián)得到，因此建樹(shù)時(shí)的分裂標(biāo)準(zhǔn)是均方誤差和。

回歸樹(shù)如何解決分類(lèi)問(wèn)題？
以邏輯回歸為例，邏輯回歸其實(shí)也可以理解為廣義線性回歸函數(shù)來(lái)擬合對(duì)數(shù)幾率。因此回歸樹(shù)也可以用類(lèi)似的方法來(lái)進(jìn)行分類(lèi)。

梯度提升樹(shù)的每個(gè)樹(shù)都會(huì)擬合上棵樹(shù)的擬合目標(biāo)殘差。

在梯度提升決策樹(shù)中，還添加了shrinkage，這個(gè)是與adaboost的一個(gè)重大區(qū)別，相當(dāng)于學(xué)習(xí)率，控制每棵樹(shù)學(xué)習(xí)到更少的東西，使用更多的樹(shù)來(lái)進(jìn)行集成學(xué)習(xí)。

缺點(diǎn)：

• 對(duì)異常點(diǎn)敏感，可通過(guò)huber loss來(lái)進(jìn)行緩解；
• 沒(méi)有剪枝策略；

XGBOOST

xgboost的相對(duì)于GBDT的一個(gè)非常重要的改進(jìn)就是使用泰勒二階展開(kāi)來(lái)近似擬合殘差，也即如下公式：

xgb原始loss

再加上模型復(fù)雜度的表示，可以得到最終loss：

這里我們簡(jiǎn)單說(shuō)一下模型復(fù)雜度的組成，第一項(xiàng) γT其實(shí)是控制的樹(shù)的葉子節(jié)點(diǎn)不要太多（可以理解為參數(shù)不要太多，L1正則化），第二項(xiàng)其實(shí)是控制每個(gè)葉子結(jié)點(diǎn)的數(shù)值不要太大（可以理解為模型參數(shù)不要太大，L2正則化）。

上面幾步看不明白的可以去https://zhuanlan.zhihu.com/p/87885678 看一步一步的推導(dǎo)過(guò)程。

可以看到，模型的優(yōu)化目標(biāo)其實(shí)僅與前一棵樹(shù)一階導(dǎo)（G）、二階導(dǎo)（H）、lambda（可以理解為L(zhǎng)2正則化系數(shù)）、γ（理解為L(zhǎng)1正則化系數(shù)）有關(guān)系。對(duì)于決策樹(shù)的每次分裂，我們的目標(biāo)其實(shí)就是要使得上面的目標(biāo)函數(shù)值更小，換句話說(shuō)，上面的目標(biāo)函數(shù)就是我們的分裂標(biāo)準(zhǔn)，這與前面所有的決策樹(shù)的分裂方式都是完全不同的。

看看下面的圖可能更好理解：

如何選擇分裂特征？

• 1、像cart樹(shù)那樣遍歷特征的所有值以找到最佳分裂點(diǎn)，此方法能找大全局最優(yōu)，但是計(jì)算量大；
• 2、排序分箱（其實(shí)還使用了二階導(dǎo)加權(quán)）然后遍歷幾個(gè)分箱值以尋找最佳分裂點(diǎn)，此方法不一定能找到全局最優(yōu)，但是能大大提升運(yùn)算效率。

稀疏感知算法

在分裂選擇特征時(shí)，僅使用非缺失值來(lái)進(jìn)行計(jì)算增益。而對(duì)于缺失結(jié)點(diǎn)的劃分，則是將每個(gè)缺失樣本分別放入到兩個(gè)子節(jié)點(diǎn)中，哪個(gè)增益大就選擇劃分到哪個(gè)結(jié)點(diǎn)。

工程化優(yōu)化

略。。。

優(yōu)點(diǎn)：

• 精度更高：二階泰勒展開(kāi)近似；
• 更靈活：不僅支持CART還支持線性分類(lèi)器；
• 正則化：將剪枝過(guò)程整合到了loss函數(shù)中（L1系數(shù)控制結(jié)點(diǎn)數(shù)量，L2系數(shù)控制葉子結(jié)點(diǎn)數(shù)值）；
• shrinkage：削弱每棵樹(shù)的影響，使用更多的樹(shù)來(lái)進(jìn)行集成學(xué)習(xí)；
• 缺失值處理：稀疏感知算法；
• 并行化；

LightGBM

更快，占用內(nèi)存更小的GBM。

優(yōu)化的點(diǎn)如下：

• 1、單邊抽樣：xgb在每棵樹(shù)學(xué)習(xí)時(shí)其實(shí)還是使用了所有的樣本的（or 抽樣），而這些樣本里面其實(shí)有很多樣本已經(jīng)學(xué)習(xí)的很好了，也即梯度很小，貢獻(xiàn)也很小，因此在lgb中后續(xù)樹(shù)學(xué)習(xí)時(shí)，使用梯度大的那部分樣本a，然后加上抽取一些梯度小的樣本得到總樣本b，分裂時(shí)梯度小的樣本需要乘以權(quán)重(1-a)/b來(lái)保持?jǐn)?shù)據(jù)分布不變，使用這些樣本來(lái)進(jìn)行學(xué)習(xí)；

• 2、直方圖算法：直方圖算法與xgb中分裂時(shí)候的分箱算法基本是相同的，即對(duì)連續(xù)數(shù)值進(jìn)行分箱處理，然后遍歷分箱值即可以找到特征最佳分裂點(diǎn)；

• 3、直方圖加速：左節(jié)點(diǎn)的直方圖可以由父節(jié)點(diǎn)直方圖減去左節(jié)點(diǎn)得到。且在構(gòu)建直方圖時(shí)，還可以先構(gòu)建小的直方圖來(lái)進(jìn)一步減小計(jì)算量；

• 4、互斥特征捆綁：高維特征常常是稀疏的，且不同特征還有可能是互斥的，通過(guò)允許一定的非互斥率，將那些可能互斥的特征捆綁在一起可以達(dá)到降維的效果；

• 5、leaf-wise算法：也可以理解為類(lèi)深度優(yōu)先算法。xgb中是每層所有結(jié)點(diǎn)一起分裂，可以視為廣度優(yōu)先算法，這種做法的缺點(diǎn)是可能有些結(jié)點(diǎn)他的分裂收益已經(jīng)很小了，不分裂可能更好。因此在lgb中，采用leaf-wise的類(lèi)深度優(yōu)先算法，每次都尋找分裂收益最大的結(jié)點(diǎn)來(lái)進(jìn)行分裂。這種做法可以減少計(jì)算量；

• 6、類(lèi)別特征最優(yōu)分割：一般的決策樹(shù)使用類(lèi)別特征進(jìn)行分裂時(shí)使用的是one-vs-rest的策略，這種策略（1）可能會(huì)產(chǎn)生分裂時(shí)樣本劃分不均衡；（2）將數(shù)據(jù)劃分到多個(gè)小空間容易導(dǎo)致過(guò)擬合，影響決策樹(shù)學(xué)習(xí)。因此lgb采用了一種many-vs-many的算法，即將多個(gè)類(lèi)別捆綁為一組作為一個(gè)類(lèi)，其余的類(lèi)別作為另一類(lèi)；

• 7、工程方面：特征并行、數(shù)據(jù)并行、投票并行、緩存優(yōu)化；

與xgb相比：

• 1、內(nèi)存更?。?/p>

  • 不需要xgb的預(yù)排序，lgb使用的分箱，只需要存bin值即可；
  • 互斥特征捆綁達(dá)到了降維的效果；

• 2、速度更快：

  • 單邊梯度；
  • 分箱操作；
  • 互斥特征捆綁；
  • leaf-wise生長(zhǎng);
  • 工程上的一些優(yōu)化；

基于樹(shù)模型的特征選擇

樹(shù)模型解釋性較好，我們常?？梢酝ㄟ^(guò)樹(shù)模型來(lái)進(jìn)行特征選擇，留下重要特征。不同樹(shù)模型特征重要性評(píng)估方法略有區(qū)別。

決策樹(shù)、隨機(jī)森林、GBDT

決策樹(shù)、隨機(jī)森林和GBDT的特征重要性評(píng)估方法相同都是根據(jù)不純度減小(也即gini系數(shù))來(lái)進(jìn)行度量：

sklearn API

XGBoost

xgboost的特征重要性評(píng)估方法更為多樣，如下：

• weight，也即根據(jù)特征使用的次數(shù)來(lái)決定其權(quán)重；
• gain，根據(jù)收益（也即loss減小量）來(lái)決定其收益，其又可以分為兩種：
  • gain，平均每次使用特征獲得的收益；
  • total_gain，使用某個(gè)特征的收益總和；
• cover，覆蓋率，也即這個(gè)特征覆蓋了多少個(gè)樣本，同樣也分為兩種：
  • cover，平均覆蓋率，平均每次使用特征覆蓋的樣本數(shù)量（或者說(shuō)覆蓋率）；
  • total_cover，總覆蓋率，某個(gè)特征總覆蓋率。

LightGBM

lightGBM的特征評(píng)估方式如下：

• split，也即特征使用次數(shù)，與xgboost中的weight是一致的；
• gain，使用特征的總收益（也即loss減?。?，與xgboost中的total_gain相同。

參考：
《統(tǒng)計(jì)學(xué)習(xí)方法》李航
【機(jī)器學(xué)習(xí)】決策樹(shù)（下）——XGBoost、LightGBM（非常詳細(xì)）
樹(shù)模型(六)：XGBoost (帶手動(dòng)建樹(shù)實(shí)例，非常推薦)