目錄

• Bagging
• Boosting
• stacking
• 常用的集成算法
• • 隨機(jī)森林 Random Forest
  • Adaboost
  • GBDT
  • xgboost
  • Lightgbm
• 關(guān)于作者

集成算法是構(gòu)建多個(gè)學(xué)習(xí)器，通過(guò)一定策略結(jié)合來(lái)完成學(xué)習(xí)任務(wù)。正所謂三個(gè)臭皮匠頂一個(gè)諸葛亮，當(dāng)弱學(xué)習(xí)器被正確組合時(shí)，我們能得到更精確、魯棒性更好的學(xué)習(xí)器。由于個(gè)體學(xué)習(xí)器在準(zhǔn)確性和多樣性存在沖突，追求多樣性勢(shì)必要犧牲準(zhǔn)確性。這就需要將這些“好而不同”的個(gè)體學(xué)習(xí)器結(jié)合起來(lái)。而研究如何產(chǎn)生并結(jié)合個(gè)體學(xué)習(xí)器也是集成學(xué)習(xí)研究的核心。
集成學(xué)習(xí)的思想時(shí)將這些弱學(xué)習(xí)器的偏置或方差結(jié)合起來(lái)，從而創(chuàng)建一個(gè)強(qiáng)學(xué)習(xí)機(jī)，獲得更好的性能
按照個(gè)體學(xué)習(xí)器之間的關(guān)系，集成算法分為Bagging、Boosting、Stacking三大類(lèi)。

Bagging

基于自主采樣法（bootstrap sampling）隨即得到一些樣本集訓(xùn)練，用來(lái)分別訓(xùn)練不同的基學(xué)習(xí)器，然后對(duì)不同的基學(xué)習(xí)器得到的結(jié)果投票得出最終的分類(lèi)結(jié)果。自主采樣法得到的樣本大概會(huì)有63%的數(shù)據(jù)樣本被使用(有些數(shù)據(jù)樣本會(huì)被重復(fù)抽取，有些不會(huì)被抽取），剩下的可以用來(lái)做驗(yàn)證集。

Bagging中各個(gè)算法之間沒(méi)有依賴，可以并行計(jì)算，他的結(jié)果參考了各種情況，實(shí)現(xiàn)的是在欠擬合和過(guò)擬合之間取折中。

Boosting

Boosting，提升算法，通過(guò)反復(fù)學(xué)習(xí)得到一系列弱分類(lèi)器，然后組合這些弱分類(lèi)器得到一個(gè)強(qiáng)分類(lèi)器，吧弱學(xué)習(xí)器提升為強(qiáng)學(xué)習(xí)器的過(guò)程。主要分為兩個(gè)部分，加法模型和向前分布。
加法模型就是把一系列弱學(xué)習(xí)器相加串聯(lián)為強(qiáng)學(xué)習(xí)器，
$$F_M(x;P)=\sum _{m=1}^n{\beta }_{m}h(x;a_m)$$
其中，$h(x;a_m)$是一些列的弱學(xué)習(xí)器，$a_m$是該學(xué)習(xí)器訓(xùn)練得到的最優(yōu)參數(shù)，${\beta }_m$是對(duì)應(yīng)弱學(xué)習(xí)器在強(qiáng)學(xué)習(xí)器中所占比例的系數(shù)。
向前分布是指本輪中的學(xué)習(xí)器是在上一輪學(xué)習(xí)器的基礎(chǔ)上迭代訓(xùn)練得到的，
$$F_m(x)=F_{m?1}(x)+{\beta }_m{h}_m(x;a_m)$$

訓(xùn)練過(guò)程為階梯狀，基模型按照次序一一進(jìn)行訓(xùn)練，基模型的訓(xùn)練集按照某種策略每次都進(jìn)行一定的轉(zhuǎn)化，如果某一個(gè)數(shù)據(jù)在這次分錯(cuò)了，那么在下一次就會(huì)給他更大的權(quán)重。對(duì)所有基模型預(yù)測(cè)的結(jié)果進(jìn)行線性綜合產(chǎn)生最終的預(yù)測(cè)結(jié)果。
一般來(lái)說(shuō)，他的效果會(huì)比Bagging好一些，由于新模型是在就模型的基本上建立的，因此不能使用并行方式訓(xùn)練，并且由于對(duì)錯(cuò)誤樣本的關(guān)注，也可能造成過(guò)擬合。

stacking

stacking訓(xùn)練一個(gè)模型用于組合其他各個(gè)基模型。具體方法是吧數(shù)據(jù)分成兩部分，用其中一部分訓(xùn)練幾個(gè)基模型1、2、3，用另一部分?jǐn)?shù)據(jù)測(cè)試這幾個(gè)基模型，把1、2、3的輸出作為輸入，訓(xùn)練組合模型。注意，他不是把模型的結(jié)果組織起來(lái)，而把模型組織起來(lái)。理論上，stacking可以組織任何模型，實(shí)際中常用單層logistic回歸作為模型。

舉個(gè)栗子：

首先我們會(huì)得到兩組數(shù)據(jù)：訓(xùn)練集和測(cè)試集。將訓(xùn)練集分成5份：train1,train2,train3,train4,train5。

選定基模型。這里假定我們選擇了xgboost, lightgbm 和 randomforest這三種作為基模型。比如xgboost模型部分：依次用train1,train2,train3,train4,train5作為驗(yàn)證集，其余4份作為訓(xùn)練集，進(jìn)行5折交叉驗(yàn)證進(jìn)行模型訓(xùn)練；再在測(cè)試集上進(jìn)行預(yù)測(cè)。這樣會(huì)得到在訓(xùn)練集上由xgboost模型訓(xùn)練出來(lái)的5份predictions，和在測(cè)試集上的1份預(yù)測(cè)值B1。將這五份縱向重疊合并起來(lái)得到A1。lightgbm和randomforest模型部分同理。

