終於有人把XGBoost 和 LightGBM 講明白了，項目中最主流的集成演算法！

2019 年 11 月 7 日
筆記

本文是決策樹的第三篇，主要介紹基於 Boosting 框架的主流集成演算法，包括 XGBoost 和 LightGBM。

送上完整的思維導圖：

XGBoost

XGBoost 是大規模並行 boosting tree 的工具，它是目前最快最好的開源 boosting tree 工具包，比常見的工具包快 10 倍以上。Xgboost 和 GBDT 兩者都是 boosting 方法，除了工程實現、解決問題上的一些差異外，最大的不同就是目標函數的定義。故本文將從數學原理和工程實現上進行介紹，並在最後介紹下 Xgboost 的優點。

1.1 數學原理

1.1.1 目標函數

我們知道 XGBoost 是由 k 個基模型組成的一個加法運算式：

其中為第 k 個基模型，為第 i 個樣本的預測值。

損失函數可由預測值與真實值進行表示：

其中 n 為樣本數量。

我們知道模型的預測精度由模型的偏差和方差共同決定，損失函數代表了模型的偏差，想要方差小則需要簡單的模型，所以目標函數由模型的損失函數 L 與抑制模型複雜度的正則項組成，所以我們有：

為模型的正則項，由於 XGBoost 支援決策樹也支援線性模型，所以這裡不再展開描述。

我們知道 boosting 模型是前向加法，以第 t 步的模型為例，模型對第 i 個樣本的預測為：

其中由第 t-1 步的模型給出的預測值，是已知常數，是我們這次需要加入的新模型的預測值，此時，目標函數就可以寫成：

求此時最優化目標函數，就相當於求解。

泰勒公式是將一個在處具有 n 階導數的函數 f(x) 利用關於的 n 次多項式來逼近函數的方法，若函數 f(x) 在包含的某個閉區間上具有 n 階導數，且在開區間 (a,b) 上具有 n+1 階導數，則對閉區間上任意一點 x 有其中的多項式稱為函數在處的泰勒展開式，是泰勒公式的余項且是的高階無窮小。

根據泰勒公式我們把函數在點 x 處進行泰勒的二階展開，可得到如下等式：

我們把視為，視為，故可以將目標函數寫為：

其中為損失函數的一階導，為損失函數的二階導，注意這裡的求導是對求導。

我們以平方損失函數為例：

則：

由於在第 t 步時其實是一個已知的值，所以是一個常數，其對函數的優化不會產生影響，因此目標函數可以寫成：

所以我們只需要求出每一步損失函數的一階導和二階導的值（由於前一步的是已知的，所以這兩個值就是常數），然後最優化目標函數，就可以得到每一步的 f(x) ，最後根據加法模型得到一個整體模型。

1.1.2 基於決策樹的目標函數

我們知道 Xgboost 的基模型不僅支援決策樹，還支援線性模型，這裡我們主要介紹基於決策樹的目標函數。

我們可以將決策樹定義為，x 為某一樣本，這裡的 q(x) 代表了該樣本在哪個葉子結點上，而 w_q 則代表了葉子結點取值 w ，所以就代表了每個樣本的取值 w （即預測值）。

決策樹的複雜度可由葉子數 T 組成，葉子節點越少模型越簡單，此外葉子節點也不應該含有過高的權重 w （類比 LR 的每個變數的權重），所以目標函數的正則項可以定義為：

即決策樹模型的複雜度由生成的所有決策樹的葉子節點數量，和所有節點權重所組成的向量的範式共同決定。

這張圖給出了基於決策樹的 XGBoost 的正則項的求解方式。

我們設為第 j 個葉子節點的樣本集合，故我們的目標函數可以寫成：

第二步到第三步可能看的不是特別明白，這邊做些解釋：第二步是遍歷所有的樣本後求每個樣本的損失函數，但樣本最終會落在葉子節點上，所以我們也可以遍歷葉子節點，然後獲取葉子節點上的樣本集合，最後在求損失函數。即我們之前樣本的集合，現在都改寫成葉子結點的集合，由於一個葉子結點有多個樣本存在，因此才有了和這兩項，為第 j 個葉子節點取值。

為簡化表達式，我們定義，則目標函數為：

這裡我們要注意和是前 t-1 步得到的結果，其值已知可視為常數，只有最後一棵樹的葉子節點不確定，那麼將目標函數對求一階導，並令其等於 0 ，則可以求得葉子結點 j 對應的權值：

所以目標函數可以化簡為：

