XGB

算法思想就是不斷地添加樹，不斷地進行特征分裂來生長一棵樹，每次添加一個樹，其實是學習一個新函數，去拟合上次預測的殘差。當我們訓練完成得到k棵樹，我們要預測一個樣本的分數，其實就是根據這個樣本的特征，在每棵樹中會落到對應的一個葉子節點，每個葉子節點就對應一個分數，最後隻需要将每棵樹對應的分數加起來就是該樣本的預測值。

注：w_q(x)為葉子節點q的分數，f(x)為其中一棵回歸樹

如下圖例子，訓練出了2棵決策樹，小孩的預測分數就是兩棵樹中小孩所落到的結點的分數相加。爺爺的預測分數同理。

3.損失函數

　　　　對于回歸問題，我們常用的損失函數是MSE，即：

對于分類問題，我們常用的損失函數是對數損失函數：

XGBoost目标函數定義為：

目标函數由兩部分構成，第一部分用來衡量預測分數和真實分數的差距，另一部分則是正則化項。正則化項同樣包含兩部分，T表示葉子結點的個數，w表示葉子節點的分數。γ可以控制葉子結點的個數，λ可以控制葉子節點的分數不會過大，防止過拟合。

正如上文所說，新生成的樹是要拟合上次預測的殘差的，即當生成t棵樹後，預測分數可以寫成：

同時，可以将目标函數改寫成：

很明顯，我們接下來就是要去找到一個f_t能夠最小化目标函數。XGBoost的想法是利用其在f_t=0處的泰勒二階展開近似它。是以，目标函數近似為：

其中g_i為一階導數，h_i為二階導數：

由于前t-1棵樹的預測分數與y的殘差對目标函數優化不影響，可以直接去掉。簡化目标函數為：

上式是将每個樣本的損失函數值加起來，我們知道，每個樣本都最終會落到一個葉子結點中，是以我們可以将是以同一個葉子結點的樣本重組起來，過程如下圖：

是以通過上式的改寫，我們可以将目标函數改寫成關于葉子結點分數w的一個一進制二次函數，求解最優的w和目标函數值就變得很簡單了，直接使用頂點公式即可。是以，最優的w和目标函數公式為

4.分裂結點算法

　　在上面的推導中，我們知道了如果我們一棵樹的結構确定了，如何求得每個葉子結點的分數。但我們還沒介紹如何确定樹結構，即每次特征分裂怎麼尋找最佳特征，怎麼尋找最佳分裂點。

正如上文說到，基于空間切分去構造一顆決策樹是一個NP難問題，我們不可能去周遊所有樹結構，是以，XGBoost使用了和CART回歸樹一樣的想法，利用貪婪算法，周遊所有特征的所有特征劃分點，不同的是使用上式目标函數值作為評價函數。具體做法就是分裂後的目标函數值比單子葉子節點的目标函數的增益，同時為了限制樹生長過深，還加了個門檻值，隻有當增益大于該門檻值才進行分裂。

5.正則化

xgboost使用了如下的正則化項：

注意：這裡出現了γ和λ，這是xgboost自己定義的，在使用xgboost時，你可以設定它們的值，顯然，γ越大，表示越希望獲得結構簡單的樹，因為此時對較多葉子節點的樹的懲罰越大。λ越大也是越希望獲得結構簡單的樹。

為什麼xgboost要選擇這樣的正則化項？很簡單，好使！效果好才是真的好。

6.對缺失值處理

　　 xgboost模型卻能夠處理缺失值，模型允許缺失值存在。

原始論文中關于缺失值的處理将其看與稀疏矩陣的處理看作一樣。在尋找split point的時候，不會對該特征為missing的樣本進行周遊統計，隻對該列特征值為non-missing的樣本上對應的特征值進行周遊，通過這個技巧來減少了為稀疏離散特征尋找split point的時間開銷。在邏輯實作上，為了保證完備性，會分别處理将missing該特征值的樣本配置設定到左葉子結點和右葉子結點的兩種情形，計算增益後選擇增益大的方向進行分裂即可。可以為缺失值或者指定的值指定分支的預設方向，這能大大提升算法的效率。如果在訓練中沒有缺失值而在預測中出現缺失，那麼會自動将缺失值的劃分方向放到右子樹。

7.優缺點

　　優點：

1） xgBoosting支援線性分類器，相當于引入L1和L2正則化項的邏輯回歸（分類問題）和線性回歸（回歸問題）；

2） xgBoosting對代價函數做了二階Talor展開，引入了一階導數和二階導數；

3）當樣本存在缺失值是，xgBoosting能自動學習分裂方向；

4）xgBoosting借鑒RF的做法，支援列抽樣，這樣不僅能防止過拟合，還能降低計算；

5）xgBoosting的代價函數引入正則化項，控制了模型的複雜度，正則化項包含全部葉子節點的個數，每個葉子節點輸出的score的L2模的平方和。從貝葉斯方差角度考慮，正則項降低了模型的方差，防止模型過拟合；

6）xgBoosting在每次疊代之後，為葉子結點配置設定學習速率，降低每棵樹的權重，減少每棵樹的影響，為後面提供更好的學習空間；

