李村合,姜 宇,李 帥

(中國(guó)石油大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,青島 266580)

支持向量機(jī)是常見(jiàn)的一種基于統(tǒng)計(jì)學(xué)習(xí)理論的分類算法,核心是結(jié)構(gòu)風(fēng)險(xiǎn)最小化和VC 維理論.其主旨是在高維空間中尋找一個(gè)最優(yōu)分類面,將樣本正確分類且保證分類間隔最大化[1].隨著人工智能時(shí)代的到來(lái),支持向量機(jī)成功應(yīng)用至許多方面,尤其是在分類問(wèn)題的解決上已經(jīng)成為了主流方法,如網(wǎng)頁(yè)分類[2],手寫(xiě)識(shí)別[3]等.

但在實(shí)際生活及現(xiàn)實(shí)應(yīng)用中,許多常見(jiàn)的數(shù)據(jù)往往具有極大的不平衡性,如缺陷數(shù)據(jù)[4],文本數(shù)據(jù)[5]、疾病數(shù)據(jù)[6]等.當(dāng)利用支持向量機(jī)處理不平衡數(shù)據(jù)時(shí),往往會(huì)出現(xiàn)分類結(jié)果具有一定傾向性的現(xiàn)象,即分類器對(duì)多數(shù)類的分類準(zhǔn)確度較高,而對(duì)少數(shù)類的分類準(zhǔn)確度較低.另外超平面的位置對(duì)支持向量機(jī)的性能有很大的影響,并且超平面的確定極易受樣本中噪點(diǎn)的影響[7].所以為了解決上述問(wèn)題,提高支持向量機(jī)的分類性能成為眾多學(xué)者亟待解決的問(wèn)題[8].

在支持向量機(jī)的決策過(guò)程中,決策面位置的選取取決于樣本空間的分布.由于不平衡數(shù)據(jù)集的類不平衡性較大,許多樣本點(diǎn)對(duì)決策面的確定貢獻(xiàn)度不大,容易識(shí)別為噪聲并對(duì)分類器的性能造成影響.模糊向量機(jī)可以改善噪聲數(shù)據(jù)造成的分類精度下降現(xiàn)象,通過(guò)為樣本點(diǎn)賦予不同的隸屬度來(lái)確定樣本點(diǎn)的性質(zhì).但傳統(tǒng)的模糊支持向量機(jī)在確定樣本隸屬度時(shí),僅考慮了類內(nèi)距離,應(yīng)用于不平衡數(shù)據(jù)集分類時(shí)容易出現(xiàn)較大誤差[9].故本文提出一種應(yīng)用不等距超平面距離的改進(jìn)模糊支持向量機(jī).文中將樣本數(shù)量多的類規(guī)定為正類,將樣本數(shù)量少的類規(guī)定為負(fù)類.通過(guò)向標(biāo)準(zhǔn)模糊支持向量機(jī)中引入?yún)?shù) λ,以控制超平面與樣本之間的距離.在構(gòu)造隸屬度函數(shù)時(shí),不僅取決于樣本之間的距離,還考慮了樣本之間的互距離,更精準(zhǔn)的表示樣本分布,以減小不平衡的樣本分布給分類準(zhǔn)確度帶來(lái)的影響.

1 相關(guān)工作

在不平衡樣本集上進(jìn)行訓(xùn)練時(shí),相關(guān)的修改算法主要在兩個(gè)方面上進(jìn)行相關(guān)的改進(jìn),樣本數(shù)據(jù)上和訓(xùn)練算法上[10].在訓(xùn)練樣本數(shù)據(jù)上進(jìn)行的改進(jìn),主要有兩種方法,分別是增加負(fù)類樣本數(shù)量和減少正類樣本數(shù)量,如欠采樣和過(guò)采樣.但采樣方法容易造成分類模型在訓(xùn)練和測(cè)試過(guò)程中具有較大的誤差,無(wú)法獲得較準(zhǔn)確的分類結(jié)果.文獻(xiàn)[11,12]中解釋了減少正類樣本數(shù)量雖然可以改善數(shù)據(jù)的不平衡性,但會(huì)使樣本所含信息丟使,分類效果降低;文獻(xiàn)[13]證明了增加負(fù)樣本也會(huì)出現(xiàn)過(guò)擬合現(xiàn)象,令噪聲數(shù)據(jù)對(duì)模型分類準(zhǔn)確度的影響更顯著.

