集成学习-Boosting集成学习算法XGBoost
?
? ? ? XGBoost全名叫（eXtreme Gradient Boosting）極端梯度提升，經(jīng)常被用在一些項(xiàng)目中，其效果顯著。它是大規(guī)模并行boosted tree的工具，它是目前最快最好的開源boosted tree工具包。XGBoost 所應(yīng)用的算法就是GBDT（gradient boosting decision tree）的改進(jìn)，既可以用于分類也可以用于回歸問題中。
- 全稱：eXtreme Gradient Boosting（極值梯度提升算法）
- 作者：陳天奇(華盛頓大學(xué)博士)?
- 基礎(chǔ)：GBDT?
- 所屬：boosting迭代型、樹類算法。?
- 適用范圍：分類、回歸等
- 優(yōu)點(diǎn)：速度快、效果好、能處理大規(guī)模數(shù)據(jù)、支持多種語言、支持自定義損失函數(shù)等等。
目錄
XGBoost和GBDT的區(qū)別
加法模型與前向分步算法
XGBoost目標(biāo)損失函數(shù)推導(dǎo)
帶正則項(xiàng)的Boosting Tree模型
XGBoost損失函數(shù)推導(dǎo)
最優(yōu)切分點(diǎn)劃分算法
XGBoost的優(yōu)缺點(diǎn)
XGBoosting涉及的算法工程優(yōu)化策略
Xgboost算法訓(xùn)練參數(shù)
XGBoost和GBDT的區(qū)別
XGBoost作為GBDT的高效實(shí)現(xiàn)，對比原算法GBDT，XGBoost主要從下面幾個(gè)方面做了優(yōu)化：
- XGBoost的基學(xué)習(xí)器除了可以是CART也可以是線性分類器，而GBDT只能是CART；
- XGBoost在代價(jià)函數(shù)中加入了正則項(xiàng)，用于控制模型的復(fù)雜度(正則項(xiàng)的方式不同，GBDT是一種類似于縮減系數(shù)，而XGBoost類似于L2正則化項(xiàng))，可以防止過擬合，泛化能力更強(qiáng)。
- XGBoost借鑒了隨機(jī)森林的做法，支持特征抽樣，不僅防止過擬合，還能減少計(jì)算；
- XGBoost工具支持并行化；
- 對于缺失值的特征，通過枚舉所有缺失值在當(dāng)前節(jié)點(diǎn)是進(jìn)入左子樹還是右子樹來決定缺失值的處理方式。
- 在算法的優(yōu)化方式上，GBDT的損失函數(shù)只對誤差部分做負(fù)梯度（一階泰勒）展開，而XGBoost損失函數(shù)對誤差部分做二階泰勒展開，更加準(zhǔn)確。
XGBoost與深度學(xué)習(xí)對比，不同的機(jī)器學(xué)習(xí)模型適用于不同類型的任務(wù)。深度神經(jīng)網(wǎng)絡(luò)通過對時(shí)空位置建模，能夠很好地捕獲圖像、語音、文本等高維數(shù)據(jù)。而基于樹模型的XGBoost則能很好地處理表格數(shù)據(jù)，同時(shí)還擁有一些深度神經(jīng)網(wǎng)絡(luò)所沒有的特性（如：模型的可解釋性、輸入數(shù)據(jù)的不變性、更易于調(diào)參等）。?
?
加法模型與前向分步算法
GBDT和XGBoost的算法核心都是：先構(gòu)造一個(gè)（決策）樹，然后不斷在已有模型和實(shí)際樣本輸出的殘差上再構(gòu)造一顆樹，依次迭代。算法都使用了前向分布算法的思路，從前向后，每一步學(xué)習(xí)一個(gè)基函數(shù)及其系數(shù)，最終逐步逼近優(yōu)化目標(biāo)函數(shù)式。
前向分布算法的前提，還需要介紹一下加法模型：
如果給定了損失函數(shù)L，所以前向分布算法考慮的問題是，如何求出所有的βm和γm，那我們的優(yōu)化目標(biāo)即為：
顯然一次性求出所有的βm和γm基本不可能，所以前向分布算法給出的解決辦法是：“利用貪心算法，每一步只學(xué)習(xí)一個(gè)弱模型及其系數(shù)，使得當(dāng)前弱模型和之前所有的弱模型組合后目標(biāo)表達(dá)式取得最優(yōu)值，最終就可以使得所有弱模型組合后目標(biāo)表達(dá)式取得最優(yōu)值”。
下面通過一個(gè)具體的例子來說明：預(yù)測一個(gè)人是否喜歡電腦游戲，下圖表明小男孩更喜歡打游戲，預(yù)測的結(jié)果為 tree1 和 tree 2 累加的結(jié)果2.9。
總之，提升方法告訴我們?nèi)绾蝸砬笠粋€(gè)效果更好模型，那就是將多個(gè)弱模型組合起來，這僅僅是一個(gè)思路，而前向分布算法就具體告訴我們應(yīng)該如何來做。
?
XGBoost目標(biāo)損失函數(shù)推導(dǎo)
帶正則項(xiàng)的Boosting Tree模型
其中，γγ為L1L1正則的懲罰項(xiàng)，λλ為L2L2正則的懲罰項(xiàng)
復(fù)雜度計(jì)算例子如下：
XGBoost損失函數(shù)推導(dǎo)
最優(yōu)切分點(diǎn)劃分算法
在實(shí)際訓(xùn)練過程中，當(dāng)建立第 t 棵樹時(shí)，一個(gè)非常關(guān)鍵的問題是如何找到葉子節(jié)點(diǎn)的最優(yōu)切分點(diǎn)，XGBoost支持兩種分裂節(jié)點(diǎn)的方法——貪心算法和近似算法。
（1）貪心算法
從樹的深度為0開始：
那么如何計(jì)算每個(gè)特征的分裂收益呢？
假設(shè)我們在某一節(jié)點(diǎn)完成特征分裂，則分裂前的目標(biāo)函數(shù)可以寫為：
分裂后的目標(biāo)函數(shù)為：
則對于目標(biāo)函數(shù)來說，分裂后的收益為：
注意：?該特征收益也可作為特征重要性輸出的重要依據(jù)。
對于每次分裂，我們都需要枚舉所有特征可能的分割方案，如何高效地枚舉所有的分割呢？
假設(shè)我們要枚舉某個(gè)特征所有 x<a?這樣條件的樣本，對于某個(gè)特定的分割點(diǎn)?a 我們要計(jì)算 a 左邊和右邊的導(dǎo)數(shù)和。
我們可以發(fā)現(xiàn)對于所有的分裂點(diǎn) a? ，只要做一遍從左到右的掃描就可以枚舉出所有分割的梯度和GL、GR?。然后用上面的公式計(jì)算每個(gè)分割方案的收益就可以了。
觀察分裂后的收益，我們會發(fā)現(xiàn)節(jié)點(diǎn)劃分不一定會使得結(jié)果變好，因?yàn)槲覀冇幸粋€(gè)引入新葉子的懲罰項(xiàng)，也就是說引入的分割帶來的增益如果小于一個(gè)閥值的時(shí)候，我們可以剪掉這個(gè)分割。
（2）近似算法
貪心算法可以得到最優(yōu)解，但當(dāng)數(shù)據(jù)量太大時(shí)則無法讀入內(nèi)存進(jìn)行計(jì)算，近似算法主要針對貪心算法這一缺點(diǎn)給出了近似最優(yōu)解。
對于每個(gè)特征，只考察分位點(diǎn)可以減少計(jì)算復(fù)雜度。
該算法首先根據(jù)特征分布的分位數(shù)提出候選劃分點(diǎn)，然后將連續(xù)型特征映射到由這些候選點(diǎn)劃分的桶中，然后聚合統(tǒng)計(jì)信息找到所有區(qū)間的最佳分裂點(diǎn)。
在提出候選切分點(diǎn)時(shí)有兩種策略：
-
Global：學(xué)習(xí)每棵樹前就提出候選切分點(diǎn)，并在每次分裂時(shí)都采用這種分割；
-
Local：每次分裂前將重新提出候選切分點(diǎn)。直觀上來看，Local策略需要更多的計(jì)算步驟，而Global策略因?yàn)楣?jié)點(diǎn)已有劃分所以需要更多的候選點(diǎn)。
下圖給出不同種分裂策略的AUC變化曲線，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為測試集AUC，eps為近似算法的精度，其倒數(shù)為桶的數(shù)量。
我們可以看到 Global 策略在候選點(diǎn)數(shù)多時(shí)（eps 小）可以和 Local 策略在候選點(diǎn)少時(shí)（eps 大）具有相似的精度。此外我們還發(fā)現(xiàn)，在 eps 取值合理的情況下，分位數(shù)策略可以獲得與貪婪算法相同的精度。
XGBoost的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
（1）并行處理，支持并行化。boosting技術(shù)中下一棵樹依賴上一棵樹的殘差進(jìn)行訓(xùn)練和預(yù)測，所以樹與樹之間應(yīng)該是只能串行。但是同層級節(jié)點(diǎn)可并行，具體的對于某個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)選擇最佳分裂點(diǎn)，進(jìn)行枚舉的時(shí)候并行，（據(jù)說恰好這個(gè)也是樹形成最耗時(shí)的階段）。候選分裂點(diǎn)計(jì)算增益用多線程并行，訓(xùn)練速度快。
（2）高度的靈活性。XGBoost 允許用戶定義自定義優(yōu)化目標(biāo)函數(shù)和評價(jià)標(biāo)準(zhǔn)。
（3）缺失值處理。XGBoost內(nèi)置處理缺失值的規(guī)則。用戶需要提供一個(gè)和其它樣本不同的值，然后把它作為一個(gè)參數(shù)傳進(jìn)去，以此來作為缺失值的取值。XGBoost在不同節(jié)點(diǎn)遇到缺失值時(shí)采用不同的處理方法，并且會學(xué)習(xí)未來遇到缺失值時(shí)的處理方法。
（4）內(nèi)置交叉驗(yàn)證。XGBoost允許在每一輪boosting迭代中使用交叉驗(yàn)證。因此，可以方便地獲得最優(yōu)boosting迭代次數(shù)。而GBM使用網(wǎng)格搜索，只能檢測有限個(gè)值。early?stop，當(dāng)預(yù)測結(jié)果已經(jīng)很好的時(shí)候可以提前停止建樹，加快訓(xùn)練速度。
（5）XGBoost還特別設(shè)計(jì)了針對稀疏數(shù)據(jù)的算法?
假設(shè)樣本的第i個(gè)特征缺失時(shí)，無法利用該特征對樣本進(jìn)行劃分，這里的做法是將該樣本默認(rèn)地分到指定的子節(jié)點(diǎn)，至于具體地分到哪個(gè)節(jié)點(diǎn)還需要某算法來計(jì)算，算法的主要思想是，分別假設(shè)特征缺失的樣本屬于右子樹和左子樹，而且只在不缺失的樣本上迭代，分別計(jì)算缺失樣本屬于右子樹和左子樹的增益，選擇增益最大的方向?yàn)槿笔?shù)據(jù)的默認(rèn)方向（論文中“枚舉”指的不是枚舉每個(gè)缺失樣本在左邊還是在右邊，而是枚舉缺失樣本整體在左邊，還是在右邊兩種情況。 分裂點(diǎn)還是只評估特征不缺失的樣本。）；
（6）XGBoost還提出了三種防止過擬合的方法：Shrinkage and Column Subsampling、正則化項(xiàng)
Shrinkage方法就是在每次迭代中對樹的每個(gè)葉子結(jié)點(diǎn)的分?jǐn)?shù)乘上一個(gè)縮減權(quán)重η，這可以使得每一棵樹的影響力不會太大，留下更大的空間給后面生成的樹去優(yōu)化模型。Column Subsampling類似于隨機(jī)森林中的選取部分特征進(jìn)行建樹。其可分為兩種，一種是按層隨機(jī)采樣，在對同一層內(nèi)每個(gè)結(jié)點(diǎn)分裂之前，先隨機(jī)選擇一部分特征，然后只需要遍歷這部分的特征，來確定最優(yōu)的分割點(diǎn)。另一種是隨機(jī)選擇特征，則建樹前隨機(jī)選擇一部分特征然后分裂就只遍歷這些特征。一般情況下前者效果更好。
缺點(diǎn)
（1）雖然利用預(yù)排序和近似算法可以降低尋找最佳分裂點(diǎn)的計(jì)算量，但是xgBoosting采用預(yù)排序，在迭代之前，對結(jié)點(diǎn)的特征做預(yù)排序，需要遍歷數(shù)據(jù)集選擇最優(yōu)分割點(diǎn)，數(shù)據(jù)量大，非常耗時(shí)；LightGBM方法采用histogram算法，占用的內(nèi)存低，數(shù)據(jù)分割的復(fù)雜度更低；
（2）預(yù)排序過程的空間復(fù)雜度過高，不僅需要存儲特征值，還需要存儲特征對應(yīng)樣本的梯度統(tǒng)計(jì)值的索引，相當(dāng)于消耗了兩倍的內(nèi)存。
（3）xgBoosting采用level-wise生成決策樹，同時(shí)分裂同一層的葉子，從而進(jìn)行多線程優(yōu)化，不容易過擬合，但很多葉子節(jié)點(diǎn)的分裂增益較低，沒必要進(jìn)行跟進(jìn)一步的分裂，這就帶來了不必要的開銷；LightGBM采用深度優(yōu)化，leaf-wise生長策略，每次從當(dāng)前葉子中選擇增益最大的結(jié)點(diǎn)進(jìn)行分裂，循環(huán)迭代，但會生長出更深的決策樹，產(chǎn)生過擬合，因此引入了一個(gè)閾值進(jìn)行限制，防止過擬合。
XGBoosting涉及的算法工程優(yōu)化策略
（1） 對內(nèi)存的優(yōu)化（列分塊）
在XGBoost模型計(jì)算過程中，特征值的排序與切分點(diǎn)的選擇是最耗時(shí)的部分，文章中提出了一種劃分塊的優(yōu)化方法，具體表現(xiàn)為如下流程：
- 整體訓(xùn)練數(shù)據(jù)可以看做一個(gè)n*m 的超大規(guī)模稀疏矩陣
- 按照mini-batch的方式橫向分割，可以切成很多個(gè)“Block”
- 每一個(gè)“Block”內(nèi)部采用一種Compress Sparse Column的稀疏短陣格式，每一列特征分別做好升序排列，便于搜索切分點(diǎn)，整體的時(shí)間復(fù)雜度有效降低。
（2）對CPU Cache的優(yōu)化
針對一個(gè)具體的塊(block)，其中存儲了排序好的特征值，以及指向特征值所屬樣本的索引指針，算法需要間接地利用索引指針來獲得樣本的梯度值。由于塊中數(shù)據(jù)是按特征值來排序的，當(dāng)索引指針指向內(nèi)存中不連續(xù)的樣本時(shí)，無法充分利用CPU緩存來提速。文章中作者提出來了兩種優(yōu)化思路。
- 提前取數(shù)（Prefetching）
對于精確搜索，利用多線程的方式，給每個(gè)線程劃分一個(gè)連續(xù)的緩存空間，當(dāng)training線程在按特征值的順序計(jì)算梯度的累加時(shí)，prefetching線程可以提前將接下來的一批特征值對應(yīng)的梯度加載到CPU緩存中。
- 合理設(shè)置分塊大小
對于近似分桶搜索，按行分塊時(shí)需要準(zhǔn)確地選擇塊的大小。塊太小會導(dǎo)致每個(gè)線程的工作量太少，切換線程的成本過高，不利于并行計(jì)算；塊太大導(dǎo)致緩存命中率低，需要花費(fèi)更多時(shí)間在讀取數(shù)據(jù)上。經(jīng)過反復(fù)實(shí)驗(yàn)，作者找到一個(gè)合理的block_size?。
（3）對IO的優(yōu)化
當(dāng)數(shù)據(jù)集太大，無法全部加載到內(nèi)存時(shí)，主要的性能瓶頸就變成了磁盤IO，因此需要對IO進(jìn)行優(yōu)化。文章中主要提出來了兩種優(yōu)化思路。
- Block壓縮優(yōu)化
原始數(shù)據(jù)在磁盤上是以壓縮格式存取的，讀取的時(shí)候，現(xiàn)場解壓 (decompress on-the-fly)
相當(dāng)于犧牲一部分CPU時(shí)間，換取對磁盤IO的讀取時(shí)間損耗。
- Block 分片優(yōu)化
將壓縮后的塊存放在多個(gè)不同的磁盤中，每個(gè)磁盤開一個(gè)prefetching線程分別讀取數(shù)據(jù)到各自的緩存，提供給一個(gè)training線程使用。
?
Xgboost算法訓(xùn)練參數(shù)
XGBoost可以把所有的參數(shù)分成了三類：
- 通用參數(shù)：宏觀函數(shù)控制。
- Booster參數(shù)：控制每一步的booster(tree/regression)。
- 學(xué)習(xí)目標(biāo)參數(shù)：控制訓(xùn)練目標(biāo)的表現(xiàn)。
（1）通用參數(shù)
這些參數(shù)用來控制XGBoost的宏觀功能。
booster[默認(rèn)gbtree]
- 選擇每次迭代的模型，有兩種選擇：?
gbtree：基于樹的模型?
gbliner：線性模型
silent[默認(rèn)0]
- 當(dāng)這個(gè)參數(shù)值為1時(shí)，靜默模式開啟，不會輸出任何信息。
- 一般這個(gè)參數(shù)就保持默認(rèn)的0，因?yàn)檫@樣能幫我們更好地理解模型。
nthread[默認(rèn)值為最大可能的線程數(shù)]
- 這個(gè)參數(shù)用來進(jìn)行多線程控制，應(yīng)當(dāng)輸入系統(tǒng)的核數(shù)。
- 如果你希望使用CPU全部的核，那就不要輸入這個(gè)參數(shù)，算法會自動檢測它。
還有兩個(gè)參數(shù)，XGBoost會自動設(shè)置，目前你不用管它。接下來咱們一起看booster參數(shù)。
（2）booster參數(shù)
盡管有兩種booster可供選擇，我這里只介紹tree booster，因?yàn)?strong>它的表現(xiàn)遠(yuǎn)遠(yuǎn)勝過linear booster，所以linear booster很少用到。
eta[默認(rèn)0.3]
- 和GBM中的 learning rate 參數(shù)類似。
- 通過減少每一步的權(quán)重，可以提高模型的魯棒性。
- 典型值為0.01-0.2。
min_child_weight[默認(rèn)1]
- 決定最小葉子節(jié)點(diǎn)樣本權(quán)重和。
- 和GBM的 min_child_leaf 參數(shù)類似，但不完全一樣。XGBoost的這個(gè)參數(shù)是最小樣本權(quán)重的和，而GBM參數(shù)是最小樣本總數(shù)。
- 這個(gè)參數(shù)用于避免過擬合。當(dāng)它的值較大時(shí)，可以避免模型學(xué)習(xí)到局部的特殊樣本。
- 但是如果這個(gè)值過高，會導(dǎo)致欠擬合。這個(gè)參數(shù)需要使用CV來調(diào)整。
max_depth[默認(rèn)6]
- 和GBM中的參數(shù)相同，這個(gè)值為樹的最大深度。
- 這個(gè)值也是用來避免過擬合的。max_depth越大，模型會學(xué)到更具體更局部的樣本。
- 需要使用CV函數(shù)來進(jìn)行調(diào)優(yōu)。
- 典型值：3-10
max_leaf_nodes
- 樹上最大的節(jié)點(diǎn)或葉子的數(shù)量。
- 可以替代max_depth的作用。因?yàn)槿绻傻氖嵌鏄?#xff0c;一個(gè)深度為n的樹最多生成n2n2個(gè)葉子。
- 如果定義了這個(gè)參數(shù)，GBM會忽略max_depth參數(shù)。
gamma[默認(rèn)0]
- 在節(jié)點(diǎn)分裂時(shí)，只有分裂后損失函數(shù)的值下降了，才會分裂這個(gè)節(jié)點(diǎn)。Gamma指定了節(jié)點(diǎn)分裂所需的最小損失函數(shù)下降值。
- 這個(gè)參數(shù)的值越大，算法越保守。這個(gè)參數(shù)的值和損失函數(shù)息息相關(guān)，所以是需要調(diào)整的。
max_delta_step[默認(rèn)0]
- 這參數(shù)限制每棵樹權(quán)重改變的最大步長。如果這個(gè)參數(shù)的值為0，那就意味著沒有約束。如果它被賦予了某個(gè)正值，那么它會讓這個(gè)算法更加保守。
- 通常，這個(gè)參數(shù)不需要設(shè)置。但是當(dāng)各類別的樣本十分不平衡時(shí)，它對邏輯回歸是很有幫助的。
- 這個(gè)參數(shù)一般用不到，但是你可以挖掘出來它更多的用處。
subsample[默認(rèn)1]
- 和GBM中的subsample參數(shù)一模一樣。這個(gè)參數(shù)控制對于每棵樹，隨機(jī)采樣的比例。
- 減小這個(gè)參數(shù)的值，算法會更加保守，避免過擬合。但是，如果這個(gè)值設(shè)置得過小，它可能會導(dǎo)致欠擬合。
- 典型值：0.5-1
colsample_bytree[默認(rèn)1]
- 和GBM里面的max_features參數(shù)類似。用來控制每棵隨機(jī)采樣的列數(shù)的占比(每一列是一個(gè)特征)。
- 典型值：0.5-1
colsample_bylevel[默認(rèn)1]
- 用來控制樹的每一級的每一次分裂，對列數(shù)的采樣的占比。
- 我個(gè)人一般不太用這個(gè)參數(shù)，因?yàn)閟ubsample參數(shù)和colsample_bytree參數(shù)可以起到相同的作用。但是如果感興趣，可以挖掘這個(gè)參數(shù)更多的用處。
lambda[默認(rèn)1]
- 權(quán)重的L2正則化項(xiàng)。(和Ridge regression類似)。
- 這個(gè)參數(shù)是用來控制XGBoost的正則化部分的。雖然大部分?jǐn)?shù)據(jù)科學(xué)家很少用到這個(gè)參數(shù)，但是這個(gè)參數(shù)在減少過擬合上還是可以挖掘出更多用處的。
alpha[默認(rèn)1]
- 權(quán)重的L1正則化項(xiàng)。(和Lasso regression類似)。
- 可以應(yīng)用在很高維度的情況下，使得算法的速度更快。
scale_pos_weight[默認(rèn)1]
- 在各類別樣本十分不平衡時(shí)，把這個(gè)參數(shù)設(shè)定為一個(gè)正值，可以使算法更快收斂。
（3）學(xué)習(xí)目標(biāo)參數(shù)
這個(gè)參數(shù)用來控制理想的優(yōu)化目標(biāo)和每一步結(jié)果的度量方法。
1、objective[默認(rèn)reg:linear]
- 這個(gè)參數(shù)定義需要被最小化的損失函數(shù)。最常用的值有：?
- binary:logistic 二分類的邏輯回歸，返回預(yù)測的概率(不是類別)。
- multi:softmax 使用softmax的多分類器，返回預(yù)測的類別(不是概率)。?在這種情況下，你還需要多設(shè)一個(gè)參數(shù)：num_class(類別數(shù)目)。
- multi:softprob 和multi:softmax參數(shù)一樣，但是返回的是每個(gè)數(shù)據(jù)屬于各個(gè)類別的概率。
2、eval_metric[默認(rèn)值取決于objective參數(shù)的取值]
- 對于有效數(shù)據(jù)的度量方法。
- 對于回歸問題，默認(rèn)值是rmse，對于分類問題，默認(rèn)值是error。
- 典型值有：?
- rmse 均方根誤差(∑Ni=1?2N?????√∑i=1N?2N)
- mae 平均絕對誤差(∑Ni=1|?|N∑i=1N|?|N)
- logloss 負(fù)對數(shù)似然函數(shù)值
- error 二分類錯(cuò)誤率(閾值為0.5)
- merror 多分類錯(cuò)誤率
- mlogloss 多分類logloss損失函數(shù)
- auc 曲線下面積
?
?
?
?
總結(jié)
以上是生活随笔為你收集整理的集成学习-Boosting集成学习算法XGBoost的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 集成学习-Boosting集成学习算法G
- 下一篇： 集成学习-Boosting集成学习算法L