李 浩，朱 焱

（西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，成都 611756）

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

0 引言

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

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

LCGHA-Xgboost 算法關(guān)注數(shù)據(jù)集中的難分樣本，這些樣本絕大部分存在于因?yàn)閿?shù)量過少而導(dǎo)致難以被正確分類的少數(shù)類中，還有部分存在于多數(shù)類中；因此本文方法對少數(shù)類和多數(shù)類的學(xué)習(xí)能力都有較大提升，對算法性能的提升效果更加出色。LCGHA 梯度調(diào)節(jié)算法定義損失貢獻(xiàn)密度來衡量樣本被正確分類的難易程度。依據(jù)損失貢獻(xiàn)密度，動態(tài)調(diào)整樣本一階梯度分布，間接提高難分樣本損失量在總損失量中的占比，使Xgboost 偏重對難分樣本的學(xué)習(xí)，從而提高Xgboost 的分類能力。

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

本文算法LCGHA-Xgboost與文獻(xiàn)［2］算法和文獻(xiàn)［3］算法的不同之處在于本文算法關(guān)注數(shù)據(jù)集中難分樣本，算法作用范圍更加廣泛；并且本文算法對不同樣本的關(guān)注度隨模型訓(xùn)練的過程而變化，可以更好地?cái)M合數(shù)據(jù)集樣本，提高Xgboost分類能力。本文與文獻(xiàn)［5］同樣研究了梯度不平衡調(diào)節(jié)策略，但本文的損失貢獻(xiàn)密度可以更好地衡量樣本被正確分類的難易程度，更準(zhǔn)確地識別難分樣本和易分樣本，從而進(jìn)行更加合理的梯度調(diào)整。

通過在UCI 數(shù)據(jù)集、WebSpam-UK2007 和DC2010 等多個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證得出，LCGHA 梯度調(diào)節(jié)算法有效地提高了Xgboost 對少數(shù)類樣本的檢出能力，增強(qiáng)了Xgboost 算法性能。

1 相關(guān)技術(shù)

1.1 Xgboost算法原理及模型介紹

Xgboost 是由Chen 等［9］提出的一種集成學(xué)習(xí)算法。它在GBDT（Gradient Boosting Decision Tree）的基礎(chǔ)上，通過改進(jìn)模型擬合目標(biāo)，在目標(biāo)函數(shù)中添加正則項(xiàng)，進(jìn)一步優(yōu)化了性能。因?yàn)镚BDT 算法在優(yōu)化損失函數(shù)時(shí)只使用了一階導(dǎo)數(shù)信息，而Xgboost算法則是對損失函數(shù)進(jìn)行了二階泰勒展開，利用了一階導(dǎo)數(shù)和二階導(dǎo)數(shù)信息，從而能更好地?cái)M合損失函數(shù)，減小優(yōu)化過程中存在的誤差。具體定義如下所示。

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

式中：表示訓(xùn)練模型的預(yù)測值；fk表示第k個(gè)子模型；xi表示第i個(gè)輸入樣本。Xgboost算法的優(yōu)化目標(biāo)包括損失函數(shù)和正則項(xiàng)兩個(gè)部分，因此最終的優(yōu)化目標(biāo)為：

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

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

式中：gi表示樣本xi的一階梯度；hi表示樣本xi的二階梯度；ω j表示第j個(gè)節(jié)點(diǎn)的輸出值；λ和γ是正則項(xiàng)系數(shù)，防止模型過擬合；Ij是第j個(gè)葉節(jié)點(diǎn)中的樣本子集。

Xgboost 模型的訓(xùn)練過程就是求解式（3），找到最佳的及其對應(yīng)的目標(biāo)函數(shù)最優(yōu)解，即：

式（5）用來衡量一棵樹的結(jié)構(gòu)好壞，其值越低，代表樹的結(jié)構(gòu)越好。因此當(dāng)樹分裂節(jié)點(diǎn)時(shí)，可以得到式（6）：

如果Gain值大于零，則繼續(xù)分裂節(jié)點(diǎn)；否則停止分裂節(jié)點(diǎn)。

1.2 梯度分布定義

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

定義 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為中心、ε為半徑的區(qū)域內(nèi)；δ(xi)表示樣本集D中落在以gi為中心、ε為半徑的樣本數(shù)。則Φ={δ(x1)，δ(x2)，…，δ(xn)}表示樣本D內(nèi)每個(gè)樣本的梯度分布。由定義1可以得出樣本集總體的梯度分布情況。

2 基于梯度分布調(diào)節(jié)策略的改進(jìn)Xgboost算法

Xgboost 在許多分類問題上表現(xiàn)都十分出色，但是在垃圾網(wǎng)頁、故障檢測等數(shù)據(jù)不平衡的領(lǐng)域中，對難分樣本的檢出能力較差，分類性能較低。為了提高Xgboost對難分樣本的檢出能力，本文定義了損失貢獻(xiàn)和損失貢獻(xiàn)密度，提出LCGHAXgboost 算法。以損失貢獻(xiàn)模擬樣本損失量，以損失貢獻(xiàn)密度衡量樣本被正確分類的難易程度。依據(jù)損失貢獻(xiàn)密度調(diào)節(jié)樣本一階梯度gi的分布情況，達(dá)到間接提高難分樣本損失量的目的，從而增強(qiáng)算法對難分樣本的關(guān)注和學(xué)習(xí)，提高Xgboost的分類性能。

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

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

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

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