在用于不平衡數(shù)據(jù)分類的支持向量機(jī)訓(xùn)練算法中,不斷有學(xué)者提出改進(jìn)的算法.在文獻(xiàn)[14]中,算法引用補(bǔ)償因子以修正超平面的偏移量,利用支持向量的決策值估計(jì)補(bǔ)償因子的數(shù)值,文獻(xiàn)中所做的實(shí)驗(yàn)表明引用的補(bǔ)償因子,訓(xùn)練樣本離超平面的間隔可以在一定程度上得到正確的修正.但是,當(dāng)不平衡樣本集中正負(fù)類的訓(xùn)練樣本有很大的交叉區(qū)域和有噪音數(shù)據(jù)時(shí),算法的分類性能有很大的下降.在文獻(xiàn)[15]中,算法在支持向量機(jī)訓(xùn)練過(guò)程中的為正負(fù)類樣本分別設(shè)置了各自的懲罰因子,并將約束條件中加入新的參數(shù)控制分類間隔.將改進(jìn)的近似支持向量機(jī)應(yīng)用到不平衡樣本的分類,減小樣本數(shù)量對(duì)分類面的影響,提高了算法精度.但這種方法的改善效果受到KKT 條件的限制,KKT條件將懲罰參數(shù)作為其上限條件,而不是下限條件,同時(shí)尋找合適的懲罰參數(shù)是比較困難的.在文獻(xiàn)[16],算法對(duì)相關(guān)的核函數(shù)進(jìn)行修改并將其應(yīng)用于不平衡樣本集中,在黎曼幾何結(jié)構(gòu)上對(duì)核函數(shù)優(yōu)化,提高了不平衡數(shù)據(jù)的分類準(zhǔn)確率.在文獻(xiàn)[17–20]中,介紹了SVM相關(guān)的改進(jìn)算法,將其應(yīng)用于不平衡樣本,從各種方面使得負(fù)類樣本的分類結(jié)果得到優(yōu)化.

在文獻(xiàn)[21]中,介紹了模糊支持向量機(jī),它在處理分類和預(yù)測(cè)等現(xiàn)實(shí)問(wèn)題時(shí)表現(xiàn)出了十分出色的性能,相較支持向量機(jī)而言,它可以減輕噪聲數(shù)據(jù)對(duì)分類器性能的影響.隸屬度函數(shù)的確定影響著模糊支持向量機(jī)分類性能,已有許多算法應(yīng)用于解決隸屬度函數(shù)的選擇問(wèn)題,如聚類算法[22,23]、啟發(fā)式算法[24]等,但至今為止,模糊隸屬度函數(shù)的確立尚無(wú)系統(tǒng)的理論規(guī)定和準(zhǔn)則.

通過(guò)計(jì)算類內(nèi)距離確定樣本隸屬度,是構(gòu)造隸屬度函數(shù)的經(jīng)典方法.計(jì)算樣本到其類中心點(diǎn)的距離,若距離小則判定該樣本點(diǎn)屬于該類的可能性較大,為該其賦予一個(gè)較大的隸屬度值;若距離過(guò)大則判定該樣本點(diǎn)為噪聲數(shù)據(jù),并賦予該點(diǎn)一個(gè)較小的隸屬度值.以此作為樣本貢獻(xiàn)度的衡量指標(biāo),可能會(huì)令分類器對(duì)噪聲的辨識(shí)度降低[25],使分類器訓(xùn)練時(shí)誤差較大,降低分類器的分類精度和泛化性能.

