XGBoost號稱“比賽奪冠的必備大殺器”，橫掃機器學習競賽罕逢敵手

XGBoost號稱“比賽奪冠的必備大殺器”，橫掃機器學習競賽罕逢敵手，堪稱機器學習算法中的新女王！

在涉及非結(jié)構(gòu)化數(shù)據(jù)（圖像、文本等）的預測問題中，人工神經(jīng)網(wǎng)絡顯著優(yōu)于所有其他算法或框架。但當涉及到中小型結(jié)構(gòu)/表格數(shù)據(jù)時，基于決策樹的算法現(xiàn)在被認為是最佳方法。而基于決策樹算法中最驚艷的，非XGBoost莫屬了。

打過Kaggle、天池、DataCastle、Kesci等國內(nèi)外數(shù)據(jù)競賽平臺之后，一定對XGBoost的威力印象深刻。XGBoost號稱“比賽奪冠的必備大殺器”，橫掃機器學習競賽罕逢敵手。最近甚至有一位大數(shù)據(jù)/機器學習主管被XGBoost在項目中的表現(xiàn)驚艷到，盛贊其為“機器學習算法中的新女王”！

XGBoost最初由陳天奇開發(fā)。陳天奇是華盛頓大學計算機系博士生，研究方向為大規(guī)模機器學習。他曾獲得KDD CUP 2012 Track 1第一名，并開發(fā)了SVDFeature，XGBoost，cxxnet等著名機器學習工具，是Distributed (Deep) Machine Learning Common的發(fā)起人之一。

XGBoost實現(xiàn)了高效、跨平臺、分布式gradient boosting (GBDT, GBRT or GBM) 算法的一個庫，可以下載安裝并應用于C++，Python，R，Julia，Java，Scala，Hadoop等。目前Github上超過15700星、6500個fork。

項目主頁：

https://XGBoost.ai/

XGBoost是什么

XGBoost全稱：eXtreme Gradient Boosting，是一種基于決策樹的集成機器學習算法，使用梯度上升框架，適用于分類和回歸問題。優(yōu)點是速度快、效果好、能處理大規(guī)模數(shù)據(jù)、支持多種語言、支持自定義損失函數(shù)等，不足之處是因為僅僅推出了不足5年時間，需要進一步的實踐檢驗。

XGBoost選用了CART樹，數(shù)學公式表達XGBoost模型如下：

K是樹的數(shù)量，F(xiàn)表示所有可能的CART樹，f表示一棵具體的CART樹。這個模型由K棵CART樹組成。

模型的目標函數(shù)，如下所示：

XGBoost具有以下幾個特點：

靈活性：支持回歸、分類、排名和用戶定義函數(shù)

跨平臺：適用于Windows、Linux、macOS，以及多個云平臺

多語言：支持C++, Python, R, Java, Scala, Julia等

效果好：贏得許多數(shù)據(jù)科學和機器學習挑戰(zhàn)。用于多家公司的生產(chǎn)

云端分布式：支持多臺計算機上的分布式訓練，包括AWS、GCE、Azure和Yarn集群。可以與Flink、Spark和其他云數(shù)據(jù)流系統(tǒng)集成

下圖顯示了基于樹的算法的發(fā)展歷程：

決策樹：由一個決策圖和可能的結(jié)果（包括資源成本和風險）組成， 用來創(chuàng)建到達目標的規(guī)劃。

Bagging：是一種集合元算法，通過多數(shù)投票機制將來自多決策樹的預測結(jié)合起來，也就是將弱分離器 f_i(x) 組合起來形成強分類器 F(x) 的一種方法

隨機森林：基于Bagging算法。隨機選擇一個包含多種特性的子集來構(gòu)建一個森林，或者決策樹的集合

Boosting：通過最小化先前模型的誤差，同時增加高性能模型的影響，順序構(gòu)建模型

梯度上升：對于似然函數(shù)，要求最大值，叫做梯度上升

XGBoost：極端梯度上升，XGBoost是一個優(yōu)化的分布式梯度上升庫，旨在實現(xiàn)高效，靈活和跨平臺

為什么XGBoost能橫掃機器學習競賽平臺？

下圖是XGBoost與其它gradient boosting和bagged decision trees實現(xiàn)的效果比較，可以看出它比R, Python，Spark，H2O的基準配置都快。

XGBoost和Gradient Boosting Machines（GBMs）都是集合樹方法，使用梯度下降架構(gòu)來提升弱學習者（通常是CART）。而XGBoost通過系統(tǒng)優(yōu)化和算法增強改進了基礎GBM框架，在系統(tǒng)優(yōu)化和機器學習原理方面都進行了深入的拓展。

系統(tǒng)優(yōu)化：

并行計算：

由于用于構(gòu)建base learners的循環(huán)的可互換性，XGBoost可以使用并行計算實現(xiàn)來處理順序樹構(gòu)建過程。

外部循環(huán)枚舉樹的葉節(jié)點，第二個內(nèi)部循環(huán)來計算特征，這個對算力要求更高一些。這種循環(huán)嵌套限制了并行化，因為只要內(nèi)部循環(huán)沒有完成，外部循環(huán)就無法啟動。

因此，為了改善運行時，就可以讓兩個循環(huán)在內(nèi)部交換循環(huán)的順序。此開關通過抵消計算中的所有并行化開銷來提高算法性能。

Tree Pruning：

GBM框架內(nèi)樹分裂的停止標準本質(zhì)上是貪婪的，取決于分裂點的負損失標準。XGBoost首先使用'max_depth'參數(shù)而不是標準，然后開始向后修剪樹。這種“深度優(yōu)先”方法顯著的提高了計算性能。

硬件優(yōu)化：

該算法旨在有效利用硬件資源。這是通過在每個線程中分配內(nèi)部緩沖區(qū)來存儲梯度統(tǒng)計信息來實現(xiàn)緩存感知來實現(xiàn)的。諸如“核外”計算等進一步增強功能可優(yōu)化可用磁盤空間，同時處理不適合內(nèi)存的大數(shù)據(jù)幀。

算法增強：

正則化：

它通過LASSO（L1）和Ridge（L2）正則化來懲罰更復雜的模型，以防止過擬合。

稀疏意識：

XGBoost根據(jù)訓練損失自動“學習”最佳缺失值并更有效地處理數(shù)據(jù)中不同類型的稀疏模式。

加權(quán)分位數(shù)草圖：

XGBoost采用分布式加權(quán)分位數(shù)草圖算法，有效地找到加權(quán)數(shù)據(jù)集中的最優(yōu)分裂點。

交叉驗證：

該算法每次迭代時都帶有內(nèi)置的交叉驗證方法，無需顯式編程此搜索，并可以指定單次運行所需的增強迭代的確切數(shù)量。

為了測試XGBoost到底有多快，可以通過Scikit-learn的'Make_Classification'數(shù)據(jù)包，創(chuàng)建一個包含20個特征（2個信息和2個冗余）的100萬個數(shù)據(jù)點的隨機樣本。

下圖為邏輯回歸，隨機森林，標準梯度提升和XGBoost效率對比：