基于pinball损失的一对一加权孪生支持向量机

李凯，李洁

(河北大学 网络空间安全与计算机学院，河北 保定 071002)

支持向量机(support vector machine，SVM)是由Vapnik等[1]提出的一种机器学习方法，一种基于统计学习理论的结构风险最小化准则和间隔最大化的思想，通过求解一个二次规划问题，以此获得一个最优分类超平面.为了解决SVM中计算复杂度过高的问题，Jayadeva等[2]提出了孪生支持向量机(Twin SVM，TWSVM)，通过求解2个较小的二次规划问题，确定2个非平行超平面，使得每个超平面都更接近一类而远离另一类，该方法进一步提高了计算速度.此后，人们在TWSVM的基础上提出了多种算法及其应用[3-9].

为了解决SVM和TWSVM中采用铰链损失函数的缺陷，研究人员采用pinball损失，提出了基于pinball损失的支持向量机和孪生支持向量机[10-12]，较好地解决了算法对噪声敏感的问题.另外，不论是SVM还是TWSVM，将所有样本视为同等重要，实际上，不同样本对分类超平面具有不同程度的影响，为此，人们将模糊理论引入到SVM和TWSVM中，提出了模糊支持向量机[13](Fuzzy SVM，FSVM)、模糊孪生支持向量机[14-15](Fuzzy TWSVM，FTWSVM)及其一些改进算法[16-17].通过对样本赋予不同权重的方法，提高了算法的噪声不敏感性.

可以看到，上述算法均适用于二类问题，然而，在实际应用中，多分类问题更加普遍.目前，用于多分类的孪生支持向量机主要分为如下几种[18-20]：

1)一对多孪生支持向量机.该方法在k个类中任意挑选一类作为正类，其余k-1类作为负类，并构造k个二分类器进行分类.

2)一对一孪生支持向量机.将一个多分类问题转化为一系列的2类问题进行求解.该算法在训练阶段对任意2类样本构造一个TWSVM，共构造k(k-1)/2个分类器进行分类，使用投票法对测试样本进行分类.

3)有向无环图支持向量机.在训练阶段类似于一对一孪生支持向量机，而在测试阶段，需要建立一个有向无环图，其中k个叶子结点对应k个类，每个内部节点对应一个二分类器，共k(k-1)/2个，待分类样本从根节点开始根据每个分类器的分类结果进行决策，直至叶结点得到对应的类别.

4)一对一对多孪生支持向量机[21].在一对一的思想上，将其余的k-2个类作为第3类与前2类分隔开，其最终分类结果为三元输出{-1，0，+1}.

5)其他解决方法[22].该方法在训练时使k类中的任意一类距离超平面最远，而其他k-1类距离超平面最近，对于待分类样本，需要决策该样本离超平面的距离来确定，即离哪个超平面最远则将此样本归为该类.

为了进一步提高孪生支持向量机的性能，将pinball损失函数与样本权重引入到多分类算法中，提出了一种基于pinball损失的一对一加权孪生支持向量机(Pin-OVO-STWSVM).用pinball损失函数代替一对一孪生支持向量机中的铰链损失函数，并通过引入权重方法，使得较重要的样本赋予较大的权值，而对噪声及异常值赋予较小的权重，以此区分不同样本的重要程度，该算法对噪声不敏感且训练时间短.实验中使用不同方法对样本赋予权值，并在具有不同噪声的人工数据集和UCI标准数据集[23]上进行了实验，结果表明，与一对一孪生支持向量机OVO-TWSVM、一对多孪生支持向量机OVA-TWSVM以及基于pinball损失的一对一孪生支持向量机Pin-OVO-TWSVM等方法对比，提出的Pin-OVO-STWSVM算法具有较好的性能.

1 相关工作

1.1 OVO-TWSVM

