本文僅為簡單梳理樹模型升級過程，盡量少牽扯到數(shù)學(xué)公式援所，用大白話來理解。

預(yù)備知識

熵欣除，熵用來描述事件的不確定性住拭，越隨機(jī)熵值越大。

如何理解不確定性呢历帚？假設(shè)現(xiàn)在有一個伯努利分布滔岳，p(0) = p(1) = 1/2，則這個分布的不確定性是最大的挽牢，因為我們抽樣的時候完全無法確定抽樣出來的那個數(shù)值的概率更大谱煤，兩者都是1/2，所以不確定性在這里可以理解為某個事件發(fā)生的概率禽拔。我們再來看看熵值的公式：

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

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

當(dāng)P等于4/5時寥闪，我們有很大的概率（80%）可以確定事件會發(fā)生，而p=1/2時磨淌，則完全無法確定事件是否會發(fā)生疲憋，因為發(fā)生不發(fā)生的概率相等，這就是事件發(fā)生的不確定性梁只。也即熵值H(p=1/2) > H(p=4/5)可以得出p=4/5時缚柳，不確定性更小，能更方便的猜出事件是否會發(fā)生搪锣。

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

決策樹

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

ID3決策樹

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

一個極端的例子佩迟，假設(shè)我們以人的DNA為特征來對訓(xùn)練集中的人群進(jìn)行分類团滥，毫無疑問的，只需要這一個特征（每個樣本一個特征值）且只要這一次分裂就可以將所有人分開报强，因為每個人的DNA是唯一的灸姊，因此每一個人都是一個葉子結(jié)點。但是這個時候如果我們想要預(yù)測測試集怎么辦躺涝？測試集中的人群DNA在訓(xùn)練集中沒出現(xiàn)過厨钻，因此模型無法對測試集進(jìn)行正確預(yù)測。也就是發(fā)生了我們常常說的過擬合現(xiàn)象坚嗜。

白話信息增益：信息增益可以理解為在得知了額外的信息后事件發(fā)生不確定性的減少量夯膀。譬如我們想知道明天是否會下雨，如果我們在一個黑房子里面則什么信息都收不到苍蔬，但是當(dāng)我們走出房門诱建，發(fā)現(xiàn)天氣悶熱，螞蟻搬家蛇過道這些額外信息（即特征）后我們就可以很大概率說明天會下雨了碟绑。同時我們也知道了特朗普競選總統(tǒng)失敯吃场（特征），但是這個對于明天是否下雨是無關(guān)的格仲，無法幫助我們確定明天是否會下雨押袍，也即沒有什么信息增益。

ID3小總結(jié)：

• ID3決策樹為多叉樹凯肋，因此每個特征只使用一次谊惭，因為一次就將能分開的樣本全部分開了；
• ID3決策樹偏好值更多的特征侮东，因此更容易發(fā)生過擬合現(xiàn)象圈盔；
• 沒有剪枝，容易過擬合悄雅；
• 無法處理缺失值驱敲；
• 只能處理離散值；

C4.5決策樹

C4.5決策樹針對ID3決策樹偏好值多的缺點進(jìn)行改進(jìn)宽闲，引入了信息增益比來作為分裂標(biāo)準(zhǔn)众眨。

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

• 1握牧、使用信息增益比來作為分裂標(biāo)準(zhǔn)，此時又會導(dǎo)致另一個問題——更加傾向于值更少的特征娩梨，值更少（熵更小我碟，即計算信息增益比的分母更小）姚建；
• 2、能處理連續(xù)數(shù)據(jù)吱殉，具體方法為：遍歷所有值掸冤，以每個值來作為分割點將所有樣本分為兩類，找到信息增益比最大的點友雳；
• 3稿湿、可以處理缺失值，具體地押赊，僅使用非缺失樣本來計算特征的信息增益饺藤，并將信息增益乘以缺失率以降低顯示出缺失的影響，而對于缺失樣本則是將缺失樣本以某個概率分到子節(jié)點流礁；
• 4涕俗、添加了剪枝來防止過擬合，有兩種剪枝策略：
  • 預(yù)剪枝：在建樹的過程中如果分裂后的準(zhǔn)確率變低了神帅，則停止分裂再姑。這是一種貪心算法，可能得不到全局最優(yōu)解找御；
  • 后剪枝：在完成建樹后元镀，依次刪掉葉子節(jié)點并求準(zhǔn)確率，最后通過比較就能得到最好的樹霎桅。能得到全局最優(yōu)解栖疑，但是算法復(fù)雜度較大；

C4.5樹仍然使用的是多叉樹滔驶，因此每個特征僅使用一次遇革，在后續(xù)分裂中不再使用。且只能用于分類瓜浸。

CART決策樹

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

