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

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

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

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

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

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

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

0 引言

在異常檢測［1-4］、信用欺詐檢測［5-7］、醫(yī)保欺詐檢測［8］、電信詐騙檢測［9-10］等應(yīng)用場景中，傳統(tǒng)分類模型往往較難取得理想的效果，因為傳統(tǒng)分類模型著重關(guān)注總體分類精度，在巨大的樣本數(shù)量差距下，少數(shù)類易被“忽視”。因此，研究者們提出了兩種策略來增加對少數(shù)類的“關(guān)注度”：一是對數(shù)據(jù)進行重構(gòu)，即減少多數(shù)類樣本數(shù)量或增加少數(shù)類樣本數(shù)量，使多數(shù)類和少數(shù)類樣本數(shù)量趨于平衡；二是在分類模型［11］和思想上聚焦于少數(shù)類的分類準確度［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)練速度。隨機欠采樣（Random UnderSampling， RUS）方法［13］是最簡易的欠采樣方法之一，其使用完全隨機的方法移除多數(shù)類樣本，顯然，RUS方法并沒有考慮到多數(shù)類樣本所攜帶的信息，極可能將一些對后續(xù)分類過程有價值的樣本移除。

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

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

文獻［25］中提出了密度峰值聚類（Clustering by fast search and find of Density Peaks， DPC）算法，該算法利用“密度”和“峰值”信息發(fā)現(xiàn)樣本的潛在層次結(jié)構(gòu)，基于這種結(jié)構(gòu)可對球形和非球形數(shù)據(jù)進行聚類。文獻［26］中提出了球k均值聚類算法（Ballk-means），該算法將類簇視為球并將其劃分為“穩(wěn)定區(qū)域”和“活動區(qū)域”，只計算“活動區(qū)域”與“近鄰簇”中心之間的距離，從而有效減少了質(zhì)心距離計算量。受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é)合了“密度峰值”定義誤分代價。DPBCPUSBoost同時考慮類依賴代價和樣本依賴代價，賦予少數(shù)類更高誤分代價的同時，也考慮到類簇內(nèi)部樣本分布的差異，對于密度和峰值都較大的樣本賦予更高的誤分代價。

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

1 相關(guān)工作

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

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

1.1 DPC算法

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

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

由式（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ù)文獻［25］的方法，可以選取樣本1和樣本2作為兩個類簇的中心。

1.2 Ball k-means算法

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

球簇內(nèi)“穩(wěn)定區(qū)域”以外的區(qū)域為“活動區(qū)域”，若球簇的近鄰簇數(shù)量多于一個，“活動區(qū)域”會被細分為多個“環(huán)形區(qū)域”。

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

1.3 USCBoost算法

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

算法1 USCBoost算法。

b） Else

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

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

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

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

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

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

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

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

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

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

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

2.2 定義誤分代價

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

2.3 復(fù)雜度分析

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

算法2 DPBCPUSBoost算法。

b） Else

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

3 實驗與結(jié)果分析

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

3.1 實驗設(shè)置

為驗證DPBCPUSBoost的有效性，在10個KEEL不平衡數(shù)據(jù)集（https：//sci2s.ugr.es/keel/imbalanced.php）上進行實驗，數(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ù)集均已用五折交叉驗證方式劃分為5個子數(shù)據(jù)集。

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

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

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

3.2 評價指標

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

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

Accuracy、F1-Score和G-mean等評價指標可通過混淆矩陣和以下計算式得出：

3.3 分類性能對比

為驗證本文算法的有效性，對各算法的分類性能進行測試。表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，因為其在樣本權(quán)重調(diào)整過程中，提高了有更高誤分代價樣本的權(quán)重；USCBoost的性能總體上優(yōu)于RUSBoost，因為其不僅結(jié)合了代價敏感學(xué)習(xí)，而且在欠采樣過程中保留了較高權(quán)重的樣本。

DPBCPUSBoost初次迭代利用樣本抽樣權(quán)重對多數(shù)類樣本進行欠采樣，RUSBoost和USCBoost初次迭代使用RUS對多數(shù)類進行欠采樣。因此，為驗證DPBCPUSBoost改進欠采樣方法的有效性，對這3個算法初次迭代后的性能進行測試。表5為各個算法在不同數(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初次迭代后的性能對比實驗結(jié)果可得出兩個結(jié)論：

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

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

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

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

3.4 運行時間對比

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

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

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

4 結(jié)語

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

[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ù)據(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] 張躍飛，王敬飛，陳斌，等.基于改進的Mask R-CNN的公路裂縫檢測算法［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］.計算機研究與發(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] 易東義，鄧根強，董超雄，等.基于圖卷積神經(jīng)網(wǎng)絡(luò)的醫(yī)保欺詐檢測算法［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］.計算機應(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］.計算機應(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ù)集的機器學(xué)習(xí)分類策略［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］.計算機應(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] 王俊紅，閆家榮.基于欠采樣和代價敏感的不平衡數(shù)據(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] 萬建武，楊明.代價敏感學(xué)習(xí)方法綜述［J］.軟件學(xué)報，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é)基金資助項目（61772427）；甘肅省高等學(xué)校創(chuàng)新能力提升資助項目（2021B?145，2021B?147）；甘肅省自然科學(xué)基金資助項目（17JR5RA177）；甘肅省重點研發(fā)計劃項目（21YF5FA087）。

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