基于高斯混合聚類采樣的不平衡數(shù)據(jù)處理方法

嚴(yán) 濤 江開忠 姜新盈 王舒梵

(上海工程技術(shù)大學(xué)數(shù)理統(tǒng)計(jì)學(xué)院 上海 201620)

0 引 言

在過去的幾十年里,非平衡數(shù)據(jù)集的分類吸引了大量的研究興趣[1]。在現(xiàn)實(shí)中很多地方都有不平衡數(shù)據(jù)的身影,例如垃圾郵件過濾[2]、癌癥的診斷、信用風(fēng)險(xiǎn)評(píng)估[3]和網(wǎng)絡(luò)入侵?jǐn)?shù)據(jù)[4]等,此類問題的特征都是一類數(shù)據(jù)量遠(yuǎn)大于另一類。在處理非平衡數(shù)據(jù)時(shí),我們更愿意看到是把數(shù)據(jù)樣本少的那一類進(jìn)行正確分類,這是因?yàn)榘褍深悢?shù)據(jù)分錯(cuò)的代價(jià)是不同的。傳統(tǒng)的分類算法是基于數(shù)據(jù)分布的多樣化、從不同類取樣的樣本數(shù)大致平衡的情形設(shè)計(jì)的,因此在面對(duì)非平衡數(shù)據(jù)時(shí),傳統(tǒng)算法就會(huì)出現(xiàn)分類結(jié)果向多數(shù)類樣本進(jìn)行偏移的現(xiàn)象[5]。如何對(duì)傳統(tǒng)算法進(jìn)行改進(jìn),使不平衡數(shù)據(jù)分類結(jié)果更加精確,已成為數(shù)據(jù)挖掘領(lǐng)域的一大研究重點(diǎn)[6]。

當(dāng)今,解決不平衡數(shù)據(jù)主要有兩個(gè)著手點(diǎn),一是算法層面,二是數(shù)據(jù)層面。從算法層面上來看,有代價(jià)敏感學(xué)習(xí)[7]、集成學(xué)習(xí)[8]、單類學(xué)習(xí)和模糊支持向量機(jī)[9]等。此類算法是通過引進(jìn)懲罰因子或是某種錯(cuò)分代價(jià)來平衡非平衡數(shù)據(jù)所帶來的影響,雖然規(guī)避了剔除樣本所帶來的誤差,但是算法層面的改進(jìn)都是基于某一類具體的算法,這就使得該算法的泛化性不強(qiáng)[10]。從數(shù)據(jù)處理的層面上來看,可分為過采樣和欠采樣兩種方法。過采樣是通過對(duì)少數(shù)樣本進(jìn)行增加而達(dá)到數(shù)據(jù)平衡的一種算法。文獻(xiàn)[11]所提出的SMOTE算法就是主流的過采樣算法,它是通過對(duì)少數(shù)樣本進(jìn)行隨機(jī)的線性插值,依此來創(chuàng)造新樣本,但參與合成的樣本是隨機(jī)選擇的,這就導(dǎo)致合成的新樣本質(zhì)量不高。對(duì)此Han等[12]提出了改進(jìn)的Borderline-SMOTE算法,該算法認(rèn)為影響分類結(jié)果的是來自邊界的樣本,用邊界上的點(diǎn)來創(chuàng)造新樣本,適當(dāng)?shù)鼐徑饬巳哂鄻颖镜漠a(chǎn)生。面對(duì)SMOTE算法的線性插值問題,董燕杰[13]用Random-SMOTE算法把插值放入三角形內(nèi),緩解了少數(shù)類樣本分布稀疏的問題。文獻(xiàn)[14]所提出的SVMOM算法通過少數(shù)類樣本的密度和距離權(quán)重來選擇樣本,進(jìn)而緩解噪聲樣本帶來的影響。但是這些算法都是對(duì)少數(shù)類樣本進(jìn)行處理,精確度不高。欠采樣是一種通過對(duì)多數(shù)類樣本隨機(jī)篩選丟棄的算法,但是帶來的后果就是一些含有重要信息的樣本可能遺失。為此,文獻(xiàn)[15]先對(duì)多數(shù)類樣本進(jìn)行譜聚類,通過距離和類的大小來找到有效的信息,并最終達(dá)到樣本之間的平衡,該方法也解決了數(shù)據(jù)選擇的盲目性。文獻(xiàn)[16]提出了先對(duì)多數(shù)類樣本進(jìn)行高斯混合聚類,然后再把類中冗余的樣本剔除,以保證樣本空間結(jié)構(gòu)的完整。上述的各種算法雖然在處理不平衡數(shù)據(jù)有一定的優(yōu)勢(shì),但是對(duì)于數(shù)據(jù)的處理都是單方面進(jìn)行,這就導(dǎo)致少數(shù)、多數(shù)樣本的處理區(qū)分度不高。

