駱自超，金 隼，邱雪峰

LUO Zichao,JIN Sun,QIU Xuefeng

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

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

1 引言

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

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

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

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

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

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

2 不平衡數(shù)據(jù)集處理方法

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

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

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

2.1 欠抽樣方法

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

2.2 過抽樣方法

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

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

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

圖1 算法流程圖

3.1 改進的譜聚類算法

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

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

（1）將初始聚類數(shù)k設為10。

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

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

（3）根據(jù)下式計算矩陣D：

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

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

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

3.2 優(yōu)化的SMOTE算法

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

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

其中，n為少數(shù)類樣本總數(shù)。

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

其中Ci為每個類所包含樣本個數(shù)。

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

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

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

4 實驗設定

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

4.1 數(shù)據(jù)集

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

表1 數(shù)據(jù)集描述

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

4.2 評價指標

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

圖2 合成數(shù)據(jù)集的數(shù)據(jù)結構

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

其中，Tp，F(xiàn)p，Tn，F(xiàn)n分別表示被分類器正確分類的少數(shù)類樣本個數(shù)，被錯誤分類的少數(shù)類樣本個數(shù)，被正確分類的多數(shù)類樣本個數(shù)，被錯誤分類的多數(shù)類樣本個數(shù)。

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

5 實驗結果與分析

5.1 實際數(shù)據(jù)驗證結果

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

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

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

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

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

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

5.2 合成數(shù)據(jù)測試結果

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

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

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

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

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

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

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

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

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

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

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

6 結論

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

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

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

[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]陳思，郭躬德，陳黎飛.基于聚類融合的不平衡數(shù)據(jù)分類方法[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]陳川，張化祥.基于聚類的少數(shù)類樣本采樣方法[J].信息技術與信息化，2011（5）：65-68.

[9]楊永，王莉利.基于K-means聚類和遺傳算法的少數(shù)類樣本采樣方法研究[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，F(xiàn)lorida，2001：261-265.