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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

1）利用了“密度峰值”定義多數類樣本抽樣權重。考慮樣本的潛在空間結構，對于密度和峰值都較大的樣本，DPBCPUSBoost賦予其更大的抽樣權重。

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

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

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

1 相關工作

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

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

1.1 DPC算法

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

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

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

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

表2 樣本信息Tab. 2 Sample information

圖1 樣本分布Fig. 1 Sample distribution

圖2 決策圖Fig. 2 Decision diagram

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

1.2 Ball k-means算法

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

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

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

1.3 USCBoost算法

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

算法1 USCBoost算法。

b） Else

c） 欠采樣后的多數類樣本與全部少數類樣本組成臨時訓練集，并歸一化樣本權重；

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

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

2.1 定義抽樣權重

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

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

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

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

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

抽樣權重調整后，對其歸一化：

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

2.2 定義誤分代價

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

2.3 復雜度分析

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

算法2 DPBCPUSBoost算法。

b） Else

c） 將欠采樣后的多數類樣本與全部少數類樣本組成臨時訓練集，并歸一化樣本權重；

3 實驗與結果分析

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

3.1 實驗設置

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

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

表3 實驗數據集Tab. 3 Experimental datasets

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

本文選取決策樹樁（Decision Stump）作為弱分類器，Decision Stump是單層決策樹，其結構簡單，適合用作集成學習中的分類器。

3.2 評價指標

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

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

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

3.3 分類性能對比

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

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

由圖4可知，AdaCost的性能總體上優(yōu)于AdaBoost，因為其在樣本權重調整過程中，提高了有更高誤分代價樣本的權重；USCBoost的性能總體上優(yōu)于RUSBoost，因為其不僅結合了代價敏感學習，而且在欠采樣過程中保留了較高權重的樣本。

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

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

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

由表5初次迭代后的性能對比實驗結果可得出兩個結論：

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

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

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

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

3.4 運行時間對比

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

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

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

4 結語

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

[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] 胡姣姣，王曉峰，張萌，等.基于深度學習的時間序列數據異常檢測方法［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］.計算機應用，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] 劉穎，楊軻.基于深度集成學習的類極度不均衡數據信用欺詐檢測算法［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] 易東義，鄧根強，董超雄，等.基于圖卷積神經網絡的醫(yī)保欺詐檢測算法［J］.計算機應用，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］.計算機應用，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] 王偉，謝耀濱，尹青.針對不平衡數據的決策樹改進方法［J］.計算機應用，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] 徐玲玲，遲冬祥.面向不平衡數據集的機器學習分類策略［J］.計算機工程與應用，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] 陳木生，盧曉勇.三種用于垃圾網頁檢測的隨機欠采樣集成分類器［J］.計算機應用，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] 王俊紅，閆家榮.基于欠采樣和代價敏感的不平衡數據分類算法［J］.計算機應用，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] 萬建武，楊明.代價敏感學習方法綜述［J］.軟件學報，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。

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

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

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.