面向不平衡數(shù)據(jù)集融合Canopy和K-means的SMOTE改進(jìn)算法

郭朝有，許 喆，馬硯堃，曹蒙蒙

(海軍工程大學(xué)動(dòng)力工程學(xué)院,武漢 430033)

在類別數(shù)量上分布不均衡的數(shù)據(jù)集稱為不平衡數(shù)據(jù)集[1],一般將類別數(shù)量多的數(shù)據(jù)樣本稱為多數(shù)類,類別數(shù)量少的數(shù)據(jù)樣本稱為少數(shù)類。不平衡數(shù)據(jù)集在信用卡詐騙、醫(yī)療診斷、網(wǎng)絡(luò)入侵、故障診斷、網(wǎng)絡(luò)事件發(fā)現(xiàn)等領(lǐng)域均廣泛存在[2-4],如何利用現(xiàn)有分類算法對(duì)不平衡數(shù)據(jù)進(jìn)行有效分類是數(shù)據(jù)挖掘領(lǐng)域面臨的挑戰(zhàn)之一[5]。目前,主要從兩個(gè)方面解決不平衡數(shù)據(jù)集的分類問題:一是從數(shù)據(jù)層面出發(fā),利用數(shù)據(jù)平衡化方法使數(shù)據(jù)集達(dá)到平衡,如過采樣或欠采樣技術(shù)[6]等；二是從算法層面出發(fā),通過改進(jìn)現(xiàn)有算法使其能夠針對(duì)性地處理不平衡數(shù)據(jù),如代價(jià)敏感學(xué)習(xí)[7]、集成學(xué)習(xí)[8]和單類學(xué)習(xí)[9]等。

過采樣或欠采樣技術(shù)通過人為地增加或減少原始不平衡數(shù)據(jù)集中的少數(shù)類或多數(shù)類樣本以改變數(shù)據(jù)樣本的不平衡分布,從而使新的數(shù)據(jù)集在類別數(shù)量上達(dá)到平衡。Chawla等[10]提出的(synthetic minority over-sampling technique, SMOTE)算法是最為經(jīng)典的啟發(fā)式過采樣技術(shù),該算法在少數(shù)類樣本和其近鄰樣本之間利用隨機(jī)線性插值的方法合成新的少數(shù)類樣本。但因?qū)ι贁?shù)類樣本進(jìn)行無(wú)差別地選擇,導(dǎo)致其合成樣本質(zhì)量不高。為此,Han等[11]提出了Borderline-SMOTE算法；Yen等12提出了先聚類再抽樣的數(shù)據(jù)平衡化方法；曹正鳳[13]提出了C_SMOTE算法；陳斌等[14]提出了KM-SMOTE算法,該方法先利用K-means算法聚類,然后再運(yùn)用SMOTE算法進(jìn)行過采樣；劉丹等[15]提出了一種最近三角區(qū)域的NNTR-SMOTE算法,使生成的樣本不突破原始類別邊界地更接近少數(shù)類。雖然上述改進(jìn)方法在一定程度上改善了數(shù)據(jù)集的不平衡分布,但也存在著一些不足,如數(shù)據(jù)樣本分布模式改變、數(shù)據(jù)樣本重疊導(dǎo)致合成樣本有效性不足等。

綜合上述SMOTE改進(jìn)算法,本文融合Canopy和K-means算法優(yōu)點(diǎn),對(duì)SMOTE平衡化方法進(jìn)行改進(jìn),并將其定義為C-K-SMOTE算法,然后利用隨機(jī)森林算法開展了分類實(shí)驗(yàn)。

1 相關(guān)算法

1.1 Canopy算法

Canopy算法[16]基于歐式距離測(cè)度等快速距離測(cè)度和距離閾值T1、T2(T1>T2),將數(shù)據(jù)劃分成一些重疊的簇(canopy簇)以實(shí)現(xiàn)近似聚類,是一種快速近似聚類技術(shù),能夠?qū)崿F(xiàn)海量高維數(shù)據(jù)的聚類分析。

Canopy算法基本流程如下：

