基于二次SVM的不均衡數(shù)據(jù)算法

張燕

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

基于二次SVM的不均衡數(shù)據(jù)算法

張燕

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

為減少不均衡數(shù)據(jù)對(duì)支持向量機(jī)分類性能的影響，提出一種基于二次支持向量機(jī)的欠取樣分類算法，該算法依據(jù)樣本的分類超平面貢獻(xiàn)大小對(duì)多數(shù)類樣本進(jìn)行欠取樣，并對(duì)少數(shù)類樣本進(jìn)行過取樣，重構(gòu)訓(xùn)練數(shù)據(jù)集。該算法能夠刪除樣本中的噪聲數(shù)據(jù)，用控制參數(shù)控制刪除樣本的規(guī)模，實(shí)驗(yàn)表明，該算法能夠提高支持向量機(jī)在不均衡數(shù)據(jù)集下的分類性能。

支持向量機(jī)；不均衡數(shù)據(jù)；欠取樣；分類超平面

支持向量機(jī)(Support Vector Machine，簡(jiǎn)稱SVM)[1]是在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上發(fā)展起來的一種新的機(jī)器學(xué)習(xí)方法，它基于結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則，在解決小樣本、非線性及高維模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢(shì)。傳統(tǒng)SVM在均衡訓(xùn)練樣本下有較好的分類性能，然而在樣本數(shù)量不均衡的情況下SVM對(duì)多數(shù)類樣本的過于擬合，而對(duì)少數(shù)類樣本則是欠學(xué)習(xí)。均衡化方法可以分為兩類：數(shù)據(jù)層面的方法和算法層面的方法。數(shù)據(jù)層面的方法主要是通過一定策略刪除多數(shù)類的樣本或者增加少數(shù)類的樣本使數(shù)據(jù)集均衡化，進(jìn)而提高分類器在不均衡數(shù)據(jù)集下的分類性能，常采用的方法有過采樣[3-7]和欠采樣[8-13]。算法層面的方法主要有代價(jià)敏感學(xué)習(xí)、核方法、集成方法如boosting等。

楊智明等[10]在核空間中對(duì)多數(shù)類樣本進(jìn)行譜聚類，然后依據(jù)聚類大小及聚類與少數(shù)類樣本間的距離選擇有代表性的樣本；陶新民等[11]利用模糊樣本修剪技術(shù)計(jì)算邊界樣本隸屬度概率，還利用基于無監(jiān)督學(xué)習(xí)方法的指導(dǎo)型欠采樣技術(shù)減少欠采樣時(shí)分類信息丟失的問題；吳磊等[12]、金鑫等[13]融合欠采樣技術(shù)和過采樣技術(shù)，避免過度欠采樣導(dǎo)致分類信息丟失。以上欠采樣方法中，都是為了減少樣本修剪的過程中分類信息丟失，在一定程度上減少了信息的丟失，但仍會(huì)造成部分分類信息的丟失。然而在支持向量機(jī)中影響最終決策函數(shù)的是由支持向量所決定的分類超平面，而遠(yuǎn)離超平面的樣本對(duì)決策函數(shù)影響較小，甚至沒有影響；而過采樣將增加訓(xùn)練集的規(guī)模，也會(huì)大大增加訓(xùn)練時(shí)間，基于以上分析，本文提出一種基于二次支持向量機(jī)（Double Support Vector Machine，DSVM）決策函數(shù)特點(diǎn)不均衡數(shù)據(jù)分類算法，該算法依據(jù)樣本對(duì)構(gòu)建分類超平面的貢獻(xiàn)大小進(jìn)行修剪，同時(shí)利用控制參數(shù)控制刪除樣本的比例，較好地實(shí)現(xiàn)不均衡數(shù)的均衡化處理，仿真實(shí)驗(yàn)表明該方法較好地解決了不均衡數(shù)據(jù)的分類，提高了分類準(zhǔn)確率，特別是少數(shù)類樣本的分類準(zhǔn)確率。

1 支持向量機(jī)

1.1 SVM算法

訓(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ò)誤率最小，可以通過求解(1)式二次優(yōu)化問題，得到?jīng)Q策函數(shù)。

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

其中K(xi，yi)為核函數(shù)，K(xi，yi)=〈φ(xi)，φ(xj)〉，是采用非線性映射φ:Rk|→F將訓(xùn)練樣本從輸入空間映射到某一特征空間，在該特征空間中樣本是線性可分的。最后可以得到?jīng)Q策函數(shù)為：

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

