侯秋玲，杨志霞，周 哲

(新疆大学数学与系统科学学院，乌鲁木齐 830046)

双支持向量顺序回归机

侯秋玲，杨志霞，周 哲

(新疆大学数学与系统科学学院，乌鲁木齐 830046)

针对顺序回归问题的深入研究，基于支持向量顺序回归机提出了双支持向量顺序回归机。由于双支持向量顺序回归机所对应的2个优化问题是对称的，则只需求解其中的一个问题，进而得出一个分划超平面。又因其对应的优化问题的规模只是支持向量顺序回归机规模的一半，故其运算速度会快于支持向量顺序回归机。数值实验的结果表明：双支持向量顺序回归机在一些数据分析中具有较高的正确率。

顺序回归问题;支持向量顺序回归机;双支持向量顺序回归机;顺序函数

在20世纪六七十年代，Vapnik等［1-2］就提出了统计学习理论的基本思想，并在90年代中期不断发展和成熟。基于该理论，Vapnik等［3-4］又于1995年提出了针对2类分类问题的支持向量机理论，被认为是机器学习领域中的革命性更新。近年来，支持向量机理论不断发展和成熟，已在模式识别［5］、文本分类［6］、脑机接口［7］、财务回归［8］等领域得到了较好的应用。

2006年，Mangasarian和Wild针对2类分类问题又提出了广义特征值中心支持向量机［9］。由该方法可以得到对应每类点的2个非平行超平面，而这2个非平行超平面是由2个相关的广义特征值问题的最小特征值所对应的特征向量决定的。

双支持向量机［10］与广义特征值中心支持向量机相似，其思想也是要求得到2个非平行的超平面，即由正类点确定的超平面和由负类点确定的超平面。而超平面的特点是到一类点的距离尽可能近，而另一类点的距离尽可能远，所以双支持向量机对应的是2个较小规模的优化问题，得到的是2个非平行的超平面，故与支持向量机相比，其运行时间更短。

Herbrich等于2000年提出的支持向量顺序回归机［11］因其良好的理论和特性得到了一定的应用［17］。支持向量顺序回归机是把顺序回归问题转化为一个2类分类问题，然后对转化后的2类分类问题建立支持向量机，从而得到最终的决策函数。然而，由于转化后的2类分类问题规模变大，使得优化问题的计算复杂度大幅提高。为克服该缺点，本文将顺序回归问题转化成2类分类问题，用双支持向量机进行求解。针对转化后的问题的对称性，该方法只需求解一个小规模的二次规划问题，计算复杂度是文献［11］中所提方法的1/8。

1 背景知识

1.1 支持向量机

给定训练集 D={(x1，y1)，…，(xl，yl)}，其中xi∈X⊂Rn，yi∈{-1，1}，i=1，…，l。寻找最优分划超平面：

H(w，b)：(w·x)+b=0

该超平面可通过求解下面的二次规划问题得到：

其中c(＞0)是惩罚参数。由于优化问题(1)的约束条件较多，通常求解其对偶问题［12］。最终决策函数的形式为

1.2 双支持向量机

给定训练集 D={(x1，y1)，…，(xl，yl)}，其中xi∈X⊂Rn，yi∈{-1，1}，i=1，…，l。记 A∈Rm1×n和B∈Rm2×n分别为D中正类点和负类点的输入所组成的矩阵，则有m1+m2=l。

双支持向量机要得到的2个非平行超平面通过求解下面的一对二次规划问题得到：

其中：c1和c2是惩罚参数;e1∈Rm1和 e2∈Rm2是由1 组成的向量;ξ1∈Rm1和 ξ2∈Rm2是与正类点和负类点对应的误差向量。双支持向量机虽然与支持向量机的格式相似，但其解决的却是2个小规模的优化问题。支持向量机的复杂性是O(l3)，而双支持向量机在其正负类点的个数都约为l/2的情况下，其复杂性却是O(2×(l/2)3)，所以两者运行时间之比为l3/［2×(l/2)3］=4，即双支持向量机的运行速度是支持向量机的4倍。

通过引入拉格朗日函数和KKT条件［13-15］，得到优化问题(2)和(3)的对偶问题如下：

其中 H=［A e1］，G=［B e2］。

(w1·x)+b1=0 和 (w2·x)+b2=0(6)

最终通过比较输入到式(6)中的2个超平面的距离来判断其所属类别的，即类别

其中|·|表示点x到超平面的垂直距离。

