基于樣本密度峰值的不平衡數據欠抽樣方法

蘇俊寧，葉東毅

(福州大學 數學與計算機科學學院，福州 350108)

0 引言

在許多模式分類的應用問題中，不同類別的數據分布往往是不平衡的[1-3]，即某些類別樣本的數量遠遠小于其他類別樣本的數量，其中樣本數少的類稱為少數類，樣本數大的類稱為多數類[4]。如果不考慮不平衡性因素的影響，傳統的機器學習算法對于不平衡數據的分類學習結果往往會傾向滿足多數類樣本的分類正確性而造成少數類樣本的誤分，也即容易產生分類決策邊界偏移[5]，降低了分類模型(特別是對少數類樣本正確分類)的泛化能力[6-7]，因此，研究如何有效處理不平衡數據的分類問題具有重要的理論和實際意義。

近年來，人們針對不平衡數據的分類問題提出了許多方法，這些方法大致分為三類[8]。

一是數據層面的方法[9-12]，即通過對不平衡數據集進行重抽樣而得到平衡的數據集，應用已有的學習算法對平衡處理后的數據集進行學習和建模。常用的抽樣方法包括對少數類樣本的過抽樣[9-10]和對多數類樣本的欠抽樣[11-12]，其中，SMOTE(Synthetic Minority Over-sampling TEchnique)[9]是一種經典的過抽樣方法，它通過插值擴充少數類樣本集使樣本數目達到均衡。一般來說，過抽樣容易產生過擬合，而欠抽樣可能丟失與分類相關的信息[5,13]。

二是算法層面的方法，即通過在學習算法中考慮不平衡的因素來改進現有的學習算法，使之適合于處理不平衡數據的分類問題[14-16]，如代價敏感支持向量機[14]，該算法通過對不同類型的錯分引入不同的懲罰代價，以保證分類器總體錯分代價最小。該類方法能有效地提高少數類的識別率，但在多數情況下，真實的錯分代價很難被準確估計[17]，且對于一些不能直接使用代價敏感學習的分類器，只能通過調整正負樣本比例或者決策閾值間接地實現代價敏感學習[18]，不能保證代價敏感學習的效果。

第三類融合了數據層面方法和算法層面方法[19-22]，通過對不平衡數據集進行多次重抽樣獲得多個不同的平衡訓練集，并訓練相應的分類器，最后對這些分類器進行集成[23]。該類方法已成為目前處理不平衡數據分類問題的一個主要方法，得到研究者的廣泛關注。例如：文獻[19]中提出的結合欠抽樣和bagging技術的RBBag(Roughly Balanced Bagging)算法，文獻[20]中提出的基于權重抽樣的uNBBag(under-sampling NeighBorhood Bagging)算法，文獻[21]中提出的基于樣本聚類的KAcBag(K-means Adacost Bagging)算法和文獻[22]中提出的同樣基于聚類和欠抽樣的CbUs(Clustering-based Under-sampling)算法。

盡管上述第三類型算法有效地提升了不平衡數據的分類性能，但是它們采用的欠抽樣方法在數據分布一致性保持和噪聲處理方面還存在不足，因而分類準確性有待進一步提高。具體而言，RBBag算法主要是隨機抽取多數類樣本獲得平衡數據集，并未考慮多數類樣本的分布特點，導致可能丟失多數類中與分類相關的有用信息，降低分類的質量；uNBBag算法同樣未考慮多數類數據的整體分布特點，也未考慮噪聲的處理；KAcBag算法根據K-means聚類算法對形成的不同類簇賦予不同的權重進行欠抽樣，雖然考慮了多數類數據分布的因素，但由于同一類簇的樣本被賦予相同的權重，因而不能充分體現同一類簇中的樣本分布信息；CbUs算法則采用一種基于聚類代表點的欠抽樣策略，該策略在一定程度上考慮了多數類數據分布的因素，但由于只考慮類簇中心作為抽樣代表點容易忽視邊界區域樣本的選擇，導致與決策面相關的有用信息丟失，進而影響分類特別是多數類的正確率。