2 不等距超平面距離改進(jìn)的模糊支持向量機(jī)(IFD-FSVM)

模糊支持向量機(jī)模型為:訓(xùn)練集為{(xi,yi,ui)|i=1,2,···,l},xi為樣本集,yi為樣本xi的標(biāo)簽且yi∈{+1,?1},ui為模糊隸屬度,反映了不同的類對(duì)分類面形成的貢獻(xiàn)度,參數(shù) εi為 松弛變量,參數(shù)C為懲罰參數(shù).通常將類到超平面之間的分類間隔成為超平面距離,利用支持向量機(jī)求解分類問(wèn)題的本質(zhì)就是使超平面距離最大化.

其數(shù)學(xué)模型用公式表示為:

不等式約束條件為:

式中,ω為決定超平面方向的法向量,b表示該決策面到坐標(biāo)軸原點(diǎn)的距離.

模糊支持向量機(jī)的決策函數(shù)為:

K(x,xi)為核函數(shù),常見(jiàn)的核函數(shù)有線性核函數(shù)、多項(xiàng)式核函數(shù)、高斯核函數(shù)等,在求解過(guò)程中核函數(shù)的選擇要視數(shù)據(jù)集性質(zhì)而定.

利用不等距超平面距離改進(jìn)后的模糊支持向量機(jī).當(dāng)0<λ<1,超平面距離正類樣本較近;反之則超平面距離負(fù)類樣本較近.改進(jìn)后的模糊支持向量機(jī)最優(yōu)決策面即為下列公式的最優(yōu)解:

不等式約束條件變?yōu)?

通過(guò)引入拉格朗日乘子求解上述不等式約束的凸優(yōu)化問(wèn)題:

其中,ai為拉格朗日因子

求解的關(guān)鍵變?yōu)榈玫?7)的最小值,故對(duì)(7)式中的ω,b,ε分別求偏導(dǎo)得到:

將式(8)中得到的結(jié)果代入到式(7),利用拉格朗日對(duì)偶性可以將求解原問(wèn)題滿足約束條件的極小值轉(zhuǎn)化為:

將上面列出的凸優(yōu)化問(wèn)題求解完畢,得到改進(jìn)的模糊支持向量機(jī)的決策函數(shù):

λ的值影響超平面與類之間的空間距離,若0<λ<1,則超平面與正類間的空間距離較小;若 λ>1,則超平面與負(fù)類之間的空間距離較小;若 λ=1 該算法等同于標(biāo)準(zhǔn)的模糊支持向量機(jī).

從式(11)、式(12)可以得到改進(jìn)后的模糊支持向量機(jī)和標(biāo)準(zhǔn)的模糊支持向量機(jī)的基本原理相同的結(jié)論,可以將標(biāo)準(zhǔn)模糊支持向量機(jī)的訓(xùn)練方法應(yīng)用于改進(jìn)的模糊支持向量機(jī)上.

3 確定隸屬度函數(shù)

在超平面的確定過(guò)程中,并不是所有的樣本點(diǎn)都能起到?jīng)Q定性作用的,樣本貢獻(xiàn)度就是度量求解超平面所需的樣本點(diǎn)的性質(zhì).圖1展示了樣本空間的分布狀態(tài),其中深色區(qū)域中的樣本貢獻(xiàn)度較大,區(qū)域外的樣本貢獻(xiàn)度法較小,在求解過(guò)程中更有被識(shí)別為噪聲數(shù)據(jù)的可能性,影響超平面位置的選取.另外,大部分的支持向量樣本位于陰影部分.本文提出一種確定隸屬度函數(shù)的方法,既考慮到了樣本內(nèi)的距離關(guān)系,又考慮到了樣本之間的相互關(guān)系.

圖1 樣本的空間分布

通常定義隸屬度函數(shù)如下:

