密度不均衡數(shù)據(jù)分類算法

杜紅樂，張 燕

(商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西 商洛 726000)

·計(jì)算機(jī)軟件理論、技術(shù)與應(yīng)用·

密度不均衡數(shù)據(jù)分類算法

杜紅樂，張 燕

(商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西 商洛 726000)

針對(duì)不均衡數(shù)據(jù)下分類超平面偏移、少數(shù)類識(shí)別率較低的問題，提出一種基于樣本密度的不均衡數(shù)據(jù)分類算法。該算法首先計(jì)算樣本密度和類樣本密度，依據(jù)類樣本密度之間的關(guān)系確定聚類類數(shù),然后利用K-means聚類算法對(duì)多數(shù)類樣本進(jìn)行聚類，用聚類所得類中心作為樣本集取代原多數(shù)類樣本集,最后對(duì)新構(gòu)造的訓(xùn)練集進(jìn)行訓(xùn)練得到最終決策函數(shù)。其實(shí)驗(yàn)結(jié)果表明，該算法能夠提高SVM在不均衡數(shù)據(jù)下的分類性能，尤其是少數(shù)類的分類性能。

支持向量機(jī)；不均衡數(shù)據(jù)集；樣本密度；欠取樣；K-近鄰

支持向量機(jī)(support vector machine， SVM)基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，在解決小樣本、非線性及高維屬性等模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢，因此，SVM得到許多專家的關(guān)注，并在許多領(lǐng)域得到應(yīng)用。

傳統(tǒng)SVM在均衡訓(xùn)練樣本下有較好的分類性能，然而，研究表明，在樣本密度分布不均衡的情況下，SVM對(duì)少數(shù)類樣本分類準(zhǔn)確率遠(yuǎn)低于對(duì)多數(shù)類樣本的分類準(zhǔn)確率。因?yàn)閭鹘y(tǒng)SVM算法對(duì)多數(shù)類是過學(xué)習(xí)，而對(duì)少數(shù)類則是欠學(xué)習(xí)，從而導(dǎo)致對(duì)少數(shù)類樣本的分類錯(cuò)誤率較高。實(shí)際應(yīng)用中對(duì)少數(shù)類樣本的分類性能要求比對(duì)多數(shù)類樣本的分類性能高得多。例如入侵檢測中入侵行為樣本較難收集，是少數(shù)樣本，把一個(gè)入侵行為錯(cuò)分為正常行為要比把一個(gè)正常行為錯(cuò)分為入侵行為造成的危害大得多，因此為提高對(duì)不均衡數(shù)據(jù)的分類能力，學(xué)者們提出了相應(yīng)的解決方法。這些方法大致可以分為2類：基于數(shù)據(jù)的和基于算法的?；跀?shù)據(jù)的方法主要是依據(jù)一定策略刪除部分多數(shù)類的樣本或者增加一些少數(shù)類的樣本使數(shù)據(jù)集均衡化，進(jìn)而提高分類器的分類性能，常用的方法有過取樣[1-5]、欠取樣[6-10]和混合取樣[11-13]；基于算法的方法主要有代價(jià)敏感學(xué)習(xí)[14]、集成方法(如boosting[15])、單類學(xué)習(xí)法[16]等。

文獻(xiàn)[6-11]都采用聚類算法對(duì)數(shù)據(jù)集進(jìn)行相應(yīng)處理。文獻(xiàn)[7]利用K-means算法對(duì)多數(shù)類樣本進(jìn)行聚類并提取類中心，得到與少數(shù)類樣本數(shù)量相同的樣本，重構(gòu)新的訓(xùn)練集，為避免少數(shù)類樣本過少導(dǎo)致最終訓(xùn)練樣本過度稀疏，對(duì)少數(shù)類樣本采用SMOTE算法進(jìn)行過取樣。文獻(xiàn)[8]為提高泛化能力，聚類在核空間中進(jìn)行，并利用AdaBoost集成手段對(duì)該欠取樣算法進(jìn)行集成。文獻(xiàn)[9]引入“聚類一致性系數(shù)”找出處于少數(shù)類邊界區(qū)域和處于多數(shù)類中心區(qū)域的樣本，然后用SMOTE對(duì)少數(shù)類樣本進(jìn)行過取樣，用改進(jìn)的隨機(jī)欠取樣對(duì)多數(shù)類樣本進(jìn)行處理。文獻(xiàn)[10]利用譜聚類的優(yōu)點(diǎn)對(duì)多數(shù)類樣本在核空間中進(jìn)行譜聚類，然后依據(jù)聚類大小和聚類中樣本與少數(shù)類樣本間的距離選擇有代表性的信息點(diǎn)。

