GBDT
Gradient Boosting Decision Tree
GBDT是一種迭代的決策樹算法，由多課決策樹組成，分類的話是每棵樹的結(jié)果投票決定，回歸的話是每棵樹的結(jié)果相加得到。
GBDT中的決策樹指的是CART的回歸樹?；貧w樹總體流程類似于分類樹，區(qū)別在于，回歸樹的每一個(gè)節(jié)點(diǎn)都會(huì)得一個(gè)預(yù)測值，以年齡為例，該預(yù)測值等于屬于這個(gè)節(jié)點(diǎn)的所有人年齡的平均值。分枝時(shí)窮舉每一個(gè)feature的每個(gè)閾值找最好的分割點(diǎn)，但衡量最好的標(biāo)準(zhǔn)不再是最大熵，而是最小化平方誤差。因?yàn)榉诸惖慕Y(jié)果不好疊加，所以才用回歸樹。
為了防止過擬合，剪枝操作。有預(yù)剪枝和
C4.5分類樹在每次分枝時(shí)，是窮舉每一個(gè)feature的每一個(gè)閾值，找到使得按照feature<=閾值，和feature>閾值分成的兩個(gè)分枝的熵最大的feature和閾值（熵最大的概念可理解成盡可能每個(gè)分枝的男女比例都遠(yuǎn)離1:1），按照該標(biāo)準(zhǔn)分枝得到兩個(gè)新節(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.itdecent.cn/p/7467e616f227
GBM（Boosted trees）指通過不斷地?cái)M合去擬合出函數(shù)來。每次迭代都增加一棵樹（一個(gè)new function）。
xgBoost本質(zhì)也是一堆cart樹，對于分類問題，由于CART樹的葉子節(jié)點(diǎn)對應(yīng)的值是一個(gè)實(shí)際的分?jǐn)?shù)，而非一個(gè)確定的類別，這將有利于實(shí)現(xiàn)高效的優(yōu)化算法。xgboost出名的原因一是準(zhǔn)，二是快，之所以快，其中就有選用CART樹的一份功勞。
第t棵樹的優(yōu)化目標(biāo)函數(shù)是均方差損失函數(shù)+正則。當(dāng)MSE作為損失函數(shù)時(shí)，目標(biāo)函數(shù)包含殘差和新一棵樹預(yù)測結(jié)果的平方。
二次展開的好處：
- gbdt只用到了一階信息，如果按照上文中推導(dǎo)，相當(dāng)于loss只進(jìn)行了一階泰勒展開。在沒有復(fù)雜度項(xiàng)的情況下，無法確定步長，所以只能用常數(shù)步長根據(jù)一階梯度方向去逼近。這就是牛頓下降法和梯度下降法的區(qū)別。由于二階展開用二次函數(shù)去逼近函數(shù)，所以可以利用二階信息確定更新步長，比只利用一階信息的gdbt用更少的迭代獲得更好的效果。cf.牛頓梯度法的二階收斂性。
- 每個(gè)樣本的gi, hi相關(guān)，可并行計(jì)算。
- gi和hi是不依賴于損失函數(shù)的形式的，只要這個(gè)損失函數(shù)二次可微就可以了。好處就是xgboost可以支持自定義損失函數(shù)，只需滿足二次可微即可。
尋找最佳樹結(jié)構(gòu)：
對于第t棵樹的優(yōu)化目標(biāo)函數(shù)，我們繼續(xù)推導(dǎo)：
Ij代表一個(gè)集合，集合中每個(gè)值代表一個(gè)訓(xùn)練樣本的序號，整個(gè)集合就是被第t棵CART樹分到了第j個(gè)葉子節(jié)點(diǎn)上的訓(xùn)練樣本。
由此推導(dǎo)出最佳值：
split點(diǎn)的評判標(biāo)準(zhǔn)：
這個(gè)Gain實(shí)際上就是單節(jié)點(diǎn)的obj減去切分后的兩個(gè)節(jié)點(diǎn)的樹obj，Gain如果是正的，并且值越大，表示切分后obj越小于單節(jié)點(diǎn)的obj，就越值得切分。同時(shí)，我們還可以觀察到，Gain的左半部分如果小于右側(cè)的γ，則Gain就是負(fù)的，表明切分后obj反而變大了。γ在這里實(shí)際上是一個(gè)臨界值，它的值越大，表示我們對切分后obj下降幅度要求越嚴(yán)。這個(gè)值也是可以在xgboost中設(shè)定的。
注意：xgboost的切分操作和普通的決策樹切分過程是不一樣的。普通的決策樹在切分的時(shí)候并不考慮樹的復(fù)雜度，而依賴后續(xù)的剪枝操作來控制。xgboost在切分的時(shí)候就已經(jīng)考慮了樹的復(fù)雜度，就是那個(gè)γ參數(shù)。所以，它不需要進(jìn)行單獨(dú)的剪枝操作。
LightGBM
分布式 GBDT。速度快！
它拋棄了大多數(shù) GBDT 工具使用的按層生長
(level-wise) 的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise) 算法。leaf-wise則是一種更為高效的策略，每次從當(dāng)前所有葉子中，找到分裂增益最大(一般也是數(shù)據(jù)量最大)的一個(gè)葉子，然后分裂，如此循環(huán)。因此同 level-wise 相比，在分裂次數(shù)相同的情況下，leaf-wise 可以降低更多的誤差，得到更好的精度。leaf-wise 的缺點(diǎn)是可能會(huì)長出比較深的決策樹，產(chǎn)生過擬合。因此 LightGBM 在leaf-wise 之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過擬合。
- 缺失值（missing value）的自動(dòng)處理
- 類別特征(Categorical Feature) 的進(jìn)一步優(yōu)化，不再使用類似one-hot coding的分割方式。對于類別數(shù)量很多的類別特征，使用one-vs-other的切分方式會(huì)長出很不平衡的樹，不能實(shí)現(xiàn)較好的精度。這是樹模型在支持類別特征的一個(gè)痛點(diǎn)。 LightGBM可以找出類別特征的最優(yōu)切割，即many-vs-many的切分方式。并且最優(yōu)分割的查找的時(shí)間復(fù)雜度可以在線性時(shí)間完成，和原來的one-vs-other的復(fù)雜度幾乎一致。
