基于譜聚類的不平衡數據欠采樣方法研究*

楊曉月

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

在機器學習和數據挖掘領域中，分類問題是其中一個比較重要的研究方向。傳統的分類方法有K近鄰、支持向量機、決策樹、貝葉斯網絡、神經網絡等［1～3］，這些方法為數據挖掘技術提供了豐富的理論和技術基礎。但是在實際生活中，由于數據的真實性問題會導致傳統的分類方法失效，數據樣本的不平衡就是其中一個亟待解決的問題。

不平衡問題普遍存在于很多領域，例如：在醫學檢測［4］領域，檢測診斷病人是否患癌癥，患者屬于少數類，若將患癌癥的患者誤診斷為健康，那么會使患者錯過最佳的治療時間；在互聯網入侵檢測［5］領域，入侵的樣本數遠少于正常訪問的樣本數，若將網絡入侵判別為正常訪問，那么會導致系統受到外界侵害；故障診斷［6］領域，機器故障屬于少數類，若將故障診斷為正常，可能會帶來不必要的損失等。在這些應用中，數據集中某個類別的樣本數可能會遠多于其他類別，其中真正有價值的信息集中在那一小部分數據，僅占全部數據的一小部分。在這種情況下，傳統的分類方法通常會傾向于將測試樣本判別為多類，對少類的識別率很低，這導致得到的分類器在少類上的分類效果很差，對少類的錯分代價是非常大的［7］。

總而言之，傳統分類算法并不適合直接用于對不平衡數據進行分類，研究如何讓分類算法更加關注少類樣本，提升少數類的分類準確率，對于不平衡數據在實際生產生活中的應用具有重要科學意義。

2 基于譜聚類的欠采樣方法

目前處理不平衡問題的方法主要分為兩類，一類是在數據層面上，通過欠采樣（under-sampling）或過采樣（over-sampling）的方法平衡類別分布，欠采樣方法可以提升模型對少類樣本的分類性能，但是這種方法會造成多類樣本數據的信息丟失，而使得模型無法充分利用已有的信息［8］。傳統的過采樣方法可以生成少類樣本的數據，但是只是基于當前少數類蘊含的信息，缺乏數據多樣性，一定程度上會造成過擬合。另一類是在算法層面上，修改已有的分類算法或者提出新的算法。集成學習［9］、代價敏感學習［10］、單類學習［11］等，是處理不平衡數據集的常見算法。其中，集成學習通過集成多個分類器，來避免單個分類器對不平衡數據分類預測造成的偏差。代價敏感學習是在算法迭代過程中，設置少數類被錯分時具有較高的代價損失，通常與集成學習算法組合使用。

隨機欠采樣方法是欠采樣中常用的方法之一，它通過隨機地刪除多類樣本來降低數據集的不平衡程度，但是這種方法可能會丟失有價值的信息。本文針對這一問題，提出一種基于譜聚類［12］的欠采樣方法，先對多類數據進行譜聚類，得到聚類簇，再根據聚類簇按比例進行欠采樣，可以有效去除多數類的冗余數據，根據聚類簇中的樣本數據到少類樣本數據的平均距離來選擇樣本，能夠有選擇地去除部分多數類的邊界數據，但是能夠保留重要邊界信息，不會對數據的總體分布造成影響，這樣便于后續的分類工作。

2.1 譜聚類算法

聚類算法直觀上就是根據樣本數據的相似性，將其劃分成不同的組，使得在相同組內的數據是相似的，不同組之間的數據具有較低的相似性。一些經典的聚類算法，如K-means算法、EM算法（Ex?pectation Maximization Algorithm）等，都只適用于聚類球狀形的數據集，不能推廣到任意的形狀，當數據集不為凸時，算法會陷入局部最優［13］。譜聚類算法在最近幾年開始變得受歡迎起來，主要是因為算法實現比較簡單，可以對任意形狀的樣本空間進行聚類，并且收斂于全局最優解，不易陷入局部最優，聚類效果常優于經典的聚類算法。

譜聚類是從圖論中演化出的一種算法，其思想源于圖論中的譜圖理論，是將聚類問題轉化成一個無向圖的最優劃分問題。標準化譜聚類的算法步驟如下：

輸入：數據集S=(x1，x2，…xn)和聚類簇的數目k；

輸出：聚類簇A1，A2，…，AK。

1）使用式（1）計算n*n的相似度矩陣W，即為Sij組成的相似度矩陣；

2）使用式（2）計算度矩陣D，即為W的每行元素之和，由di組成的n*n對角矩陣；

