基于譜聚類的不平衡數(shù)據(jù)欠采樣方法研究*

楊曉月

（南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 南京 210094）

1 引言

在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域中，分類問(wèn)題是其中一個(gè)比較重要的研究方向。傳統(tǒng)的分類方法有K近鄰、支持向量機(jī)、決策樹(shù)、貝葉斯網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)等［1～3］，這些方法為數(shù)據(jù)挖掘技術(shù)提供了豐富的理論和技術(shù)基礎(chǔ)。但是在實(shí)際生活中，由于數(shù)據(jù)的真實(shí)性問(wèn)題會(huì)導(dǎo)致傳統(tǒng)的分類方法失效，數(shù)據(jù)樣本的不平衡就是其中一個(gè)亟待解決的問(wèn)題。

不平衡問(wèn)題普遍存在于很多領(lǐng)域，例如：在醫(yī)學(xué)檢測(cè)［4］領(lǐng)域，檢測(cè)診斷病人是否患癌癥，患者屬于少數(shù)類，若將患癌癥的患者誤診斷為健康，那么會(huì)使患者錯(cuò)過(guò)最佳的治療時(shí)間；在互聯(lián)網(wǎng)入侵檢測(cè)［5］領(lǐng)域，入侵的樣本數(shù)遠(yuǎn)少于正常訪問(wèn)的樣本數(shù)，若將網(wǎng)絡(luò)入侵判別為正常訪問(wèn)，那么會(huì)導(dǎo)致系統(tǒng)受到外界侵害；故障診斷［6］領(lǐng)域，機(jī)器故障屬于少數(shù)類，若將故障診斷為正常，可能會(huì)帶來(lái)不必要的損失等。在這些應(yīng)用中，數(shù)據(jù)集中某個(gè)類別的樣本數(shù)可能會(huì)遠(yuǎn)多于其他類別，其中真正有價(jià)值的信息集中在那一小部分?jǐn)?shù)據(jù)，僅占全部數(shù)據(jù)的一小部分。在這種情況下，傳統(tǒng)的分類方法通常會(huì)傾向于將測(cè)試樣本判別為多類，對(duì)少類的識(shí)別率很低，這導(dǎo)致得到的分類器在少類上的分類效果很差，對(duì)少類的錯(cuò)分代價(jià)是非常大的［7］。

總而言之，傳統(tǒng)分類算法并不適合直接用于對(duì)不平衡數(shù)據(jù)進(jìn)行分類，研究如何讓分類算法更加關(guān)注少類樣本，提升少數(shù)類的分類準(zhǔn)確率，對(duì)于不平衡數(shù)據(jù)在實(shí)際生產(chǎn)生活中的應(yīng)用具有重要科學(xué)意義。

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

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

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

2.1 譜聚類算法

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

譜聚類是從圖論中演化出的一種算法，其思想源于圖論中的譜圖理論，是將聚類問(wèn)題轉(zhuǎn)化成一個(gè)無(wú)向圖的最優(yōu)劃分問(wèn)題。標(biāo)準(zhǔn)化譜聚類的算法步驟如下：

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

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

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

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

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

4）計(jì)算Lrsym的特征值，將特征值從小到大排序，取前k個(gè)特征值，并計(jì)算前k個(gè)特征值對(duì)應(yīng)的特征向量μ1，μ2，…，μk；

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

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

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

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

2.2 支持向量機(jī)

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

以二分類為例，設(shè)給定訓(xùn)練樣本集{(x1，y1)，…，(xn，yn)}，i=1，2，…，n，其中xi表示樣本的數(shù)據(jù)特征，yi∈{+1，-1}表示樣本的類別標(biāo)簽。選取適當(dāng)?shù)暮撕瘮?shù)K和懲罰參數(shù)C。

1）構(gòu)造最優(yōu)化問(wèn)題：

其中，ξi為松弛變量，表示允許樣本可以錯(cuò)分的程度，C為懲罰項(xiàng)，即對(duì)錯(cuò)分樣本的懲罰程度，拉格朗日函數(shù)為：