1.3 支持向量顺序回归机

假设输入空间为X(⊂Rn)，输出空间为Y={r1，r2，…，rq}，且输出的类别之间还存在着一种序的关系rq＞rq-1＞…＞r1。

则存在一系列的顺序函数f∈F，使得

其中 xi，xj∈X。

假设f是线性函数，即

将式(8)代入式(7)得xi＞xj⇔(w·(xi-xj)) ＞0。

优化问题(9)的对偶问题为：

任给一新的输入 x∈Rn，则其输出由下式给出：

2 双支持向量顺序回归机

2.1 线性情形

在本节中提出了解决顺序回归问题的新方法。

记A和B分别为S'中由正类点和负类点的输入组成的矩阵。由S'的特点可知：B=-A，即A和B都包含个训练点，则该模型对应的原始优化问题可表示为：

其中，c1和c2是惩罚参数;e1∈和 e2∈是由1组成的向量;q1∈和 q2∈是对应正类点和负类点的误差向量。由A和B的特点可知：式(12)和式(13)是同一个问题，下面只需求解式(12)。

与式(12)对应的拉格朗日函数为：

其中α和β是拉格朗日乘子向量。则得出KKT条件如下：

于是有 0≤α≤c1，w1=-(ATA)-1BTα。

所以式(12)的对偶问题为：

设式(14)的解为α*，则于是有顺序函数fw*(x)=(w*·x)。

另外补充定义 θ(r0)=-∞，θ(rq)=+∞。任给一新的输入x∈Rn，则其输出由下式给出：

图1(a)和图1(b)给出了最优阈值θ*(rk)的直观意义，即位于rk和rk+1类的有效用(作差后为支持向量的输入)的最靠近对象的中间。

图1 最优阈值的直观图示

下面给出线性情形时的算法：

2)选择适当的惩罚参数c1＞0;

4)由式(15)计算w*，则顺序函数fw*(x)=(w*·x);

5)由式(16)计算出θ(rk)，并且补充θ(r0)=-∞，θ(rq)=+∞;

6)决策函数由式(17)给出。

2.2 非线性情形

若顺序函数是非线性的，则对输入X引入非线性变换，然后用φ(x)代替x，再建立双支持向量顺序回归机模型。其对应的二次规划问题如下：

则优化问题(18)和(19)是同一个问题，下面只需求解式(18)。

记 E=K(A1，A2，C1，C2)，F=K(B1，B2，C1，C2)，对式(18)引入拉格朗日函数，运用KKT条件，得到对偶问题为：

设式(20)的解为α*，则

于是可以得到顺序函数为fu*(x)=(u*·(k(xT，C1)T-k(xT，C2)T))。

任给一新的输入x∈Rn时，则其输出由下式给出：

下面给出针对非线性情形时的算法：

1得到 A1、A2、B1、B2、C1、C2;

2)选择适当的核函数K、k及惩罚参数c1＞0;

4)由式(21)计算u*，则顺序函数fu*(x)=(u*·(k(xT，C1)T-k(xT，C2)T));

5)计算出 θ(rk)，并且补充 θ(r0)=-∞，θ(rq)=+∞;

6)决策函数由式(22)给出。

3 数值实验

为了验证双支持向量顺序回归机的分类准确率，构造了几组人工数据。

数据1是取一直线上的27个点，其输入和输出如表1所示。

表1 数据1

数据2是取一平面上的30个点，根据这30个点就可以从直观上确定分划线的大致位置。该数据对应的输入和输出如表2所示。

表2 数据2

首先考虑线性情形。数据1和数据2的运行时间及准确率如表3所示。

表3 数据1和数据2的运行时间及准确率

表3是通过十折交叉验证方法［16］计算的分类准确率。

接下来考察非线性情形。构造顺序函数为：f(x)=10(x1-0.5)(x2-0.5)，而决策函数为：y=i⇔10(x1-0.5)(x2-0.5)+ε∈［θ(ri-1)，θ(ri)］，其中 ε ～N(0，0.125)，θ=(- ∞，-1，-0.1，0.25，1，+∞)为预先定义的边界。

图2给出了由该顺序函数随机产生点的情形。

为了比较双支持向量顺序回归机和支持向量顺序回归机这2个不同的算法，随机选取10～30个包含每类点的数据进行训练，再随机选取150个点进行测试，得到的结果如表4所示。

图2 非线性情形下顺序函数随机产生点图

表4 2种算法对比结果

