郭晨晨， 朱紅康

(山西師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 山西 臨汾 041000)

一種改進(jìn)的支持向量機(jī)模型研究

郭晨晨， 朱紅康*

(山西師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 山西 臨汾 041000)

傳統(tǒng)的支持向量機(jī)無法充分、有效地檢測出類間重疊區(qū)域中的少數(shù)實(shí)例，也無法對不平衡的數(shù)據(jù)集作出合理分類，而類的重疊分布和不平衡分布在復(fù)雜數(shù)據(jù)集中是常見的.因而，它們對支持向量機(jī)的分類性能產(chǎn)生負(fù)面影響.基于此，提出了一種利用距離度量代替支持向量機(jī)松弛變量的改進(jìn)模型.在一定程度上解決了支持向量機(jī)處理復(fù)雜數(shù)據(jù)集中類間重疊和不平衡的問題.最后，利用合成數(shù)據(jù)集和UCL數(shù)據(jù)庫中的數(shù)據(jù)集的實(shí)驗(yàn)驗(yàn)證了該算法的先進(jìn)性.

支持向量機(jī)； 重疊； 不平衡； 松弛變量； 距離度量

0 引言

自Vapnik[1]提出支持向量機(jī)，因其有效的分

類性能，嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)理論基礎(chǔ)，成為處理分類問題的熱門技術(shù).在小樣本數(shù)據(jù)集、非線性分類問題中有很好的效果，特別對于高維數(shù)據(jù)的處理，可以有效的避免維數(shù)災(zāi)難[2].支持向量機(jī)主要原理是最大化超平面邊距同時最小化分類誤差.但SVM無法充分、有效地檢測出類間重疊區(qū)域中的少數(shù)實(shí)例，也無法對不平衡的數(shù)據(jù)集作出合理分類.因?yàn)轭愰g存在重疊區(qū)域時，類間清晰的超平面邊緣將不存在.而數(shù)據(jù)集中同時存在大樣本類和小樣本類時，支持向量機(jī)的處理結(jié)果往往趨向于大樣本類，使分類結(jié)果產(chǎn)生嚴(yán)重的偏差.針對SVM存在的問題，目前已經(jīng)提出了一批實(shí)用的方法，比如對數(shù)據(jù)預(yù)處理方式進(jìn)行調(diào)整，對大樣本類多取樣，對小樣本類少取樣[3-5]；改良核函數(shù)矩陣調(diào)整聚類邊界降低迭代過程中原核矩陣與保形變換核矩陣之間會產(chǎn)生偏差[6]；對誤報率和漏報率之間進(jìn)行權(quán)衡控制[7]；通過修改松弛變量減少異常數(shù)據(jù)點(diǎn)對自適應(yīng)邊緣和決策函數(shù)的影響,利用數(shù)據(jù)點(diǎn)的平均值和標(biāo)準(zhǔn)差來克服數(shù)據(jù)擾動等[8-10].

本文試圖通過一種新的方式改善這一問題.即調(diào)整決策邊界，設(shè)置邊緣為適當(dāng)距離提高分類性能.由于原有松弛變量模型在學(xué)習(xí)階段對離群數(shù)據(jù)點(diǎn)并不敏感，因而采用了新型的松弛變量模型，用距離度量代替原來的松弛變量，并在訓(xùn)練階段適當(dāng)擴(kuò)大了異常點(diǎn)與正常點(diǎn)的距離.從而降低類分布的影響，使得大樣本類和小樣本類都能得到很好的劃分.基于距離度量的松弛變量被包含在對偶問題的最優(yōu)函數(shù)中，參數(shù)由梯度下降法得到.使得改進(jìn)的松弛變量模型不容易受到復(fù)雜數(shù)據(jù)集的影響.

1 改進(jìn)松弛變量的支持向量機(jī)

1.1 傳統(tǒng)支持向量機(jī)

Vapnik[1]提出的支持向量機(jī)主要處理二分類問題，其核心思想如下：

