工程實現(xiàn)

塊結構設計

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

• 每一個塊結構包括一個或多個已經(jīng)排序好的特征；
• 缺失特征值將不進行排序；
• 每個特征會存儲指向樣本梯度統(tǒng)計值的索引，方便計算一階導和二階導數(shù)值；

這種塊結構存儲的特征之間相互獨立，方便計算機進行并行計算。在對節(jié)點進行分裂時需要選擇增益最大的特征作為分裂，這時各個特征的增益計算可以同時進行，這也是 Xgboost 能夠?qū)崿F(xiàn)分布式或者多線程計算的原因。

緩存訪問優(yōu)化算法

塊結構的設計可以減少節(jié)點分裂時的計算量，但特征值通過索引訪問樣本梯度統(tǒng)計值的設計會導致訪問操作的內(nèi)存空間不連續(xù)，這樣會造成緩存命中率低，從而影響到算法的效率。

為了解決緩存命中率低的問題，XGBoost 提出了緩存訪問優(yōu)化算法：為每個線程分配一個連續(xù)的緩存區(qū)，將需要的梯度信息存放在緩沖區(qū)中，這樣就是實現(xiàn)了非連續(xù)空間到連續(xù)空間的轉(zhuǎn)換，提高了算法效率。

此外適當調(diào)整塊大小，也可以有助于緩存優(yōu)化。

“核外”塊計算

當數(shù)據(jù)量過大時無法將數(shù)據(jù)全部加載到內(nèi)存中，只能先將無法加載到內(nèi)存中的數(shù)據(jù)暫存到硬盤中，直到需要時再進行加載計算，而這種操作必然涉及到因內(nèi)存與硬盤速度不同而造成的資源浪費和性能瓶頸。為了解決這個問題，XGBoost 獨立一個線程專門用于從硬盤讀入數(shù)據(jù)，以實現(xiàn)處理數(shù)據(jù)和讀入數(shù)據(jù)同時進行。

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

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

優(yōu)點：

精度更高：GBDT 只用到一階泰勒展開，而 XGBoost 對損失函數(shù)進行了二階泰勒展開。XGBoost
引入二階導一方面是為了增加精度，另一方面也是為了能夠自定義損失函數(shù)，二階泰勒展開可以近似大量損失函數(shù)；

靈活性更強：GBDT 以 CART 作為基分類器，XGBoost 不僅支持 CART 還支持線性分類器，（使用線性分類器的
XGBoost 相當于帶 L1 和 L2 正則化項的邏輯斯蒂回歸（分類問題）或者線性回歸（回歸問題））。此外，XGBoost
工具支持自定義損失函數(shù)，只需函數(shù)支持一階和二階求導；

正則化：XGBoost 在目標函數(shù)中加入了正則項，用于控制模型的復雜度。正則項里包含了樹的葉子節(jié)點個數(shù)、葉子節(jié)點權重的 L2
范式。正則項降低了模型的方差，使學習出來的模型更加簡單，有助于防止過擬合；

Shrinkage（縮減）：相當于學習速率。XGBoost
在進行完一次迭代后，會將葉子節(jié)點的權重乘上該系數(shù)，主要是為了削弱每棵樹的影響，讓后面有更大的學習空間；

列抽樣：XGBoost 借鑒了隨機森林的做法，支持列抽樣，不僅能降低過擬合，還能減少計算；

缺失值處理：XGBoost 采用的稀疏感知算法極大的加快了節(jié)點分裂的速度；

可以并行化操作：塊結構可以很好的支持并行計算。

缺點：

雖然利用預排序和近似算法可以降低尋找最佳分裂點的計算量，但在節(jié)點分裂過程中仍需要遍歷數(shù)據(jù)集；

預排序過程的空間復雜度過高，不僅需要存儲特征值，還需要存儲特征對應樣本的梯度統(tǒng)計值的索引，相當于消耗了兩倍的內(nèi)存。

總結

以上是生活随笔為你收集整理的XGBoost-工程实现与优缺点（中）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。