(1)根據(jù)數(shù)據(jù)集的特征或通過多次交叉實(shí)驗(yàn)優(yōu)選確定距離閾值T1和T2。

(2)數(shù)據(jù)集中任取一點(diǎn)A,若無(wú)canopy簇存在,則把A點(diǎn)當(dāng)作第一個(gè)canopy簇,否則計(jì)算A點(diǎn)與各個(gè)canopy簇簇心間距離D={D1,D2,…,Dk}(k為canopy聚類簇簇?cái)?shù))。

(3)比較D與T1和T2,若D≤T1,則點(diǎn)A歸入相應(yīng)的canopy簇,并根據(jù)canopy簇中各點(diǎn)幾何平均值重新調(diào)整canopy簇的簇心；若D≤T2,則將點(diǎn)A從數(shù)據(jù)集中剔除；若D>T1,則將生成一新的canopy簇,并以點(diǎn)A作為該canopy簇的簇心。

(4)重復(fù)執(zhí)行步驟(2)和(3),直至數(shù)據(jù)集為空,算法結(jié)束。

該算法原理簡(jiǎn)單、易于實(shí)現(xiàn),由于采用了簡(jiǎn)單快速的距離測(cè)度,使得其計(jì)算耗時(shí)少,數(shù)據(jù)劃分效率高,可迅速地對(duì)大量數(shù)據(jù)進(jìn)行粗略聚類。此外,該算法無(wú)需事先設(shè)定聚類簇?cái)?shù),避免了隨機(jī)確定聚類簇?cái)?shù)的盲目性。但也正是由于其距離測(cè)度的簡(jiǎn)單化也導(dǎo)致其聚類輸出的聚類精度不高。

1.2 K-means算法

K-means算法[17]核心思想:基于Euclidean Distance Measure等距離測(cè)度,結(jié)合預(yù)設(shè)聚類簇?cái)?shù)k和初始聚類中心,通過不斷迭代運(yùn)算,實(shí)現(xiàn)數(shù)據(jù)集的劃分聚類。基本流程如下。

(1)數(shù)據(jù)集中隨機(jī)選擇k個(gè)點(diǎn)作為初始聚類中心(k為聚類簇簇?cái)?shù))。

(2)計(jì)算剩余數(shù)據(jù)到k個(gè)聚類中心的距離,將它們劃分至距離最近的簇中。

(3)計(jì)算每個(gè)聚類簇中所有數(shù)據(jù)樣本的平均值,將其作為新的聚類中心,并計(jì)算目標(biāo)函數(shù)E。

(4)重復(fù)步驟(2)和(3),直至聚類中心不再變化或E達(dá)到收斂條件,算法結(jié)束。

目標(biāo)函數(shù)E如式(1)所示,E越小,聚類效果越好。

(1)

式(1)中：xi表示數(shù)據(jù)集中第i個(gè)數(shù)據(jù)樣本；ωj表示第j個(gè)聚類簇；zj表示第j個(gè)聚類簇的簇心。

該算法原理簡(jiǎn)單、易于操作且能夠快速收斂,能夠高效地處理大規(guī)模數(shù)據(jù)。但也存在一定的不足,如聚類簇?cái)?shù)k選取盲目和初始聚類中心敏感等。

1.3 SMOTE算法

SMOTE算法基于在相距較近的少數(shù)類樣本之間仍然存在少數(shù)類樣本的假設(shè),采用隨機(jī)線性插值的方法在少數(shù)類樣本之間合成新的樣本,進(jìn)而使不平衡數(shù)據(jù)集趨向平衡。基本流程如下：

(1)獲取不平衡數(shù)據(jù)集中的少數(shù)類樣本{X1,X2,…,Xn}。

(2)基于歐氏距離求取每個(gè)少數(shù)類樣本的m個(gè)最近鄰樣本{Yi1,Yi2,…,Yim}。

(3)在少數(shù)類樣本與其m個(gè)最近鄰樣本之間進(jìn)行隨機(jī)線性插值處理,這樣每個(gè)少數(shù)類樣本Xi經(jīng)過插值都可以得到m個(gè)合成樣本Pj(j=1,2,…,m)；