三個(gè)基模型訓(xùn)練完畢后，將三個(gè)模型在訓(xùn)練集上的預(yù)測(cè)值作為分別作為3個(gè)"特征"A1,A2,A3，使用LR模型進(jìn)行訓(xùn)練，建立LR模型。

使用訓(xùn)練好的LR模型，在三個(gè)基模型之前在測(cè)試集上的預(yù)測(cè)值所構(gòu)建的三個(gè)"特征"的值(B1,B2,B3)上，進(jìn)行預(yù)測(cè)，得出最終的預(yù)測(cè)類(lèi)別或概率。

stacking一般是兩層就夠了。

常用的集成算法

隨機(jī)森林 Random Forest

概念：通過(guò)集成學(xué)習(xí)的思想將多棵樹(shù)集成的一種算法。基本單元是決策樹(shù)。隨機(jī)森林中每顆決策樹(shù)都是一個(gè)分類(lèi)器，對(duì)于一個(gè)輸入樣本，N棵樹(shù)會(huì)有N個(gè)分類(lèi)結(jié)果。隨機(jī)森林集成了所有的分類(lèi)投票結(jié)果，將投票次數(shù)最多的類(lèi)別指定為最終輸出。

隨機(jī)森林生成規(guī)則：

• 如果訓(xùn)練集大小為N，對(duì)于每棵樹(shù)而言，隨機(jī)且有放回的從訓(xùn)練集中的抽取N個(gè)訓(xùn)練樣本，作為該樹(shù)的訓(xùn)練集。（隨機(jī)抽樣保證每棵樹(shù)的訓(xùn)練集不同，有放回抽樣保證每棵樹(shù)的訓(xùn)練樣本有交集，避免樹(shù)的結(jié)果有很大差異）
• 特征隨機(jī)。如果每個(gè)樣本的特征維度是M。指定一個(gè)常數(shù)m<<M,隨機(jī)從M個(gè)特征中選取m個(gè)特征子集，每次樹(shù)進(jìn)行分裂時(shí)，從m個(gè)特征中選擇最優(yōu)的
• 每棵樹(shù)盡最大程度生長(zhǎng)，并沒(méi)有剪枝過(guò)程
• 將生成的多棵樹(shù)組成隨機(jī)森林，用隨機(jī)森林對(duì)新的數(shù)據(jù)進(jìn)行分類(lèi)，分類(lèi)結(jié)果按樹(shù)分類(lèi)多少而定

特點(diǎn)：

• 在當(dāng)前所有算法中，具有極好的準(zhǔn)確率
• 能夠處理具有高維特征的輸入樣本，而且不需要降維
• 能夠評(píng)估各個(gè)特征在分類(lèi)問(wèn)題上的重要性
• 在生成過(guò)程中，能夠獲取到內(nèi)部生成誤差的一種無(wú)偏估計(jì)
• 對(duì)于缺省值也能夠獲得很好的結(jié)果
• 隨機(jī)森林中的兩個(gè)“隨機(jī)性”是隨機(jī)森林不容易陷入過(guò)擬合，并且具有很好的抗噪能力
• 能夠處理離散型/連續(xù)型數(shù)據(jù)，無(wú)需規(guī)范化
• 隨機(jī)森林不使用全樣本，因?yàn)槿珮颖竞鲆暳司植繕颖镜囊?guī)律，不利于模型泛化能力

缺點(diǎn)：

• 隨機(jī)森林在解決回歸問(wèn)題時(shí)，表現(xiàn)較差，這是因?yàn)樗⒉荒芙o出一個(gè)連續(xù)的輸出。
• 隨機(jī)森林已經(jīng)被證明在某些噪音較大的分類(lèi)或者回歸問(wèn)題上會(huì)過(guò)擬合
• 隨機(jī)森林就像黑盒子，無(wú)法控制模型內(nèi)部運(yùn)行（可控性差）
• 對(duì)于小數(shù)據(jù)或者低維數(shù)據(jù)，可能不能產(chǎn)生很好的分類(lèi)

Adaboost

adaboost將弱分類(lèi)器迭代成強(qiáng)分類(lèi)器的過(guò)程，每個(gè)迭代過(guò)程中改變樣本權(quán)重和分類(lèi)器權(quán)重，最終結(jié)果是每個(gè)分類(lèi)器的權(quán)重和。
原理：

初始化訓(xùn)練樣本數(shù)據(jù)（每個(gè)樣本）的權(quán)值分布：如果有N個(gè)樣本，則每一個(gè)訓(xùn)練的樣本點(diǎn)最開(kāi)始時(shí)都被賦予相同的權(quán)重

訓(xùn)練弱分類(lèi)器。具體訓(xùn)練過(guò)程中，如果某個(gè)樣本已經(jīng)被準(zhǔn)確的分類(lèi)，那么在構(gòu)造下一個(gè)訓(xùn)練集中，他的權(quán)重就被降低；相反，如果某個(gè)樣本點(diǎn)沒(méi)有被準(zhǔn)確分類(lèi)，那么他的權(quán)重就得到提高。同時(shí)，得到弱分類(lèi)器對(duì)應(yīng)的話語(yǔ)權(quán)。然后，更新權(quán)值后的樣本及被用于訓(xùn)練下一個(gè)分類(lèi)器，整個(gè)訓(xùn)練過(guò)程如此迭代的進(jìn)行下去。

將各個(gè)訓(xùn)練得到的弱分類(lèi)器組合成強(qiáng)分類(lèi)器。各個(gè)弱分類(lèi)器的訓(xùn)練過(guò)程結(jié)束后，分類(lèi)誤差率小的弱分類(lèi)器話語(yǔ)權(quán)較大，其在最終的分類(lèi)函數(shù)中起著較大的決定作用，而分類(lèi)誤差率大的弱分類(lèi)器的話語(yǔ)權(quán)小。

