之前介紹過梯度下降法與牛頓法米者，GBDT與XGBoost就與這兩種方法有關(guān)汉矿。

boosting(包括GBDT热押、XGBoost)是一個加法模型，有以下優(yōu)缺點：

優(yōu)點：
? 可解釋性強
? 可處理混合類型特征
? 具體伸縮不變性（不用歸一化特征）
? 有特征組合的作用
? 可自然地處理缺失值
? 對異常點魯棒
? 有特征選擇作用
? 可擴展性強动猬，容易并行
缺點：
? 缺乏平滑性（回歸預(yù)測時輸出值只能輸出有限的若干種數(shù)值）
? 不適合處理高維稀疏數(shù)據(jù)

一、GBDT

GBDT泛指所有梯度提升樹算法表箭，包括XGBoost赁咙，它也是GBDT的一種變種，為了區(qū)分它們，GBDT一般特指“Greedy Function Approximation：A Gradient Boosting Machine”里提出的算法彼水，只用了一階導(dǎo)數(shù)信息崔拥。

GBDT是在函數(shù)空間上利用梯度下降進行優(yōu)化
GBDT是多個弱分類器合成強分類器的過程(加權(quán)求和)，每次迭代產(chǎn)生一個弱分類器凤覆，當(dāng)前弱分類器是在之前分類器殘差基礎(chǔ)上訓(xùn)練链瓦。
目標(biāo)：損失函數(shù)盡可能快減小，則讓損失函數(shù)沿著梯度方向下降盯桦。--> gbdt 的gb的核心了慈俯。

算法流程如下：

2.1 ：求之前分類器損失函數(shù)的負梯度作為本次弱分類器需要擬合的輸出
2.2：對回歸樹的學(xué)習(xí)，一般選擇CART TREE（分類回歸樹）拥峦，對應(yīng)的葉節(jié)點區(qū)域為w贴膘，CART TREE生成就用平方誤差最小化
2.3：在葉結(jié)點區(qū)域上損失函數(shù)最小，求弱分類器權(quán)重
2.4：合成新的分類器

算法流程圖也可以如下圖：

不同問題的提升樹學(xué)習(xí)方法使用的損失函數(shù)不同略号，回歸問題一般用平方誤差損失函數(shù)刑峡，分類問題一般用指數(shù)損失函數(shù)，以及其它一般決策問題的一般損失函數(shù)璃哟。

GBDT常用損失函數(shù)
分類算法：
分類算法中CART樹也是采用回歸樹
(1) 指數(shù)損失函數(shù)：

負梯度計算和葉子節(jié)點的最佳負梯度擬合與Adaboost相似氛琢。
(2) 對數(shù)損失函數(shù)：
二元分類：

多元分類：

回歸算法：
(1)均方差：

(2)絕對損失：

負梯度誤差為：

(3)Huber損失：
均方差和絕對損失的折中，對遠離中心的異常點随闪，采用絕對損失阳似，而中心附近的點采用均方差。界限一般用分位數(shù)點度量铐伴。損失函數(shù)如下：

負梯度誤差：

(4) 分位數(shù)損失：分位數(shù)回歸的損失函數(shù)撮奏，表達式為

θ為分位數(shù)，需要我們在回歸前指定当宴。對應(yīng)的負梯度誤差為：

Huber損失和分位數(shù)損失畜吊，減少異常點對損失函數(shù)的影響。

問題：GBDT如何減少異常點的影響户矢？

(1) 使用健壯損失函數(shù)玲献，如Huber損失函數(shù)和分位數(shù)（Quantile）損失函數(shù)；
(2) 增加正則化項梯浪；
(3) 采用無放回的子采樣捌年。
異常點的魯棒性，隨機森林要比GBDT好挂洛。原因是GBDT的模型在迭代過程中較遠的異常點殘差往往會比正常點大礼预，導(dǎo)致最終建立的模型出現(xiàn)偏差。一般的經(jīng)驗是虏劲，異常點少的樣本集GBDT表現(xiàn)更加優(yōu)秀托酸，而異常點多的樣本集褒颈，隨機森林表現(xiàn)更好。

GBDT優(yōu)點：

