六、集成學(xué)習(xí)五、集成學(xué)習(xí)（Boosting、三)

四、LightGBM

? ? LightGBM也是常用的GBDT工具包，速度快于XGBoost，精度也還可以，其設(shè)計(jì)理念為：

? ? -單個(gè)機(jī)器在不犧牲速度的情況下，盡可能使用上更多的數(shù)據(jù)

? ? -多機(jī)并行時(shí)，通信的代價(jià)盡可能的低，并且在計(jì)算上可以做到線性加速

所以其使用分布式的GBDT，選擇了基于直方圖的決策樹(shù)算法。

????LightGBM在很多方面會(huì)比XGBoost表現(xiàn)的更為優(yōu)秀。它有以下優(yōu)勢(shì)：

-更快的訓(xùn)練效率

-低內(nèi)存使用

-更高的準(zhǔn)確率

-支持并行化學(xué)習(xí)

-可處理大規(guī)模數(shù)據(jù)

-支持直接使用category特征

主要流程：

按直方圖查找最佳分割 FindBestSplitByHistogram

Input：Training data X，Current Model?T_{c-1}(X)

? ? ? ? ? ? First order gradient G，second order gradient H

For all Leaf p in?T_{c-1}(X): #

訓(xùn)練前將特征值轉(zhuǎn)換為bin

? ? For all f in X.Features:

??????????? #構(gòu)造直方圖construct histogram

??????????? H = new Histogram()

????????????For i in (0, num_of_row): #使用bin索引直方圖，不需要排序

????????????????????H[f.bins[i]].g += g_i;H[f.bins[i]].n+= 1

??????????????????? #從直方圖中找到最佳分割

??????????????????? For i in (0, len(H)): #遍歷bins

????????????????????????????S_L += H[i].g；n_L += H[i].n

????????????????????????????S_R = S_P-S_L;n_R=n_P-n_L

????????????????????????????\Delta loss = \frac{S_L^2}{n_L} + \frac{S_R^2}{n_R} -\frac{S_P^2}{n_P}

??????????????????????? if?\Delta loss > \Delta loss(p_m,f_m,v_m):

????????????????????????????????(p_m,f_m,v_m) = (p,f,H[i].value)


直方圖算法

回憶：XGBoost中的Exact greedy算法（貪心算法）：

? ? -對(duì)每個(gè)特征都按照特征值進(jìn)行排序

? ? -在每個(gè)排好序的特征都尋找最優(yōu)切分點(diǎn)

? ? -用最優(yōu)切分點(diǎn)進(jìn)行切分

優(yōu)點(diǎn)是比較精確，缺點(diǎn)是空間消耗比較大，時(shí)間開(kāi)銷大和對(duì)內(nèi)存不友好，使用直方圖算法進(jìn)行劃分點(diǎn)的查找可以克服這些缺點(diǎn)。