上圖給出目標函數計算的例子，求每個節點每個樣本的一階導數和二階導數，然後針對每個節點對所含樣本求和得到的和，最後遍歷決策樹的節點即可得到目標函數。

1.1.3 最優切分點劃分演算法

在決策樹的生長過程中，一個非常關鍵的問題是如何找到葉子的節點的最優切分點，Xgboost 支援兩種分裂節點的方法——貪心演算法和近似演算法。

1）貪心演算法

從深度為 0 的樹開始，對每個葉節點枚舉所有的可用特徵；
針對每個特徵，把屬於該節點的訓練樣本根據該特徵值進行升序排列，通過線性掃描的方式來決定該特徵的最佳分裂點，並記錄該特徵的分裂收益；
選擇收益最大的特徵作為分裂特徵，用該特徵的最佳分裂點作為分裂位置，在該節點上分裂出左右兩個新的葉節點，並為每個新節點關聯對應的樣本集
回到第 1 步，遞歸執行到滿足特定條件為止

那麼如何計算每個特徵的分裂收益呢？

假設我們在某一節點完成特徵分裂，則分列前的目標函數可以寫為：

分裂後的目標函數為：

則對於目標函數來說，分裂後的收益為：

注意該特徵收益也可作為特徵重要性輸出的重要依據。

對於每次分裂，我們都需要枚舉所有特徵可能的分割方案，如何高效地枚舉所有的分割呢？

我假設我們要枚舉所有 x < a 這樣的條件，對於某個特定的分割點 a 我們要計算 a 左邊和右邊的導數和。

我們可以發現對於所有的分裂點 a，我們只要做一遍從左到右的掃描就可以枚舉出所有分割的梯度和和。然後用上面的公式計算每個分割方案的分數就可以了。

2）近似演算法

貪婪演算法可以的到最優解，但當數據量太大時則無法讀入記憶體進行計算，近似演算法主要針對貪婪演算法這一缺點給出了近似最優解。

對於每個特徵，只考察分位點可以減少計算複雜度。

該演算法會首先根據特徵分布的分位數提出候選劃分點，然後將連續型特徵映射到由這些候選點劃分的桶中，然後聚合統計資訊找到所有區間的最佳分裂點。

在提出候選切分點時有兩種策略：

Global：學習每棵樹前就提出候選切分點，並在每次分裂時都採用這種分割；
Local：每次分裂前將重新提出候選切分點。

直觀上來看，Local 策略需要更多的計算步驟，而 Global 策略因為節點沒有劃分所以需要更多的候選點。

下圖給出不同種分裂策略的 AUC 變換曲線，橫坐標為迭代次數，縱坐標為測試集 AUC，eps 為近似演算法的精度，其倒數為桶的數量。

我們可以看到 Global 策略在候選點數多時（eps 小）可以和 Local 策略在候選點少時（eps 大）具有相似的精度。此外我們還發現，在 eps 取值合理的情況下，分位數策略可以獲得與貪婪演算法相同的精度。

第一個 for 循環：對特徵 k 根據該特徵分布的分位數找到切割點的候選集合。XGBoost 支援 Global 策略和 Local 策略。
第二個 for 循環：針對每個特徵的候選集合，將樣本映射到由該特徵對應的候選點集構成的分桶區間中，即，對每個桶統計 G,H 值，最後在這些統計量上尋找最佳分裂點。

下圖給出近似演算法的具體例子，以三分位為例：

根據樣本特徵進行排序，然後基於分位數進行劃分，並統計三個桶內的 G,H 值，最終求解節點劃分的增益。

1.1.4 加權分位數縮略圖

事實上， XGBoost 不是簡單地按照樣本個數進行分位，而是以二階導數值作為樣本的權重進行劃分，如下：

那麼問題來了：為什麼要用進行樣本加權？

我們知道模型的目標函數為：

我們稍作整理，便可以看出有對 loss 加權的作用。

其中與 C 皆為常數。我們可以看到 h_i 就是平方損失函數中樣本的權重。

對於樣本權值相同的數據集來說，找到候選分位點已經有了解決方案（GK 演算法），但是當樣本權值不一樣時，該如何找到候選分位點呢？（作者給出了一個 Weighted Quantile Sketch 演算法，這裡將不做介紹。）

1.1.5 稀疏感知演算法

在決策樹的第一篇文章中我們介紹 CART 樹在應對數據缺失時的分裂策略，XGBoost 也給出了其解決方案。

