基于梯度分布調節策略的Xgboost算法優化

李 浩，朱 焱

（西南交通大學信息科學與技術學院，成都 611756）

（?通信作者電子郵箱yzhu@swjtu.edu.cn）

0 引言

在機器學習、模式識別等領域中，不平衡二分類問題一直是非常重要的研究課題。在現實生活中，不平衡數據存在于方方面面，如病毒檢測、垃圾網頁檢測等。其特點是多數類的數據量一般遠遠多于少數類的數據量，數據呈現不平衡的分布狀態。但是在許多不平衡分類問題中，少數類通常是更重要的。例如在垃圾檢測領域中，垃圾網頁的數據量遠遠少于正常網頁的數據量。但相對正常網頁，垃圾網頁的漏檢、誤檢往往會給社會帶來更多的危害，帶來更大的損失。因此，如何提高對少數類的分類準確率，減小少數類分類錯誤帶來的損失，是數據挖掘中迫切需要解決的問題。Xgboost（eXtreme gradient boosting）算法是近年來興起的一種高效集成學習算法，但是它在不平衡二分類問題上的表現卻不令人滿意。這是因為當多數類樣本量遠遠多于少數類時，多數類的損失量占比將會遠大于少數類，這導致Xgboost在建模時會偏重對多數類的學習，忽視少數類，從而降低Xgboost分類性能。

為了解決Xgboost 在二分類問題中少數類檢出率低的問題，許多改進的算法被提出。Luo 等［1］提出以Xgboost 作為基分類器，結合欠采樣和Tomek-Link 技術構造集成學習分類器。但是該方法是局限在樣本集上的改進，對Xgboost算法本身并未改進；而且欠采樣和Tomek-Link 技術會使得數據集有信息損失，從而可能導致最終的分類結果不理想。Shi 等［2］基于帶權重的Xgboost構建了二層分類檢測模型；但是該模型中針對Xgboost的權重計算方式過于簡單，僅考慮了同類別樣本數量的占比，且權重大小恒定不變，沒有很好地平衡不同類別樣本的損失量。Chen 等［3］提出了基于IEEM（Interval Error Evaluation Method）對于不同的樣本使用分段劃等級的方式給予不同的重要性，從而提高了算法對少數類的關注；但是人為指定樣本等級過于主觀，容易造成較大的誤差。Li 等［5］針對少數類樣本提出了基于梯度密度的調節策略，在神經網絡使用梯度下降法學習數據的過程中，調節樣本的梯度分布，增大少數類樣本的梯度，減小多數類樣本的梯度，從而提高神經網絡對少數類樣本的檢出能力。正是受文獻［5］的啟發，本文提出 了 LCGHA （Loss Contribution Gradient Harmonized Algorithm）-Xgboost 算法，LCGHA-Xgboost 算法流程如圖1 所示，該算法不僅提高了Xgboost 的性能，而且實現更加自動化和智能化。

LCGHA-Xgboost 算法關注數據集中的難分樣本，這些樣本絕大部分存在于因為數量過少而導致難以被正確分類的少數類中，還有部分存在于多數類中；因此本文方法對少數類和多數類的學習能力都有較大提升，對算法性能的提升效果更加出色。LCGHA 梯度調節算法定義損失貢獻密度來衡量樣本被正確分類的難易程度。依據損失貢獻密度，動態調整樣本一階梯度分布，間接提高難分樣本損失量在總損失量中的占比，使Xgboost 偏重對難分樣本的學習，從而提高Xgboost 的分類能力。

圖1 LCGHA-Xgboost算法流程Fig.1 Flowchart of LCGHA-Xgboost algorithm

本文算法LCGHA-Xgboost與文獻［2］算法和文獻［3］算法的不同之處在于本文算法關注數據集中難分樣本，算法作用范圍更加廣泛；并且本文算法對不同樣本的關注度隨模型訓練的過程而變化，可以更好地擬合數據集樣本，提高Xgboost分類能力。本文與文獻［5］同樣研究了梯度不平衡調節策略，但本文的損失貢獻密度可以更好地衡量樣本被正確分類的難易程度，更準確地識別難分樣本和易分樣本，從而進行更加合理的梯度調整。