在一個樣本空間中，由決策邊界將所有樣本分為兩個部分，即對訓(xùn)練樣本集進(jìn)行二元分類.對于一個含有n個樣本點(diǎn)的訓(xùn)練樣本集，每個樣本點(diǎn)都表示為一個二元組，(xi,yi)(i=1,2,…,n)其中xi=(xi1,xi2,…,xik)T對應(yīng)于第i個樣本的屬性集，yi∈{-1,1}表示分類結(jié)果.將原始空間中的樣本點(diǎn)xi通過映射函數(shù)φ(x)映射到高維特征空間中，得到線性支持向量機(jī)決策邊界基本形式如公式(1)所示：

f(x)=w·φ(x)+b

(1)

由于訓(xùn)練數(shù)據(jù)集中可能存在的噪聲，即線性SVM不可分情況.必須考慮邊緣寬度與線性決策邊界允許的訓(xùn)練錯誤數(shù)目之間的折中.從而引入松弛變量實(shí)現(xiàn)邊緣“軟化”，如公式(2)所示.

(w·φ(x)+b)≥1-ξi,當(dāng)yi=+1;

(w·φ(x)+b)≤-1+ξi,當(dāng)yi=-1.

(2)

式(2)中：?i,ξi≥0.

由于在決策邊界誤分樣本數(shù)沒有限制，從而可能產(chǎn)生邊緣很寬，但誤分離很多訓(xùn)練實(shí)例的決策邊界.修改目標(biāo)函數(shù)，以懲罰松弛變量值很大的決策邊界.修改后的目標(biāo)函數(shù)如公式(3)所示.

s.t.yi(w·φ(x)+b)≥1-ξi

(3)

式(3)中：C是軟邊緣懲罰參數(shù).

1.2 改進(jìn)松弛變量的支持向量機(jī)

雖然在傳統(tǒng)SVM中利用軟邊緣的方法解決了線性不可分的問題，但這都建立在數(shù)據(jù)集中的類是大致平衡且少重疊的.針對數(shù)據(jù)集中存在的類間重疊和不平衡問題，利用距離度量代替原來的松弛變量ξi，在馬氏空間中放大了正常樣本與異常樣本的距離，如圖1所示.

圖1 馬氏空間中正常樣本與異常樣本的距離示意圖

此外，為了發(fā)現(xiàn)一個最佳超平面及邊緣以達(dá)到克服擾動的最大魯棒性并且減少錯誤分類風(fēng)險的概率，超平面的變化過程如圖2所示.

圖2 超平面與邊緣變化過程

以上通過圖示展示改進(jìn)產(chǎn)生的相關(guān)變化，下面對距離度量代替松弛變量ξi做具體解釋.

傳統(tǒng)的線性支持向量機(jī)的不可分情況如公式(3)所示，這里作出改進(jìn)，將距離D(x)2替換原來的松弛變量ξi，并且最小化向量w而非原來的w與誤差余量的和.D(x)2表示每個樣本點(diǎn)與其各自類中心的歸一化距離，修改后的目標(biāo)函數(shù)如下：

s.t.yif(xi)≥1-θD(xi)2

(4)

式(4)中：θ是預(yù)選參數(shù)，用于測量松弛變量的平均影響，距離計(jì)算如公式(5)所示：

(5)

式(5)中：S-1是協(xié)方差矩陣的逆，μ是均值向量，t是轉(zhuǎn)置符號.

樣本點(diǎn)與其各自類中心間的距離在一定范圍才能建立聯(lián)系，距離D(x)2滿足需要下面的約束條件：

0≤D(xi)2≤1

(6)

確定距離D(x)2，得到支持向量滿足下面的等式：

yif(xi)=1-θD(xi)2

(7)

由此，該優(yōu)化問題的拉格朗日函數(shù)可以記作如下形式：

(8)

式(8)中：αi叫做拉格朗日乘子.

為了最小化拉格朗日函數(shù)，采用與傳統(tǒng)方法相似化的方法進(jìn)行處理.對Lp關(guān)于w和b求偏導(dǎo)，并令它們等于0，得到(9)、(10)兩個等式：