XGBoost 在構建樹的節點過程中只考慮非缺失值的數據遍歷，而為每個節點增加了一個預設方向，當樣本相應的特徵值缺失時，可以被歸類到預設方向上，最優的預設方向可以從數據中學到。至於如何學到預設值的分支，其實很簡單，分別枚舉特徵預設的樣本歸為左右分支後的增益，選擇增益最大的枚舉項即為最優預設方向。

在構建樹的過程中需要枚舉特徵缺失的樣本，乍一看該演算法的計算量增加了一倍，但其實該演算法在構建樹的過程中只考慮了特徵未缺失的樣本遍歷，而特徵值缺失的樣本無需遍歷只需直接分配到左右節點，故演算法所需遍歷的樣本量減少，下圖可以看到稀疏感知演算法比 basic 演算法速度塊了超過 50 倍。

1.2 工程實現

1.2.1 塊結構設計

我們知道，決策樹的學習最耗時的一個步驟就是在每次尋找最佳分裂點是都需要對特徵的值進行排序。而 XGBoost 在訓練之前對根據特徵對數據進行了排序，然後保存到塊結構中，並在每個塊結構中都採用了稀疏矩陣存儲格式（Compressed Sparse Columns Format，CSC）進行存儲，後面的訓練過程中會重複地使用塊結構，可以大大減小計算量。

每一個塊結構包括一個或多個已經排序好的特徵；
缺失特徵值將不進行排序；
每個特徵會存儲指向樣本梯度統計值的索引，方便計算一階導和二階導數值；

這種塊結構存儲的特徵之間相互獨立，方便電腦進行並行計算。在對節點進行分裂時需要選擇增益最大的特徵作為分裂，這時各個特徵的增益計算可以同時進行，這也是 Xgboost 能夠實現分散式或者多執行緒計算的原因。

1.2.2 快取訪問優化演算法

塊結構的設計可以減少節點分裂時的計算量，但特徵值通過索引訪問樣本梯度統計值的設計會導致訪問操作的記憶體空間不連續，這樣會造成快取命中率低，從而影響到演算法的效率。

為了解決快取命中率低的問題，XGBoost 提出了快取訪問優化演算法：為每個執行緒分配一個連續的快取區，將需要的梯度資訊存放在緩衝區中，這樣就是實現了非連續空間到連續空間的轉換，提高了演算法效率。

此外適當調整塊大小，也可以有助於快取優化。

1.2.3 「核外」塊計算

當數據量過大時無法將數據全部載入到記憶體中，只能先將無法載入到記憶體中的數據暫存到硬碟中，直到需要時再進行載入計算，而這種操作必然涉及到因記憶體與硬碟速度不同而造成的資源浪費和性能瓶頸。為了解決這個問題，XGBoost 獨立一個執行緒專門用於從硬碟讀入數據，以實現處理數據和讀入數據同時進行。

此外，XGBoost 還用了兩種方法來降低硬碟讀寫的開銷：

塊壓縮：對 Block 進行按列壓縮，並在讀取時進行解壓；
塊拆分：將每個塊存儲到不同的磁碟中，從多個磁碟讀取可以增加吞吐量。

1.3 優缺點

1.3.1 優點

精度更高：GBDT 只用到一階泰勒展開，而 XGBoost 對損失函數進行了二階泰勒展開。XGBoost 引入二階導一方面是為了增加精度，另一方面也是為了能夠自定義損失函數，二階泰勒展開可以近似大量損失函數；
靈活性更強：GBDT 以 CART 作為基分類器，XGBoost 不僅支援 CART 還支援線性分類器，（使用線性分類器的 XGBoost 相當於帶 L1 和 L2 正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題））。此外，XGBoost 工具支援自定義損失函數，只需函數支援一階和二階求導；
正則化：XGBoost 在目標函數中加入了正則項，用於控制模型的複雜度。正則項里包含了樹的葉子節點個數、葉子節點權重的 L2 範式。正則項降低了模型的方差，使學習出來的模型更加簡單，有助於防止過擬合；
Shrinkage（縮減）：相當於學習速率。XGBoost 在進行完一次迭代後，會將葉子節點的權重乘上該係數，主要是為了削弱每棵樹的影響，讓後面有更大的學習空間；
列抽樣：XGBoost 借鑒了隨機森林的做法，支援列抽樣，不僅能降低過擬合，還能減少計算；
缺失值處理：XGBoost 採用的稀疏感知演算法極大的加快了節點分裂的速度；
可以並行化操作：塊結構可以很好的支援並行計算。

1.3.2 缺點

