1.1 LightGBM提出的動機
常用的機器學習算法，如神經網絡，可以通過mini-batch進行訓練，並且訓練數據的大小不會受到內存的限制。在每次叠代中，GBDT需要多次遍歷整個訓練數據。如果將整個訓練數據加載到內存中，則訓練數據的大小將受到限制；如果不將其加載到內存中，則重復讀取和寫入訓練數據將花費大量時間。尤其是在面對工業海量數據時，普通的GBDT算法無法滿足其需求。
提出LightGBM的主要原因是為了解決GBDT在海量數據中遇到的問題，以便GBDT可以更好、更快地用於工業實踐。
1.2 XGBoost的缺點及LightGBM的優化
（1）XG boost的缺點
在LightGBM提出之前，最著名的GBDT工具是XGBoost，它是壹種基於預排序方法的決策樹算法。這種構建決策樹算法的基本思想是:
這種預排序算法的優點是可以準確地找到分割點。但是缺點也很明顯:
首先，它占用了大量空間。這樣的算法需要保存數據的特征值和特征排序的結果（例如，為了將來快速計算分割點，保存排序後的索引），這需要兩倍於訓練數據的內存。
其次，時間上也有很大的開銷。當遍歷每個分割點時，需要計算分裂增益，這是昂貴的。
最後，對緩存優化不友好。預排序後，特征對梯度的訪問是隨機訪問，不同特征的訪問順序不同，因此無法優化緩存。同時，當每壹層都很長時，需要從行索引到葉索引隨機訪問壹個數組，並且不同特征的訪問順序不同，這也會造成較大的緩存未命中。
（2）優化2）輕型GBM
為了避免XGBoost的上述缺陷並在不損害精度的情況下加快GBDT模型的訓練，lightGBM對傳統的GBDT算法進行了如下優化:
下面我們來詳細介紹壹下上面提到的lightGBM優化算法。
2.1基於直方圖的決策樹算法
（1）直方圖算法
直方圖算法應該翻譯成直方圖算法。直方圖算法的基本思想是將連續的浮點特征值離散化為整數，構造壹個寬度為的直方圖。遍歷數據時，統計數據根據作為索引的離散化值在直方圖中累積。當遍歷壹次數據時，直方圖累積所需的統計量，然後根據直方圖的離散值，搜索最佳分割點。
直方圖算法簡單理解為:首先，確定每個特征需要多少個面元，並為每個面元分配壹個整數；然後將浮點數的範圍劃分為若幹區間，區間數等於盒數，將屬於盒的樣本數據更新為盒的值；最後，用直方圖（條數）表示。它看起來很高大上，但實際上是直方圖統計，將大規模數據放在直方圖中。
我們知道特征離散化有很多優點，比如存儲方便、運算速度快、魯棒性強、模型更穩定等。對於直方圖算法，最直接的有以下兩個優點:
當然，直方圖算法並不完美。因為特征是離散化的，分割點不是很準確，所以會對結果有影響。然而，在不同數據集上的結果表明，離散分割點對最終精度的影響很小，有時甚至更好。原因是決策樹是壹個弱模型，分割點是否準確並不太重要；粗分割點還具有正則化效果，可以有效防止過擬合；即使單棵樹的訓練誤差略大於精確分割算法的訓練誤差，在梯度提升的框架下也沒有太大影響。
②直方圖差分加速
LightGBM的另壹個優化是直方圖差分加速。葉子的直方圖可以通過其父節點的直方圖和其兄弟節點的直方圖之間的差異來獲得，這可以使速度加倍。通常，在構建直方圖時，需要遍歷葉子上的所有數據，但直方圖差異只需要遍歷直方圖的k個桶。在實際的建樹過程中，LightGBM還可以計算直方圖較小的葉子節點，然後利用直方圖差異獲得直方圖較大的葉子節點，從而以非常小的代價獲得其兄弟葉子的直方圖。
註意:XGBoost在預排序過程中只考慮非零值進行加速，而LightGBM也采用了類似的策略:只使用非零特征來構建直方圖。
2.2具有深度限制的逐葉算法
在直方圖算法的基礎上，對LightGBM進行了進壹步優化。首先，它放棄了大多數GBDT工具使用的逐層決策樹生長策略，而是使用具有深度限制的逐層決策樹算法。
XGBoost采用Level-wise的增長策略，通過遍歷壹次數據，可以同時拆分同壹層的葉子，便於多線程優化，控制模型復雜度，不易過擬合。但事實上，Level-wise是壹種低效的算法，因為它不加區別地對待同壹層的葉子。實際上，許多葉子的分裂增益較低，因此不必進行搜索和分裂，這帶來了大量不必要的計算開銷。
LightGBM采用Leaf-wise的生長策略，每次從所有當前葉子中找到分裂增益最大的葉子，然後將其分裂，以此類推。因此，與Level-wise相比，Leaf-wise具有以下優點:在相同分裂數的情況下，Leaf-wise可以減少更多的錯誤並獲得更好的準確性；逐葉方式的缺點是它可能會生成更深的決策樹並產生過度擬合。因此，LightGBM將在Leaf-wise上添加最大深度限制，以確保高效率並防止過擬合。
基於梯度的單側采樣應翻譯為單側梯度采樣（GOSS）。GOSS算法從減少樣本的角度出發，排除了大部分梯度較小的樣本，僅使用剩余樣本計算信息增益。這是壹種在減少數據量和確保準確性方面取得平衡的算法。
在AdaBoost中，樣本權重是數據重要性的指標。然而，GBDT沒有原始樣本重量，因此加權抽樣無法適用。幸運的是，我們觀察到GBDT的每個數據都有不同的梯度值，這對采樣非常有用。即梯度小的樣本訓練誤差相對較小，說明數據已經被模型很好地學習了，直接的思路就是丟掉這部分梯度小的數據。但是，這樣做會改變數據的分布並影響訓練模型的準確性。為了避免這個問題，提出了高斯算法。
GOSS是壹種樣本采樣算法，其目的是丟棄壹些對計算信息增益沒有幫助的樣本，並留下有幫助的樣本。根據計算信息增益的定義，梯度大的樣本對信息增益的影響更大。因此，GOSS在采樣數據時只保留梯度大的數據，但如果直接丟棄所有梯度小的數據，則必然會影響數據的整體分布。因此，GOSS首先將所有要拆分的特征的值按絕對值降序排序（XGBoost也排序，但LightGBM不需要保存排序結果），並選擇絕對值最大的數據。然後從剩余的較小梯度數據中隨機選擇數據。然後將該數據乘以壹個常數，以便算法將更多地關註訓練不足的樣本，而不會過多地改變原始數據集的分布。最後，該數據用於計算信息增益。下圖是GOSS的具體算法。
2.4互斥特征綁定算法
高維數據通常是稀疏的，這啟發我們設計壹種無損方法來降低特征的維度。通常綁定的要素是互斥的（也就是說，這些要素不會同時為非零值，如one-hot），因此這兩個要素綁定在壹起時不會丟失信息。如果兩個特征不是完全互斥的（在某些情況下，兩個特征都是非零的），則可以使用壹個指標來衡量特征的非互斥程度，該指標稱為沖突比。當該值較小時，我們可以選擇在不影響最終精度的情況下結合兩個不完全互斥的特征。
獨家特征綁定算法（EFB）指出，如果將壹些特征進行融合和綁定，可以減少特征的數量。這樣，構造直方圖的時間復雜度從O（# data * # feature）變為O（# data * #bundle），其中bundle是指特征融合綁定後的特征包數量，# bundle比# feature小得多。
我們將論文《LightGBM:壹種高效的梯度提升決策樹》中未提及的優化方案及其相關論文《壹種通信高效的決策樹並行算法》中提及的優化方案作為LightGBM的工程優化放入本節向您介紹。
3.1直接支持類別功能。
事實上，大多數機器學習工具無法直接支持類別特征。通常需要通過壹鍵編碼將類別特征轉化為多維0/1特征，降低了空間和時間效率。但是，我們知道不建議對決策樹進行壹次性編碼，尤其是當類別特征中有許多類別時，會出現以下問題:
1，會出現樣本分割的不平衡，導致分割增益非常小（也就是浪費了這個特性）。使用one-hot編碼意味著只有壹個vs rest（如狗、貓等。）可用於每個決策節點。
比如動物分類分割後，會出現壹系列特征，比如是不是狗，是不是貓等。在這壹系列特征中，只有少數樣本為1，大量樣本為0。此時，分割樣本將是不平衡的，這意味著分割增益將很小。較小的分段樣本集占總樣本的比例太小，在乘以該比例後幾乎可以忽略不計增益；較大的分裂樣本集幾乎是原始樣本集，其增益幾乎為零。直觀的理解就是不平衡分割和不分割沒有區別。
2、會影響決策樹的學習。因為即使這個類別特征可以分割，獨特的熱度編碼也會將數據分割成許多分散的小空間，如下圖左側所示。然而，決策樹學習使用統計信息。在這些小數據空間中，統計信息不準確，學習效果會變差。但是，如果使用下圖右側的分割方法，數據將被分割成兩個更大的空間，進壹步研究將更好。下圖中右邊的葉節點的含義是X=A或X=C放在左邊的子節點中，其余的放在右邊的子節點中。
算法流程如下圖所示。在枚舉分割點之前，先根據每個類別對應的標簽均值對直方圖進行排序。然後根據排序結果依次枚舉最優分割點。從下圖可以看出，它是類別的平均值。當然，這種方法很容易過擬合，因此在LightGBM中對這種方法有許多約束和正則化。
在Expo數據集上的實驗結果表明，與0/1擴展方法相比，利用LightGBM支持的類別特征，訓練速度可加快8倍，且精度保持壹致。更重要的是，LightGBM是第壹個直接支持類別特性的GBDT工具。
3.2支持高效並行
（1）特征並行性
特征並行的主要思想是不同的機器在不同的特征集上尋找最優分割點，然後在機器之間同步最優分割點。XGBoost使用這種特性並行方法。這種特征並行方法有壹個很大的缺點:數據被垂直分割，每臺機器包含不同的數據，然後使用不同的機器來尋找不同特征的最佳分割點，分割結果需要傳達給每臺機器，這增加了額外的復雜性。
LightGBM不會垂直劃分數據，而是將所有訓練數據保存在每臺機器上。在得到最佳分割方案後，可以在本地執行分割，減少不必要的通信。具體流程如下圖所示。
②數據並行性
傳統的數據並行策略主要是對數據進行水平劃分，使不同的機器先在局部構建直方圖，然後在全局進行合並，最後在合並後的直方圖上找到最優分割點。這種數據劃分有壹個很大的缺點:通信開銷太大。如果使用點對點通信，壹臺機器的通信成本約為O（# machine * # feature * # bin）。如果使用集成通信，通信成本為
LightGBM通過在數據並行中使用Reduce scatter將直方圖合並的任務分配給不同的機器，減少了通信和計算，並通過使用直方圖差異進壹步將通信流量減少了壹半。具體流程如下圖所示。
⑶平行表決
基於投票的數據並行進壹步優化了數據並行中的通信開銷，使得通信開銷恒定。當數據量非常大的時候，通過並行投票的方式只合並部分特征的直方圖，達到降低流量的目的，可以得到非常好的加速效果。具體流程如下圖所示。
壹般步驟分為兩步:
XGBoost對緩存優化不友好，如下圖所示。預排序後，特征對梯度的訪問是隨機訪問，不同特征的訪問順序不同，因此無法優化緩存。同時，當每壹層都很長時，需要從行索引到葉索引隨機訪問壹個數組，並且不同特征的訪問順序不同，這也會造成較大的緩存未命中。為了解決緩存命中率低的問題，XGBoost提出了壹種改進的緩存訪問算法。
雖然LightGBM使用直方圖算法天生對緩存友好:
4.1的優勢
這壹部分主要總結了LightGBM相對於XGBoost的優勢，並從內存和速度兩方面進行介紹。
（1）更快
②內存較小
4.2缺點
培訓配置:
6307410個樣本作為訓練集。
經過訓練的LightGBM模型文件及其含義分析:
1樹
樹形結構
第二棵樹指的是第壹棵樹的意思。
特征重要性
重要性值是統計特征在所有樹中被用作中間節點（分裂節點）的分裂特征且分裂增益為正的次數，可以理解為分裂效果越大，特征越重要。
參考自:
微強
尤達爾