作者：ChrisCao

https://zhuanlan.zhihu.com/p/75468124

一.決策樹

決策樹是一個有監(jiān)督分類模型，本質(zhì)是選擇一個最大信息增益的特征值進(jìn)行輸?shù)姆指?，直到達(dá)到結(jié)束條件或葉子節(jié)點純度達(dá)到閾值。下圖是決策樹的一個示例圖：

根據(jù)分割指標(biāo)和分割方法，可分為：ID3、C4.5、CART算法。

1.ID3算法：以信息增益為準(zhǔn)則來選擇最優(yōu)劃分屬性

信息增益的計算是基于信息熵（度量樣本集合純度的指標(biāo)）

 信息熵越小，數(shù)據(jù)集  的純度越大

假設(shè)基于數(shù)據(jù)集  上建立決策樹，數(shù)據(jù)有  個類別：

公式(1)中：

 表示第K類樣本的總數(shù)占數(shù)據(jù)集D樣本總數(shù)的比例。

公式(2)表示是以特征A作為分割的屬性，得到的信息熵：Di表示的是以屬性A為劃分，分成n個分支，第i個分支的節(jié)點集合。因此，該公式求得的是以屬性A為劃分，n個分支的信息熵總和。

公式(3)是以A為屬性劃分前和劃分后的信息熵差值，也就是信息增益，越大越好。

假設(shè)每個記錄有一個屬性'ID',若按照ID進(jìn)行分割的話，在這個屬性上，能夠取得的特征值是樣本數(shù)，特征數(shù)目太多，無論以哪一個ID進(jìn)行劃分，葉子節(jié)點的值只會有一個，純度很大，得到的信息增益很大，這樣劃分出來的決策樹沒有意義，即，ID3偏向于取值較多的屬性進(jìn)行分割，存在一定的偏好。為減少這一影響，有學(xué)者提出了C4.5算法。

2.C4.5基于信息增益率準(zhǔn)則 選擇最有分割屬性的算法

信息增益率通過引入一個被稱為分裂信息(Split information)的懲罰項來懲罰取值較多的屬性：

 , 

其中，IV(a)是由屬性A的特征值個數(shù)決定的，個數(shù)越多，IV值越大，信息增益率越小，這樣就可以避免模型偏好特征值多的屬性，如果簡單按這個規(guī)則分割，模型又會偏好特征值少的特征，因此C4.5決策樹先從候選劃分屬性中找出信息增益高于平均水平的屬性，在從中選擇增益率最高的。

對于連續(xù)值屬性來說，可取值數(shù)目不再有限，因此可以采用離散化技術(shù)（如二分法）進(jìn)行處理。將屬性值從小到大排序，然后選擇中間值作為分割點，數(shù)值比它小的點被劃分到左子樹，數(shù)值不小于它的點被分到右子樹，計算分割的信息增益率，選擇信息增益率最大的屬性值進(jìn)行分割。

3.CART:以基尼系數(shù)為準(zhǔn)則選擇最優(yōu)劃分屬性，可用于分類和回歸

CART是一棵二叉樹，采用二元切分法，每次把數(shù)據(jù)分成兩份，分別進(jìn)入左子樹、右子樹。并且每個非葉子節(jié)點都有兩個孩子，所以CART的葉子節(jié)點比非葉子節(jié)點多一。相比于ID3和C4.5，CART的應(yīng)用要多一些，既可以用于分類也可以用于回歸。CART分類時，選擇基尼指數(shù)（Gini）為最好的分類特征，gini描述的是純度，與信息熵含義類似，CART中每次迭代都會降低基尼系數(shù)。

Gini(D)反映了數(shù)據(jù)集D的純度，值越小，純度越高。我們在候選集合中選擇使得劃分后基尼指數(shù)最小的屬性作為最優(yōu)化分屬性。

分類樹和回歸樹

先說分類樹，ID3、C4.5在每一次分支時，是窮舉每一個特征屬性的每一個閾值，找到使得按照特征值<=閾值，和特征值>閾值分成的兩個分支的熵最大的特征和閾值。按照該標(biāo)準(zhǔn)分支得到兩個新節(jié)點，用同樣的方法進(jìn)行分支，直到所有人被分入性別唯一的葉子節(jié)點，或達(dá)到預(yù)設(shè)的終止條件，若最終葉子節(jié)點中性別不唯一，則以多數(shù)人的性別作為該葉子節(jié)點的性別。

