不均衡數(shù)據(jù)混合取樣分類算法

杜紅樂，張 燕（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

不均衡數(shù)據(jù)混合取樣分類算法

杜紅樂?，張 燕
（商洛學(xué)院數(shù)學(xué)與計(jì)算機(jī)應(yīng)用學(xué)院，陜西商洛726000）

摘 要：針對(duì)不均衡數(shù)據(jù)分類決策面偏移導(dǎo)致少數(shù)類識(shí)別率較低的問題，提出一種混合取樣算法。首先計(jì)算類樣本數(shù)的比值K；然后分別在多數(shù)類和少數(shù)類中隨機(jī)選取一個(gè)樣本，計(jì)算該樣本的K－1近鄰，以K個(gè)樣本的中心作為新樣本；再對(duì)剩余的樣本重復(fù)上面操作，直到所有樣本都被處理；最后所得新樣本與原少數(shù)類樣本共同構(gòu)成新的訓(xùn)練集。該算法在改變樣本密度的同時(shí)保持了原樣本的空間分布，實(shí)驗(yàn)結(jié)果表明該算法能夠提高SVM在不均衡數(shù)據(jù)下的分類性能，尤其是少數(shù)類的分類性能。

關(guān)鍵詞：支持向量機(jī)；過取樣；不均衡數(shù)據(jù)集；欠取樣；K近鄰

0　引言

支持向量機(jī)（Support Vector Machine，SVM）是在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的一種新的機(jī)器學(xué)習(xí)方法，它基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，在解決小樣本、非線性及高維模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢。近年來，SVM是機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)研究熱點(diǎn)，在許多領(lǐng)域都取得廣泛的應(yīng)用。

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

文獻(xiàn)［4?9］都采用聚類算法對(duì)數(shù)據(jù)集進(jìn)行相應(yīng)處理，文獻(xiàn)［5］利用K?Means算法對(duì)多數(shù)類樣本進(jìn)行聚類并提取類中心，得到與少數(shù)類樣本數(shù)量相當(dāng)?shù)臉颖局貥?gòu)新的訓(xùn)練集，為了避免少數(shù)類樣本過少導(dǎo)致最終訓(xùn)練樣本過度稀疏，對(duì)少數(shù)類樣本采用SMOTE算法進(jìn)行過取樣；文獻(xiàn)［6］為提高泛化能力，聚類在核空間中進(jìn)行，并利用AdaBoost集成手段對(duì)該欠取樣算法進(jìn)行集成；文獻(xiàn)［7］引入“聚類一致性系數(shù)”找出處于少數(shù)類邊界區(qū)域和處于多數(shù)類中心區(qū)域的樣本，然后用SMOTE對(duì)少數(shù)類樣本進(jìn)行過取樣，用改進(jìn)的隨機(jī)欠取樣對(duì)多數(shù)類樣本進(jìn)行處理；文獻(xiàn)［8］利用譜聚類的優(yōu)點(diǎn)對(duì)多數(shù)類樣本在核空間中進(jìn)行譜聚類，然后依據(jù)聚類大小和聚類與少數(shù)樣本間的距離選擇有代表性的信息點(diǎn)。以上方法要么用聚類方法，要么經(jīng)過聚類再進(jìn)一步進(jìn)行欠取樣和過取樣，但導(dǎo)致分類超平面偏移主要原因是兩類中樣本密度差異，數(shù)據(jù)集的均衡化處理實(shí)際就是在多數(shù)類和少數(shù)類樣本空間中密度分布的均衡化，而影響分類超平面走勢的是樣本空間分布，而聚類算法在改變樣本密度同時(shí)會(huì)改變樣本的空間分布。

基于以上分析，結(jié)合聚類算法和K近鄰算法，本文給出一種基于核空間的K近鄰變形算法，并將其應(yīng)用于不均衡數(shù)據(jù)分類中，該算法首先計(jì)算多數(shù)類樣本數(shù)與少數(shù)類樣本數(shù)的比值K；然后對(duì)多數(shù)類隨機(jī)選取一個(gè)樣本p并計(jì)算其K－1個(gè)近鄰樣本，用K個(gè)樣本的中心取代上面K個(gè)樣本；重復(fù)以上過程直到所有樣本都被處理；對(duì)于少數(shù)類樣本用K個(gè)近鄰的中心加入原少數(shù)類樣本中，最終重構(gòu)新的數(shù)據(jù)訓(xùn)練集。該算法不僅保持樣本在原樣本的空間分布，而且對(duì)不均衡數(shù)據(jù)進(jìn)行均衡化處理，仿真實(shí)驗(yàn)表明該方法較好地避免了不均衡數(shù)據(jù)集導(dǎo)致分類決策面偏移的問題，提高了分類器的分類準(zhǔn)確率，特別是對(duì)少數(shù)類樣本的分類準(zhǔn)確率。