導(dǎo)致分類超平面偏移的本質(zhì)是樣本密度的不均衡。樣本密度小，則該類樣本出現(xiàn)的概率越小，分類超平面向該區(qū)域偏移時(shí)錯(cuò)分的可能性越小；因此，錯(cuò)分的總代價(jià)也越小(兩類錯(cuò)分代價(jià)相同，但是錯(cuò)分的概率?。灰虼?，平均出錯(cuò)就少，平均代價(jià)也就小)。如果超平面向密度大的區(qū)域偏移，樣本出現(xiàn)在該區(qū)域的概率就大，造成錯(cuò)分的總代價(jià)就大，而支持向量機(jī)在保證分類間隔盡可能大的同時(shí)，錯(cuò)誤分類代價(jià)盡可能的??；因此，分類超平面會(huì)向樣本密度小的一方偏移。以上方法都是依據(jù)少數(shù)類樣本數(shù)量和多數(shù)類樣本數(shù)量之間的關(guān)系對(duì)多數(shù)類進(jìn)行重取樣，沒有考慮實(shí)際的樣本密度分布情況。

基于以上分析，結(jié)合聚類算法和K-近鄰算法，本文給出一種基于樣本密度的聚類算法以解決樣本不均衡的問題。該算法依據(jù)類樣本密度之間關(guān)系和少數(shù)類樣本數(shù)量，計(jì)算多數(shù)類重取樣后的樣本數(shù)量k，然后用K-means聚類算法對(duì)多數(shù)類樣本進(jìn)行聚類，用所得的類中心作為樣本取代原多數(shù)類樣本集。該算法在重取樣時(shí)既考慮了樣本數(shù)量，又考慮樣本密度的分布。其仿真實(shí)驗(yàn)結(jié)果表明，該方法較好地解決了不均衡數(shù)據(jù)集導(dǎo)致分類超平面偏移的問題，提高了支持向量機(jī)的泛化能力，提高了少數(shù)類樣本的分類準(zhǔn)確率。

1 支持向量機(jī)

1.1 支持向量機(jī)

SVM的訓(xùn)練過程實(shí)質(zhì)是二次優(yōu)化問題，既要保證分類錯(cuò)誤代價(jià)最小，又要保證最大化分類間隔。給定一個(gè)樣本集T={(x1,y1),(x2,y2),…,(x1,y1)},xi∈R″,yi∈{1,-1}。SVM的主要目的是構(gòu)造一個(gè)超平面以分割2類樣本，使得分類間隔最大，同時(shí)分類錯(cuò)誤代價(jià)最小。通過求解下面二次優(yōu)化問題，得到?jīng)Q策函數(shù)。

s.t.yi(+b)≥1-εi

(1)

εi≥0,i=1,2,…,l。

通過引入Lagrange算子，可以得到問題(1)的對(duì)偶問題：

(2)

其中K(xi,xj)為核函數(shù)，K(xi,xj)=〈φ(xi),φ(xj)〉，對(duì)于線性不可分問題，采用非線性映射φ:RkF將訓(xùn)練集從輸入空間映射到某一特征空間上，在該特征空間上訓(xùn)練集是線性可分的。最后得到?jīng)Q策函數(shù)

(3)

由決策函數(shù)可以看出，決定支持向量機(jī)分類性能的是支持向量，即ai≠0的樣本，而那些遠(yuǎn)離分類超平面的樣本對(duì)分類結(jié)果影響較小可以忽略。

1.2 密度不均衡對(duì)SVM的影響