通過在UCI 數據集、WebSpam-UK2007 和DC2010 等多個數據集上進行實驗驗證得出，LCGHA 梯度調節算法有效地提高了Xgboost 對少數類樣本的檢出能力，增強了Xgboost 算法性能。

1 相關技術

1.1 Xgboost算法原理及模型介紹

Xgboost 是由Chen 等［9］提出的一種集成學習算法。它在GBDT（Gradient Boosting Decision Tree）的基礎上，通過改進模型擬合目標，在目標函數中添加正則項，進一步優化了性能。因為GBDT 算法在優化損失函數時只使用了一階導數信息，而Xgboost算法則是對損失函數進行了二階泰勒展開，利用了一階導數和二階導數信息，從而能更好地擬合損失函數，減小優化過程中存在的誤差。具體定義如下所示。

已知一個訓練數據集D={(x1，y1)，(x2，y2)，…，(xn，yn)}，xi∈X?Rm，yi∈Y?R，X為輸入空間，Y為輸出空間。Xgboost可以表示成加法模型，即：

式中：表示訓練模型的預測值；fk表示第k個子模型；xi表示第i個輸入樣本。Xgboost算法的優化目標包括損失函數和正則項兩個部分，因此最終的優化目標為：

式中：L(t)表示第t次迭代時的目標函數；yi表示原始樣本類標；(t-1)表示樣本在t-1 次模型迭代時，模型的預測值；ft(xi)表示樣本在第t次模型迭代時，模型的預測值；H(ft)是目標函數的正則項。

對式（2）泰勒展開，可得：

式中：gi表示樣本xi的一階梯度；hi表示樣本xi的二階梯度；ω j表示第j個節點的輸出值；λ和γ是正則項系數，防止模型過擬合；Ij是第j個葉節點中的樣本子集。

Xgboost 模型的訓練過程就是求解式（3），找到最佳的及其對應的目標函數最優解，即：

式（5）用來衡量一棵樹的結構好壞，其值越低，代表樹的結構越好。因此當樹分裂節點時，可以得到式（6）：

如果Gain值大于零，則繼續分裂節點；否則停止分裂節點。

1.2 梯度分布定義

在使用梯度下降法或牛頓法建模時，需要計算樣本一階梯度或二階梯度。但是在同一個損失函數下，不同樣本的梯度分布往往是不同的，因此有了梯度分布的概念。

定義 1梯度分布 。已知樣本集D={(x1，y1)，(x2，y2)，…，(xn，yn)}，xi∈X?Rm，yi∈Y?R，X為輸入空間，Y為輸出空間。樣本集D的一階梯度集合G={g1，g2，…，gn}，gi為樣本xi的梯度。

其中：gi代表樣本xi的梯度；gj∈G；χ(gi，gj)表示樣本x的梯度值是否落在以gi為中心、ε為半徑的區域內；δ(xi)表示樣本集D中落在以gi為中心、ε為半徑的樣本數。則Φ={δ(x1)，δ(x2)，…，δ(xn)}表示樣本D內每個樣本的梯度分布。由定義1可以得出樣本集總體的梯度分布情況。

2 基于梯度分布調節策略的改進Xgboost算法

Xgboost 在許多分類問題上表現都十分出色，但是在垃圾網頁、故障檢測等數據不平衡的領域中，對難分樣本的檢出能力較差，分類性能較低。為了提高Xgboost對難分樣本的檢出能力，本文定義了損失貢獻和損失貢獻密度，提出LCGHAXgboost 算法。以損失貢獻模擬樣本損失量，以損失貢獻密度衡量樣本被正確分類的難易程度。依據損失貢獻密度調節樣本一階梯度gi的分布情況，達到間接提高難分樣本損失量的目的，從而增強算法對難分樣本的關注和學習，提高Xgboost的分類性能。

