一种改进的鲁棒模糊孪生支持向量机算法

周裕群，张德生，张 晓

西安理工大学 理学院，西安 710054

支持向量机（support vector machine，SVM）是由Cortes等人[1]提出的一种有效的机器学习算法，该算法被广泛应用于模式识别和数据分割等领域。SVM算法通过引入核函数，将非线性分类问题转化为某个高维特征空间中的线性分类问题，进而解决了小样本、非线性和维数灾难等问题。但是，SVM算法也存在以下几点不足：SVM算法在构建模型时，采用的是铰链损失函数，导致SVM算法对训练集中的噪声比较敏感；SVM算法在求解对偶问题时，计算成本较高；SVM算法使用平行平面来区分两类样本，而平行平面不一定符合数据的分布趋势。

针对SVM算法存在的不足，学者们提出了以下改进方法：文献[2]提出了广义特征值近端支持向量机算法（generalized eigenvalue proximal support vector machine，GEPSVM），该算法通过求解两个广义特征值问题来构建两个非平行超平面。基于GEPSVM算法的思想，文献[3]提出了孪生支持向量机算法（TWSVM），在运行速度上，TWSVM算法比SVM算法大约快4倍。但是，GEPSVM算法和TWSVM算法都没有考虑不同输入样本点对最优超平面的影响，为此，文献[4]提出了模糊支持向量机算法（fuzzy support vector machine，FSVM），文献[5]将TWSVM算法和FSVM算法结合，提出了模糊孪生支持向量机算法（fuzzy twin support vector machine，FTSVM），FTSVM算法在一定程度上降低了异常值对分类性能的影响。为了实现结构风险最小化，文献[6]在TWSVM算法中引入正则化项，进而提出了孪生有界支持向量机算法（twin bounded support vector machine，TBSVM）。文献[7-8]提出了基于pinball损失的支持向量机算法和孪生支持向量机算法，这两种算法在一定程度上降低了噪声对分类性能的影响。文献[9]提出了大规模最小二乘孪生支持向量机算法（large-scale least squares twin SVM，LS-LSTSVM），实验结果表明，该方法能够有效处理大规模数据集。文献[10]提出了一种密度加权的模糊孪生支持向量机算法，从而减小了不平衡数据的影响。文献[11]提出了一种新的模糊孪生支持向量机算法（NFTSVM），NFTSVM算法在一定程度上提高了算法的分类性能，然而，此方法需要计算复杂的逆矩阵，使其在一些应用上存在一定的局限性。文献[12]通过对TWSVM算法进行改进，提出了模糊简约孪生支持向量机算法，从而避免了逆矩阵运算。为了降低模型对样本集几何形状的依赖，文献[13]提出了基于类内超平面的模糊支持向量机算法。文献[14]将文献[13]应用到语音情感识别问题，提出了基于类内超平面距离度量模糊支持向量机的语音情感识别。

通过对FTSVM算法的改进，FTSVM算法已经成为了一种较为常用的分类算法，然而，FTSVM算法仍存在以下不足：（1）在FTSVM算法中，单纯基于样本点到类中心的距离确定的模糊隶属度函数不能有效区分异常值和有效样本点；（2）FTSVM算法只考虑了经验风险最小化，容易过拟合；（3）基于铰链损失的FTSVM算法考虑的是类间的最短距离，使得算法对噪声仍然敏感。

为了进一步提高FTSVM算法的分类性能，本文提出了一种改进的鲁棒模糊孪生支持向量机算法（IRFTSVM）。首先，确定了一种新的混合隶属度函数，降低了噪声或异常值对最优超平面的影响；其次，对FTSVM算法的目标函数做了一些改进，并通过构造新的拉格朗日函数的方式来避免逆矩阵运算；最后，用pinball损失函数代替铰链损失函数，在一定程度上达到了抗噪的效果。

1 预备知识

1.1 FTSVM算法

FTSVM算法[5]的两个非平行超平面分别为wT