不均衡數(shù)據(jù)集指的是同一數(shù)據(jù)集中某類的樣本數(shù)量比其他類的樣本數(shù)量多得多，其中樣本數(shù)量多的類稱為多數(shù)類，樣本數(shù)量少的類稱為少數(shù)類。所謂不均衡分類問題是指基于這種不平衡數(shù)據(jù)集進(jìn)行的分類。實(shí)際上，影響SVM分類性能的不僅是樣本數(shù)量，還與樣本空間分布有關(guān)，即受類樣本密度的影響。

為觀察類樣本密度對(duì)分類超平面的影響，隨機(jī)生成2類均勻分布的樣本，數(shù)據(jù)集1的第1類樣本為U([0,1]×[0,1])、第2類樣本為U([1,2]×[0,1])，如圖1(a)所示；數(shù)據(jù)集2的第1類樣本為U([0,1]×[0,1])、第2類樣本為U([1,1.3]×[0,1])，如圖1(b)所示；數(shù)據(jù)集3的第1類樣本為U([0,1]×[0,1])、第2類樣本為U([1,1.1]×[0,1])，如圖1(c)所示。圖1中第1類樣本數(shù)均為200，第2類樣本數(shù)均為20，經(jīng)支持向量機(jī)訓(xùn)練最終的分類超平面如圖1(a)、(b)、(c)所示，其中細(xì)線為分類超平面。

由圖1可以看出：在類樣本密度不均衡的情況下，分類超平面會(huì)向少數(shù)類樣本偏移，即對(duì)少數(shù)類的欠學(xué)習(xí)，如圖1(a)所示；類樣本密度相差較小的時(shí)候，分類超平面偏移也較小如圖1(b)所示；當(dāng)類樣本密度相同時(shí)，分類超平面不偏移，如圖1(c) 所示。換句話說，在樣本密度不均衡時(shí)，分類超平面向類樣本密度較小側(cè)偏移，導(dǎo)致對(duì)樣本密度大的類的過學(xué)習(xí)。這是因?yàn)閭鹘y(tǒng)支持向量機(jī)在訓(xùn)練的時(shí)候認(rèn)為2類樣本錯(cuò)分代價(jià)相同，而2個(gè)類(區(qū)域)樣本密度不同，即出現(xiàn)在密度小的區(qū)域的概率小，大密度區(qū)域出現(xiàn)的概率大。SVM為了保證分類間隔盡可能的大，同時(shí)錯(cuò)分代價(jià)盡可能的小，因此分類超平面會(huì)向樣本密度小的區(qū)域(少數(shù)類)偏移。針對(duì)此，文獻(xiàn)[13]提出了對(duì)2個(gè)類采用不同的懲罰因子的方法，對(duì)少數(shù)類采用較大的懲罰因子，增加少數(shù)類樣本的錯(cuò)分代價(jià)，而對(duì)多數(shù)類采用較小的懲罰因子；但是對(duì)于不同的訓(xùn)練數(shù)據(jù)懲罰因子確定困難。文獻(xiàn)[7]對(duì)多數(shù)類樣本采用聚類的方法，減少了多數(shù)類樣本的數(shù)量，同時(shí)也減少了樣本的密度。當(dāng)多數(shù)類樣本空間與少數(shù)類樣本空間相同時(shí)，由于最后2類樣本數(shù)量相等，因此樣本密度也就均衡;但是如果2類樣本空間大小不同則導(dǎo)致出現(xiàn)新的樣本密度不均衡，其原因在于該方法只考慮樣本的數(shù)量而沒有考慮樣本空間大小。為此，本文從樣本集本身出發(fā)，結(jié)合樣本數(shù)量和樣本空間大小，即依據(jù)類樣本密度之間的關(guān)系對(duì)多數(shù)類樣本進(jìn)行欠取樣，從而使數(shù)據(jù)集均衡化。

2 重取樣算法

2.1 樣本密度

為了描述樣本密度及類樣本密度，本文采用歐式距離計(jì)算樣本間的距離。

