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

(海軍工程大學動力工程學院,武漢 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)有分類算法對不平衡數(shù)據(jù)進行有效分類是數(shù)據(jù)挖掘領(lǐng)域面臨的挑戰(zhàn)之一[5]。目前,主要從兩個方面解決不平衡數(shù)據(jù)集的分類問題:一是從數(shù)據(jù)層面出發(fā),利用數(shù)據(jù)平衡化方法使數(shù)據(jù)集達到平衡,如過采樣或欠采樣技術(shù)[6]等；二是從算法層面出發(fā),通過改進現(xiàn)有算法使其能夠針對性地處理不平衡數(shù)據(jù),如代價敏感學習[7]、集成學習[8]和單類學習[9]等。

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

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

1 相關(guān)算法

1.1 Canopy算法

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

Canopy算法基本流程如下：

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

(2)數(shù)據(jù)集中任取一點A,若無canopy簇存在,則把A點當作第一個canopy簇,否則計算A點與各個canopy簇簇心間距離D={D1,D2,…,Dk}(k為canopy聚類簇簇數(shù))。

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

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

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

1.2 K-means算法

K-means算法[17]核心思想:基于Euclidean Distance Measure等距離測度,結(jié)合預設(shè)聚類簇數(shù)k和初始聚類中心,通過不斷迭代運算,實現(xiàn)數(shù)據(jù)集的劃分聚類?；玖鞒倘缦隆?/p>

(1)數(shù)據(jù)集中隨機選擇k個點作為初始聚類中心(k為聚類簇簇數(shù))。

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

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

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

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

(1)

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

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

1.3 SMOTE算法

SMOTE算法基于在相距較近的少數(shù)類樣本之間仍然存在少數(shù)類樣本的假設(shè),采用隨機線性插值的方法在少數(shù)類樣本之間合成新的樣本,進而使不平衡數(shù)據(jù)集趨向平衡?；玖鞒倘缦拢?/p>

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

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

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

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

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

其中,隨機線性插值公式為

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

(2)

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

2 C-K-SMOTE改進算法

2.1 SMOTE算法問題

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

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

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

2.1.2 樣本分布模式失真問題

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

2.1.3 樣本邊界模糊化問題

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

2.1.4 插值樣本失效問題

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

2.2 C-K-SMOTE算法

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

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

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

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

(2)基于精準簇隨機插值合成新數(shù)據(jù)集?；诓襟E(1)得到的精準簇,運用SMOTE過采樣算法,采用修正的隨機插值公式即可合成新樣本,如圖2所示。

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

其中修正的隨機插值公式為

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

(3)

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

3 算例驗證

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

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

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

3.2 評價指標

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

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

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

表3 其他的性能評價指標Table 3 Extra performance evaluation indicators

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

(4)

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

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

圖3 TP/FP散點圖Fig.3 TP/FP scatter plot

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

3.3 實驗

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

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

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

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

3.4 實驗結(jié)果及分析

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

表4 實驗G-means指標值Table 4 G-means indicator of the experiment

圖4 實驗G-means指標柱狀圖Fig.4 The histogram of G-means indicator

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

(1)CKSMOTE+RF模型在8個數(shù)據(jù)集上的G-means值均高于SMOTE+RF模型,平均提高了8%左右,這表明CKSMOTE算法相比傳統(tǒng)的SMOTE算法在處理不平衡數(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散點圖如圖5所示。

圖5 TP/FP散點圖Fig.5 TP/FP scatter plot

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

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

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

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

4 結(jié)論

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

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