考慮類內不平衡的譜聚類過抽樣方法

駱自超，金 隼，邱雪峰

LUO Zichao,JIN Sun,QIU Xuefeng

上海交通大學 機械與動力工程學院，上海 200000

School of Mechanical Engineering,Shanghai Jiaotong University,Shanghai 200000,China

1 引言

不平衡數據集指某些類包含的樣本數遠大于其他類樣本數的數據集。在分類算法的現實應用中，不平衡的數據結構是一個普遍存在的問題，例如識別油井泄漏[1]、進行醫學診斷[2]、檢測信用卡詐騙[3]等等。研究者發現不平衡數據結構會降低分類算法的性能。

不平衡分類中，樣本數較少的類叫做少數類，這類樣本往往是關注的重點，需要很高的識別精度。但是標準分類器是基于數據平衡分布的假設建立的，在處理不平衡數據集中，難以得到令人滿意的少數類識別率。為此，不平衡數據分類問題越來越受到學界廣泛關注，并且被一些學者認為是數據挖掘領域的關鍵挑戰之一[4]。

不平衡數據集中少數類樣本往往可以再劃分為幾個子類，因此數據的不平衡結構可再細分為類間不平衡與類內不平衡。前者指多數集與少數集之間存在的數據樣本量不平衡情況，后者則是少數類樣本中各子類間樣本數據量的不平衡。

當前解決不平衡分類問題的方法可以分為算法層面的方法和數據層面的方法兩類：前者是通過改進標準分類算法，使分類器適應不平衡數據集下的分類；后者則是通過對數據集進行處理，減少數據不平衡程度，從而使分類器能夠在平衡的數據集上進行學習，提高少數類的分類正確率。

數據層面的不平衡分類處理方法又分為欠抽樣和過抽樣，在過抽樣方法中，基于聚類的過抽樣方法[5-9]是較受學者關注的一類。當前基于聚類的過抽樣方法有兩方面不足：首先，這類方法主要建立在k均值聚類算法的基礎上，聚類效果對初始中心的選擇和分類個數的選定非常敏感，并且傾向于生成大小相似的類，在實際應用中聚類不穩定、效果有待提高；其次，這類方法僅考慮類間不平衡，沒有考慮普遍存在的類間不平衡的情況。

針對以上兩個問題，本文提出一種基于改進的譜聚類的過抽樣方法處理存在類內不平衡的數據集。該方法首先自動選擇合理的聚類個數并對少數類樣本進行譜聚類，再根據簇內包含的樣本個數與少數類總樣本數之比決定對每個簇生成的新樣本數量，最后采用SMOTE方法進行新樣本生成，使數據集在類間和類內均趨于平衡。

2 不平衡數據集處理方法

不平衡數據分類問題處理方法分為算法層面和數據層面兩類。Maloof等指出，通過算法層面方法調整誤分代價策略獲得的分類面和在經過數據重抽樣的數據集上進行學習獲得的分類面幾乎完全一致[10]。即采用這兩類方法獲得的結果是非常相近的，因此本文只研究數據層面的不平衡數據集處理方法。

另外，本文的研究只針對二分類問題，即一個數據集中僅含有一個多數類和一個少數類。對于多分類的情況，可以將其分解為多個二分類問題[11]，或者通過逐對耦合方法，將針對二分類的算法擴展到多分類問題[12]。

針對二分類的不平衡數據分類問題，數據層面的方法分為欠抽樣和過抽樣兩類，前者減少多數類中包含的樣本數，從而獲得相對平衡的新數據集，后者則在少數類中生成新的樣本點，使新數據集達到平衡。

2.1 欠抽樣方法

最原始的欠抽樣方法是隨機欠抽樣，這種方法從多數類中隨機刪去數據樣本，從而獲得平衡數據集。這類方法的主要缺陷在于可能刪去數據集中的重要信息。Kubat[13]提出了單側選擇（One-Sided Selection）算法，檢測并刪除多數類中的冗余和噪聲點，從而獲得較為清晰的邊界。Yen和Lee[14]提出了基于聚類的欠抽樣方法，首先對所有訓練樣本進行聚類，再根據多數類樣本數與少數類樣本數之比計算每個類中應該保留的樣本個數，最后隨機刪除每個類中的多數類樣本，使得該類中樣本總數滿足要求。Yu等[15]提出ACOsampling，用蟻群算法尋找原始多數類集中最優的子集，從而篩選出多數類中包含最多信息的樣本點。將該子集與原少數類重新組合，即獲得相對平衡的新數據集。

