基于类向心度的模糊支持向量机*

许翠云，业 宁

(南京林业大学信息科学技术学院，江苏 南京 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