陸陸續續整理的機器學習的知識點，資料大多數來自網上，不做盈利目的，如果侵權請告知即刪！如果文章中有錯誤的地方還請各位同學指正，，一起學習，一起進步！
每天都在更新中，記得收藏，每天進步一點點！！

一天1個機器學習知識點（一）（決策樹，有無監督學習，SVM，梯度下降法，邏輯回歸，NB）
一天1個機器學習知識點（二）（KNN，Kmeans，偏差方差，參數非參數模型，生成模型判別模型，正則化，概率，牛頓法，熵）
一天1個機器學習知識點（三）（損失函數，生成模型和判別模型，DBSCAN，OPTICS）
一天1個機器學習知識點（四）這部分主要更新集成學習的內容（RF,adaboost,GBDT,XGBoost等）
一天1個機器學習知識點（五）（特征工程相關，ＰＣＡ，ＬＤＡ等）

穿越---->深度學習知識點！！

目錄

• 1.bagging和boosting
• • 1.1 bagging（套袋法）
  • 1.2boosting
  • 1.3 區別
  • 1.4為什么說bagging是減少variance，而boosting是減少bias？
• 1.隨機森林（RF）
• • 1.1原理
  • 1.2 優缺點
  • 1.3其他面試點
• 2.Adaboost
• • 2.1加法模型和指數損失函數
  • 2.2原理
  • 2.3算法流程
  • 2.4弱分類器權重公式推導
  • 2.5優缺點
  • 2.6其他面試點
• 3.GBDT（梯度提升決策樹）
• • 3.1 原理
  • 3.2GBDT 算法的流程？
  • 3.3GBDT 如何選擇特征 ？
  • 3.4GBDT如何構建特征 （GBDT+LR）
  • 3.5GBDT 如何用于分類？
  • 3.6GBDT的優點和局限性
  • 3.7梯度提升和梯度下降的區別和聯系
  • 3.8RF、GBDT的區別
  • 3.9GBDT怎樣設置單棵樹的停止生長條件？
  • 3.10GBDT如何評估特征的權重大小？
  • 3.11GBDT中哪些部分可以并行?
  • 3.12如何防止過擬合？
  • 3.13GBDT當增加樣本數量時，訓練時長是線性增加嗎？
  • 3.14當增加樹的顆數時，訓練時長是線性增加嗎？
  • 3.15當增加一個棵樹葉子節點數目時，訓練時長是線性增加嗎？
  • 3.16每個節點上都保存什么信息？
• 4.XgBoost
• • 4.1XgBoost有哪些特點
  • 4.2對于連續值如何進行分割？
  • 4.3對于特征缺失值如何分類？
  • 4.4XGBoost怎么做到并行化
  • 4.5XgBoost和GBDT的區別和聯系
  • 4.6.XGBoost和深度學習的區別？
  • 4.7.xgboost為什么使用二階泰勒展開
• 5.lightGBM
• • 5.1LGB原理
  • 5.2.XGboost的不足之處
  • 5.3.XGBoost和LGBM樹的生長方式
  • 5.4.XGBoost和LGBM樹的劃分方式
  • 5.5.支持類別特征
  • 5.6.支持并行學習
  • 5.7lightGBM與XGboost對比
  • 5.8直方圖算法

1.bagging和boosting

1.1 bagging（套袋法）

其算法過程如下：

從原始樣本集中抽取訓練集。每輪從原始樣本集中使用Bootstraping的方法抽取n個訓練樣本（在訓練集中，有些樣本可能被多次抽取到，而有些樣本可能一次都沒有被抽中）。共進行k輪抽取，得到k個訓練集。（k個訓練集之間是相互獨立的）

每次使用一個訓練集得到一個模型，k個訓練集共得到k個模型。（注：這里并沒有具體的分類算法或回歸方法，我們可以根據具體問題采用不同的分類或回歸方法，如決策樹、感知器等）

對分類問題：將上步得到的k個模型采用投票的方式得到分類結果；對回歸問題，計算上述模型的均值作為最后的結果。（所有模型的重要性相同）

1.2boosting

AdaBoosting方式每次使用的是全部的樣本，每輪訓練改變樣本的權重。下一輪訓練的目標是找到一個函數f 來擬合上一輪的殘差。當殘差足夠小或者達到設置的最大迭代次數則停止。Boosting會減小在上一輪訓練正確的樣本的權重，增大錯誤樣本的權重。（對的殘差小，錯的殘差大）
梯度提升的Boosting方式是使用代價函數對上一輪訓練出的模型函數f的偏導來擬合殘差。