針對上述方法存在的不足，本文提出一種基于樣本密度峰值的不平衡數據欠抽樣方法以及基于該欠抽樣方法的集成分類學習算法——DPBag(Density Peaks Bagging)，其欠抽樣的思路是通過考量樣本密度分布信息來盡量保持抽取樣本與多數類樣本數據分布的一致性。具體而言，該方法通過密度峰值聚類算法[22]完成多數類數據的聚類，并利用樣本局部密度和密度峰值的分布來賦予每個樣本權重，使得對于每個類簇而言，越靠近類簇中心區域的樣本權重越大，越接近邊界區域的樣本權重越小，盡可能使抽取的樣本集合能較好地反映多數類樣本的分布情況。實驗結果表明，與上述欠抽樣方法相比，在同樣采用集成學習方法對重抽樣得到的訓練集進行分類模型學習的情況下，本文的欠抽樣方法有效提高了分類的性能，取得了良好的改進效果。

1 基于樣本密度峰值的欠抽樣方法

1.1 密度峰值聚類算法

為便于描述本文提出的DPBag算法，首先簡要回顧一下算法抽樣權重計算中將要使用到的密度峰值聚類算法——DPC(Clustering by fast search and find of Density Peaks)[24]。該算法的基本思路是通過計算樣本點的局部密度并尋找密度峰值點，從而形成類簇。對于每個樣本點xi，DPC算法需計算兩個量：樣本點xi的局部密度ρi和該點到具有更高局部密度的點的最小距離δi，其定義如下：

(1)

其中：dij為樣本i，j間的歐氏距離；dc為截斷距離(由用戶設置的距離)。

(2)

DPC算法將具有高δ值和相對較高ρ值的點作為類簇中心，而具有高δ值和較低ρ值的點往往是離群點或噪聲點。在類簇中心找到后，剩余點被歸屬到具有更高密度的最近鄰點所屬類簇。一般來說，DPC算法具有較好的區分類簇中心、邊界樣本和離群點(含噪聲)的能力。

1.2 本文提出的DPBag算法

DPBag算法的核心在于對多數類欠抽樣的樣本權重計算方法。

1.2.1 樣本權重的計算

樣本權重計算的基本思想是使得抽樣后的樣本與原始樣本的分布盡量保持一致。注意到，DPC聚類算法中的δ值和ρ值可以較好地反映樣本點在相應類簇中所處的位置，即對于任意一個樣本點xi而言：

①若xi具有較高δ值和較高ρ值時，則該點被判定為類簇中心；

②若xi具有較高δ值和較低ρ值時，則該點被判定為噪聲點或小類簇點；

③若xi具有較低δ值和較高ρ值時，則該點被判定為類簇中心周邊點；

④若xi具有較低δ值和較低ρ值時，則該點被判定為邊界點。

由此依據樣本點xi的δ值和ρ值，本文提出如下的多數類樣本欠抽樣權重計算方法。

首先對δ值進行歸一化處理使之屬于0到1之間，其次，根據ρ值和歸一化后的δ值初始化多數類樣本的權重，對于樣本xi，令其權值為：

wi=(ρi+1)eδi

(3)

式(3)所得初始化結果使得各類簇中心具有最大的權值，其他點的權值較小。在初始化權重的基礎上，根據DPC算法對多數類樣本的聚類結果進行權值更新，具體規則如下。

(4)

由于wk-wi>0，則：

因此可得：

1)當樣本點xi為類簇中心周邊點時，因為其ρi值與類簇中心的ρk值相近，故權值更新后類簇中心周邊樣本的權值得到了提高。

2)當樣本點xi為邊界點或噪聲點時，由于邊界點和噪聲點的ρ值較小，即ρi?ρk，由式(4)可知樣本點xi更新后的權值近似不變。

由上述分析可知，經過權重更新后，對于多數類的每一個類簇，樣本權重值盡可能由類簇中心區域向邊界區域呈現逐漸遞減的趨勢，因而以此權重抽樣的樣本與該類簇樣本的分布較為近似，并能一定程度上抑制噪聲數據。

1.2.2 基于加權Bagging的分類器集成

前述RBBag、uNBBag、KAcBag等算法使用的分類器學習均采用基于Bagging的集成學習方法。為便于算法性能比較，本文同樣采用這種集成學習的方法構建分類器。Bagging方法[15]是由多個子分類器投票返回預測的類標簽，可以提高基分類器的準確率。考慮到抽樣的不確定性將導致每個子分類器的性能不同，因此，一般采用加權的方法賦予每個子分類器不同的權重以反映其對最終預測結果的貢獻程度[17,19],其中對于子分類器hi權重αi定義如下：

(5)

其中，少數類樣本權重的計算方法與多數類樣本相同，由于處于少數類邊界樣本對分類性能影響更大[10]，因此對少數類樣本權重wj-minority進行求倒數運算，即：