計(jì)算弱分類(lèi)器的誤差函數(shù)，即分錯(cuò)樣本對(duì)應(yīng)的權(quán)值之和，adaboost損失函數(shù)為指數(shù)損失
$${?}_m=\sum _{n=1}N{w}_n^{(m)}I(y_m(x_n)=t_n)$$
計(jì)算弱分類(lèi)器$G_m(x)$的話語(yǔ)權(quán)${\alpha }_m$
$${\alpha }_m=\frac{1}{2}log\frac{1?{?}_m}{{?}_m}$$
更新訓(xùn)練樣本集的權(quán)值分布
$$D_{m+1}=(W_{m+1,1},W_{m+1,,2}.......W_{m+1,i}.......W_{m+1,N})$$
$$W_{m+1,i}=\frac{W_{mi}}{Z_m}exp(?{\alpha }_m{y}_i{G}_m{x}_i)),i=1,2.......N$$
$D_{m+1}$是用于下次迭代時(shí)樣本的權(quán)值，$W_{m+1,i}$是下一次迭代時(shí)，第i個(gè)樣本的權(quán)值。其中，$y_i$代表第i個(gè)樣本對(duì)應(yīng)的類(lèi)別（1或-1），$G_m(x_i)$表示弱分類(lèi)器對(duì)樣本$x_i$的分類(lèi)（1或-1）。$Z_m$是歸一化因子，使得所有樣本對(duì)應(yīng)的權(quán)值之和為
$$Z_M=\sum _{i=1}^N{w}_{mi}exp(?{\alpha }_m{y}_i{G}_m(x_i))$$
迭代完成和，組合弱分類(lèi)器
$$G(x)=sign(f(x))=sign(\sum _{m=1}^M{\alpha }_m{G}_m(x))$$

優(yōu)點(diǎn)

• 精度很高的分類(lèi)器
• 很好地利用了弱分類(lèi)器進(jìn)行級(jí)聯(lián)
• 可以將不同的分類(lèi)算法作為弱分類(lèi)器
• 充分考慮每個(gè)分類(lèi)器的權(quán)重
• 提供的是框架，可以使用各種方法構(gòu)建弱分類(lèi)器
• 簡(jiǎn)單，不需要做特征篩選
• 不用擔(dān)心過(guò)擬合

實(shí)際應(yīng)用

• 用于二分類(lèi)或多分類(lèi)
• 特征選擇
• 分類(lèi)任務(wù)的baseline

缺點(diǎn)

• 迭代次數(shù)不太好設(shè)定
• 數(shù)據(jù)不平衡導(dǎo)致分類(lèi)精度下降
• 訓(xùn)練比較耗時(shí)，每次重新選擇當(dāng)前分類(lèi)器最好切分點(diǎn)
• 對(duì)異常樣本比較敏感，異常樣本在迭代過(guò)程中會(huì)獲得較高權(quán)值，影響最終學(xué)習(xí)器的性能表現(xiàn)

訓(xùn)練過(guò)程中，每輪訓(xùn)練一直存在分類(lèi)錯(cuò)誤的問(wèn)題，整個(gè)Adaboost卻能快速收斂
每輪訓(xùn)練結(jié)束后，AdaBoost 會(huì)對(duì)樣本的權(quán)重進(jìn)行調(diào)整，調(diào)整的結(jié)果是越到后面被錯(cuò)誤分類(lèi)的樣本權(quán)重會(huì)越高。而后面的分類(lèi)器為了達(dá)到較低的帶權(quán)分類(lèi)誤差，會(huì)把樣本權(quán)重高的樣本分類(lèi)正確。這樣造成的結(jié)果是，雖然每個(gè)弱分類(lèi)器可能都有分錯(cuò)的樣本，然而整個(gè) AdaBoost 卻能保證對(duì)每個(gè)樣本進(jìn)行正確分類(lèi)，從而實(shí)現(xiàn)快速收斂。

GBDT

gbdt，Gradient Boost Decision Tree,梯度下降樹(shù)。是一種基于提升決策樹(shù)的模型以分類(lèi)回歸決策樹(shù)作為基本分類(lèi)器的模型。

boosting tree
提升樹(shù)就是把分類(lèi)回歸決策樹(shù)CART直接進(jìn)行線性組合的決策樹(shù)模型。
$$f_M(x)==\sum _{m=1}MT(x;{\theta }_m)$$
$T(x;{\theta }_m)$表示決策樹(shù)，${\theta }_m$是決策樹(shù)的參數(shù)，M是樹(shù)的個(gè)數(shù)
到第m步的模型是：
$$f_m(x)=f_{m?1}(x)+T(x;{\theta }_m)$$
$f_{m?1}(x)$當(dāng)前模型，通過(guò)最小化損失函數(shù)的方法確定下一顆決策樹(shù)的參數(shù)。一般對(duì)于回歸問(wèn)題采用的損失函數(shù)是平方誤差損失函數(shù)，對(duì)于分類(lèi)問(wèn)題則使用指數(shù)損失函數(shù)。
$$f_m(x)=f_{m?1}(x)?T(x;{\theta }_m)$$
以回歸問(wèn)題為例：
$$L=[y?f_m(x){]}^2=[r?T(x;{\theta }_m){]}^2$$
$r=y?f_{m?1}(x)$是當(dāng)前模型擬合的殘差

gradient boosting
提升樹(shù)算法利用加法模型與前向分布算法實(shí)現(xiàn)學(xué)習(xí)的優(yōu)化過(guò)程，當(dāng)損失函數(shù)是平方損失和指數(shù)損失的時(shí)候，每一步優(yōu)化比較簡(jiǎn)單，但是對(duì)一般損失函數(shù)而言，往往每一步算法優(yōu)化并不是那么容易，所以就有了梯度提升算法，主要是利用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值：
$$?[\frac{?L(y,f(x_i))}{?f(x_i)}{]}_{f(x)=f_{m?1}(x)}$$
算法流程：