圖1 樣本比例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ù)集中所占比例非常?。ㄍǔ＿h(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所示，其中線條為分類超平面。

圖2 樣本比例是200：20的決策面

由圖1和圖2可以看出，樣本不均衡的情況下，分類超平面向少數(shù)類樣本側(cè)移動(dòng)。這是因?yàn)橹С窒蛄繖C(jī)在訓(xùn)練時(shí)認(rèn)為兩類樣本錯(cuò)分造成的損失相同，即采用相同的懲罰因子。支持向量機(jī)為使分類間隔盡可能的大，同時(shí)保證分類錯(cuò)誤率盡可能的小，因此分類超平面會(huì)向少數(shù)類樣本方向偏移，最終導(dǎo)致對(duì)少數(shù)類樣本分類錯(cuò)誤率較高。對(duì)此，文獻(xiàn)[14]提出對(duì)兩個(gè)類采用不同的懲罰因子，為體現(xiàn)對(duì)少數(shù)類的重視，對(duì)少數(shù)類采用較大的懲罰因子，而對(duì)多數(shù)類采用較小的懲罰因子，但數(shù)據(jù)不均衡問題根本原因在于樣本數(shù)量不均衡性，即提高少數(shù)類樣本的分類準(zhǔn)確率從樣本的均衡化入手，使得分類超平面不會(huì)向少數(shù)類方向偏移。

1.3 點(diǎn)到超平面的距離

從圖1可以看出，對(duì)分類結(jié)果有影響的是靠近分類邊界的樣本，而遠(yuǎn)離分類邊界的樣本對(duì)分類結(jié)果沒什么影響，為了描述樣本對(duì)最終的分類器的影響大小，定義點(diǎn)到分類超平面的距離。

定義1樣本x到分類超平面的距離：

其中x0為樣本x在超平面上的投影，w為超平面的法向量，||w||表示w的二階范數(shù)，如圖3所示。

圖3 點(diǎn)到超平面距離

對(duì)式(4)進(jìn)行變形為：

由于x0是分類超平面上點(diǎn)，因此滿足f(x0)= wx0+b=0，代入式(5)得

〈xi，x〉表示xi與x的內(nèi)積。

對(duì)于線性不可分問題，樣本x到分類超平面的距離為：

K(xi，x)是核函數(shù)，K(xi，yi)=〈φ(xi)，φ(xj)〉。

樣本x到分類超平面的距離d(x)的值可以是正也可以是負(fù)，d(x)為正數(shù)表示樣本與類中心在分類超平面同側(cè)，負(fù)數(shù)表示樣本與類中心在分類超平面的相反側(cè)，對(duì)于多數(shù)類樣本若d(x)為負(fù)數(shù)則認(rèn)為樣本為噪聲數(shù)據(jù)。

定義2類到分類超平面的距離D(ci)為類ci到分類超平面距離：

對(duì)于多數(shù)類，ni為屬于類ci，且d(x)≥0的樣本數(shù)；對(duì)于少數(shù)類ni為屬于類ci的全部樣本數(shù)量。

2 DSVM欠取樣算法

在多數(shù)類樣本中存在大量的重復(fù)信息或?qū)Ψ诸悷o幫助的信息（如遠(yuǎn)離分類超平面的樣本），這些冗余信息導(dǎo)致訓(xùn)練樣本的不均衡性，進(jìn)而導(dǎo)致分離器最終的分類性能。因此一種常用的方法就是通過一定的策略刪除這些冗余信息，即欠采樣方法，如DROP、CNN、聚類等算法，但這些方法在刪除冗余信息的同時(shí)也會(huì)刪除一些邊界樣本，本文提出基于樣本到分類超平面距離的欠取樣算法，算法過程描述如下：

Step 1針對(duì)訓(xùn)練數(shù)據(jù)集T用支持向量機(jī)進(jìn)行訓(xùn)練，得到分類超平面f(x)，法向量w，支持向量集合SV及每個(gè)支持向量對(duì)應(yīng)系數(shù)ai；

Step 2依據(jù)式(7)或者式(8)（線性可分問題用式(7)，線性不可分問題用式(8)計(jì)算樣本到分類超平面的距離d(xj)；

Step 3根據(jù)式(9)計(jì)算類到分類超平面的距離D(ci)；

Step 4對(duì)于多數(shù)類樣本，依據(jù)給定的控制參數(shù)a值刪除d(x)＞a*D(ci)的樣本點(diǎn)，得到新的訓(xùn)練集T′；

Step 5對(duì)T′進(jìn)行訓(xùn)練，如果分類效果達(dá)到理想狀態(tài)，則得到最終的分類超平面和決策函數(shù)；否則，重新設(shè)定控制參數(shù)a，返回setp 4。

Step 6對(duì)新的少數(shù)類樣本有插值法，增加樣本；

控制參數(shù)a用來控制刪除多數(shù)類樣本的比例，其值依據(jù)少數(shù)類樣本數(shù)量與多數(shù)類樣本數(shù)量比值來確定，即，其中ni少數(shù)類樣本數(shù)量，nj為多數(shù)類樣本數(shù)量，k為常數(shù)。

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

3.1 實(shí)驗(yàn)數(shù)據(jù)選擇