（1）處理各種類型的數(shù)據(jù)(非線性數(shù)據(jù))励堡，包括連續(xù)值和離散值谷丸，處理多特征類型。
（2）在相對少的調(diào)參時間情況下念秧，預(yù)測的準備率也可以比較高(相對SVM)淤井。
（樹的個數(shù) 100~10000、葉子的深度 3~8摊趾、學(xué)習(xí)速率 0.01~1币狠、葉子上最大節(jié)點樹 20、訓(xùn)練采樣比例 0.5~1砾层、訓(xùn)練特征采樣比例 (√n)(n)）
（3）能適應(yīng)多種損失函數(shù)漩绵，使用健壯的損失函數(shù)，對異常值的魯棒性強肛炮。如 Huber損失函數(shù)和Quantile損失函數(shù)止吐。
（4）適合低維稠密數(shù)據(jù)，模型可解釋性好
（5）不需要做特征的歸一化侨糟，可以自動選擇特征

GBDT缺點：

（1）弱學(xué)習(xí)器之間依賴碍扔，難以并行訓(xùn)練數(shù)據(jù)★踔兀可以通過自采樣SGBT達到部分并行不同。
（2）計算復(fù)雜度大
（3）不使用高維稀疏特征

Adaboost與GBDT：

Adaboost是通過提高錯分樣本的權(quán)重來定位模型的不足，采用指數(shù)損失溶耘，基分類器是最常見為決策樹(深度為1)
GBDT是通過負梯度來定位模型的不足二拐，因此GBDT可以使用更多種類的損失函數(shù)

RF與GBDT：

1、組成RF的樹可以是分類樹凳兵，也可以是回歸樹百新；而GBDT只由回歸樹組成，因為GBDT對所有樹的結(jié)果累加庐扫，累加無法通過分類完成
2饭望、組成RF的樹并行生成；GBDT串行生成 形庭，GBDT更容易過擬合
3杰妓、輸出結(jié)果，RF采用多數(shù)投票等碘勉；GBDT將所有結(jié)果累加，或加權(quán)累加
4桩卵、RF對異常值不敏感验靡，GBDT對異常值敏感
5倍宾、RF對訓(xùn)練集一視同仁，每棵樹分裂特征隨機胜嗓；GBDT基于權(quán)值的弱分類器的集成 高职，前面的樹優(yōu)先分裂對大部分樣本區(qū)分的特征，后分裂對小部分樣本區(qū)分的特征
6辞州、RF通過減少模型方差提高性能怔锌，GBDT通過減少模型偏差提高性能(低方差和高偏差)
7、RF參數(shù)主要是樹的棵樹变过，GBDT主要是樹的深度埃元，一般為1

RF優(yōu)點：

1、易理解和解釋媚狰，樹可以被可視化岛杀。
2、不需要太多的數(shù)據(jù)預(yù)處理崭孤，不需要數(shù)據(jù)歸一化等类嗤。
3、隱含創(chuàng)造多個聯(lián)合特征辨宠，解決非線性問題遗锣。
4、和決策樹模型嗤形、GBDT模型相比精偿，RF不易過擬合。
5派殷、自帶out-of-bag (oob)錯誤評估功能还最。 RF的重要特性是不用進行交叉驗證或使用一個獨立的測試集獲得無偏估計，它可以在內(nèi)部進行評估毡惜，在生成的過程中可以對誤差進行無偏估計拓轻，由于每個基學(xué)習(xí)器只使用了訓(xùn)練集中約63.2%的樣本，剩下約36.8%的樣本可用做驗證集來對其泛化性能進行‘包外估計’经伙。
6扶叉、易于并行化。

RF缺點：

1帕膜、不適合小樣本枣氧，只適合大樣本。
2垮刹、大多數(shù)情況下达吞，RF模型的精度略低于GBDT模型的精度。
3荒典、適合決策邊界是矩形的酪劫，不適合對角線型的吞鸭。

二、XGBoost

XGBoost應(yīng)用牛頓法(二階泰勒展開)
加入正則項覆糟，對每棵樹的復(fù)雜度進行懲罰刻剥，防止過擬合

XGBoost目標(biāo)函數(shù)及歸一化公式

歸一化解釋

XGBoost參數(shù)定義

XGBoost第t次迭代：訓(xùn)練第t棵子樹，損失函數(shù)最小求參數(shù)滩字，計算過程如下

