密度峰值優(yōu)化的球簇劃分欠采樣不平衡數(shù)據(jù)分類算法

劉學(xué)文，王繼奎*，楊正國，李強(qiáng)，2，易紀(jì)海，李冰，聶飛平

（1.蘭州財(cái)經(jīng)大學(xué) 信息工程學(xué)院，蘭州 730020； 2.甘肅省電子商務(wù)技術(shù)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室（蘭州財(cái)經(jīng)大學(xué)），蘭州 730020；3.西北工業(yè)大學(xué) 光學(xué)影像分析與學(xué)習(xí)中心，西安 710072）（?通信作者電子郵箱wjkweb@163.com）

密度峰值優(yōu)化的球簇劃分欠采樣不平衡數(shù)據(jù)分類算法

劉學(xué)文1，王繼奎1*，楊正國1，李強(qiáng)1，2，易紀(jì)海1，李冰1，聶飛平3

（1.蘭州財(cái)經(jīng)大學(xué) 信息工程學(xué)院，蘭州 730020； 2.甘肅省電子商務(wù)技術(shù)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室（蘭州財(cái)經(jīng)大學(xué)），蘭州 730020；3.西北工業(yè)大學(xué) 光學(xué)影像分析與學(xué)習(xí)中心，西安 710072）（?通信作者電子郵箱wjkweb@163.com）

在集成算法中嵌入代價(jià)敏感和重采樣方法是一種有效的不平衡數(shù)據(jù)分類混合策略。針對現(xiàn)有混合方法中誤分代價(jià)計(jì)算和欠采樣過程較少考慮樣本的類內(nèi)與類間分布的問題，提出了一種密度峰值優(yōu)化的球簇劃分欠采樣不平衡數(shù)據(jù)分類算法DPBCPUSBoost。首先，利用密度峰值信息定義多數(shù)類樣本的抽樣權(quán)重，將存在“近鄰簇”的多數(shù)類球簇劃分為“易誤分區(qū)域”和“難誤分區(qū)域”，并提高“易誤分區(qū)域”內(nèi)樣本的抽樣權(quán)重；其次，在初次迭代過程中按照抽樣權(quán)重對多數(shù)類樣本進(jìn)行欠采樣，之后每輪迭代中按樣本分布權(quán)重對多數(shù)類樣本進(jìn)行欠采樣，并把欠采樣后的多數(shù)類樣本與少數(shù)類樣本組成臨時(shí)訓(xùn)練集并訓(xùn)練弱分類器；最后，結(jié)合樣本的密度峰值信息與類別分布為所有樣本定義不同的誤分代價(jià)，并通過代價(jià)調(diào)整函數(shù)增加高誤分代價(jià)樣本的權(quán)重。在10個(gè)KEEL數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，與現(xiàn)有自適應(yīng)增強(qiáng)（AdaBoost）、代價(jià)敏感自適應(yīng)增強(qiáng)（AdaCost）、隨機(jī)欠采樣增強(qiáng)（RUSBoost）和代價(jià)敏感欠采樣自適應(yīng)增強(qiáng)（USCBoost）等不平衡數(shù)據(jù)分類算法相比，DPBCPUSBoost在準(zhǔn)確率（Accuracy）、F1分?jǐn)?shù)（F1-Score）、幾何均值（G-mean）和受試者工作特征（ROC）曲線下的面積（AUC）指標(biāo)上獲得最高性能的數(shù)據(jù)集數(shù)量均多于對比算法。實(shí)驗(yàn)結(jié)果驗(yàn)證了DPBCPUSBoost中樣本誤分代價(jià)和抽樣權(quán)重定義的有效性。

不平衡數(shù)據(jù)分類；密度峰值；球聚類；代價(jià)敏感；欠采樣

0 引言

在異常檢測［1-4］、信用欺詐檢測［5-7］、醫(yī)保欺詐檢測［8］、電信詐騙檢測［9-10］等應(yīng)用場景中，傳統(tǒng)分類模型往往較難取得理想的效果，因?yàn)閭鹘y(tǒng)分類模型著重關(guān)注總體分類精度，在巨大的樣本數(shù)量差距下，少數(shù)類易被“忽視”。因此，研究者們提出了兩種策略來增加對少數(shù)類的“關(guān)注度”：一是對數(shù)據(jù)進(jìn)行重構(gòu)，即減少多數(shù)類樣本數(shù)量或增加少數(shù)類樣本數(shù)量，使多數(shù)類和少數(shù)類樣本數(shù)量趨于平衡；二是在分類模型［11］和思想上聚焦于少數(shù)類的分類準(zhǔn)確度［12］。兩種策略都能有效地提高分類算法在不平衡數(shù)據(jù)上的分類性能。

數(shù)據(jù)重構(gòu)策略主要包括特征選擇和重采樣方法，其中重采樣方法包括欠采樣［13-14］、過采樣［15-17］以及結(jié)合欠采樣和過采樣的混合采樣方法［18-19］。過采樣方法通過增加不平衡數(shù)據(jù)中的少數(shù)類樣本來平衡數(shù)據(jù)分布，欠采樣通過減少不平衡數(shù)據(jù)中的多數(shù)類樣本來平衡數(shù)據(jù)分布。在較大規(guī)模的數(shù)據(jù)中，欠采樣方法能顯著減少訓(xùn)練數(shù)據(jù)的數(shù)量從而提升訓(xùn)練速度。隨機(jī)欠采樣（Random UnderSampling， RUS）方法［13］是最簡易的欠采樣方法之一，其使用完全隨機(jī)的方法移除多數(shù)類樣本，顯然，RUS方法并沒有考慮到多數(shù)類樣本所攜帶的信息，極可能將一些對后續(xù)分類過程有價(jià)值的樣本移除。

