高 陽,劉其成,牟春曉

(煙臺(tái)大學(xué)計(jì)算機(jī)與控制工程學(xué)院,山東 煙臺(tái) 264005)

不平衡數(shù)據(jù)集是指樣本集中各自類別所含樣本數(shù)目的多少存在較大的差距,對(duì)于含有較多樣本數(shù)的類別稱之為多數(shù)類(反例)樣本,反之為少數(shù)類(正例)樣本[1]。在不平衡數(shù)據(jù)集中,樣本數(shù)量較少的類可能包含更加關(guān)鍵的信息。例如醫(yī)療診斷中人類患腫瘤性疾病的事件屬于少數(shù)類,但是如果將腫瘤性疾病誤診為沒有病變,可能就會(huì)喪失早期治療的機(jī)會(huì),造成難以挽回的結(jié)果[2]。不平衡分類產(chǎn)生的原因是采用普通分類方法去處理不平衡數(shù)據(jù)集導(dǎo)致分類器的分類結(jié)果不理想[3]。例如一個(gè)數(shù)據(jù)集中有998個(gè)反例,2個(gè)正例,那么只需要選擇一個(gè)將訓(xùn)練集數(shù)據(jù)預(yù)測(cè)為反例的學(xué)習(xí)方法即可,這樣該學(xué)習(xí)方法生成的學(xué)習(xí)器就可以達(dá)到99.8%的分類精度。但這樣的學(xué)習(xí)器對(duì)不平衡數(shù)據(jù)集的研究起不到任何積極的作用,因?yàn)樗穷A(yù)測(cè)不出正例的。隨著大數(shù)據(jù)時(shí)代的到來,現(xiàn)在這種問題普遍存在于故障檢測(cè)、信用卡欺詐檢測(cè)、網(wǎng)絡(luò)入侵識(shí)別以及電子郵件分類等領(lǐng)域,因此如何將不均衡的數(shù)據(jù)集既快速又準(zhǔn)確的處理是當(dāng)下學(xué)術(shù)研究的一個(gè)熱門方向[4-7]。

通常從算法和數(shù)據(jù)2個(gè)層面解決不平衡數(shù)據(jù)集問題[8]。數(shù)據(jù)層面有2種選擇,分別是增大正例樣本數(shù)目的過采樣以及縮減反例樣本數(shù)目的欠采樣。二者有一定的共同之處,都是通過改變各自類別的樣本數(shù)目使數(shù)據(jù)集達(dá)到一定程度的平衡。代表性的算法有合成少數(shù)類過采樣技術(shù)SMOTE[9]。算法層面所用到的方法,主要是在得到平衡數(shù)據(jù)集之后,通過引入代價(jià)矩陣或者對(duì)分類錯(cuò)誤率進(jìn)行改進(jìn)。將數(shù)據(jù)層面的方法和算法層面的方法結(jié)合起來得到的新分類器可以具有更強(qiáng)的多元性和魯棒性。

傳統(tǒng)分類器將不平衡數(shù)據(jù)集中的少數(shù)類預(yù)測(cè)正確的精度很低,為此對(duì)于上文提到的2種解決方案,當(dāng)前研究者大都以增加數(shù)據(jù)集中的正例樣本數(shù)目為切入點(diǎn)。文獻(xiàn)[9]所用的SMOTE算法是針對(duì)所有的正例樣本過采樣,容易產(chǎn)生重疊的新合成的正例樣本。Safe-level SMOTE[10]算法會(huì)對(duì)每個(gè)少數(shù)類樣本的檢測(cè)其臨近同類樣本的個(gè)數(shù),并以此設(shè)置每個(gè)少數(shù)類樣本的安全等級(jí),當(dāng)其值高于一定閾值時(shí)才會(huì)對(duì)此樣本進(jìn)行過采樣。該方法在一定程度上避免了噪聲數(shù)據(jù)的產(chǎn)生,但合成數(shù)據(jù)都過于集中在少數(shù)類內(nèi)部可能會(huì)出現(xiàn)過擬合現(xiàn)象。DB-SMOTE算法[11]以正例子簇簇心的距離為標(biāo)準(zhǔn)進(jìn)行過采樣,挑選那些邊際處的正例樣本當(dāng)作種子,以此避免過擬合現(xiàn)象,但這種方法容易產(chǎn)生重疊樣例。WOHC算法[12]考慮到在過采樣時(shí)會(huì)產(chǎn)生重疊樣本以及導(dǎo)致過擬合問題,采用加權(quán)過采樣的方法避免產(chǎn)生重疊樣本,但是該方法只能起到預(yù)防的作用,并不能起到根除產(chǎn)生重疊樣本的作用。

