基于不等距超平面距離的模糊支持向量機①

李村合,姜 宇,李 帥

(中國石油大學 計算機科學與技術學院,青島 266580)

支持向量機是常見的一種基于統計學習理論的分類算法,核心是結構風險最小化和VC 維理論.其主旨是在高維空間中尋找一個最優分類面,將樣本正確分類且保證分類間隔最大化[1].隨著人工智能時代的到來,支持向量機成功應用至許多方面,尤其是在分類問題的解決上已經成為了主流方法,如網頁分類[2],手寫識別[3]等.

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

在支持向量機的決策過程中,決策面位置的選取取決于樣本空間的分布.由于不平衡數據集的類不平衡性較大,許多樣本點對決策面的確定貢獻度不大,容易識別為噪聲并對分類器的性能造成影響.模糊向量機可以改善噪聲數據造成的分類精度下降現象,通過為樣本點賦予不同的隸屬度來確定樣本點的性質.但傳統的模糊支持向量機在確定樣本隸屬度時,僅考慮了類內距離,應用于不平衡數據集分類時容易出現較大誤差[9].故本文提出一種應用不等距超平面距離的改進模糊支持向量機.文中將樣本數量多的類規定為正類,將樣本數量少的類規定為負類.通過向標準模糊支持向量機中引入參數 λ,以控制超平面與樣本之間的距離.在構造隸屬度函數時,不僅取決于樣本之間的距離,還考慮了樣本之間的互距離,更精準的表示樣本分布,以減小不平衡的樣本分布給分類準確度帶來的影響.

1 相關工作

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

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

在文獻[21]中,介紹了模糊支持向量機,它在處理分類和預測等現實問題時表現出了十分出色的性能,相較支持向量機而言,它可以減輕噪聲數據對分類器性能的影響.隸屬度函數的確定影響著模糊支持向量機分類性能,已有許多算法應用于解決隸屬度函數的選擇問題,如聚類算法[22,23]、啟發式算法[24]等,但至今為止,模糊隸屬度函數的確立尚無系統的理論規定和準則.

通過計算類內距離確定樣本隸屬度,是構造隸屬度函數的經典方法.計算樣本到其類中心點的距離,若距離小則判定該樣本點屬于該類的可能性較大,為該其賦予一個較大的隸屬度值;若距離過大則判定該樣本點為噪聲數據,并賦予該點一個較小的隸屬度值.以此作為樣本貢獻度的衡量指標,可能會令分類器對噪聲的辨識度降低[25],使分類器訓練時誤差較大,降低分類器的分類精度和泛化性能.

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

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

其數學模型用公式表示為:

不等式約束條件為:

式中,ω為決定超平面方向的法向量,b表示該決策面到坐標軸原點的距離.

模糊支持向量機的決策函數為:

K(x,xi)為核函數,常見的核函數有線性核函數、多項式核函數、高斯核函數等,在求解過程中核函數的選擇要視數據集性質而定.

利用不等距超平面距離改進后的模糊支持向量機.當0<λ<1,超平面距離正類樣本較近;反之則超平面距離負類樣本較近.改進后的模糊支持向量機最優決策面即為下列公式的最優解:

不等式約束條件變為:

通過引入拉格朗日乘子求解上述不等式約束的凸優化問題:

其中,ai為拉格朗日因子

求解的關鍵變為得到(7)的最小值,故對(7)式中的ω,b,ε分別求偏導得到:

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

將上面列出的凸優化問題求解完畢,得到改進的模糊支持向量機的決策函數:

λ的值影響超平面與類之間的空間距離,若0<λ<1,則超平面與正類間的空間距離較小;若 λ>1,則超平面與負類之間的空間距離較小;若 λ=1 該算法等同于標準的模糊支持向量機.

從式(11)、式(12)可以得到改進后的模糊支持向量機和標準的模糊支持向量機的基本原理相同的結論,可以將標準模糊支持向量機的訓練方法應用于改進的模糊支持向量機上.

3 確定隸屬度函數

在超平面的確定過程中,并不是所有的樣本點都能起到決定性作用的,樣本貢獻度就是度量求解超平面所需的樣本點的性質.圖1展示了樣本空間的分布狀態,其中深色區域中的樣本貢獻度較大,區域外的樣本貢獻度法較小,在求解過程中更有被識別為噪聲數據的可能性,影響超平面位置的選取.另外,大部分的支持向量樣本位于陰影部分.本文提出一種確定隸屬度函數的方法,既考慮到了樣本內的距離關系,又考慮到了樣本之間的相互關系.

圖1 樣本的空間分布

通常定義隸屬度函數如下:

定義1.類中心:一類樣本的平均樣本特征定義為該類的中心.如訓練樣本標記為:{x1,x2,···,xn},類中心記為正類樣本的類中心記為m+,負類樣本的類中心記為m?.

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

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

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

為此提出了隸屬度函數的設計算法如算法1.

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

最終得到兩類樣本的隸屬度函數:

4 實驗結果與分析

當分類問題應用到現實生活中時,往往對負類的分類結果有更高的要求.本文應用兩種評價準則來驗證改進算法的分類效果,即準確率和召回率.其中準確率描述的是分類結果,表示負類分類結果中實際負類樣本的比例.召回率描述的是原有樣本的分類覆蓋率,表示的是原有樣本中的負類被正確分類的比例.其表達式分別為:

準確率Precision=TN/TN+FN

召回率Recall=TN/TN+FP

TN代表實為負類且分類結果為負類的樣本,FN代表實為負類但分類結果為正類的樣本,FP代表實為正類但分類結果為負類的樣本.

實驗基于UCI 數據集,并選出4 種不平衡率不同的訓練樣本集,樣本不平衡率如表1所示.

表1 樣本訓練集

實驗將IFD-FSVM 算法應用于UCI 數據集驗證算法性能,并將實驗結果與SVM、FSVM 在相同場景下的分類結果進行比較.

SVM 算法:等距超平面且沒有將隸屬度函數應用于支持向量機.

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

IFD-FSVM 算法:應用不等距超平面距離的改進模糊支持向量機.

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

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

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

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

圖2 負類樣本分類準確率對比

圖3 負類樣本回歸率對比

圖2和圖3分別展示了3 種算法在4 種樣本集上負類的分類的準確率和召回率.可以看出,IFD-FSVM算法的分類效果明顯優于另外兩個標準算法.且樣本數據不平衡比例越高,分類效果的改善越明顯,在Abalone數據集上的負樣本分類準確率和召回率都有較大幅度提升.

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

圖4 正類樣本分類準確率對比

從圖4中可以看出,若將參數 λ的值設置為如上,相較于標準的模糊支持向量機,IFD-FSVM 算法對正類分類效果明顯下降.由于參數 λ過小,超平面與正類樣本距離過小,負類樣本被識別為噪聲的概率增加,導致正類分類準確率受到影響.

5 結論與展望

通過對不平衡支持向量機的研究,本文提出了應用不等距超平面距離改進的模糊支持向量機IFDFSVM.算法通過改進原有的模糊支持向量機,引入參數 λ以調節超平面到正類的距離,實驗時規定 λ<1,令超平面接近正類樣本.利用樣本之間的互距離確定模糊隸屬度函數,有利于確定貢獻度大的樣本數據,更好的反映了訓練樣本對超平面形成的貢獻作用,降低了噪聲數據給分類器性能帶來的影響.最后利用UCI 數據集來驗證IFD-FSVM 算法的有效性,實驗結果說明IFD-FSVM 算法能夠有效提高不平衡樣本的分類準確率.