介紹

Xgboost是GB算法的高效實現(xiàn)，xgboost中的基學(xué)習(xí)器除了可以是CART（gbtree）也可以是線性分類器（gblinear）。

與GBDT不同之處

xgboost在目標(biāo)函數(shù)中顯示的加上了正則化項，基學(xué)習(xí)為CART時，正則化項與樹的葉子節(jié)點(diǎn)的數(shù)量T和葉子節(jié)點(diǎn)的值有關(guān)。

GB中使用Loss Function對f（x）的一階導(dǎo)數(shù)計算出偽殘差用于學(xué)習(xí)生成fm（x），xgboost不僅使用到了一階導(dǎo)數(shù)，還使用二階導(dǎo)數(shù)。GB中使用Loss Function對f（x）的一階導(dǎo)數(shù)計算出偽殘差用于學(xué)習(xí)生成fm（x），xgboost不僅使用到了一階導(dǎo)數(shù)，還使用二階導(dǎo)數(shù)

上面提到CART回歸樹中尋找最佳分割點(diǎn)的衡量標(biāo)準(zhǔn)是最小化均方差，xgboost尋找分割點(diǎn)的標(biāo)準(zhǔn)是最大化，lamda，gama與正則化項相關(guān) 上面提到CART回歸樹中尋找最佳分割點(diǎn)的衡量標(biāo)準(zhǔn)是最小化均方差，xgboost尋找分割點(diǎn)的標(biāo)準(zhǔn)是最大化，lamda，gama與正則化項相關(guān)

支持并行化，這是XGBoost的閃光點(diǎn)，雖然樹與樹之間是串行關(guān)系，但是同層級節(jié)點(diǎn)可并行。具體的對于某個節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)選擇最佳分裂點(diǎn)，候選分裂點(diǎn)計算增益用多線程并行。訓(xùn)練速度快。

xgboost算法的步驟和GB基本相同，都是首先初始化為一個常數(shù)，gb是根據(jù)一階導(dǎo)數(shù)ri，xgboost是根據(jù)一階導(dǎo)數(shù)gi和二階導(dǎo)數(shù)hi，迭代生成基學(xué)習(xí)器，相加更新學(xué)習(xí)器。

優(yōu)化內(nèi)容

xgboost與gdbt除了上述三點(diǎn)的不同，xgboost在實現(xiàn)時還做了許多優(yōu)化：

在尋找最佳分割點(diǎn)時，考慮傳統(tǒng)的枚舉每個特征的所有可能分割點(diǎn)的貪心法效率太低，xgboost實現(xiàn)了一種近似的算法。大致的思想是根據(jù)百分位法列舉幾個可能成為分割點(diǎn)的候選者，然后從候選者中根據(jù)上面求分割點(diǎn)的公式計算找出最佳的分割點(diǎn)。

xgboost考慮了訓(xùn)練數(shù)據(jù)為稀疏值的情況，可以為缺失值或者指定的值指定分支的默認(rèn)方向，這能大大提升算法的效率，paper提到50倍。

特征列排序后以塊的形式存儲在內(nèi)存中，在迭代中可以重復(fù)使用；雖然boosting算法迭代必須串行，但是在處理每個特征列時可以做到并行。

按照特征列方式存儲能優(yōu)化尋找最佳的分割點(diǎn)，但是當(dāng)以行計算梯度數(shù)據(jù)時會導(dǎo)致內(nèi)存的不連續(xù)訪問，嚴(yán)重時會導(dǎo)致cache miss，降低算法效率。paper中提到，可先將數(shù)據(jù)收集到線程內(nèi)部的buffer，然后再計算，提高算法的效率。

xgboost 還考慮了當(dāng)數(shù)據(jù)量比較大，內(nèi)存不夠時怎么有效的使用磁盤，主要是結(jié)合多線程、數(shù)據(jù)壓縮、分片的方法，盡可能的提高算法的效率。