3）計算拉普拉斯矩陣Lrsym=D-1/2LD-1/2=D-1/2(D-W)D-1/2；

4）計算Lrsym的特征值，將特征值從小到大排序，取前k個特征值，并計算前k個特征值對應的特征向量μ1，μ2，…，μk；

5）將上面的k個列向量組成矩陣U={μ1，μ2，…，μk}，U∈Rn*k；

6）令yi∈Rk是U的第i行的向量，其中i=1，2，…，n，再將yi∈Rk依次單位化，使得|yi|=1；

7）使 用k-means算 法 將 新 樣 本 點Y={y1，y2，…，yn}聚類成簇A1，A2，…，AK；

8）輸出A1，A2，…，AK。

2.2 支持向量機

支持向量機（Support Vector Machine）［14］是一種經典的分類算法，常用于二分類問題。支持向量機可以分為線性和非線性兩大類。其主要思想是在空間中找到一個能夠將所有數據劃分開的超平面，并且讓數據集中所有樣本到這個超平面的距離最短，離超平面較近的樣本之間能有更大的間距，也就是尋求可以更好隔離兩個類別的超平面。當訓練樣本線性可分時，使用硬間隔最大化（hard mar?gin maximization）訓練得到線性分類器；當訓練樣本近似線性可分時，使用軟間隔最大化（soft mar?gin maximization）訓練得到線性分類器；當訓練樣本不可分時，使用核技巧（kernel trick）和軟間隔最大化訓練非線性的分類器。

以二分類為例，設給定訓練樣本集{(x1，y1)，…，(xn，yn)}，i=1，2，…，n，其中xi表示樣本的數據特征，yi∈{+1，-1}表示樣本的類別標簽。選取適當的核函數K和懲罰參數C。

1）構造最優化問題：

其中，ξi為松弛變量，表示允許樣本可以錯分的程度，C為懲罰項，即對錯分樣本的懲罰程度，拉格朗日函數為：