對(duì)于上述問題,本文提出基于蟻群聚類改進(jìn)的SMOTE不平衡數(shù)據(jù)過采樣算法ACC-SMOTE(Ant Colony Clustering Synthetic Minority Oversampling Technique)。首先采用改善的蟻群聚類算法將正例樣本劃分為不同的子簇,而后再根據(jù)各個(gè)正例子簇所占的樣本比例采用SMOTE算法來過采樣;最后讓經(jīng)過上述操作的正例樣本采用Tomek Links方法及時(shí)改正,清理掉正例樣本集中產(chǎn)生的噪聲數(shù)據(jù),進(jìn)而提高合成之后正例樣本的質(zhì)量。本文提出的ACC-SMOTE算法與經(jīng)典的SMOTE[9]、Safe-leve SMOTE[10]、DB-SMOTE[11]、WOHC[12]算法相對(duì)比,實(shí)驗(yàn)結(jié)果顯示該方法使正例樣本的預(yù)測(cè)精準(zhǔn)度得到提升。

1 預(yù)備理論

1.1 SMOTE算法

CHAWLA等[9]在2002年提出了對(duì)正例樣本合成的方法,即SMOTE。首先隨機(jī)選擇一個(gè)正例樣本,然后再找出距離它最近的k個(gè)樣本,按照采樣概率從距離它最近的k個(gè)樣本中選擇一個(gè)樣本按照公式(1)合成新樣本,反復(fù)執(zhí)行以上過程使數(shù)據(jù)集達(dá)到平衡。

Y=X1+rand·(X1-X2)。

(1)

其中,X1正例樣本,X2是距離X1最近的k個(gè)樣本中的一個(gè),rand是隨機(jī)生成一個(gè)從0至1區(qū)間內(nèi)的數(shù)的函數(shù),Y代表了新生成的正例樣本。

1.2 蟻群算法基本原理

蟻群聚類算法的思想是讓螞蟻在一個(gè)含有許多數(shù)據(jù)的區(qū)域隨機(jī)挪動(dòng)轉(zhuǎn)移[13]。當(dāng)螞蟻隨機(jī)挪動(dòng)到其中一個(gè)帶有數(shù)據(jù)的區(qū)域時(shí),計(jì)算該數(shù)據(jù)在它領(lǐng)域內(nèi)的相似度來得到螞蟻背負(fù)它的概率,如果該概率比隨機(jī)數(shù)大,螞蟻撿起該數(shù)據(jù)并背負(fù)它隨機(jī)挪動(dòng)轉(zhuǎn)移,否則螞蟻不撿起該數(shù)據(jù)繼續(xù)隨機(jī)挪動(dòng)轉(zhuǎn)移;在螞蟻背負(fù)數(shù)據(jù)隨機(jī)挪動(dòng)轉(zhuǎn)移到不含數(shù)據(jù)的空白區(qū)域時(shí),計(jì)算空白區(qū)域的相似度得到丟棄該數(shù)據(jù)的概率,若概率值大于隨機(jī)數(shù)則丟棄,反之丟棄失敗,繼續(xù)挪動(dòng)轉(zhuǎn)移到別的空白區(qū)域判斷。蟻群經(jīng)過上述過程反復(fù)的撿起、挪動(dòng)轉(zhuǎn)移、丟棄當(dāng)達(dá)到某個(gè)循環(huán)結(jié)束標(biāo)志時(shí)就會(huì)得到一個(gè)最終的聚類結(jié)果。

1.3 Tomek Link數(shù)據(jù)清理技術(shù)