2.2 過抽樣方法

過抽樣方法中，隨機過抽樣方法隨機復制少數類樣本，而不對多數類數據進行處理。該方法會導致分類器，尤其是分類樹的決策域收縮，從而引起過擬合[16]。由 Chawla等[17]提出的 SMOTE（Synthetic Minority Oversampling Technique）算法在特征空間中相鄰的樣本之間進行線性插值，從而獲得需要的新少數類樣本。Han等[18]發現不平衡數據分類中，誤分樣本大多位于多數類和少數類的邊界上，因此他們提出先篩選出位于邊界上的少數類樣本。在進行過抽樣時，只對邊界上的少數類樣本進行操作。He等[19]針對之前的過抽樣方法沒有考慮到樣本分布，對每個樣本合成同樣數量的新數據樣本的問題，以每個少數類樣本k個最近鄰樣本中多數類樣本的數量為依據，為周邊多數類樣本多的少數類樣本生成較多新樣本。為了防止在過抽樣中生成噪聲，Barua等[6]設計了CBOS（Cluster Based Synthetic Oversampling）算法，利用層級聚類先對少數類進行聚類，再在每個類之內合成新樣本。

3 基于改進譜聚類的過抽樣方法

本文提出一種基于改進譜聚類的過抽樣方法（Spectral Clustering based Over Sampling，SCOS），該方法首先自動確定聚類個數，再對少數類數據集進行譜聚類，之后根據每個類內包含的樣本個數與總的少數類樣本個數之比，確定在每個類內部合成的樣本數，最后通過在類內部進行SMOTE過抽樣，獲得相對平衡的新數據集。算法流程框圖如圖1所示。

圖1 算法流程圖

3.1 改進的譜聚類算法

譜聚類（Spectral Clustering）算法的思想來自圖論，它將每個數據作為一個圖節點，將聚類問題轉化為帶權無向圖的分割問題[20]。盡管構建的相似度表征和映射方法不同，導致具體實現方法很多，但是譜聚類的基本思路都是先對樣本數據的相似矩陣進行分解，再將得到的特征向量進行聚類[21]。

標準譜聚類中，聚類數需要根據經驗選擇，但是面對未知的數據結構，聚類數的人工選擇往往會造成某些類中數據量過少，這對于過抽樣中新樣本的生成是非常不利的。針對這個問題，本文改進譜聚類方法使其自動選擇聚類數，以保證每個類中樣本數都達到一定值，以便下一步進行過抽樣。具體實現步驟如下：

（1）將初始聚類數k設為10。

（2）取出少數類樣本，設少數類集中包含n個樣本，則可用一個n×n矩陣W表述少數類數據樣本兩兩之間的相似性：

W(i，j)代表數據點Si與Sj之間的相似程度，且有W(i，j)=W(j， i)， W(i，i)=0 。其中，d(si，sj)取為歐幾里德距離，σ為尺度參數。

（3）根據下式計算矩陣D：

（4）令L=D-W ，根據聚類個數k求L矩陣的前k個特征值（按照特征值升序排列）以及對應的特征向量。

（5）將這k個特征向量按列排成一個n×k矩陣，其中每一行可以看作原數據點在k維空間中的投影坐標。用k均值聚類算法對這n個少數類樣本點進行聚類。

（6）檢驗是否每個類中樣本數均大于n/20，如果滿足該條件，則聚類結束；如果不滿足，則k=k-1，重復步驟（2）～（5）。

3.2 優化的SMOTE算法

SMOTE算法因為其易于實現以及在現實應用中效果顯著，被學者大量應用于解決不平衡分類問題，但是SMOTE算法對每個少數類樣本均生成相同個數的新樣本，對類內不平衡沒有改善作用。為解決這個問題，本文優化了SMOTE算法，在合成新樣本之前，根據每個類內包含的樣本個數與總的少數類樣本個數之比，確定在每個類內部合成的樣本數，以平衡少數類的子類數據量。具體步驟如下：

