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

許翠云，業 寧

(南京林業大學信息科學技術學院，江蘇 南京 210037)

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

許翠云，業 寧

(南京林業大學信息科學技術學院，江蘇 南京 210037)

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

模糊支持向量機；隸屬度函數；類向心度

1 引言

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

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

2 模糊支持向量機

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

(1)

其中，c為常數。

與標準支持向量機求解過程類似，首先構造拉格朗日函數:

(2)

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

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

(3)

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

(4)

根據KKT條件可知，最優解還應當滿足KT條件:

(5)

求得決策函數:

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

(6)

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

3 基于類向心度的隸屬度函數設計

3.1 基于距離的隸屬度函數

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

(1)線性可分情形。

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

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

r+=maxdi+，r-=maxdi-

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

(2)非線性可分情形。

引入樣本空間到特征空間的映射函數φ(x)，則特征空間中正、負類樣本的類中心變為φ(x+)、φ(x-)，則：

由上面的計算可設計出基于距離的隸屬度函數：

(7)

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

3.2 樣本緊密度的表示

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

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

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

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

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

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

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

(8)

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

(9)

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

(10)

其中:

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

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

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

(11)

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

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

(12)

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

結合樣本與類中心的關系及其樣本與樣本之間的關系，給出基于類向心度的隸屬度函數：

(13)

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

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

4 實驗結果與分析

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

4.1 人工數據集

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

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

Figure 2 Classification results of SVM圖2 SVM的分類結果

Figure 3 Classification results of SFSVM圖3 SFSVM的分類結果

Figure 4 Classification results of KNN-FSVM圖4 KNN-FSVM的分類結果

Figure 5 Classification results of CCD-FSVM圖5 CCD-FSVM的分類結果

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

4.2 UCI標準數據集

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

Table 2 Basic information of the data sets表2 數據集的基本信息

Table 3 Experimental results of SPECT表3 數據集SPECT的實驗結果

Table 4 Experimental results of WDBC表4 數據集WDBC的實驗結果

Table 5 Experimental results of PD表5 數據集PD的實驗結果

Table 6 Experimental results of Haberman表6 數據集Haberman的實驗結果

Table 7 Experimental results of Heart表7 數據集Heart的實驗結果

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

5 結束語

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

[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].中國圖像圖形學報,2006,11(8):1188-1192.

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

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

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

[7] 章慧.改進模糊支持向量機方法及其應用[J].安徽農業科學,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)；江蘇省研究生創新基金資助項目(CXLX11_0525，CXZZ12_0527)；江蘇省青藍工程學術帶頭人；江蘇省六大人才高峰(電子信息類)

TP391.3

：A

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

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

通信地址：210037 江蘇省南京市南京林業大學信息科學技術學院

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