Tomek Links是對(duì)數(shù)據(jù)集清理的一種關(guān)鍵技術(shù),可以用它來清理那些因過采樣而產(chǎn)生的噪聲數(shù)據(jù)和重疊樣例[14]。其主要思想是將Tomek Links看作是1對(duì)數(shù)據(jù)實(shí)例,它們距離(歐式距離)很近但屬于不同的類別。只有當(dāng)2個(gè)數(shù)據(jù)實(shí)例中的1個(gè)是噪聲數(shù)據(jù)或者2個(gè)數(shù)據(jù)實(shí)例都在各自類別的邊界上時(shí),這2個(gè)數(shù)據(jù)實(shí)例才有可能構(gòu)成一對(duì)Tomek Links。比如給定1對(duì)數(shù)據(jù)(xi,xj),xi,xj屬于不同的類別,即少數(shù)類xi,多數(shù)類xj,用d(xi,xj)表示它們之間的歐式距離。如果不存在另一數(shù)據(jù)實(shí)例x,使得d(xi,x)

2 改進(jìn)的過采樣算法ACC-SMOTE

為了獲取更多數(shù)據(jù)集中正例樣本所表示的信息內(nèi)容,本文通過致力于改進(jìn)SMOTE過采樣算法得到ACC-SMOTE算法,使各自類別的樣本數(shù)目達(dá)到相對(duì)均衡。該算法不僅著眼于數(shù)據(jù)集不同類別之間的不平衡,還想到同類之間不同子簇所含樣本數(shù)目的差異以及噪聲數(shù)據(jù)對(duì)樣本的影響。采用蟻群聚類得到最優(yōu)解,為下一階段采用SMOTE算法過采樣合成樣本提供更準(zhǔn)確的聚類結(jié)果,從而得到更理想的合成樣本。為了根除合成新樣本產(chǎn)生的重疊樣本,該算法采用了Tomek Links方法。ACC-SMOTE算法主要分為三部分:蟻群聚類階段,過采樣階段,合成數(shù)據(jù)整理階段。

2.1 蟻群聚類階段

在ACC-SMOTE算法的初始階段,需要將訓(xùn)練集先進(jìn)行預(yù)處理操作,即將訓(xùn)練集中的少數(shù)類進(jìn)行聚類,分為不同的子簇,然后再根據(jù)其所占的比例進(jìn)行過采樣。這樣做的目的是著眼于數(shù)據(jù)集不同類別之間的不平衡而且還有同類之間不同子簇所含樣本數(shù)目的差異,從而保證合成樣本的質(zhì)量,防止過擬合。

為避免一個(gè)數(shù)據(jù)反復(fù)地被拾起放下,導(dǎo)致聚類速度變慢,同時(shí)也為了避免因?yàn)殡S機(jī)性導(dǎo)致聚類結(jié)果的準(zhǔn)確性降低,ACC-SMOTE算法采用的蟻群聚類方法每只螞蟻對(duì)應(yīng)一種聚類方案,轉(zhuǎn)移方程中只有信息素權(quán)重。這是因?yàn)槊總€(gè)簇的聚類中心需要不斷地移動(dòng),轉(zhuǎn)移期望不好衡量,所以轉(zhuǎn)移方程中沒有轉(zhuǎn)移期望。在搜索解空間選擇某個(gè)點(diǎn)的類別時(shí),將信息素看成當(dāng)前點(diǎn)與每個(gè)類別的臨近程度,以概率p挑選信息素最高的點(diǎn),1-p的概率按信息素分布用輪盤賭方法挑選。概率p計(jì)算公式如下:

(2)

式(2)中1-pTh的值表示螞蟻在搜索路徑中隨機(jī)因素作用的強(qiáng)度,其值越大,選擇走過路徑的概率越大,從而導(dǎo)致局部最優(yōu),因此將直接轉(zhuǎn)移閾值設(shè)為pTh=0.9;τij(t)表達(dá)的意思是時(shí)間為t時(shí),邊(i,j)上所含的信息素。

更新信息素方面,為了解決其更新缺乏時(shí)效性的問題,根據(jù)方案的優(yōu)度(1/MSE)來增加方案上所有點(diǎn)-類對(duì)的信息素,每次迭代,每只螞蟻都得到一個(gè)方案;然后刷新每個(gè)點(diǎn)-類對(duì)上的信息素的濃度值。具體公式如下,其中所有方案已按MSE升序排好。