“一对一”(one-verus-one，OVO)是由Knerr将二类推广到多类问题提出的一种方法.对于k分类问题，需要2个阶段完成分类任务.在分解阶段，需要在k个类中任意选择2类样本，并使用SVM分类方法对其进行分类，通过此种方法需要构建k(k-1)/2个分类器，而每个分类器只需对2类样本进行分类；在重构阶段，根据每个分类器的分类结果投票给不同的类，并按照每一类所得票数确定待分类样本的类别.

为了克服SVM存在的缺陷，研究人员将TWSVM引入到OVO中，提出了OVO-TWSVM[20]，该方法不仅提高了分类准确率，同时使得训练时间减少到之前的1/4.假设A矩阵由m个样本点构成，其中A∈Rm×n.对于k分类问题，任意选取第i类和第j类，其优化问题如下：

1.2 损失函数

对于传统的SVM以及TWSVM，在建立相应模型时，主要使用了铰链损失函数，即

Lhinge(x,y,f(x))=max(0,1-yf(x))，

其中y和f(x)分别为理想值和预测值.由于铰链损失函数使用了最短距离，因此，易导致噪声敏感性和重采样的不稳定性.为此，人们对不同损失函数的SVM及TWSVM进行研究，其中pinball损失函数研究较为广泛.pinball损失函数定义如下：

其中τ∈[0，1].可以看到，pinball损失函数不仅对分类错误的样本进行惩罚，而且对分类正确的样本给出一个额外惩罚；另外，该函数使用了分位数距离，因此，对噪声不敏感，数据重采样更稳定，且不会增加计算成本.当pinball损失的参数趋于零时，损失函数成为铰链损失.

2 基于pinball损失的一对一加权孪生支持向量机

将pinball损失函数和权重引入到一对一策略的多分类孪生支持向量机中,用pinball损失代替传统的铰链损失，并针对不同样本的重要程度，为每一个样本赋予一个权重，从而得到基于pinball损失的一对一加权孪生支持向量机算法Pin-OVO-STWSVM.下面将分为2种情况进行介绍.

2.1 线性情况

给定一个k类训练数据集T={(xi，yi，Si)|i=1，2，…，m}，共包含m个样本，其中，xi∈Rn为训练样本数据，yi∈{1，2，…，k}为样本标签，Ai和Aj分别表示第i类和第j类的样本.线性Pin-OVO-STWSVM算法的目标是为k类中的任意2类样本找到一对非平行超平面.假设将第i类和第j类分开的超平面为

xTwi+bi=0 和xTwj+bj=0，

(1)

则获得2个超平面的第i类和第j类的优化问题为

(2)

(3)

其中c1>0和c2>0是平衡因子，ξi和ξj是松弛变量，ei和ej为全由1组成的列向量.

对于式(2)与(3)，与OVO-TWSVM的不同主要体现在目标函数的第2项和约束条件中，其中目标函数的第1项是第i类点到该类对应超平面距离的平方和；第2项是求误差变量的和，而Si和Sj分别是由第i类和第j类中样本的权重值所组成的向量，样本点的权重值越小，则该样本点的重要程度越低，反之，权重值越大则较为重要，因此，为每个误差变量乘上相应的权重值可以使误差对于分类问题的影响更准确；而约束条件使用了pinball损失，τ1，τ2∈[0，1]为参数.

下面以式(2)为例，使用拉格朗日方法对其求解，为此，构造拉格朗日函数

(4)

其中α≥0，β≥0是由拉格朗日乘子所组成的向量.

根据KKT(Karush-Kuhn-Tucker)条件可得

(5)

(6)

(7)

-(Ajwi+ejbi)≥ej-ξi,ξi≥0，

(8)

αT(-(Ajwi+ejbi)+ξi-ej)=0，

(9)

(10)

α≥0,β≥0.

(11)

进一步化简得到

(12)

令H=[Aiei]，G=[Ajej]，vi=[wibi]T，则式(12)变为

νi=-(HTH)-1GT(α-β).

(13)

为了防止HTH可能不适用的情况，引入一个正则化项δI，则式(13)变为

νi=-(HTH+δI)-1GT(α-β)，

(14)

其中δ是一个很小的正数，I是一个单位矩阵.