分類思想改進(jìn)也是提高不平衡數(shù)據(jù)分類性能的重要策略，代表方法包括集成學(xué)習(xí)［20］和代價(jià)敏感學(xué)習(xí)［21］等。現(xiàn)有研究中，將重采樣與分類思想改進(jìn)策略相結(jié)合的方法的分類效果可能比單一策略更好。文獻(xiàn)［22］中結(jié)合隨機(jī)欠采樣和集成學(xué)習(xí)方法，提出了EasyEnsemble和BalanceCascade方法。EasyEnsemble從多數(shù)類樣本中隨機(jī)抽取與少數(shù)類樣本數(shù)量相等的多個(gè)獨(dú)立子集，分別與少數(shù)類樣本組合成新訓(xùn)練集，獨(dú)立訓(xùn)練多個(gè)自適應(yīng)增強(qiáng)（Adaptive Boosting， AdaBoost）分類器［20］，最終輸出集成分類器。BalanceCascade與EasyEnsemble的不同之處在于，每次迭代利用分類閾值從訓(xùn)練集中移除分類正確的樣本。相較于RUS，上述兩種方法減少了多數(shù)類樣本的信息損失，但是顯著增加了訓(xùn)練時(shí)間。有研究者基于AdaBoost提出了隨機(jī)欠采樣增強(qiáng)（Random UnderSampling Boosting， RUSBoost）方法［23］，該方法在迭代過程中對多數(shù)類進(jìn)行隨機(jī)欠采樣并與少數(shù)類組成臨時(shí)訓(xùn)練集，然后使用臨時(shí)訓(xùn)練集和權(quán)值訓(xùn)練弱分類器。RUSBoost仍然使用隨機(jī)欠采樣的方式平衡數(shù)據(jù)分布，當(dāng)不平衡比例非常高時(shí)，可能需要非常多的迭代次數(shù)。

文獻(xiàn)［21］中將集成學(xué)習(xí)和代價(jià)敏感學(xué)習(xí)相結(jié)合，提出了代價(jià)敏感自適應(yīng)增強(qiáng)（Cost-sensitive AdaBoost， AdaCost）方法。AdaBoost賦予每個(gè)樣本同等的誤分代價(jià)，AdaCost則可對不同樣本賦予不同的誤分代價(jià)，例如對少數(shù)類樣本賦予更高的誤分代價(jià)，可以降低迭代過程中的累積誤分風(fēng)險(xiǎn)。文獻(xiàn)［14］中采用AdaCost的樣本權(quán)重更新策略，提出了基于欠采樣和代價(jià)敏感的不平衡數(shù)據(jù)分類算法——代價(jià)敏感欠采樣自適應(yīng)增強(qiáng)（UnderSampling and Cost-sensitive Boosting， USCBoost）。與隨機(jī)采樣方法不同，USCBoost只選取權(quán)重較大的多數(shù)類樣本和所有少數(shù)類樣本作為臨時(shí)訓(xùn)練集，訓(xùn)練速度較快。USCBoost采用類依賴代價(jià)，為少數(shù)類樣本定義比多數(shù)類樣本更高的誤分代價(jià)，但是該方法并沒有考慮到同類樣本內(nèi)部之間也存在差異［24］。

文獻(xiàn)［25］中提出了密度峰值聚類（Clustering by fast search and find of Density Peaks， DPC）算法，該算法利用“密度”和“峰值”信息發(fā)現(xiàn)樣本的潛在層次結(jié)構(gòu)，基于這種結(jié)構(gòu)可對球形和非球形數(shù)據(jù)進(jìn)行聚類。文獻(xiàn)［26］中提出了球k均值聚類算法（Ballk-means），該算法將類簇視為球并將其劃分為“穩(wěn)定區(qū)域”和“活動(dòng)區(qū)域”，只計(jì)算“活動(dòng)區(qū)域”與“近鄰簇”中心之間的距離，從而有效減少了質(zhì)心距離計(jì)算量。受DPC和Ballk-means思想的啟發(fā)，本文提出了密度峰值優(yōu)化的球簇劃分欠采樣不平衡數(shù)據(jù)分類算法DPBCPUSBoost （Boosting algorithm based on Ball Cluster Partitioning and UnderSampling with Density Peak optimization）。本文的主要工作如下：

1）利用了“密度峰值”定義多數(shù)類樣本抽樣權(quán)重?？紤]樣本的潛在空間結(jié)構(gòu)，對于密度和峰值都較大的樣本，DPBCPUSBoost賦予其更大的抽樣權(quán)重。

2）結(jié)合了“Ballk-means”思想調(diào)整多數(shù)類樣本抽樣權(quán)重。DPBCPUSBoost將存在“近鄰簇”的多數(shù)類球簇劃分為“易誤分區(qū)域”和“難誤分區(qū)域”，并增大“易誤分區(qū)域”內(nèi)的樣本抽樣權(quán)重。