τij(t+m)=(1-volR)·τij(t)+Δτij(t),

(3)

(4)

(5)

式(3)中考慮到信息正反饋的作用,volR較小時(shí),信息正反饋占主導(dǎo)地位,算法收斂速度加快。為了提高蟻群聚類算法的收斂速度,可將信息素的散發(fā)率適當(dāng)降低為volR=0.1,式(4)中刷新信息素的最優(yōu)方案數(shù)updNum=3,式(5)中信息素系數(shù)pherC=107,最優(yōu)方案MSE的數(shù)組為sol數(shù)組。

上述算法的偽代碼如下：

輸入:聚類數(shù)K,樣本數(shù)N,少數(shù)類mindata

輸出:K個(gè)少數(shù)類子簇

(1)每只螞蟻對(duì)應(yīng)一種解決方案。

(2)初始化,生成一個(gè)較好的聚類方案,讓所有螞蟻都從該方案出發(fā)。

(3)將信息素看成當(dāng)前點(diǎn)與每個(gè)類別的臨近程度,根據(jù)公式(2)搜索解空間。

(4)依靠公式(3)(4)(5)刷新信息素;依靠方案的優(yōu)度來增加方案中所有點(diǎn)類對(duì)的信息素。

(5)反復(fù)執(zhí)行步驟(2)(3)(4),直到Num大于MaxNum或方案連續(xù)CRN次重復(fù)并且Num大于MinNum,結(jié)束循環(huán)(Num表示目前執(zhí)行了循環(huán)多少次,MaxNum和MinNum分別代表最多和最少可以執(zhí)行循環(huán)多少次)。

對(duì)于步驟(1)(2)使用最近距離輪盤賭法,在給定的N個(gè)正例樣本中選擇較分散的K個(gè)數(shù)據(jù)樣本當(dāng)成初始的子簇中心,按最近距離給出初始的聚類方案,存到每只的solution數(shù)組中;然后讓所有螞蟻都從該聚類方案出發(fā)。步驟(4)的更新過程中,將會(huì)失去volR比例的信息素,MSE較小的updNum個(gè)方案對(duì)其點(diǎn)-類對(duì)的信息素產(chǎn)生增量。

2.2 過采樣階段

經(jīng)過上述改進(jìn)的蟻群聚類可以得到不同少數(shù)類的子簇,其中2.1節(jié)的4個(gè)公式是該算法的核心,直接決定了聚類結(jié)果的好壞。采用SMOTE算法對(duì)少數(shù)類進(jìn)行過采樣大致可分為以下2個(gè)部分,首先將少數(shù)類劃分為不同的子簇,根據(jù)每個(gè)子簇大小所占樣本的比例確定采樣比重T,如公式(6)。然后按照公式(1)對(duì)不同子簇的少數(shù)類進(jìn)行過采樣,重復(fù)執(zhí)行以上過程直到達(dá)到過采樣比重。SMOTE算法可以使正例樣本數(shù)目增加,進(jìn)而改善數(shù)據(jù)集的不平衡性。

Ti=(Nmax-Nmin)×(Nmin-Ci)/Nmin。

(6)

式(6)中Nmax,Nmin分別代表反例以及正例的樣本數(shù)目;Ci表示當(dāng)前子簇的樣本數(shù)目;Ti代表i子簇的采樣比重。

單個(gè)正例樣本簇實(shí)現(xiàn)SMOTE過采樣的偽代碼如下。

輸入:正例樣本簇mindata,反例樣本數(shù)m1,正例樣本數(shù)m2

輸出:合成樣本后新的正例樣本簇new-mindata

(1)[r1,c1]=size(mindata);

(2)//確定采樣比例

(3)T=(m2-m1)×(m1-r1)/m1;//計(jì)算過采樣之后的簇樣本數(shù)

(4)ratio=T./r1;//使用每個(gè)樣本的KNN次數(shù)

(5)k=5;//近鄰數(shù)