定義1.類中心:一類樣本的平均樣本特征定義為該類的中心.如訓(xùn)練樣本標(biāo)記為:{x1,x2,···,xn},類中心記為正類樣本的類中心記為m+,負(fù)類樣本的類中心記為m?.

定義2.兩類樣本之間的距離:兩類樣本的類中心之間的距離為兩類樣本之間的距離,記為d,d=|m+?m?|.

定義3.兩類樣本之間的互距離:規(guī)定所有正類樣本到正類中心的距離=|xi?m+|,到負(fù)類中心的距離=|xi?m?|.同樣地,規(guī)定所有負(fù)類樣本到負(fù)類中心的距離=|xi?m?|,到正類中心的距離=|xi?m+|.

由于支持向量機(jī)是通過(guò)將樣本映射到高維空間尋找最優(yōu)決策面,依據(jù)上文給出的定義,各類的樣本距離和樣本互距離在高維空間中求解過(guò)程為:

為此提出了隸屬度函數(shù)的設(shè)計(jì)算法如算法1.

算法1.利用樣本距離確定隸屬度函數(shù)算法d?ip 1)計(jì)算樣本中心點(diǎn)之間的距離,計(jì)算正類樣本的互距離 ;d?ip>d d?ip≤d d 2)比較樣本距離與樣本互距離的大小:若,樣本大都位于圖1深色區(qū)域外部分,若,樣本大都位于圖1深色區(qū)域內(nèi)部分;d?ip≤dd+ipR+3)取 的樣本點(diǎn)計(jì)算其,將其中的最大值記為.R?4)同理得到負(fù)類樣本的.

最終得到兩類樣本的隸屬度函數(shù):

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

當(dāng)分類問(wèn)題應(yīng)用到現(xiàn)實(shí)生活中時(shí),往往對(duì)負(fù)類的分類結(jié)果有更高的要求.本文應(yīng)用兩種評(píng)價(jià)準(zhǔn)則來(lái)驗(yàn)證改進(jìn)算法的分類效果,即準(zhǔn)確率和召回率.其中準(zhǔn)確率描述的是分類結(jié)果,表示負(fù)類分類結(jié)果中實(shí)際負(fù)類樣本的比例.召回率描述的是原有樣本的分類覆蓋率,表示的是原有樣本中的負(fù)類被正確分類的比例.其表達(dá)式分別為:

準(zhǔn)確率Precision=TN/TN+FN

召回率Recall=TN/TN+FP

TN代表實(shí)為負(fù)類且分類結(jié)果為負(fù)類的樣本,FN代表實(shí)為負(fù)類但分類結(jié)果為正類的樣本,FP代表實(shí)為正類但分類結(jié)果為負(fù)類的樣本.

實(shí)驗(yàn)基于UCI 數(shù)據(jù)集,并選出4 種不平衡率不同的訓(xùn)練樣本集,樣本不平衡率如表1所示.

表1 樣本訓(xùn)練集

實(shí)驗(yàn)將IFD-FSVM 算法應(yīng)用于UCI 數(shù)據(jù)集驗(yàn)證算法性能,并將實(shí)驗(yàn)結(jié)果與SVM、FSVM 在相同場(chǎng)景下的分類結(jié)果進(jìn)行比較.

SVM 算法:等距超平面且沒(méi)有將隸屬度函數(shù)應(yīng)用于支持向量機(jī).

FSVM 算法:等距超平面線性隸屬度函數(shù)的模糊支持向量機(jī).

IFD-FSVM 算法:應(yīng)用不等距超平面距離的改進(jìn)模糊支持向量機(jī).

首先,將4 種樣本集的參數(shù)分別設(shè)置為 λIrist=0.8,λBalance=0.7,λYeast=0.63,λAbalone=0.37,δ=0.2 時(shí),各樣本集的負(fù)類分類結(jié)果如表2所示.

表2 各數(shù)據(jù)集在3 種算法下的分類準(zhǔn)確率與回歸率(%)