（1）根據過抽樣比率η，計算需要生成的少數類樣本個數：

其中，n為少數類樣本總數。

（2）計算每個類包含樣本個數與少數類總樣本個數之比：

其中Ci為每個類所包含樣本個數。

（3）將 g從大到小排序，記錄 gi對應的序號 j，j=1，2，…，k。

（4）計算為每個類合成的樣本數：

（5）在每個類內執行SMOTE算法（步驟參見文獻[16]），生成指定個數的樣本。

4 實驗設定

為驗證上述算法的有效性，本文在一個合成數據集和四個來自UCI機器學習數據庫的實際數據集上，將本文提出的算法與SMOTE[17]、CBOS[6]和基于k均值聚類的過抽樣算法[8]進行對比測試。在獲得相對平衡的數據集后，用標準CART（Classification And Regression Tree）分類樹[22]進行分類，測試中采用三次獨立的十折交叉驗證（10-fold cross validation），最終性能度量取三次的平均值。

4.1 數據集

（1）為驗證本文算法在實際不平衡數據集分類中的性能，本文在表1所列出的四個實際數據集上對算法進行測試。在具有多個類別的數據集中，選取其中一類為少數類，而將其他所有類別合并成為多數類。

表1 數據集描述

（2）為進一步考察基于k均值和譜聚類的兩種過抽樣方法在目標數據集存在少數類類內不平衡，區域重合（綠色與紅色區域部分重疊）和類間距離差異等特性下的性能，采用如圖2所示二維合成不平衡數據集對進行測試。圖2（a）中，黑色點代表10000個多數類樣本，青色代表少數類樣本，共1600個。少數類本身存在類內不平衡，它由圖2（b）所示綠色區域的1000個樣本，紅色區域的500個樣本和藍色區域的100個樣本組成。其中該綠色區域中心為[0.4，0.5]，紅色區域為[0.7，0.3]，藍色區域為[0.8，0.8]。

4.2 評價指標

在不平衡分類問題中，少數類具有更高的價值，誤分少數類和誤分多數類的代價不同，傳統分類中廣泛采用的總體精度基于兩類誤分等代價的假設，無法準確體現分類器性能。在不平衡分類中，F-measure和G-mean是更加合理的評價指標，在許多研究中得到應用。它們的計算方式如下：

圖2 合成數據集的數據結構

其中 β表示Precision和Recall的相對重要性，通常設為1。 F-measure和G-mean都是0到1之間的值，值越大，分類器性能越好。上式中Precision，Recall，Acc+和Acc-的定義如下：

其中，Tp，Fp，Tn，Fn分別表示被分類器正確分類的少數類樣本個數，被錯誤分類的少數類樣本個數，被正確分類的多數類樣本個數，被錯誤分類的多數類樣本個數。

為全面評價算法性能，本文同時采用F-measure，G-mean和Recall三個評價指標對分類結果進行評估。

5 實驗結果與分析

5.1 實際數據驗證結果

在實際數據集上進行驗證時，算法參數的選擇如下：過抽樣比率設為200%，譜聚類的尺度參數σ設為0.02，SMOTE中近鄰數設為5，基于k均值聚類的過抽樣算法中，為更好對比聚類部分對整個算法性能的影響，其聚類數也采用3.1節中描述的自動選擇方法確定。在原始數據（Origin）以及經過SMOTE算法、CBOS算法、基于k均值聚類的過抽樣算法和本文提出的SCOS算法四種不同過抽樣方法處理過的數據集上用CART進行分類，結果如表2所示（評價指標中最好的用粗體表示）。

表2 過抽樣率200%時不同方法實驗結果對比

本文選取了不同不平衡率、不同維數的四個不平衡數據集對算法進行了測試，實驗結果表明：

（1）對比原數據集，在過抽樣方法處理過的數據集上使用分類器能顯著提高分類結果。

（2）對比SMOTE和其他三種方法，可以觀察到基于聚類的過抽樣方法對不平衡分類效果的提升作用更加明顯。這是因為SMOTE算法的假設較為簡單，沒有考慮少數類在樣本空間中分布的情況，因此在新樣本合成中會引入噪聲，影響最終的分類精度。