為簡(jiǎn)化過程本文實(shí)驗(yàn)數(shù)據(jù)采用人工生成方式，為觀察不均衡數(shù)據(jù)對(duì)分類決策面的影響，隨機(jī)產(chǎn)生兩類均勻分布的不均衡樣本，第一類樣本為U([0，1]×[0，1]數(shù)量是200，第二類樣本為U([0，1]×[1，2]數(shù)量是20。測(cè)試集同樣采用均衡分布的人工數(shù)據(jù)第一類樣本為U([0，1]×[0，1]，第二類樣本為U([0，1]×[1，2]，兩類樣本各50個(gè)樣本。

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

由于上面數(shù)據(jù)集是隨機(jī)生成的，具有一定的偶然性，因此實(shí)驗(yàn)采用10次測(cè)試其結(jié)果。表1給出了10次實(shí)驗(yàn)不同的控制參數(shù)的實(shí)驗(yàn)結(jié)果,其中核函數(shù)采用多項(xiàng)式核函數(shù)，表1中數(shù)字為測(cè)試的準(zhǔn)確率。

表1 DSVM與SVM的實(shí)驗(yàn)結(jié)果對(duì)比

從表1可以看到，隨著K值的減小，多數(shù)類樣本的數(shù)量也減少，在極限情況下（K=0時(shí)），問題轉(zhuǎn)化為一類問題，導(dǎo)致多類樣本信息丟失，分類準(zhǔn)確率反而會(huì)下降，如表1中，K=3時(shí)，10次中就有兩次準(zhǔn)確率反而下降。圖5是圖4中相同數(shù)據(jù)經(jīng)處理后的分類超平面分布的圖，可以看到分類超平面向多數(shù)類傾斜。

圖4 原始分類圖

4 結(jié)論

針對(duì)實(shí)際應(yīng)用中訓(xùn)練樣本不均衡的問題，本文根據(jù)支持向量機(jī)的特點(diǎn)，刪除距離分類邊界比較遠(yuǎn)的樣本，同時(shí)對(duì)少數(shù)類樣本利用SMOTE進(jìn)行過取樣，從一定程度上減少訓(xùn)練數(shù)據(jù)的不均衡程度，提高了分類準(zhǔn)確率。但沒有能從根本上解決不均衡數(shù)據(jù)集因?yàn)榉诸惓矫娴钠贫鴮?dǎo)致分類準(zhǔn)確率低的問題，因此如何提取邊界樣本中有用信息，使得分類超平面向多數(shù)類方向偏移將是下階段的主要工作。

圖5 DSVM下的分類圖

[1]Vapnik V.The nature of statistical learning theory[M]. NewYokr:Springer-verlag,1995.

[2]Wang B X,Japkowicz N.Boosting support vector machines for imbalanced datasets[J].Lecture Notes in Computer Science,2008,4994:38-47.

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

[4]李 鵬,王曉龍,劉遠(yuǎn)超.一種基于混合策略的失衡數(shù)據(jù)集分類方法[J].電子學(xué)報(bào),2007,35(11):2161-2165.

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

[6]He H,Garcia E A.Learning from imbalanced data[J]. IEEE Transactions on Knowledge and Data Engineering, 2009,21(9):1263-1284.

[7]Chen B,Ma L,Hu J.An improved multi-label classification method based on SVMwith delicate decision boundary[J].International Journal of Innovative Computing,Information and Control,2010,6(4):1605-1614.

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

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

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

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

[12]吳 磊,房 斌,刁麗萍,等.融合過抽樣和欠抽樣的不平衡數(shù)據(jù)重抽樣方法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49 (21):173-176,185.

[13]金 鑫,李玉鑒.不平衡支持向量機(jī)的懲罰因子選擇方法[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(33):129-133.

（責(zé)任編輯：李堆淑）

An Algorithm for Imbalanced Dataset Based on Double SVM

ZHANG Yan
（College of Mathematics and Computer Application,Shangluo University,Shangluo 726000,Shaanxi)

In order to reduce the effect of imbalanced datacet on SVMclassification performance,a newunder-sampling algorithm based on the twice support vector machine is proposed for imbalanced data classification.For samples of majority class,this algorithm deletes the samples far from the classification hyperplane.And for samples of minority class,this algorithm use over-sampling algorithm to add newsamples.The method may resolve the problem of imbalanced dataset and improve the classification performance of SVM.Experiment results with artificial dataset showthe algorithm is effective for imbalanced dataset,especially for the minority class samples.

Support Vector Machine;imbalanced dataset;under-sampling;classification hyperplane

TP181

：A

：1674-0033（2014）04-0038-04

10.13440/j.slxy.1674-0033.2014.04.009

2014-03-21

商洛學(xué)院科研基金項(xiàng)目（13SKY024）；商洛學(xué)院教育教學(xué)改革研究項(xiàng)目（10JYJX02011）

張 燕，女，陜西丹鳳人，碩士，助教