3）結(jié)合了“密度峰值”定義誤分代價(jià)。DPBCPUSBoost同時(shí)考慮類依賴代價(jià)和樣本依賴代價(jià)，賦予少數(shù)類更高誤分代價(jià)的同時(shí)，也考慮到類簇內(nèi)部樣本分布的差異，對于密度和峰值都較大的樣本賦予更高的誤分代價(jià)。

為驗(yàn)證DPBCPUSBoost算法的有效性，在10個(gè)KEEL不平衡數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，相較于AdaBoost、AdaCost、RUSBoost和USCBoost算法，DPBCPUSBoost在準(zhǔn)確率（Accuracy）、F1分?jǐn)?shù)（F1-Score）、幾何均值（Geometric Mean， G-mean）和受試者工作特征（Receiver Operating Characteristic， ROC）曲線下面的面積（Area Under Curve， AUC）指標(biāo)上均取得了較好的效果。

1 相關(guān)工作

本文涉及的變量較多，因此，在表1中對出現(xiàn)次數(shù)較多和較重要的變量進(jìn)行了說明。

表1 變量及說明Tab. 1 Variables and descriptions

1.1 DPC算法

文獻(xiàn)［25］中認(rèn)為類簇中心應(yīng)該具有以下特點(diǎn)：類簇中心與比它密度更高的樣本相距較遠(yuǎn)；類簇中心被更低密度的樣本所圍繞。

文獻(xiàn)［25］中定義了樣本的“局部密度”和“峰值”，并認(rèn)為“局部密度”和“峰值”都較大的樣本成為類簇中心的概率更大。

由式（2）可知，樣本的峰值為與“密度高于它且離它最近”的樣本之間的距離。

為便于理解，通過表2、圖1～2的示例來展示類簇中心的選取過程。表2為二類別含噪聲的人工數(shù)據(jù)集信息（數(shù)值四舍五入保留三位小數(shù)），樣本的分布情況如圖1所示，類簇中心選取的決策圖如圖2所示。在圖1～2中，圓形表示多數(shù)類樣本，菱形表示少數(shù)類樣本，矩形表示噪聲樣本。

表2 樣本信息Tab. 2 Sample information

圖1 樣本分布Fig. 1 Sample distribution

圖2 決策圖Fig. 2 Decision diagram

從圖2可以看出，相較于大部分樣本位于下方，樣本1和樣本2位于右上角，根據(jù)文獻(xiàn)［25］的方法，可以選取樣本1和樣本2作為兩個(gè)類簇的中心。

1.2 Ball k-means算法

為減少k-means算法迭代過程中的質(zhì)心距離計(jì)算量，Ballk-means［26］算法將球簇劃分為“穩(wěn)定區(qū)域”和“活動(dòng)區(qū)域”。

球簇內(nèi)“穩(wěn)定區(qū)域”以外的區(qū)域?yàn)椤盎顒?dòng)區(qū)域”，若球簇的近鄰簇?cái)?shù)量多于一個(gè)，“活動(dòng)區(qū)域”會被細(xì)分為多個(gè)“環(huán)形區(qū)域”。

文獻(xiàn)［26］中通過理論證明，當(dāng)前輪次迭代過程中，“穩(wěn)定區(qū)域”內(nèi)的樣本不會被劃分到任何其他的簇中，而“活動(dòng)區(qū)域”內(nèi)的樣本可能會被劃分到近鄰簇，因此，只需在每輪迭代中計(jì)算“活動(dòng)區(qū)域”內(nèi)的點(diǎn)與近鄰簇中心點(diǎn)之間的距離，從而極大減少了距離計(jì)算量。

1.3 USCBoost算法

文獻(xiàn)［14］中結(jié)合AdaCost算法的代價(jià)調(diào)整函數(shù)提出了USCBoost算法，該算法在每輪迭代過程中只選取權(quán)值較高的多數(shù)類樣本參與分類器訓(xùn)練，具體步驟如算法1。

算法1 USCBoost算法。

b） Else

c） 欠采樣后的多數(shù)類樣本與全部少數(shù)類樣本組成臨時(shí)訓(xùn)練集，并歸一化樣本權(quán)重；

2 結(jié)合密度峰值代價(jià)和欠采樣的分類算法

本文受DPC和Ballk-means的啟發(fā)，利用密度峰值定義隨機(jī)抽樣權(quán)重，將多數(shù)類球簇劃分為“易誤分區(qū)域”和“難誤分區(qū)域”，并增加“易誤分區(qū)域”內(nèi)樣本的抽樣權(quán)重，在初次迭代中，依據(jù)不同的抽樣權(quán)重對多數(shù)類樣本進(jìn)行欠采樣。本文結(jié)合密度峰值和樣本類別分布信息定義新的誤分代價(jià)，并通過代價(jià)調(diào)整函數(shù)使高誤分代價(jià)的樣本在迭代過程中更快地增加樣本權(quán)重。

2.1 定義抽樣權(quán)重

在DPC算法中，中心點(diǎn)必須同時(shí)滿足“具有較高密度”和“離其他更高密度點(diǎn)較遠(yuǎn)”這兩個(gè)條件，因此，值的大小可以反映樣本作為局部中心的可能性。如表2、圖1～2所示，值最大的兩個(gè)樣本分別作為不同類簇的中心，而值較大的樣本成為局部中心，值較小的樣本則分布在類簇邊緣。因此，本文方法在欠采樣中盡量保留這些中心點(diǎn)。