（3）本文提出的研究方法在四個數據集上都取得了很好的效果，證明了基于譜聚類的過抽樣方法的有效性。

5.2 合成數據測試結果

由于算法復雜度低、實現容易等優點，k均值聚類在基于聚類的過抽樣方法中被學者大量采用[8-9，23]。但是k均值聚類對聚類個數設定敏感，魯棒性差，并且傾向于將數據集劃分為大小相同的類。這些特點讓基于k均值聚類的過抽樣方法在處理存在類內不平衡的數據集時，可能在多數類所處區域合成大量噪聲，反而降低分類器的總體性能。

為了排除實際數據集中難以避免的對分類器性能造成影響的其他因素，本文采用合成數據集僅僅針對類內不平衡驗證不同聚類方式對過抽樣算法的影響。本文在過抽樣率分別為100%，200%，300%，400%，500%，600%的條件下，在合成數據集上對基于k均值聚類的過抽樣方法和基于譜聚類的過抽樣方法性能進行研究。結果如表3所示。

為更直觀比較二者性能，將表3結果可視化如圖3所示。

圖3 兩種基于聚類的過抽樣方法性能圖

通過對比圖3（a）與圖3（b）可以觀察到，基于不同聚類方法的過抽樣算法在性能表現上有一定差異：基于k均值聚類的過抽樣方法對少數類樣本的分類精度在達到一定高度之后基本保持穩定，但是F-measure和G-mean在過抽樣率300%到600%時呈下降趨勢，這說明隨著新樣本的生產，基于k均值聚類的過抽樣方法在少數類中生成了一些噪聲點，導致部分多數類樣本被錯誤地劃分入少數類，從而引起分類器綜合性能下降。而基于譜聚類的過抽樣方法隨著過抽樣率的增加，總體上保持性能上升，說明這種方法能有效減少噪聲生成。

為了研究上述兩種基于聚類的過抽樣方法性能差異的原因，對圖2（b）表示的少數類樣本分別進行k=3，k=4，k=5的k均值聚類和譜聚類（譜聚類中σ取0.02），結果如圖4和圖5所示。

對比圖4和圖5，可以觀察到k均值聚類在預先給定的聚類數不合理時(k=4，5)，傾向于將樣本數多的子類進行分割，不能忠實反映原數據集的特性；即使給定了正確聚類數(k=3)，k均值算法仍然傾向于獲得大小相近的類，因此出現了圖4（a）中，兩個包含樣本數目較少的類（紅、藍區域）對樣本數較多的類（綠色區域）的“入侵”。而在圖5中，可以明顯看到譜聚類的結果更加穩定，在給定類數據不合理時，仍然能很好地反映原始數據的結構。

聚類的結果很好地解釋了隨著過抽樣率提高，兩種方法在性能表現上的差異：在圖4所示的k聚類基礎上進行過抽樣，則在藍色所示類中合成新樣本，會出現落在多數類區域的噪聲點，影響分類器的綜合性能。而基于譜聚類進行過抽樣時，這個問題得到了很大改善。因此隨著過抽樣率的提高，基于k均值聚類的過抽樣算法性能下降，而基于譜聚類的過抽樣算法性能保持穩定。

表3 過抽樣率改變時兩種過抽樣方法實驗結果對比

圖4 不同k值情況下k均值聚類結果

圖5 不同k值情況下譜聚類結果

6 結論

不平衡數據分類問題是數據挖掘領域面臨的重要挑戰之一，過抽樣方法是解決不平衡問題的一種有效方法。

在之前過抽樣算法中，學者們對類內不平衡問題缺乏重視。本文提出了一種基于改進譜聚類的過抽樣方法，該方法首先自動確定聚類數，再對少數類數據集進行譜聚類，之后根據每個類內包含的樣本個數與總的少數類樣本個數之比，確定在每個類內部合成的樣本數，最后通過在類內進行SMOTE過抽樣，獲得相對平衡的新數據集。

通過在現實數據集上的測試，本文提出方法的有效性得到了驗證。本文進一步研究了在二維合成數據集上基于k均值聚類和譜聚類過抽樣方法的性能，發現聚類效果對過抽樣算法的最終性能有重要影響。譜聚類算法的魯棒性強，對聚類數選擇不敏感，基于該方法進行過抽樣能獲得較好的效果。