上圖最小損失L是衡量第t棵CART樹的結(jié)構(gòu)好壞的標(biāo)準造虏。L只和Gj和Hj和T有關(guān)，它們又只和樹的結(jié)構(gòu)(q(x))有關(guān)麦箍，與葉子節(jié)點的值沒有關(guān)系漓藕。

假設(shè)分到j(luò)這個葉子節(jié)點上的樣本只有一個。那么内列，w*_j如下：

撵术，w*_j的最佳值是負的梯度乘以權(quán)重系數(shù)，該系數(shù)類似于隨機梯度下降中的學(xué)習(xí)率话瞧。h_j越大嫩与，系數(shù)越小，學(xué)習(xí)率越小交排。h_j代表在該點附近梯度變化非常劇烈划滋，只要一點改變，梯度就從10000變到了1埃篓，所以在使用反向梯度更新時步子就要小处坪，也就是權(quán)重系數(shù)要更小。

回歸樹的學(xué)習(xí)策略

XGBoost的打分函數(shù)

上圖中Gain是單節(jié)點的L*減去切分后的兩個節(jié)點的樹L*架专，Gain如果是正的同窘，且值越大，表示切分后L*越小于單節(jié)點的L*部脚，越值得切分想邦。Gain的左半部分如果小于右側(cè)的γ，則Gain就是負的委刘，表明切分后L*變大丧没。γ是一個臨界值，值越大锡移，表示對切分后L*下降幅度要求越嚴呕童。這個值可以在xgboost中設(shè)定。

γ是加入新葉子節(jié)點引入的復(fù)雜度代價

xgboost切分和普通的決策樹切分過程不同淆珊。普通的決策樹在切分的時候并不考慮樹的復(fù)雜度夺饲，而依賴后續(xù)的剪枝操作來控制。xgboost在切分的時候就考慮樹的復(fù)雜度，就是γ參數(shù)往声。不需要進行單獨的剪枝操作茫蛹。

樹節(jié)點分裂方法

對于連續(xù)型特征值，當(dāng)樣本數(shù)量非常大烁挟，特征取值過多時，遍歷所有取值會花費很多時間骨坑，且容易過擬合撼嗓。因此XGBoost思想是對特征進行分桶，即找到l個劃分點欢唾，將位于相鄰分位點之間的樣本分在一個桶中且警。在遍歷該特征的時候，只需要遍歷各個分位點礁遣，從而計算最優(yōu)劃分斑芜。從算法偽代碼中該流程還可以分為兩種，全局的近似是在新生成一棵樹之前就對各個特征計算分位點并劃分樣本祟霍，之后在每次分裂過程中都采用近似劃分杏头，而局部近似就是在具體的某一次分裂節(jié)點的過程中采用近似算法。
近似算法流程如下：

尋找分為點可以使用Weighted Quantile Sketch—分布式加權(quán)直方圖算法

稀疏值處理

輸入x稀疏很常見沸呐。 稀疏性有多種可能原因：
（1）數(shù)據(jù)中存在缺失值
（2）統(tǒng)計中頻繁的零項
（3）特征工程醇王，例如one-hot編碼。
特征值缺失時崭添，無法利用該特征進行劃分寓娩，則將每個樹節(jié)點中添加一個默認方向，如下圖呼渣，當(dāng)稀疏矩陣x中缺少一個值時棘伴，樣本被分類為默認方向。
默認方向選擇：將該樣本分別劃分到左結(jié)點和右結(jié)點屁置，計算增益焊夸，分到增益大的一側(cè)。

關(guān)鍵的改進是只訪問非缺失的條目I_k缰犁。 所提出的算法將不存在的值視為缺失值并且學(xué)習(xí)處理缺失值的最佳方向淳地。稀疏感知算法運行速度比初始版本快50倍

XGBoost的其它特性

Shrinkage and Column Subsampling
Shrinkage and Column Subsampling均是為了防止過擬合