回歸樹總體流程也是類似，不過在每個節(jié)點(不一定是葉子節(jié)點)都會得到預(yù)測值，以年齡為例，該預(yù)測值等于屬于這個節(jié)點的所有人年齡的平均值。分支時窮舉每個特征的每個閾值，找最好的分割點，但衡量的標(biāo)準(zhǔn)變成了最小化均方誤差，即（每個人的年齡-預(yù)測年齡）^2 的總和 / N，或者說是每個人的預(yù)測誤差平方和 除以 N。這很好理解，被預(yù)測出粗的人數(shù)越多，錯的越離譜，均方誤差越大，通過最小化均方誤差找最靠譜的分支依據(jù)。分支直到每個葉子節(jié)點上的人的年齡都唯一(這太難了)，或者達(dá)到預(yù)設(shè)的終止條件(如葉子個數(shù)上限)，若最終葉子節(jié)點上人的年齡不唯一，則以該節(jié)點上所有人的平均年齡作為該葉子節(jié)點的預(yù)測年齡。

二.隨機(jī)森林

先補(bǔ)充組合分類器的概念，將多個分類器的結(jié)果進(jìn)行多票表決或取平均值，以此作為最終的結(jié)果。

1.構(gòu)建組合分類器的好處：

(1)提升模型精度：整合各個模型的分類結(jié)果，得到更合理的決策邊界，減少整體錯誤呢，實現(xiàn)更好的分類效果：

(2)處理過大或過小的數(shù)據(jù)集：數(shù)據(jù)集較大時，可將數(shù)據(jù)集劃分成多個子集，對子集構(gòu)建分類器；當(dāng)數(shù)據(jù)集較小時，通過自助采樣(bootstrap)從原始數(shù)據(jù)集采樣產(chǎn)生多組不同的數(shù)據(jù)集，構(gòu)建分類器。

(3)若決策邊界過于復(fù)雜，則線性模型不能很好地描述真實情況。因此，現(xiàn)對于特定區(qū)域的數(shù)據(jù)集，訓(xùn)練多個線性分類器，再將他們集成。

(4)比較適合處理多源異構(gòu)數(shù)據(jù)（存儲方式不同（關(guān)系型、非關(guān)系型），類別不同（時序型、離散型、連續(xù)型、網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)））

隨機(jī)森林是一個多決策樹的組合分類器，隨機(jī)主要體現(xiàn)在兩個方面：數(shù)據(jù)選取的隨機(jī)性和特征選取的隨機(jī)性。

(1)數(shù)據(jù)的隨機(jī)選取

第一，從原始數(shù)據(jù)集中采取有放回的抽樣(bootstrap),構(gòu)造子數(shù)據(jù)集，子數(shù)據(jù)集扥數(shù)量和原始數(shù)據(jù)集的數(shù)量一樣。不同的子數(shù)據(jù)集的元素可以重復(fù)，同一個子數(shù)據(jù)集中的元素也可以重復(fù)。

第二，利用子數(shù)據(jù)集構(gòu)建子決策樹，將這個數(shù)據(jù)放到每個子決策樹中，每個子決策樹輸出一個結(jié)果。最后，如果有了新的數(shù)據(jù)需啊喲通過隨機(jī)森林得到分類結(jié)果，就可以通過子決策樹的判斷結(jié)果來投票，得到隨機(jī)森林的輸出結(jié)果。如下圖，假設(shè)隨機(jī)森林中有3棵子決策樹，2棵子樹的分類結(jié)果是A類，1棵子樹的分類結(jié)果是B類，那么隨機(jī)森林的分類結(jié)果就是A類。

(2)待選特征的隨機(jī)選取

類似于數(shù)據(jù)集的隨機(jī)選取，隨即森林中的子樹的每一個分裂過程并未用到所有的待選特征，而是從所有的待選特征中隨機(jī)選取一定的特征，之后再在隨機(jī)選取的特征中選擇最優(yōu)的特征。這樣能使隨機(jī)森林中的決策樹能不同，提升系統(tǒng)的多樣性，從而提升分類性能。

組合樹示例圖

三、GBDT和XGBoost

1.在講GBDT和XGBoost之前先補(bǔ)充Bagging和Boosting的知識。

Bagging是并行的學(xué)習(xí)算法，思想很簡單，即每一次從原始數(shù)據(jù)中根據(jù)均勻概率分布有放回的抽取和原始數(shù)據(jù)集一樣大小的數(shù)據(jù)集合。樣本點可以出現(xiàn)重復(fù)，然后對每一次產(chǎn)生的數(shù)據(jù)集構(gòu)造一個分類器，再對分類器進(jìn)行組合。

