lgb演算法模型畫像

A. LightGBM（lgb）介紹

GBDT (Gradient Boosting Decision Tree) 是機器學習中一個長盛不衰的模型，其主要思想是利用弱分類器（決策樹）迭代訓練以得到最優模型，該模型具有訓練效果好、不易過擬合等優點。GBDT不僅在工業界應用廣泛，通常被用於多分類、點擊率預測、搜索排序等任務；在各種數據挖掘競賽中也是致命武器，據統計Kaggle上的比賽有一半以上的冠軍方案都是基於GBDT。而LightGBM（Light Gradient Boosting Machine）是一個實現GBDT演算法的框架，支持高效率的並行訓練，並且具有更快的訓練速度、更低的內存消耗、更好的准確率、支持分布式可以快速處理海量數據等優點。

1.1 LightGBM提出的動機

常用的機器學習演算法，例如神經網路等演算法，都可以以mini-batch的方式訓練，訓練數據的大小不會受到內存限制。而GBDT在每一次迭代的時候，都需要遍歷整個訓練數據多次。如果把整個訓練數據裝進內存則會限制訓練數據的大小；如果不裝進內存，反復地讀寫訓練數據又會消耗非常大的時間。尤其面對工業級海量的數據，普通的GBDT演算法是不能滿足其需求的。

LightGBM提出的主要原因就是為了解決GBDT在海量數據遇到的問題，讓GBDT可以更好更快地用於工業實踐。

1.2 XGBoost的缺點及LightGBM的優化

（1）XGBoost的缺點

在LightGBM提出之前，最有名的GBDT工具就是XGBoost了，它是基於預排序方法的決策樹演算法。這種構建決策樹的演算法基本思想是：

這樣的預排序演算法的優點是能精確地找到分割點。但是缺點也很明顯：

首先，空間消耗大。這樣的演算法需要保存數據的特徵值，還保存了特徵排序的結果（例如，為了後續快速的計算分割點，保存了排序後的索引），這就需要消耗訓練數據兩倍的內存。

其次，時間上也有較大的開銷，在遍歷每一個分割點的時候，都需要進行分裂增益的計算，消耗的代價大。

最後，對cache優化不友好。在預排序後，特徵對梯度的訪問是一種隨機訪問，並且不同的特徵訪問的順序不一樣，無法對cache進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數組，並且不同特徵訪問的順序也不一樣，也會造成較大的cache miss。

（2）LightGBM的優化

為了避免上述XGBoost的缺陷，並且能夠在不損害准確率的條件下加快GBDT模型的訓練速度，lightGBM在傳統的GBDT演算法上進行了如下優化：

下面我們就詳細介紹以上提到的lightGBM優化演算法。

2.1 基於Histogram的決策樹演算法

（1）直方圖演算法

Histogram algorithm應該翻譯為直方圖演算法，直方圖演算法的基本思想是：先把連續的浮點特徵值離散化成 個整數，同時構造一個寬度為 的直方圖。在遍歷數據的時候，根據離散化後的值作為索引在直方圖中累積統計量，當遍歷一次數據後，直方圖累積了需要的統計量，然後根據直方圖的離散值，遍歷尋找最優的分割點。

直方圖演算法簡單理解為：首先確定對於每一個特徵需要多少個箱子（bin）並為每一個箱子分配一個整數；然後將浮點數的范圍均分成若干區間，區間個數與箱子個數相等，將屬於該箱子的樣本數據更新為箱子的值；最後用直方圖（#bins）表示。看起來很高大上，其實就是直方圖統計，將大規模的數據放在了直方圖中。

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

當然，Histogram演算法並不是完美的。由於特徵被離散化後，找到的並不是很精確的分割點，所以會對結果產生影響。但在不同的數據集上的結果表明，離散化的分割點對最終的精度影響並不是很大，甚至有時候會更好一點。原因是決策樹本來就是弱模型，分割點是不是精確並不是太重要；較粗的分割點也有正則化的效果，可以有效地防止過擬合；即使單棵樹的訓練誤差比精確分割的演算法稍大，但在梯度提升（Gradient Boosting）的框架下沒有太大的影響。