1　支持向量機(jī)

1.1SVM算法

訓(xùn)練SVM的過程實(shí)質(zhì)就是求解最優(yōu)分類超平面問題，即要保證正確分類的最小錯(cuò)誤率，又要保證最大化分類間隔。給定一個(gè)樣本集T＝｛（x1，y1），（x2，y2），…，（xl，yl）｝，xi∈Rn，yi∈｛1，－1｝。SVM的主要目的是構(gòu)造一個(gè)分類超平面以分割兩類不同的樣本，使得分類間隔最大，同時(shí)錯(cuò)誤率最小，通過求解下面二次優(yōu)化問題，得到?jīng)Q策函數(shù)。

通過引入Lagrange算子可以得到問題（1）的對(duì)偶問題：其中，K（xi，xj）為核函數(shù)，K（xi，xj）＝〈?（xi），?（xj）〉，是采用非線性映射φ：Rn｜→F將訓(xùn)練樣本從輸入空間映射到某一特征空間，在該特征空間中樣本是線性可分的。最后可以得到?jīng)Q策函數(shù)為

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

圖1　樣本比例100∶100分類超平面Fig.1　Classification decision surface of proportion of the sample 100∶100

1.2不均衡數(shù)據(jù)對(duì)SVM的影響

不均衡數(shù)據(jù)（Imbalanced Data，ID）指的是同一數(shù)據(jù)集中某些類的樣本數(shù)量比其他類的樣本數(shù)量多的多，其中樣本數(shù)量多的類稱為多數(shù)類，樣本數(shù)量少的類稱為少數(shù)類。通常如果目標(biāo)類在數(shù)據(jù)集中所占比例非常小（通常遠(yuǎn)低于10%）就稱為稀有類。所謂不均衡分類問題指的是對(duì)這些不平衡數(shù)據(jù)進(jìn)行分類時(shí)，傳統(tǒng)的分類方法傾向于對(duì)多數(shù)類有較高的識(shí)別率，對(duì)少數(shù)類的識(shí)別率卻很低的問題。

為觀察不均衡數(shù)據(jù)對(duì)分類決策面的影響，隨機(jī)產(chǎn)生兩類均勻分布的樣本，第一類樣本為U（［0，1］×［0，1］），第二類樣本為U（［0，1］×［1，2］），第一類樣本數(shù)為200，第二類樣本數(shù)為20，經(jīng)支持向量機(jī)訓(xùn)練最終的分類決策面如圖2所示，其中0號(hào)線為分類超平面。

由圖1和圖2可以看出數(shù)據(jù)不均衡的情況下，分類超平面向少數(shù)類樣本側(cè)移動(dòng)，如圖2中，分類超平面向少數(shù)類方向偏移，導(dǎo)致對(duì)多數(shù)類的過學(xué)習(xí)。這是因?yàn)橹С窒蛄繖C(jī)在訓(xùn)練的時(shí)候認(rèn)為兩類樣本錯(cuò)分造成的損失相同，即采用了相同的懲罰因子。支持向量機(jī)為了使分類間隔盡可能的大，同時(shí)保證分類錯(cuò)誤率盡可能的小，因此分類超平面會(huì)向少數(shù)類樣本方向偏移，最終導(dǎo)致對(duì)少數(shù)類樣本分類錯(cuò)誤率較高。針對(duì)此，文獻(xiàn)［13］提出了對(duì)兩個(gè)類采用不同的懲罰因子，為體現(xiàn)對(duì)少數(shù)類的重視，對(duì)少數(shù)類采用較大的懲罰因子，而對(duì)多數(shù)類采用較小的懲罰因子，一方面對(duì)于不同的訓(xùn)練數(shù)據(jù)懲罰因子確定困難，另一方面，數(shù)據(jù)不均衡問題根本原因在于樣本密度不均衡性，在圖2中表現(xiàn)為多數(shù)類和少數(shù)類在兩個(gè)區(qū)域中的樣本密度不同，因此提高少數(shù)類樣本的分類準(zhǔn)確率從樣本的均衡化入手，使得分類超平面不會(huì)向少數(shù)類方向偏移。圖3為圖2中數(shù)據(jù)把原來邊界樣本刪除，但分類邊界樣本密度不改變情況下的分類超平面示意圖。由此可以看到，若只改變樣本數(shù)量而不改變樣本密度，則不會(huì)改變分類超平面的位置，因此重取樣需要保持樣本原有的分布同時(shí)改變樣本密度。