1.3 區別

1）樣本選擇上：
Bagging：訓練集是在原始集中有放回選取的，從原始集中選出的各輪訓練集之間是獨立的。
Boosting：每一輪的訓練集不變，只是訓練集中每個樣例在分類器中的權重發生變化。而權值是根據上一輪的分類結果進行調整。

2）樣例權重：
Bagging：使用均勻取樣，每個樣例的權重相等。
Boosting：根據錯誤率不斷調整樣例的權值，錯誤率越大則權重越大。

3）預測函數權重：
Bagging：所有預測函數的權重相等。
Boosting：每個弱分類器都有相應的權重，對于分類誤差小的分類器會有更大的權重。

4）并行計算：
Bagging：各個預測函數可以并行生成
Boosting：各個預測函數只能順序生成，因為后一個模型參數需要前一輪模型的結果。

1.4為什么說bagging是減少variance，而boosting是減少bias？

關于偏差和方差在機器學習系列第二篇。

• bagging的方法主要是隨機取樣，每個模型的目標函數跟單模型并沒有很大的區別，所以bias變化不大，而多個模型的集成降低異常點的影響，這兩個方法都可以降低variance。
• boosting的方法通過殘差學習，最后得預測值發生了改變，是由多個模型預測值與每個模型權重重新表示，糾錯之后的boosting預測值自然是更接近真實值，因此bais偏離真實值的誤差會降低。（我覺得根據這個可以用在stacking的模型選擇上）

1.隨機森林（RF）

1.1原理

Random Forest（隨機森林）是Bagging的擴展變體，它在以決策樹為基學習器構建Bagging集成的基礎上，進一步在決策樹的訓練過程中引入了隨機特征選擇，因此可以概括RF包括四個部分：1、隨機選擇樣本（放回抽樣）；2、隨機選擇特征；3、構建決策樹；4、隨機森林投票（平均）。

隨機選擇樣本和Bagging相同，隨機選擇特征是指在樹的構建中，會從樣本集的特征集合中隨機選擇部分特征，然后再從這個子集中選擇最優的屬性用于劃分，這種隨機性導致隨機森林的偏差會有稍微的增加（相比于單棵不隨機樹），但是由于隨機森林的‘平均’特性，會使得它的方差減小，而且方差的減小補償了偏差的增大，因此總體而言是更好的模型。

在構建決策樹的時候，RF的每棵決策樹都最大可能的進行生長而不進行剪枝；在對預測輸出進行結合時，RF通常對分類問題使用簡單投票法，回歸任務使用簡單平均法。
小細節：每個袋外數據會對相應的樹作預測，評估其誤差（稱為袋外誤差）；隨機森林中的絕大多數樹為Cart樹

1.2 優缺點

隨機森林的優點：

在數據集上表現良好，相對于其他算法有較大的優勢（訓練速度、預測準確度）；

能夠處理很高維的數據，并且不用特征選擇，而且在訓練完后，給出特征的重要性。因此可做特征選擇；

容易做成并行化方法。

噪聲小的時候不容易過擬合，因為跟bagging一樣減小variance。

隨機性的引入，增加了多樣性，泛化能力非常強，抗噪聲能力強

RF的缺點：

在噪聲較大的分類或者回歸問題上會過擬合。

隨機森林在解決回歸問題時，表現較差，這是因為它并不能給出一個連續的輸出。

對于小數據或者低維數據（特征較少的數據），可能不能產生很好的分類。

隨機森林給人的感覺就像一個黑盒子，無法控制模型內部運行（可控性差）。

1.3其他面試點

為什么隨機抽樣？
保證基分類器的多樣性，若每棵樹的樣本集都一樣，那訓練的每棵決策樹都是一樣

為什么要有放回的抽樣？
保證樣本集間有重疊，若不放回，每個訓練樣本集及其分布都不一樣，可能導致訓練的各決策樹差異性很大，最終多數表決無法 “求同”，即最終多數表決相當于“求同”過程。

為什么不用全樣本訓練？
全樣本忽視了局部樣本的規律，不利于模型泛化能力