将式(14)带入到式(4)中得到

(15)

从而获得原问题的对偶问题如下：

(16)

其中γ=(α-β).

按照同样的方法，可以得到式(3)的对偶问题为

(17)

其中ρ=(σ-ε)，σ和ε为拉格朗日乘子，νj=[wjbj]T.

通过求解式(16)与(17)，从而获得 [wibi]T与[wjbj]T，即

(18)

当对新样本x分类时，需遍历k(k-1)/2个分类器，并对每个分类器的分类结果投票，则票数最高的类即为样本x所属类别.式(19)给出了使用第i类和第j类样本训练得到的分类器的决策函数，其中r为类标签，r=i或j

(19)

2.2 非线性情况

通过引入核函数，将线性情况推广到非线性情况中.利用核矩阵将输入样本映射到高维特征空间，使其在高维空间中实现线性可分，因此，决策面方程为

K(xT,CT)ui+bi=0和K(xT，CT)uj+bj=0,

(20)

其中CT=[AB]T，K(x1,x2)=φ(x1)φ(x2)，且φ是原空间到特征空间的映射.则非线性情况中第i类和第j类对应的优化问题

(21)

(22)

按照求解式(2)与(3)方法，得到式(21)与(22)的对偶问题如下：

(23)

(24)

其中γ=(α-β)，ρ=(σ-ε)，α、β、σ和ε为拉格朗日乘子，zi=[uibi]T，zj=[ujbj]T，通过求解对偶问题，进一步得到[uibi]T和[ujbj]T，即

(25)

当对新样本x分类时，与线性情况类似，只是决策函数有所不同，式(26)给出了使用第i类和第j类样本训练得到的分类器的决策函数，其中r为类标签，r=i或j

(26)

3 实验及结果分析

为了验证提出算法的性能，将OVO-TWSVM、OVA-TWSVM、 Pin-OVO-TWSVM与提出的算法Pin-OVO-STWSVM在UCI数据库中的12个标准数据集和4个人工生成数据集上进行实验.同时，为了检测提出算法的抗噪性，在数据集中分别添加了5%和10%的特征噪声，并检测其准确率.实验中高斯核函数为K(i，j)=exp(-p‖x-y‖2)，使用了10重交叉验证，并将10次测试的平均值及标准差作为最终的评价结果.采用网格搜索方法确定最优参数，参数c1和c2的搜索范围为{2i|i∈[-4，10]}；高斯核参数p的搜索范围为{2i|i∈[-4，10]}；pinball损失参数的τ1=τ2，其取值范围为{0.05，0.1，0.5}.

3.1 样本权重的确定方法

为了研究不同样本赋予不同权重时对分类结果的影响，使用3种确定权重值方法进行了实验，分别为类中心距离法、模糊C均值法和S型方法.

1)类中心距离法.根据每类中的样本距离该类中心的距离远近来定义其权重，距离类中心点越近的样本权重越大，距离越远权重越小.计算样本权重Si的方法如下：

其中di表示样本到该类类中心的距离，ri表示该类的半径，即距离类中心最远的样本到中心的距离.

2)模糊C均值法.利用模糊C均值聚类方法，获得每个样本的隶属度，并计算样本隶属每个簇程度的最大值，以此作为样本的权重.具体计算方法如下：

其中vj为聚类中心，sij为第i个样本在第j个簇中的权重，m为模糊加权指数.在聚类时，需要使用迭代方法获得sij和vj.

3)S型方法.根据样本距离该类中心的距离远近来确定权重，对类中心距离法中使用的线性函数用非线性函数替换，即

其中a和b为确定的参数并满足b=(a+c)/2，当di=b时，Si=0.5.

3.2 人工数据集