Shrinkage：每次迭代中對樹的每個葉子結(jié)點的分數(shù)乘上一個縮減權(quán)重η，降低了每棵獨立樹的影響帅容，并為將颇象，留更大的空間給后面生成的樹去優(yōu)化模型。類似于學(xué)習(xí)速率并徘。
Column Subsampling：類似于隨機森林中的選取部分特征進行建樹遣钳。
一種是按層隨機采樣，在對同一層內(nèi)每個結(jié)點分裂之前麦乞，先隨機選擇一部分特征蕴茴，然后只需要遍歷這部分的特征劝评，來確定最優(yōu)的分割點。
另一種是隨機選擇特征倦淀，建樹前隨機選擇一部分特征然后分裂就只遍歷這些特征蒋畜。一般情況下前者效果更好。

XGBoost的系統(tǒng)設(shè)計

Column Block
xgboost的并行不是tree粒度的并行撞叽，而是特征粒度上姻成。

決策樹學(xué)習(xí)中最耗時的部分是將數(shù)據(jù)按照特征值進行排序。為了降低排序成本愿棋，xgboost將數(shù)據(jù)存儲在內(nèi)存單元中（block）科展。每個block數(shù)據(jù)以壓縮列（CSC）格式存儲，每列按特征值排序糠雨。輸入數(shù)據(jù)布局僅需要在訓(xùn)練之前計算一次才睹，在以后的迭代中重復(fù)使用，減少了計算量甘邀。block結(jié)構(gòu)使并行變成可能琅攘。在進行結(jié)點的分裂時，需要計算每個特征的增益鹃答，最終選擇增益最大的特征做分裂乎澄，各個特征的增益計算可以多進程進行。

1测摔、精確的貪婪算法：整個數(shù)據(jù)集存儲在一個block置济，通過線性掃描預(yù)先排序的條目來運行拆分搜索算法。對所有葉子集體的進行拆分查找锋八，因此對block進行一次掃描將收集所有葉子分支中的劃分候選者的統(tǒng)計數(shù)據(jù)浙于。
2、近似算法：block結(jié)構(gòu)也是有效的挟纱。使用多個塊羞酗，每個block對應(yīng)數(shù)據(jù)集中行的子集。不同的block可以跨機器分布紊服，也可以在核外設(shè)置中存儲在磁盤上檀轨。使用排序結(jié)構(gòu)，quantile查找步驟變?yōu)閷ε判蛄械木€性掃描欺嗤。對經(jīng)常在每個分支處生成的局部提議算法有用参萄，直方圖聚合中的二分搜索也變?yōu)榫€性時間合并樣式算法。煎饼。

緩存感知訪問（Cache-aware Access）

Column Block算法通過行索引間接提取梯度統(tǒng)計讹挎，由于值是按特征的順序訪問的。 這是一種非連續(xù)的內(nèi)存訪問。 分裂枚舉的簡單實現(xiàn)在累積和非連續(xù)存儲器read/write操作之間引入了immediate read/write依賴性筒溃。 當(dāng)梯度統(tǒng)計信息不適合CPU緩存并發(fā)生緩存未命中時马篮，減慢拆分查找速度。

1怜奖、精確的貪心算法：通過緩存感知預(yù)取算法（cache-aware prefetching algorith）緩解問題浑测。 在每個線程中分配一個內(nèi)部緩沖區(qū)，獲取梯度統(tǒng)計信息歪玲，然后以小批量（mini-batch）方式執(zhí)行累積尽爆。 此預(yù)取將direct read/write依賴性更改為更長的依賴性，在有大量行數(shù)時幫助減少運行時開銷读慎。 數(shù)據(jù)集很大時，精確貪婪算法的緩存感知實現(xiàn)的運行速度是普通版本的兩倍槐雾。
2夭委、近似算法：通過選擇正確的塊大小解決問題。將塊大小定義為塊中包含的最大示例數(shù)募强，這反映了梯度統(tǒng)計的高速緩存存儲成本株灸。
選擇過小的塊大小會導(dǎo)致每個線程的工作量很小，并導(dǎo)致低效的并行化擎值。
過大的塊會導(dǎo)致緩存未命中慌烧，因為梯度統(tǒng)計信息不送入CPU緩存。

XGBoost的優(yōu)點

