xgboost的出現(xiàn)，讓數(shù)據(jù)民工們告別了傳統(tǒng)的機器學習算法們：RF、GBM、SVM、LASSO........?，F(xiàn)在，微軟推出了一個新的boosting框架，想要挑戰(zhàn)xgboost的江湖地位。筆者嘗試了一下，下面請看來自第一線的報告。
包含以下幾個部分：
一. 基本介紹
二. ?XGBOOST原理及缺點
三. LightGBM的優(yōu)化
四. 建模過程（python）
五. 調(diào)參
一. 基本介紹
LightGBM 是一個梯度 boosting 框架，使用基于學習算法的決策樹。它可以說是分布式的，高效的，它有以下優(yōu)勢：
- 更快的訓練效率
- 低內(nèi)存使用
- 更好的準確率
- 支持并行學習
- 可處理大規(guī)模數(shù)據(jù)
與常用的機器學習算法進行比較：
· 速度飛起
二. ?XGBOOST原理及缺點
1. 原理
1 ) 有監(jiān)督學習
有監(jiān)督學習的目標函數(shù)是下面這個東東：
其中，第一項稱為誤差函數(shù)，常見的誤差函數(shù)有平方誤差，logistic誤差等等，第二項稱為正則項，常見的有L1正則和L2正則，神經(jīng)網(wǎng)絡里面的dropout等等
2）Boosted Tree
i）基學習器：分類樹和回歸樹（CART）
ii ) Tree Ensemble
一個CART往往過于簡單無法有效地預測，因此一個更加強力的模型叫做tree ensemble。
簡而言之，Boosted Tree 就是一種 Tree Ensemble的方法，和RF一樣，只是構(gòu)造（學習）模型參數(shù)的方法不同。
iii）模型學習：additive training
每一次保留原來的模型不變，加入一個新的函數(shù)f到我們的模型中。
f 的選擇標準---最小化目標函數(shù)！
通過二階泰勒展開，以及（中間省略N步），我們得到了最終的目標函數(shù)：
G、H：與數(shù)據(jù)點在誤差函數(shù)上的一階、二階導數(shù)有關，T：葉子的個數(shù)
iv ) 枚舉所有不同樹結(jié)構(gòu)的貪心算法
不斷地枚舉不同樹的結(jié)構(gòu)，根據(jù)目標函數(shù)來尋找出一個最優(yōu)結(jié)構(gòu)的樹，加入到我們的模型中，再重復這樣的操作。不過枚舉所有樹結(jié)構(gòu)這個操作不太可行，所以常用的方法是貪心法，每一次嘗試去對已有的葉子加入一個分割。對于一個具體的分割方案，我們可以獲得的增益可以由如下公式計算。
對于每次擴展，我們還是要枚舉所有可能的分割方案，如何高效地枚舉所有的分割呢？我假設我們要枚舉所有 x
我們可以發(fā)現(xiàn)對于所有的a，我們只要做一遍從左到右的掃描就可以枚舉出所有分割的梯度和GL和GR。然后用上面的公式計算每個分割方案的分數(shù)就可以了。
詳細的內(nèi)容可以看陳天奇大神的文章【3】
2. 缺點
--?在每一次迭代的時候，都需要遍歷整個訓練數(shù)據(jù)多次。如果把整個訓練數(shù)據(jù)裝進內(nèi)存則會限制訓練數(shù)據(jù)的大??；如果不裝進內(nèi)存，反復地讀寫訓練數(shù)據(jù)又會消耗非常大的時間。
-- 預排序方法（pre-sorted）：
首先，空間消耗大。這樣的算法需要保存數(shù)據(jù)的特征值，還保存了特征排序的結(jié)果（例如排序后的索引，為了后續(xù)快速的計算分割點），這里需要消耗訓練數(shù)據(jù)兩倍的內(nèi)存。
其次，時間上也有較大的開銷，在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。
最后，對cache優(yōu)化不友好。在預排序后，特征對梯度的訪問是一種隨機訪問，并且不同的特征訪問的順序不一樣，無法對cache進行優(yōu)化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數(shù)組，并且不同特征訪問的順序也不一樣，也會造成較大的cache miss。
三. LightGBM的優(yōu)化
基于Histogram的決策樹算法
帶深度限制的Leaf-wise的葉子生長策略
直方圖做差加速
直接支持類別特征(Categorical Feature)
Cache命中率優(yōu)化
基于直方圖的稀疏特征優(yōu)化
多線程優(yōu)化
下面主要介紹Histogram算法、帶深度限制的Leaf-wise的葉子生長策略。
>>>>
Histogram算法
直方圖算法的基本思想是先把連續(xù)的浮點特征值離散化成k個整數(shù)，同時構(gòu)造一個寬度為k的直方圖。在遍歷數(shù)據(jù)的時候，根據(jù)離散化后的值作為索引在直方圖中累積統(tǒng)計量，當遍歷一次數(shù)據(jù)后，直方圖累積了需要的統(tǒng)計量，然后根據(jù)直方圖的離散值，遍歷尋找最優(yōu)的分割點。
圖：直方圖算法
>>>>
帶深度限制的Leaf-wise的葉子生長策略
Level-wise過一次數(shù)據(jù)可以同時分裂同一層的葉子，容易進行多線程優(yōu)化，也好控制模型復雜度，不容易過擬合。但實際上Level-wise是一種低效的算法，因為它不加區(qū)分的對待同一層的葉子，帶來了很多沒必要的開銷，因為實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂。
Leaf-wise則是一種更為高效的策略，每次從當前所有葉子中，找到分裂增益最大的一個葉子，然后分裂，如此循環(huán)。因此同Level-wise相比，在分裂次數(shù)相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度。Leaf-wise的缺點是可能會長出比較深的決策樹，產(chǎn)生過擬合。因此LightGBM在Leaf-wise之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。
四. 建模過程（python）
數(shù)據(jù)導入
# 接受：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ù)
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. 預測
ypred = estimators.predict(dtest[predictors])
四. 實測效果
試了一下90W條記錄*130維的樣本，num_threads設置為40
時間：
2. 準確率：
五. 調(diào)參
1. 使用num_leaves
因為LightGBM使用的是leaf-wise的算法，因此在調(diào)節(jié)樹的復雜程度時，使用的是num_leaves而不是max_depth
大致?lián)Q算關系：num_leaves = 2^(max_depth)
2.對于非平衡數(shù)據(jù)集：可以param['is_unbalance']='true’
3. Bagging參數(shù)：bagging_fraction+bagging_freq（必須同時設置）、feature_fraction
4.?min_data_in_leaf、min_sum_hessian_in_leaf
參考文獻
https://github.com/Microsoft/LightGBM/
關于LightGBM： http://mp.weixin.qq.com/s?__biz=MzA3MzI4MjgzMw==&mid=2650719786&idx=3&sn=ab1c5a77237dc4b2ee5ae12c7a68ff87&chksm=871b0254b06c8b42d5a4fdf3327f7284c9ffbe72fe7911301d368b157024b32923d88401c2a8&scene=0&open_source=weibo_search
關于XGBOOST：http://www.52cs.org/?p=429
對數(shù)據(jù)感興趣的小伙伴，歡迎交流，微信公共號:一白侃數(shù)
