xgboost的出現(xiàn)，讓數(shù)據(jù)民工們告別了傳統(tǒng)的機(jī)器學(xué)習(xí)算法們：RF、GBM、SVM、LASSO........?，F(xiàn)在，微軟推出了一個(gè)新的boosting框架，想要挑戰(zhàn)xgboost的江湖地位。筆者嘗試了一下，下面請(qǐng)看來自第一線的報(bào)告。

包含以下幾個(gè)部分：

一. 基本介紹

二. ?XGBOOST原理及缺點(diǎn)

三. LightGBM的優(yōu)化

四. 建模過程（python）

五. 調(diào)參

一. 基本介紹

LightGBM 是一個(gè)梯度 boosting 框架，使用基于學(xué)習(xí)算法的決策樹。它可以說是分布式的，高效的，它有以下優(yōu)勢(shì)：

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

- 低內(nèi)存使用

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

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

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

與常用的機(jī)器學(xué)習(xí)算法進(jìn)行比較：

· 速度飛起

二. ?XGBOOST原理及缺點(diǎn)

1. 原理

1 ) 有監(jiān)督學(xué)習(xí)

有監(jiān)督學(xué)習(xí)的目標(biāo)函數(shù)是下面這個(gè)東東：

其中，第一項(xiàng)稱為誤差函數(shù)，常見的誤差函數(shù)有平方誤差，logistic誤差等等，第二項(xiàng)稱為正則項(xiàng)，常見的有L1正則和L2正則，神經(jīng)網(wǎng)絡(luò)里面的dropout等等

2）Boosted Tree

i）基學(xué)習(xí)器：分類樹和回歸樹（CART）

ii ) Tree Ensemble

一個(gè)CART往往過于簡(jiǎn)單無法有效地預(yù)測(cè)，因此一個(gè)更加強(qiáng)力的模型叫做tree ensemble。

簡(jiǎn)而言之，Boosted Tree 就是一種 Tree Ensemble的方法，和RF一樣，只是構(gòu)造（學(xué)習(xí)）模型參數(shù)的方法不同。

iii）模型學(xué)習(xí)：additive training

每一次保留原來的模型不變，加入一個(gè)新的函數(shù)f到我們的模型中。

f 的選擇標(biāo)準(zhǔn)---最小化目標(biāo)函數(shù)！

通過二階泰勒展開，以及（中間省略N步），我們得到了最終的目標(biāo)函數(shù)：

G、H：與數(shù)據(jù)點(diǎn)在誤差函數(shù)上的一階、二階導(dǎo)數(shù)有關(guān)，T：葉子的個(gè)數(shù)

iv ) 枚舉所有不同樹結(jié)構(gòu)的貪心算法

不斷地枚舉不同樹的結(jié)構(gòu)，根據(jù)目標(biāo)函數(shù)來尋找出一個(gè)最優(yōu)結(jié)構(gòu)的樹，加入到我們的模型中，再重復(fù)這樣的操作。不過枚舉所有樹結(jié)構(gòu)這個(gè)操作不太可行，所以常用的方法是貪心法，每一次嘗試去對(duì)已有的葉子加入一個(gè)分割。對(duì)于一個(gè)具體的分割方案，我們可以獲得的增益可以由如下公式計(jì)算。

對(duì)于每次擴(kuò)展，我們還是要枚舉所有可能的分割方案，如何高效地枚舉所有的分割呢？我假設(shè)我們要枚舉所有 x

我們可以發(fā)現(xiàn)對(duì)于所有的a，我們只要做一遍從左到右的掃描就可以枚舉出所有分割的梯度和GL和GR。然后用上面的公式計(jì)算每個(gè)分割方案的分?jǐn)?shù)就可以了。

詳細(xì)的內(nèi)容可以看陳天奇大神的文章【3】

2. 缺點(diǎn)

--?在每一次迭代的時(shí)候，都需要遍歷整個(gè)訓(xùn)練數(shù)據(jù)多次。如果把整個(gè)訓(xùn)練數(shù)據(jù)裝進(jìn)內(nèi)存則會(huì)限制訓(xùn)練數(shù)據(jù)的大小；如果不裝進(jìn)內(nèi)存，反復(fù)地讀寫訓(xùn)練數(shù)據(jù)又會(huì)消耗非常大的時(shí)間。

-- 預(yù)排序方法（pre-sorted）：

首先，空間消耗大。這樣的算法需要保存數(shù)據(jù)的特征值，還保存了特征排序的結(jié)果（例如排序后的索引，為了后續(xù)快速的計(jì)算分割點(diǎn)），這里需要消耗訓(xùn)練數(shù)據(jù)兩倍的內(nèi)存。