• CART決策樹使用二叉樹澳淑，效率高，且特征可以重復(fù)使用插佛；
• 使用gini系數(shù)來最為分裂標(biāo)準(zhǔn)杠巡，計算復(fù)雜度大大降低；
• 缺失值處理：分裂時仍然是僅考慮CART樹并通過乘以一個系數(shù)來顯示缺失值的影響雇寇；而對于缺失值如何劃分到子節(jié)點氢拥，則是使用了一種較為復(fù)雜的代理分裂的策略蚌铜，簡單理解即是對于這些缺失的樣本選擇別的特征來計算gini增益，如果又碰到了缺失嫩海，就需要再次找代理特征冬殃。。叁怪。审葬；
• 對于回歸問題，使用最小方差（也即均方誤差）和來作為分裂標(biāo)準(zhǔn)奕谭；
• 使用代價復(fù)雜度剪枝策略涣觉，即不僅考慮了準(zhǔn)確率，還將樹的復(fù)雜度考慮進(jìn)去了血柳。

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

隨機(jī)森林屬于bagging算法官册，有兩個隨機(jī)過程：

• 1、對于每顆子樹难捌，有放回的隨機(jī)選擇N個樣本（即bootstrap抽樣）膝宁；
• 2、在每個結(jié)點分裂時根吁，先隨機(jī)選擇m個特征员淫，然后按照某個分裂標(biāo)準(zhǔn)從這些特征中選擇分裂特征；

預(yù)測時击敌，分類問題投票满粗，回歸問題求平均。

優(yōu)點：

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

梯度提升樹（Gradient Boosting Decision Tree）

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

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

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

在梯度提升決策樹中寿烟，還添加了shrinkage澈驼，這個是與adaboost的一個重大區(qū)別，相當(dāng)于學(xué)習(xí)率筛武，控制每棵樹學(xué)習(xí)到更少的東西缝其，使用更多的樹來進(jìn)行集成學(xué)習(xí)挎塌。

缺點：

• 對異常點敏感，可通過huber loss來進(jìn)行緩解内边；
• 沒有剪枝策略榴都；

XGBOOST

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

xgb原始loss

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

這里我們簡單說一下模型復(fù)雜度的組成快鱼，第一項 γT其實是控制的樹的葉子節(jié)點不要太多（可以理解為參數(shù)不要太多颠印，L1正則化），第二項其實是控制每個葉子結(jié)點的數(shù)值不要太大（可以理解為模型參數(shù)不要太大抹竹，L2正則化）线罕。

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

可以看到窃判，模型的優(yōu)化目標(biāo)其實僅與前一棵樹一階導(dǎo)（G）钞楼、二階導(dǎo)（H）、lambda（可以理解為L2正則化系數(shù)）袄琳、γ（理解為L1正則化系數(shù)）有關(guān)系询件。對于決策樹的每次分裂，我們的目標(biāo)其實就是要使得上面的目標(biāo)函數(shù)值更小唆樊，換句話說宛琅，上面的目標(biāo)函數(shù)就是我們的分裂標(biāo)準(zhǔn)，這與前面所有的決策樹的分裂方式都是完全不同的逗旁。

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

如何選擇分裂特征嘿辟？

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

稀疏感知算法

在分裂選擇特征時箕戳，僅使用非缺失值來進(jìn)行計算增益某残。而對于缺失結(jié)點的劃分，則是將每個缺失樣本分別放入到兩個子節(jié)點中陵吸，哪個增益大就選擇劃分到哪個結(jié)點玻墅。

工程化優(yōu)化

略。壮虫。澳厢。

優(yōu)點：

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

LightGBM

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

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

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

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

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

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

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

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

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

與xgb相比：

• 1憨琳、內(nèi)存更小：

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

• 2遍略、速度更快：

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

基于樹模型的特征選擇

樹模型解釋性較好纽绍，我們常忱倬茫可以通過樹模型來進(jìn)行特征選擇，留下重要特征拌夏。不同樹模型特征重要性評估方法略有區(qū)別僧著。

決策樹履因、隨機(jī)森林、GBDT

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

sklearn API

XGBoost

xgboost的特征重要性評估方法更為多樣，如下：

• weight涤久，也即根據(jù)特征使用的次數(shù)來決定其權(quán)重澈缺；
• gain，根據(jù)收益（也即loss減小量）來決定其收益，其又可以分為兩種：
  • gain作谭，平均每次使用特征獲得的收益；
  • total_gain箍铭，使用某個特征的收益總和螟炫；
• cover，覆蓋率仅醇，也即這個特征覆蓋了多少個樣本冗美，同樣也分為兩種：
  • cover，平均覆蓋率析二，平均每次使用特征覆蓋的樣本數(shù)量（或者說覆蓋率）粉洼；
  • total_cover，總覆蓋率叶摄，某個特征總覆蓋率属韧。

LightGBM

lightGBM的特征評估方式如下：

• split蛤吓，也即特征使用次數(shù)宵喂，與xgboost中的weight是一致的；
• gain会傲，使用特征的總收益（也即loss減泄亍），與xgboost中的total_gain相同淌山。

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