雖然利用預排序和近似演算法可以降低尋找最佳分裂點的計算量，但在節點分裂過程中仍需要遍曆數據集；
預排序過程的空間複雜度過高，不僅需要存儲特徵值，還需要存儲特徵對應樣本的梯度統計值的索引，相當於消耗了兩倍的記憶體。

LightGBM

LightGBM 由微軟提出，主要用於解決 GDBT 在海量數據中遇到的問題，以便其可以更好更快地用於工業實踐中。

從 LightGBM 名字我們可以看出其是輕量級（Light）的梯度提升機（GBM），其相對 XGBoost 具有訓練速度快、記憶體佔用低的特點。下圖分別顯示了 XGBoost、XGBoost_hist（利用梯度直方圖的 XGBoost）和 LightGBM 三者之間針對不同數據集情況下的記憶體和訓練時間的對比：

那麼 LightGBM 到底如何做到更快的訓練速度和更低的記憶體使用的呢？

我們剛剛分析了 XGBoost 的缺點，LightGBM 為了解決這些問題提出了以下幾點解決方案：

單邊梯度抽樣演算法；
直方圖演算法；
互斥特徵捆綁演算法；
基於最大深度的 Leaf-wise 的垂直生長演算法；
類別特徵最優分割；
特徵並行和數據並行；
快取優化。

本節將繼續從數學原理和工程實現兩個角度介紹 LightGBM。

2.1 數學原理

2.1.1 單邊梯度抽樣演算法

GBDT 演算法的梯度大小可以反應樣本的權重，梯度越小說明模型擬合的越好，單邊梯度抽樣演算法（Gradient-based One-Side Sampling, GOSS）利用這一資訊對樣本進行抽樣，減少了大量梯度小的樣本，在接下來的計算鍋中只需關注梯度高的樣本，極大的減少了計算量。

GOSS 演算法保留了梯度大的樣本，並對梯度小的樣本進行隨機抽樣，為了不改變樣本的數據分布，在計算增益時為梯度小的樣本引入一個常數進行平衡。具體演算法如下所示：

我們可以看到 GOSS 事先基於梯度的絕對值對樣本進行排序（無需保存排序後結果），然後拿到前 a% 的梯度大的樣本，和剩下樣本的 b%，在計算增益時，通過乘上 frac{1-a}{b} 來放大梯度小的樣本的權重。一方面演算法將更多的注意力放在訓練不足的樣本上，另一方面通過乘上權重來防止取樣對原始數據分布造成太大的影響。

2.1.2 直方圖演算法

直方圖演算法

直方圖演算法的基本思想是將連續的特徵離散化為 k 個離散特徵，同時構造一個寬度為 k 的直方圖用於統計資訊（含有 k 個 bin）。利用直方圖演算法我們無需遍曆數據，只需要遍歷 k 個 bin 即可找到最佳分裂點。

我們知道特徵離散化的具有很多優點，如存儲方便、運算更快、魯棒性強、模型更加穩定等等。對於直方圖演算法來說最直接的有以下兩個優點（以 k=256 為例）：

