許翠云，業(yè) 寧

(南京林業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，江蘇 南京 210037)

基于類向心度的模糊支持向量機*

許翠云，業(yè) 寧

(南京林業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，江蘇 南京 210037)

傳統(tǒng)支持向量機(SVM)訓(xùn)練含有噪聲或野值點的數(shù)據(jù)時，容易產(chǎn)生過擬合，而模糊支持向量機可以有效地處理這種問題。針對使用樣本與類中心之間的距離關(guān)系來構(gòu)建模糊支持向量機隸屬度函數(shù)的不足，提出了一種基于類向心度的模糊支持向量機(CCD-FSVM)。該方法不僅考慮到樣本與類中心之間的關(guān)系，還考慮到類中各個樣本之間的聯(lián)系，并用類向心度來表示。將類向心度應(yīng)用于模糊隸屬度函數(shù)的設(shè)計，能夠很好地將有效樣本與噪聲、野值點樣本區(qū)分開來，而且可以通過向心度的大小，對混合度比較高的樣本進行區(qū)分，從而達到提高分類精度的效果。實驗結(jié)果表明，基于類向心度的模糊支持向量機其分類正確率比支持向量機高，在使用三種不同隸屬度函數(shù)的FSVM中，該方法的抗噪性能最好，分類性能最強。

模糊支持向量機；隸屬度函數(shù)；類向心度

1 引言

支持向量機SVM(Support Vector Machines)[1]是將結(jié)構(gòu)風(fēng)險最小化原則引入到分類的一種機器學(xué)習(xí)方法，它基于統(tǒng)計學(xué)習(xí)理論，致力于在屬性空間中構(gòu)建最優(yōu)分類超平面，從而獲得分類器的全局最優(yōu)解。SVM泛化能力強，能夠較好地解決傳統(tǒng)機器學(xué)習(xí)方法中存在的問題，如：局部極小、過學(xué)習(xí)和維數(shù)災(zāi)難等。但是，它的抗噪性比較差，對噪聲或野值點比較敏感。為了改善這個問題，Lin C F[2]等人根據(jù)不同樣本對構(gòu)建分類面所起的作用也不同這一特點，將隸屬度函數(shù)引入支持向量機，構(gòu)建了一種模糊支持向量機FSVM(Fuzzy Support Vector Machines)，為了削弱噪聲或野值點對分類面的影響，對噪聲或野值點權(quán)值賦予較小的值。

模糊隸屬度函數(shù)直接影響到最終的分類結(jié)果及算法實現(xiàn)的難易程度，因此在構(gòu)建FSVM的過程中，如何設(shè)計出一個能夠準(zhǔn)確反映系統(tǒng)中樣本的分布情況的函數(shù)顯得尤為重要。目前，構(gòu)造隸屬度函數(shù)的方法有很多種，但始終沒有一個通用的準(zhǔn)則，其中最常用的是用樣本與類中心的距離來確定隸屬度函數(shù)的大小[2，3]，這種方法的缺點是忽略了類中各樣本點之間的關(guān)系。本文通過類向心度來體現(xiàn)樣本之間的緊密程度，提出一種基于類向心度的模糊支持向量機CCD-FSVM(Class Centripetal Degree Fuzzy Support Vector Machine)。CCD-FSVM克服了傳統(tǒng)FSVM缺陷的同時，還可以通過向心度來對混合程度較高的樣本進行區(qū)分，從而達到有效地識別有效樣本、噪聲野值點的目的，減小了噪聲、野值點對構(gòu)造最優(yōu)分類面的影響。

2 模糊支持向量機

為了提高支持向量機對噪聲、野值點數(shù)據(jù)的抵抗力，模糊支持向量機在原有的基礎(chǔ)上，給每個訓(xùn)練樣本賦予不同的隸屬度值。利用FSVMs進行分類時，需要對樣本數(shù)據(jù)進行模糊化的預(yù)處理，即根據(jù)選擇的隸屬度函數(shù)，計算每個樣本xi的隸屬度值si，于是將訓(xùn)練集變成模糊訓(xùn)練集T={(x1,y1,s1),(x2,y2,s2),…,(xl,yl,sl)}，其中xi∈Rn，yi∈{-1,1}，0≤si≤1。則求解最優(yōu)超平面的優(yōu)化問題變?yōu)椋?/p>