圖2　樣本比例200∶20時(shí)的分類超平面Fig.2　Classification decision surface of proportion of the sample 200∶20

圖3　樣本密度不改變的分類超平面Fig.3　Classification decision surface of invariant density of the sample

2　重取樣算法

本算法首先依據(jù)多數(shù)類樣本和少數(shù)類樣本數(shù)量比值確定K值，然后對(duì)多數(shù)類隨機(jī)取一個(gè)樣本p 的K－1個(gè)近鄰，然后利用這K個(gè)樣本的平均值取代該樣本，然后計(jì)算樣本p最遠(yuǎn)的樣本的K－1個(gè)近鄰，重復(fù)以上過程構(gòu)造新的平衡數(shù)據(jù)集，該方法可以保持樣本原來的密度分布，同時(shí)可以對(duì)不均衡訓(xùn)練數(shù)據(jù)進(jìn)行均衡化，避免直接使用不均衡數(shù)據(jù)集導(dǎo)致對(duì)多數(shù)類過擬合現(xiàn)象。

算法1 欠取樣算法

算法2 過取樣算法

算法1得到的數(shù)據(jù)集CB和算法2得到的數(shù)據(jù)集CS合并得到新的訓(xùn)練集。算法1和算法2都是利用K近鄰進(jìn)行數(shù)據(jù)處理，具體處理過程如下：

1）計(jì)算樣本之間的距離矩陣

2）任意選擇一行，記錄該行中最小的K個(gè)值對(duì)應(yīng)的列號(hào)，然后計(jì)算對(duì)應(yīng)編號(hào)的數(shù)據(jù)的平均值；

3）刪除上面列號(hào)對(duì)應(yīng)的行和列，若行數(shù)小于K，則計(jì)算剩余編號(hào)對(duì)應(yīng)的數(shù)據(jù)的平均值；否則重復(fù)執(zhí)行（2）。

計(jì)算距離采用特征空間中的距離，本文中核函數(shù)選擇RBF進(jìn)行空間轉(zhuǎn)換。算法1和算法2都能夠更準(zhǔn)確的保持?jǐn)?shù)據(jù)集原來的樣本分布，對(duì)于少數(shù)類樣本能夠較充分的包含該類樣本信息時(shí)可以只選擇算法1對(duì)多數(shù)類樣本進(jìn)行欠取樣，對(duì)于多數(shù)類樣本如果已經(jīng)不能再精簡的情況下可以只選擇算法2對(duì)少數(shù)類樣本進(jìn)行過取樣，在大多數(shù)情況下結(jié)合使用算法1和算法2。

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í)間進(jìn)行比較，對(duì)比分類時(shí)間及總體分類性能上的效果。

本文中所做實(shí)驗(yàn)是在Matlab 7.11.0環(huán)境下，結(jié)合臺(tái)灣林智仁老師的LIBSVM［14］，CPU為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é)者［15］給出了針對(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ù)量。假設(shè)正類為多數(shù)類，則由此得少數(shù)類正確分類率為

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

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

Pr＝TN/（FP＋TN），（6）則Fv和Gm定義如下：其中，λ為Pr與Re的相對(duì)重要性。Fv綜合考慮少數(shù)類樣本的準(zhǔn)確率和查準(zhǔn)率，因此能夠更準(zhǔn)確的反映對(duì)少數(shù)類樣本的分類性能；而Gm綜合考慮多數(shù)類和少數(shù)類樣本的分類準(zhǔn)確率，因此能夠衡量分類器的整體分類性能。本文實(shí)驗(yàn)中使用這兩個(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)生兩類均勻分布的不均衡樣本，第一類樣本為U（［0，1］×［0，1］），第二類樣本為U（［0，1］×［1，2］），第一類樣本數(shù)為200，第二類樣本數(shù)為20。測試集同樣采用均衡分布的人工數(shù)據(jù)第一類樣本為U（［0，1］×［0，1］），第二類樣本為U（［0，1］×［1，2］），兩類樣本各100個(gè)樣本。