gbdt的核心在于，每一顆樹(shù)學(xué)的是之前所有樹(shù)結(jié)論和的殘差，這個(gè)殘差就是一個(gè)加預(yù)測(cè)之后能得到真實(shí)值的累加量（所以gbdt中的樹(shù)都是回歸樹(shù)）。gbdt的弱分類(lèi)器默認(rèn)選擇CART TREE，也可以選擇其他低方差高偏差的分類(lèi)器。
比如A的真實(shí)年齡是18歲，但第一棵樹(shù)的預(yù)測(cè)年齡是12歲，差了6歲，即殘差為6歲。那么在第二棵樹(shù)里我們把A的年齡設(shè)為6歲去學(xué)習(xí)，如果第二棵樹(shù)真的能把A分到6歲的葉子節(jié)點(diǎn)，那累加兩棵樹(shù)的結(jié)論就是A的真實(shí)年齡；如果第二棵樹(shù)的結(jié)論是5歲，則A仍然存在1歲的殘差，第三棵樹(shù)里A的年齡就變成1歲，繼續(xù)學(xué)

在第一棵樹(shù)分枝和圖1一樣，由于A,B年齡較為相近，C,D年齡較為相近，他們被分為兩撥，每撥用平均年齡作為預(yù)測(cè)值。此時(shí)計(jì)算殘差（殘差的意思就是： A的預(yù)測(cè)值 + A的殘差 = A的實(shí)際值），所以A的殘差就是16-15=1（注意，A的預(yù)測(cè)值是指前面所有樹(shù)累加的和，這里前面只有一棵樹(shù)所以直接是15，如果還有樹(shù)則需要都累加起來(lái)作為A的預(yù)測(cè)值）。進(jìn)而得到A,B,C,D的殘差分別為-1,1，-1,1。然后我們拿殘差替代A,B,C,D的原值，到第二棵樹(shù)去學(xué)習(xí)，如果我們的預(yù)測(cè)值和它們的殘差相等，則只需把第二棵樹(shù)的結(jié)論累加到第一棵樹(shù)上就能得到真實(shí)年齡了。這里的數(shù)據(jù)顯然是我可以做的，第二棵樹(shù)只有兩個(gè)值1和-1，直接分成兩個(gè)節(jié)點(diǎn)。此時(shí)所有人的殘差都是0，即每個(gè)人都得到了真實(shí)的預(yù)測(cè)值。

適用范圍

• 所有回歸問(wèn)題（線性/非線性）
• 二分類(lèi)問(wèn)題

優(yōu)點(diǎn)

• 預(yù)測(cè)精度高
• 適合低維數(shù)據(jù)
• 能處理非線性數(shù)據(jù)

缺點(diǎn)

• 并行麻煩
• 數(shù)據(jù)維度高時(shí)會(huì)加大算法的計(jì)算復(fù)雜度

xgboost

xgboost，exterme gradient boosting，極限梯度提升。是基于決策樹(shù)的集成機(jī)器學(xué)習(xí)算法，以梯度提升為框架。xgboost由gbdt發(fā)展而來(lái)，同樣是利用加法模型與前向分布算法實(shí)現(xiàn)學(xué)習(xí)的優(yōu)化過(guò)程，但與gbdt不同的地方在于：

• 基分類(lèi)器：XGBoost的基分類(lèi)器不僅支持CART決策樹(shù)，還支持線性分類(lèi)器，此時(shí)XGBoost相當(dāng)于帶L1和L2正則化項(xiàng)的Logistic回歸（分類(lèi)問(wèn)題）或者線性回歸（回歸問(wèn)題）。
• 目標(biāo)函數(shù)：xgboost的損失函數(shù)添加了正則化項(xiàng)，使用正則用以控制模型的復(fù)雜度，正則項(xiàng)里包含了樹(shù)的葉子節(jié)點(diǎn)個(gè)數(shù)、每個(gè)葉子節(jié)點(diǎn)權(quán)重（葉節(jié)點(diǎn)的score值）的平方和。
• 優(yōu)化方法：xgboost對(duì)損失函數(shù)做了二階泰勒展開(kāi)。并且支持自定義損失函數(shù)，只要損失函數(shù)一階、二階可導(dǎo)
• xgboost對(duì)缺失值進(jìn)行了處理。讓缺失值分別被切分到左節(jié)點(diǎn)以及右節(jié)點(diǎn)，通過(guò)計(jì)算得分值比較兩種切分方法哪一個(gè)更優(yōu)，則會(huì)對(duì)每個(gè)特征的缺失值都會(huì)學(xué)習(xí)到一個(gè)最優(yōu)的默認(rèn)切分方向。
• 防止過(guò)擬合：xgboost除了增加了正則項(xiàng)來(lái)防止過(guò)擬合，還支持列采樣的方式來(lái)防止過(guò)擬合
• 并行化，可以在最短時(shí)間內(nèi)用更少的計(jì)算資源得到更好的結(jié)果。注意不是tree維度的并行，而是特征維度的并行。XGBoost預(yù)先將每個(gè)特征按特征值排好序，存儲(chǔ)為塊結(jié)構(gòu)，分裂結(jié)點(diǎn)時(shí)可以采用多線程并行查找每個(gè)特征的最佳分割點(diǎn)，極大提升訓(xùn)練速度。

XGBoost的可以使用Regression Tree（CART）作為基學(xué)習(xí)器，也可以使用線性分類(lèi)器作為基學(xué)習(xí)器。
圖中為兩顆回歸樹(shù)（左右兩個(gè)），其中樹(shù)下方的輸出值即為葉節(jié)點(diǎn)的權(quán)重（得分），當(dāng)輸出一個(gè)樣本進(jìn)行預(yù)測(cè)時(shí)，根據(jù)每個(gè)內(nèi)部節(jié)點(diǎn)的決策條件進(jìn)行劃分節(jié)點(diǎn)，最終被劃分到的葉節(jié)點(diǎn)的權(quán)重即為該樣本的預(yù)測(cè)輸出值