為什么要隨機特征？
隨機特征保證基分類器的多樣性（差異性），最終集成的泛化性能可通過個體學習器之間的差異度而進一步提升，從而提高泛化能力和抗噪能力

需要剪枝嗎？
不需要

RF與決策樹的區別？
（1）RF是決策樹的集成；
（2）RF中是“隨機屬性型”決策樹

RF為什么比bagging效率高？
bagging無隨機特征，使得訓練決策樹時效率更低

2.Adaboost

AdaBoost就是損失函數為指數損失的Boosting算法。

2.1加法模型和指數損失函數

2.2原理

分類器權值根據分類的誤差或者正確率來計算。再根據分類器權重求樣本權重。

2.3算法流程

（弱分類器–>計算誤差–>弱分類器權重–>樣本權重–>強分類器）

2.4弱分類器權重公式推導

看這里

2.5優缺點

優點：
1.可使用不同分類器（LR,DT…）作為基分類器
2.精度高

缺點：
1.對異常值敏感
2.基分類器數目（迭代次數）不好設定
3.對樣本不平衡敏感

2.6其他面試點

3.GBDT（梯度提升決策樹）

梯度提升樹(GBDT)原理小結

3.1 原理

GBDT 通過不斷減小訓練過程產生的殘差，以及采用加法模型來達到將數據分類或者回歸的算法。GBDT 通過多輪迭代，每輪迭代產生一個弱分類器，每個分類器在上一輪分類器的殘差基礎上進行訓練，每個弱分類器通過線性疊加成一個強分類器。對弱分類器的要求一般是足夠簡單，并且是低方差和高偏差的。因為訓練的過程是通過降低偏差來不斷提高最終分類器的精度。

GBDT與傳統的Boosting區別較大，它的每一次計算都是為了減少上一次的殘差，而為了消除殘差，我們可以在殘差減小的梯度方向上建立模型,所以說，在GradientBoost中，每個新的模型的建立是為了使得之前的模型的殘差往梯度下降的方法，與傳統的Boosting中關注正確錯誤的樣本加權有著很大的區別。

在GradientBoosting算法中，關鍵就是利用損失函數的負梯度方向在當前模型的值作為殘差的近似值，進而擬合一棵CART回歸樹。

GBDT的會累加所有樹的結果，而這種累加是無法通過分類完成的，因此GBDT的樹都是CART回歸樹，而不是分類樹（盡管GBDT調整后也可以用于分類但不代表GBDT的樹為分類樹）。

3.2GBDT 算法的流程？

3.3GBDT 如何選擇特征 ？

GBDT選擇特征的細節其實是想問你CART Tree（最小基尼指數）生成的過程。這里有一個前提，gbdt的弱分類器默認選擇的是CART TREE。其實也可以選擇其他弱分類器的，選擇的前提是低方差和高偏差。框架服從boosting 框架即可。

3.4GBDT如何構建特征 （GBDT+LR）

參考

邏輯回歸本身是適合處理線性可分的數據，如果我們想讓邏輯回歸處理非線性的數據，其中一種方式便是組合不同特征，增強邏輯回歸對非線性分布的擬合能力。利用gbdt去產生有效的特征組合，以便用于邏輯回歸的訓練，提升模型最終的效果。

其實說GBDT 能夠構建特征并非很準確，GBDT 本身是不能產生特征的，但是我們可以利用GBDT去產生特征的組合。
我們使用 GBDT 生成了兩棵樹，兩顆樹一共有五個葉子節點。我們將樣本 X 輸入到兩顆樹當中去，樣本X 落在了第一棵樹的第二個葉子節點，第二顆樹的第一個葉子節點，于是我們便可以依次構建一個五緯的特征向量，每一個緯度代表了一個葉子節點，樣本落在這個葉子節點上面的話那么值為1，沒有落在該葉子節點的話，那么值為 0.
于是對于該樣本，我們可以得到一個向量[0,1,0,1,0] 作為該樣本的組合特征，和原來的特征一起輸入到邏輯回歸當中進行訓練。實驗證明這樣會得到比較顯著的效果提升。

3.5GBDT 如何用于分類？

看這里
一些注意點：