(6)new-mindata=mySMOTE(mindata,ratio,k);

(7)//調(diào)用另個(gè)函數(shù)中SMOTE算法根據(jù)公式(1)過采樣

(8)[r2,c2]=size(new-mindata);

(9)ifr2>T

(10)new=randperm(r2,T);

(11)new-mindata=new-mindata(new,:);

(12)else

(13)new=randperm(r2,T-r2);

(15)end if

樣本合成示例如圖1。

圖1 過采樣合成樣本示例

2.3 合成數(shù)據(jù)整理階段

普通情況下在合成新的少數(shù)類樣本時(shí)產(chǎn)生噪聲樣本是不可消除的,而且噪聲樣本的存在會(huì)使分類器的性能下降。況且對(duì)少數(shù)類來說,樣本數(shù)目少就導(dǎo)致了它本身抗噪聲能力弱的缺陷,從而噪聲數(shù)據(jù)對(duì)分類效果產(chǎn)生較大的影響。通過過采樣對(duì)少數(shù)類樣本合成,從而使得樣本集中各類樣本數(shù)相對(duì)平衡。如果在過采樣時(shí)種子樣本的近鄰樣本是多數(shù)類樣本,那么合成之后的樣本就會(huì)是噪聲數(shù)據(jù),在使用分類器進(jìn)行分類時(shí)就不會(huì)提供有用的信息,反而可能會(huì)誤導(dǎo)分類器做出錯(cuò)誤的判斷,進(jìn)而會(huì)降低其分類精度。因此ACC-SMOTE算法采用Tomek Links數(shù)據(jù)清理技術(shù)處理新合成的樣本,其思想已在1.3節(jié)有簡單介紹,下面主要給出Tomek Links算法實(shí)現(xiàn)的偽代碼。

輸入:原始數(shù)據(jù)集Originaldata,數(shù)據(jù)的維度ic

輸出:Cleardata

(1)min-dist=zeros(size(Originaldata,1), 1);

(2)tomek-link=[];

5）回噴入爐工藝。發(fā)達(dá)國家垃圾熱值高，含水率低，且實(shí)行垃圾分類收集處理的方式，所以發(fā)達(dá)國家垃圾滲瀝液產(chǎn)生量小，可直接回噴入爐燃燒，解決了滲瀝液濃液的二次污染問題［1］。但我國生活垃圾沒有分選，生活垃圾中廚余垃圾占比大，含水率高，滲瀝液及處理后的濃縮液產(chǎn)生量大［2］。若全部回噴入爐，將降低爐溫，造成燃燒負(fù)荷波動(dòng)大，甚至850℃、2 s無法保證，且減少鍋爐的蒸發(fā)量和整個(gè)電廠發(fā)電量［3-4］。

(3)fori=1: size(Originaldata, 1)