訓(xùn)練過(guò)程
目標(biāo)函數(shù)：

公式（2）右邊第一部分是度量預(yù)測(cè)值與真實(shí)值之間的損失函數(shù)，第二部分表示對(duì)模型復(fù)雜度的懲罰項(xiàng)（正則項(xiàng)），在懲罰項(xiàng)中 $\gamma$ 、 $\lambda$ 表示懲罰系數(shù)， $T$表示給定一顆樹(shù)的葉節(jié)點(diǎn)數(shù)，$||\omega |{|}^2$ 表示每顆樹(shù)葉節(jié)點(diǎn)上的輸出分?jǐn)?shù)的平方(相當(dāng)于L2正則)。從目標(biāo)函數(shù)的定義可以看出XGBoost對(duì)模型復(fù)雜度考慮了每顆樹(shù)的葉節(jié)點(diǎn)個(gè)數(shù)，以及每顆樹(shù)葉節(jié)點(diǎn)輸出得分值得平方和。

XGBoost為什么使用泰勒二階展開(kāi)

• 精準(zhǔn)性：相對(duì)于GBDT的一階泰勒展開(kāi)，XGBoost采用二階泰勒展開(kāi)，可以更為精準(zhǔn)的逼近真實(shí)的損失函數(shù)
• 可擴(kuò)展性：損失函數(shù)支持自定義，只需要新的損失函數(shù)二階可導(dǎo)。

XGBoost為什么快

• 分塊并行：訓(xùn)練前每個(gè)特征按特征值進(jìn)行排序并存儲(chǔ)為Block結(jié)構(gòu)，后面查找特征分割點(diǎn)時(shí)重復(fù)使用，并且支持并行查找每個(gè)特征的分割點(diǎn)
• 候選分位點(diǎn)：每個(gè)特征采用常數(shù)個(gè)分位點(diǎn)作為候選分割點(diǎn)
• CPU cache 命中優(yōu)化： 使用緩存預(yù)取的方法，對(duì)每個(gè)線程分配一個(gè)連續(xù)的buffer，讀取每個(gè)block中樣本的梯度信息并存入連續(xù)的Buffer中。
• Block 處理優(yōu)化：Block預(yù)先放入內(nèi)存；Block按列進(jìn)行解壓縮；將Block劃分到不同硬盤(pán)來(lái)提高吞吐

XGBoost防止過(guò)擬合的方法

• 目標(biāo)函數(shù)添加正則項(xiàng)：葉子節(jié)點(diǎn)個(gè)數(shù)+葉子節(jié)點(diǎn)權(quán)重的L2正則化
• 列抽樣：訓(xùn)練的時(shí)候只用一部分特征（不考慮剩余的block塊即可）
• 子采樣：每輪計(jì)算可以不使用全部樣本，使算法更加保守
• shrinkage: 可以叫學(xué)習(xí)率或步長(zhǎng)，為了給后面的訓(xùn)練留出更多的學(xué)習(xí)空間

XGBoost中葉子結(jié)點(diǎn)的權(quán)重如何計(jì)算出來(lái)

XGBoost如何處理不平衡數(shù)據(jù)

• 使用AUC時(shí)，可以通過(guò)設(shè)置scale_pos_weight來(lái)平衡正樣本和負(fù)樣本的權(quán)重。例如，當(dāng)正負(fù)樣本比例為1:10時(shí)，scale_pos_weight可以取10；
• 如果你在意概率(預(yù)測(cè)得分的合理性)，你不能重新平衡數(shù)據(jù)集(會(huì)破壞數(shù)據(jù)的真實(shí)分布)，應(yīng)該設(shè)置max_delta_step為一個(gè)有限數(shù)字來(lái)幫助收斂（基模型為L(zhǎng)R時(shí)有效）。
• 通過(guò)上采樣、下采樣、SMOTE算法或者自定義代價(jià)函數(shù)的方式解決正負(fù)樣本不平衡的問(wèn)題。

XGBoost中如何對(duì)樹(shù)進(jìn)行剪枝

• 在目標(biāo)函數(shù)中增加了正則項(xiàng)：使用葉子結(jié)點(diǎn)的數(shù)目和葉子結(jié)點(diǎn)權(quán)重的L2模的平方，控制樹(shù)的復(fù)雜度。
• 在結(jié)點(diǎn)分裂時(shí)，定義了一個(gè)閾值，如果分裂后目標(biāo)函數(shù)的增益小于該閾值，則不分裂。
• 當(dāng)引入一次分裂后，重新計(jì)算新生成的左、右兩個(gè)葉子結(jié)點(diǎn)的樣本權(quán)重和。如果任一個(gè)葉子結(jié)點(diǎn)的樣本權(quán)重低于某一個(gè)閾值（最小樣本權(quán)重和），也會(huì)放棄此次分裂。
• XGBoost 先從頂?shù)降捉?shù)直到最大深度，再?gòu)牡椎巾敺聪驒z查是否有不滿足分裂條件的結(jié)點(diǎn)，進(jìn)行剪枝。(后剪枝)

XGBoost如何評(píng)價(jià)特征的重要性

• weight ：該特征在所有樹(shù)中被用作分割樣本的特征的總次數(shù)。
• gain ：該特征在其出現(xiàn)過(guò)的所有樹(shù)中產(chǎn)生的平均增益。
• cover ：該特征在其出現(xiàn)過(guò)的所有樹(shù)中的平均覆蓋范圍。

LightGBM比XGBoost的優(yōu)點(diǎn)