• GBDT 無論用于分類還是回歸一直都是使用的CART 回歸樹。不會因為我們所選擇的任務是分類任務就選用分類樹，這里面的核心是因為GBDT每輪的訓練是在上一輪的訓練的殘差基礎之上進行訓練的。這里的殘差就是當前模型的負梯度值 。這個要求每輪迭代的時候，弱分類器的輸出的結果相減是有意義的。殘差相減是有意義的。
• 如果選用的弱分類器是分類樹，類別相減是沒有意義的。上一輪輸出的是樣本 x 屬于 A類，本一輪訓練輸出的是樣本 x 屬于 B類。 A 和 B 很多時候甚至都沒有比較的意義，A 類- B類是沒有意義的。
• GBDT 的多分類是針對每個類都獨立訓練一個 CART Tree。

3.6GBDT的優點和局限性

查看《百面機器學習》
優點：

預測階段的計算速度快，樹與樹之間可并行化計算

在分布稠密的數據集上，泛化能力和表達能力都很好

采用決策樹作為弱分類器使得GBDT具有較好的解釋性和魯棒性，能夠自動發現特征間的高階關系，并且不需要對數據進行特殊的數據處理和歸一化等

局限性：

GBDT在高維稀疏的數據集上表現不如支持向量機或者神經網絡

在處理文本分類特征問題上，相對其他模型的優勢不如它在處理數值特征時明顯

訓練過程現需要串行訓練，只能在決策樹內部采用一些局部并行的手段提高訓練速度

3.7梯度提升和梯度下降的區別和聯系

兩者都是在每一輪迭代中，利用損失函數相對于模型的負梯度方向的信息來對當前模型進行更新，只不過在梯度下降中，模型是以參數化形式表示，從而模型的更新等價于參數的更新，而在梯度提升中，模型并不需要進行參數化表示，而是直接定義在損失函數空間中，從而大大擴展了可以使用的模型種類。（見百面機器學習）

3.8RF、GBDT的區別

• 組成隨機森林的數可是分類樹也可以是回歸樹，而GBDT只由回歸樹組成
• 組成隨機森林的數可是并行生成，而GBDT只能是串行生成
• 隨機森林的結果是多棵樹表決決定，而GBDT則是多棵樹累加之和
• 隨機森林對異常值不敏感，而GBDT對異常值比較敏感
• 隨機森林是通過減少模型的方差來提高性能，而GBDT是減少模型的偏差來提高性能

3.9GBDT怎樣設置單棵樹的停止生長條件？

• 節點分裂時的最小樣本數
• 樹的最大深度
• 最多葉子結點數
• Loss滿足約束條件

3.10GBDT如何評估特征的權重大小？

• 計算每個特征在訓練集下的信息增益，最后計算每個特征信息增益與所有特征信息增益之和的比為權重值。
• 借鑒投票機制。用相同的GBDT參數對w每個特征訓練出一個模型，然后在該模型下計算每個特征正確分類的個數，最后計算每個特征正確分類的個數與所有正確分類個數之和的比例為權重值。

3.11GBDT中哪些部分可以并行?

• 計算每個樣本的負梯度時
• 分裂挑選最佳特征及其分割點時，對特征計算相應的誤差及均值時
• 更新每個樣本的負梯度時
• 最后預測的過程當中，每個樣本將之前的所有樹的結果累加的時候

3.12如何防止過擬合？

• 增加樣本，移除噪聲
• 減少特征，保留一些重要的特征
• 對樣本進行采樣，就是在構建樹的時候，不是把所有的樣本都作為輸入，而是選擇一部分數據作為子集
• 對特征進行采樣，和對樣本采樣基本一致，就是在每次建樹的時候只對部分的特征進行切分（XgBoost）

3.13GBDT當增加樣本數量時，訓練時長是線性增加嗎？

NO,因為生成單顆決策樹時，對于 損失函數極小值與樣本數量N不是線性相關

3.14當增加樹的顆數時，訓練時長是線性增加嗎？

NO，因為每顆樹的生成時間復雜度O(N)不同

3.15當增加一個棵樹葉子節點數目時，訓練時長是線性增加嗎？

NO，葉子節點數和每棵樹的生成的時間復雜度O(N)不成正比

3.16每個節點上都保存什么信息？

中間節點保存某個特征的分割值，葉節點保存預測是某個類別的概率

4.XgBoost

這個寫得超詳細。
還有這個
原始的GBDT算法基于經驗損失函數的負梯度來構建新的決策樹，只是在局測試構建完成后再進行剪枝。而XGboost在決策樹構建階段就加入正則項，起到一定預剪枝的作用。正則項包括兩部分，T表示葉子結點的個數，w表示葉子節點的分數。γ可以控制葉子結點的個數，λ可以控制葉子節點的分數不會過大，防止過擬合。
損失函數為：