定義 1 樣本間距離：樣本x與樣本y之間的距離d(x,y)為

d(x,y)=x-y。

(4)

式中：x、y為多維向量；x表示x的二階范數(shù)，用于計(jì)算樣本間的歐式距離。

在線性不可分情況下，支持向量機(jī)通過核函數(shù)將樣本由輸入空間映射到某一特征空間中，使得樣本在該特征空間中可分，假設(shè)映射函數(shù)為φ:RkF，核函數(shù)為K(x,y)=〈φ(x),φ(y)〉，則在特征空間下2個(gè)樣本間的距離為

假設(shè)核函數(shù)采用RBF，則K(x,y)=exp(-gx-y2)，g為一待定的常數(shù)，且g的值也將影響最終結(jié)果，g值一般取維數(shù)的倒數(shù)，由式(5)可得

(6)

定義2 樣本密度：第i類樣本集中任意樣本x的樣本密度D(x)定義為

D(x)=N(xij|d(x,xij)ar,j=1,2,…,ni)。

(7)

式中：N(·)是統(tǒng)計(jì)滿足條件的樣本數(shù)；xij表示第i類樣本中第j個(gè)樣本；ni表示第i類樣本的數(shù)量；d(x,xij)表示第i類樣本x與第i類樣本中的第j個(gè)樣本間的距離，是歐氏距離，也可以是特征空間中的距離；r表示超球的半徑(閾值)。閾值的選擇對(duì)樣本密度的計(jì)算有很大的影響，選擇過大，所有樣本都被包含進(jìn)去即樣本密度為ni，選擇過小，每個(gè)樣本的密度都為1。a為控制系數(shù)，可以進(jìn)一步調(diào)整閾值，使樣本密度能夠反映實(shí)際的樣本分布。本文將對(duì)多數(shù)類樣本中每個(gè)樣本包含K個(gè)樣本的最小超半徑的平均值作為r。

定義3 類樣本密度：第i類樣本的類樣本密度D(Ci)為

(8)

確保經(jīng)聚類后各類樣本密度的均衡的關(guān)鍵在于K-means中K值的確定。本文依據(jù)樣本數(shù)量與樣本密度之間的關(guān)系來確定K值，D(x)實(shí)質(zhì)上就是指定半徑的超球內(nèi)的樣本數(shù)量，D(Ci)為平均值，因此ni/D(Ci)表示ni個(gè)樣本可以用多個(gè)這樣的超球容納。為使各類之間最終形成的超球數(shù)量相同，則應(yīng)滿足

n1/D(C1)=n2/D(C2)=…=ni/D(Ci)。

(9)

對(duì)于2類分類，假設(shè)n1表示多數(shù)類樣本數(shù)量，n2表示少數(shù)類樣本數(shù)量，設(shè)對(duì)多數(shù)類樣本經(jīng)過聚類處理后的樣本數(shù)量為n，則

n/D(C1)=n2/D(C2)。

變形可得

n=D(C1)·n2/D(C2)。

(10)

2.2 重取樣算法描述

基于樣本密度的聚類算法具體描述如下。

輸入：多數(shù)類樣本集bdata，少數(shù)類樣本集sbata。

輸出：對(duì)多數(shù)類樣本重取樣的樣本集bdata’，少數(shù)類樣本集sdata。

Step1對(duì)于多數(shù)類樣本集，計(jì)算每個(gè)樣本K-近鄰中相距最遠(yuǎn)的樣本距離di。

Step3對(duì)于每類中的樣本，利用公式(7)計(jì)算每個(gè)樣本的密度D(x)，并用公式(8)計(jì)算類樣本密度D(Ci)。

Step4利用公式(10)計(jì)算多數(shù)類樣本聚類后的類別數(shù)。

Step5調(diào)用K-means聚類算法對(duì)多數(shù)類樣本進(jìn)行聚類，以聚類所得類中心為新的樣本，與原有少數(shù)類樣本共同構(gòu)成新的訓(xùn)練集。

3 實(shí)驗(yàn)及數(shù)據(jù)分析