• 分割點(diǎn)查找算法：XGB使用特征預(yù)排序算法，LGB使用基于直方圖的切分點(diǎn)算法，減少內(nèi)存占用，提高計(jì)算效率
• 支持離散變量：無(wú)法直接輸入類(lèi)別型變量，因此需要事先對(duì)類(lèi)別型變量進(jìn)行編碼（例如獨(dú)熱編碼），而LightGBM可以直接處理類(lèi)別型變量。
• 緩存命中率：XGB使用Block結(jié)構(gòu)的一個(gè)缺點(diǎn)是取梯度的時(shí)候，是通過(guò)索引來(lái)獲取的，而這些梯度的獲取順序是按照特征的大小順序的，這將導(dǎo)致非連續(xù)的內(nèi)存訪問(wèn)，可能使得CPU cache緩存命中率低，從而影響算法效率。而LGB是基于直方圖分裂特征的，梯度信息都存儲(chǔ)在一個(gè)個(gè)bin中，所以訪問(wèn)梯度是連續(xù)的，緩存命中率高。
• LightGBM 與 XGboost 的并行策略不同

Lightgbm

LightGBM（Light Gradient Boosting Machine）是一個(gè)實(shí)現(xiàn)GBDT算法的框架，支持高效率的并行訓(xùn)練，并且具有更快的訓(xùn)練速度、更低的內(nèi)存消耗、更好的準(zhǔn)確率、支持分布式可以快速處理海量數(shù)據(jù)等優(yōu)點(diǎn)。

基于Histogram的決策樹(shù)算法
轉(zhuǎn)自https://zhuanlan.zhihu.com/p/99069186
直方圖算法
Histogram algorithm應(yīng)該翻譯為直方圖算法，直方圖算法的基本思想是：先把連續(xù)的浮點(diǎn)特征值離散化成 [公式] 個(gè)整數(shù)，同時(shí)構(gòu)造一個(gè)寬度為 [公式] 的直方圖。在遍歷數(shù)據(jù)的時(shí)候，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。

直方圖算法簡(jiǎn)單理解為：首先確定對(duì)于每一個(gè)特征需要多少個(gè)箱子（bin）并為每一個(gè)箱子分配一個(gè)整數(shù)；然后將浮點(diǎn)數(shù)的范圍均分成若干區(qū)間，區(qū)間個(gè)數(shù)與箱子個(gè)數(shù)相等，將屬于該箱子的樣本數(shù)據(jù)更新為箱子的值；最后用直方圖（bins）表示。看起來(lái)很高大上，其實(shí)就是直方圖統(tǒng)計(jì)，將大規(guī)模的數(shù)據(jù)放在了直方圖中。
特征離散化具有很多優(yōu)點(diǎn)，如存儲(chǔ)方便、運(yùn)算更快、魯棒性強(qiáng)、模型更加穩(wěn)定等。對(duì)于直方圖算法來(lái)說(shuō)最直接的有以下兩個(gè)優(yōu)點(diǎn)：

• 內(nèi)存占用更小：直方圖算法不僅不需要額外存儲(chǔ)預(yù)排序的結(jié)果，而且可以只保存特征離散化后的值，而這個(gè)值一般用8位整型存儲(chǔ)就足夠了，內(nèi)存消耗可以降低為原來(lái)的1/8。也就是說(shuō)XGBoost需要用32位的浮點(diǎn)數(shù)去存儲(chǔ)特征值，并用[公式]位的整形去存儲(chǔ)索引，而 LightGBM只需要用 32 位去存儲(chǔ)直方圖，內(nèi)存相當(dāng)于減少為1/8
• 計(jì)算代價(jià)更小：預(yù)排序算法XGBoost每遍歷一個(gè)特征值就需要計(jì)算一次分裂的增益，而直方圖算法LightGBM只需要計(jì)算k次（k可以認(rèn)為是常數(shù)），直接將時(shí)間復(fù)雜度從O(datafeature)降低到O(kfeature)，而我們知道data>>k。
  當(dāng)然，Histogram算法并不是完美的。由于特征被離散化后，找到的并不是很精確的分割點(diǎn)，所以會(huì)對(duì)結(jié)果產(chǎn)生影響。但在不同的數(shù)據(jù)集上的結(jié)果表明，離散化的分割點(diǎn)對(duì)最終的精度影響并不是很大，甚至有時(shí)候會(huì)更好一點(diǎn)。原因是決策樹(shù)本來(lái)就是弱模型，分割點(diǎn)是不是精確并不是太重要；較粗的分割點(diǎn)也有正則化的效果，可以有效地防止過(guò)擬合；即使單棵樹(shù)的訓(xùn)練誤差比精確分割的算法稍大，但在梯度提升（Gradient Boosting）的框架下沒(méi)有太大的影響。

直方圖做差加速
LightGBM另一個(gè)優(yōu)化是Histogram（直方圖）做差加速。一個(gè)葉子的直方圖可以由它的父親節(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到，在速度上可以提升一倍。通常構(gòu)造直方圖時(shí)，需要遍歷該葉子上的所有數(shù)據(jù)，但直方圖做差僅需遍歷直方圖的k個(gè)桶。在實(shí)際構(gòu)建樹(shù)的過(guò)程中，LightGBM還可以先計(jì)算直方圖小的葉子節(jié)點(diǎn)，然后利用直方圖做差來(lái)獲得直方圖大的葉子節(jié)點(diǎn)，這樣就可以用非常微小的代價(jià)得到它兄弟葉子的直方圖。

注意：XGBoost 在進(jìn)行預(yù)排序時(shí)只考慮非零值進(jìn)行加速，而 LightGBM 也采用類(lèi)似策略：只用非零特征構(gòu)建直方圖。

帶深度限制的 Leaf-wise 算法
在Histogram算法之上，LightGBM進(jìn)行進(jìn)一步的優(yōu)化。首先它拋棄了大多數(shù)GBDT工具使用的按層生長(zhǎng) (level-wise) 的決策樹(shù)生長(zhǎng)策略，而使用了帶有深度限制的按葉子生長(zhǎng) (leaf-wise) 算法。
XGBoost 采用 Level-wise 的增長(zhǎng)策略，該策略遍歷一次數(shù)據(jù)可以同時(shí)分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，也好控制模型復(fù)雜度，不容易過(guò)擬合。但實(shí)際上Level-wise是一種低效的算法，因?yàn)樗患訁^(qū)分的對(duì)待同一層的葉子，實(shí)際上很多葉子的分裂增益較低，沒(méi)必要進(jìn)行搜索和分裂，因此帶來(lái)了很多沒(méi)必要的計(jì)算開(kāi)銷(xiāo)。