正則項為：

4.1XgBoost有哪些特點

每個葉子節點的值w是最優化求出來的，不是啥平均值或規則指定的，這個算是一個思路上的新穎吧；

正則化防止過擬合的技術，上述看到了，直接loss function里面就有；

支持自定義loss function，只要能泰勒展開（能求一階導和二階導）就行；

可實現后剪枝

xgboost還支持設置樣本權重，這個權重體現在梯度g和二階梯度h上，是不是有點adaboost的意思，重點關注某些樣本

Shrinkage，你可以是幾個回歸樹的葉子節點之和為預測值，也可以是加權，比如第一棵樹預測值為3.3，label為4.0，第二棵樹才學0.7，….再后面的樹還學個鬼，所以給他打個折扣，比如3折，那么第二棵樹訓練的殘差為4.0-3.3*0.3=3.01，這就可以發揮了啦，以此類推，作用是啥，防止過擬合，如果對于“偽殘差”學習，那更像梯度下降里面的學習率；
（以下4.2，4.3，4.4也是XgBoost的特點）

4.2對于連續值如何進行分割？

方法名字：Weighted Quantile Sketch
以收入為例：每個樣本在節點（將要分裂的節點）處的loss function一階導數gi和二階導數hi，衡量預測值變化帶來的loss function變化，舉例來說，將樣本“月收入”進行升序排列，5k、5.2k、5.3k、…、52k，分割線為“收入1”、“收入2”、…、“收入j”，滿足(每個間隔的樣本的hi之和/總樣本的hi之和）為某個百分比?（我這個是近似的說法），那么可以一共分成大約1/?個分裂點。

4.3對于特征缺失值如何分類？

假設樣本的第i個特征缺失時，無法利用該特征對樣本進行劃分，這里的做法是將該樣本默認地分到指定的子節點，至于具體地分到哪個節點還需要某算法來計算，算法的主要思想是，分別假設特征缺失的樣本屬于右子樹和左子樹，而且只在不缺失的樣本上迭代，分別計算缺失樣本屬于右子樹和左子樹的增益，選擇增益最大的方向為缺失數據的默認方向，論文中“枚舉”指的不是枚舉每個缺失樣本在左邊還是在右邊，而是枚舉缺失樣本整體在左邊，還是在右邊兩種情況。 分裂點還是只評估特征不缺失的樣本。

4.4XGBoost怎么做到并行化

這個地方有必要說明下，因為這是xgboost的閃光點，直接的效果是訓練速度快，boosting技術中下一棵樹依賴上述樹的訓練和預測，所以樹與樹之間應該是只能串行！但在在選擇最佳分裂點，進行枚舉的時候并行！（據說恰好這個也是樹形成最耗時的階段）。XGBoost的并行是在特征粒度上的。我們知道，決策樹的學習最耗時的一個步驟就是對特征的值進行排序（因為要確定最佳分割點），XGBoost在訓練之前，預先對數據進行了排序，然后保存為block結構，后面的迭代中重復地使用這個結構，大大減小計算量。這個block結構也使得并行成為了可能，在進行節點的分裂時，需要計算每個特征的增益，最終選增益最大的那個特征去做分裂，那么各個特征的增益計算就可以開多線程進行。

4.5XgBoost和GBDT的區別和聯系

（2二階導數+3基分類器+4缺失值）（防止過擬合：1正則項+5特征采樣+6縮減）

在使用CART作為基分類器的時候，XGBoost加入正則項來控制模型的復雜度，從權衡方差偏差來看，它降低了模型的方差，有利于防止過擬合，提高模型泛化能力

GBDT在模型訓練的時候只使用代價函數的一階導數信息，XGBoost對代價函數進行二階泰勒展開，可以同時使用一階和二階導數

傳統的GBDT采用CART作為基分類器，XGBoost支持多種類型的基分類器，比如線性分類器，這個時候XGBoost相當于L1和L2正則化的邏輯斯蒂回歸（分類）或者線性回歸（回歸）

GBDT沒有設計對缺失值的處理，XGBoost能夠自動學習出缺失值的處理策略

GBDT在每輪迭代時使用全部的數據，XGBoost采用與隨機森林相似的策略，支持對數據進行列采樣（列抽樣即隨機特征采樣），不僅防止過擬合，還能減少計算

shrinkage（縮減），相當于學習速率（XGBoost中的eta）。XGBoost在進行完一次迭代時，會將葉子節點的權值乘上該系數，主要是為了削弱每棵樹的影響，讓后面有更大的學習空間。（GBDT也有學習速率）

4.6.XGBoost和深度學習的區別？

Xgboost第一感覺就是防止過擬合+各種支持分布式/并行，所以一般傳言這種大殺器效果好（集成學習的高配）+訓練效率高（分布式），與深度學習相比，對樣本量和特征數據類型要求沒那么苛刻，適用范圍廣。
不同的機器學習模型適用于不同類型的任務。深度神經網絡通過對時空位置建模，能夠很好地捕獲圖像、語音、文本等高維數據。而基于樹模型的XGBoost則能很好地處理表格數據，同時還擁有一些深度神經網絡所沒有的特性（如：模型的可解釋性、輸入數據的不變性、更易于調參等）。

4.7.xgboost為什么使用二階泰勒展開

關于Xgboost用泰勒二階展開的原因，主要有兩點：

• Xgboost官網上有說，當目標函數是MSE時，展開是一階項（殘差）+二階項的形式（官網說這是一個nice form），而其他目標函數，如logloss的展開式就沒有這樣的形式。為了能有個統一的形式，所以采用泰勒展開來得到二階項，這樣就能把MSE推導的那套直接復用到其他自定義損失函數上。簡短來說，就是為了統一損失函數求導的形式以支持自定義損失函數。這是從為什么會想到引入泰勒二階的角度來說的。
• 二階信息本身就能讓梯度收斂更快更準確。這一點在優化算法里的牛頓法里已經證實了?？梢院唵握J為一階導指引梯度方向，二階導指引梯度方向如何變化。這是從二階導本身的性質，也就是為什么要用泰勒二階展開的角度來說的。

P.S.為什么要在形式上與MSE統一？因為MSE是最普遍且常用的損失函數，而且求導最容易，求導后的形式也十分簡單。所以理論上只要損失函數形式與MSE統一了，那就只用推導MSE就好啦

5.lightGBM

5.1LGB原理

參考
XGB采用了直方圖加速，只需要遍歷幾個可能的分裂節點就好了！它也不需要計算所有樣本吖！

這里的意思是，XGB雖然每次只需要遍歷幾個可能的分裂節點，然后比較每個分裂節點的信息增益，選擇最大的那個進行分割，但比較時需要考慮所有樣本帶來的信息增益。而LGB只需采用少量的樣本計算信息增益，所以速度會快很多。

那么問題就來了，XGB如果選少量的樣本算信息增益，該如何保證把信息損失降到最低呢？
LGB選擇梯度大的樣本來計算信息增益。如果一個樣本的梯度較小，證明這個樣本訓練的誤差已經很小了，所以不需要計算了。我們在XGB的那篇文章中說過，GBDT的梯度算出來實際上就是殘差，梯度小殘差就小，所以該樣本擬合較好，不需要去擬合他們了。

這聽起來仿佛很有道理，但問題是丟掉他們會改變數據的分布，還是無法避免信息損失，進而導致精度下降，所以LGB提出了一個很樸實無華且枯燥的方法進行優化。
LGB的優化方法是，在保留大梯度樣本的同時，隨機地保留一些小梯度樣本，同時放大了小梯度樣本帶來的信息增益。

除了通過部分樣本計算信息增益以外，LGB還內置了特征降維技術，思想就是合并那些沖突小的稀疏特征。
舉個例子，對于一列特征[1,nan,1,nan,1]和一列特征[nan,1,nan,1,nan]，他們正好可以合并成一列特征[1,2,1,2,1]。LGB的目標就是在于找到這樣的特征并且將他們合并在一起。

至于LGB為什么比XGB的精度高這一點，我的理解是選擇梯度大(殘差大)樣本來進行特征分裂生成的樹，借鑒了Adaboost的更改樣本權重的思想。每棵樹針對某些特定訓練樣本有著較好的劃分能力，導致每棵樹之間的異質性較大，對于效果近似但異質性大的模型加權往往會帶來更大的提升。

5.2.XGboost的不足之處

1）每輪迭代時，都需要遍歷整個訓練數據多次。如果把整個訓練數據裝進內存則會限制訓練數據的大小；如果不裝進內存，反復地讀寫訓練數據又會消耗非常大的時間。
2）預排序方法的時間和空間的消耗都很大

LGBM最大的優勢就是快。

5.3.XGBoost和LGBM樹的生長方式

• XGBoost按層生長的方式，有利于工程優化，但對學習模型效率不高
• LightGBM是直接去選擇獲得最大收益的結點來展開，這樣呢LightGBM能夠在更小的計算代價上建立我們需要的決策樹。當然在這樣的算法中我們也需要控制樹的深度和每個葉子結點的最小數據量，從而減少過擬合。

5.4.XGBoost和LGBM樹的劃分方式

• XGBoost中采用預排序的方法，計算過程當中是按照value的排序，逐個數據樣本來計算劃分收益，這樣的算法能夠精確的找到最佳劃分值，但是代價比較大同時也沒有較好的推廣性。
• LightGBM直方圖算法：將這些精確的連續的每一個value劃分到一系列離散的域中，也就是筒子里。以浮點型數據來舉例，一個區間的值會被作為一個筒，然后以這些筒為精度單位的直方圖來做。這樣一來，數據的表達變得更加簡化，減少了內存的使用，而且直方圖帶來了一定的正則化的效果，能夠使我們做出來的模型避免過擬合且具有更好的推廣性。另外數據結構的變化使得在細節處的變化理上效率會不同.
  按照bin來索引“直方圖”，所以不用按照每個“特征”來排序，也不用一一去對比不同“特征”的值，大大的減少了運算量。

5.5.支持類別特征

傳統的機器學習一般不能支持直接輸入類別特征，需要先轉化成多維的0-1特征，這樣無論在空間上還是時間上效率都不高。LightGBM通過更改決策樹算法的決策規則，直接原生支持類別特征，不需要轉化，提高了近8倍的速度

5.6.支持并行學習

參考
LightGBM原生支持并行學習，目前支持特征并行(Featrue Parallelization)和數據并行(Data Parallelization)兩種，還有一種是基于投票的數據并行(Voting Parallelization)

• 特征并行的主要思想是在不同機器、在不同的特征集合上分別尋找最優的分割點，然后在機器間同步最優的分割點。
• 數據并行則是讓不同的機器先在本地構造直方圖，然后進行全局的合并，最后在合并的直方圖上面尋找最優分割點。

LightGBM針對這兩種并行方法都做了優化。

• 特征并行算法中，通過在本地保存全部數據避免對數據切分結果的通信。
• 數據并行中使用分散規約 (Reduce scatter) 把直方圖合并的任務分攤到不同的機器，降低通信和計算，并利用直方圖做差，進一步減少了一半的通信量。
• 基于投票的數據并行(Voting Parallelization)則進一步優化數據并行中的通信代價，使通信代價變成常數級別。在數據量很大的時候，使用投票并行可以得到非常好的加速效果。

5.7lightGBM與XGboost對比

1、xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，區別是xgboost對每一層所有節點做無差別分裂，可能有些節點的增益非常小，對結果影響不大，但是xgboost也進行了分裂，帶來了不必要的開銷。 leaft-wise的做法是在當前所有葉子節點中選擇分裂收益最大的節點進行分裂，如此遞歸進行，很明顯leaf-wise這種做法容易過擬合，因為容易陷入比較高的深度中，因此需要對最大深度做限制，從而避免過擬合。
　　
2、lightgbm使用了基于histogram直方圖的決策樹算法，這一點不同于xgboost中的 exact預排序算法，histogram算法在內存和計算代價上都有不小優勢。

• 內存上優勢：很明顯，直方圖算法的內存消耗為(#data* #features * 1Bytes)(因為對特征分桶后只需保存特征離散化之后的值)，而xgboost的預排序算法內存消耗為：(2 * #data * #features* 4Bytes)，因為xgboost既要保存原始feature的值，也要保存這個值的順序索引，這些值需要32位的浮點數來保存。
• 計算上的優勢，預排序算法在選擇好分裂特征計算分裂收益時需要遍歷所有樣本，時間為(#data)，而直方圖算法只需要遍歷桶就行了，時間為(#bin)

5.8直方圖算法

總結

以上是生活随笔為你收集整理的一天1个机器学习知识点（四）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。