其中，αi和τi是拉格朗日算子，0≤αi≤C(i=1，2，代入化簡(jiǎn)后得到目標(biāo)函數(shù)：

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

3）構(gòu)造決策函數(shù)為

2.3 SCUnder算法

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

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

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

2）利用上述譜聚類算法對(duì)多類樣本數(shù)據(jù)進(jìn)行聚類，生成聚類簇A1，A2，…，AK，k=clusterN；

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

并將其歸一化：

4）計(jì)算第i個(gè)聚類簇中的樣本到少類樣本數(shù)據(jù)的平均距離AI_disti，并將其歸一化：

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

6）計(jì)算每個(gè)聚類簇的采樣數(shù)目SCsizei，即

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

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

Snew。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 性能評(píng)估指標(biāo)

在類別不平衡數(shù)據(jù)分類問(wèn)題中，需要采用適用于不平數(shù)據(jù)分類器的評(píng)估指標(biāo)。通常采用基于混淆矩陣的評(píng)價(jià)方法，Precision（準(zhǔn)確率/查準(zhǔn)率）、Re?call（召回率/查全率）、F-measure以及G-mean，用以評(píng)估分類器性能。對(duì)于二分類問(wèn)題，將少類樣本數(shù)據(jù)記為正類（Positive），多類樣本數(shù)據(jù)記為負(fù)類（Negative）。表示分類結(jié)果的混淆矩陣如表1所示。

表1 混淆矩陣

其中，TP、FN分別表示正類數(shù)據(jù)被正確分類的數(shù)目、正類數(shù)據(jù)被錯(cuò)分為負(fù)類的數(shù)目，F(xiàn)P、TN分別表示負(fù)類數(shù)據(jù)被錯(cuò)分為正類的數(shù)目、負(fù)類樣本被正確分類的數(shù)目。根據(jù)混淆矩陣，有以下幾種性能評(píng)估指標(biāo)。

查準(zhǔn)率表示被正確分類的正類數(shù)目占被分為正類的全部數(shù)目的比例。

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

F-measure表示查準(zhǔn)率和查全率的組合均值，β是表示兩者相對(duì)重要性的參數(shù)，通常取β=1。

AUC（area under the ROC curve）也是一個(gè)有效的不平衡數(shù)據(jù)分類性能評(píng)價(jià)指標(biāo)，即ROC［15］（re?ceiver operating characteristic curve）曲線下方的面積。

為了能更好地評(píng)價(jià)算法性能，本文采用F-measure和AUC兩個(gè)評(píng)估指標(biāo)對(duì)分類結(jié)果進(jìn)行評(píng)價(jià)。

3.2 實(shí)驗(yàn)數(shù)據(jù)集

本文從KEEL不平衡數(shù)據(jù)庫(kù)［16］中選取了9組基準(zhǔn)數(shù)據(jù)集對(duì)算法進(jìn)行驗(yàn)證，數(shù)據(jù)集的基本信息由表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集的基本信息

3.3 實(shí)驗(yàn)結(jié)果與分析

為了驗(yàn)證本文提出的基于譜聚類的欠采樣方法的有效性，也為了方便與其他采樣方法進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)選擇SVM作為分類器。與本文提出的SCUnder算法進(jìn)行對(duì)比的方法有基于隨機(jī)欠采樣的支持向量機(jī)（簡(jiǎn)稱RU_SVM）、基于代價(jià)敏感的支持向量機(jī)（簡(jiǎn)稱WS_SVM）、基于單邊選擇欠采樣的支持向量機(jī)（簡(jiǎn)稱OSS_SVM）、基于Smote過(guò)采樣的支持向量機(jī)（簡(jiǎn)稱Smote_SVM）。本文的實(shí)驗(yàn)采用5折交叉驗(yàn)證的方式，重復(fù)進(jìn)行10次實(shí)驗(yàn)，計(jì)算10次實(shí)驗(yàn)評(píng)價(jià)指標(biāo)的平均值，作為最終的實(shí)驗(yàn)結(jié)果。

其中，分類器SVM統(tǒng)一采用高斯核函數(shù)，懲罰因子C設(shè)置為50，核函數(shù)寬度σ的值設(shè)置為5。實(shí)驗(yàn)采用python中scikit-learn庫(kù)中的支持向量機(jī)SVC分類算法。本文提出的基于譜聚類的算法實(shí)驗(yàn)采用scikit-learn庫(kù)中的譜聚類SpectralClustering算法，相似度矩陣使用高斯核函數(shù)，核函數(shù)參數(shù)gamma經(jīng)過(guò)交叉驗(yàn)證進(jìn)行調(diào)參，選擇最合適的值。SCUnder算法中的加權(quán)系數(shù)α同樣采用交叉驗(yàn)證的方式選擇最優(yōu)解。

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

圖1 欠采樣方法F-measure值對(duì)比圖

圖2 欠采樣方法AUC值對(duì)比圖

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

表4 SCUnder算法和其他方法的AUC性能對(duì)比

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

4 結(jié)語(yǔ)

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