7）xgBoosting工具支援并行,但并不是tree粒度上的，而是特征粒度，決策樹最耗時的步驟是對特征的值排序，xgBoosting在疊代之前，先進行預排序，存為block結構，每次疊代，重複使用該結構，降低了模型的計算；block結構也為模型提供了并行可能，在進行結點的分裂時，計算每個特征的增益，選增益最大的特征進行下一步分裂，那麼各個特征的增益可以開多線程進行；

8）可并行的近似直方圖算法，樹結點在進行分裂時，需要計算每個節點的增益，若資料量較大，對所有節點的特征進行排序，周遊的得到最優分割點，這種貪心法異常耗時，這時引進近似直方圖算法，用于生成高效的分割點，即用分裂後的某種值減去分裂前的某種值，獲得增益，為了限制樹的增長，引入門檻值，當增益大于門檻值時，進行分裂；

缺點：

1）xgBoosting采用預排序，在疊代之前，對結點的特征做預排序，周遊選擇最優分割點，資料量大時，貪心法耗時，LightGBM方法采用histogram算法，占用的記憶體低，資料分割的複雜度更低；

2）xgBoosting采用level-wise生成決策樹，同時分裂同一層的葉子，進而進行多線程優化，不容易過拟合，但很多葉子節點的分裂增益較低，沒必要進行跟進一步的分裂，這就帶來了不必要的開銷；LightGBM采用深度優化，leaf-wise生長政策，每次從目前葉子中選擇增益最大的結點進行分裂，循環疊代，但會生長出更深的決策樹，産生過拟合，是以引入了一個門檻值進行限制，防止過拟合.

8.sklearn參數

1. eta [預設 0.3]

和 GBM 中的 learning rate 參數類似。 通過減少每一步的權重，可以提高模型的穩定性。 典型值為 0.01-0.2。

1. min_child_weight [預設 1]

決定最小葉子節點樣本權重和。和 GBM 的 min_child_leaf 參數類似，但不完全一樣。XGBoost 的這個參數是最小樣本權重的和，而 GBM 參數是最小樣本總數。這個參數用于避免過拟合。當它的值較大時，可以避免模型學習到局部的特殊樣本。但是如果這個值過高，會導緻欠拟合。這個參數需要使用 CV 來調整。

1. max_depth [預設 6]

和 GBM 中的參數相同，這個值為樹的最大深度。這個值也是用來避免過拟合的。max_depth 越大，模型會學到更具體更局部的樣本。需要使用 CV 函數來進行調優。 典型值：3-10

1. max_leaf_nodes

樹上最大的節點或葉子的數量。 可以替代 max_depth 的作用。因為如果生成的是二叉樹，一個深度為 n 的樹最多生成 n2 個葉子。 如果定義了這個參數，GBM 會忽略 max_depth 參數。

1. gamma [預設 0]

在節點分裂時，隻有分裂後損失函數的值下降了，才會分裂這個節點。Gamma 指定了節點分裂所需的最小損失函數下降值。 這個參數的值越大，算法越保守。這個參數的值和損失函數息息相關，是以是需要調整的。

6、max_delta_step[預設 0]

這參數限制每棵樹權重改變的最大步長。如果這個參數的值為 0，那就意味着沒有限制。如果它被賦予了某個正值，那麼它會讓這個算法更加保守。 通常，這個參數不需要設定。但是當各類别的樣本十分不平衡時，它對邏輯回歸是很有幫助的。 這個參數一般用不到，但是你可以挖掘出來它更多的用處。

1. subsample [預設 1]

和 GBM 中的 subsample 參數一模一樣。這個參數控制對于每棵樹，随機采樣的比例。 減小這個參數的值，算法會更加保守，避免過拟合。但是，如果這個值設定得過小，它可能會導緻欠拟合。 典型值：0.5-1

1. colsample_bytree [預設 1]

和 GBM 裡面的 max_features 參數類似。用來控制每棵随機采樣的列數的占比 (每一列是一個特征)。 典型值：0.5-1

1. colsample_bylevel [預設 1]

用來控制樹的每一級的每一次分裂，對列數的采樣的占比。 我個人一般不太用這個參數，因為 subsample 參數和 colsample_bytree 參數可以起到相同的作用。但是如果感興趣，可以挖掘這個參數更多的用處。

1. lambda [預設 1]

權重的 L2 正則化項。(和 Ridge regression 類似)。 這個參數是用來控制 XGBoost 的正則化部分的。雖然大部分資料科學家很少用到這個參數，但是這個參數在減少過拟合上還是可以挖掘出更多用處的。

1. alpha [預設 1]

權重的 L1 正則化項。(和 Lasso regression 類似)。 可以應用在很高次元的情況下，使得算法的速度更快。

1. scale_pos_weight [預設 1]

在各類别樣本十分不平衡時，把這個參數設定為一個正值，可以使算法更快收斂。

學習目标參數

這個參數用來控制理想的優化目标和每一步結果的度量方法。

1. objective [預設 reg:linear]

這個參數定義需要被最小化的損失函數。最常用的值有：

binary:logistic 二分類的邏輯回歸，傳回預測的機率 (不是類别)。 multi:softmax 使用 softmax 的多分類器，傳回預測的類别 (不是機率)。

在這種情況下，你還需要多設一個參數：num_class(類别數目)。 multi:softprob 和 multi:softmax 參數一樣，但是傳回的是每個資料屬于各個類别的機率。

1. eval_metric [預設值取決于 objective 參數的取值]

1. seed [預設 0]