(4)將插值得到的少數(shù)類樣本放入不平衡數(shù)據(jù)集中,得到新的數(shù)據(jù)集并計(jì)算不平衡度。

(5)若不平衡度已達(dá)到要求,則程序結(jié)束,否則轉(zhuǎn)步驟(1)。

其中,隨機(jī)線性插值公式為

Pj=Xi+rand(0,1)(Yij-Xi)

(2)

式(2)中,Xi為少數(shù)類樣本；Yij為與Xi相鄰的m個(gè)最近鄰樣本；rand(0,1)為(0,1)區(qū)間的隨機(jī)數(shù)。

2 C-K-SMOTE改進(jìn)算法

2.1 SMOTE算法問題

深入分析SMOTE算法,并結(jié)合相關(guān)文獻(xiàn),總結(jié)其存在的自身難以克服的問題[18]如下：

2.1.1 近鄰樣本選擇盲目性問題

SMOTE算法合成的新樣本與每個(gè)少數(shù)類樣本的m個(gè)最近鄰值密切相關(guān),因此,近鄰值的選取關(guān)乎著合成樣本的數(shù)據(jù)質(zhì)量,但m的選擇具有一定的盲目性。

2.1.2 樣本分布模式失真問題

數(shù)據(jù)集均存在一定的原始分布模式,而SMOTE算法在合成少數(shù)類樣本時(shí),未考慮數(shù)據(jù)集的原始分布,極易導(dǎo)致新生成的數(shù)據(jù)會(huì)影響原來(lái)的分布模式。

2.1.3 樣本邊界模糊化問題

當(dāng)對(duì)處于多數(shù)類和少數(shù)類邊界處的少數(shù)類樣本進(jìn)行過采樣時(shí),新生成的數(shù)據(jù)也會(huì)位于樣本邊界附近,從而使得少數(shù)類樣本越來(lái)越邊緣化,進(jìn)而造成多數(shù)類與少數(shù)類的邊界越來(lái)越模糊。

2.1.4 插值樣本失效問題

SMOTE算法合成新樣本時(shí),不能很好地處理少數(shù)類樣本存在噪聲數(shù)據(jù)的情況,往往會(huì)導(dǎo)致合成樣本有效性不足。

2.2 C-K-SMOTE算法

針對(duì)SMOTE算法存在的上述不足,借鑒曹正風(fēng)提出的C_SMOTE算法和陳斌提出的KM-SMOTE算法,融合Canopy和K-means聚類算法,形成了一全新的SMOTE改進(jìn)算法——C-K-SMOTE。C-K-SMOTE核心為:利用Canopy算法對(duì)少數(shù)類樣本進(jìn)行快速近似聚類,得到一系列canopy簇；然后再利用K-means聚類算法對(duì)canopy簇再聚類,得到精準(zhǔn)聚類簇,最后再利用SMOTE算法基于精準(zhǔn)聚類簇進(jìn)行插值處理,從而增加少數(shù)類樣本數(shù)量使數(shù)據(jù)樣本趨向平衡。

2.3 C-K-SMOTE算法核心步驟

(1)少數(shù)類樣本的粗、細(xì)聚類,得到精準(zhǔn)簇。運(yùn)用Canopy算法進(jìn)行粗聚類,生成以A、B和C為簇心的三個(gè)canopy簇；運(yùn)用K-means算法對(duì)canopy簇進(jìn)行再聚類,得到三個(gè)精準(zhǔn)簇,經(jīng)過不斷的劃分和初始中心優(yōu)化調(diào)整之后,三個(gè)精準(zhǔn)簇的中心分別為C1、C2和C3,聚類過程示意圖如圖1所示。

圖1 基于Canopy算法和K-means算法對(duì)少數(shù)類樣本聚類Fig.1 Clustering of minority samples based on Canopy and K-means algorithm

(2)基于精準(zhǔn)簇隨機(jī)插值合成新數(shù)據(jù)集。基于步驟(1)得到的精準(zhǔn)簇,運(yùn)用SMOTE過采樣算法,采用修正的隨機(jī)插值公式即可合成新樣本,如圖2所示。