(1)

其中，c為常數(shù)。

與標(biāo)準(zhǔn)支持向量機求解過程類似，首先構(gòu)造拉格朗日函數(shù):

(2)

其中，αi,βi≥0為拉格朗日乘子。

變量w、b和ξ在鞍點處滿足如下條件：

(3)

將式(3)代入到式(2)中，得到原問題(1)的對偶問題:

(4)

根據(jù)KKT條件可知，最優(yōu)解還應(yīng)當(dāng)滿足KT條件:

(5)

求得決策函數(shù):

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

(6)

由FSVMs的構(gòu)造過程可以看出：(1)當(dāng)αi>0時，對應(yīng)的xi為支持向量；當(dāng)αi=0，ξi=0時，對應(yīng)的xi被正確分類；支持向量有兩種類型：普通的支持向量及邊界支持向量，若xi是普通的支持向量，則0<αi

3 基于類向心度的隸屬度函數(shù)設(shè)計

3.1 基于距離的隸屬度函數(shù)

基于距離設(shè)計的隸屬度中距離是指樣本與其所在類中心之間距離，具體分為以下幾種情況：

(1)線性可分情形。

設(shè)x+、x-分別是正、負類樣本的類中心，di+、di-分別是正、負樣本到各自類中心的距離，r+、r-分別是正、負樣本距離其類中心的最遠距離，則：

di+=‖xi-x+‖，di-=‖xi-x-‖

r+=maxdi+，r-=maxdi-

其中，l+、l-分別是正、負類樣本的個數(shù)。

(2)非線性可分情形。

引入樣本空間到特征空間的映射函數(shù)φ(x)，則特征空間中正、負類樣本的類中心變?yōu)棣?x+)、φ(x-)，則：

由上面的計算可設(shè)計出基于距離的隸屬度函數(shù)：

(7)

其中，δ為事先給定的一個很小的正數(shù)，r+=maxdi+,r-=maxdi-。

3.2 樣本緊密度的表示

SVM最優(yōu)分類面的構(gòu)造是由靠近類邊緣的支持向量所決定的，而噪聲、野值點往往也在這一區(qū)域。因此，依據(jù)樣本到類中心距離設(shè)計的隸屬度函數(shù)并不能有效地區(qū)分支持向量與孤立點，從而降低了FSVM算法的分類精度。圖1所示為兩個不同類別的樣本之間緊密度的差別。

Figure 1 Difference of affinity of samples in different classes圖1 不同類別的樣本之間緊密度的差別

圖1a與圖1b中樣本點x到其類中心的距離相等，如果根據(jù)式(7)計算隸屬度，它們的值是相等的，然而考慮到圖1a中樣本x到其它樣本點的距離比圖1b中的要近，圖1a中的x比圖1b中的更有可能成為有效樣本，圖1b中的x比圖1a中的更有可能成為野值點。所以，圖1a中樣本點x屬于所在類的隸屬度要比圖1b中的大。

針對這種情況，文獻[4,5]提出了基于樣本緊密度的隸屬度函數(shù)，即：結(jié)合樣本與其所在類中心、樣本點與周圍其他樣本點之間的關(guān)系(樣本之間的緊密程度)來計算隸屬度。目前用來表示樣本緊密程度的方法有：one-class分類算法、k近鄰[6]、模糊連接度[3,7]等。但是,這些方法均有著自身的缺陷，如：當(dāng)兩類樣本集混合比較嚴重時，k近鄰表現(xiàn)出的只是樣本之間距離的遠近關(guān)系，而沒有考慮到k個近鄰樣本自身的類別信息，即在樣本與其k個近鄰屬于同一類、均不屬于同一類、一部分同類而另一部分不同類這三種情況下，k個近鄰樣本點對樣本分屬于哪一類所造成的影響是不同的；模糊連接度的計算過程相當(dāng)復(fù)雜；one-class分類算法相當(dāng)于在分類之前先做一次分類，時間耗費特別多等。