樣本損失貢獻（Loss Contribution，LC）的具體定義如下：

即損失貢獻表現為以樣本xi的二階梯度的平方除以一階度。損失貢獻分布定義如下。

定義 2損失貢獻分布。已知樣本集D={(x1，y1)，(x2，y2)，…，(xn，yn)}，xi∈X?Rm，yi∈Y?R，X為輸入空間，Y為輸出空間。樣本集D的損失貢獻集合LC_Set={LC1，LC2，…，LCn}，LCi表示樣本xi的損失貢獻。

其中：χ(LCi，LCj)表示樣本xi的損失貢獻是否落在以LCi為中心、ε為半徑的區域內；δ(xi)表示樣本集D中落在以LCi為中心、ε為半徑的樣本數。則Ω={δ(x1)，δ(x2)，…，δ(xn)}表示樣本集D內樣本的損失貢獻分布。相較定義1，定義2是為了統計樣本集總體的損失貢獻分布情況。

損失貢獻密度（Loss Contribution Density，LCD）定義如下。

定義 3損失貢獻密度。已知樣本集D={(x1，y1)，(x2，y2)，…，(xn，yn)}，xi∈X?Rm，yi∈Y?R，X為輸入空間，Y為輸出空間。N代表樣本D的樣本數量；LCD(xi)表示樣本xi的損失貢獻密度。樣本集D的損失貢獻分布Ω={δ(x1)，δ(x2)，…，δ(xn)}，δ(xi)表示樣本xi損失貢獻分布。

樣本xi損失貢獻密度是樣本的δ(xi)值除以總樣本數的商，依據定義3 可以得到個體樣本損失貢獻分布區域的稀疏情況。樣本xi的損失貢獻密度越大，代表在樣本xi附近與其損失貢獻相近的樣本就越多。這部分樣本損失量占比就會越高，就會越發受到算法的關注和學習，因此越容易被算法正確檢出。反之，樣本xi的損失貢獻密度越小，就越難被算法正確檢出。

使用損失貢獻密度可以很好地衡量樣本被正確分類的難易程度。想要提高對難分樣本的檢出能力，只需要通過調整樣本的一階梯度分布的方式，來間接地調整樣本在式（5）中的損失量，具體定義如下。

難分樣本由于其LCD 值遠小于易分樣本的LCD 值，經過式（13）調整后，其一階梯度的增幅會大于易分樣本，從而間接導致式（5）中難分樣本損失量增幅會大于易分樣本的增幅，最終使得Xgboost 偏向關注對難分樣本的學習和分類。具體算法過程如下所示。

算法1 LCGHA。

算法1 會在每個基分類器訓練完成后，動態調整樣本的一階梯度分布。訓練下一棵樹時，算法就會著重關注難分樣本。LCGHA-Xgboost算法的具體過程如下：

算法2 LCGHA-Xgboost。

3 LCGHA-Xgboost性能驗證與分析

3.1 實驗數據集

為了檢驗算法性能優劣，本文選擇了多個UCI數據集，它們有不同的不平衡比例。這些數據集來自于UCI 數據庫，是加州大學歐文分校（University of California，Irvine）提出的用于機器學習的數據庫，而UCI 數據集是一個常用的標準測試數據集（網址為：https：//archive.ics.uci.edu/ml/index.php）。數據集數據分布如表1所示。

表1 UCI數據集數據分布Tab.1 Data distribution of UCI datasets