為驗(yàn)證本文算法的有效性，該節(jié)用人工數(shù)據(jù)集和UCI數(shù)據(jù)集對(duì)本文算法進(jìn)行驗(yàn)證。實(shí)驗(yàn)設(shè)計(jì)思路如下：首先選擇二維人工不均衡數(shù)據(jù)，可以看到分類超平面的偏移情況，并與聚類方法和不使用降維處理的SVM算法進(jìn)行對(duì)比，來驗(yàn)證本文算法的性能；然后用不均衡的UCI數(shù)據(jù)集進(jìn)行相同的驗(yàn)證；最后對(duì)分類器訓(xùn)練的時(shí)間復(fù)雜度進(jìn)行分析，并比較在UCI數(shù)據(jù)集上的訓(xùn)練時(shí)間，對(duì)比分類時(shí)間及總體分類性能上的效果。

本文所做實(shí)驗(yàn)是在Matlab 7.11.0環(huán)境中結(jié)合了臺(tái)灣林智仁老師的LIBSVM[17]，主機(jī)為Intel Core i7 2.3GHz，8G內(nèi)存，操作系統(tǒng)為Win7的PC機(jī)上完成的。

3.1 性能評(píng)價(jià)

對(duì)于均衡數(shù)據(jù)的分類方法，常用分類精度作為評(píng)價(jià)指標(biāo)，該評(píng)價(jià)指標(biāo)基于錯(cuò)分代價(jià)相同，因此這個(gè)評(píng)價(jià)指標(biāo)用在不均衡數(shù)據(jù)集則不合理。有學(xué)者給出了針對(duì)不均衡數(shù)據(jù)的評(píng)價(jià)指標(biāo)，TP為正類樣本被分為正類的數(shù)量，F(xiàn)P為正類樣本被分為負(fù)類的數(shù)量，F(xiàn)N為負(fù)類樣本被分為正類的樣本數(shù)量，TN為負(fù)類樣本被分為負(fù)類的數(shù)量[18]。假設(shè)正類為多數(shù)類，由此得少數(shù)類正確分類率為

Se=TN/(TN+FN) ，

(11)

多數(shù)類樣本正確率為

Re=TP/(TP+FP)，

(12)

少數(shù)類查準(zhǔn)率為

Pr=TN/(FP+TN)，

(13)

則Fv和Gm定義如下：

(14)

(15)

其中λ為Pr與Re的相對(duì)重要性。Fv綜合考慮少數(shù)類樣本的準(zhǔn)確率和查準(zhǔn)率，因此能夠更準(zhǔn)確地反映對(duì)少數(shù)類樣本的分類性能。Gm綜合考慮多數(shù)類和少數(shù)類樣本的分類準(zhǔn)確率，因此能夠衡量分類器的整體分類性能。本文實(shí)驗(yàn)使用這2個(gè)評(píng)價(jià)指標(biāo)，且取λ=1。

3.2 人工數(shù)據(jù)集

3.2.1 線性可分?jǐn)?shù)據(jù)

為簡化過程，本文實(shí)驗(yàn)數(shù)據(jù)采用人工生成方式。為觀察不均衡數(shù)據(jù)對(duì)分類決策面的影響，隨機(jī)產(chǎn)生2類均勻分布的不均衡樣本，第1類樣本為U([0,1]×[0,1])，第2類樣本為U([1,1.4]×[0,1])，第1類樣本數(shù)為300，第2類樣本數(shù)為50。測試集同樣采用均衡分布的人工數(shù)據(jù)，第1類樣本為U([0,1.05]×[0,1])，第2類樣本為U([0.95,1.35]×[0,1])，2類樣本各100個(gè)樣本，如圖2所示。