記憶體佔用更小：XGBoost 需要用 32 位的浮點數去存儲特徵值，並用 32 位的整形去存儲索引，而 LightGBM 只需要用 8 位去存儲直方圖，相當於減少了 1/8；
計算代價更小：計算特徵分裂增益時，XGBoost 需要遍歷一次數據找到最佳分裂點，而 LightGBM 只需要遍歷一次 k 次，直接將時間複雜度從 O(#data * #feature) 降低到 O(k * #feature) ，而我們知道 #data >> k 。

雖然將特徵離散化後無法找到精確的分割點，可能會對模型的精度產生一定的影響，但較粗的分割也起到了正則化的效果，一定程度上降低了模型的方差。

直方圖加速

在構建葉節點的直方圖時，我們還可以通過父節點的直方圖與相鄰葉節點的直方圖相減的方式構建，從而減少了一半的計算量。在實際操作過程中，我們還可以先計算直方圖小的葉子節點，然後利用直方圖作差來獲得直方圖大的葉子節點。

稀疏特徵優化

XGBoost 在進行預排序時只考慮非零值進行加速，而 LightGBM 也採用類似策略：只用非零特徵構建直方圖。

2.1.3 互斥特徵捆綁演算法

高維特徵往往是稀疏的，而且特徵間可能是相互排斥的（如兩個特徵不同時取非零值），如果兩個特徵並不完全互斥（如只有一部分情況下是不同時取非零值），可以用互斥率表示互斥程度。互斥特徵捆綁演算法（Exclusive Feature Bundling, EFB）指出如果將一些特徵進行融合綁定，則可以降低特徵數量。

針對這種想法，我們會遇到兩個問題：

哪些特徵可以一起綁定？
特徵綁定後，特徵值如何確定？

對於問題一：EFB 演算法利用特徵和特徵間的關係構造一個加權無向圖，並將其轉換為圖著色演算法。我們知道圖著色是個 NP-Hard 問題，故採用貪婪演算法得到近似解，具體步驟如下：

構造一個加權無向圖，頂點是特徵，邊是兩個特徵間互斥程度；
根據節點的度進行降序排序，度越大，與其他特徵的衝突越大；
遍歷每個特徵，將它分配給現有特徵包，或者新建一個特徵包，是的總體衝突最小。

演算法允許兩兩特徵並不完全互斥來增加特徵捆綁的數量，通過設置最大互斥率來平衡演算法的精度和效率。EFB 演算法的偽程式碼如下所示：

我們看到時間複雜度為 O(#feature^2) ，在特徵不多的情況下可以應付，但如果特徵維度達到百萬級別，計算量則會非常大，為了改善效率，我們提出了一個更快的解決方案：將 EFB 演算法中通過構建圖，根據節點度來排序的策略改成了根據非零值的技術排序，因為非零值越多，互斥的概率會越大。

對於問題二：論文給出特徵合併演算法，其關鍵在於原始特徵能從合併的特徵中分離出來。假設 Bundle 中有兩個特徵值，A 取值為 [0, 10]、B 取值為 [0, 20]，為了保證特徵 A、B 的互斥性，我們可以給特徵 B 添加一個偏移量轉換為 [10, 30]，Bundle 後的特徵其取值為 [0, 30]，這樣便實現了特徵合併。具體演算法如下所示：

2.1.4 帶深度限制的 Leaf-wise 演算法

在建樹的過程中有兩種策略：

Level-wise：基於層進行生長，直到達到停止條件；
Leaf-wise：每次分裂增益最大的葉子節點，直到達到停止條件。

XGBoost 採用 Level-wise 的增長策略，方便並行計算每一層的分裂節點，提高了訓練速度，但同時也因為節點增益過小增加了很多不必要的分裂，降低了計算量；LightGBM 採用 Leaf-wise 的增長策略減少了計算量，配合最大深度的限制防止過擬合，由於每次都需要計算增益最大的節點，所以無法並行分裂。

2.1.5 類別特徵最優分割

大部分的機器學習演算法都不能直接支援類別特徵，一般都會對類別特徵進行編碼，然後再輸入到模型中。常見的處理類別特徵的方法為 one-hot 編碼，但我們知道對於決策樹來說並不推薦使用 one-hot 編碼：

會產生樣本切分不平衡問題，切分增益會非常小。如，國籍切分後，會產生是否中國，是否美國等一系列特徵，這一系列特徵上只有少量樣本為 1，大量樣本為 0。這種劃分的增益非常小：較小的那個拆分樣本集，它佔總樣本的比例太小。無論增益多大，乘以該比例之後幾乎可以忽略；較大的那個拆分樣本集，它幾乎就是原始的樣本集，增益幾乎為零；
影響決策樹學習：決策樹依賴的是數據的統計資訊，而獨熱碼編碼會把數據切分到零散的小空間上。在這些零散的小空間上統計資訊不準確的，學習效果變差。本質是因為獨熱碼編碼之後的特徵的表達能力較差的，特徵的預測能力被人為的拆分成多份，每一份與其他特徵競爭最優劃分點都失敗，最終該特徵得到的重要性會比實際值低。

LightGBM 原生支援類別特徵，採用 many-vs-many 的切分方式將類別特徵分為兩個子集，實現類別特徵的最優切分。假設有某維特徵有 k 個類別，則有 2^{(k-1)} – 1 中可能，時間複雜度為 O(2^k) ，LightGBM 基於 Fisher 大佬的《On Grouping For Maximum Homogeneity》實現了 O(klog_2k) 的時間複雜度。

上圖為左邊為基於 one-hot 編碼進行分裂，後圖為 LightGBM 基於 many-vs-many 進行分裂，在給定深度情況下，後者能學出更好的模型。

其基本思想在於每次分組時都會根據訓練目標對類別特徵進行分類，根據其累積值 frac{sum gradient }{sum hessian} 對直方圖進行排序，然後在排序的直方圖上找到最佳分割。此外，LightGBM 還加了約束條件正則化，防止過擬合。

我們可以看到這種處理類別特徵的方式使得 AUC 提高了 1.5 個點，且時間僅僅多了 20%。

2.2 工程實現

2.2.1 特徵並行

傳統的特徵並行演算法在於對數據進行垂直劃分，然後使用不同機器找到不同特徵的最優分裂點，基於通訊整合得到最佳劃分點，然後基於通訊告知其他機器劃分結果。

傳統的特徵並行方法有個很大的缺點：需要告知每台機器最終劃分結果，增加了額外的複雜度（因為對數據進行垂直劃分，每台機器所含數據不同，劃分結果需要通過通訊告知）。

LightGBM 則不進行數據垂直劃分，每台機器都有訓練集完整數據，在得到最佳劃分方案後可在本地執行劃分而減少了不必要的通訊。

2.2.2 數據並行

傳統的數據並行策略主要為水平劃分數據，然後本地構建直方圖並整合成全局直方圖，最後在全局直方圖中找出最佳劃分點。

這種數據劃分有一個很大的缺點：通訊開銷過大。如果使用點對點通訊，一台機器的通訊開銷大約為 O(#machine * #feature *#bin ) ；如果使用集成的通訊，則通訊開銷為 O(2 * #feature *#bin ) ，

LightGBM 採用分散規約（Reduce scatter）的方式將直方圖整合的任務分攤到不同機器上，從而降低通訊代價，並通過直方圖做差進一步降低不同機器間的通訊。

2.2.3 投票並行

針對數據量特別大特徵也特別多的情況下，可以採用投票並行。投票並行主要針對數據並行時數據合併的通訊代價比較大的瓶頸進行優化，其通過投票的方式只合併部分特徵的直方圖從而達到降低通訊量的目的。

大致步驟為兩步：

本地找出 Top K 特徵，並基於投票篩選出可能是最優分割點的特徵；
合併時只合併每個機器選出來的特徵。

2.2.4 快取優化

上邊說到 XGBoost 的預排序後的特徵是通過索引給出的樣本梯度的統計值，因其索引訪問的結果並不連續，XGBoost 提出快取訪問優化演算法進行改進。

而 LightGBM 所使用直方圖演算法對 Cache 天生友好：

首先，所有的特徵都採用相同的方法獲得梯度（區別於不同特徵通過不同的索引獲得梯度），只需要對梯度進行排序並可實現連續訪問，大大提高了快取命中；
其次，因為不需要存儲特徵到樣本的索引，降低了存儲消耗，而且也不存在 Cache Miss的問題。

2.3 與 XGBoost 的對比

本節主要總結下 LightGBM 相對於 XGBoost 的優點，從記憶體和速度兩方面進行介紹。

2.3.1 記憶體更小

XGBoost 使用預排序後需要記錄特徵值及其對應樣本的統計值的索引，而 LightGBM 使用了直方圖演算法將特徵值轉變為 bin 值，且不需要記錄特徵到樣本的索引，將空間複雜度從 O(2*#data) 降低為 O(#bin) ，極大的減少了記憶體消耗；
LightGBM 採用了直方圖演算法將存儲特徵值轉變為存儲 bin 值，降低了記憶體消耗；
LightGBM 在訓練過程中採用互斥特徵捆綁演算法減少了特徵數量，降低了記憶體消耗。

2.3.2 速度更快

LightGBM 採用了直方圖演算法將遍歷樣本轉變為遍歷直方圖，極大的降低了時間複雜度；
LightGBM 在訓練過程中採用單邊梯度演算法過濾掉梯度小的樣本，減少了大量的計算；
LightGBM 採用了基於 Leaf-wise 演算法的增長策略構建樹，減少了很多不必要的計算量；
LightGBM 採用優化後的特徵並行、數據並行方法加速計算，當數據量非常大的時候還可以採用投票並行的策略；
LightGBM 對快取也進行了優化，增加了 Cache hit 的命中率。

參考文獻

XGBoost: A Scalable Tree Boosting System
陳天奇論文演講 PPT
機器學習演算法中 GBDT 和 XGBOOST 的區別有哪些？- wepon的回答 – 知乎
LightGBM: A Highly Efficient Gradient Boosting Decision Tree
LightGBM 文檔
論文閱讀——LightGBM 原理
機器學習演算法之 LightGBM
關於sklearn中的決策樹是否應該用one-hot編碼？- 柯國霖的回答 – 知乎
如何玩轉LightGBM
A Communication-Efficient Parallel Algorithm for Decision Tree.