(9)

(10)

w可由公式(11)得到：

(11)

使用b的平均值作為決策邊界的參數(shù)，計(jì)算公式如下：

αi{yif(xi)-1+θD(xi)2}=0

(12)

對于支持向量，將公式(11)帶入公式(8)可得：

(13)

這樣，不可分的對偶問題可以轉(zhuǎn)化為下面的優(yōu)化問題：

(14)

通過求解對偶問題得到最優(yōu)參數(shù)w和b后，可以根據(jù)符號進(jìn)行分類(公式1)，參數(shù)θ可由梯度下降法求得，這是一個一階優(yōu)化算法.本方法需要最大化公式(13)并且找到合適的參數(shù)θ，從而進(jìn)行如下計(jì)算：

(15)

t≥0.

(16)

由于θ的不同取值會對整個優(yōu)化問題的性質(zhì)產(chǎn)生根本影響，因此需要對參數(shù)θ進(jìn)行分類討論：

情況1：當(dāng)θ=0，則邊緣不用修改，此問題轉(zhuǎn)化為硬邊緣SVM問題；

情況2：當(dāng)θ=1，則該問題同傳統(tǒng)SVM相同；

情況3：當(dāng)0<θ<1，則0<θ×D(xi)2<1，該算法對決策邊界右側(cè)的異常點(diǎn)有較好的效果，每個類中心的影響是有限的；

情況4：當(dāng)θ>1，則θ×D(xi)2>1，對于落在錯誤位置的異常點(diǎn)，該算法性能強(qiáng)大.較大的θ使得支持向量靠近類中心，因而更容易得到一個清晰的決策邊界.然而，分類的錯誤率也會隨之增加，調(diào)整后的決策邊界更趨向于檢測異常點(diǎn).

(17)

(18)

1.3 算法描述

根據(jù)上節(jié)的推導(dǎo)過程，設(shè)計(jì)相應(yīng)的算法進(jìn)行實(shí)驗(yàn)分析.該算法需要對數(shù)據(jù)集xi進(jìn)行最大次數(shù)T次的迭代運(yùn)算，在每一次的迭代中，自適應(yīng)的計(jì)算函數(shù)D(x)2并更新參數(shù)θ和σ的值，算法如下：

輸入：訓(xùn)練數(shù)據(jù)集xi，核函數(shù)K，最大迭代次數(shù)T，終止條件η，核函數(shù)參數(shù)σ，規(guī)則化參數(shù)θ.

子函數(shù)：邊緣函數(shù)Margin(xi,σ) ,訓(xùn)練模型SVM(xi,K,σ,θ) ，V-折交叉驗(yàn)證函數(shù)V-Fold(xi,v) ；

主函數(shù)：v←1

