GBDT
Gradient Boosting Decision Tree
GBDT是一種迭代的決策樹算法，由多課決策樹組成朽基，分類的話是每棵樹的結(jié)果投票決定布隔，回歸的話是每棵樹的結(jié)果相加得到。
GBDT中的決策樹指的是CART的回歸樹稼虎⌒铺矗回歸樹總體流程類似于分類樹，區(qū)別在于霎俩，回歸樹的每一個節(jié)點(diǎn)都會得一個預(yù)測值哀军，以年齡為例，該預(yù)測值等于屬于這個節(jié)點(diǎn)的所有人年齡的平均值打却。分枝時窮舉每一個feature的每個閾值找最好的分割點(diǎn)杉适，但衡量最好的標(biāo)準(zhǔn)不再是最大熵，而是最小化平方誤差柳击。因?yàn)榉诸惖慕Y(jié)果不好疊加猿推，所以才用回歸樹。
為了防止過擬合，剪枝操作蹬叭。有預(yù)剪枝和
C4.5分類樹在每次分枝時藕咏，是窮舉每一個feature的每一個閾值，找到使得按照feature<=閾值秽五，和feature>閾值分成的兩個分枝的熵最大的feature和閾值（熵最大的概念可理解成盡可能每個分枝的男女比例都遠(yuǎn)離1:1）孽查，按照該標(biāo)準(zhǔn)分枝得到兩個新節(jié)點(diǎn)，用同樣方法繼續(xù)分枝直到所有人都被分入性別唯一的葉子節(jié)點(diǎn)坦喘，或達(dá)到預(yù)設(shè)的終止條件卦碾，若最終葉子節(jié)點(diǎn)中的性別不唯一，則以多數(shù)人的性別作為該葉子節(jié)點(diǎn)的性別起宽。
梯度提升指的是每棵樹都是在上一棵樹的殘差上來繼續(xù)訓(xùn)練的洲胖。所以才說，回歸的最后結(jié)果是所有樹結(jié)果的加和坯沪。
損失函數(shù)MSE绿映，梯度迭代求到后正好是2倍的殘差。
xgBoost
rf：https://xgboost.readthedocs.io/en/latest/model.html
http://www.reibang.com/p/7467e616f227
GBM（Boosted trees）指通過不斷地?cái)M合去擬合出函數(shù)來腐晾。每次迭代都增加一棵樹（一個new function）叉弦。
xgBoost本質(zhì)也是一堆cart樹，對于分類問題藻糖，由于CART樹的葉子節(jié)點(diǎn)對應(yīng)的值是一個實(shí)際的分?jǐn)?shù)淹冰，而非一個確定的類別，這將有利于實(shí)現(xiàn)高效的優(yōu)化算法巨柒。xgboost出名的原因一是準(zhǔn)樱拴，二是快，之所以快洋满，其中就有選用CART樹的一份功勞晶乔。
第t棵樹的優(yōu)化目標(biāo)函數(shù)是均方差損失函數(shù)+正則。當(dāng)MSE作為損失函數(shù)時牺勾，目標(biāo)函數(shù)包含殘差和新一棵樹預(yù)測結(jié)果的平方正罢。
二次展開的好處：
- gbdt只用到了一階信息，如果按照上文中推導(dǎo)驻民，相當(dāng)于loss只進(jìn)行了一階泰勒展開翻具。在沒有復(fù)雜度項(xiàng)的情況下，無法確定步長回还，所以只能用常數(shù)步長根據(jù)一階梯度方向去逼近裆泳。這就是牛頓下降法和梯度下降法的區(qū)別。由于二階展開用二次函數(shù)去逼近函數(shù)懦趋，所以可以利用二階信息確定更新步長晾虑，比只利用一階信息的gdbt用更少的迭代獲得更好的效果。cf.牛頓梯度法的二階收斂性。
- 每個樣本的gi, hi相關(guān)帜篇，可并行計(jì)算糙捺。
- gi和hi是不依賴于損失函數(shù)的形式的，只要這個損失函數(shù)二次可微就可以了笙隙。好處就是xgboost可以支持自定義損失函數(shù)洪灯，只需滿足二次可微即可。
尋找最佳樹結(jié)構(gòu)：
對于第t棵樹的優(yōu)化目標(biāo)函數(shù)竟痰，我們繼續(xù)推導(dǎo)：
Ij代表一個集合签钩，集合中每個值代表一個訓(xùn)練樣本的序號，整個集合就是被第t棵CART樹分到了第j個葉子節(jié)點(diǎn)上的訓(xùn)練樣本坏快。
由此推導(dǎo)出最佳值：
split點(diǎn)的評判標(biāo)準(zhǔn)：
這個Gain實(shí)際上就是單節(jié)點(diǎn)的obj減去切分后的兩個節(jié)點(diǎn)的樹obj铅檩，Gain如果是正的，并且值越大莽鸿，表示切分后obj越小于單節(jié)點(diǎn)的obj昧旨，就越值得切分。同時祥得，我們還可以觀察到兔沃，Gain的左半部分如果小于右側(cè)的γ，則Gain就是負(fù)的级及，表明切分后obj反而變大了乒疏。γ在這里實(shí)際上是一個臨界值，它的值越大饮焦，表示我們對切分后obj下降幅度要求越嚴(yán)怕吴。這個值也是可以在xgboost中設(shè)定的。
注意：xgboost的切分操作和普通的決策樹切分過程是不一樣的追驴。普通的決策樹在切分的時候并不考慮樹的復(fù)雜度械哟，而依賴后續(xù)的剪枝操作來控制。xgboost在切分的時候就已經(jīng)考慮了樹的復(fù)雜度殿雪，就是那個γ參數(shù)。所以锋爪，它不需要進(jìn)行單獨(dú)的剪枝操作丙曙。
LightGBM
分布式 GBDT。速度快其骄！
它拋棄了大多數(shù) GBDT 工具使用的按層生長
(level-wise) 的決策樹生長策略亏镰，而使用了帶有深度限制的按葉子生長 (leaf-wise) 算法。leaf-wise則是一種更為高效的策略拯爽，每次從當(dāng)前所有葉子中索抓，找到分裂增益最大(一般也是數(shù)據(jù)量最大)的一個葉子，然后分裂，如此循環(huán)逼肯。因此同 level-wise 相比耸黑，在分裂次數(shù)相同的情況下，leaf-wise 可以降低更多的誤差篮幢，得到更好的精度大刊。leaf-wise 的缺點(diǎn)是可能會長出比較深的決策樹，產(chǎn)生過擬合三椿。因此 LightGBM 在leaf-wise 之上增加了一個最大深度的限制缺菌，在保證高效率的同時防止過擬合。
- 缺失值（missing value）的自動處理
- 類別特征(Categorical Feature) 的進(jìn)一步優(yōu)化搜锰，不再使用類似one-hot coding的分割方式伴郁。對于類別數(shù)量很多的類別特征，使用one-vs-other的切分方式會長出很不平衡的樹蛋叼，不能實(shí)現(xiàn)較好的精度蛾绎。這是樹模型在支持類別特征的一個痛點(diǎn)。 LightGBM可以找出類別特征的最優(yōu)切割鸦列，即many-vs-many的切分方式租冠。并且最優(yōu)分割的查找的時間復(fù)雜度可以在線性時間完成，和原來的one-vs-other的復(fù)雜度幾乎一致薯嗤。