基于以上情況，本文用類向心度來表示樣本之間的緊密程度。類向心度的定義如下：

每個樣本xi計算與它距離最近的k個樣本，不妨設(shè)它們到xi的距離分別為di1,di2,…,dik，用1/dij表示第j個近鄰對該樣本點所產(chǎn)生的類別影響因子。分以下幾種情況進行定義：

(1)若這k個樣本與樣本xi均屬于同一類，則類向心度為：

(8)

(2)若這k個樣本與樣本xi均不屬于同一類，則類向心度為：

(9)

(3) 若這k個樣本中有l(wèi)個與樣本xi屬于同一類(假設(shè)距離為di1,di2,…,dil)，而剩下的k-l個與樣本xi都不是同一個類(假設(shè)距離為di1+1,dil+2,…,dik)。說明有混淆, 程度是否嚴重要根據(jù)類向心度進行判別。類向心度為:

(10)

其中:

則樣本之間的緊密程度si2可以設(shè)計如下：

(1)計算樣本xi的k個近鄰。

(2)判斷k個近鄰與樣本xi是否均屬于不同的類別。若是，則令：

(11)

若否，則根據(jù)式(8)或式(10)計算xi的類向心度。

(3)針對(2)中否的情況，在計算出ei后，令M=max(|ei|)，則：

(12)

3.3 基于類向心度的隸屬度函數(shù)(CCD-FSVM)

結(jié)合樣本與類中心的關(guān)系及其樣本與樣本之間的關(guān)系，給出基于類向心度的隸屬度函數(shù)：

(13)

其中，si1、si2分別由式(7)、式(11)或式(7)、式(12)確定。

由式(13)定義的隸屬度函數(shù)可以看出：(1)當(dāng)樣本與類中心的距離一定時，樣本的隸屬度調(diào)整幅度與樣本之間的緊密度成反比；(2)當(dāng)類向心度一定時，隸屬度大小與樣本距類中心之間的距離成反比；(3)當(dāng)k近鄰一定時，如果近鄰中存在混合，則它們對分類的綜合作用是削弱的，該樣本點的隸屬相對比較小。這樣可以將式(13)直接用到模糊支持向量機中。

4 實驗結(jié)果與分析

為了驗證CCD-FSVM算法的有效性，本文以人工數(shù)據(jù)集和UCI標(biāo)準(zhǔn)數(shù)據(jù)集中的數(shù)據(jù)為測試數(shù)據(jù)，將其與SVM算法、文獻[4]中基于k近鄰的模糊支持向量機算法(KNN-FSVM)、文獻[2]中傳統(tǒng)的模糊支持向量機算法(SFSVM)的分類結(jié)果進行比較。

4.1 人工數(shù)據(jù)集

本實驗的訓(xùn)練集樣本為隨機產(chǎn)生的400個兩類二維樣本，其中正、負樣本均為200個，并在其中隨機地加入了2.5%的噪聲；測試樣本為200個隨機二維樣本，加入了2%的噪聲數(shù)據(jù)。四種支持向量機選擇的參數(shù)一致(C=100)，分類的正確率、支持向量的個數(shù)由表1給出；分類效果如圖2～圖5所示，圖中‘+’、‘*’分別代表正、負類樣本點，圈出來的樣本是支持向量。

Table 1 Classification results of four different SVMs表1 四種支持向量機分類結(jié)果

Figure 2 Classification results of SVM圖2 SVM的分類結(jié)果

Figure 3 Classification results of SFSVM圖3 SFSVM的分類結(jié)果

Figure 4 Classification results of KNN-FSVM圖4 KNN-FSVM的分類結(jié)果

Figure 5 Classification results of CCD-FSVM圖5 CCD-FSVM的分類結(jié)果