1 x+b1=0和wT2x+b2=0，其中w1,w2,b1,b2∈Rn。在非线性情况下，引入核矩阵K(xT,CT)=φ(xT)·φ(CT)，其中CT=[A·B]T，K(x,y)为任意的核函数。同时，在取线性核函数时，令w1=CTu1，w2=CTu2，则FTSVM算法的优化问题为：

式（1）和式（2）的对偶问题分别如下：

其中H=[K(A,CT)e1]，G=[K(B,CT)e2]，α和β是由拉格朗日乘子所构成的列向量，m1和m2分别表示正类样本数和负类样本数。通过求解对偶问题（3）和（4），从而确定非平行超平面。

1.2 损失函数

FTSVM算法主要通过使用铰链损失函数来构建模型，其中铰链损失函数的定义[15]为：

其中y为理想值，f(x)为预测值。

铰链损失函数考虑的是类间的最短距离，导致模型中存在噪声敏感性以及数据重采样不稳定性等缺点。因此，学者们对不同的损失函数进行了深入研究，其中研究较为广泛的是pinball损失函数，pinball损失函数考虑的是分位数距离，在一定程度上降低了噪声敏感性。pinball损失函数的定义如下：

其中参数τ∈[0,1]。

2 IRFTSVM算法

2.1 隶属度函数的设计

经典的FTSVM算法[5]的隶属度函数的表达式如下：

其中di+和di-分别表示正类样本点和负类样本点到类中心的距离，ω表示一个很小的正数，r+=max{di+}，r-=max{di-}。

FTSVM算法在构造隶属度函数时，是通过式（7）来确定的，而该方法降低了接近超平面而远离类中心的样本点的影响。如图1给出了样本点的分类情况。

图1 样本点的分类情况Fig.1 Classification of sample points

在图1中，用黑色线表示样本点的分类面，图1（a）中的样本点A，B，C，D在分类面附近，而样本点C和样本点D距离类中心较远，若依据式（7）来确定隶属度，则会降低样本点C和样本点D的隶属度。图1（b）中的样本点A，B，C，D，E对于分类面的作用几乎相同，而到类中心的距离不同，从而被赋予了不同的隶属度值，其中E点更有可能被误判为异常值，若对于非球形分布的样本数据，误判率会更高。基于此，文献[13]提出了一种基于类内超平面的隶属度函数，即将样本点到类中心的距离替换为样本点到类内超平面的距离。具体表达式如下：

其中δ是一个足够小的正数，使得qi满足qi∈(0,1]，di+和di-分别表示正类样本点和负类样本点到类内超平面的距离，

虽然基于类内超平面的FTSVM算法减少了模型对样本集几何形状的依赖。但不足的是，基于样本点到类内超平面的距离来确定隶属度函数忽略了样本的紧密程度，从而影响了分类性能。为了更加直观地体现这一问题，图2给出了两个不同类别样本点间的紧密度差别，并对其进行了解释。

图2 样本间紧密度的差别Fig.2 Difference of sample affinity

在图2（a）和图2（b）中，假设H1和H2分别表示图2（a）和图2（b）中的超平面。从图2可以发现：样本点x到超平面H1的距离大于样本点x到超平面H2的距离，若单纯地通过式（8）来确定隶属度，则图2（a）中的样本点x的隶属度比图2（b）中的样本点x的隶属度小。但是，图2（a）中的样本点x到其他样本点的距离比图2（b）中的样本点x到其他样本点的距离近，即图2（a）中的样本点x与其附近样本点的紧密度比图2（b）中的样本点x与其附近样本点的紧密度高，图2（a）中的样本点x比图2（b）中的样本点x更有可能成为有效样本点，则图2（a）中的样本点x应被赋予更大的隶属度才更加合理。

因此，为了能够更好地反映样本点的不确定性，本文在基于类内超平面的隶属度函数的基础上进一步引入了k近邻隶属度函数，并对k近邻隶属度函数做了改进，从而构造了一种新的混合隶属度函数。下面对改进的k近邻隶属度函数和混合隶属度函数的定义进行描述，具体如下：