圖2 基于CKSMOTE算法合成新樣本Fig.2 Synthesis new samples based on CKSMOTE algorithm

其中修正的隨機(jī)插值公式為

Pi=Xi+rand(0,1)(ut-Xi)

(3)

式(3)中：Xi(i=1,2,…,n)為少數(shù)類樣本,n表示少數(shù)類樣本總數(shù)；ut(t=1,2,…,k)為精準(zhǔn)聚類簇簇心,k表示聚類簇?cái)?shù)；Pj(j=1,2,…,m)為合成的新數(shù)據(jù),m表示新合成數(shù)據(jù)的總數(shù)。rand(0,1)表示(0,1)區(qū)間的隨機(jī)數(shù)。

3 算例驗(yàn)證

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

算例數(shù)據(jù)集來(lái)自于公開數(shù)據(jù)集KEEL(knowledge extraction on evolutionary learning)數(shù)據(jù)庫(kù)[19]中的不平衡數(shù)據(jù)集,共選取了Yeast、Ecoli和Page-blocks三組不同不平衡度的數(shù)據(jù)集(如表1所示)，并采用10倍5折交叉驗(yàn)證方法將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集。

表1 測(cè)試數(shù)據(jù)集Table 1 Testing data sets

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

由于不平衡數(shù)據(jù)本身的特殊性,僅憑某單一性能指標(biāo)無(wú)法綜合評(píng)價(jià)基于不平衡數(shù)據(jù)的分類性能,為此,優(yōu)選G-means和TP/FP(ture positive/false positive)散點(diǎn)圖作為不平衡數(shù)據(jù)集分類效果的綜合評(píng)價(jià)指標(biāo)。

基于表2的混淆矩陣,可定義真正率(TPrate)、假正率(FPrate)等其他常見的性能評(píng)價(jià)指標(biāo),如表3所示。

表2 混淆矩陣Table 2 Confusion matrix for binary classification

表3 其他的性能評(píng)價(jià)指標(biāo)Table 3 Extra performance evaluation indicators

G-means是真正率和真負(fù)率乘積的平方根,如式(4)所示:

(4)

G-means綜合了真正率、真負(fù)率,較好地反映了面向不平衡數(shù)據(jù)集的整體分類能力。

TP/FP散點(diǎn)圖是反映分類器正確分類率和錯(cuò)誤分類率之間關(guān)系的可視化表示方法,是以假正率(FPrate)為橫軸,真正率(TPrate)為縱軸的二維曲線圖,如圖3所示。

圖3 TP/FP散點(diǎn)圖Fig.3 TP/FP scatter plot

圖3中每個(gè)點(diǎn)(FPrate,TPrate)對(duì)應(yīng)一個(gè)分類器模型。當(dāng)FPrate越小且TPrate越大時(shí),分類模型的分類效果越好；在TP/FP散點(diǎn)圖上表現(xiàn)為越靠近左上方,分類性能越優(yōu)。

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

為對(duì)比測(cè)試SMOTE算法和CKSMOTE算法的數(shù)據(jù)平衡化性能,設(shè)計(jì)了如下三組實(shí)驗(yàn)方案。其中隨機(jī)森林的決策樹數(shù)目設(shè)定為100,SMOTE算法的最近鄰值設(shè)定為3[20]。

方案一運(yùn)用RF算法對(duì)原始不平衡數(shù)據(jù)進(jìn)行分類

方案二運(yùn)用RF算法對(duì)利用傳統(tǒng)SMOTE算法平衡化后的數(shù)據(jù)集進(jìn)行分類

方案三運(yùn)用RF算法對(duì)利用C-K-SMOTE算法平衡化后的數(shù)據(jù)集進(jìn)行分類

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

按上述實(shí)驗(yàn)方案對(duì)表1所列8個(gè)不平衡數(shù)據(jù)集進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)G-means如表4所示。表4所列為實(shí)驗(yàn)G-means指標(biāo)值,轉(zhuǎn)換為柱狀圖為圖4所示。