由表2可以看出,相比其他算法,IFD-FSVM 算法明顯提高了分類準(zhǔn)確率與回歸率.在Irist 數(shù)據(jù)集上應(yīng)用IFD-FSVM 算法進(jìn)行分類,準(zhǔn)確率分別比應(yīng)用標(biāo)準(zhǔn)SVM 和FSVM 提高了15.68%和7.29%.在Balance Scale 數(shù)據(jù)集上應(yīng)用本文算法進(jìn)行分類,準(zhǔn)確率分別比應(yīng)用標(biāo)準(zhǔn)SVM 和FSVM 提高了14.83%和10.46%.而在Yeast 數(shù)據(jù)集上,IFD-FSVM 算法的分類準(zhǔn)確率比其他兩種算法分別提高了19.31%和7.01%,在Abalone數(shù)據(jù)集上則具有較大的準(zhǔn)確度改善,較其他兩種算法分別提高了26.92%和15.93%.

各樣本集的負(fù)類分類效果如圖2、圖3所示.

圖2 負(fù)類樣本分類準(zhǔn)確率對(duì)比

圖3 負(fù)類樣本回歸率對(duì)比

圖2和圖3分別展示了3 種算法在4 種樣本集上負(fù)類的分類的準(zhǔn)確率和召回率.可以看出,IFD-FSVM算法的分類效果明顯優(yōu)于另外兩個(gè)標(biāo)準(zhǔn)算法.且樣本數(shù)據(jù)不平衡比例越高,分類效果的改善越明顯,在Abalone數(shù)據(jù)集上的負(fù)樣本分類準(zhǔn)確率和召回率都有較大幅度提升.

雖然參數(shù) λ對(duì)分類器性能有著至關(guān)重要的影響,當(dāng)參數(shù) λ<1 時(shí),負(fù)類的分類效果有明顯改善,但并不是參數(shù) λ的設(shè)置越小越好.當(dāng)參數(shù) λ過(guò)小時(shí),正類的分類效果受到影響.如將4 種樣本集的參數(shù)分別設(shè)置為 λIrist=0.21,λBalance=0.19,λYeast=0.12,λAbalone=0.08 時(shí),各樣本集的正類分類準(zhǔn)確率如圖4所示.

圖4 正類樣本分類準(zhǔn)確率對(duì)比

從圖4中可以看出,若將參數(shù) λ的值設(shè)置為如上,相較于標(biāo)準(zhǔn)的模糊支持向量機(jī),IFD-FSVM 算法對(duì)正類分類效果明顯下降.由于參數(shù) λ過(guò)小,超平面與正類樣本距離過(guò)小,負(fù)類樣本被識(shí)別為噪聲的概率增加,導(dǎo)致正類分類準(zhǔn)確率受到影響.

5 結(jié)論與展望

通過(guò)對(duì)不平衡支持向量機(jī)的研究,本文提出了應(yīng)用不等距超平面距離改進(jìn)的模糊支持向量機(jī)IFDFSVM.算法通過(guò)改進(jìn)原有的模糊支持向量機(jī),引入?yún)?shù) λ以調(diào)節(jié)超平面到正類的距離,實(shí)驗(yàn)時(shí)規(guī)定 λ<1,令超平面接近正類樣本.利用樣本之間的互距離確定模糊隸屬度函數(shù),有利于確定貢獻(xiàn)度大的樣本數(shù)據(jù),更好的反映了訓(xùn)練樣本對(duì)超平面形成的貢獻(xiàn)作用,降低了噪聲數(shù)據(jù)給分類器性能帶來(lái)的影響.最后利用UCI 數(shù)據(jù)集來(lái)驗(yàn)證IFD-FSVM 算法的有效性,實(shí)驗(yàn)結(jié)果說(shuō)明IFD-FSVM 算法能夠有效提高不平衡樣本的分類準(zhǔn)確率.