Boosting的每一次抽樣的樣本分布是不一樣的，每一次迭代，都是根據(jù)上一次迭代的結(jié)果，增加被錯誤分類的樣本的權(quán)重。使模型在之后的迭代中更加注重難以分類的樣本。這是一個不斷學(xué)習(xí)的過程，也是一個不斷提升的過程，這就是Boosting思想的本質(zhì)所在。迭代之后，將每次迭代的基分類器進(jìn)行集成，那么如何進(jìn)行樣本權(quán)重的調(diào)整和分類器的集成是我們需要考慮的關(guān)鍵問題。

Boosting算法結(jié)構(gòu)圖

以著名的Adaboost算法舉例：

有一個數(shù)據(jù)集，樣本大小為N，每一個樣本對應(yīng)一個原始標(biāo)簽起初，我們初始化樣本的權(quán)重為1/N

 計算的是當(dāng)前數(shù)據(jù)下，模型的分類誤差率，模型的系數(shù)值是基于分類誤差率的

根據(jù)模型的分類結(jié)果，更新原始數(shù)據(jù)中數(shù)據(jù)的分布，增加被錯分的數(shù)據(jù)被抽中的概率，以便下一次迭代的時候能被模型重新訓(xùn)練

最終的分類器是各個基分類器的組合

2.GBDT

GBDT是以決策樹(CART)為基學(xué)習(xí)器的GB算法，是迭代樹而不是分類樹，Boost是'提升'的意思，一般Boosting算法都是一個迭代的過程，每一次新的訓(xùn)練都是為了改進(jìn)上一次的結(jié)果。有了前面Adaboost的鋪墊，大家應(yīng)該能很容易理解大體思想。

GBDT的核心是：每一棵樹學(xué)習(xí)的是之前所有樹結(jié)論和的殘差。這個殘差就是一個加預(yù)測值后能得真實值的累加量。比如A的真實年齡是18歲，但第一棵樹的預(yù)測年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹里我們把A的年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹真的能把A分到6歲的葉子節(jié)點，那累加兩棵樹的結(jié)論就是A的真實年齡；如果第二棵樹的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹里A的年齡就變成1歲，繼續(xù)學(xué)習(xí)。

3.XGBoost

XGBoostt相比于GBDT來說，更加有效應(yīng)用了數(shù)值優(yōu)化，最重要是對損失函數(shù)（預(yù)測值和真實值的誤差）變得更復(fù)雜。目標(biāo)函數(shù)依然是所有樹的預(yù)測值相加等于預(yù)測值。

損失函數(shù)如下，引入了一階導(dǎo)數(shù)，二階導(dǎo)數(shù)：

好的模型需要具備兩個基本要素：一是要有好的精度（即好的擬合程度），二是模型要盡可能的簡單（復(fù)雜的模型容易出現(xiàn)過擬合，并且更加不穩(wěn)定）因此，我們構(gòu)建的目標(biāo)函數(shù)右邊第一項是模型的誤差項，第二項是正則化項（也就是模型復(fù)雜度的懲罰項）

常用的誤差項有平方誤差和邏輯斯蒂誤差，常見的懲罰項有l(wèi)1，l2正則，l1正則是將模型各個元素進(jìn)行求和，l2正則是對元素求平方。

每一次迭代，都在現(xiàn)有樹的基礎(chǔ)上，增加一棵樹去擬合前面樹的預(yù)測結(jié)果與真實值之間的殘差

目標(biāo)函數(shù)如上圖，最后一行畫圈部分實際上就是預(yù)測值和真實值之間的殘差

先對訓(xùn)練誤差進(jìn)行展開：

xgboost則對代價函數(shù)進(jìn)行了二階泰勒展開，同時用到了殘差平方和的一階和二階導(dǎo)數(shù)

再研究目標(biāo)函數(shù)中的正則項：

樹的復(fù)雜度可以用樹的分支數(shù)目來衡量，樹的分支我們可以用葉子結(jié)點的數(shù)量來表示

那么樹的復(fù)雜度式子：右邊第一項是葉子結(jié)點的數(shù)量T，第二項是樹的葉子結(jié)點權(quán)重w的l2正則化，正則化是為了防止葉子結(jié)點過多

此時，每一次迭代，相當(dāng)于在原有模型中增加一棵樹，目標(biāo)函數(shù)中，我們用wq（x）表示一棵樹，包括了樹的結(jié)構(gòu)以及葉子結(jié)點的權(quán)重，w表示權(quán)重（反映預(yù)測的概率），q表示樣本所在的索引號（反映樹的結(jié)構(gòu)）

將最終得到的目標(biāo)函數(shù)對參數(shù)w求導(dǎo)，帶回目標(biāo)函數(shù)，可知目標(biāo)函數(shù)值由紅色方框部分決定：

