前言
xgboost是一種集成學(xué)習(xí)算法驶忌，通過(guò)回歸樹叠骑，每一次對(duì)殘差（實(shí)際值與預(yù)測(cè)值之差）進(jìn)行擬合，最后把預(yù)測(cè)值相加得到最終的預(yù)測(cè)值固该。比如一個(gè)小男孩是10歲伸眶，我用一棵樹去擬合劫侧，得到4.殘差是6惭蹂，第二課樹擬合挪捕，得到3，這時(shí)殘差是3.第三棵樹繼續(xù)擬合拼坎，得到2.這時(shí)我們的預(yù)測(cè)值就是4+3+2=9.和實(shí)際值10比較接近了浮毯。
淺析
1）先看下前言說(shuō)的相加的數(shù)學(xué)公式。
q代表每棵樹的結(jié)構(gòu)演痒，通過(guò)它我們能知道每個(gè)樣本在每棵樹的位置。T是樹的葉子數(shù)趋惨。
2）然后我們看下目標(biāo)函數(shù)的形式
是樣本i的預(yù)測(cè)值鸟顺，
則是樣本i的實(shí)際值。w代表每個(gè)葉子節(jié)點(diǎn)的分?jǐn)?shù)。l(
,
)代表預(yù)測(cè)值與真實(shí)值的差異讯嫂。
(f)作為懲罰項(xiàng)蹦锋，主要是降低模型的復(fù)雜度，避免過(guò)擬合欧芽。懲罰主要包含兩個(gè)方面莉掂，
T表示更少的葉子數(shù)，而||w||的平方項(xiàng)則希望更小的葉子節(jié)點(diǎn)分?jǐn)?shù)千扔。
3）我們先令=
+
(
).其中
表示前t-1顆樹對(duì)樣本i的預(yù)測(cè)值之和憎妙，而
(
)表示第t棵樹對(duì)樣本i的預(yù)測(cè)值，然后對(duì)equ2進(jìn)行泰勒二階展開曲楚。
上式便是泰勒二階展開公式厘唾。equ2按照泰勒公式展開后如下
為一階導(dǎo)數(shù)，
為二階導(dǎo)數(shù)龙誊。仔細(xì)看equ2似乎和泰勒展開表達(dá)式不太一樣抚垃，可以把l(
,
)當(dāng)成是f(x),
x當(dāng)作是
(
).
4)去掉常數(shù)項(xiàng)l(,
)---實(shí)際值和前t-1顆樹在第t輪都是已知的。然后把
代入趟大，得
其中j是葉子鹤树，是葉子j上所有的樣本集合。此時(shí)逊朽，我們可以求解目標(biāo)函數(shù)的最小值罕伯。令上式的導(dǎo)數(shù)為0，我們可以解得
=? -
.代入equ4得
這是目標(biāo)函數(shù)的最小值惋耙。然而捣炬，需要注意的是，它依然是一個(gè)變量绽榛。因?yàn)闃涞慕Y(jié)構(gòu)未知湿酸。那么，能窮舉么灭美？似乎不太現(xiàn)實(shí)推溃。這時(shí)我們使用貪婪算法
5）我們首先將所有樣本置于一個(gè)葉子節(jié)點(diǎn)上，然后再對(duì)這個(gè)葉子節(jié)點(diǎn)進(jìn)行分裂届腐。然后不斷分裂铁坎，樹不斷生長(zhǎng)。然而犁苏，前面我們說(shuō)過(guò)懲罰項(xiàng)不希望模型太過(guò)復(fù)雜硬萍。我們可以先計(jì)算下分裂帶來(lái)的目標(biāo)函數(shù)下降是多少
這個(gè)式子是分裂前的目標(biāo)函數(shù)減去分裂后的目標(biāo)函數(shù)。當(dāng)然围详，我們希望它是正數(shù)
6）上式的值同樣是未知的朴乖。問(wèn)題在于用哪個(gè)特征劃分祖屏？又用哪個(gè)特征值劃分？我們首先能想到的是精確算法买羞。遍歷每一個(gè)特征袁勺，遍歷每一個(gè)特征值，肯定能找出最佳分裂點(diǎn)畜普。這個(gè)計(jì)算量有點(diǎn)大期丰。于是又有近似算法。簡(jiǎn)單說(shuō)這時(shí)我們不再遍歷每一個(gè)特征值吃挑，而只是計(jì)算部分特征值钝荡，從中選取最優(yōu)分裂點(diǎn)（only? among? proposed splits）。如下所示
其中k代表各個(gè)特征儒鹿，,
就是特征k上面的分割點(diǎn)化撕。然后計(jì)算各個(gè)區(qū)間段的
,
.
便是特征k上的特征值。另外约炎，劃分分割點(diǎn)也有兩種不同的方法植阴，主要是根據(jù)劃分的時(shí)間點(diǎn)。global會(huì)在初始階段就把分割點(diǎn)確定好了圾浅，后面怎么分裂都是用這些分割點(diǎn)掠手。而local方法會(huì)在分裂后對(duì)這些分割點(diǎn)進(jìn)行調(diào)整，分割點(diǎn)不是固定的狸捕。通常global需要更多的分割點(diǎn)才能達(dá)到和local同樣的效果喷鸽。下面的圖形可以說(shuō)明精確算法、近似算法（global/local）的差異
eps可以看成是特征分隔區(qū)間的倒數(shù)灸拍。圖中可以看出global方法如果只是把特征分成3個(gè)左右區(qū)間做祝，準(zhǔn)確率是不怎么高的。而local只需要3個(gè)鸡岗，global提升到20個(gè)混槐，就能媲美精確算法了。
7）如何處理缺失值轩性。xgboost對(duì)于缺失值声登，要么劃分到左子樹，要么劃分到右子樹揣苏。具體劃分到哪一邊是從訓(xùn)練數(shù)據(jù)中得到的悯嗓。首先我們把所有的樣本分到右子樹，然后從右子樹不斷把不缺失的樣本分到左子樹卸察，計(jì)算最大的分?jǐn)?shù)增加值脯厨。然后又把所有樣本分到左子樹，同樣操作坑质，計(jì)算最大的分?jǐn)?shù)增加值合武。如果分到右邊分?jǐn)?shù)增加的更多个少，則默認(rèn)方向就是右邊。以后測(cè)試時(shí)有缺失值到達(dá)這個(gè)節(jié)點(diǎn)時(shí)自動(dòng)分到右邊眯杏。原文算法如下
是不含缺失值的集合。注意畫紅線的地方壳澳，先把缺失值劃分到右邊時(shí)岂贩，是按從小到大的順序把非缺失值劃分到左子樹的。而后面是從大到小排序巷波。這樣能加快計(jì)算速度
陳天奇博士論文：https://arxiv.org/pdf/1603.02754v1.pdf? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 陳天奇博士PPT：https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
