許翠云，業(yè) 寧

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

基于類向心度的模糊支持向量機(jī)*

許翠云，業(yè) 寧

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

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

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

1 引言

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

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

2 模糊支持向量機(jī)

為了提高支持向量機(jī)對(duì)噪聲、野值點(diǎn)數(shù)據(jù)的抵抗力，模糊支持向量機(jī)在原有的基礎(chǔ)上，給每個(gè)訓(xùn)練樣本賦予不同的隸屬度值。利用FSVMs進(jìn)行分類時(shí)，需要對(duì)樣本數(shù)據(jù)進(jìn)行模糊化的預(yù)處理，即根據(jù)選擇的隸屬度函數(shù)，計(jì)算每個(gè)樣本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)支持向量機(jī)求解過程類似，首先構(gòu)造拉格朗日函數(shù):

(2)

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

變量w、b和ξ在鞍點(diǎn)處滿足如下條件：

(3)

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

(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時(shí)，對(duì)應(yīng)的xi為支持向量；當(dāng)αi=0，ξi=0時(shí)，對(duì)應(yīng)的xi被正確分類；支持向量有兩種類型：普通的支持向量及邊界支持向量，若xi是普通的支持向量，則0<αi

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

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

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

(1)線性可分情形。

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

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

r+=maxdi+，r-=maxdi-

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

(2)非線性可分情形。

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

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

(7)

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

3.2 樣本緊密度的表示

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

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

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

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

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

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

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

(8)

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

(9)

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

(10)

其中:

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

(1)計(jì)算樣本xi的k個(gè)近鄰。

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

(11)

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

(3)針對(duì)(2)中否的情況，在計(jì)算出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)樣本與類中心的距離一定時(shí)，樣本的隸屬度調(diào)整幅度與樣本之間的緊密度成反比；(2)當(dāng)類向心度一定時(shí)，隸屬度大小與樣本距類中心之間的距離成反比；(3)當(dāng)k近鄰一定時(shí)，如果近鄰中存在混合，則它們對(duì)分類的綜合作用是削弱的，該樣本點(diǎn)的隸屬相對(duì)比較小。這樣可以將式(13)直接用到模糊支持向量機(jī)中。

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

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

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

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

Table 1 Classification results of four different SVMs表1 四種支持向量機(jī)分類結(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的正確率與其相同，但是支持向量的個(gè)數(shù)卻大大減少。本文提出的CCD-FSVM將支持向量的個(gè)數(shù)減少至23個(gè)，并能有效地識(shí)別噪聲數(shù)據(jù)，極大降低了它們?cè)跇?gòu)造分類面過程中的作用，從而提高了分類的精度。

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

[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.

附中文參考文獻(xiàn)：

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

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

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

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

[7] 章慧.改進(jìn)模糊支持向量機(jī)方法及其應(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計(jì)劃資助項(xiàng)目(2012CB114505)；國家杰出青年計(jì)劃資助項(xiàng)目(31125008)；江蘇省研究生創(chuàng)新基金資助項(xiàng)目(CXLX11_0525，CXZZ12_0527)；江蘇省青藍(lán)工程學(xué)術(shù)帶頭人；江蘇省六大人才高峰(電子信息類)

TP391.3

：A

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

許翠云(1989-),女,江蘇如皋人，碩士生，研究方向?yàn)閿?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