LightGBM采用Leaf-wise的增長(zhǎng)策略，該策略每次從當(dāng)前所有葉子中，找到分裂增益最大的一個(gè)葉子，然后分裂，如此循環(huán)。因此同Level-wise相比，Leaf-wise的優(yōu)點(diǎn)是：在分裂次數(shù)相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度；Leaf-wise的缺點(diǎn)是：可能會(huì)長(zhǎng)出比較深的決策樹(shù)，產(chǎn)生過(guò)擬合。因此LightGBM會(huì)在Leaf-wise之上增加了一個(gè)最大深度的限制，在保證高效率的同時(shí)防止過(guò)擬合。

單邊梯度采樣算法
Gradient-based One-Side Sampling 應(yīng)該被翻譯為單邊梯度采樣（GOSS）。GOSS算法從減少樣本的角度出發(fā)，排除大部分小梯度的樣本，僅用剩下的樣本計(jì)算信息增益，它是一種在減少數(shù)據(jù)量和保證精度上平衡的算法。
AdaBoost中，樣本權(quán)重是數(shù)據(jù)重要性的指標(biāo)。然而在GBDT中沒(méi)有原始樣本權(quán)重，不能應(yīng)用權(quán)重采樣。幸運(yùn)的是，我們觀察到GBDT中每個(gè)數(shù)據(jù)都有不同的梯度值，對(duì)采樣十分有用。即梯度小的樣本，訓(xùn)練誤差也比較小，說(shuō)明數(shù)據(jù)已經(jīng)被模型學(xué)習(xí)得很好了，直接想法就是丟掉這部分梯度小的數(shù)據(jù)。然而這樣做會(huì)改變數(shù)據(jù)的分布，將會(huì)影響訓(xùn)練模型的精確度，為了避免此問(wèn)題，提出了GOSS算法。
GOSS是一個(gè)樣本的采樣算法，目的是丟棄一些對(duì)計(jì)算信息增益沒(méi)有幫助的樣本留下有幫助的。根據(jù)計(jì)算信息增益的定義，梯度大的樣本對(duì)信息增益有更大的影響。因此，GOSS在進(jìn)行數(shù)據(jù)采樣的時(shí)候只保留了梯度較大的數(shù)據(jù)，但是如果直接將所有梯度較小的數(shù)據(jù)都丟棄掉勢(shì)必會(huì)影響數(shù)據(jù)的總體分布。所以，GOSS首先將要進(jìn)行分裂的特征的所有取值按照絕對(duì)值大小降序排序（XGBoost一樣也進(jìn)行了排序，但是LightGBM不用保存排序后的結(jié)果），選取絕對(duì)值最大的a100%個(gè)數(shù)據(jù)。然后在剩下的較小梯度數(shù)據(jù)中隨機(jī)選擇b100%個(gè)數(shù)據(jù)。接著將這b*100%個(gè)數(shù)據(jù)乘以一個(gè)常數(shù)(1-b)/a，這樣算法就會(huì)更關(guān)注訓(xùn)練不足的樣本，而不會(huì)過(guò)多改變?cè)瓟?shù)據(jù)集的分布。最后使用這（a+b)*100%個(gè)數(shù)據(jù)來(lái)計(jì)算信息增益。

互斥特征捆綁算法
高維度的數(shù)據(jù)往往是稀疏的，這種稀疏性啟發(fā)我們?cè)O(shè)計(jì)一種無(wú)損的方法來(lái)減少特征的維度。通常被捆綁的特征都是互斥的（即特征不會(huì)同時(shí)為非零值，像one-hot），這樣兩個(gè)特征捆綁起來(lái)才不會(huì)丟失信息。如果兩個(gè)特征并不是完全互斥（部分情況下兩個(gè)特征都是非零值），可以用一個(gè)指標(biāo)對(duì)特征不互斥程度進(jìn)行衡量，稱之為沖突比率，當(dāng)這個(gè)值較小時(shí)，我們可以選擇把不完全互斥的兩個(gè)特征捆綁，而不影響最后的精度。互斥特征捆綁算法（Exclusive Feature Bundling, EFB）指出如果將一些特征進(jìn)行融合綁定，則可以降低特征數(shù)量。這樣在構(gòu)建直方圖時(shí)的時(shí)間復(fù)雜度從O(datafeature) 變?yōu)镺(databundle) ，這里 bundle 指特征融合綁定后特征包的個(gè)數(shù)，且 bundle遠(yuǎn)小于feature 。
針對(duì)這種想法，我們會(huì)遇到兩個(gè)問(wèn)題：