表1中的面積比值是多數(shù)類樣本分布區(qū)域與少數(shù)類樣本分布區(qū)域的面積比，依據(jù)這個(gè)區(qū)域及樣本數(shù)量可以粗略估計(jì)樣本密度。當(dāng)面積為1∶3時(shí)，經(jīng)過聚類算法后密度比約為1∶3，出現(xiàn)新的不均衡；當(dāng)面積接近1∶1時(shí)，即聚類后樣本密度接近1∶1時(shí)，聚類算法效果較好；當(dāng)面積比例接近樣本數(shù)量比時(shí)(樣本數(shù)300∶50，面積比1∶0.2)，聚類算法與本文算法都比直接支持向量機(jī)算法的效果要差。本文算法差的原因在于，本文算法只用于改變原多數(shù)類樣本的密度，而沒有改變少數(shù)類樣本的密度。當(dāng)面積為1∶0.1時(shí)，實(shí)際多數(shù)類樣本密度要比少數(shù)類樣本密度小，因此無法調(diào)整密度使2類樣本密度接近，從而導(dǎo)致其結(jié)果不如直接SVM算法的結(jié)果。

從圖2可以看到，傳統(tǒng)支持向量機(jī)分類超平面會(huì)向少數(shù)類方向偏移，使得對(duì)少數(shù)類欠學(xué)習(xí)，如圖(a)所示。經(jīng)聚類處理[8]后，分類超平面向多數(shù)類偏移，其原因在于對(duì)原多數(shù)類樣本重取樣后數(shù)量與原少數(shù)類樣本數(shù)量相同；但從圖2(b)中可以看出，原多數(shù)類樣本空間大小是少數(shù)類樣本空間大小2.5倍，也就是說聚類結(jié)束后，原少數(shù)類樣本密度與多數(shù)類樣本密度之比為2.5，形成了新的密度不均衡，原來的多數(shù)類變?yōu)槊芏刃〉念?，分類超平面向新的少?shù)類偏移。圖2(c)是本文算法處理后的結(jié)果，可以看到分類超平面能很好地分離2個(gè)類。

由于上面數(shù)據(jù)集是隨機(jī)生成的，具有一定的偶然性，因此實(shí)驗(yàn)給出5次測試結(jié)果和平均值。表2給出了5次隨機(jī)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果，其中訓(xùn)練集第1類樣本為U([0,1]×[0,1])，第2類樣本為U([1,1.4]×[0,1])，第1類樣本數(shù)為300，第2類樣本數(shù)為50，核函數(shù)采用徑向基核函數(shù)。

從表2可以看到，在2個(gè)類樣本空間不同的情況下，本文算法的性能比聚類算法和直接SVM算法要好。對(duì)比圖2可以看出，本文算法的分類超平面能更準(zhǔn)確地把2個(gè)類區(qū)分開。

3.2.2 線性不可分?jǐn)?shù)據(jù)集

從表3可以看到，5次實(shí)驗(yàn)結(jié)果中本文算法都優(yōu)于聚類算法和直接SVM算法。對(duì)比圖3，也可以看到本文算法的分類超平面既不向多數(shù)類偏移，也不向少數(shù)類偏移，能更準(zhǔn)確區(qū)分2類樣本，因此有較高的分類準(zhǔn)確率。

3.3 UCI數(shù)據(jù)集

本實(shí)驗(yàn)數(shù)據(jù)集選取contraceptive method choice(Cmc)、haberman′s survival、ionosphere、letter recognition和pima indians diabetes 5組UCI數(shù)據(jù)，這5組實(shí)驗(yàn)數(shù)據(jù)屬性都為實(shí)數(shù)，并且類樣本間有不同程度的不均衡性。本實(shí)驗(yàn)中多數(shù)類樣本為正類，少數(shù)類樣本為負(fù)類。表4給出了各組實(shí)驗(yàn)數(shù)據(jù)集中屬性、樣本數(shù)量等特點(diǎn)。數(shù)據(jù)集Cmc和letter是多類數(shù)據(jù)集，該實(shí)驗(yàn)把其轉(zhuǎn)換為2類數(shù)據(jù)。數(shù)據(jù)集Cmc把B類作為少數(shù)類，其他R和L類作為多數(shù)類；數(shù)據(jù)集letter把A類作為少數(shù)類，其他B-Z類作為多數(shù)類。