{

xiv←V-Fold(xi,v)；

Ctv←SVM(xiv,K,σK);

t←0;

While(Ctv-Ctv+1<η&t

{

t←t+1；

}

End While

Cv←Ctv;

v←v+1;

}

ReturnAccuracy;

輸出：Cv.

2 性能測試

2.1 數(shù)據(jù)集復(fù)雜度的度量

分類算法性能的好壞很大程度上取決于訓(xùn)練數(shù)據(jù)集本身的特性，以前的研究往往通過減少未知數(shù)據(jù)集的選取進(jìn)行分類的弱比較，很難從統(tǒng)計(jì)學(xué)和幾何類分布角度來考慮分類結(jié)果.基于此，為了提高數(shù)據(jù)復(fù)雜度度量的合理性，采用兩種量度方式進(jìn)行綜合評估.

2.1.1 Fisher鑒別準(zhǔn)則

Fisher的廣義判別式(F1)[11]用來對兩個類間的區(qū)別進(jìn)行鑒別，公式如下：

(19)

這樣對于多維或多類數(shù)據(jù)集的類間重疊率(R1)，可以表示為如下形式：

(20)

2.1.2 重疊率

對于重疊率的計(jì)算，該方法采用的指標(biāo)R2[12]進(jìn)行度量，具體公式如下：

(21)

式(21)中：

min maxi=min{max(fi,ci),max(fi,c2)},

max mini=max{min(fi,ci),min(fi,c2)},

max maxi=max{max(fi,c1),max(fi,c2)},

min mini=min{min(fi,c1),min(fi,c2)}.

max(fi,ci)和min(fi,ci)分別是類ci(i=1,2) 的特征值fi中的最大值和最小值.R2的值越小表明類間的重疊程度越高.

2.2 性能度量

準(zhǔn)確率度量是將數(shù)據(jù)集中所有的類看成同等重要，因此并不適合分析不平衡數(shù)據(jù)集.在不平衡數(shù)據(jù)集中，少數(shù)類往往比多數(shù)類更有意義.

二元分類問題中，少數(shù)類通常記為正類，多數(shù)類記為負(fù)類.表1顯示了匯總分類模型正確和不正確預(yù)測的實(shí)例數(shù)目的混淆矩陣.

表1 類不是同等重要的二分類問題的混淆矩陣

混淆矩陣中的計(jì)數(shù)可以表示為百分比的形式.靈敏度定義為被模型正確預(yù)測的正樣本的比例，即：

(22)

同理，特指度定義為被模型正確預(yù)測的負(fù)樣本的比例，即：

(23)

精確度定義為模型正確預(yù)測的所有樣本的比例，即：

(24)

3 實(shí)驗(yàn)

通過該算法與傳統(tǒng)SVM進(jìn)行性能對比來展示改進(jìn)算法在復(fù)雜數(shù)據(jù)集分類性能上獲得的提升.對合成數(shù)據(jù)集的各個變量進(jìn)行控制，產(chǎn)生三種因素的不同組合來研究類不平衡問題與類間重疊問題對分類精度產(chǎn)生的影響.

3.1 析因?qū)嶒?yàn)

實(shí)驗(yàn)一設(shè)計(jì)加入了三個程度的“類不平衡”因素、三個程度的“類重疊”因素、兩個種類的“分類器”幾種不同的情況，將它們安排在同一個析因?qū)嶒?yàn)中.根據(jù)不同的處理組合產(chǎn)生合成數(shù)據(jù)集.每個數(shù)據(jù)集分為兩個類并且隨機(jī)地以二維正態(tài)分布，共100個實(shí)例.

重疊性根據(jù)重疊程度劃分為三個層次：低度：μ1=40，μ2=60；中度：μ1=45，μ2=55；高度：μ1=50，μ2=50.

則合成數(shù)據(jù)集的協(xié)方差矩陣定義為：

同理，將不平衡性劃分為三個不同層次.低度：50%的實(shí)例屬于第一類，50%的實(shí)例屬于第二類；中度：75%的實(shí)例屬于第一類，25%的實(shí)例屬于第二類；高度：90%的實(shí)例屬于第一類，10%的實(shí)例屬于第二類.

分類器因素：一種是傳統(tǒng)的SVM，一種是本文改進(jìn)算法.

根據(jù)上面的各種因素設(shè)計(jì)出9種不同的合成數(shù)據(jù)集，其中坐標(biāo)軸Y軸對類重疊性和類不平衡性沒有影響.分別將類重疊的低、中、高三種程度表示為1、2、3，類不平衡的低、中、高三種程度表示為一、二、三，“×”表示少數(shù)類，“Ο”表示多數(shù)類，實(shí)驗(yàn)結(jié)果如圖3所示.

圖3 合成數(shù)據(jù)集聚類實(shí)驗(yàn)

表2顯示了用R1和R2兩種測量指標(biāo)對合成數(shù)據(jù)集的計(jì)算結(jié)果.

表2 合成數(shù)據(jù)集的R1和R2指標(biāo)計(jì)算結(jié)果

根據(jù)表2中的指標(biāo)數(shù)據(jù)，得到最終實(shí)驗(yàn)結(jié)果，如表3所示.