• 怎么判定哪些特征應(yīng)該綁在一起（build bundled）？
• 怎么把特征綁為一個(gè)（merge feature）？
  （1）解決哪些特征應(yīng)該綁在一起
  將相互獨(dú)立的特征進(jìn)行綁定是一個(gè) NP-Hard 問(wèn)題，LightGBM的EFB算法將這個(gè)問(wèn)題轉(zhuǎn)化為圖著色的問(wèn)題來(lái)求解，將所有的特征視為圖的各個(gè)頂點(diǎn)，將不是相互獨(dú)立的特征用一條邊連接起來(lái)，邊的權(quán)重就是兩個(gè)相連接的特征的總沖突值，這樣需要綁定的特征就是在圖著色問(wèn)題中要涂上同一種顏色的那些點(diǎn)（特征）。此外，我們注意到通常有很多特征，盡管不是100％相互排斥，但也很少同時(shí)取非零值。 如果我們的算法可以允許一小部分的沖突，我們可以得到更少的特征包，進(jìn)一步提高計(jì)算效率。經(jīng)過(guò)簡(jiǎn)單的計(jì)算，隨機(jī)污染小部分特征值將影響精度最多$O([1?\gamma ]n)$ ， $\gamma$是每個(gè)綁定中的最大沖突比率，當(dāng)其相對(duì)較小時(shí)，能夠完成精度和效率之間的平衡。具體步驟可以總結(jié)如下：
  構(gòu)造一個(gè)加權(quán)無(wú)向圖，頂點(diǎn)是特征，邊有權(quán)重，其權(quán)重與兩個(gè)特征間沖突相關(guān)；
  根據(jù)節(jié)點(diǎn)的度進(jìn)行降序排序，度越大，與其它特征的沖突越大；
  遍歷每個(gè)特征，將它分配給現(xiàn)有特征包，或者新建一個(gè)特征包，使得總體沖突最小。
  算法允許兩兩特征并不完全互斥來(lái)增加特征捆綁的數(shù)量，通過(guò)設(shè)置最大沖突比率 [公式] 來(lái)平衡算法的精度和效率。
  算法3的時(shí)間復(fù)雜度是$O(featur{e}^2)$，訓(xùn)練之前只處理一次，其時(shí)間復(fù)雜度在特征不是特別多的情況下是可以接受的，但難以應(yīng)對(duì)百萬(wàn)維度的特征。為了繼續(xù)提高效率，LightGBM提出了一種更加高效的無(wú)圖的排序策略：將特征按照非零值個(gè)數(shù)排序，這和使用圖節(jié)點(diǎn)的度排序相似，因?yàn)楦嗟姆橇阒低ǔ?huì)導(dǎo)致沖突，新算法在算法3基礎(chǔ)上改變了排序策略。
  （2）解決怎么把特征綁為一捆
  特征合并算法，其關(guān)鍵在于原始特征能從合并的特征中分離出來(lái)。綁定幾個(gè)特征在同一個(gè)bundle里需要保證綁定前的原始特征的值可以在bundle中識(shí)別，考慮到histogram-based算法將連續(xù)的值保存為離散的bins，我們可以使得不同特征的值分到bundle中的不同bin（箱子）中，這可以通過(guò)在特征值中加一個(gè)偏置常量來(lái)解決。比如，我們?cè)赽undle中綁定了兩個(gè)特征A和B，A特征的原始取值為區(qū)間[0,10)，B特征的原始取值為區(qū)間[0,20），我們可以在B特征的取值上加一個(gè)偏置常量10，將其取值范圍變?yōu)閇10,30），綁定后的特征取值范圍為 [0, 30），這樣就可以放心的融合特征A和B了

優(yōu)點(diǎn)
（1）速度更快

• LightGBM 采用了直方圖算法將遍歷樣本轉(zhuǎn)變?yōu)楸闅v直方圖，極大的降低了時(shí)間復(fù)雜度；
• LightGBM 在訓(xùn)練過(guò)程中采用單邊梯度算法過(guò)濾掉梯度小的樣本，減少了大量的計(jì)算；
• LightGBM 采用了基于 Leaf-wise 算法的增長(zhǎng)策略構(gòu)建樹(shù)，減少了很多不必要的計(jì)算量；
• LightGBM 采用優(yōu)化后的特征并行、數(shù)據(jù)并行方法加速計(jì)算，當(dāng)數(shù)據(jù)量非常大的時(shí)候還可以采用投票并行的策略；
• LightGBM 對(duì)緩存也進(jìn)行了優(yōu)化，增加了緩存命中率；
  （2）內(nèi)存更小
• XGBoost使用預(yù)排序后需要記錄特征值及其對(duì)應(yīng)樣本的統(tǒng)計(jì)值的索引，而 LightGBM 使用了直方圖算法將特征值轉(zhuǎn)變?yōu)?bin 值，且不需要記錄特征到樣本的索引，將空間復(fù)雜度從 O(2*data) 降低為 O(bin)，極大的減少了內(nèi)存消耗；
• LightGBM 采用了直方圖算法將存儲(chǔ)特征值轉(zhuǎn)變?yōu)榇鎯?chǔ) bin 值，降低了內(nèi)存消耗；
• LightGBM 在訓(xùn)練過(guò)程中采用互斥特征捆綁算法減少了特征數(shù)量，降低了內(nèi)存消耗。

缺點(diǎn)

• 可能會(huì)長(zhǎng)出比較深的決策樹(shù)，產(chǎn)生過(guò)擬合。因此LightGBM在Leaf-wise之上增加了一個(gè)最大深度限制，在保證高效率的同時(shí)防止過(guò)擬合；
• Boosting族是迭代算法，每一次迭代都根據(jù)上一次迭代的預(yù)測(cè)結(jié)果對(duì)樣本進(jìn)行權(quán)重調(diào)整，所以隨著迭代不斷進(jìn)行，誤差會(huì)越來(lái)越小，模型的偏差（bias）會(huì)不斷降低。由于LightGBM是基于偏差的算法，所以會(huì)對(duì)噪點(diǎn)較為敏感；
• 在尋找最優(yōu)解時(shí)，依據(jù)的是最優(yōu)切分變量，沒(méi)有將最優(yōu)解是全部特征的綜合這一理念考慮進(jìn)去；

關(guān)于作者

總結(jié)

以上是生活随笔為你收集整理的集成算法总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。