介紹

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

與GBDT不同之處

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

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

上面提到CART回歸樹中尋找最佳分割點的衡量標準是最小化均方差，xgboost尋找分割點的標準是最大化，lamda，gama與正則化項相關 上面提到CART回歸樹中尋找最佳分割點的衡量標準是最小化均方差，xgboost尋找分割點的標準是最大化，lamda，gama與正則化項相關

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

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

優(yōu)化內容

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

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

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

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

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

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