（2）直方圖做差加速

LightGBM另一個優化是Histogram（直方圖）做差加速。一個葉子的直方圖可以由它的父親節點的直方圖與它兄弟的直方圖做差得到，在速度上可以提升一倍。通常構造直方圖時，需要遍歷該葉子上的所有數據，但直方圖做差僅需遍歷直方圖的k個桶。在實際構建樹的過程中，LightGBM還可以先計算直方圖小的葉子節點，然後利用直方圖做差來獲得直方圖大的葉子節點，這樣就可以用非常微小的代價得到它兄弟葉子的直方圖。

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

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

在Histogram演算法之上，LightGBM進行進一步的優化。首先它拋棄了大多數GBDT工具使用的按層生長 (level-wise) 的決策樹生長策略，而使用了帶有深度限制的按葉子生長 (leaf-wise) 演算法。

XGBoost 採用 Level-wise 的增長策略，該策略遍歷一次數據可以同時分裂同一層的葉子，容易進行多線程優化，也好控制模型復雜度，不容易過擬合。但實際上Level-wise是一種低效的演算法，因為它不加區分的對待同一層的葉子，實際上很多葉子的分裂增益較低，沒必要進行搜索和分裂，因此帶來了很多沒必要的計算開銷。

LightGBM採用Leaf-wise的增長策略，該策略每次從當前所有葉子中，找到分裂增益最大的一個葉子，然後分裂，如此循環。因此同Level-wise相比，Leaf-wise的優點是：在分裂次數相同的情況下，Leaf-wise可以降低更多的誤差，得到更好的精度；Leaf-wise的缺點是：可能會長出比較深的決策樹，產生過擬合。因此LightGBM會在Leaf-wise之上增加了一個最大深度的限制，在保證高效率的同時防止過擬合。

Gradient-based One-Side Sampling 應該被翻譯為單邊梯度采樣（GOSS）。GOSS演算法從減少樣本的角度出發，排除大部分小梯度的樣本，僅用剩下的樣本計算信息增益，它是一種在減少數據量和保證精度上平衡的演算法。

AdaBoost中，樣本權重是數據重要性的指標。然而在GBDT中沒有原始樣本權重，不能應用權重采樣。幸運的是，我們觀察到GBDT中每個數據都有不同的梯度值，對采樣十分有用。即梯度小的樣本，訓練誤差也比較小，說明數據已經被模型學習得很好了，直接想法就是丟掉這部分梯度小的數據。然而這樣做會改變數據的分布，將會影響訓練模型的精確度，為了避免此問題，提出了GOSS演算法。

GOSS是一個樣本的采樣演算法，目的是丟棄一些對計算信息增益沒有幫助的樣本留下有幫助的。根 據計算信息增益的定義，梯度大的樣本對信息增益有更大的影響。因此，GOSS在進行數據采樣的 時候只保留了梯度較大的數據，但是如果直接將所有梯度較小的數據都丟棄掉勢必會影響數據的總 體分布。所以，GOSS首先將要進行分裂的特徵的所有取值按照絕對值大小降序排序（XGBoost一 樣也進行了排序，但是LightGBM不用保存排序後的結果），選取絕對值最大的 個數 據。然後在剩下的較小梯度數據中隨機選擇 個數據。接著將這 個數據乘 以一個常數 這樣演算法就會更關注訓練不足的樣本, 而不會過多改變原數據集的分布。最 後使用這 個數據來計算信息增益。下圖是GOSS的具體演算法。

2.4 互斥特徵捆綁演算法

高維度的數據往往是稀疏的，這種稀疏性啟發我們設計一種無損的方法來減少特徵的維度。通常被 抹綁的特徵都是互斥的（即特徵不會同時為非零值，像one-hot），這樣兩個特徵描綁起來才不會 丟失信息。如果兩個特徵並不是完全互斥 (部分情況下兩個特徵都是非零值)，可以用一個指標對 特徵不互斥程度進行像量，稱之為沖突比率，當這個值較小時，我們可以選擇把不完全互斥的兩個 特徵肺綁，而不影響最後的精度。