表5給出了在數(shù)據(jù)集contraceptive method choice(Cmc)、haberman’s survival、ionosphere、letter recognition和pima上的實(shí)驗(yàn)結(jié)果。由于聚類算法初始K個(gè)樣本是隨機(jī)選擇的，具有一定的隨機(jī)性，因此表5中的數(shù)據(jù)均為進(jìn)行5次實(shí)驗(yàn)后，取的最優(yōu)結(jié)果。從表5中可以看到，本文算法比采用聚類算法的結(jié)果要優(yōu)，另外，最終對(duì)多數(shù)類樣本進(jìn)行欠取樣的結(jié)果也是相等的。

3.4 K值對(duì)算法的影響

本文算法需要計(jì)算每個(gè)樣本的K-近鄰，利用包含K個(gè)近鄰樣本的最小距離的平均值作為閾值計(jì)算每個(gè)樣本的密度，然后再用每個(gè)樣本密度的平均值作為類密度；因此K值對(duì)計(jì)算最終的類密度有很大的影響。如果K=1，則每個(gè)樣本的密度都為1，類的密度必定相同，若K值過大，則把整個(gè)類的樣本都包含進(jìn)去，類的樣本密度仍然相等；因此K值決定樣本的縮減規(guī)模和增加規(guī)模。為了更直觀地看到K值的影響，該節(jié)選用3.2.1節(jié)中的數(shù)據(jù)集進(jìn)行分析，其不同K值對(duì)應(yīng)的結(jié)果如表6所示。由表6可以看出，隨著K值的變化，分類性能在不斷波動(dòng)，隨著K值的增加，對(duì)多數(shù)類樣本進(jìn)行重取樣的數(shù)目就比較少，準(zhǔn)確率在不斷的波動(dòng)，但整體是降低的。

4 結(jié)論

由于實(shí)際應(yīng)用中訓(xùn)練樣本不均衡的問題主要表現(xiàn)為樣本密度分布不均衡，因此，本文結(jié)合聚類算法和K-近鄰算法，提出一種基于樣本密度的不均衡數(shù)據(jù)分類算法。該算法利用類樣本密度之間的關(guān)系確定最終多數(shù)類樣本數(shù)量，然后用聚類對(duì)多數(shù)類樣本進(jìn)行欠取樣。該方法進(jìn)行重取樣后能夠保持2類樣本密度的均衡化，使得分類超平面不向任何一方偏移。最后用人工數(shù)據(jù)集和UCI數(shù)據(jù)集驗(yàn)證該方法的有效性。通過與聚類算法和直接SVM算法進(jìn)行比較的結(jié)果表明：在不同的數(shù)據(jù)集及不同的不均衡化程度下，該方法有較好的實(shí)驗(yàn)效果；然而如果少數(shù)類樣本數(shù)量很少，且樣本密度與多數(shù)類樣本密度相差不大的時(shí)候分類性能仍然會(huì)下降。如何對(duì)這樣的少數(shù)類樣本進(jìn)行過取樣將是下階段的主要工作。

[1]李雄飛,李軍,董元方，等.一種新的不平衡數(shù)據(jù)學(xué)習(xí)算法PCBoost[J]. 計(jì)算機(jī)學(xué)報(bào)，2012, 35(2):202-209.

[2]曾志強(qiáng),吳群,廖備水.一種基于核SMOTE的非平衡數(shù)據(jù)集分類方法[J].電子學(xué)報(bào)，2009,37(11):2489-2495.

[3]CHEN B, MA L, HU J. An Improved Multi-label Classification Method Based on SVM with Delicate Decision Boundary [J]. International Journal of Innovative Computing, Information and Control, 2010, 6(4):1605-1614.

[4]樓曉俊,孫雨軒,劉海濤.聚類邊界過采樣不平衡數(shù)據(jù)分類方法[J]. 浙江大學(xué)學(xué)報(bào):工學(xué)版,2013,47(6):944-950.

[5]林舒楊,李翠華,江弋,等.不平衡數(shù)據(jù)的降維采用方法研究[J].計(jì)算機(jī)研究與發(fā)展,2011,48(增刊3):47-53.

[6]陶新民,郝思媛,張冬雪.核聚類集成失衡數(shù)據(jù)SVM算法[J].哈爾濱工程大學(xué)學(xué)報(bào),2013，34(3):381-388.