針對(duì)合成無效樣本、剔除重要信息的問題[17],本文提出了一種基于高斯混合聚類采樣的不平衡數(shù)據(jù)處理方法(Mixed Sampling Based on Gaussian Mixture Model in Unbalanced Data, MSGMM)。該算法首先是對(duì)多數(shù)類和少數(shù)類樣本分別進(jìn)行高斯混合聚類,多數(shù)類樣本是通過聚類中心到SVM產(chǎn)生的超平面距離以及其各個(gè)聚類簇之間的樣本數(shù)量賦予各簇一定的采樣比例。這樣是為了保證樣本空間結(jié)構(gòu)基本不變,提高刪除冗余樣本的精度。對(duì)于少數(shù)類樣本則通過聚類中心到超平面的距離來確定采樣數(shù),以其聚類后各簇被選取的樣本為基礎(chǔ),通過Random-SMOTE過采樣算法來產(chǎn)生新的少數(shù)樣本,目的是改善過擬合、增進(jìn)新樣本和原少數(shù)類樣本各簇之間的聯(lián)系,提高樣本的質(zhì)量。實(shí)驗(yàn)結(jié)果表明,本文所提出的MSGMM算法相較于其他算法分類效果更優(yōu)。

1 相關(guān)理論

1.1 高斯混合模型

高斯混合模型(GMM)是由多個(gè)高斯分布函數(shù)線性組合而來的,從理論上來看高斯混合模型可以擬合出各種不同類型的分布,所以本文選用其來進(jìn)行聚類,以產(chǎn)生更加符合原來樣本分布的新樣本。

(1) 單一高斯分布:

(1)

(2) 混合高斯分布:

(2)

對(duì)于GMM的參數(shù)一般是用期望最大化EM來估計(jì)。

通常,聚類個(gè)數(shù)K可以通過優(yōu)化如下問題來求解:

(3)

式中:F1-value、Gmean為評(píng)價(jià)指標(biāo)。

(4)

1.2 Random-SMOTE算法

Random-SMOTE算法是在三個(gè)樣本內(nèi)產(chǎn)生新樣本,算法流程如下。

(1) 隨機(jī)選擇一個(gè)初始樣本以及和周圍的兩個(gè)樣本a、b組成一個(gè)三角形。

(2) 在樣本a、b上進(jìn)行隨機(jī)線性插值產(chǎn)生臨時(shí)樣本y。

(3) 在初始樣本x和臨時(shí)樣本y之間通過式(5)產(chǎn)生新的少數(shù)類樣本Xnew。

Xnew=x+rand(1,0)×(y-x)

(5)

2 方法設(shè)計(jì)

MSGMM算法通過優(yōu)化類間距離盡可能遠(yuǎn)且類內(nèi)距離盡可能近的問題初步確定聚類個(gè)數(shù)。迭代開始,首先用初步確定的聚類數(shù)對(duì)測(cè)試集上的少數(shù)類和多數(shù)類樣本分別進(jìn)行高斯混合聚類,接下來對(duì)聚類后的兩類樣本分別進(jìn)行采樣處理,以獲得多數(shù)類和少數(shù)類樣本數(shù)量相等的平衡數(shù)據(jù)集,通過該數(shù)據(jù)集來計(jì)算F1-value和Gmean的和。之后通過迭代,不斷調(diào)整聚類個(gè)數(shù)來獲得兩值之和,直到所選的聚類個(gè)數(shù)全部運(yùn)行完成,迭代結(jié)束。最后選擇和值最大的那輪訓(xùn)練集作為最終平衡數(shù)據(jù)。該算法可以使得新生成的樣本和原樣本有更高的關(guān)聯(lián)度,剔除樣本所包含的重要信息更少,提高分類器的分類性能。

2.1 MSGMM算法描述

圖1 MSGMM算法流程

2.2 MSGMM算法流程

輸入:不平衡數(shù)據(jù)集C。

輸出:平衡后的數(shù)據(jù)集。

Step1通過SVM對(duì)訓(xùn)練集上的數(shù)據(jù)進(jìn)行訓(xùn)練,生成超平面Σ。

Step2通過優(yōu)化類間距離遠(yuǎn)類內(nèi)距離近的問題初步確定多數(shù)樣本C(0)的聚類簇?cái)?shù)K(0)和少數(shù)樣本C(1)的聚類簇?cái)?shù)K(1)。

Step9將Train_data_most和Train_data_min合并為處理后的新訓(xùn)練集Train_data。放入SVM進(jìn)行訓(xùn)練。

