1. foreword
TSA比賽中，開始整的LR，把原始特征one-hot處理后輸入LR訓(xùn)練。過了段時間開始搞RF和XGB，再后面搞LightGBM。
2. lightGBM簡介
xgboost的出現(xiàn)，讓數(shù)據(jù)民工們告別了傳統(tǒng)的機(jī)器學(xué)習(xí)算法們：RF、GBM、SVM、LASSO……..?，F(xiàn)在微軟推出了一個新的boosting框架，想要挑戰(zhàn)xgboost的江湖地位。
顧名思義，lightGBM包含兩個關(guān)鍵點(diǎn)：light即輕量級，GBM 梯度提升機(jī)。
LightGBM 是一個梯度 boosting 框架，使用基于學(xué)習(xí)算法的決策樹。它可以說是分布式的，高效的，有以下優(yōu)勢：
更快的訓(xùn)練效率
低內(nèi)存使用
更高的準(zhǔn)確率
支持并行化學(xué)習(xí)
可處理大規(guī)模數(shù)據(jù)
與常用的機(jī)器學(xué)習(xí)算法進(jìn)行比較：速度飛起
3. xgboost缺點(diǎn)
XGB的介紹見此篇博文
其缺點(diǎn)，或者說不足之處：
每輪迭代時，都需要遍歷整個訓(xùn)練數(shù)據(jù)多次。如果把整個訓(xùn)練數(shù)據(jù)裝進(jìn)內(nèi)存則會限制訓(xùn)練數(shù)據(jù)的大小；如果不裝進(jìn)內(nèi)存，反復(fù)地讀寫訓(xùn)練數(shù)據(jù)又會消耗非常大的時間。
預(yù)排序方法（pre-sorted）：首先，空間消耗大。這樣的算法需要保存數(shù)據(jù)的特征值，還保存了特征排序的結(jié)果（例如排序后的索引，為了后續(xù)快速的計(jì)算分割點(diǎn)），這里需要消耗訓(xùn)練數(shù)據(jù)兩倍的內(nèi)存。其次時間上也有較大的開銷，在遍歷每一個分割點(diǎn)的時候，都需要進(jìn)行分裂增益的計(jì)算，消耗的代價大。
對cache優(yōu)化不友好。在預(yù)排序后，特征對梯度的訪問是一種隨機(jī)訪問，并且不同的特征訪問的順序不一樣，無法對cache進(jìn)行優(yōu)化。同時，在每一層長樹的時候，需要隨機(jī)訪問一個行索引到葉子索引的數(shù)組，并且不同特征訪問的順序也不一樣，也會造成較大的cache miss。
4. lightGBM特點(diǎn)
以上與其說是xgboost的不足，倒不如說是lightGBM作者們構(gòu)建新算法時著重瞄準(zhǔn)的點(diǎn)。解決了什么問題，那么原來模型沒解決就成了原模型的缺點(diǎn)。
概括來說，lightGBM主要有以下特點(diǎn)：
基于Histogram的決策樹算法
帶深度限制的Leaf-wise的葉子生長策略
直方圖做差加速
直接支持類別特征(Categorical Feature)
Cache命中率優(yōu)化
基于直方圖的稀疏特征優(yōu)化
多線程優(yōu)化
前2個特點(diǎn)使我們尤為關(guān)注的。
Histogram算法
直方圖算法的基本思想：先把連續(xù)的浮點(diǎn)特征值離散化成k個整數(shù)，同時構(gòu)造一個寬度為k的直方圖。遍歷數(shù)據(jù)時，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計(jì)量，當(dāng)遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計(jì)量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點(diǎn)。
帶深度限制的Leaf-wise的葉子生長策略
Level-wise過一次數(shù)據(jù)可以同時分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，也好控制模型復(fù)雜度，不容易過擬合。但實(shí)際上Level-wise是一種低效算法，因?yàn)樗患訁^(qū)分的對待同一層的葉子，帶來了很多沒必要的開銷，因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂。
Leaf-wise則是一種更為高效的策略：每次從當(dāng)前所有葉子中，找到分裂增益最大的一個葉子，然后分裂，如此循環(huán)。因此同Level-wise相比，在分裂次數(shù)相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度。
Leaf-wise的缺點(diǎn)：可能會長出比較深的決策樹，產(chǎn)生過擬合。因此LightGBM在Leaf-wise之上增加了一個最大深度限制，在保證高效率的同時防止過擬合。
5. lightGBM調(diào)參
（1）num_leaves
LightGBM使用的是leaf-wise的算法，因此在調(diào)節(jié)樹的復(fù)雜程度時，使用的是num_leaves而不是max_depth。
大致?lián)Q算關(guān)系：num_leaves = 2^(max_depth)
（2）樣本分布非平衡數(shù)據(jù)集：可以param[‘is_unbalance’]=’true’
（3）Bagging參數(shù)：bagging_fraction+bagging_freq（必須同時設(shè)置）、feature_fraction
（4）min_data_in_leaf、min_sum_hessian_in_leaf
// 01. train set and test set
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)
// 02. parameters
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'
// 03. cv and train
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']))
// 04. test predict
ypred = estimators.predict(dtest[predictors])
參考資料
【1】比XGBOOST更快–LightGBM介紹
https://zhuanlan.zhihu.com/p/25308051
如何看待微軟新開源的LightGBM?
GBDT 雖然是個強(qiáng)力的模型，但卻有著一個致命的缺陷，不能用類似 mini batch 的方式來訓(xùn)練，需要對數(shù)據(jù)進(jìn)行無數(shù)次的遍歷。如果想要速度，就需要把數(shù)據(jù)都預(yù)加載在內(nèi)存中，但這樣數(shù)據(jù)就會受限于內(nèi)存的大?。蝗绻胍?xùn)練更多的數(shù)據(jù)，就要使用外存版本的決策樹算法。雖然外存算法也有較多優(yōu)化，SSD 也在普及，但在頻繁的 IO 下，速度還是比較慢的。
為了能讓 GBDT 高效地用上更多的數(shù)據(jù)，我們把思路轉(zhuǎn)向了分布式 GBDT， 然后就有了 LightGBM。設(shè)計(jì)的思路主要是兩點(diǎn)，1. 單個機(jī)器在不犧牲速度的情況下，盡可能多地用上更多的數(shù)據(jù)；2.
多機(jī)并行的時候，通信的代價盡可能地低，并且在計(jì)算上可以做到線性加速。
基于這兩個需求，LightGBM 選擇了基于 histogram 的決策樹算法。相比于另一個主流的算法 pre-sorted（如 xgboost 中的 exact 算法），histogram 在內(nèi)存消耗和計(jì)算代價上都有不少優(yōu)勢。
Pre-sorted 算法需要的內(nèi)存約是訓(xùn)練數(shù)據(jù)的兩倍(2 * #data * #features
* 4Bytes)，它需要用32位浮點(diǎn)來保存 feature value，并且對每一列特征，都需要一個額外的排好序的索引，這也需要32位的存儲空間。對于 histogram 算法，則只需要(#data
* #features * 1Bytes)的內(nèi)存消耗，僅為 pre-sorted算法的1/8。因?yàn)?histogram 算法僅需要存儲 feature
bin value (離散化后的數(shù)值)，不需要原始的 feature value，也不用排序，而 bin
value 用 uint8_t (256
bins) 的類型一般也就足夠了。
在計(jì)算上的優(yōu)勢則主要體現(xiàn)在“數(shù)據(jù)分割”。決策樹算法有兩個主要操作組成，一個是“尋找分割點(diǎn)”，另一個是“數(shù)據(jù)分割”。從算法時間復(fù)雜度來看，Histogram 算法和 pre-sorted 算法在“尋找分割點(diǎn)”的代價是一樣的，都是O(#feature*#data)。而在“數(shù)據(jù)分割”時，pre-sorted 算法需要O(#feature*#data)，而 histogram 算法是O(#data)。因?yàn)?pre-sorted 算法的每一列特征的順序都不一樣，分割的時候需要對每個特征單獨(dú)進(jìn)行一次分割。Histogram算法不需要排序，所有特征共享同一個索引表，分割的時候僅需對這個索引表操作一次就可以。（更新:這一點(diǎn)不完全正確，pre-sorted 與 level-wise 結(jié)合的時候，其實(shí)可以共用一個索引表(row_idx_to_tree_node_idx)。然后在尋找分割點(diǎn)的時候，同時操作同一層的節(jié)點(diǎn)，省去分割的步驟。但這樣做的問題是會有非常多隨機(jī)訪問，有很大的chche miss，速度依然很慢。）。
另一個計(jì)算上的優(yōu)勢則是大幅減少了計(jì)算分割點(diǎn)增益的次數(shù)。對于一個特征，pre-sorted 需要對每一個不同特征值都計(jì)算一次分割增益，而 histogram 只需要計(jì)算 #bin (histogram 的橫軸的數(shù)量) 次。
最后，在數(shù)據(jù)并行的時候，用 histgoram 可以大幅降低通信代價。用 pre-sorted 算法的話，通信代價是非常大的（幾乎是沒辦法用的）。所以 xgoobst 在并行的時候也使用 histogram 進(jìn)行通信。
當(dāng)然， histogram 算法也有缺點(diǎn)，它不能找到很精確的分割點(diǎn)，訓(xùn)練誤差沒有 pre-sorted 好。但從實(shí)驗(yàn)結(jié)果來看， histogram 算法在測試集的誤差和 pre-sorted 算法差異并不是很大，甚至有時候效果更好。實(shí)際上可能決策樹對于分割點(diǎn)的精確程度并不太敏感，而且較“粗”的分割點(diǎn)也自帶正則化的效果。
在 histogram 算法之上， LightGBM 進(jìn)行進(jìn)一步的優(yōu)化。首先它拋棄了大多數(shù) GBDT 工具使用的按層生長
(level-wise) 的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise) 算法。 level-wise 過一次數(shù)據(jù)可以同時分裂同一層的葉子，容易進(jìn)行多線程優(yōu)化，不容易過擬合。但實(shí)際上level-wise是一種低效的算法，因?yàn)樗患訁^(qū)分的對待同一層的葉子，帶來了很多沒必要的開銷。因?yàn)閷?shí)際上很多葉子的分裂增益較低，沒必要進(jìn)行搜索和分裂。leaf-wise則是一種更為高效的策略，每次從當(dāng)前所有葉子中，找到分裂增益最大(一般也是數(shù)據(jù)量最大)的一個葉子，然后分裂，如此循環(huán)。因此同 level-wise 相比，在分裂次數(shù)相同的情況下，leaf-wise 可以降低更多的誤差，得到更好的精度。leaf-wise 的缺點(diǎn)是可能會長出比較深的決策樹，產(chǎn)生過擬合。因此 LightGBM 在leaf-wise 之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。
另一個比較巧妙的優(yōu)化是 histogram 做差加速。一個容易觀察到的現(xiàn)象：一個葉子的直方圖可以由它的父親節(jié)點(diǎn)的直方圖與它兄弟的直方圖做差得到。通常構(gòu)造直方圖，需要遍歷該葉子上的所有數(shù)據(jù)，但直方圖做差僅需遍歷直方圖的 k 個桶。利用這個方法，LightGBM 可以在構(gòu)造一個葉子的直方圖后，可以用非常微小的代價得到它兄弟葉子的直方圖，在速度上可以提升一倍。
如需要更多的細(xì)節(jié)，可以參考github上的文檔：https://github.com/Microsoft/LightGBM/wiki/Features