由于上面數(shù)據(jù)集是隨機(jī)生成的，具有一定的偶然性，因此實(shí)驗(yàn)給出5次測試結(jié)果及平均值。表1給出了5次隨機(jī)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果，其中核函數(shù)采用徑向基核函數(shù)。

從表1中可以看到，本文算法的Fv和Gm3次結(jié)果比聚類算法結(jié)果要好，有一次同聚類算法的結(jié)果相同，有一次比聚類算法的結(jié)果稍差，但是所有都比直接采用SVM算法要好，從5次的平均值可以看到該算法略優(yōu)于聚類算法，明顯優(yōu)于直接采用SVM算法。圖4和圖5是圖2中不均衡數(shù)據(jù)集經(jīng)聚類算法和本文算法進(jìn)行相應(yīng)處理后，用SVM進(jìn)行訓(xùn)練得到的分類超平面圖，可以看到分類超平面明顯向多數(shù)類傾斜，傾斜程度可以通過K值進(jìn)行控制。從圖中可以看到本文算法較好的保持了原樣本的空間分布，因此該算法比聚類算法和直接用SVM算法實(shí)驗(yàn)效果好。

表1　實(shí)驗(yàn)結(jié)果對(duì)比（一）Tab.1　Comparison of experimental results（1）

圖4　聚類算法的分類超平面Fig.4　Classification figure of clustering algorithm

圖5　本文算法的分類超平面Fig.5　Classification figure of the proposed algorithm

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

其中，第一類樣本的半徑是均勻分布ρ∈［0，5］，第二類樣本的半徑是均勻分布ρ∈［5，10］，第一類樣本數(shù)為200個(gè)，第二類樣本數(shù)為20，作為訓(xùn)練樣本；測試樣本集數(shù)量為200，兩類各100個(gè)樣本。這里選擇徑向基核函數(shù)K（x，y）＝exp（－g‖x－y‖2）。與3.2.1節(jié)相同，實(shí)驗(yàn)同樣給出5次測試結(jié)果及平均值，表2給出了5次隨機(jī)數(shù)據(jù)的實(shí)驗(yàn)結(jié)果，其中核函數(shù)仍然采用徑向基核函數(shù)。從表2中可以看到，5次實(shí)驗(yàn)結(jié)果中本文算法都優(yōu)于聚類算法和直接SVM算法，尤其是在第4次中，本文算法的Fv和Gm都達(dá)到到100%。對(duì)比表1和表2，表2中本文算法和聚類算法的性能指標(biāo)要優(yōu)于表1，原因在于該數(shù)據(jù)集的樣本空間要比表1中對(duì)應(yīng)樣本空間要大，因此樣本分布在邊界附近的概率就小，因此各項(xiàng)指標(biāo)優(yōu)于表1。

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

本實(shí)驗(yàn)數(shù)據(jù)集采選取Contraceptive Method Choice（Cmc）、Haberman′s survival、Ionosphere、Letter Recognition和Pima Indians Diabetes5組UCI數(shù)據(jù)，這5組實(shí)驗(yàn)數(shù)據(jù)屬性都為實(shí)數(shù)，并且類樣本間有不同程度的不均衡性，本實(shí)驗(yàn)中多數(shù)類樣本為正類，少數(shù)類樣本為負(fù)類。由表3可以看出，多數(shù)類和少數(shù)類各組數(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ù)類。

表4給出了在數(shù)據(jù)集Cmc、Haberman′ssurvival、Ionosphere、Letter Recognition和Pima上的實(shí)驗(yàn)結(jié)果，本文算法在數(shù)據(jù)集pima和Ionosphere上實(shí)驗(yàn)效果比聚類算法差，而在其余數(shù)據(jù)集上算法優(yōu)于聚類算法，原因在于本文算法若K＝1則相當(dāng)于數(shù)據(jù)集未被改變，不均衡問題仍然存在；若K＝2相當(dāng)于把多數(shù)類樣本減少一半，結(jié)果是原來的多數(shù)類變?yōu)樯贁?shù)類，原來的少數(shù)類變?yōu)槎鄶?shù)類，構(gòu)成新的不均衡數(shù)據(jù)。而對(duì)于比值較大的Cmc、Haberman′s survival和Letter Recognition數(shù)據(jù)集有較好的實(shí)驗(yàn)效果。