wj-minority′=1/wj-minority

error(hi)為子分類器hi的錯分率，即hi誤分訓練樣本子集Di的樣本權重和，計算公式為：

若樣本xd被誤分，則err(xd)為1；否則err(xd)為0。

1.2.3 DPBag算法具體過程

考慮到對于一些小規模或高度不平衡(不平衡比率大于等于9的數據集[25])的不平衡數據集，單獨采用欠抽樣會使訓練集樣本過小而導致整體分類性能下降，因此針對這種情況，本文加入過抽樣策略來處理單純的欠抽樣所帶來的缺陷。

給定一個分類器學習算法WeakLearn，DPBag算法步驟如下,其具體框架如圖1所示。

輸入：訓練集D，參數dc的百分比，迭代次數T。

輸出：集成分類模型H。

步驟2 對每個多數類樣本點xi，按照權重大小計算其被抽取概率，即：

步驟3 若N/M≥9，則對少數類樣本進行過抽樣，且過抽樣率為「N/(5*M)?*100%；

步驟4 樣本抽取以及子分類器的訓練

fort=1 toT

/*可并行執行*/

1)依照賭輪原則[26]對多數類樣本進行欠抽樣，得到與少數類樣本數量相同的多數類樣本集，與所有少數類樣本構成一個平衡訓練集Dt；

2)應用Weaklearn對Dt進行學習，獲得子分類器ht，計算子分類器權重αt(式(5))。

步驟5 生成集成模型：

其中符號函數sign定義為：

圖1 DPBag算法框架Fig. 1 Framework of DPBag algorithm

由上述算法流程可以得出DPBag算法由三部分構成：權重的計算、按照權重對訓練集進行重采樣以及基于加權baggin的分類器集成。首先，權重的計算方法利用了DPC聚類算法中的δ值和ρ值可以較好地反映樣本點在相應類簇中所處位置的特性，賦予樣本點權重，使得對于多數類的每一個類簇，樣本權重值盡可能由類簇中心區域向邊界區域呈現逐漸遞減的趨勢；然后按照該權重對多數類進行欠抽樣，使得抽取的樣本既能平衡訓練集，又盡可能地與原始樣本的分布保持一致，提高少數類的分類性能；最后，利用集成學習提高不平衡數據整體分類性能的特點，考慮了抽樣的不確定性給子分類器帶來的影響，賦予了子分類器權重，使得集成分類器能更好地提高不平衡數據集的整體分類性能。

1.2.4 DPBag算法復雜度分析

DPBag算法復雜度主要包括兩個方面，如下所示。

1)樣本權重的計算，即應用DPC算法分別計算多數類和少數類樣本權重，由于多數類樣本數遠多于少數類樣本數，因此該部分復雜度量級上等于計算多數類樣本權重的復雜度：

a)計算樣本間的距離O(N2)；

b)計算多數類樣本的密度ρ值O(N2)；

c)計算多數類樣本的δ值O(N2)；

d)初始化多數類樣本權重O(N)；

e)依據聚類結果對多數類樣本權重更新O(N)。

因此，權重計算的總復雜度為O(N2)。

2)T輪分類器的訓練。設基分類器訓練為CART(Classification And Regression Tree)算法，其時間復雜度與抽樣獲得的平衡訓練集Dt大小成線性關系，為O(|Dt|)，|Dt|=2M，故T輪分類器的訓練時間為O(2TM)。

因此，DPBag算法的復雜度為O(N2)+O(2TM)。

針對在引言中敘述的其他欠抽樣方法RBBag、uNBBag、KAcBag和CbUs四種算法，其時間復雜度如表1所示。

表1 4種算法的時間復雜度對比 Tab. 1 Time complexity comparison of four algorithms

通過對比可以得出本文算法與其他欠抽樣算法的時間復雜度差別主要在于樣本抽取的過程，雖然本文時間花費稍大，但其所抽取的樣本與原始數據集的分布較為近似，并能一定程度上抑制噪聲數據。

2 實驗結果與分析

2.1 分類的評價方法

不平衡數據分類問題的常用標準有：查全率(Recall)、查準率(Precision)、F1-measure以及G-mean[27]。其計算方法均建立在表2混淆矩陣的基礎上，其中正類和負類分別表示少數類和多數類。Recall、Precision、F1-measure、G-mean值計算方法如下：

表2 二類問題的混淆矩陣 Tab. 2 Confusion matrix for two-class problem