这2种算法都以Matlab(R2008a)为平台。

从上述实验结果可以看出：双支持向量顺序回归机的运行时间和正确率都优于支持向量顺序回归机。

4 结束语

针对顺序回归问题，本文提出了双支持向量顺序回归机。双支持向量顺序回归机首先把顺序回归问题转化为2类分类问题，然后再对转化后的2类分类问题运用双支持向量机进行求解。相比支持向量顺序回归机，双支持向量顺序回归机只需求解一个小规模的二次规划问题，因此后者比前者快很多。同时从数值实验的结果还可以看出，双支持向量顺序回归机应用于一些数据的分类具有较高的正确率。

本文虽然提出了双支持向量顺序回归机，但对此方法的理论分析及其在实际问题中的应用并没有涉及。因此，对此方法的理论分析、格式改进以及在实际问题中的应用将是下一步研究的重点。

［1］ Vapnik V N.Statistical learning theory［M］.New York，Wiley，1998.

［2］ Vapnik V.The nature of statistical learning theory［M］.New York，Springer，1995.

［3］ Cortes C，Vapnik V N.Support vector networks［J］.Machine Learning，1995，20(3)：273-297.

［4］ Cristianini C，Shawe-Taylor J.An introduction to support vector machines［M］.Cambridge University Press，2000：113-145.

［5］ Osuna E，Freund R，Girosi F.Training support vector machines：an application to face detection［C］//1997 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.［S.l.］：［s.n.］，1997：130-136.

［6］ Joachims T，Ndellec C，Rouveriol C.Text categorization with support vector machines：Learning with many relevant features［C］//In European Conference on Machine learning.［S.l.］：［s.n.］，1998：137-142.

［7］ Ebrahimi T，Garcia G N，Vesin J M.Joint time-frequencyspace classification of EEG in a brain-computer interface application［J］.Journal of Apply Signal Process，2003，1(7)：713-729.

［8］ Ince H，Trafalis T B.Support vector machine for regression and application to financial forecasting［C］//IEEE In International Joint Conference on Neural Networks.USA：［s.n.］，2002，6(6)：348-353.

［9］ Mangasarian O L，Wild E W.Multisurface proximal support vector classification via generalized eigenvalues［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2006，28(1)：69-74.

［10］ Jayadeva，Khemchandani R，Suresh C.Twin support vector machines for pattern classification［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2007，29(5)：905-910.

［11］ Herbrich R，Graepel T，Obermayer K.Large margin rank boundaries for ordinal regression［M］.Advances in Large Margin Classifiers，2000：115-132.

［12］邓乃扬，田英杰.支持向量机——理论、算法与拓展［M］.北京：科学出版社，2009.

［13］ Mangasarian O L.Unconstrained Lagrangians in Nonlinear Programming［J］.SIAM Journal on Control，1975，13(4)：772-791.

［14］王越，吕奇峰，王泉，等.一种改进的支持向量机序列最小优化算法［J］.重庆理工大学学报：自然科学版，2013，27(3)：76-79.

［15］邬啸，魏延，吴瑕.基于混合核函数的支持向量机［J］重庆理工大学学报：自然科学版，2011，25(10)：66-70.

［16］ Duda R O，Hart P R，Stork D G.Pattern Classification［M］.2nd edition，New York：John wiley and Sons，2001.

［17］张培林，钱林方，曹建军，等.基于蚁群算法的支持向量机参数优化［J］.南京理工大学学报：自然科学版，2009，33(4)：464-468.

Twin Support Vector Ordinal Regression

HOU Qiu-ling，YANG Zhi-xia，ZHOU Zhe
(College of Mathematics and System Science，Xinjiang University，Urumqi 830046，China)

With further research at ordinal regression，TSVOR which is in the spirit of SVOR is proposed.TSVOR determines a plane by solving a SVM-type problem，since the two related SVM-type problems are identical.It is faster than SVOR because the problem corresponding to it is smaller than that of SVOR on several benchmark datasets.Some experimental results indicate that TSVOR also hasa higher accuracy.

ordinal regression;SVOR;TSVOR;ranking function

TP18;O224

A

1674-8425(2013)10-0096-06

10.3969/j.issn.1674-8425(z).2013.10.021

2013-09-03

国家自然科学基金资助项目(11161045)

侯秋玲(1985—)，女，山东菏泽人，硕士研究生，主要从事最优化方法的研究。

(责任编辑 刘 舸)