互斥特徵肺綁演算法 (Exclusive Feature Bundling, EFB) 指出如 果將一些特徵進行融合綁定，則可以降低特徵數量。這樣在構建直方圖時的時間復雜度從O(#data* # feature)變為 O(#data* # bundle), 這里 bundle 指特徵融合綁 定後特徵包的個數, 且 #bundle 遠小於 # feature 。

我們將論文《Lightgbm: A highly efficient gradient boosting decision tree》中沒有提到的優化方案，而在其相關論文《A communication-efficient parallel algorithm for decision tree》中提到的優化方案，放到本節作為LightGBM的工程優化來向大家介紹。

3.1 直接支持類別特徵

實際上大多數機器學習工具都無法直接支持類別特徵，一般需要把類別特徵，通過 one-hot 編碼，轉化到多維的0/1特徵，降低了空間和時間的效率。但我們知道對於決策樹來說並不推薦使用 one-hot 編碼，尤其當類別特徵中類別個數很多的情況下，會存在以下問題：

1,會產生樣本切分不平衡問題，導致切分增益非常小（即浪費了這個特徵）。使用 one-hot編碼，意味著在每一個決策節點上只能使用one vs rest（例如是不是狗，是不是貓等）的切分方式。

例如，動物類別切分後，會產生是否狗，是否貓等一系列特徵，這一系列特徵上只有少量樣本為 1，大量樣本為 0，這時候切分樣本會產生不平衡，這意味著切分增益也會很小。較小的那個切分樣本集，它占總樣本的比例太小，無論增益多大，乘以該比例之後幾乎可以忽略；較大的那個拆分樣本集，它幾乎就是原始的樣本集，增益幾乎為零。比較直觀的理解就是不平衡的切分和不切分沒有區別。

2,會影響決策樹的學習。因為就算可以對這個類別特徵進行切分，獨熱編碼也會把數據切分到很多零散的小空間上，如下圖左邊所示。而決策樹學習時利用的是統計信息，在這些數據量小的空間上，統計信息不準確，學習效果會變差。但如果使用下圖右邊的切分方法，數據會被切分到兩個比較大的空間，進一步的學習也會更好。下圖右邊葉子節點的含義是X=A或者X=C放到左孩子，其餘放到右孩子。

演算法流程如下圖所示，在枚舉分割點之前，先把直方圖按照每個類別對應的label均值進行排序; 然後按照排序的結果依次枚舉最優分割點。從下圖可以看到, 為類別的均值。當然，這個方法很容易過擬合，所以LightGBM裡面還增加了很多對於這個方法的約束和正則化。

在Expo數據集上的實驗結果表明，相比0/1展開的方法，使用LightGBM支持的類別特徵可以使訓練速度加速8倍，並且精度一致。更重要的是，LightGBM是第一個直接支持類別特徵的GBDT工具。

3.2 支持高效並行

（1）特徵並行

特徵並行的主要思想是不同機器在不同的特徵集合上分別尋找最優的分割點，然後在機器間同步最優的分割點。XGBoost使用的就是這種特徵並行方法。這種特徵並行方法有個很大的缺點：就是對數據進行垂直劃分，每台機器所含數據不同，然後使用不同機器找到不同特徵的最優分裂點，劃分結果需要通過通信告知每台機器，增加了額外的復雜度。

LightGBM 則不進行數據垂直劃分，而是在每台機器上保存全部訓練數據，在得到最佳劃分方案後可在本地執行劃分而減少了不必要的通信。具體過程如下圖所示。

（2）數據並行

傳統的數據並行策略主要為水平劃分數據，讓不同的機器先在本地構造直方圖，然後進行全局的合 並，最後在合並的直方圖上面尋找最優分割點。這種數據劃分有一個很大的缺點：通訊開銷過大。 如果使用點對點通信，一台機器的通訊開銷大約為 O(#machine* # feature*#bin) 如果使用集成的通信，則通訊開銷為

LightGBM在數據並行中使用分散規約 (Rece scatter) 把直方圖合並的任務分攤到不同的機器，降低通信和計算，並利用直方圖做差，進一步減少了一半的通信量。具體過程如下圖所示。

(3）投票並行

基於投票的數據並行則進一步優化數據並行中的通信代價，使通信代價變成常數級別。在數據量很大的時候，使用投票並行的方式只合並部分特徵的直方圖從而達到降低通信量的目的，可以得到非常好的加速效果。具體過程如下圖所示。

大致步驟為兩步：

XGBoost對cache優化不友好，如下圖所示。在預排序後，特徵對梯度的訪問是一種隨機訪問，並且不同的特徵訪問的順序不一樣，無法對cache進行優化。同時，在每一層長樹的時候，需要隨機訪問一個行索引到葉子索引的數組，並且不同特徵訪問的順序也不一樣，也會造成較大的cache miss。為了解決緩存命中率低的問題，XGBoost 提出了緩存訪問演算法進行改進。

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

4.1 優點
這部分主要總結下 LightGBM 相對於 XGBoost 的優點，從內存和速度兩方面進行介紹。

（1）速度更快

（2）內存更小

4.2 缺點

訓練配置 ：
6307410個樣本做訓練集

訓練出的LightGBM模型文件及其含義解析：

第1棵樹

樹的結構

第二棵樹，含義參考第一棵樹

特徵重要性

重要性值是統計特徵在所有樹中作為中間節點（分裂節點）的分裂特徵且分裂增益為正的次數，可以理解成是對分裂作用越大的特徵越重要

參考自：
Microstrong
魚達爾

B. 機器學習一般常用的演算法有哪些

機器學習是人工智慧的核心技術，是學習人工智慧必不可少的環節。機器學習中有很多演算法，能夠解決很多以前難以企的問題，機器學習中涉及到的演算法有不少，下面小編就給大家普及一下這些演算法。

一、線性回歸

一般來說，線性回歸是統計學和機器學習中最知名和最易理解的演算法之一。這一演算法中我們可以用來預測建模，而預測建模主要關注最小化模型誤差或者盡可能作出最准確的預測，以可解釋性為代價。我們將借用、重用包括統計學在內的很多不同領域的演算法，並將其用於這些目的。當然我們可以使用不同的技術從數據中學習線性回歸模型，例如用於普通最小二乘法和梯度下降優化的線性代數解。就目前而言，線性回歸已經存在了200多年，並得到了廣泛研究。使用這種技術的一些經驗是盡可能去除非常相似（相關）的變數，並去除噪音。這是一種快速、簡單的技術。

二、Logistic 回歸

它是解決二分類問題的首選方法。Logistic 回歸與線性回歸相似，目標都是找到每個輸入變數的權重，即系數值。與線性回歸不同的是，Logistic 回歸對輸出的預測使用被稱為 logistic 函數的非線性函數進行變換。logistic 函數看起來像一個大的S，並且可以將任何值轉換到0到1的區間內。這非常實用，因為我們可以規定logistic函數的輸出值是0和1並預測類別值。像線性回歸一樣，Logistic 回歸在刪除與輸出變數無關的屬性以及非常相似的屬性時效果更好。它是一個快速的學習模型，並且對於二分類問題非常有效。

三、線性判別分析（LDA）

在前面我們介紹的Logistic 回歸是一種分類演算法，傳統上，它僅限於只有兩類的分類問題。而LDA的表示非常簡單直接。它由數據的統計屬性構成，對每個類別進行計算。單個輸入變數的 LDA包括兩個，第一就是每個類別的平均值，第二就是所有類別的方差。而在線性判別分析，進行預測的方法是計算每個類別的判別值並對具備最大值的類別進行預測。該技術假設數據呈高斯分布，因此最好預先從數據中刪除異常值。這是處理分類預測建模問題的一種簡單而強大的方法。

四、決策樹

決策樹是預測建模機器學習的一種重要演算法。決策樹模型的表示是一個二叉樹。這是演算法和數據結構中的二叉樹，沒什麼特別的。每個節點代表一個單獨的輸入變數x和該變數上的一個分割點。而決策樹的葉節點包含一個用於預測的輸出變數y。通過遍歷該樹的分割點，直到到達一個葉節點並輸出該節點的類別值就可以作出預測。當然決策樹的有點就是決策樹學習速度和預測速度都很快。它們還可以解決大量問題，並且不需要對數據做特別准備。

五、樸素貝葉斯

其實樸素貝葉斯是一個簡單但是很強大的預測建模演算法。而這個模型由兩種概率組成，這兩種概率都可以直接從訓練數據中計算出來。第一種就是每個類別的概率，第二種就是給定每個 x 的值，每個類別的條件概率。一旦計算出來，概率模型可用於使用貝葉斯定理對新數據進行預測。當我們的數據是實值時，通常假設一個高斯分布，這樣我們可以簡單的估計這些概率。而樸素貝葉斯之所以是樸素的，是因為它假設每個輸入變數是獨立的。這是一個強大的假設，真實的數據並非如此，但是，該技術在大量復雜問題上非常有用。所以說，樸素貝葉斯是一個十分實用的功能。

六、K近鄰演算法

K近鄰演算法簡稱KNN演算法，KNN 演算法非常簡單且有效。KNN的模型表示是整個訓練數據集。KNN演算法在整個訓練集中搜索K個最相似實例（近鄰）並匯總這K個實例的輸出變數，以預測新數據點。對於回歸問題，這可能是平均輸出變數，對於分類問題，這可能是眾數類別值。而其中的訣竅在於如何確定數據實例間的相似性。如果屬性的度量單位相同，那麼最簡單的技術是使用歐幾里得距離，我們可以根據每個輸入變數之間的差值直接計算出來其數值。當然，KNN需要大量內存或空間來存儲所有數據，但是只有在需要預測時才執行計算。我們還可以隨時更新和管理訓練實例，以保持預測的准確性。

七、Boosting 和 AdaBoost

首先，Boosting 是一種集成技術，它試圖集成一些弱分類器來創建一個強分類器。這通過從訓練數據中構建一個模型，然後創建第二個模型來嘗試糾正第一個模型的錯誤來完成。一直添加模型直到能夠完美預測訓練集，或添加的模型數量已經達到最大數量。而AdaBoost 是第一個為二分類開發的真正成功的 boosting 演算法。這是理解 boosting 的最佳起點。現代 boosting 方法建立在 AdaBoost 之上，最顯著的是隨機梯度提升。當然，AdaBoost 與短決策樹一起使用。在第一個決策樹創建之後，利用每個訓練實例上樹的性能來衡量下一個決策樹應該對每個訓練實例付出多少注意力。難以預測的訓練數據被分配更多權重，而容易預測的數據分配的權重較少。依次創建模型，每一個模型在訓練實例上更新權重，影響序列中下一個決策樹的學習。在所有決策樹建立之後，對新數據進行預測，並且通過每個決策樹在訓練數據上的精確度評估其性能。所以說，由於在糾正演算法錯誤上投入了太多注意力，所以具備已刪除異常值的干凈數據十分重要。

八、學習向量量化演算法（簡稱 LVQ）

學習向量量化也是機器學習其中的一個演算法。可能大家不知道的是，K近鄰演算法的一個缺點是我們需要遍歷整個訓練數據集。學習向量量化演算法（簡稱 LVQ）是一種人工神經網路演算法，它允許你選擇訓練實例的數量，並精確地學習這些實例應該是什麼樣的。而學習向量量化的表示是碼本向量的集合。這些是在開始時隨機選擇的，並逐漸調整以在學習演算法的多次迭代中最好地總結訓練數據集。在學習之後，碼本向量可用於預測。最相似的近鄰通過計算每個碼本向量和新數據實例之間的距離找到。然後返回最佳匹配單元的類別值或作為預測。如果大家重新調整數據，使其具有相同的范圍，就可以獲得最佳結果。當然，如果大家發現KNN在大家數據集上達到很好的結果，請嘗試用LVQ減少存儲整個訓練數據集的內存要求