F1-measure是一種反映分類器對少數類樣本識別率的評價指標，它是Recall和Precision的組合，僅當少數類的Recall值和Precision值都較大時，它的F1-measure值才較大。此外G-mean是一種度量單個數據集整體分類性能的評價指標，僅當分類器對多數類和少數類的分類精度都較大時，才能獲得較大的G-mean值。本實驗采用F1-measure和G-mean來衡量算法的分類性能。

由于F1-measure和G-mean是從單個數據集上衡量不同分類算法性能的指標，因此為了從整體上比較各種分類算法優劣，本文引入Friedman檢驗[28]和Wilcoxon符號秩檢驗[28]來衡量各重抽樣方法整體性能上的差異。其中，Friedman檢驗是利用秩判斷不同算法是否存在顯著性差異的非參數檢驗方法；而Wilcoxon符號秩檢驗是通過分析兩配對樣本，推斷樣本來自的兩個算法是否存在顯著性差異。

2.2 實驗設置

本文選擇12個少數類和多數類樣本不平衡且具有不同實際應用背景的UCI數據集[29]進行實驗。各數據集的基本信息如表3所示，其中，對于有多個類別屬性的數據，將數量最少的若干類別作為少數類，將其他類合并為一個多數類；最后一列表示數據集不平衡比率(Imbalanced Ratio, IR)，即多數類樣本數與少數類樣本數的比值。

表3 UCI數據集的基本信息 Tab. 3 Information of UCI datasets

本實驗將DPBag算法與OvBag(Over-Bagging)[30]、SmBag(SMOTE-Bagging)[30]、oNBBag(over-sampling Neighborhood Bagging)[20]三種過抽樣算法以及RBBag[19]、uNBBag[20]、KAcBag[21]和CbUs[22]四種欠抽樣算法在F1-measure和G-mean兩個指標上的結果進行對比分析，如表4所示。

實驗中，對DPBag算法設置如下：按照DPC算法的推薦做法，將數據集中兩兩樣本之間的距離按照由小到大的方式排序，處于第2%位置的值作為截斷距離dc的值；針對不平衡比率大于9的數據集，使用隨機過抽樣方法，過抽樣率設為「IR/5?。對CbUs算法設置如下：選擇其中實驗效果更好的策略2，即用K-means聚類算法對多數類樣本進行聚類，將聚類中心的最近鄰真實樣本作為多數類代表點與所有少數類樣本組成平衡數據集用于分類器的訓練；聚類個數K設為少數類樣本數。將weka軟件[31]的J48決策樹算法(C4.5)作為基分類器，算法參數使用weka中的默認參數設置。

2.3 結果分析

為了使實驗更具客觀性，采用十折交叉驗證的方法對分類效果進行驗證，將均值作為最終結果。表4為8種算法在12個UCI數據集上的F1-measure值和G-mean值，表中的每行表示數據集在對應算法上的實驗結果，每一行中的最高值以加粗下劃線表示，第二高值以加粗表示；表格最后一行為每種算法在所有數據集上的平均秩，其值越小說明算法性能越好。表5為不同算法兩兩比較的Wilcoxon符號秩檢驗結果。為了更直觀體現算法對比的結果，圖2給出8種算法在12個數據集上F1-measure值和G-mean值的平均值的圖形表示。

由表4可知，對于F1-measure和G-mean兩個評價指標而言，本文的DPBag算法在12個數據集上的平均秩分別為1.92和2.17，排名均為第1，說明它在8種算法中的平均性能最優。此外，相對G-mean指標而言，DPBag算法在F1-measure指標上的優勢更為明顯，由圖2可以看出，它在12個數據集上的平均F1-measure值明顯高于其他7種算法的對應值，而且比它們中取得最高值的KAcBag算法高出2.36%。對于abalone和yeast數據集，可以看出過抽樣算法OvBag、SmBag和oNBBag得到的F1-measure值明顯優于欠抽樣算法uNBBag、RBBag、KAcBag和CbUS。這是因為這些數據集中少數類樣本過少且數據集的不平衡程度較高，使得欠抽樣算法得到的平衡數據集丟失過多的多數類樣本，造成分類性能降低，但本文增加的過抽樣策略能較為有效地處理該問題，如對yeast數據集，DPBag算法與欠抽樣算法相比，與F1-measure值的最高值之差為+15.89%，與G-mean值的最高值之差為-6.16%；同時DPBag算法與過抽樣算法相比，其F1-measure值為最高，并且G-mean值也高于過抽樣算法中的最高值+6.06%。