損失貢獻(xiàn)密度（Loss Contribution Density，LCD）定義如下。

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

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

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

難分樣本由于其LCD 值遠(yuǎn)小于易分樣本的LCD 值，經(jīng)過式（13）調(diào)整后，其一階梯度的增幅會大于易分樣本，從而間接導(dǎo)致式（5）中難分樣本損失量增幅會大于易分樣本的增幅，最終使得Xgboost 偏向關(guān)注對難分樣本的學(xué)習(xí)和分類。具體算法過程如下所示。

算法1 LCGHA。

算法1 會在每個(gè)基分類器訓(xùn)練完成后，動態(tài)調(diào)整樣本的一階梯度分布。訓(xùn)練下一棵樹時(shí)，算法就會著重關(guān)注難分樣本。LCGHA-Xgboost算法的具體過程如下：

算法2 LCGHA-Xgboost。

3 LCGHA-Xgboost性能驗(yàn)證與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

為了檢驗(yàn)算法性能優(yōu)劣，本文選擇了多個(gè)UCI數(shù)據(jù)集，它們有不同的不平衡比例。這些數(shù)據(jù)集來自于UCI 數(shù)據(jù)庫，是加州大學(xué)歐文分校（University of California，Irvine）提出的用于機(jī)器學(xué)習(xí)的數(shù)據(jù)庫，而UCI 數(shù)據(jù)集是一個(gè)常用的標(biāo)準(zhǔn)測試數(shù)據(jù)集（網(wǎng)址為：https：//archive.ics.uci.edu/ml/index.php）。數(shù)據(jù)集數(shù)據(jù)分布如表1所示。

表1 UCI數(shù)據(jù)集數(shù)據(jù)分布Tab.1 Data distribution of UCI datasets

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

表2 垃圾網(wǎng)頁數(shù)據(jù)集數(shù)據(jù)分布Tab.2 Data distribution of Web spam datasets

3.2 評價(jià)指標(biāo)

解決不平衡分類問題，僅使用準(zhǔn)確率、精確率等指標(biāo)是不全面的。本文加入了AUC（Area Under the Curve）來共同評價(jià)模型的性能，AUC 綜合考慮少數(shù)類和多數(shù)類的分類準(zhǔn)確性?；煜仃嚳梢院芎玫乇硎境龈鞣N分類情況。

表3 混淆矩陣Tab.3 Confusion matrix

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

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

3.3 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

基于上述數(shù)據(jù)集和評價(jià)指標(biāo)，本文設(shè)計(jì)分類檢測實(shí)驗(yàn)，將LCGHA-Xgboost 算法與當(dāng)前較為流行的集成學(xué)習(xí)算法進(jìn)行對比，這些算法包括隨機(jī)森林（Random_Forest）、GBDT 和Xgboost算法，實(shí)驗(yàn)對比結(jié)果如表4所示。

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

從表4 中可以看出，本文提出的LCGHA-Xgboost 模型有效地提高了絕大多數(shù)數(shù)據(jù)集樣本的分類性能，其中，在Glass數(shù)據(jù)集上，其AUC 值達(dá)到了100%。本文算法通過調(diào)整樣本一階梯度增大難分樣本損失量的策略有效提高了算法對少數(shù)類的關(guān)注和多數(shù)類中部分難分樣本的關(guān)注，使得Xgboost對少數(shù)類和多數(shù)類的分類能力都得到了提升，從而做到在Glass數(shù)據(jù)集上完全分類正確。在Ecoli、Yeast、Climate、Ionosphere 和DC2010 數(shù)據(jù)集上，LCGHA-Xgboost 分類性能最優(yōu)，其AUC 值相較對比算法有0.94%～7.41%的提升。這是因?yàn)楸疚乃惴ǘx的損失貢獻(xiàn)和損失貢獻(xiàn)密度可以準(zhǔn)確地模擬樣本實(shí)際損失量和識別出難分樣本，從而更加合理地提高難分樣本的損失量占比，增強(qiáng)算法對少數(shù)類、多數(shù)類難分樣本的檢出能力。另外，在數(shù)據(jù)集WebSpam-UK2007 上的實(shí)驗(yàn)結(jié)果顯示，LCGHA-Xgboost 算法AUC 值相較傳統(tǒng)Xgboost 提高了19.3%，相較Random_Forest 提高了近35.6%，主要原因是本文算法Recall 提高了97.7%～383.3%，少數(shù)類樣本被有效檢出，所以算法分類性能得到較大提高。在Leaf 數(shù)據(jù)集上，LCGHAXgboost算法性能略低于GBDT 算法，高于RF和Xgboost算法。綜合所有數(shù)據(jù)集上的表現(xiàn)可知，本文提出的LCGHA-Xgboost算法可以有效增強(qiáng)Xgboost 對少數(shù)類的檢出能力，提高算法性能。

4 結(jié)語

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