[1]Kubat M，Holte R C，Matwin S.Machine learning for the detection of oil spills in satellite radar images[J].Machine Learning，1998，30（2/3）：195-215.

[2]Ling C X，Sheng V S，Yang Q.Teststrategiesfor cost-sensitive decision trees[J].IEEE Transactions on Knowledge and Data Engineering，2006，18（8）：1055-1067.

[3]Chan P K，Stolfo S J.Toward scalablelearning with non-uniform class and cost distributions：a case study in credit card fraud detection[C]//Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining，New York，1998：164-168.

[4]Yang Q，Wu X.10 challenging problems in data mining research[J].International Journal of Information Technology&Decision Making，2006，5（4）：597-604.

[5]陳思，郭躬德，陳黎飛.基于聚類融合的不平衡數據分類方法[J].模式識別與人工智能，2010，23（5）.

[6]Barua S，Islam M M，Murase K.A novel synthetic minority oversampling technique for imbalanced data set learning[C]//Proceedings ofthe 18th InternationalConference on Neural Information Processing，2011，7063：735-744.

[7]Kollios G，Gunopulos D，Koudas N，et al.Efficient biased sampling for approximate clustering and outlier detection in large data sets[J].IEEE Transactions on Knowledge and Data Engineering，2003，15（5）：1170-1187.

[8]陳川，張化祥.基于聚類的少數類樣本采樣方法[J].信息技術與信息化，2011（5）：65-68.

[9]楊永，王莉利.基于K-means聚類和遺傳算法的少數類樣本采樣方法研究[J].科學技術與工程，2010，10（10）：2334-2338.

[10]Maloof M A.Learning when data sets are imbalanced and when costs are unequal and unknown[C]//Proceedings of International Conference on Machine Learning，Workshop on Learning from Imbalanced Data Sets II，Washington DC，2003.

[11]Ou G，Murphey Y L.Multi-class pattern classification using neural networks[J].Pattern Recognition，2007，40（1）：4-18.

[12]Fernández A，Del Jesus M J，Herrera F.Computational intelligence forknowledge-based systems design[M].Heidelberg：Springer，2010：89-98.

[13]Kubat M，MatwinS.Addressingthecurseofimbalanced training sets：one-sided selection[C]//Proceedings of the 14th International Conference on Machine Learning，San Francisco，1997，97：179-186.

[14]Yen S J，Lee Y S.Cluster-based under-sampling approaches for imbalanced data distributions[J].Expert Systems with Applications，2009，36（3）：5718-5727.

[15]Yu H，Ni J，Zhao J.ACOSampling：an ant colony optimization-based undersampling method forclassifying imbalanced DNA microarray data[J].Neurocomputing，2012，101：309-318.

[16]Weiss G M，Provost F J.Learning when training data are costly：the effect of class distribution on tree induction[J].Jounal of Artificial Intelligence Research，2003，19：315-354.

[17]Chawla N V，Bowyer K W，Hall L O，et al.SMOTE：synthetic minority over-sampling technique[J].Journal of Artificial Intelligence Research，2002，16（1）：321-357.

[18]Han H，Wang W Y，Mao B H.Borderline-SMOTE：a new over-sampling method in imbalanced data sets learning[C]//Proceedings of International Conference on Intelligent Computing，2005，3644：878-887.

[19]He H，Bai Y，Garcia E A，et al.ADASYN：Adaptive synthetic sampling approach for imbalanced learning[C]//ProceedingsofIEEE InternationalJointConference on Neural Networks，2008：1322-1328.

[20]蔡曉妍，戴冠中，楊黎斌.譜聚類算法綜述[J].計算機科學，2008，35（7）：14-18.

[21]Verma D，Meila M.A comparison of spectral clustering algorithms[R].Washingtong DC：Department of CSE，University of Washington，2005.

[22]Steinberg D，Colla P.CART：classification and regression trees[M].San Diego，CA：Salford Systems，2009：179-201.

[23]Nickerson A，JapkowiczN，MiliosE.Using unsupervised learning to guide resampling in imbalanced data sets[C]//Proceedings of the 8th International Workshop on Artificial Intelligence and Statitsics，Florida，2001：261-265.