1鸠儿、多種防止過擬合方法屹蚊，正則化、Shrinkage进每、Column Subsampling等汹粤。
2、 目標(biāo)函數(shù)優(yōu)化利用損失函數(shù)關(guān)于待求函數(shù)的二階導(dǎo)數(shù)
3田晚、支持并行化嘱兼，閃光點，雖然樹與樹串行贤徒，但同層級節(jié)點可并行芹壕。候選分裂點計算增益用多線程并行。訓(xùn)練速度快接奈。
4踢涌、添加對稀疏數(shù)據(jù)的處理。
5鲫趁、交叉驗證斯嚎，early stop，當(dāng)預(yù)測結(jié)果已經(jīng)很好的時候可以提前停止建樹，加快訓(xùn)練速度堡僻。
6糠惫、分裂點尋找近似算法。
7钉疫、面向體系結(jié)構(gòu)的優(yōu)化硼讽，針對cache和內(nèi)存做了性能優(yōu)化。

XGBoost與GBDT對比

1牲阁、GBDT以CART作為基分類器固阁，XGBoost還支持線性分類器〕蔷眨可以通過booster[default=gbtree]設(shè)置參數(shù)：gbtree:tree-based models;gblinear:linear models备燃，這個時候xgboost相當(dāng)于帶L1和L2正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題）
2、GBDT用到一階導(dǎo)數(shù)信息凌唬，XGBoost對代價函數(shù)進行了二階泰勒展開并齐，同時用到一階與二階導(dǎo)數(shù)，支持自定義代價函數(shù)(二階可導(dǎo))
3客税、XGBoost在代價函數(shù)中加入正則化項况褪，控制模型復(fù)雜度，降低模型variance更耻，模型更加簡單测垛，防止過擬合，正則項包含樹的葉子節(jié)點個數(shù)秧均、每個葉子節(jié)點上輸出的score的L2模的平方和食侮。代替剪枝
4、分裂結(jié)點處通過結(jié)構(gòu)打分和分割損失動態(tài)生長目胡。結(jié)構(gòu)分數(shù)代替了回歸樹的誤差平方和
5疙描、新增shronkage和column subsampling，為了防止過擬合
6讶隐、對缺失值處理起胰。對特征值有缺失的樣本，XGBoost可以自動學(xué)習(xí)它的分裂方向
7巫延、 xgboost工具支持并行效五。
8、可并行的近似直方圖算法
9炉峰、Xgboost的訓(xùn)練速度快于GBDT畏妖，10倍量級。

GBDT算法流程明確下一次擬合的是損失的負梯度方向疼阔，然后擬合回歸樹戒劫，最后計算疊加后強分類器的損失
XGBoost流程是從損失函數(shù)最小化開始推導(dǎo)半夷，得到當(dāng)前這顆樹最優(yōu)權(quán)重和和分裂權(quán)重，分裂權(quán)重與損失一次導(dǎo)數(shù)和二次導(dǎo)數(shù)均有關(guān)系

問題：XGBoost為什么使用CART樹而不是用普通的決策樹呢迅细？

分類問題巫橄，CART樹的葉子節(jié)點對應(yīng)的值是一個實際的分數(shù)，而非一個確定的類別茵典，有利于實現(xiàn)高效的優(yōu)化算法湘换。XGBoost一是準，二是快统阿，之所以快彩倚，其中有選用CART樹的一份功勞。

XGBoost參數(shù)說明

補充：CART樹

回歸樹生成算法如下扶平，使用最小二乘偏差（LSD）帆离。

分類樹算法流程如下，使用GINI指數(shù)

(1)對每個特征 A所有可能取值 a结澄，將數(shù)據(jù)集分為 A＝a和 A!＝a 兩個子集盯质，計算集合 D 基尼指數(shù)
(2)遍歷所有的特征 A，計算所有可能取值 a 的基尼指數(shù)概而，選擇 D 的基尼指數(shù)最小值對應(yīng)的特征及切分點作為最優(yōu)劃分，數(shù)據(jù)分為兩個子集囱修。
(3)上述兩個子節(jié)點遞歸調(diào)用步驟(1)(2)赎瑰，直到滿足停止條件。
(4)生成 CART 決策樹破镰。

GINI

GINI 指數(shù)：

1餐曼、一種不等性度量；
2鲜漩、介于 0~1 之間的數(shù)源譬，0-完全相等，1-完全不相等孕似；
3踩娘、總體內(nèi)包含的類別越雜亂，GINI指數(shù)就越大（跟熵的概念很相似）

分類中喉祭，假設(shè) K 個類，樣本屬于第 k 類的概率為 p_k，概率分布的基尼指數(shù)為：