Step10計(jì)算V=F1-value+Gmean。

Step11通過在初步確定的K(0)、K(1)附近取值來重復(fù)Step3到Step10。

Step12選擇V最大的那輪的樣本作為最終的訓(xùn)練集。

2.3 多數(shù)類剔除樣本的選擇計(jì)算

(1) 通過SVM對(duì)初始少數(shù)類和多數(shù)類樣本確定超平面Σ:

Σ:β·x+b=0

(6)

(7)

(8)

(9)

(5) 每個(gè)類所確定的刪除數(shù)。

(10)

2.4 少數(shù)類樣本的采樣計(jì)算

(11)

(12)

式中:mid(|Si|)表示樣本數(shù)量通過排序后位于中位的Si。

(13)

3 實(shí) 驗(yàn)

3.1 評(píng)價(jià)指標(biāo)

在面對(duì)非平衡數(shù)據(jù)集問題時(shí),傳統(tǒng)面向平衡數(shù)據(jù)集的評(píng)價(jià)指標(biāo)已經(jīng)不再適用,這是因?yàn)殄e(cuò)分的代價(jià)是不同的。因此為了更合理地對(duì)數(shù)據(jù)集的分類效果進(jìn)行評(píng)價(jià),提出了混淆矩陣,如表1所示,結(jié)合G-mean[17]和F1-value[17]的評(píng)價(jià)方法,F1-value和G-mean在本文的評(píng)價(jià)體系中處于同等重要地位。

表1 混淆矩陣

其中:TP表示實(shí)際為少數(shù)類且預(yù)測(cè)為正確樣本數(shù)量;FN是實(shí)際為少數(shù)類且預(yù)測(cè)錯(cuò)誤的樣本數(shù)量;FP是實(shí)際為多數(shù)類且預(yù)測(cè)錯(cuò)誤的樣本數(shù)量;TN是實(shí)際為多數(shù)類且預(yù)測(cè)正確的樣本數(shù)量。

Re:少數(shù)類樣本被成功分類的精度。

(14)

Rp:多數(shù)類樣本被成功分類的精度。

(15)

Rr:分類器的分類精度。

(16)

G-mean:

(17)

F1-value:

(18)

由于G-means考慮了少數(shù)類樣本和多數(shù)類樣本成功分類的情況,只有當(dāng)兩類樣本成功分類的精度變大,其數(shù)值才會(huì)變大。F1-value綜合考慮了少數(shù)類樣本的召回率和查準(zhǔn)率,可以全面反映少數(shù)樣本的分類精度。本文從Re、Rp、G-mean、F1-value這四個(gè)角度來探究算法的分類效果。

3.2 數(shù)據(jù)集描述

本文從UCI公開數(shù)據(jù)庫[18]中選取了8個(gè)不平衡數(shù)據(jù)集來驗(yàn)證本文所提出算法的有效性。數(shù)據(jù)集信息如表2所示。其中選取的數(shù)據(jù)既有二分類數(shù)據(jù)集又有多分類數(shù)據(jù)集:Abalone數(shù)據(jù)集中“F”類定義為少數(shù)類,其余的合起來作為多數(shù)類;Vehicle數(shù)據(jù)集中的“Van”類定義為少數(shù)類,其余的作為多數(shù)類;Pima數(shù)據(jù)集的“1”類定義為少數(shù)類,“0”類定義為多數(shù)類;Thyroid數(shù)據(jù)集中的第2類和第3類合起來定義為少數(shù)類,第1類定義為多數(shù)類;Wine數(shù)據(jù)集的“1”類定義為少數(shù)類,其他合起來為多數(shù)類;Bupa數(shù)據(jù)集的第1類定義為少數(shù)類,其他的為多數(shù)類;Seed數(shù)據(jù)集的“1”類定義為少數(shù)類,其他的合起來為多數(shù)類;Aggregation數(shù)據(jù)集的“2”類定義為少數(shù)類,其他定義為多數(shù)類。

表2 數(shù)據(jù)集信息

3.3 實(shí)驗(yàn)內(nèi)容

為了驗(yàn)證本文所提出的MSGMM算法的有效性,設(shè)計(jì)將該算法與SMOTE算法、Borderline-SMOTE算法、ADASYN算法、RU-SMOTE、SMOTE+TOMEK算法在Abalone、Vehicle、Pima、Thyroid、Wine、Bupa、Seed和Aggregation 共8個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)打分比較。實(shí)驗(yàn)為了確保每次訓(xùn)練集與測(cè)試集的劃分一致,統(tǒng)一按照70%的訓(xùn)練集、30%的測(cè)試集進(jìn)行操作。本文實(shí)驗(yàn)環(huán)境使用MATLAB 2016b,所使用的其他對(duì)比算法均采用imbalance-learn 所提供的算法實(shí)現(xiàn),本文的k近鄰取值為5。