此外本文還選擇了樣本更多、不平衡率更大的WebSpam-UK2007［11］和DC2010［12］作為本次的實驗數據集。WebSpam-UK2007 是由垃圾網頁檢測挑戰賽和對抗性信息檢索Web 討論組（AIRWEB）于2007 年收集的公開資料集（下載網址：https：//chato.cl/webspam/datasets/uk2007/），主要用于2008 年垃圾網頁檢測挑戰賽。DC2010 數據集是由匈牙利科學院（the Hungarian Academy of Sciences）于2010 年收集的公開數據集（下載網址為：https：//dms.sztaki.hu/en/download/webspam-resources），主要用于2010 年ECML/PKDD 發現挑戰賽。其中WebSpam-UK2007數據集曾經過信息增益率優選特征處理，數據集具體數據分布如表2所示。

表2 垃圾網頁數據集數據分布Tab.2 Data distribution of Web spam datasets

3.2 評價指標

解決不平衡分類問題，僅使用準確率、精確率等指標是不全面的。本文加入了AUC（Area Under the Curve）來共同評價模型的性能，AUC 綜合考慮少數類和多數類的分類準確性。混淆矩陣可以很好地表示出各種分類情況。

表3 混淆矩陣Tab.3 Confusion matrix

AUC 是接受者操作特性曲線（Receiver Operating Characteristic curve，ROC）下的面積，取值在0 到1 之間。精確率（Precision）、召回率（Recall）、F1 值和AUC 等指標計算式如下：

其中：NP表示正類樣本（少數類）總數；NN表示負類樣本（多數類）總數；i表示正類樣本；ranki表示正類樣本的置信度排序。

3.3 實驗設計與結果分析

基于上述數據集和評價指標，本文設計分類檢測實驗，將LCGHA-Xgboost 算法與當前較為流行的集成學習算法進行對比，這些算法包括隨機森林（Random_Forest）、GBDT 和Xgboost算法，實驗對比結果如表4所示。

表4 不同數據集上不同算法的分類性能對比Tab.4 Classification performance comparison of different algorithms on different datasets

從表4 中可以看出，本文提出的LCGHA-Xgboost 模型有效地提高了絕大多數數據集樣本的分類性能，其中，在Glass數據集上，其AUC 值達到了100%。本文算法通過調整樣本一階梯度增大難分樣本損失量的策略有效提高了算法對少數類的關注和多數類中部分難分樣本的關注，使得Xgboost對少數類和多數類的分類能力都得到了提升，從而做到在Glass數據集上完全分類正確。在Ecoli、Yeast、Climate、Ionosphere 和DC2010 數據集上，LCGHA-Xgboost 分類性能最優，其AUC 值相較對比算法有0.94%～7.41%的提升。這是因為本文算法定義的損失貢獻和損失貢獻密度可以準確地模擬樣本實際損失量和識別出難分樣本，從而更加合理地提高難分樣本的損失量占比，增強算法對少數類、多數類難分樣本的檢出能力。另外，在數據集WebSpam-UK2007 上的實驗結果顯示，LCGHA-Xgboost 算法AUC 值相較傳統Xgboost 提高了19.3%，相較Random_Forest 提高了近35.6%，主要原因是本文算法Recall 提高了97.7%～383.3%，少數類樣本被有效檢出，所以算法分類性能得到較大提高。在Leaf 數據集上，LCGHAXgboost算法性能略低于GBDT 算法，高于RF和Xgboost算法。綜合所有數據集上的表現可知，本文提出的LCGHA-Xgboost算法可以有效增強Xgboost 對少數類的檢出能力，提高算法性能。

4 結語

本文針對不平衡二分類問題中少數類誤分錯誤率高的問題，提出了LCGHA-Xgboost 算法。LCGHA-Xgboost 算法定義了損失貢獻和損失貢獻密度，針對Xgboost算法的建模特性進行改進優化，提出了一階梯度的調節策略LCGHA 算法，以達到調整樣本損失量的目的。實驗結果表明，該算法在多數數據集上具有更高的AUC 值，有效提高了Xgboost 算法的分類性能。在接下來的工作中，將研究用誤分類總代價替換傳統的損失函數，結合優秀的進化算法，以達到更好的分類性能。