取样本点xi以及与它距离最近的k个样本，并将这k个样本记为xj(j=1,2,…,k)，xi与这k个样本点的距离分别为di1,di2,…,dik。若用1/(dij+ε)表示第j个近邻对该样本点所产生的类别影响因子，则样本紧密度ti的表达式[16]为：

其中ε是一个足够小的正数，在线性情形下dij=‖xi-xj‖，在非线性情形下

标准化后的ti为=ti Ti，其中Ti=max{t1,t2,…,tm}，m表示总样本数，从式（9）可以看出：k近邻只体现了样本间的距离关系，并未考虑样本点和其k个近邻所属类别的不同。因此，本文对k近邻隶属度函数进行了适当调整，具体分为以下三种情况：（1）如果样本点与其k个近邻样本在同一类别，没有混淆时，则-ti保持不变；（2）如果样本点与其k个近邻样本均在不同类别时，则认为该样本点是噪声，将样本点的隶属度赋值为0；（3）如果样本点与其k个近邻样本有一部分在同一类别，而其余部分存在混淆时，则应该适当减少-ti的值。综上，改进后的k近邻隶属度函数为：

其中l表示样本点xi的k个近邻中与xi不同类别的标签个数，且有0≤l≤k。

结合式（8）和式（10），确定了一种新的混合隶属度函数，该函数的表达式为：

新隶属度函数不仅考虑了样本集的几何形状，还分析了k个近邻样本点的所属类别。由混合隶属度函数可知：当k近邻确定的样本紧密度一定时，则基于类内超平面隶属度函数qi与隶属度si的值成反比；当qi一定时，如果样本紧密度越高以及混淆程度越低时，则隶属度si的值越大。

2.2 改进的线性IRFTSVM算法

集合T={(xi,yi,si),i=1,2,…,m1,m1+1,m1+2,…,m1+m2}，其中xi∈Rn表示输入的特征向量，yi∈表示相应的类标签，隶属度si∈[0,1]。在n维数据集中，将正类样本用矩阵Am1×n=(x1,x2,…,xm1)T以及负类样本用矩阵Bm2×n=(xm1+1,xm1+2,…,xm1+m2)T表示，则IRFTSVM算法的优化问题为：

其中ci(i=1,2,3,4)为惩罚参数，ξ1和ξ2为松弛变量，e1和e2表示全为1的列向量，η1和η2为合适维度的向量，sA和sB表示正类样本和负类样本权重值所组成的向量。约束条件使用了pinball损失函数，且参数τ∈[0,1]。

通过拉格朗日乘子法对问题（12）和（13）求解，式（12）的拉格朗日函数如下：

其 中α=(α1,α2,…,αm2)T, α≥0, β=(β1,β2,…,βm1)T,β≥0以及γ=(γ1,γ2,…,γm2)T, γ≥0。根据KKT条件，对式（14）中的w1，b1，η1和ξ2求偏导数，并令其为零，得到以下等式：

由式（15）和（16）化简可得：

令α-γ=μ，且γ≥0，因此，式（18）被重新写为μ+γ(1+1 τ)=c1sAe2，将式（22）和（23）代入拉格朗日函数（14），并根据以上等式，求得式（12）的对偶问题：

其中I表示m1阶的单位矩阵，矩阵E表示所有元素全为1的m1+m2阶方阵。

通过对偶问题（24）和（25）求得拉格朗日乘子向量α、β和γ的最优解，将其代入式（22）和（23），进一步求得w1和b1的值，即可确定非平行超平面wT1x+b1=0。按照同样的方法，求解优化问题（13）中的w2和b2以及对偶问题，具体表达式如下：

其中λ-ρ=ψ，ρ≥0，其中I表示m2阶的单位矩阵，矩阵E是所有元素全为1的m1+m2阶方阵。

在线性情况下，IRFTSVM算法的具体步骤如算法1所示：

算法1线性IRFTSVM算法

输入：训练样本集T，隶属度函数中的参数ε,δ和k以及预测样本点x。