樣本集合 D 的基尼指數(shù)為：

C_k為數(shù)據(jù)集D中屬于第k類的樣本子集峰弹，| * |表示樣本集中樣本的個數(shù)距辆。
數(shù)據(jù)集 D 根據(jù)特征 A 在某一取值 a 上進行分割，得到 D₁蔽氨、D₂兩部分藐唠，則在特征 A 下集合 D 的基尼指數(shù)為：

停止條件：

1帆疟、節(jié)點中樣本個數(shù)小于設(shè)定閾值
2、樣本集Gini系數(shù)小于設(shè)定閾值（樣本基本屬于同一類）
3宇立、沒有更多特征

剪枝
決策樹防止過擬合方法：

1踪宠、閾值控制終止條件，避免樹形結(jié)構(gòu)分支過細
2泄伪、基于Bootstrap思想建立隨機森林
3殴蓬、對已經(jīng)形成決策樹剪枝來避免過擬合

代價復(fù)雜度剪枝 Cost-Complexity Pruning(CCP) 方法對CART剪枝，算法流程如下：

1蟋滴、從整個樹 T₀開始染厅，先剪去一棵子樹，生成子樹 T₁
2津函、在 T₁上再剪去一棵子樹肖粮，生成子樹 T₂
3、重復(fù)尔苦，直到最后只剩一個根節(jié)點的子樹 Tn
4涩馆、得到了子樹序列 T0～Tn
5、利用獨立的驗證數(shù)據(jù)集允坚，計算每個子樹的平方誤差或者基尼指數(shù)
6魂那、選擇誤差最小的子樹作為最優(yōu)的剪枝后樹

其中 C(T)為誤差（例如基尼指數(shù)），|T| 為 T 的葉節(jié)點個數(shù)稠项，alpha 為非負參數(shù)涯雅，用來權(quán)衡訓(xùn)練數(shù)據(jù)的擬合程度和模型的復(fù)雜度。

在計算整體損失函數(shù)時展运，內(nèi)部節(jié)點以外的值都沒變活逆，只有判斷是否剪枝的內(nèi)部節(jié)點的局部損失函數(shù)改變，因此本需要計算全局的損失函數(shù)拗胜，但現(xiàn)在只需要計算內(nèi)部節(jié)點剪枝前和剪枝后的損失函數(shù)蔗候。

對于(3)中的公式，分母是葉子結(jié)點減少的數(shù)量埂软，分子是誤差減小的數(shù)量锈遥，比值是誤差減小率，如果誤差減小率很小勘畔，剪枝迷殿。
每次都剪g(t)最小的T_t，g(t)越小咖杂，增加葉子帶來的誤差減小量越小庆寺，增加這個葉子節(jié)點的作用越小。

剪枝例子如下：

R(t)=C(t)訓(xùn)練數(shù)據(jù)的預(yù)測誤差（如基尼指數(shù)）= 節(jié)點 t 上的數(shù)據(jù)占所有數(shù)據(jù)的比例 * 節(jié)點 t 的誤差率
R(Tt)=C(Tt)是子樹Tt的預(yù)測誤差 = 子樹Tt上所有葉子節(jié)點的預(yù)測誤差之和(葉子節(jié)點的預(yù)測誤差 = 葉子節(jié)點上的數(shù)據(jù)占所有數(shù)據(jù)的比例 * 葉子節(jié)點的誤差率)
節(jié)點 t 的誤差率 = 該節(jié)點較少類別的數(shù)/該節(jié)點類別總數(shù)(大多數(shù)原則诉字，該節(jié)點想要區(qū)分的類別是落在該節(jié)點數(shù)目多的類別)

例如 t₁節(jié)點懦尝，R(t)即剪枝后誤差知纷，數(shù)據(jù)所占比例16/16，節(jié)點誤差率 = 該節(jié)點較少類別的數(shù)/該節(jié)點類別總數(shù) = 8/16
R(Tt)為剪枝前誤差陵霉，即葉子節(jié)點誤差之和琅轧，以該節(jié)點為根節(jié)點的4葉子節(jié)點均只有一個類別的樣本，該節(jié)點較少類別的數(shù)/該節(jié)點類別總數(shù) = 0踊挠，所以R(Tt) = 0

參考