表4 實(shí)驗(yàn)G-means指標(biāo)值Table 4 G-means indicator of the experiment

圖4 實(shí)驗(yàn)G-means指標(biāo)柱狀圖Fig.4 The histogram of G-means indicator

由表5、圖4分析可得以下結(jié)果。

(1)CKSMOTE+RF模型在8個(gè)數(shù)據(jù)集上的G-means值均高于SMOTE+RF模型,平均提高了8%左右,這表明CKSMOTE算法相比傳統(tǒng)的SMOTE算法在處理不平衡數(shù)據(jù)時(shí)的平衡效果更好,在提升隨機(jī)森林算法分類效果上更為顯著。

(2)數(shù)據(jù)集的不平衡度越高,C-K-SMOTE算法的數(shù)據(jù)平衡化性能更好。以Yeast數(shù)據(jù)集為例,相比于SMOTE算法,Yeast1、Yeast3和Yeast4數(shù)據(jù)集C-K-SMOTE算法的G-means分別提高了5.66%、5.78%和26.47%。

TP/FP散點(diǎn)圖如圖5所示。

圖5 TP/FP散點(diǎn)圖Fig.5 TP/FP scatter plot

由圖5分析可得以下結(jié)果。

(1)C-K-SMOTE+RF模型在8個(gè)數(shù)據(jù)集下的TPrate均比SMOTE+RF算法有提升,平均提高了約4.48%,同時(shí)FPrate均有所降低,平均降低了約22.02%。即相比SMOTE+RF模型,C-K-SMOTE+RF模型平衡化不平衡數(shù)據(jù)性能更優(yōu),隨機(jī)森林分類效果提升程度更高。

(2)數(shù)據(jù)集的不平衡度越高,C-K-SMOTE+RF模型的平衡化效果越顯著。以Page-blocks數(shù)據(jù)集為例,由TP/FP散點(diǎn)圖可以看出,經(jīng)CKSMOTE改進(jìn)算法平衡化處理后,數(shù)據(jù)集Page-blocks0和Page-blocks1Ecoli4的坐標(biāo)位置相比于SMOTE+RF算法更趨近于左上角(0,1)的位置,這直觀地表明了CKSMOTE改進(jìn)算法能夠更好地平衡不平衡數(shù)據(jù)集,同時(shí)也能改善隨機(jī)森林的分類效果。

綜合上述G-means值和TP/FP散點(diǎn)圖的分析,設(shè)計(jì)的C-K-SMOTE算法在平衡化處理不平衡數(shù)據(jù)集時(shí)效果更優(yōu),CKSMOTE+RF分類模型對(duì)少數(shù)類樣本識(shí)別準(zhǔn)確率更高,特別是對(duì)于不平衡度較大的數(shù)據(jù)集,其效果更加顯著。

4 結(jié)論

針對(duì)SMOTE算法存在的問題,結(jié)合Canopy和K-means算法,設(shè)計(jì)一種新的C-K-SMOTE改進(jìn)算法:采用“先聚類后插值”的方法,既保證了新生成的樣本的有效性也保留了原數(shù)據(jù)分布模式且不存在邊界模糊問題；利用修正的SMOTE算法插值公式避免了近鄰樣本選擇盲目性問題；實(shí)現(xiàn)了Canopy算法和K-means算法有機(jī)融合,利用K-means再聚類解決了Canopy算法聚類精度低的問題,同時(shí)利用Canopy聚類克服了K-means算法聚類簇?cái)?shù)難以確定以及初始中心過于隨機(jī)的問題。

基于公開數(shù)據(jù)集的算例,驗(yàn)證了改進(jìn)算法的有效性。但該算法也存在一定的不足,如Canopy算法中兩個(gè)距離閾值T1和T2的選取,采用多次實(shí)驗(yàn)交叉驗(yàn)證方法進(jìn)行設(shè)定,雖然該方法快速有效,但仍具有一定的隨機(jī)性和盲目性,還需要進(jìn)一步的深入研究。