输出：测试样本y的类别。

1.利用网格搜索法，选取惩罚参数ci(i=1,2,3,4)，pinball损失参数τ；

2.根据公式(11)计算隶属度；

3.根据式（24），（25），（28）和（29）求得向量(α,γ,β)和(θ,λ,ρ)的最优解；

4.根据式（22），（23），（26）和（27）求得原始问题w1, b1和w2, b2的解，确定非平行超平面wT1x+b1=0和wT2x+b2=0；

5.计算新样本点x到超平面wT1x+b1和wT2 x+b2的垂直距离，分别记为dist+1和dist-1；

6.若dist+1＞dist-1，则认为样本点x为-1类，否则x为+1类。

2.3 改进的非线性IRFTSVM算法

与经典的FTSVM算法不同的是：IRFTSVM算法不用考虑核生成的曲面，而是引入核函数K(xi,xj)=(φ(xi) · φ(xj))，直接将其运用到式（24）、（25）、（28）以及（29）中。

对x进行相应的变换，即X=φ(x) ，其中X∈H，H为希尔伯特空间，则训练样本集T~={(Xi,yi,si) , i=1,2,…,m1,m1+1,m1+2,…,m1+m2}，因此，分类超平面的优化问题为：

在非线性情况下，IRFTSVM算法与SVM算法的形式类似，通过使用核技巧，式（29）和（30）的对偶问题可以直接从线性情形演变而来，使得模型变得简单易行。具体表达式为：

每个类对应的非平行超平面为：

若求得拉格朗日乘子向量(α,γ,β)和(θ,λ,ρ)，非平行超平面（36）和（37）即可被确定。

在非线性情况下，IRFTSVM算法的具体步骤如算法2所示：

算法2非线性IRFTSVM算法

输入：训练样本集T，隶属度函数中的参数ε,δ和k以及预测样本点x。

输出：测试样本y的类别。

1.选择核函数K，利用网格搜索法，选取惩罚参数ci(i=1,2,3,4)，pinball损失参数τ以及高斯核参数σ；

2.根据公式（11）计算隶属度；

3.根据式（32），（33），（34）和（35）求解(α,γ,β)和(θ,λ,ρ)的最优解；

4.根据式（36）和（37）构造非平行超平面；

5.计算新样本点x到超平面（36）和（37）的垂直距离，分别记为dist+1和dist-1；

6.若dist+1＞dist-1，则认为样本点x为-1类，否则x为+1类。

2.4 IRFTSVM时间复杂度分析和算法描述

在本节中，对FTSVM算法和IRFTSVM算法的时间复杂度进行了分析与比较。

假设训练样本的总数为m，且正类样本数和负类样本数相等，即约为m/2。在FTSVM算法中，FTSVM算法的时间复杂度[5]约为O(2×(m/2)2)，即O(m3)/4；在IRFTSVM算法中，求解隶属度所花费的时间复杂度约为O(m)，IRFTSVM算法在求解对偶问题时，由于矩阵规模较大，使得时间复杂度较高，即求解两个二次规划问题所需要花费的时间复杂度约为O(m3)。则IRFTSVM算法的总时间复杂度约为O(m+m3)，即约为O(m3)，IRFTSVM算法的时间复杂度比FTSVM算法高了4倍左右。

尽管IRFTSVM算法的时间复杂度高于FTSVM算法，但是IRFTSVM算法不需要像FTSVM算法一样计算复杂的逆矩阵，且模拟实验结果表明，本文算法的平均准确率均高于FTSVM算法。

为了能够更加直观体现本文算法的思想，如图3给出了IRKFTSVM算法的流程图。

图3 IRFTSVM算法流程图Fig.3 Flow chart of IRFTSVM algorithm

3 仿真实验与分析

3.1 数据集

选用人工数据集Ripley[17]和UCI中的12个常用数据集进行实验。Ripley数据集包含250个训练样本点，1 000个测试样本点，特征维数为2。表1和表2列出了UCI数据集的相关信息。