其次，時(shí)間上也有較大的開銷，在遍歷每一個(gè)分割點(diǎn)的時(shí)候，都需要進(jìn)行分裂增益的計(jì)算，消耗的代價(jià)大。

最后，對(duì)cache優(yōu)化不友好。在預(yù)排序后，特征對(duì)梯度的訪問是一種隨機(jī)訪問，并且不同的特征訪問的順序不一樣，無法對(duì)cache進(jìn)行優(yōu)化。同時(shí)，在每一層長(zhǎng)樹的時(shí)候，需要隨機(jī)訪問一個(gè)行索引到葉子索引的數(shù)組，并且不同特征訪問的順序也不一樣，也會(huì)造成較大的cache miss。

三. LightGBM的優(yōu)化

基于Histogram的決策樹算法

帶深度限制的Leaf-wise的葉子生長(zhǎng)策略

直方圖做差加速

直接支持類別特征(Categorical Feature)

Cache命中率優(yōu)化

基于直方圖的稀疏特征優(yōu)化

多線程優(yōu)化

下面主要介紹Histogram算法、帶深度限制的Leaf-wise的葉子生長(zhǎng)策略。

>>>>

Histogram算法

直方圖算法的基本思想是先把連續(xù)的浮點(diǎn)特征值離散化成k個(gè)整數(shù)，同時(shí)構(gòu)造一個(gè)寬度為k的直方圖。在遍歷數(shù)據(jù)的時(shí)候，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。

圖：直方圖算法

>>>>

帶深度限制的Leaf-wise的葉子生長(zhǎng)策略

Level-wise過一次數(shù)據(jù)可以同時(shí)分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，也好控制模型復(fù)雜度，不容易過擬合。但實(shí)際上Level-wise是一種低效的算法，因?yàn)樗患訁^(qū)分的對(duì)待同一層的葉子，帶來了很多沒必要的開銷，因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂。

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

四. 建模過程（python）

數(shù)據(jù)導(dǎo)入

# 接受：libsvm/tsv/csv 、Numpy 2D array、pandas object（dataframe）、LightGBM binary file

# 需要指定 feature names and categorical features

train_data = lgb.Dataset(dtrain[predictors],label=dtrain[target],feature_name=list(dtrain[predictors].columns), categorical_feature=dummies)

test_data = lgb.Dataset(dtest[predictors],label=dtest[target],feature_name=list(dtest[predictors].columns), categorical_feature=dummies)

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

param = {'max_depth':6,'num_leaves':64,'learning_rate':0.03,'scale_pos_weight':1,'num_threads':40,'objective':'binary','bagging_fraction':0.7,'bagging_freq':1,'min_sum_hessian_in_leaf':100}

param['is_unbalance']='true'

param['metric'] = 'auc'

3. CV

bst=lgb.cv(param,train_data,num_boost_round=1000,nfold=3,early_stopping_rounds=30)

estimators = lgb.train(param,train_data,num_boost_round=len(bst['auc-mean']))

4. 預(yù)測(cè)

ypred = estimators.predict(dtest[predictors])

四. 實(shí)測(cè)效果

試了一下90W條記錄*130維的樣本，num_threads設(shè)置為40

時(shí)間：

2. 準(zhǔn)確率：

五. 調(diào)參

1. 使用num_leaves

因?yàn)長(zhǎng)ightGBM使用的是leaf-wise的算法，因此在調(diào)節(jié)樹的復(fù)雜程度時(shí)，使用的是num_leaves而不是max_depth

大致?lián)Q算關(guān)系：num_leaves = 2^(max_depth)

2.對(duì)于非平衡數(shù)據(jù)集：可以param['is_unbalance']='true’

3. Bagging參數(shù)：bagging_fraction+bagging_freq（必須同時(shí)設(shè)置）、feature_fraction

4.?min_data_in_leaf、min_sum_hessian_in_leaf

參考文獻(xiàn)

https://github.com/Microsoft/LightGBM/

關(guān)于LightGBM： http://mp.weixin.qq.com/s?__biz=MzA3MzI4MjgzMw==&mid=2650719786&idx=3&sn=ab1c5a77237dc4b2ee5ae12c7a68ff87&chksm=871b0254b06c8b42d5a4fdf3327f7284c9ffbe72fe7911301d368b157024b32923d88401c2a8&scene=0&open_source=weibo_search

關(guān)于XGBOOST：http://www.52cs.org/?p=429

對(duì)數(shù)據(jù)感興趣的小伙伴，歡迎交流，微信公共號(hào):一白侃數(shù)