從Friedman統計檢驗的角度看，F1-measure上的Friedman檢驗結果為0.009(p<0.05)，G-mean上的Friedman檢驗結果小于0.001(p<0.05)，說明8種算法F1-measure和G-mean指標在整體上均有顯著性差異。

由表5的Wilcoxon符號秩檢驗結果以及圖2所展示的8種方法在12個數據集上的平均F1-measure值可以得出DPBag算法在F1-measure指標上顯著優于其他7種算法；在G-mean指標上，DPBag算法與KAcBag算法無顯著性差異，但均優于其他6種算法。

表4 DPBag算法與其他抽樣算法的F1-measure值、G-mean值對比 單位：% Tab. 4 F1-measure and G-mean comparison of DPBag and other sampling algorithms unit:%

表5 DPBag算法與其他抽樣算法兩兩比較的Wilcoxon符號秩檢驗 Tab. 5 Wilcoxon sign rank test for DPBag and other sampling algorithms

圖2 12個數據集上F1-measure值和G-mean值的平均值Fig. 2 Average F1-measure and G-mean on 12 datasets

綜合以上分析，在12個不平衡的數據集上，DPBag算法取得了良好的改進效果，說明本文提出的DPBag算法通過盡量保持欠抽樣樣本與原始樣本分布的一致性對于提高不平衡數據的分類精度是一個合理、有效的途徑；并且針對欠抽樣算法在少數類樣本過少且不平衡程度較高的不平衡數據集下F1-measure值較低的問題，DPBag算法增加的過抽樣策略有效地處理了該情況，在對整體分類性能影響較小的情況下，提升了分類器對少數類的識別率。

為了觀察參數dc值對DPBag算法的影響，圖3和圖4分別給出DPBag算法在取不同dc值[1%，2%，3%，4%，5%]的情況下F1-measure值和G-mean值的變化。

由圖3和圖4可得，從整體上看dc值的選取對DPBag算法的影響較小，當dc值取2%、3%時，兩個評價指標均可以取得較好的結果。

由于Yeast是典型的不平衡數據集，其不平衡比率較大且樣本數較多，因此本文主要針對該數據集觀察不同的過抽樣率[100%,1 000%]對DPBag算法的影響。圖5給出dc=2%時不同過抽樣率對DPBag算法的F1-measure值和G-mean值的影響。

由圖5可得，當過抽樣率達到500%以上(接近「IR/5?，即「28.1/5?)時，F1-measure值逐漸達到峰值，而G-mean值呈下降趨勢，這是由于當過抽樣率過大時，分類器對訓練集產生了過擬合現象，因此，選擇合適的過抽樣率，少數類的F1-measure值和整體性能的G-mean值均能取得較好的結果。

圖3 不同dc值對F1-measure值的影響Fig. 3 Effect of different dc values on F1-measure

圖4 不同dc值對G-mean值的影響Fig. 4 Effect of different dc values on G-mean

圖5 不同過抽樣率的實驗結果(dc=2%)Fig. 5 Experimental results of different oversampling rates(dc=2%)

3 結語

本文研究了不平衡數據分類問題中的數據重抽樣方法。針對現有欠抽樣方法在樣本分布一致性保持和噪聲數據處理方面存在的不足，提出一種基于樣本密度峰值的不平衡數據欠抽樣方法。該方法應用密度峰值聚類算法中的樣本密度峰值和局部密度來初始化多數類樣本權重，通過計算樣本與類簇中心密度差異來更新多數類權重信息，按照權重大小對多數類樣本進行欠抽樣，使得所抽取的多數類樣本盡可能由類簇中心區域向邊界區域逐步遞減，既能較好地反映原始數據集的分布又可有效抑制噪聲數據，減小決策面的偏倚程度。在UCI數據集上的實驗結果表明，與近期的重抽樣方法相比，在同樣采用集成學習方法對重抽樣得到的訓練集進行分類模型學習的情況下，本文方法取得了較為明顯的改進效果，達到了相對最佳的總體泛化性能。這表明盡量保持欠抽樣樣本與原始樣本分布的一致性對于提高不平衡數據的最終集成分類精度是一個合理可行的途徑。當然，本文方法還存在一些需要改進的地方，在權重計算方面，噪聲數據和邊界樣本的權重都較小，不易被區分，因此如何進一步地區分邊界樣本和噪聲數據將成為下一階段的研究重點。