表3 數(shù)據(jù)集不同程度重疊性和不平衡性的度量結(jié)果對比

從表3可知，改進(jìn)算法在靈敏度和準(zhǔn)確度上均有較大提升，特別在高度重疊性和高度不平衡性的合成數(shù)據(jù)集中體現(xiàn)的尤為明顯，在中低度層面基本保持不變.結(jié)果表明，數(shù)據(jù)復(fù)雜性(重疊性和不平衡性)對分類精確度影響明顯，且成反相關(guān)性.

3.2 UCI數(shù)據(jù)集實(shí)驗(yàn)

實(shí)驗(yàn)二設(shè)計(jì)從UCI數(shù)據(jù)庫中選擇6個數(shù)據(jù)集進(jìn)行測試，如表4所示.

表4 UCI數(shù)據(jù)集測試

表4中，第二列中括號中的數(shù)據(jù)分別表示多數(shù)類和少數(shù)類樣本的數(shù)量，即正樣本和負(fù)樣本的數(shù)量.僅從正負(fù)樣本的比例分析，German、Glass、BCW數(shù)據(jù)集存在低度不平衡性，Yeast和Car數(shù)據(jù)集存在中度不平衡性，Abalone數(shù)據(jù)集存在高度不平衡性.但考慮復(fù)雜性度量指標(biāo)R1和R2，Yeast是最不平衡的.因此，單一分析正負(fù)樣本率不能充分了解數(shù)據(jù)集的特性.

除了考慮數(shù)據(jù)復(fù)雜度對分類精度產(chǎn)生的影響外，還需要對分類器的性能進(jìn)行驗(yàn)證.使用4-交叉驗(yàn)證法驗(yàn)證傳統(tǒng)SVM和本文改進(jìn)算法的性能.該方法將原始數(shù)據(jù)集分為兩部分，一部分為訓(xùn)練數(shù)據(jù)集，一部分為測試數(shù)據(jù)集.首先用訓(xùn)練集對分類器進(jìn)行訓(xùn)練,再利用驗(yàn)證集來測試訓(xùn)練得到的模型,以此來做為評價分類器的性能指標(biāo).使用多折交叉驗(yàn)證主要為了提高可利用的訓(xùn)練數(shù)據(jù)集樣本數(shù)量.此外，可以分為多個相互獨(dú)立的測試數(shù)據(jù)集有效地覆蓋整個樣本空間.實(shí)驗(yàn)二重復(fù)4次，得出結(jié)果.

核函數(shù)選擇徑向基核函數(shù)(Radial Basis Kernel Function),利用梯度下降法獲得參數(shù)θ和σ，終止條件設(shè)置為100，并在迭代50次后得到穩(wěn)定的參數(shù).實(shí)驗(yàn)結(jié)果如表5所示.

表5 SVM與本文所提算法在UCI數(shù)據(jù)庫上的對比結(jié)果

由表5可得，改進(jìn)算法關(guān)于三種指標(biāo)的度量值均優(yōu)于傳統(tǒng)SVM.此外，由4-交叉驗(yàn)證法得到參數(shù)的θ值與數(shù)據(jù)集的復(fù)雜度成正相關(guān)，而參數(shù)σ僅依賴于數(shù)據(jù)的規(guī)格參數(shù).從表5可得，前三個數(shù)據(jù)集參數(shù)θ值均少于1.5，數(shù)據(jù)集的復(fù)雜度相應(yīng)地呈現(xiàn)低度狀態(tài)，而參數(shù)σ明顯不具有這樣的性質(zhì).

根據(jù)以上兩個實(shí)驗(yàn)可得，改進(jìn)算法在分類性能方面明顯優(yōu)于傳統(tǒng)SVM，即柔性地距離邊緣適合在重疊且不平衡類分布的區(qū)域預(yù)測稀有樣本.

4 結(jié)論