因?yàn)樵跊Q策邊界區(qū)域內(nèi)的多數(shù)類樣本容易被誤分，因此，需要提高這些樣本的抽樣權(quán)重，使其能夠在訓(xùn)練分類器的過程中獲得更多關(guān)注。Ballk-means方法將球簇劃分為“穩(wěn)定區(qū)域”和“活動(dòng)區(qū)域”，與之類似，本文將多數(shù)類球簇劃分為“易誤分區(qū)域”和“難誤分區(qū)域”，少數(shù)類球簇不作劃分。令表示少數(shù)類球簇的中心，表示多數(shù)類球簇的中心，為多數(shù)類球簇的半徑，這兩個(gè)區(qū)域的定義如下。

圖3為劃分球簇的示意圖，實(shí)線表示球簇的邊界，多數(shù)類球簇內(nèi)弧形虛線與多數(shù)類球簇邊界線所圍成的區(qū)域?yàn)椤耙渍`分區(qū)域”，多數(shù)類球簇內(nèi)“易誤分區(qū)域”以外的區(qū)域?yàn)椤半y誤分區(qū)域”。

如果少數(shù)類球簇是多數(shù)類球簇的近鄰簇，則對多數(shù)類球簇中落入“易誤分區(qū)域”內(nèi)的樣本的抽樣權(quán)重進(jìn)行調(diào)整；如果少數(shù)類球簇不是多數(shù)類球簇的近鄰簇，或者樣本落在“難誤分區(qū)域”內(nèi)，則不對抽樣權(quán)重進(jìn)行調(diào)整。

圖3 劃分球簇Fig. 3 Dividing ball clusters

抽樣權(quán)重調(diào)整后，對其歸一化：

USCBoost算法初次迭代時(shí)采用RUS方法對多數(shù)類樣本進(jìn)行欠采樣，在之后的迭代過程中則根據(jù)樣本權(quán)重的大小順序進(jìn)行欠采樣。當(dāng)不平衡比例非常高時(shí)，初次迭代訓(xùn)練的分類器質(zhì)量會非常差，進(jìn)而影響之后的訓(xùn)練過程。而本文則按照權(quán)重對多數(shù)類進(jìn)行欠采樣，這種方式盡量保留了決策邊界區(qū)域內(nèi)的有價(jià)值的多數(shù)類樣本［12，27］。

2.2 定義誤分代價(jià)

由表2中的樣本信息、圖1中樣本分布情況和圖2中的決策圖可知，和值越小的樣本，越不可能成為局部中心點(diǎn)，和值越大的樣本越有可能成為局部中心，而這些中心點(diǎn)的重要性在分類過程中的價(jià)值要更高，誤分代價(jià)也更大。因此，本文利用對不同樣本定義不同的代價(jià)。

2.3 復(fù)雜度分析

綜上，相較于采用欠采樣方法的RUSBoost和USCBoost，DPBCPUSBoost的時(shí)間復(fù)雜度和空間復(fù)雜度更高。但是，對于沒有采用欠采樣方法的AdaBoost和AdaCost，由于這些算法在迭代訓(xùn)練弱分類器時(shí)輸入了全部的樣本，而DPBCPUSBoost只輸入了欠采樣后的小部分樣本，因此DPBCPUSBoost的迭代訓(xùn)練過程相較于上述兩個(gè)算法消耗了更少的時(shí)間和空間。DPBCPUSBoost的算法步驟如算法2。

算法2 DPBCPUSBoost算法。

b） Else

c） 將欠采樣后的多數(shù)類樣本與全部少數(shù)類樣本組成臨時(shí)訓(xùn)練集，并歸一化樣本權(quán)重；

3 實(shí)驗(yàn)與結(jié)果分析

實(shí)驗(yàn)使用的系統(tǒng)為64位Windows 10，程序開發(fā)環(huán)境為Matlab 2019a，硬件為酷睿I5處理器和8 GB運(yùn)行內(nèi)存。實(shí)驗(yàn)涉及的對比算法均參照原文及網(wǎng)絡(luò)資料實(shí)現(xiàn)，所使用數(shù)據(jù)集為網(wǎng)絡(luò)公開數(shù)據(jù)集。

3.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證DPBCPUSBoost的有效性，在10個(gè)KEEL不平衡數(shù)據(jù)集（https：//sci2s.ugr.es/keel/imbalanced.php）上進(jìn)行實(shí)驗(yàn)，數(shù)據(jù)集信息如表3所示，其中不平衡比例為多數(shù)類樣本數(shù)量比少數(shù)類樣本數(shù)量。

KEEL不平衡數(shù)據(jù)集是由原始數(shù)據(jù)集轉(zhuǎn)換后得到的二類別不平衡數(shù)據(jù)集，例如在vehicle3中，少數(shù)類是原vehicle數(shù)據(jù)集中的類別3，多數(shù)類則由剩余類別組成，例如在ecoli-0-6-7_vs_5中，少數(shù)類由類別0、6和7組成，多數(shù)類由類別5組成。本文使用的KEEL數(shù)據(jù)集均已用五折交叉驗(yàn)證方式劃分為5個(gè)子數(shù)據(jù)集。

表3 實(shí)驗(yàn)數(shù)據(jù)集Tab. 3 Experimental datasets

本文選取AdaBoost、AdaCost、RUSBoost和USCBoost與DPBCPUSBoost進(jìn)行對比實(shí)驗(yàn)。AdaBoost是經(jīng)典的集成算法，可以用于不平衡數(shù)據(jù)分類；AdaCost在AdaBoost樣本權(quán)重更新步驟中加入了代價(jià)調(diào)整函數(shù)；RUSBoost在AdaBoost訓(xùn)練分類器之前對多數(shù)類進(jìn)行隨機(jī)欠采樣；USCBoost結(jié)合了隨機(jī)欠采樣方法和代價(jià)敏感學(xué)習(xí)方法；DPBCPUSBoost在USCBoost的基礎(chǔ)上采用了新的誤分代價(jià)計(jì)算方法和欠采樣方法。將上述5個(gè)相關(guān)算法進(jìn)行對比實(shí)驗(yàn)，能夠驗(yàn)證DPBCPUSBoost的有效性。實(shí)驗(yàn)中各算法的迭代次數(shù)設(shè)置為10，DPBCPUSBoost的截?cái)嗑嚯x截取閾值設(shè)置為2，AdaCost和USCBoost采用相同的誤分代價(jià)，其他均使用默認(rèn)參數(shù)。

本文選取決策樹樁（Decision Stump）作為弱分類器，Decision Stump是單層決策樹，其結(jié)構(gòu)簡單，適合用作集成學(xué)習(xí)中的分類器。

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

本文采用Accuracy、F1-Score、G-mean和AUC作為分類性能的評價(jià)指標(biāo)。其中：F1-Score是精確率（Precision）和召回率（Recall）的調(diào)和均值；G-mean是召回率和特異度（Specificity）的幾何均值；ROC曲線是以假正例率（False Positive Rate， FPR）為橫坐標(biāo)、真正例率（True Positive Rate， TPR）為縱坐標(biāo)繪制出來的曲線，曲線下的面積（AUC）越大，說明分類器效果越好，ROC曲線不易受正負(fù)樣本分布影響，能夠比較客觀地評價(jià)模型性能。

混淆矩陣是繪制ROC曲線的基礎(chǔ)。在二分類混淆矩陣中：真正例（True Positive， TP）表示實(shí)際為正例的樣本被預(yù)測為正例；假正例（False Positive， FP）表示實(shí)際類別為負(fù)例的樣本被預(yù)測為正例；真負(fù)例（True Negative， TN）表示實(shí)際為負(fù)例的樣本被預(yù)測為負(fù)例；假負(fù)例（False Negative， FN）表示實(shí)際類別為正例的樣本被預(yù)測為負(fù)例。

Accuracy、F1-Score和G-mean等評價(jià)指標(biāo)可通過混淆矩陣和以下計(jì)算式得出：

3.3 分類性能對比

為驗(yàn)證本文算法的有效性，對各算法的分類性能進(jìn)行測試。表4為AdaBoost和AdaCost的測試結(jié)果，表5為RUSBoost、USCBoost和DPBCPUSBoost的測試結(jié)果，圖4展示了各算法取得最高性能的數(shù)據(jù)集數(shù)量。

表4 AdaBoost和AdaCost的分類性能測試結(jié)果 單位：%Tab. 4 Classification performance test results of AdaBoost and AdaCost unit：%

由圖4可知，AdaCost的性能總體上優(yōu)于AdaBoost，因?yàn)槠湓跇颖緳?quán)重調(diào)整過程中，提高了有更高誤分代價(jià)樣本的權(quán)重；USCBoost的性能總體上優(yōu)于RUSBoost，因?yàn)槠洳粌H結(jié)合了代價(jià)敏感學(xué)習(xí)，而且在欠采樣過程中保留了較高權(quán)重的樣本。

DPBCPUSBoost初次迭代利用樣本抽樣權(quán)重對多數(shù)類樣本進(jìn)行欠采樣，RUSBoost和USCBoost初次迭代使用RUS對多數(shù)類進(jìn)行欠采樣。因此，為驗(yàn)證DPBCPUSBoost改進(jìn)欠采樣方法的有效性，對這3個(gè)算法初次迭代后的性能進(jìn)行測試。表5為各個(gè)算法在不同數(shù)據(jù)集上初次迭代和10次迭代后的分類性能測試結(jié)果。

表5 RUSBoost、USCBoost和DPBCPUSBoost的分類性能測試結(jié)果 單位：%Tab. 5 Classification performance test results of RUSBoost， USCBoost and DPBCPUSBoost unit：%

圖4 不同算法取得最高性能的數(shù)據(jù)集數(shù)量Fig. 4 Number of datasets of different algorithms with highest performance

由表5初次迭代后的性能對比實(shí)驗(yàn)結(jié)果可得出兩個(gè)結(jié)論：

1）初次迭代后，DPBCPUSBoost在AUC、G-mean和F1-Score指標(biāo)上獲得最高性能的數(shù)據(jù)集數(shù)量分別為5個(gè)、5個(gè)和4個(gè)，均多于RUSBoost和USCBoost。

2）初次迭代后，DPBCPUSBoost在Accuracy指標(biāo)上獲得最高性能的數(shù)據(jù)集數(shù)量為3個(gè)，要少于RUSBoost，因?yàn)锳ccuracy指標(biāo)易受多數(shù)類樣本數(shù)量影響，例如在不平衡比較高的abalone19（D10）數(shù)據(jù)集上，RUSBoost在AUC、G-mean和F1-Score指標(biāo)上的表現(xiàn)均要差于DPBCPUSBoost。

初次迭代后的分類性能測試結(jié)果表明：相較于隨機(jī)欠采樣方法，DPBCPUSBoost使用樣本抽樣權(quán)重進(jìn)行欠采樣具有一定的優(yōu)勢，這是因?yàn)镈PBCPUSBoost盡量保留了決策邊界區(qū)域內(nèi)易誤分的多數(shù)類樣本，使得分類器更加關(guān)注這些區(qū)域內(nèi)的樣本，但是在一些類重疊度較高的數(shù)據(jù)集上，該方法可能會降低分類性能。

圖4、表4～5中的實(shí)驗(yàn)結(jié)果表明，10次迭代后，DPBCPUSBoost在Accuracy、F1-Score、G-mean、AUC指標(biāo)上獲得最高性能的數(shù)據(jù)集數(shù)量分別為5個(gè)、7個(gè)、7個(gè)和5個(gè)，總體上分類性能優(yōu)于其他4個(gè)對比算法，因?yàn)镈PBCPUSBoost兼顧了類內(nèi)、類間樣本的分布情況，并利用密度峰值對不同樣本定義了不同的誤分代價(jià)。

3.4 運(yùn)行時(shí)間對比

圖5給出了本文提出的DPBCPUSBoost和對比的AdaBoost等4個(gè)算法在10個(gè)數(shù)據(jù)集上的50次平均運(yùn)行時(shí)間的結(jié)果。

圖5 不同算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間Fig. 5 Running time for different algorithms on different datasets

由圖5可知，AdaBoost和AdaCost的運(yùn)行時(shí)間明顯多于RUSBoost、USCBoost和DPBCPUSBoost，這是因?yàn)锳daBoost和AdaCost沒有對多數(shù)類樣本進(jìn)行欠采樣，訓(xùn)練集中存在更多的多數(shù)類樣本，因此訓(xùn)練時(shí)間會更長。DPBCPUSBoost的運(yùn)行時(shí)間要多于RUSBoost和USCBoost，這是因?yàn)槊芏确逯档挠?jì)算消耗了較多時(shí)間，DPBCPUSBoost采用密度峰值定義代價(jià)和抽樣權(quán)重的方式，以增加復(fù)雜度為代價(jià)提升了分類性能。

4 結(jié)語

本文針對不平衡數(shù)據(jù)分類問題提出了DPBCPUSBoost，該算法結(jié)合密度峰值信息使不同樣本具有不同的誤分代價(jià)，同時(shí)考慮了類間樣本分布和類內(nèi)樣本分布情況。DPBCPUSBoost利用密度峰值定義抽樣權(quán)重，并對多數(shù)類球簇中的“易誤分區(qū)域”內(nèi)樣本的抽樣權(quán)重進(jìn)行調(diào)整，使決策邊界區(qū)域附近的多數(shù)類樣本獲得更多關(guān)注。在多個(gè)不平衡數(shù)據(jù)集上的對比實(shí)驗(yàn)驗(yàn)證了DPBCPUSBoost的有效性。但是，對于密度不均勻的數(shù)據(jù)，密度峰值不能較好地反映數(shù)據(jù)潛在結(jié)構(gòu)，進(jìn)而影響了誤分代價(jià)的計(jì)算。因此，設(shè)計(jì)能更精準(zhǔn)反映數(shù)據(jù)潛在結(jié)構(gòu)信息的誤分代價(jià)是未來研究的主要方向。

[1] ZHOU X K， HU Y Y， LIANG W， et al. Variational LSTM enhanced anomaly detection for industrial big data ［J］. IEEE Transactions on Industrial Informatics， 2021， 17（5）： 3469-3477.

[2] 胡姣姣，王曉峰，張萌，等.基于深度學(xué)習(xí)的時(shí)間序列數(shù)據(jù)異常檢測方法［J］.信息與控制，2019，48（1）：1-8.（HU J J， WANG X F，ZHANG M， et al. Time-series data anomaly detection method based on deep learning ［J］. Information and Control， 2019， 48（1）： 1-8.）

[3] 張躍飛，王敬飛，陳斌，等.基于改進(jìn)的Mask R-CNN的公路裂縫檢測算法［J］.計(jì)算機(jī)應(yīng)用，2020，40（S2）：162-165.（ZHANG Y F， WANG J F， CHEN B， et al. Pavement crack detection algorithm based on improved Mask R-CNN ［J］. Journal of Computer Applications， 2020， 40（S2）： 162-165.）

[4] LIN P， YE K J， XU C Z. Dynamic network anomaly detection system by using deep learning techniques ［C］// Proceedings of the 2019 International Conference on Cloud Computing， LNCS 11513. Cham： Springer， 2019： 161-176.

[5] 劉穎，楊軻.基于深度集成學(xué)習(xí)的類極度不均衡數(shù)據(jù)信用欺詐檢測算法［J］.計(jì)算機(jī)研究與發(fā)展，2021，58（3）：539-547.（LIU Y， YANG K. Credit fraud detection for extremely imbalanced data based on ensembled deep learning ［J］. Journal of Computer Research and Development， 2021， 58（3）： 539-547.）

[6] ZHU H H， LIU G J， ZHOU M C， et al. Optimizing weighted extreme learning machines for imbalanced classification and application to credit card fraud detection ［J］. Neurocomputing， 2020， 407： 50-62.

[7] LI Z C， HUANG M， LIU G J， et al. A hybrid method with dynamic weighted entropy for handling the problem of class imbalance with overlap in credit card fraud detection ［J］. Expert Systems with Applications， 2021， 175： Article No.114750.

[8] 易東義，鄧根強(qiáng)，董超雄，等.基于圖卷積神經(jīng)網(wǎng)絡(luò)的醫(yī)保欺詐檢測算法［J］.計(jì)算機(jī)應(yīng)用，2020，40（5）：1272-1277.（YI D Y， DENG G Q，DONG C X， et al. Medical insurance fraud detection algorithm based on graph convolutional neural network ［J］. Journal of Computer Applications， 2020， 40（5）： 1272-1277.）

[9] 劉梟，王曉國.基于密集子圖的銀行電信詐騙檢測方法［J］.計(jì)算機(jī)應(yīng)用，2019，39（4）：1214-1219.（LIU X， WANG X G. Dense subgraph based telecommunication fraud detection approach in bank ［J］. Journal of Computer Applications， 2019， 39（4）： 1214-1219.）

[10] LU C， LIN S F， LIU X L， et al. Telecom fraud identification based on ADASYN and random forest ［C］// Proceedings of the 2020 5th International Conference on Computer and Communication Systems. Piscataway： IEEE， 2020： 447-452.

[11] 王偉，謝耀濱，尹青.針對不平衡數(shù)據(jù)的決策樹改進(jìn)方法［J］.計(jì)算機(jī)應(yīng)用，2019，39（3）：623-628.（WANG W， XIE Y B， YIN Q. Decision tree improvement method for imbalanced data ［J］. Journal of Computer Applications， 2019， 39（3）： 623-628.）

[12] 徐玲玲，遲冬祥.面向不平衡數(shù)據(jù)集的機(jī)器學(xué)習(xí)分類策略［J］.計(jì)算機(jī)工程與應(yīng)用，2020，56（24）：12-27.（XU L L， CHI D X. Machine learning classification strategy for imbalanced data sets ［J］. Computer Engineering and Applications，2020， 56（24）： 12-27.）

[13] 陳木生，盧曉勇.三種用于垃圾網(wǎng)頁檢測的隨機(jī)欠采樣集成分類器［J］.計(jì)算機(jī)應(yīng)用，2017，37（2）：535-539，558.（CHEN M S， LU X Y. Three random under-sampling based ensemble classifiers for Web spam detection ［J］. Journal of Computer Applications， 2017， 37（2）： 535-539， 558.）

[14] 王俊紅，閆家榮.基于欠采樣和代價(jià)敏感的不平衡數(shù)據(jù)分類算法［J］.計(jì)算機(jī)應(yīng)用，2021，41（1）：48-52.（WANG J H， YAN J R. Classification algorithm based on undersampling and cost-sensitiveness for unbalanced data ［J］. Journal of Computer Applications， 2021， 41（1）： 48-52.）

[15] KAYA E， KORKMAZ S， ?AHMAN M A， et al. DEBOHID： a differential evolution based oversampling approach for highly imbalanced datasets ［J］. Expert Systems with Applications， 2021， 169： Article No.114482.

[16] ENGELMANN J， LESSMANN S. Conditional Wasserstein GAN-based oversampling of tabular data for imbalanced learning ［J］. Expert Systems with Applications， 2021， 174： Article No.114582.

[17] WANG X Y， XU J， ZENG T Y， et al. Local distribution-based adaptive minority oversampling for imbalanced data classification ［J］. Neurocomputing，2021， 422： 200-213.

[18] GAO X， REN B， ZHANG H， et al. An ensemble imbalanced classification method based on model dynamic selection driven by data partition hybrid sampling ［J］. Expert Systems with Applications， 2020， 160： Article No.113660.

[19] ZHU Y W， YAN Y T， ZHANG Y W， et al. EHSO： evolutionary hybrid sampling in overlapping scenarios for imbalanced learning ［J］. Neurocomputing， 2020， 417： 333-346.

[20] FREUND Y， SCHAPIRE R E. Experiments with a new boosting algorithm ［C］// Proceedings of the 13th International Conference on International Conference on Machine Learning. San Francisco： Morgan Kaufmann Publishers Inc.， 1996：148-156.

[21] FAN W， STOLFO S J， ZHANG J X， et al. AdaCost： misclassification cost-sensitive boosting ［C］// Proceedings of the 1999 16th International Conference on Machine Learning. San Francisco： Morgan Kaufmann Publishers Inc.， 1999： 97-105.

[22] LIU X Y， WU J X， ZHOU Z H. Exploratory undersampling for class-imbalance learning ［J］. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 2009， 39（2）： 539-550.

[23] SEIFFERT C， KHOSHGOFTAAR T M， VAN HULSE J， et al. RUSBoost： a hybrid approach to alleviating class imbalance ［J］. IEEE Transactions on Systems， Man， and Cybernetics — Part A： Systems and Humans， 2010， 40（1）： 185-197.

[24] 萬建武，楊明.代價(jià)敏感學(xué)習(xí)方法綜述［J］.軟件學(xué)報(bào)，2020，31（1）：113-136.（WAN J W， YANG M. Survey on cost-sensitive learning method ［J］. Journal of Software， 2020， 31（1）： 113-136.）

[25] RODRIGUEZ A， LAIO A. Clustering by fast search and find of density peaks ［J］. Science， 2014， 344（6191）： 1492-1496.

[26] XIA S Y， PENG D W， MENG D Y， et al. Ballk-means： fast adaptive clustering with no bounds ［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2022， 44（1）： 87-99.

[27] HART P. The condensed nearest neighbor rule （corresp.） ［J］. IEEE Transactions on Information Theory，1968， 14（3）： 515-516.

Imbalanced data classification algorithm based on ball cluster partitioning and undersampling with density peak optimization

LIU Xuewen1， WANG Jikui1*， YANG Zhengguo1， LI Qiang1，2， YI Jihai1， LI Bing1， NIE Feiping3

（1.School of Information Engineering，Lanzhou University of Finance and Economics，Lanzhou Gansu730020，China；2.Key Laboratory of E?Business Technology and Application of Gansu Province（Lanzhou University of Finance and Economics），Lanzhou Gansu730020，China；3.Center for OPTical IMagery Analysis and Learning（OPTIMAL），Northwestern Polytechnical University，Xi’an Shaanxi710072，China）

It is an effective hybrid strategy for imbalanced data classification of integrating cost-sensitivity and resampling methods into the ensemble algorithms. Concerning the problem that the misclassification cost calculation and undersampling process less consider the intra-class and inter-class distributions of samples in the existing hybrid methods， an imbalanced data classification algorithm based on ball cluster partitioning and undersampling with density peak optimization was proposed， named Boosting algorithm based on Ball Cluster Partitioning and UnderSampling with Density Peak optimization （DPBCPUSBoost）. Firstly， the density peak information was used to define the sampling weights of majority samples， and the majority ball cluster with “neighbor cluster” was divided into “area misclassified easily” and “area misclassified hardly”，then the sampling weight of samples in “area misclassified easily” was increased. Secondly， the majority samples were undersampled based on the sampling weights in the first iteration， then the majority samples were undersampled based on the sample distribution weight in every iteration. And the weak classifier was trained on the temporary training set combining the undersampled majority samples with all minority samples. Finally， the density peak information of samples was combined with the categorical distribution of samples to define the different misclassification costs for all samples，and the weights of samples with higher misclassification cost were increased by the cost adjustment function. Experimental results on 10 KEEL datasets indicate that， the number of datasets with the highest performance achieved by DPBCPUSBoost is more than that of the imbalanced data classification algorithms such as Adaptive Boosting （AdaBoost）， Cost-sensitive AdaBoost （AdaCost）， Random UnderSampling Boosting （RUSBoost） and UnderSampling and Cost-sensitive Boosting （USCBoost）， in terms of evaluation metrics such as Accuracy， F1-Score，Geometric Mean （G-mean） and Area Under Curve （AUC） of Receiver Operating Characteristic （ROC）. Experimental results verify that the definition of sample misclassification cost and sampling weight of the proposed DPBCPUSBoost is effective.

imbalanced data classification; density peak; ball clustering; cost-sensitive; undersampling

TP181

A

1001-9081（2022）05-1455-09

10.11772/j.issn.1001-9081.2021050736

2021?05?10；

2021?09?19；

2021?10?14。

國家自然科學(xué)基金資助項(xiàng)目（61772427）；甘肅省高等學(xué)校創(chuàng)新能力提升資助項(xiàng)目（2021B?145，2021B?147）；甘肅省自然科學(xué)基金資助項(xiàng)目（17JR5RA177）；甘肅省重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（21YF5FA087）。

劉學(xué)文（1996—），男，江西贛州人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)、人工智能； 王繼奎（1978—），男，山東滕州人，副教授，博士，CCF會員，主要研究方向：機(jī)器學(xué)習(xí)、人工智能； 楊正國（1987—），男，甘肅積石山人，副教授，博士，CCF會員，主要研究方向：機(jī)器學(xué)習(xí)、人工智能； 李強(qiáng)（1973—），男，甘肅蘭州人，教授，碩士，CCF會員，主要研究方向：機(jī)器學(xué)習(xí)、人工智能； 易紀(jì)海（1974—），男，黑龍江伊春人，講師，碩士，主要研究方向：機(jī)器學(xué)習(xí)、人工智能； 李冰（1997—），女，山西運(yùn)城人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)、人工智能； 聶飛平（1977—），男，江西吉安人，教授，博士生導(dǎo)師，博士，CCF會員，主要研究方向：機(jī)器學(xué)習(xí)、人工智能。

This work is partially supported by National Natural Science Foundation of China （61772427），Gansu Provincial Institutions of Higher Learning Innovation Ability Promotion Program （2021B-145， 2021B-147）， Natural Science Foundation of Gansu Province （17JR5RA177）， Key Research and Development Program of Gansu Province （21YF5FA087）.

LIU Xuewen， born in 1996， M. S. candidate. His research interests include machine learning，artificial intelligence.

WANG Jikui， born in 1978， Ph. D.， associate professor. His research interests include machine learning， artificial intelligence.

YANG Zhengguo， born in 1987， Ph. D.， associate professor. His research interests include machine learning， artificial intelligence.

LI Qiang， born in 1973， M. S.， professor. His research interests include machine learning， artificial intelligence.

YI Jihai， born in 1974， M. S.， lecturer. His research interests include machine learning， artificial intelligence.

LI Bing， born in 1997， M. S. candidate. Her research interests include machine learning， artificial intelligence.

NIE Feiping， born in 1977， Ph. D.， professor. His research interests include machine learning， artificial intelligence.