由圖2～圖5及表1可以看出，傳統(tǒng)SVM所獲得的支持向量中包含了大量的噪聲數(shù)據(jù)，這就使得構(gòu)造出的分類面存在偏差，從而影響了分類的精度；與SVM相比，雖然SFSVM的正確率與其相同，但是支持向量的個數(shù)卻大大減少。本文提出的CCD-FSVM將支持向量的個數(shù)減少至23個，并能有效地識別噪聲數(shù)據(jù)，極大降低了它們在構(gòu)造分類面過程中的作用，從而提高了分類的精度。

4.2 UCI標(biāo)準(zhǔn)數(shù)據(jù)集

選用UCI標(biāo)準(zhǔn)數(shù)據(jù)庫中的五個數(shù)據(jù)集：Pima Indians Diabetes(PD)、SPECT Heart(SPECT)、Haberman’s Survival、Breast Cancer Wisconsin Diagnostic (WDBC)和Statlog(Heart)進行實驗，每個數(shù)據(jù)集在實驗過程中被隨機地劃分成trn和tst兩個子集，表2統(tǒng)計了這些數(shù)據(jù)集的基本信息。本文進行的都是兩分類問題的實驗，其中核函數(shù)為RBF核函數(shù)。對于KNN-FSVM及CCD-FSVM中的參數(shù)k，實驗過程將其設(shè)定為2～14，然后記錄分類結(jié)果最好的k值。則當(dāng)參數(shù)C、σ取不同的值時，各數(shù)據(jù)集的實驗結(jié)果如表3～表7所示。

Table 2 Basic information of the data sets表2 數(shù)據(jù)集的基本信息

Table 3 Experimental results of SPECT表3 數(shù)據(jù)集SPECT的實驗結(jié)果

Table 4 Experimental results of WDBC表4 數(shù)據(jù)集WDBC的實驗結(jié)果

Table 5 Experimental results of PD表5 數(shù)據(jù)集PD的實驗結(jié)果

Table 6 Experimental results of Haberman表6 數(shù)據(jù)集Haberman的實驗結(jié)果

Table 7 Experimental results of Heart表7 數(shù)據(jù)集Heart的實驗結(jié)果

由表3～表7可以看出，本文提出的CCD-FSVM比傳統(tǒng)SVM的分類精度提高了很多。相對于基于樣本到類中心距離的SFSVM及k近鄰的KNN-FSVM，CCD-FSVM的抗噪性能最好，分類性能最強。這是因為區(qū)別于SFSVM、KNN-FSVM，CCD-FSVM通過引入類向心度，將樣本到類中心的距離、樣本點的k近鄰及k近鄰樣本本身的類別信息三者結(jié)合起來考慮。這不僅使得均異于k個近鄰的樣本點被視為噪聲點，而且對于混合部分的樣本點，k個近鄰樣本類別信息不同，它們相互抑制，從而獲得較小的隸屬度值，從而區(qū)分了有效樣本及噪聲或野值點。

5 結(jié)束語

基于樣本點與類中心之間的關(guān)系、樣本點與樣本點之間的關(guān)系，本文提出了一種基于類向心度的模糊支持向量機。該方法在處理混合區(qū)域的樣本時，還利用了其K近鄰樣本點本身的類別信息。從實驗結(jié)果可以看出，本文提出的方法，在分類精度上得到了有效的提高，從而證實了算法的有效性。

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

[2] Lin C F,Wang S D.Fuzzy support vector machine[J].IEEE Transactions on Neural Networks(S1045-9227),2002,13(2):464-471.

[3] Zhang Xiang,Xiao Xiao-ling,Xu Guang-you.Determination and analysis of fuzzy membership for SVM[J].Journal of Image and Graphics,2006,11(8):1188-1192.(in Chinese)

[4] Liu Chang,Sun De-shan.Determination method of membership of fuzzy SVM[J].Computer Engineering and Applic-ations,2008,44(11):41-43.(in Chinese)