3.4 聚類個(gè)數(shù)分析

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

通過表3的結(jié)果,選取最優(yōu)的聚類個(gè)數(shù)來進(jìn)行實(shí)驗(yàn),將本文算法和選取的其余五種算法比較。表4是各算法在F1-value指標(biāo)上的打分情況。表5是各算法在G-mean指標(biāo)的打分情況。

表4 六種算法在不平衡數(shù)據(jù)集上F1-value的比較結(jié)果

表5 六種算法在不平衡數(shù)據(jù)集上G-mean的比較結(jié)果

從表4的結(jié)果可以看出,本文所提出的MSGMM算法在除了Vehicle、Bupa這兩個(gè)數(shù)據(jù)集之外的6個(gè)數(shù)據(jù)上的表現(xiàn)均優(yōu)于其他算法。這是由于本文所提的算法通過不斷的迭代篩選出各組數(shù)據(jù)多數(shù)和少數(shù)類最優(yōu)的聚類個(gè)數(shù),少數(shù)類數(shù)據(jù)的增加、多數(shù)類數(shù)據(jù)的剔除都是在類內(nèi)完成的。這就使得剔除的數(shù)據(jù)沒有影響到原來數(shù)據(jù)的空間結(jié)構(gòu),增加的數(shù)據(jù)與原樣本的關(guān)系更大。

從表5的結(jié)果分析數(shù)據(jù)來看,MSGMM算法在Pima數(shù)據(jù)集上的表現(xiàn)不如SMOTE+TOMEK算法。這是由于MSGMM算法通過聚類提高了少數(shù)類樣本的分類精度,降低了對(duì)多數(shù)類的分類精度,以致于提高了F1-value的值而犧牲了G-mean的得分。但是,從整體而言,本文所提出的算法相較于其他算法都是有優(yōu)勢(shì)的,這也驗(yàn)證了對(duì)數(shù)據(jù)進(jìn)行高斯混合模型聚類再處理的思想的有效性。

為了更加清楚地展示MSGMM算法與其他算法在本文所選評(píng)價(jià)指標(biāo)下的比較情況。圖2繪制了6種算法在8個(gè)數(shù)據(jù)集上的打分情況。縱坐標(biāo)代表了不同算法的得分?jǐn)?shù),跨度范圍從0到1,橫坐標(biāo)反映了G-mean、F1-value、Re和Rp四種評(píng)價(jià)指標(biāo)。從圖2的結(jié)果來看,MSGMM算法整體上是優(yōu)于SMOTE、Borderline-SMOTE、RU-SMOTE、SMOTE+TOMEK、ADASYN這五種算法的。MSGMM算法通過合理的聚類就可以有效地改善數(shù)據(jù)分布不均衡的情況,最終提高分類器的分類效果。

(a) (b)

4 結(jié) 語

本文針對(duì)不平衡數(shù)據(jù)分類問題,提出了MSGMM算法。MSGMM算法是通過迭代尋找多數(shù)和少數(shù)樣本的最優(yōu)聚類個(gè)數(shù)。在不斷的迭代過程中,首先計(jì)算每個(gè)聚類中心到SVM算法產(chǎn)生的超平面的距離。對(duì)于多數(shù)類樣本,再計(jì)算每個(gè)聚類中心所在簇的樣本數(shù)量大小,通過簇的距離和數(shù)量共同確定其各自的剔除的樣本數(shù)量。對(duì)于少數(shù)類樣本,將聚類后各簇到超平面的距離劃分為三類,以距離超平面最近的兩類所包含的樣本來采樣并生成新的少數(shù)類樣本。最后把多數(shù)和少數(shù)類樣本數(shù)目相等的平衡數(shù)據(jù)集送入SVM進(jìn)行訓(xùn)練。這樣一方面在剔除數(shù)據(jù)時(shí)保留的樣本的空間結(jié)構(gòu),另一方面也使得新產(chǎn)生的樣本與各自所在簇的關(guān)系更高。實(shí)驗(yàn)結(jié)果表明,MSGMM算法在一定程度上提高了不平衡數(shù)據(jù)的分類效果。但是,本文所提出的算法也存在一些不足,例如對(duì)于聚類個(gè)數(shù)的確定,在確定最優(yōu)的聚類個(gè)數(shù)時(shí)算法的運(yùn)行時(shí)間較長(zhǎng),以及如何把算法向存在多個(gè)少數(shù)類和多個(gè)分類超平面進(jìn)行推廣。優(yōu)化算法、提高算法運(yùn)行效率是今后的研究重點(diǎn)。