首先，随机生成了4个服从高斯分布的人工数据集，分别称为data_1、data_2、data_3和data_4，样本数分别为300、400、300和400，类别分别为3类、3类、4类和5类，其中data_1中的3类数据分别由两簇、三簇和三簇构成，data_2和data_4中每类均为一簇，data_3中的3类数据均为两簇，并且data_1、data_2和data_3中每类样本数量均相同，data_4中每类含有不同数量样本，如图1所示.实验中使用OVO-TWSVM，Pin-OVO-TWSVM和Pin-OVO-STWSVM 3种算法进行分类，实验结果如图2a所示，其中Pin-OVO-STWSVM算法采用模糊C均值法确定权重.

为了检测算法Pin-OVO-STWSVM的抗噪性，对每个数据集加入5%和10%的噪声，获得的数据集分别为data_1_n5、data_2_n5、data_3_n5、data_4_n5和data_1_n10、data_2_n10、data_3_n10、data_4_n10.同时与OVO-TWSVM和Pin-OVO-TWSVM算法进行了对比，实验结果如图2所示.

由图2a可以看出，提出的算法Pin-OVO-STWSVM在无噪声的人工生成数据集上具有较好的性能，其分类准确率均优于OVO-TWSVM和Pin-OVO-TWSVM 2种方法，而在图2b和图2c中，在加入不同比例的噪声后，其性能优于另2种分类算法.同时，使用3种不同确定权重的方法对提出的算法进行了测试，实验结果如图3所示.由图3可知，在3种确定权重的方法中，模糊C均值法较其他2种方法较为稳定，准确率也较高.

图1 人工数据集Fig.1 Artificial data sets

a.无噪声；b.5%噪声；c.10%噪声.图2 3种算法在含有噪声的人工数据集的准确率Fig.2 Accuracy of three algorithms for artificial data sets with noises

a.无噪声；b.5%噪声；c.10%噪声.图3 不同权重方法对算法准确率的影响Fig.3 Influence of different weighting methods on accuracy of algorithm

3.3 UCI数据集

为了进一步评价提出算法的性能，选用UCI数据库中的12个数据集，分别为Iris、Wine、Glass、Balance、Seeds、Vowel、Ecoli、Hayes-roth、Vehicle、Thyroid、CMC和Car，使用OVO-TWSVM、OVA-TWSVM、Pin-OVO-TWSVM和Pin-OVO-STWSVM 4种算法对数据集进行分类，并使用3种确定权重的方法进行实验，实验结果如表1所示.

表1 不同算法在标准数据集上的准确率和标准差

可以看出，提出的算法Pin-OVO-STWSVM在11个数据集上准确率优于OVO-TWSVM、OVA-TWSVM和Pin-OVO-TWSVM算法，对于Car数据集，测试结果也高于OVO-TWSVM算法.另外，由3种获取样本权值方法的实验结果可知，对于不同的数据集，使用不同确定样本权值的方法其效果是不同的，但这些方法较好地提高了分类准确率，且在12个数据集中，使用模糊C均值法确定权重，大多数数据集上均获得了较高的分类准确率.

同时，针对UCI中的数据集分别加入5%和10%的特征噪声，并与OVO-TWSVM、Pin-OVO-TWSVM和提出的算法Pin-OVO-STWSVM进行比较，实验结果如表2所示，其中样本的权重采用模糊C均值法确定，噪声采用均值为0且方差为1的高斯分布.可以看到，在12个数据集中，仅在Balance数据集添加5%的噪声和为Thyroid数据集添加10%噪声的情况下，准确率与OVO-TWSVM算法相当，而在其他数据集的分类结果均高于OVO-TWSVM算法.

表2 不同算法在加入噪声的标准数据集上的准确率和标准差

4 结论

通过对多分类中一对一策略的孪生支持向量机算法的研究，将pinball损失替换铰链损失且对样本赋予权重的方法，提出了基于pinball损失的一对一加权孪生支持向量机，较好地解决了多分类算法OVO-TWSVM中噪声敏感性与重取样不稳定问题，使用多种求取样本权重的方法，验证了提出方法的有效性.同时，与OVO-TWSVM、OVA-TWSVM和Pin-TWSVM等算法进行了比较，表明了Pin-OVO-STWSVM算法有效提高了多分类算法的性能.