其中，αi和τi是拉格朗日算子，0≤αi≤C(i=1，2，代入化簡后得到目標函數：

2）選擇α*，滿足0≤αi≤C(i=1，2，…，n)，計算：

3）構造決策函數為

2.3 SCUnder算法

SCUnder算法的主要思想是基于譜聚類算法對多類數據進行聚類，得到聚類簇，根據每一個聚類簇中的樣本數目、聚類內兩兩數據之間的平均距離，以及該聚類中的樣本數據到少類樣本數據的平均距離，來確定每個聚類簇中選擇的樣本數和選擇什么樣的多類數據，進而對多數類進行欠采樣，以達到多類數據與少類數據相對平衡的狀態，有效去除多類樣本的冗余數據，降低源數據集的不平衡程度。

記原始數據集為S=S+∪S-，其中S+和S-分別表示少類樣本數據和多類樣本數據，minorN為少類樣本數目，majorN為多類樣本數目，計算樣本之間的距離均為歐式距離。算法的主要步驟如下。

1）設置聚類數目clusterN=(minorN/majorN)*minorN；

2）利用上述譜聚類算法對多類樣本數據進行聚類，生成聚類簇A1，A2，…，AK，k=clusterN；

3）計算第i個聚類簇中的樣本數counti，計算第i個聚類簇中兩兩樣本之間距離的平均值Wdisti，由此計算第i個聚類簇的密集程度：

并將其歸一化：

4）計算第i個聚類簇中的樣本到少類樣本數據的平均距離AI_disti，并將其歸一化：

5）取每個聚類簇的密集程度Densityi和到少類樣本數據的平均距離SI_disti的加權和，作為每個聚類簇的采樣比例ratioi，α是一個加權系數，即

6）計算每個聚類簇的采樣數目SCsizei，即

7）對多類樣本進行欠采樣，先計算聚類簇Ai中每個樣本到少類的平均距離ddistj，j∈Ai，i=1，2，…，k，按從小到大的順序進行排序，選取前SCsizei個樣本數據，組合成采樣后的多類樣本數據集Snew；

8）輸出欠采樣后組合的新訓練集S'=S+∪

Snew。

3 實驗結果與分析

3.1 性能評估指標

在類別不平衡數據分類問題中，需要采用適用于不平數據分類器的評估指標。通常采用基于混淆矩陣的評價方法，Precision（準確率/查準率）、Re?call（召回率/查全率）、F-measure以及G-mean，用以評估分類器性能。對于二分類問題，將少類樣本數據記為正類（Positive），多類樣本數據記為負類（Negative）。表示分類結果的混淆矩陣如表1所示。

表1 混淆矩陣

其中，TP、FN分別表示正類數據被正確分類的數目、正類數據被錯分為負類的數目，FP、TN分別表示負類數據被錯分為正類的數目、負類樣本被正確分類的數目。根據混淆矩陣，有以下幾種性能評估指標。

查準率表示被正確分類的正類數目占被分為正類的全部數目的比例。

查全率表示被正確分類的正類數目占實際全部正類數目的比例。

F-measure表示查準率和查全率的組合均值，β是表示兩者相對重要性的參數，通常取β=1。

AUC（area under the ROC curve）也是一個有效的不平衡數據分類性能評價指標，即ROC［15］（re?ceiver operating characteristic curve）曲線下方的面積。

為了能更好地評價算法性能，本文采用F-measure和AUC兩個評估指標對分類結果進行評價。

3.2 實驗數據集

本文從KEEL不平衡數據庫［16］中選取了9組基準數據集對算法進行驗證，數據集的基本信息由表2所示。

表2 實驗數據集的基本信息

3.3 實驗結果與分析

為了驗證本文提出的基于譜聚類的欠采樣方法的有效性，也為了方便與其他采樣方法進行對比實驗，實驗選擇SVM作為分類器。與本文提出的SCUnder算法進行對比的方法有基于隨機欠采樣的支持向量機（簡稱RU_SVM）、基于代價敏感的支持向量機（簡稱WS_SVM）、基于單邊選擇欠采樣的支持向量機（簡稱OSS_SVM）、基于Smote過采樣的支持向量機（簡稱Smote_SVM）。本文的實驗采用5折交叉驗證的方式，重復進行10次實驗，計算10次實驗評價指標的平均值，作為最終的實驗結果。

其中，分類器SVM統一采用高斯核函數，懲罰因子C設置為50，核函數寬度σ的值設置為5。實驗采用python中scikit-learn庫中的支持向量機SVC分類算法。本文提出的基于譜聚類的算法實驗采用scikit-learn庫中的譜聚類SpectralClustering算法，相似度矩陣使用高斯核函數，核函數參數gamma經過交叉驗證進行調參，選擇最合適的值。SCUnder算法中的加權系數α同樣采用交叉驗證的方式選擇最優解。

下面是上述方法對比的實驗結果，表3和表4分別列出了不同算法在各數據集上F-measure和AUC的值，其中性能最好的結果用加粗的方式表示，并以圖1和圖2的形式進行直觀展示。

圖1 欠采樣方法F-measure值對比圖

圖2 欠采樣方法AUC值對比圖

表3 SCUnder算法和其他方法的F-measure性能對比

表4 SCUnder算法和其他方法的AUC性能對比

從表3可以看出，基于譜聚類的欠采樣方法在大部分數據集上的分類效果要優于其他方法，SCUnder算法在6組數據集上F-measure值最大，尤其是在glass2、haberman和yeast1數據集上，F-mea?sure值明顯優于其他方法。相比較于RU_SVM和WS_SVM這兩種方法，SCUnder_SVM的F-measure值在所有實驗的數據集上的表現均高于這兩種方法，這是因為基于譜聚類的欠采樣方法通過聚類后按比例進行采樣，可以有效去除多數類的冗余數據，而且能夠有選擇地去除部分不重要的多數類邊界數據。從表4可以看出，SCUnder算法在3組數據集上AUC的值最大，在其他數據集上的AUC值雖然不是最高的，但與每組的最優結果相差不大，能夠保持平均水平。對于不平衡比例較大的數據集，如glass2數據集，SCUnder算法的表現都優于其他算法，從某種程度上可以看出，本文提出的基于譜聚類的欠采樣方法可以適用于各種不平衡度的數據集。總體而言，SCUnder算法能夠有效提高少類樣本的分類性能。

4 結語

欠采樣方法是不平衡數據分類問題中常用的方法之一，從數據層面出發，針對欠采樣方法中存在的多類樣本數據信息丟失的問題，本文提出一種基于譜聚類的欠采樣方法，先對多類樣本數據進行譜聚類，得到聚類簇，通過聚類簇確定多類樣本的空間分布，根據每個聚類簇的密集程度以及到少類樣本的平均距離，來確定采樣數目以及選取什么樣的多類樣本，這樣按比例進行的欠采樣可以有效去除多數類的冗余數據，并去除部分不重要的邊界數據，但是能夠保留重要邊界信息。通過在9組不同數據集上的對比實驗，可以看出基于譜聚類的欠采樣方法在一定程度上能夠提高少類樣本的分類性能，能有效處理不平衡數據的分類問題。