作者：ChrisCao

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

一.決策樹

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

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

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

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

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

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

公式(1)中：

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

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

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

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

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

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

 , 

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

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

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

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

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

分類樹和回歸樹

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

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

二.隨機(jī)森林

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

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

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

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

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

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

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

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

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

第二，利用子數(shù)據(jù)集構(gòu)建子決策樹，將這個(gè)數(shù)據(jù)放到每個(gè)子決策樹中，每個(gè)子決策樹輸出一個(gè)結(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ī)選取，隨即森林中的子樹的每一個(gè)分裂過程并未用到所有的待選特征，而是從所有的待選特征中隨機(jī)選取一定的特征，之后再在隨機(jī)選取的特征中選擇最優(yōu)的特征。這樣能使隨機(jī)森林中的決策樹能不同，提升系統(tǒng)的多樣性，從而提升分類性能。

組合樹示例圖

三、GBDT和XGBoost

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

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

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

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

以著名的Adaboost算法舉例：

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

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

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

最終的分類器是各個(gè)基分類器的組合

2.GBDT

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

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

3.XGBoost

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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