因此，xgboost的迭代是以下圖中g(shù)ain式子定義的指標(biāo)選擇最優(yōu)分割點的：

那么如何得到優(yōu)秀的組合樹呢？

一種辦法是貪心算法，遍歷一個節(jié)點內(nèi)的所有特征，按照公式計算出按照每一個特征分割的信息增益，找到信息增益最大的點進(jìn)行樹的分割。增加的新葉子懲罰項對應(yīng)了樹的剪枝，當(dāng)gain小于某個閾值的時候，我們可以剪掉這個分割。但是這種辦法不適用于數(shù)據(jù)量大的時候，因此，我們需要運(yùn)用近似算法。

另一種方法：XGBoost在尋找splitpoint的時候，不會枚舉所有的特征值，而會對特征值進(jìn)行聚合統(tǒng)計，按照特征值的密度分布，構(gòu)造直方圖計算特征值分布的面積，然后劃分分布形成若干個bucket(桶)，每個bucket的面積相同，將bucket邊界上的特征值作為split
point的候選，遍歷所有的候選分裂點來找到最佳分裂點。

上圖近似算法公式的解釋：將特征k的特征值進(jìn)行排序，計算特征值分布，rk（z）表示的是對于特征k而言，其特征值小于z的權(quán)重之和占總權(quán)重的比例，代表了這些特征值的重要程度，我們按照這個比例計算公式，將特征值分成若干個bucket，每個bucket的比例相同，選取這幾類特征值的邊界作為劃分候選點，構(gòu)成候選集；選擇候選集的條件是要使得相鄰的兩個候選分裂節(jié)點差值小于某個閾值

綜合以上所述，我們可以得到xgboost相比于GBDT的創(chuàng)新之處：

傳統(tǒng)GBDT以CART作為基分類器，xgboost還支持線性分類器，這個時候xgboost相當(dāng)于帶L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）。

• 傳統(tǒng)GBDT在優(yōu)化時只用到一階導(dǎo)數(shù)信息，xgboost則對代價函數(shù)進(jìn)行了二階泰勒展開，同時用到了一階和二階導(dǎo)數(shù)。順便提一下，xgboost工具支持自定義代價函數(shù)，只要函數(shù)可一階和二階求導(dǎo)。

• xgboost在代價函數(shù)里加入了正則項，用于控制模型的復(fù)雜度。正則項里包含了樹的葉子節(jié)點個數(shù)、每個葉子節(jié)點上輸出的score的L2模的平方和。從Bias-variance tradeoff角度來講，正則項降低了模型的variance，使學(xué)習(xí)出來的模型更加簡單，防止過擬合，這也是xgboost優(yōu)于傳統(tǒng)GBDT的一個特性。

• Shrinkage（縮減），相當(dāng)于學(xué)習(xí)速率（xgboost中的eta）。每次迭代，增加新的模型，在前面成上一個小于1的系數(shù)，降低優(yōu)化的速度，每次走一小步逐步逼近最優(yōu)模型比每次走一大步逼近更加容易避免過擬合現(xiàn)象；

• 列抽樣（column subsampling）。xgboost借鑒了隨機(jī)森林的做法，支持列抽樣（即每次的輸入特征不是全部特征），不僅能降低過擬合，還能減少計算，這也是xgboost異于傳統(tǒng)gbdt的一個特性。

• 忽略缺失值：在尋找splitpoint的時候，不會對該特征為missing的樣本進(jìn)行遍歷統(tǒng)計，只對該列特征值為non-missing的樣本上對應(yīng)的特征值進(jìn)行遍歷，通過這個工程技巧來減少了為稀疏離散特征尋找splitpoint的時間開銷

• 指定缺失值的分隔方向：可以為缺失值或者指定的值指定分支的默認(rèn)方向，為了保證完備性，會分別處理將missing該特征值的樣本分配到左葉子結(jié)點和右葉子結(jié)點的兩種情形，分到那個子節(jié)點帶來的增益大，默認(rèn)的方向就是哪個子節(jié)點，這能大大提升算法的效率。

• 并行化處理：在訓(xùn)練之前，預(yù)先對每個特征內(nèi)部進(jìn)行了排序找出候選切割點，然后保存為block結(jié)構(gòu)，后面的迭代中重復(fù)地使用這個結(jié)構(gòu)，大大減小計算量。在進(jìn)行節(jié)點的分裂時，需要計算每個特征的增益，最終選增益最大的那個特征去做分裂，那么各個特征的增益計算就可以開多線程進(jìn)行，即在不同的特征屬性上采用多線程并行方式尋找最佳分割點。