[5] Cheng Jia,Sun De-shan.Approach of removing noises and outliers for SVM based on fuzzy membership[J].Computer Engineering and Design,2008,29(14):3730-3731.(in Chinese)

[6] Zhou Guang-qian,Xu Wei-hong,Yang Zhi-yong.A new fuzzy support vectors machine algorithm[J].Software Space,2010,26(10):217-218.(in Chinese)

[7] Zhang Hui.Improved fuzzy support vector machine and its application[J].Journal of Anhui Agricultural Sciences,2011,39(23):14406-14409.(in Chinese)

[8] Tao Qing,Wang Jue.A new fuzzy support vector machine based on the weighted margin[J].Neural Processing Letters,2004,20:139-150.

[9] Xiu Feng-jiang,Zhang Yi,Jian Cheng-lv.Fuzzy SVM with a new fuzzy membership function[J].Neural Comput & Applic,2006(15):268-276.

[10] He Qiang,Wu Cong-xin.Membership evaluation and feature selection for fuzzy support vector machine based on fuzzy rough sets[J].Soft Comput,2011(15):1105-1114.

[11] Sabzeka M,Yazdi H S,Naghibzadeh M.Relaxed constraints support vector machines for noisy data[J].Neural Comput & Applic,2011(20):671-685.

附中文參考文獻：

[3] 張翔,肖小玲,徐光佑.模糊支持向量機中隸屬度的確定與分析[J].中國圖像圖形學(xué)報,2006,11(8):1188-1192.

[4] 劉暢,孫德山.模糊支持向量機隸屬度的確定方法[J].計算機工程與應(yīng)用,2008,44(11):41-43.

[5] 程佳,孫德山.基于模糊隸屬度的支持向量機去噪方法[J].計算機工程與設(shè)計,2008,29(14):3730-3731.

[6] 周廣千,徐蔚鴻,楊志勇.一種新的模糊支持向量機算法[J].軟件時空,2010,26(10):217-218.

[7] 章慧.改進模糊支持向量機方法及其應(yīng)用[J].安徽農(nóng)業(yè)科學(xué),2011，39(23):14406-14409.

XUCui-yun,born in 1989,MS candidate,her research interest includes data mining.

Anovelfuzzysupportvectormachinebasedontheclasscentripetaldegree

XU Cui-yun,YE Ning

(School of Information Technology,Nanjing Forestry University,Nanjing 210037,China)

The traditional support vector machine (SVM) often falls into over-fitting when outliers are contained in the training data. The fuzzy support vector machine can effectively deal with this problem. According to the deficiency of the membership function designed based on the distance between a sample and its cluster center, a novel fuzzy support vector machine based on the class centripetal degree (CCD-FSVM) is proposed. It combines the distance between a sample and its cluster center with the relationship between samples expressed as the class centripetal degree. This function can effectively separate the valid samples from the noises or outliers. Besides, the size of the class centripetal degree can reflect the samples mixed degree. Experimental results show that the fuzzy support vector machine based on the class centripetal degree is more robust than the traditional support vector machine, and it outperforms the other two FSVM counterparts with different membership functions in terms of antinoise and classification performance.

fuzzy support vector machine;membership function;class centripetal degree

1007-130X(2014)08-1623-06

2012-09-13;

：2013-01-21

國家973計劃資助項目(2012CB114505)；國家杰出青年計劃資助項目(31125008)；江蘇省研究生創(chuàng)新基金資助項目(CXLX11_0525，CXZZ12_0527)；江蘇省青藍工程學(xué)術(shù)帶頭人；江蘇省六大人才高峰(電子信息類)

TP391.3

：A

10.3969/j.issn.1007-130X.2014.08.035

許翠云(1989-),女,江蘇如皋人，碩士生，研究方向為數(shù)據(jù)挖掘。E-mail:xcybljf@126.com

通信地址：210037 江蘇省南京市南京林業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院

Address:School of Information Technology,Nanjing Forestry University,Nanjing 210037,Jiangsu,P.R.China