直方圖算法（Histogram algorithm）把連續(xù)的浮點(diǎn)特征值離散化為k個(gè)整數(shù)（也就是分桶bins的思想），比如[0，0.1）-->0，[0.1，0.3）-->1.并根據(jù)特征所在的bin對(duì)其進(jìn)行梯度累加和個(gè)數(shù)統(tǒng)計(jì)，然后根據(jù)直方圖，尋找最優(yōu)的切分點(diǎn)。

直方圖算法

如何分桶bins？數(shù)值型特征和類別特征采用的方法是不同的

-數(shù)值型特征：

? ? -對(duì)特征值去重后進(jìn)行排序（從大到?。?，并統(tǒng)計(jì)每個(gè)值的counts

? ? -取max_bin和distinct_value.size()中的較小值作為bins_num

? ? -計(jì)算bins中的平均樣本個(gè)數(shù)mean_bin_size，若某個(gè)distinct_value的count大于mean_bin_size，則該特征值作為bins的上界，小于該特征值的第一個(gè)distinct value作為下界；若某個(gè)distinct_value的count小于mean_bin_size，則要進(jìn)行累計(jì)后再分組

-類別特征：

? ? -首先對(duì)特征取值按出現(xiàn)的次序排序（大到?。?/p>

? ? -取前min（max_bin，distinct_values_int.size()）中的每個(gè)特征做第3步（忽略一些出現(xiàn)次數(shù)很少的特征取值）

? ? -用bin_2_categorical_（vector類型，記錄bin對(duì)應(yīng)的特征取值）和categorical_2_bin_（unordered_map類型，將特征取值到哪個(gè)bin和一一對(duì)應(yīng)起來(lái)），這樣就可以方便進(jìn)行兩者之間的轉(zhuǎn)換了。

如何構(gòu)建直方圖？

? ? 給定一個(gè)特征值，可以轉(zhuǎn)化為對(duì)于的bin了，就要構(gòu)建直方圖了，直方圖中累加了一階梯度和二階梯度，并統(tǒng)計(jì)了取值的個(gè)數(shù)。

for ( ; i < num_data ; ++i ){

??????? const VAL_T bin = data_[data_indices[i]];

??????? out[bin].sum_gradients += ordered_gradients[i];

????????out[bin].sum_hessians += ordered_hessians[i];

? ? ? ? ++out[bin].cnt;

}

注：直方圖作差（一個(gè)葉子節(jié)點(diǎn)的直方圖可以由它的父節(jié)點(diǎn)的直方圖與其兄弟節(jié)點(diǎn)的直方圖作差得到。使用這個(gè)方法，構(gòu)建完一個(gè)葉子節(jié)點(diǎn)的直方圖之后，就可以用較小的代價(jià)得到兄弟節(jié)點(diǎn)的直方圖，相當(dāng)于速度提升了一倍）

Histogram = Histogram(parent) - Histogram(brother)

尋找最優(yōu)切分點(diǎn)：

? ? -遍歷所有bin

? ? -以當(dāng)前的bin作為分割點(diǎn)，累加左邊的bins至當(dāng)前的bin梯度和S_L及樣本數(shù)量n_L，并利用直方圖作差求得右邊的梯度和樣本數(shù)量

? ? -代入公式計(jì)算增益loss

? ? -在遍歷過(guò)程中取得最大的增益，以此時(shí)的特征和bin的特征值作為分裂節(jié)點(diǎn)的特征及取值。

for i in (0 , len(H)):

????????S_L += H[i].g ; n_L +=H[i].n

????????S_R =S_P - S_L ; n_R =n_P-n_L

????????\Delta loss = \frac{S_L^2}{n_L} + \frac{S_R^2}{n_R} - \frac{S_P^2} {n_P}

? ? ? ? if?\Delta loss > \Delta loss(p_m,f_m,v_m):

????????????????(p_m,f_m,v_m) = (p,f,H[i].value)

直方圖算法的優(yōu)點(diǎn)：

? ? -減少內(nèi)存占用

? ? -緩存命中率提高，直方圖中梯度存放是連續(xù)的

? ? -計(jì)算效率提高，相對(duì)于XGBoost中預(yù)排序每個(gè)特征都要遍歷數(shù)據(jù)，復(fù)雜度為O(#feature * #data)，而直方圖算法只需要遍歷每個(gè)特征的直方圖即可，復(fù)雜度為O(#feature * #bins),

? ? -在進(jìn)行數(shù)據(jù)并行時(shí)，可大幅度降低通信代價(jià)



直方圖算法改進(jìn)

? ? 直方圖算法仍有優(yōu)化的空間，建立直方圖的復(fù)雜度為O(#feature * #data)，如果能降低特征數(shù)或者降低樣本數(shù)，訓(xùn)練的時(shí)間會(huì)大大減少。假如特征存在冗余時(shí)，可以使用PCA等算法進(jìn)行降維，但特征通常是精心設(shè)計(jì)的，去除它們中的任何一個(gè)都可能會(huì)影響訓(xùn)練精度。所以在LightGBM中有GOSS算法和EFB算法

GOSS算法

? ? 樣本的梯度越小，樣本的訓(xùn)練誤差越小，表示樣本已經(jīng)訓(xùn)練的很好，直接的做法是丟掉這部分樣本，然而直接丟掉會(huì)影響輸數(shù)據(jù)的分布，因此在LightGBM中采用了one-side采樣方式來(lái)適配：GOSS（Gradient-based One-Side Sampling）采樣策略，它保留所有的大梯度樣本，對(duì)小梯度樣本進(jìn)行隨機(jī)采樣。


原始直方圖算法下，在第j個(gè)特征，值為d處進(jìn)行分裂帶來(lái)的增益可以定義為：

V_{j|O}(d) = \frac{1}{n_O}( \frac{(\sum\nolimits_{x_i \in O;x_{ij}\leq d}g_i)^2 } {n_{l|O}^j(d)} + \frac{(\sum\nolimits_{x_i \in O;x_{ij} >d}g_i)^2 } {n_{r|O}^j(d)} )

其中O為在決策樹(shù)待分裂節(jié)點(diǎn)的訓(xùn)練集，n_O = \sum I(x_i \in O)

n_{l|O}^j(d) = \sum I[x_i \in O : x_{ij} \leq d]并且n_{r|O}^j(d) = \sum I[x_i \in O : x_{ij} >d]

采用GOSS之后，在第j個(gè)特征，值為d處進(jìn)行分裂帶來(lái)的增益可以定義為：

V_{j|O}(d) = \frac{1}{n_O}( \frac{(\sum\nolimits_{x_i \in A_l } g_i + \frac {1-a} \sum\nolimits_{x_i \in B_l}g_i)^2 } {n_{l|O}^j(d)} + \frac{(\sum\nolimits_{x_i \in A_r} g_i + \frac {1-a} \sum\nolimits_{x_i \in B_l} g_r )^2 } {n_{r|O}^j(d)} )

其中A_l = x_i \in A : x_{ij} \leq d,A_r = x_i \in A: x_{ij} > d，B_l = x_i \in B: x_{ij} \leq d,B_r = x_i \in B: x_{ij} > d

（A表示大梯度樣本集，B表示小梯度樣本中隨機(jī)采樣的結(jié)果）

EFB算法

? ? 高維數(shù)據(jù)通常是稀疏的，而且許多特征是互斥的（即兩個(gè)或多個(gè)特征列不會(huì)同時(shí)為非0），LightGBM根據(jù)這一特點(diǎn)提出了EFB（exclusive feature bundling）算法將互斥特征進(jìn)行合并，能夠合并的特征為一個(gè)#bundle，從而將特征的維度降下來(lái)，相應(yīng)的，構(gòu)建histogram所耗費(fèi)的時(shí)間復(fù)雜度也從O(#data * #feature)變?yōu)镺(#data * #bundle)，其中#feature >> #bundle。實(shí)現(xiàn)起來(lái)的難點(diǎn)：

-哪些特征可以合并為一個(gè)bundle？ ?? ——Greedy bundle

-如何將特征合并為bundle，實(shí)現(xiàn)降維？ ? ? ——Merge Exclusive Features

Greedy bundle的原理與圖著色相同，給定一個(gè)圖G，定點(diǎn)為V，表示特征，邊為E，表示特征之間的互斥關(guān)系，接著采用貪心算法對(duì)圖進(jìn)行著色，以此來(lái)生成bundle。


searchOrder<-G.sortByDegree()對(duì)特征按度降序排序

for j循環(huán)，遍歷特征，將其劃分到?jīng)_突較小的bundle中，若沒(méi)有，則新建bundle

? ? 該算法復(fù)雜度為O(#feature ^ 2)，當(dāng)特征數(shù)很大時(shí)，效率不高，這時(shí)可以不建立圖，采用特征中非零值的個(gè)數(shù)作為排序的值，因?yàn)榉橇阒翟蕉鄾_突也就越大。

MEF（Merge Exclusive Features）將bundle中的特征合并為新的特征，合并的關(guān)鍵是原有的不同特征值在構(gòu)建后的bundle中仍然能夠識(shí)別。由于基于histogram的方法存儲(chǔ)的是離散的bin而不是連續(xù)的數(shù)值，因此可以通過(guò)添加偏移的方法將不同特征的bin值設(shè)定為不同的區(qū)間。


https://papers.nips.cc/paper/6907-lightgbm-a-highly-efficient-gradient-boosting-decision-tree.pdf? ——原論文

樹(shù)的生長(zhǎng)策略

? ? 在XGBoost中，樹(shù)是按層生長(zhǎng)的，同一層的所有節(jié)點(diǎn)都做分裂，最后剪枝，它不加區(qū)分的對(duì)待同一層的葉子，帶來(lái)了很多沒(méi)必要的開(kāi)銷，因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒(méi)必要進(jìn)行搜索和分裂。


? ? LightGBM的生長(zhǎng)策略是leaf-wise，以降低模型損失最大化為目的，對(duì)當(dāng)前所有葉子節(jié)點(diǎn)中切分增益最大的leaf節(jié)點(diǎn)進(jìn)行切分。leaf-wise的缺點(diǎn)是會(huì)生成比較深的決策樹(shù)，為了防止過(guò)擬合，可以在模型參數(shù)中設(shè)置決策樹(shù)的深度。




系統(tǒng)設(shè)計(jì)

? ? 主要介紹LightGBM中的并行計(jì)算優(yōu)化方法，在此，工作的節(jié)點(diǎn)稱為worker，LightGBM具有支持高效并行的特點(diǎn)，原生支持并行學(xué)習(xí)，目前支持：

? ? -特征并行

? ? -數(shù)據(jù)并行

? ? -Voting并行（數(shù)據(jù)并行的一種）

特征并行

? ? 特征并行是并行化決策樹(shù)中尋找最優(yōu)劃分點(diǎn)的過(guò)程。特征并行是將對(duì)特征進(jìn)行劃分，每個(gè)worker找到局部的最佳切分點(diǎn)，針對(duì)點(diǎn)對(duì)點(diǎn)通信找到全局的最佳切分點(diǎn)。


傳統(tǒng)算法：

? ? 不同的worker存儲(chǔ)不同的特征集，在找到全局的最佳劃分點(diǎn)后，具有該劃分點(diǎn)的worker進(jìn)行節(jié)點(diǎn)分裂，然后廣播切分后的左右子樹(shù)數(shù)據(jù)結(jié)果，其他worker收到結(jié)果后也進(jìn)行劃分。

LightGBM中算法：

? ? 每個(gè)worker中保存了所有的特征集，在找到全局的最佳劃分點(diǎn)后每個(gè)worker可自行進(jìn)行劃分，不再進(jìn)行廣播劃分結(jié)果，減小了網(wǎng)絡(luò)的通信量。但存儲(chǔ)代價(jià)變高。

數(shù)據(jù)并行

? ? 數(shù)據(jù)并行的目標(biāo)是并行化整個(gè)決策學(xué)習(xí)的過(guò)程。每個(gè)worker中擁有部分?jǐn)?shù)據(jù)，獨(dú)立的構(gòu)建局部直方圖，合并后得到全局直方圖，在全局直方圖中尋找最優(yōu)切分點(diǎn)進(jìn)行分裂。


Voting Parallel

? ? LightGBM采用一種稱為PV-Tree的算法進(jìn)行投票并行，其實(shí)這本質(zhì)上也是一種數(shù)據(jù)并行。PV-Tree和普通的決策樹(shù)差不多，只是在尋找最優(yōu)切分點(diǎn)上有所不同。


????每個(gè)worker擁有部分?jǐn)?shù)據(jù)，獨(dú)自構(gòu)建直方圖并找到top-k最優(yōu)的劃分特征，中心worker聚合得到最優(yōu)的2K個(gè)全局劃分特征，再向每個(gè)worker收集top-2k特征的直方圖，并且合并得到最優(yōu)劃分，廣播給所有worker進(jìn)行本地劃分。

