LightGBM详细
目錄
LightGBM
XGB的優缺點：
LightGBM原理
1.1 GBDT和 LightGBM對比
1.2 LightGBM 的動機
1.3 Xgboost 原理
1.4 LightGBM 優化
LightGBM算法原理：
直方圖算法（Histgram）
帶深度限制的Leaf-wise算法
單邊梯度采樣算法
互斥特征捆綁算法
LightGBM的優缺點：
速度：
內存：
LightGBM
GBDT是一個長久不衰的模型，他的思想是什么？
它的思想就是將多個弱分類器迭代訓練得到最優的模型，訓練效果好，不易過擬合等等的有點，那么XGB就是典型的一個GBDT的實現。
首先回顧一下XGB，它的核心思想就是說，是屬于GBDT的一個延申，因此它的模型也是加法模型，由多個弱分類器相加的結果，那么在構成弱分類器的時候，首先需要對特征值進行預排序，然后便利所有的切分點，然后計算每個切分點的一個增益，最后找到最優的分裂點進行數據分裂成左右子樹。
XGB的優缺點：
優點：
能夠最精確的找到切分點，因為把所有的樣本看一遍，都計算了一遍，肯定能找到最優的點。
缺點：
時間消耗比較大
LightGBM原理
1.1 GBDT和 LightGBM對比
? GBDT (Gradient Boosting Decision Tree) 是機器學習中一個長盛不衰的模型，其主要思想是利用弱分類器（決策樹）迭代訓練以得到最優模型，該模型具有訓練效果好、不易過擬合等優點。GBDT 在工業界應用廣泛，通常被用于點擊率預測，搜索排序等任務。GBDT 也是各種數據挖掘競賽的致命武器，據統計 Kaggle 上的比賽有一半以上的冠軍方案都是基于 GBDT。
? LightGBM （Light Gradient Boosting Machine）是一個實現 GBDT 算法的框架，支持高效率的并行訓練，并且具有以下優點：
更快的訓練速度
更低的內存消耗
更好的準確率
分布式支持，可以快速處理海量數據
? 如下圖，在 Higgs 數據集上 LightGBM 比 XGBoost 快將近 10 倍，內存占用率大約為 XGBoost 的1/6，并且準確率也有提升。
1.2 LightGBM 的動機
? 常用的機器學習算法，例如神經網絡等算法，都可以以 mini-batch 的方式訓練，訓練數據的大小不會受到內存限制。
? 而 GBDT 在每一次迭代的時候，都需要遍歷整個訓練數據多次。如果把整個訓練數據裝進內存則會限制訓練數據的大小；如果不裝進內存，反復地讀寫訓練數據又會消耗非常大的時間。尤其面對工業級海量的數據，普通的 GBDT 算法是不能滿足其需求的。
LightGBM 提出的主要原因就是為了解決 GBDT 在海量數據遇到的問題，讓 GBDT 可以更好更快地用于工業實踐。
1.3 Xgboost 原理
? 目前已有的 GBDT 工具基本都是基于預排序的方法（pre-sorted）的決策樹算法(如 xgboost)。這種構建決策樹的算法基本思想是：
首先，對所有特征都按照特征的數值進行預排序。
其次，在遍歷分割點的時候用O(#data)的代價找到一個特征上的最好分割點。
最后，找到一個特征的分割點后，將數據分裂成左右子節點。
這樣的預排序算法的優點是：能精確地找到分割點。
缺點也很明顯：
首先，空間消耗大。這樣的算法需要保存數據的特征值，還保存了特征排序的結果（例如排序后的索引，為了后續快速的計算分割點），這里需要消耗訓練數據兩倍的內存。
其次，時間上也有較大的開銷，在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。
最后，對 cache 優化不友好。在預排序后，特征對梯度的訪問是一種隨機訪問，并且不同的特征訪問的順序不一樣，無法對 cache 進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數組，并且不同特征訪問的順序也不一樣，也會造成較大的 cache miss。
1.4 LightGBM 優化
LightGBM 優化部分包含以下：
基于 Histogram 的決策樹算法
帶深度限制的 Leaf-wise 的葉子生長策略
直方圖做差加速
直接支持類別特征(Categorical Feature)
Cache 命中率優化
基于直方圖的稀疏特征優化
多線程優化。
? 下面主要介紹 Histogram 算法、帶深度限制的 Leaf-wise 的葉子生長策略和直方圖做差加速。
?
其實LightGBM也是一個實現GBDT算法的框架，
那么LightGBM的特點？
它支持高效的并行訓練，有著更快的訓練速度，更低的內存消耗，更好的準確率，支持分布式，可以快速的處理海量的數據。
LightGBM算法原理：
直方圖算法（Histgram）
思想：把連續的特征值離散化成K個整數，比如說0~1我們叫做1，1~2我們叫做3，。。。。。。等等，這樣然后在對特征值里邊的數據進行一個統計，這樣是不是就得到了一個直方圖，然后我們用直方圖所對應的值來進行增益的分裂，將大規模的數據更新為箱子的值。
那么這樣做的目的是什么？
對于直方圖來說最直接優點是什么？
內存占用小，因為不需要保存原來的特征了，只需要保存直方圖統計后的值，這個值一般情況下用8位的整型去儲存就夠了，但是在XGB中需要使用32位的浮點型儲存。
計算代價小，在XGB中計算分裂增益的時候需要遍歷每一個特征值然后計算一個增益，而在直方圖的算法中只需要計算K次，時間復雜度直接由原來的feature變成了現在的k而我們知道data>>k
當然我們說這種方法值最好的嘛？他有什么樣的缺點呢？
Histogram算法并不完美，由于特征被離散化后，找到的并不是一個準確的切分點，所以對結果會產生影響，但是我們發現到形成的最終的這個強學習器并不會差，有時候甚至更好，原因是什么？
原因就是說里邊的每個模型本來就是弱學習器，分割點不精確并不是特別的重要，比較粗糙的分割點真好還能起到正則化的作用，可以有效的防止過擬合，雖然每棵樹上的訓練誤差稍大，但是在總體的框架下并沒有什么太大的影響。
怎么做的差？
假如說我有x個數據，然后我是可是可以構建出來一個k個桶的直方圖，然后，我的左子節點上的數據由x1個數據，同樣是不是也可以得到一個k個桶的直方圖，那么我右子節點上是不是就有（x-x1）個樣本數據，是不是就可以通過x的直方圖減去x1的直方圖。
帶深度限制的Leaf-wise算法
XGB使用的是level-wise按層生長的策略，這種策略容易進行并行化處理，也好控制模型的復雜度，同時也可以防止過擬合，但是這種方式其實是很低效的，因為這種按層去分的話，每次構建其中的一層，但是實際上呢，速度是比較慢的，因為有的葉子節點的增益下降是比較慢的，也就是說在這一步沒有必要將這個節點繼續的進行劃分，但是卻以同樣的權重去關注同一層的每個葉子節點顯然是不合適的。去劃分它顯然是不合適的。
而LightGBM采用的是Leaf-wise的增長策略，就是說，每次都從所有的葉子節點中找出，增益最大的葉子節點去進行劃分，這樣的話是不是每次都可以下降最多的誤差，得到更好的精度，但是缺點呢就是，可能會長出一顆比較深的樹，然后導致了過擬合，但是LightGBM在Leaf-wise的基礎上加上了一個最大深度的限制，在保證高效的同時還防止了過擬合。
單邊梯度采樣算法
GOSS算法，這個算法的思想就是，從減少樣本的角度出發，排除大部分的小梯度的樣本，僅僅用剩下的樣本計算目標函數增益，它是一種在減少數據和保證精度上平衡的算法。
在GBDT中發現每個樣本都有相應的梯度值，梯度小的樣本，訓練誤差也小，說明該樣本已經很好的被模型給學習到了，直接想法就是丟掉這一部分數據，但是直接丟掉的話，就會影響到數據的分布，從而導致影響模型的精度，因此為了解決這個問題，提出了GOSS算法。GOSS是一個采樣的算法，目的是為了丟棄一些對計算信息增益沒有用的樣本，留下對計算有用的歐陽本，也說到了，梯度大的對計算增益是有幫助的，梯度小的樣本是沒有幫助的，但是在其中又不能直接的丟棄，那他是怎么做的？
首先它對于樣本的梯度進行一個排序，比如說我設定一個閾值0.5那么梯度大于0.5的樣本我全部留下，梯度小于0.5的我按照一定的比例去隨機的采樣，比如說我從里邊抽取了1/3的樣本。然后使用這樣的數據進行訓練。
互斥特征捆綁算法
數據通常都是高緯稀疏的數據，并且通常數據呢都是稀疏的，什么意思？比如說one-hot類型的數據，每一列都是0只有一個值是1，如果數據的維度太高的話會出現什么情況，模型復雜，計算繁瑣，時間復雜度高，如果將數據的維度進行壓縮一下，那么速度是不是也會由很大的提升，那么怎么去通過一種無損的壓縮來很好的減少特征的數量呢？我們發現，數據一般都是互斥的，什么是互斥的，就像one-hot中很多特征全是0，只有一個是1，那么也就是說只要我任意的兩個特征不同時為非0值，那么這兩個特征都是互斥的，我們就可以把特們綁到一起去組合成一個新的特征，但是實際中不存在完全互斥的數據吧，那么怎么辦，仍然是采用近似互斥的方法，也就是說，我們允許一些非互斥的存在，那么我們去衡量這個不互斥的情況就稱作為沖突比率，當這個比率比較小是，就可以將兩個特征進行捆綁，而不影響精度，那么怎么去衡量兩個特征之間能不能捆綁呢？
它有這個衡量公式，r是每個綁定中的最大沖突比率，當r相對較小是，完成它們速度和精度之間的一個平衡。
LightGBM的優缺點：
優點：
從內存和速度兩方面去考慮
速度：
LightGBM采用了直方圖算法將遍歷樣本轉變為遍歷直方圖，極大的降低了時間的復雜度；
LightGBM在訓練的過程當中采用了單邊梯度算法過濾掉了梯度比較小的樣本，減小了計算量
LightGBM采用了Leaf-wise算法的增長策略構建樹，減小了很多不必要的計算量
LightGBM采用了特征并行，數據并行的方法加速計算，當數據量非常大的時候還可以采用投票并行的策略
LightGBM對緩存也進行了優化，增加了緩存命中率
內存：
通過直方圖算法將原本的儲存特征值，轉變為了儲存箱子的值，降低了內存的消耗
在訓練過程當中，采用互斥特征捆綁算法，減少了特征數量，降低了內存的消耗
Lightgbm = xgboost + 直方圖（減小了內存儲存的消耗） + leaf wise（構建樹提升速度） + 單邊梯度下降（從減少數據量） + 互斥特征捆綁（從減少特征）
總結
以上是生活随笔為你收集整理的LightGBM详细的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 与音乐共缠绵
- 下一篇： 中国消费信贷行业市场供需与战略研究报告