表2　實(shí)驗(yàn)結(jié)果對(duì)比（二）Tab.2 Comparison of experimental results（2）

表3　實(shí)驗(yàn)數(shù)據(jù)集Tab.3 Experimental datasets

表4　實(shí)驗(yàn)結(jié)果對(duì)比（三）Tab.4 Comparison of experimental results（3）

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

本文算法計(jì)算K近鄰，實(shí)際用的是距離自身K－1個(gè)最近樣本，因此如果K＝1，就相當(dāng)于沒有對(duì)樣本進(jìn)行處理，樣本數(shù)量不變，分布不變；若K值過大就是整個(gè)多數(shù)類樣本變?yōu)橐粋€(gè)樣本，因此K值決定樣本的縮減規(guī)模和增加規(guī)模。為了更直觀的看到K值的影響，該節(jié)選用3.2.1節(jié)中的數(shù)據(jù)集，不同K值對(duì)應(yīng)的結(jié)果如表5所示。由表5可以看出，隨著K值的增加，分類性能越來越好，尤其是對(duì)少數(shù)類，但是當(dāng)K值為30、50、100的時(shí)候分類性能再次下降，原因在于K值過大導(dǎo)致出現(xiàn)新的不均衡。

表5　K值的影響Tab.5 Effect of K values

4　結(jié)束語

針對(duì)實(shí)際應(yīng)用中訓(xùn)練樣本不均衡的問題，主要表現(xiàn)為密度分布不均衡，結(jié)合聚類算法本文提出基于K近鄰算法的欠取樣SVM分類算法。該方法用K近鄰算法對(duì)多數(shù)類進(jìn)行欠取樣和對(duì)少數(shù)類樣本過取樣，然后得到新的訓(xùn)練集并最終得到分類超平面。該方法進(jìn)行重取樣后能夠保持原樣本的密度分布，并且達(dá)到樣本的均衡化處理，最后用人工數(shù)據(jù)集和UCI數(shù)據(jù)集進(jìn)行驗(yàn)證該方法的有效性。通過與聚類算法及直接用SVM算法進(jìn)行比較，結(jié)果表明在不同的數(shù)據(jù)集及不同的不均衡化程度下，本文方法有較好的實(shí)驗(yàn)效果。然而所有實(shí)驗(yàn)均在2類分類上進(jìn)行，如何實(shí)現(xiàn)在多類不均衡數(shù)據(jù)集下實(shí)現(xiàn)數(shù)據(jù)集的均衡化將是下一階段的主要工作。

參考文獻(xià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 .Interna? tional 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 S 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 1775.

［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］CHANG C C LIN C J.LIBSVM a library for support vector ma?chines EB/OL .http //www.csie.ntu.edu.tw/～cjlin/libsvm

［15］SU C T CHEN L S.Knowledge acquisition through information granulation for imbalanced data J .Expert Systems with Applica?tions 2006 31 3 531?541.

A classification algorithm based on mixed sampling for imbalanced dataset

DU Hong?le，ZHANG Yan
（School of Mathematics and Computer Application，Shangluo University，Shangluo，Shaanxi 726000，China）

Abstract：In order to solve the problem of the lower accuracy of minority class caused by classification hyper plane shifting，a mixed sampling algorithm for imbalanced data classification is proposed.First，the ratio of the numbers of majority class and minority class，K is calculated.Then，a sample is chosen randomly from majority class and minority class，and K－1 nearest neighbors of the sample are calculated，the center of above K samples is taken as a new sample.Above processing is repeated until all samples are processed.The new generated samples and original minority class are put together as a new training dataset.At the same time，the sample den?sity is changed and the sample distribution in the feature space is kept.Experiment results show this proposed algorithm can improve the classification performance of SVM for imbalanced dataset，especially for the minority class.

Key words：support vector machine；over?sampling；imbalanced dataset；under?sampling；K?nearest neighbor

作者簡介：?杜紅樂（1979?），男，河南洛陽人，碩士，講師，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘，Email：dhl5597＠126.com。

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

收稿日期：2014?12?22

文章編號(hào)：1007?791X（2015）02?0158?07

DOI：10.3969/j.issn.1007?791X.2015.02.010

文獻(xiàn)標(biāo)識(shí)碼：A

中圖分類號(hào)：TP301.6