XGBoost是陳天奇在博士期間研究成果，近年來也是數據挖掘比賽的一大神器，幾乎任何比賽都會使用。
Xgboost是GBDT算法的高效實現，xgboost中的基學習器除了可以是CART（gbtree）也可以是線性分類器（gblinear）。下面所有的內容來自原始paper，包括公式。
(1). xgboost在目標函數中顯示的加上了正則化項，基學習器為CART時，正則化項與樹的葉子節點的數量T和葉子節點的權值有關。
(2). GBDT中使用Loss Function對f(x)的一階導數計算出偽殘差用於學習生成fm(x)，xgboost不僅使用到了一階導數，還使用二階導數。
第t次的loss：
對上式做二階泰勒展開：g為一階導數，h為二階導數
(3). 上面提到CART迴歸樹中尋找最佳分割點的衡量標準是最小化均方差，xgboost尋找分割點的標準是最大化，lamda，gama與正則化項相關
xgboost與gdbt除了上述三點的不同，xgboost在實現時還做了許多優化：
- 在尋找最佳分割點時，考慮傳統的枚舉每個特徵的所有可能分割點的貪心法效率太低，xgboost實現了一種近似的算法。大致的思想是根據百分位法列舉幾個可能成為分割點的候選者，然後從候選者中根據上面求分割點的公式計算找出最佳的分割點。
- xgboost考慮了訓練數據為稀疏值的情況，可以為缺失值或者指定的值指定分支的默認方向，這能大大提升算法的效率，paper提到50倍。
- 特徵列排序後以塊的形式存儲在內存中，在迭代中可以重複使用；雖然boosting算法迭代必須串行，但是在處理每個特徵列時可以做到並行。
- 按照特徵列方式存儲能優化尋找最佳的分割點，但是當以行計算梯度數據時會導致內存的不連續訪問，嚴重時會導致cache miss，降低算法效率。paper中提到，可先將數據收集到線程內部的buffer，然後再計算，提高算法的效率。
- xgboost 還考慮了當數據量比較大，內存不夠時怎麼有效的使用磁盤，主要是結合多線程、數據壓縮、分片的方法，儘可能的提高算法的效率。
分享到:
閱讀更多 機器學習與數據挖掘 的文章