表1 UCI数据集Table 1 UCI datasets

表2 含有不同噪声比例的数据集Table 2 Datasets with different noise ratios

3.2 实验设计和参数设置

所有实验均在Matlab 2016a中完成，用十折交叉验证法评估本文算法与SVM、TWSVM、FTSVM、TBSVM以及PTSVM算法的平均准确率，实验中采用的核函数为线性核函数K(x,xi)=x·xi和高斯核函数K(x,xi)=exp(-‖x-xi‖22σ2)。

令模糊隶属度函数中的参数k=10，δ和ε均取值为0.05。为了简化参数调节，令c1=c2，c3=c4。采用网格搜索法[18]对高斯核参数σ、惩罚参数ci(i=1,2,3,4)和pinball损失函数中参数τ进行筛选，其中参数σ和ci(i=1,2,3,4)均在{2i|i=-8,-7,…,8}范围内确定，参数τ在{ }0.01,0.2,0.5,1.0范围内搜索。

3.3 实验结果与分析

下面通过4个实验来验证IRFTSVM算法的有效性。用准确率（ACC）作为分类性能的评价标准，准确率的计算公式如下：

其中TP、FP、TN、FN分别表示正确分类的正类样本数、错误分类的正类样本数、正确分类的负类样本数以及错误分类的负类样本数。

3.3.1 人工数据集实验结果及分析

实验1为了验证本文算法的分类性能，在人工数据集Ripley上进行实验。在等效条件下，如图4和图5展示了这6种算法在线性情形下和非线性情形下Ripley数据集上的最优超平面。表3给出了本文算法与SVM、TWSVM、FTSVM、TBSVM以及PTSVM算法在线性核和高斯核下的平均准确率。

表3 IRFTSVM算法与其他5种算法的平均准确率Table 3 Average accuracy of IRFTSVM and other five algorithms 单位：%

在图4和图5中，SVM算法中的黑色曲线为最佳决策超平面，蓝色曲线和红色曲线分别表示正类样本点和负类样本点的决策边界，而其余5种分类算法中的黑色曲线为分类线，红色曲线和蓝色曲线表示相应算法的最佳决策超平面。则可以得出：SVM算法只有一个决策超平面，其余5种算法有两个决策超平面，进而通过样本点到这两个超平面的距离来确定该样本的类别。

图5 在非线性情况下6种算法的模拟结果Fig.5 Simulation results of six algorithms in nonlinear case

从表3的结果可以看出：在线性情况下，IRFTSVM算法相对于TWSVM、TBSVM、FTSVM和PTSVM算法，它的平均准确率分别提高了0.27、0.18、0.26和0.32个百分点，而仅对于SVM算法，IRFTSVM算法的平均准确率降低了0.21个百分点；在非线性情况下，本文算法的分类性能均高于其他5种对比算法，其中相对于TWSVM算法，IRFTSVM算法的平均准确率提高了3.02个百分点，说明了本文算法在一定程度上提高了模型的泛化能力。

3.3.2 UCI数据集实验结果及分析

实验2为了验证本文所构造的混合隶属度函数的有效性，将本文算法与基于样本点到类内超平面计算隶属度的IRFTSVM算法（命名为IRFTSVM_H）以及式（10）计算隶属度的IRFTSVM算法（命名为IRFTSVM_K）进行比较，运用表2中的Vote、Breast和Splice这3个数据集。图6和图7分别是这3种算法在线性核和高斯核下的平均准确率。

图6和图7的结果表明：在线性核下，对于数据集Vote和Splice，本文提出的IRFTSVM算法的平均准确率是最高的，仅在数据集Breast不含噪声的情况下，本文算法的平均准确率相对于IRFTSVM_H算法略有下降；在高斯核下，在Vote、Breast和Splice这3个数据集中，本文算法的平均准度率均高于其他两种对比算法，当含噪量为10%时，表现结果较为明显。说明了将基于样本点到类内超平面的隶属度函数和改进的k近邻隶属度结合是有效的。