實(shí)踐：

? ? 使用XGBoost設(shè)置樹(shù)的深度，在lightGBM中是葉子節(jié)點(diǎn)的個(gè)數(shù)

num_leaves = 2^(max_depth)



代碼：

import lightgbmas lgb

from sklearn.datasetsimport load_breast_cancer

from sklearn.model_selectionimport train_test_split

from sklearn.metricsimport accuracy_score

import matplotlib.pyplotas plt

# 加載數(shù)據(jù)集

breast = load_breast_cancer()

# 獲取特征值和目標(biāo)值

x,y = breast.data,breast.target

# 獲取特征名稱

feature_name = breast.feature_names

# 數(shù)據(jù)集劃分

x_train,x_test,y_train,y_test = train_test_split(x,y,test_size=0.2,random_state=0)

# 數(shù)據(jù)格式轉(zhuǎn)換

lgb_train = lgb.Dataset(x_train,y_train)

lgb_eval = lgb.Dataset(x_test,y_test,reference=lgb_train)

# 參數(shù)設(shè)置

boost_round =50#迭代次數(shù)

early_stop_rounds =10#驗(yàn)證數(shù)據(jù)在early_stop_rounds輪中未提高，則提前停止

params = {

'boosting_type':'gbdt',#設(shè)置提mu'bia'han'shu升類型

? ? 'objective':'regression',#目標(biāo)函數(shù)

? ? 'metric':{'12','auc'},#評(píng)估函數(shù)

? ? 'num_leaves':31,#葉子節(jié)點(diǎn)數(shù)

? ? 'learning_rate':0.05,#學(xué)習(xí)速率

? ? 'feature_fraction':0.9,#建樹(shù)的特征選擇比例

? ? 'bagging_fraction':0.8,#建樹(shù)的樣本采集比例

? ? 'bagging_freq':5,#k意味著每k次迭代執(zhí)行bagging

? ? 'verbose':1#<0,顯示致命的，=0顯示錯(cuò)誤（警告），>0顯示信息

}

# 訓(xùn)練模型，加入提前停止的功能

results = {}

gbm = lgb.train(

params,

lgb_train,

num_boost_round=boost_round,

valid_sets=(lgb_eval,lgb_train),

valid_names=('validate','train'),

early_stopping_rounds=early_stop_rounds,

evals_result=results

)

# 模型預(yù)測(cè)

y_pred = gbm.predict(x_test,num_iteration=gbm.best_iteration)

print(y_pred)

lgb.plot_metric(results)

plt.show()

# 繪制重要的特征

lgb.plot_importance(gbm,importance_type='split')

plt.show()

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容