[7]陳思,郭躬德,陳黎飛.基于聚類融合的不平衡數(shù)據(jù)分類方法[J].模式識(shí)別與人工智能, 2010,23(6):772-780.

[8]陶新民,張冬梅,郝思媛,等.基于譜聚類欠取樣的不均衡數(shù)據(jù)SVM算法[J].控制與決策,2012,27(12): 1761-1768.

[9]楊智明,彭宇,彭喜元.基于支持向量機(jī)的不平衡數(shù)據(jù)集分類方法研究[J].儀器儀表學(xué)報(bào),2009, 30(5):1094-1099.

[10]陶新民,童智靖,劉玉.基于ODR和BSMOTE結(jié)合的不均衡數(shù)據(jù)SVM分類算法[J].控制與決策,2011,26(10):1535-1541.

[11]曹鵬,李博,栗偉,等.基于概率分布估計(jì)的混合采樣算法[J].控制與決策,2014,29(5):815-820.

[12]夏戰(zhàn)國,夏士雄,蔡世玉,等.類不均衡的半監(jiān)督高斯過程分類算法[J].通信學(xué)報(bào),2013,34(5):42-51.

[13]蔡艷艷,宋曉東.針對(duì)非平衡數(shù)據(jù)分類的新型模糊SVM模型[J].西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版,2015,42(5):140-145.

[14]SUN Y M, KAMEL M S, ANDREW W, et al. Cost-sensitiveBoosting for Classification of Imbalanced Data[J]. Pattern Recognition, 2007,40(12):3358-3378.

[15]XIAO J, XIE L, HE C Z, et al.Dynamic Classifier Ensemble Model for Customer Classification with Imbalanced Class Distribution[J]. Expert Systems with Applications, 2012,39(3):3668-3675.

[16]WANG S J,XI L F. ConditionMonitoring System Design with One-class and Imbalanced Data Classifier[C]//Proceedings of the 16thInternational Conference on Industrial Engineering and Engineering Management(IE&EM’09).Beijing:IEEE,2009:779-783.

[17]CHANG C C, LIN C J. LIBSVM: a Library for Support Vector Machines[EB/OL].[2014-10-15]. http://www.csie.ntu.tw/～cjlin/libsvm.

[18]SUC T,CHEN L S. Knowledge Acquisition through Information Granulation for Imbalanced Data [J]. Expert Systems with Applications, 2006,31(3):531-541.

(編校：饒莉)

A Classification Algorithm for Imbalanced Dataset of Sample Density

DU Hong-le, ZAHGN Yan

(SchoolofMathematicsandComputerApplication,ShangluoUniversity,Shangluo726000China)

In order to resolve the classifiers’ over fitting phenomenon to enhance classification performance, a new algorithm based on sample density is proposed for imbalanced data classification. Firstly, it computes the density of samples and the density of every class. Then it works out the number of class with cluster algorithm according to the relation of sample density of every class. Then it clusters the samples of majority class usingK-means algorithm with above class number. The cluster centers are treated as the new samples and then a new training dataset is constructed with the new samples and minority dataset. According to the new training dataset, we can get the decision function. The method may resolve the problem of imbalanced dataset and improve the classification performance of SVM. Results of experiments with artificial dataset and six groups of UCI dataset show that the algorithm is effective for imbalanced dataset, especially for the minority class samples.

support vector machine; imbalanced dataset; sample density; under-sampling;K-nearest neighbor

2015-01-18

陜西省自然科學(xué)基金項(xiàng)目(2014JM2-6122)；陜西省教育廳科技計(jì)劃項(xiàng)目(12JK0748)；商洛學(xué)院科學(xué)與技術(shù)研究項(xiàng)目(13sky024)。

杜紅樂(1979—)，男，碩士，講師，主要研究方向?yàn)榫W(wǎng)絡(luò)安全、機(jī)器學(xué)習(xí)。

TP181

A

1673-159X(2015)05-0016-08

10.3969/j.issn.1673-159X.2015.05.003