图6 3种算法在线性核下不同噪声比例的模拟结果Fig.6 Simulation results of three algorithms with different noise ratios using linear kernel

图7 3种算法在高斯核下不同噪声比例的模拟结果Fig.7 Simulation results of three algorithms with different noise ratios using Gaussian kernel

实验3为了验证本文所引入的pinball损失函数在噪声影响下的有效性，将基于铰链损失函数的IRFTSVM算法（命名为Hinge-IRFTSVM）和基于pinball损失函数的IRFTSVM算法（命名为Pin-IRFTSVM）分别在不含噪声、含5%的噪声以及含10%的噪声的数据集中进行测试，选取表2中的Diabetes、Liverdisorder、Haberman和Blood这4个数据集进行实验。图8和图9分别是这两种算法在线性核和高斯核下的平均准确率，其中横坐标表示数据集，纵坐标表示在不同数据集上对应的平均准确率。

实验4为了进一步验证IRFTSVM算法的有效性，将IRFTSVM算法与SVM、TWSVM、FTSVM、TBSVM以及PTSVM算法进行对比。运用表1中的UCI数据集进行实验，表4和表5给出了本文算法与其他5种对比算法分别在线性核和高斯核下的平均准确率。

表4 在线性核下IRFTSVM与对比算法的平均准确率Table 4 Average accuracy of IRFTSVM and comparison algorithms with linear kernel 单位：%

表5 在高斯核下IRFTSVM与对比算法的平均准确率Table 5 Average accuracy of IRFTSVM and comparison algorithms with Gaussian kernel 单位：%

从图8和图9的结果可以看出：在线性核函数下，当含噪量为5%和10%时，基于pinball损失的IRFTSVM算法在所有数据集中的平均准确率均高于基于铰链损失的IRFTSVM算法，然而，仅在不含噪声时，pinball损失的IRFTSVM算法在数据集Diabetes中的准确率略低于基于铰链损失的IRFTSVM算法；在非线性核函数下，当含噪量为5%和10%时，基于pinball损失的IRFTSVM算法在所有数据集中的平均准确率均高于基于铰链损失的IRFTSVM算法，而当不含噪声时，pinball损失的IRFTSVM算法在Diabetes和Liverdisorder两个数据集中的准确率低于基于铰链损失的IRFTSVM算法，体现了将铰链损失函数替换为pinball损失函数，可以降低算法对噪声的敏感性。

图8 两种算法在线性核下不同噪声比例的模拟结果Fig.8 Simulation results of two algorithms with different noise ratios using linear kernel

图9 两种算法在高斯核下不同噪声比例的模拟结果Fig.9 Simulation results of two algorithms with different noise ratios using Gaussian kernel

从表4和表5的结果可以看出：在线性核下，IRFTSVM算法在Pima、Heart、Hepatitis、Australian、German、WDBC和WPBC数据集中的分类性能最佳，而在Ionosphere数据集中，IRFTSVM算法的平均准确率相对TBSVM算法仅降低了0.06个百分点，在Sonar数据集中，IRFTSVM算法的平均准确率比SVM算法降低了0.50个百分点；在高斯核下，相对于其他5种对比算法，IRFTSVM算法在9个数据集上的平均准确率均有所提高，说明了本文所改进的算法是有效的。

4 结束语

针对FTSVM算法存在的一些问题，本文对其进行了改进，提出了一种改进的鲁棒模糊孪生支持向量机算法（IRFTSVM）。IRFTSVM算法通过引入新的混合隶属度函数，提高了算法的分类性能，此外，构造了与以往不同的拉格朗日函数，从而避免了逆矩阵运算，而且可以直接使用核技巧将线性问题扩展到非线性问题，不需要像FTSVM算法一样重新构造非线性问题。实验结果表明，IRFTSVM算法能够较好地解决分类问题，并且在分类性能上取得了令人满意的结果。由于IRFTSVM算法存在计算时间复杂度高以及只涉及到二分类等问题，因此，降低时间复杂度和将二分类问题扩展到多分类问题将是下一步的主要研究方向。