(4)sample-mat=repmat(Originaldata(i,1:ic-1),

(5)size((Originaldata,1), 1);

(6)dists=sum(abs(Originaldata(:,1:ic-1)-sample-mat), 2);

(7)[ds,id]=sort(dists);

(8)if Originaldata(id(2),ic)～=Originaldata(i,ic)

(9)min-dist(i)=id(2);

(10)if min-dist(id(2))==i

(11)if Originaldata(i,ic)==0

(12)tomek-link=[tomek-linki];

(13)else

(14)tomek-link=[tomek-linkid(2)];

(15) end if

(16) end if

(17) end if

(18) end for

(19)Originaldata(tomek-link,:)=[];

(20)Cleardata=Originaldata;

(21)Output Cleardata

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

實(shí)驗(yàn)過程將分別對(duì)多組UCI數(shù)據(jù)集采取二八分原則將數(shù)據(jù)集分為測(cè)試集以及訓(xùn)練集[15],用上述方法來驗(yàn)證算法的有效性以及可行性。由于實(shí)驗(yàn)中數(shù)據(jù)集的劃分以及合成新樣本時(shí)存在偶然性,因此下面的結(jié)果都是執(zhí)行多次取得的平均值。

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

對(duì)于不平衡數(shù)據(jù)集,傳統(tǒng)的分類結(jié)果精準(zhǔn)度和評(píng)價(jià)指標(biāo)已不適用,為此采用從如表1所示的混淆矩陣中得到新評(píng)價(jià)指標(biāo)G-means[16]和F-value[17]。

表1 混淆矩陣

根據(jù)表1可以得到如下所示的評(píng)價(jià)指標(biāo):

正類樣本召回率:

(7)

負(fù)類樣本召回率:

(8)

正類樣本查準(zhǔn)率:

(9)

G-means值:

(10)

F-value值:

(11)

G-means值綜合考量正例樣本和反例樣本的召回率,只有當(dāng)兩者值都大時(shí),G-means值才會(huì)大,可以更精確地顯示出模型的分類效果。而F-value值著眼于對(duì)正例樣本的查準(zhǔn)率和召回率,可以更加精確地顯示出正例樣本的分類準(zhǔn)確度。由此本文實(shí)驗(yàn)將由G-means值和F-value值作為評(píng)價(jià)模型的指標(biāo)。

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

在實(shí)驗(yàn)之前,對(duì)一些數(shù)據(jù)進(jìn)行整合,主要包括刪除有屬性缺失的數(shù)據(jù)和將多分類轉(zhuǎn)變成二分類。數(shù)據(jù)集結(jié)構(gòu)如表2。

表2 UCI數(shù)據(jù)集

3.3 實(shí)驗(yàn)結(jié)果對(duì)比

為了證明ACC-SMOTE算法的有效性及可行性,在Blood、Breast cancer、Ecoli、Haberman、Ionoshpere、Pima、Yeast 7種不同的數(shù)據(jù)集里將SMOTE[9]、Safe-level SMOTE[10]、DB-SMOTE[11]、WOHC[12]4種算法分別結(jié)合C4.5分類算法作比較,采用G-means和F-value作為評(píng)價(jià)指標(biāo)。把不結(jié)合任何過采樣算法的C4.5的分類結(jié)果作為比較準(zhǔn)則,從實(shí)驗(yàn)結(jié)果說明了處理不平衡數(shù)據(jù)的重要性。實(shí)驗(yàn)結(jié)果如表3。

從表3中可以得出在數(shù)據(jù)集Blood,Haberman,Ionoshpere,Pima,Yeast中,ACC-SMOTE算法的G-means值和F-value值均高于其他算法,G-means值在Blood,Breast cancer,Haberman,Ionoshpere 4組數(shù)據(jù)集上也取得較好效果。該算法相比于WOHC算法G-means和F-value值均有提升,一方面該算法有效克服了噪聲樣本的影響,另一方面,該算法能夠較好的處理具有分類困難樣本的不平衡數(shù)據(jù),有效的明確正例樣本的邊界,進(jìn)而提高了分類的精度。

表3 ACC-SMOTE算法與其他算法的比較

4 結(jié) 語

對(duì)于不平衡數(shù)據(jù)集問題,現(xiàn)在已有的方法大都僅僅著眼于數(shù)據(jù)集不同類別之間的不平衡,沒有考慮到同類之間不同子簇所含樣本數(shù)目的差異,經(jīng)過過采樣之后的訓(xùn)練集可能會(huì)出現(xiàn)邊緣化問題,訓(xùn)練出的模型更可能出現(xiàn)過擬合現(xiàn)象,從而降低分類精準(zhǔn)度。為了克服現(xiàn)有過采樣算法的不足,提出了ACC-SMOTE算法。該算法針對(duì)合成新樣本過程存在的問題,引入聚類思想和數(shù)據(jù)清理技術(shù),有效降低了數(shù)據(jù)集中類間、類內(nèi)的不平衡性以及邊緣化問題出現(xiàn)的概率。經(jīng)驗(yàn)證ACC-SMOTE算法可以明顯提高少數(shù)類樣本的分類準(zhǔn)確度,分類性能更優(yōu),從而證明了該算法的可行性與有效性。

現(xiàn)實(shí)生活中還會(huì)出現(xiàn)多分類的情形,以后的工作可以進(jìn)一步將多分類數(shù)據(jù)集的采樣方法作為研究內(nèi)容,以便于將ACC-SMOTE算法應(yīng)用于更多領(lǐng)域。