本文展示了一種新的SVM二次優(yōu)化模型，通過改變特征空間中決策邊界到邊緣的距離改良邊緣的性能.自適應(yīng)的邊緣模型可以在訓(xùn)練復(fù)雜數(shù)據(jù)集方面顯示良好的分類性能.現(xiàn)實(shí)生活中往往存在這樣的規(guī)律，少數(shù)類的正確分類要比多數(shù)類的正確分類更有價值.因此，本文所提方法才顯示出其應(yīng)用的潛力.未來的工作是將本方法應(yīng)用到更多現(xiàn)實(shí)生活中存在不平衡和重疊性的數(shù)據(jù)集中，并根據(jù)應(yīng)用情況調(diào)整算法細(xì)節(jié).

[1] Vapnik V.The nature of statistical learning theory[M].New York:Springer Verlag,1995：142-165.

[2] Tan P N,Steinbach M,Kumar V.Introduction to data mining[M].New Jersey：Addison Wesley,2005：115-131.

[3] Zhao H，Chen H，Nguyen T.Stratified over-sampling bagging method for random forests on imbalanced data[M].Switzerland：Springer International Publishing,2016：46-60.

[4] Vluymans S，Tarragó D S，Saeys Y.Fuzzy rough classifiers for class imbalanced multi-instance data[J].Pattern Recognition,2016,53:36-45.

[5] Liu Alexander,Ghosh J,Martin C.Generative oversampling for mining imbalanced datasets[C]∥Proceedings of 2007 International Conference on Data Mining .Las Vegas,Nevada,USA :CSREA Press,2007:66-72.

[6] Wu G,Chang E Y.KBA:Kernel boundary alignment considering imbalanced data distribution[J].IEEE Transactions on Knowledge and Data Engineering,2005,17:786-794.

[7] 徐小鳳,劉家芬,鄭宇衛(wèi). 基于密度的空間數(shù)據(jù)聚類的正常用戶篩選方法[J].計(jì)算機(jī)應(yīng)用，2015，35(S1):43-46.

[8] Trafalis T B,Gilbert R C.Robust classification and regression using support vector machines[J].European Journal of Operational Research,2006,173(3):893-909.

[9] Trafalis T B,Gilbert R C.Robust support vector machines for classification and computational issues[J].Optimization Methods and Software,2007,22:187-198.

[10] Song Q,Hu W,Xie W.Robust support vector machine with bullet hole image classification[J].IEEE Transactions on Systems Man and Cybernetics Part C (Applications and Reviews) ,2002,32:440-448.

[11] Mollineda R A，Snchez J S，Sotoca J M.Data characterization for effective prototype selection[J].Iberian Conference on Pattern Recognition & Image Analysis,2005,523(20):295-302.

[12] Ho T K，Basu M.Complexity measures of supervised classification problems[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2002,24(3):289-300.

【責(zé)任編輯：蔣亞儒】

Research on an improved support vector machine model

GUO Chen-chen, ZHU Hong-kang*

(School of Mathematics and Computer Science， Shanxi Normal University， Linfen 041000， China)

Traditional support vector machines can not sufficiently and effectively detect the instance of the minority class in the overlap region and can not make a reasonable classification of the imbalanced data sets.However,the overlapping and imbalanced of the classes are common in complicated data sets.As a result,they have a negative impact on the classification performance of support vector machines.Based on this,an improved model is proposed to replace the slack variables of support vector machine based on distance measure.To a certain extent,it solves the problem that the support vector machine is dealing the overlapping and imbalanced of the classes in complicated data sets.Finally,the advanced nature of the algorithm is verified by the experimental results of the data set in the synthetic data set and the UCL database.

support vector machine; overlapping; imbalanced; slack variable； distance measure

2017-01-16 基金項(xiàng)目：山西省自然科學(xué)基金項(xiàng)目(2015011040)

郭晨晨(1992-)，男，山西長治人，在讀碩士研究生，研究方向：計(jì)算機(jī)應(yīng)用

朱紅康(1975-)，男，山西汾西人，副教授，博士，研究方向：數(shù)據(jù)挖掘,zhuhkyx@126.com

1000-5811(2017)02-0189-06

TP18

A