侯秋玲，楊志霞，周 哲

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，烏魯木齊 830046)

雙支持向量順序回歸機(jī)

侯秋玲，楊志霞，周 哲

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，烏魯木齊 830046)

針對(duì)順序回歸問(wèn)題的深入研究，基于支持向量順序回歸機(jī)提出了雙支持向量順序回歸機(jī)。由于雙支持向量順序回歸機(jī)所對(duì)應(yīng)的2個(gè)優(yōu)化問(wèn)題是對(duì)稱(chēng)的，則只需求解其中的一個(gè)問(wèn)題，進(jìn)而得出一個(gè)分劃超平面。又因其對(duì)應(yīng)的優(yōu)化問(wèn)題的規(guī)模只是支持向量順序回歸機(jī)規(guī)模的一半，故其運(yùn)算速度會(huì)快于支持向量順序回歸機(jī)。數(shù)值實(shí)驗(yàn)的結(jié)果表明：雙支持向量順序回歸機(jī)在一些數(shù)據(jù)分析中具有較高的正確率。

順序回歸問(wèn)題;支持向量順序回歸機(jī);雙支持向量順序回歸機(jī);順序函數(shù)

在20世紀(jì)六七十年代，Vapnik等［1-2］就提出了統(tǒng)計(jì)學(xué)習(xí)理論的基本思想，并在90年代中期不斷發(fā)展和成熟?；谠摾碚?，Vapnik等［3-4］又于1995年提出了針對(duì)2類(lèi)分類(lèi)問(wèn)題的支持向量機(jī)理論，被認(rèn)為是機(jī)器學(xué)習(xí)領(lǐng)域中的革命性更新。近年來(lái)，支持向量機(jī)理論不斷發(fā)展和成熟，已在模式識(shí)別［5］、文本分類(lèi)［6］、腦機(jī)接口［7］、財(cái)務(wù)回歸［8］等領(lǐng)域得到了較好的應(yīng)用。

2006年，Mangasarian和Wild針對(duì)2類(lèi)分類(lèi)問(wèn)題又提出了廣義特征值中心支持向量機(jī)［9］。由該方法可以得到對(duì)應(yīng)每類(lèi)點(diǎn)的2個(gè)非平行超平面，而這2個(gè)非平行超平面是由2個(gè)相關(guān)的廣義特征值問(wèn)題的最小特征值所對(duì)應(yīng)的特征向量決定的。

雙支持向量機(jī)［10］與廣義特征值中心支持向量機(jī)相似，其思想也是要求得到2個(gè)非平行的超平面，即由正類(lèi)點(diǎn)確定的超平面和由負(fù)類(lèi)點(diǎn)確定的超平面。而超平面的特點(diǎn)是到一類(lèi)點(diǎn)的距離盡可能近，而另一類(lèi)點(diǎn)的距離盡可能遠(yuǎn)，所以雙支持向量機(jī)對(duì)應(yīng)的是2個(gè)較小規(guī)模的優(yōu)化問(wèn)題，得到的是2個(gè)非平行的超平面，故與支持向量機(jī)相比，其運(yùn)行時(shí)間更短。

Herbrich等于2000年提出的支持向量順序回歸機(jī)［11］因其良好的理論和特性得到了一定的應(yīng)用［17］。支持向量順序回歸機(jī)是把順序回歸問(wèn)題轉(zhuǎn)化為一個(gè)2類(lèi)分類(lèi)問(wèn)題，然后對(duì)轉(zhuǎn)化后的2類(lèi)分類(lèi)問(wèn)題建立支持向量機(jī)，從而得到最終的決策函數(shù)。然而，由于轉(zhuǎn)化后的2類(lèi)分類(lèi)問(wèn)題規(guī)模變大，使得優(yōu)化問(wèn)題的計(jì)算復(fù)雜度大幅提高。為克服該缺點(diǎn)，本文將順序回歸問(wèn)題轉(zhuǎn)化成2類(lèi)分類(lèi)問(wèn)題，用雙支持向量機(jī)進(jìn)行求解。針對(duì)轉(zhuǎn)化后的問(wèn)題的對(duì)稱(chēng)性，該方法只需求解一個(gè)小規(guī)模的二次規(guī)劃問(wèn)題，計(jì)算復(fù)雜度是文獻(xiàn)［11］中所提方法的1/8。

1 背景知識(shí)

1.1 支持向量機(jī)

給定訓(xùn)練集 D={(x1，y1)，…，(xl，yl)}，其中xi∈X?Rn，yi∈{-1，1}，i=1，…，l。尋找最優(yōu)分劃超平面：

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

該超平面可通過(guò)求解下面的二次規(guī)劃問(wèn)題得到：

其中c(＞0)是懲罰參數(shù)。由于優(yōu)化問(wèn)題(1)的約束條件較多，通常求解其對(duì)偶問(wèn)題［12］。最終決策函數(shù)的形式為

1.2 雙支持向量機(jī)

給定訓(xùn)練集 D={(x1，y1)，…，(xl，yl)}，其中xi∈X?Rn，yi∈{-1，1}，i=1，…，l。記 A∈Rm1×n和B∈Rm2×n分別為D中正類(lèi)點(diǎn)和負(fù)類(lèi)點(diǎn)的輸入所組成的矩陣，則有m1+m2=l。

雙支持向量機(jī)要得到的2個(gè)非平行超平面通過(guò)求解下面的一對(duì)二次規(guī)劃問(wèn)題得到：

其中：c1和c2是懲罰參數(shù);e1∈Rm1和 e2∈Rm2是由1 組成的向量;ξ1∈Rm1和 ξ2∈Rm2是與正類(lèi)點(diǎn)和負(fù)類(lèi)點(diǎn)對(duì)應(yīng)的誤差向量。雙支持向量機(jī)雖然與支持向量機(jī)的格式相似，但其解決的卻是2個(gè)小規(guī)模的優(yōu)化問(wèn)題。支持向量機(jī)的復(fù)雜性是O(l3)，而雙支持向量機(jī)在其正負(fù)類(lèi)點(diǎn)的個(gè)數(shù)都約為l/2的情況下，其復(fù)雜性卻是O(2×(l/2)3)，所以?xún)烧哌\(yùn)行時(shí)間之比為l3/［2×(l/2)3］=4，即雙支持向量機(jī)的運(yùn)行速度是支持向量機(jī)的4倍。

通過(guò)引入拉格朗日函數(shù)和KKT條件［13-15］，得到優(yōu)化問(wèn)題(2)和(3)的對(duì)偶問(wèn)題如下：

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

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

最終通過(guò)比較輸入到式(6)中的2個(gè)超平面的距離來(lái)判斷其所屬類(lèi)別的，即類(lèi)別

其中|·|表示點(diǎn)x到超平面的垂直距離。

1.3 支持向量順序回歸機(jī)

假設(shè)輸入空間為X(?Rn)，輸出空間為Y={r1，r2，…，rq}，且輸出的類(lèi)別之間還存在著一種序的關(guān)系rq＞rq-1＞…＞r1。

則存在一系列的順序函數(shù)f∈F，使得

其中 xi，xj∈X。

假設(shè)f是線(xiàn)性函數(shù)，即

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

優(yōu)化問(wèn)題(9)的對(duì)偶問(wèn)題為：

任給一新的輸入 x∈Rn，則其輸出由下式給出：

2 雙支持向量順序回歸機(jī)

2.1 線(xiàn)性情形

在本節(jié)中提出了解決順序回歸問(wèn)題的新方法。

記A和B分別為S'中由正類(lèi)點(diǎn)和負(fù)類(lèi)點(diǎn)的輸入組成的矩陣。由S'的特點(diǎn)可知：B=-A，即A和B都包含個(gè)訓(xùn)練點(diǎn)，則該模型對(duì)應(yīng)的原始優(yōu)化問(wèn)題可表示為：

其中，c1和c2是懲罰參數(shù);e1∈和 e2∈是由1組成的向量;q1∈和 q2∈是對(duì)應(yīng)正類(lèi)點(diǎn)和負(fù)類(lèi)點(diǎn)的誤差向量。由A和B的特點(diǎn)可知：式(12)和式(13)是同一個(gè)問(wèn)題，下面只需求解式(12)。

與式(12)對(duì)應(yīng)的拉格朗日函數(shù)為：

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

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

所以式(12)的對(duì)偶問(wèn)題為：

設(shè)式(14)的解為α*，則于是有順序函數(shù)fw*(x)=(w*·x)。

另外補(bǔ)充定義 θ(r0)=-∞，θ(rq)=+∞。任給一新的輸入x∈Rn，則其輸出由下式給出：

圖1(a)和圖1(b)給出了最優(yōu)閾值θ*(rk)的直觀意義，即位于rk和rk+1類(lèi)的有效用(作差后為支持向量的輸入)的最靠近對(duì)象的中間。

圖1 最優(yōu)閾值的直觀圖示

下面給出線(xiàn)性情形時(shí)的算法：

2)選擇適當(dāng)?shù)膽土P參數(shù)c1＞0;

4)由式(15)計(jì)算w*，則順序函數(shù)fw*(x)=(w*·x);

5)由式(16)計(jì)算出θ(rk)，并且補(bǔ)充θ(r0)=-∞，θ(rq)=+∞;

6)決策函數(shù)由式(17)給出。

2.2 非線(xiàn)性情形

若順序函數(shù)是非線(xiàn)性的，則對(duì)輸入X引入非線(xiàn)性變換，然后用φ(x)代替x，再建立雙支持向量順序回歸機(jī)模型。其對(duì)應(yīng)的二次規(guī)劃問(wèn)題如下：

則優(yōu)化問(wèn)題(18)和(19)是同一個(gè)問(wèn)題，下面只需求解式(18)。

記 E=K(A1，A2，C1，C2)，F(xiàn)=K(B1，B2，C1，C2)，對(duì)式(18)引入拉格朗日函數(shù)，運(yùn)用KKT條件，得到對(duì)偶問(wèn)題為：

設(shè)式(20)的解為α*，則

于是可以得到順序函數(shù)為fu*(x)=(u*·(k(xT，C1)T-k(xT，C2)T))。

任給一新的輸入x∈Rn時(shí)，則其輸出由下式給出：

下面給出針對(duì)非線(xiàn)性情形時(shí)的算法：

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

2)選擇適當(dāng)?shù)暮撕瘮?shù)K、k及懲罰參數(shù)c1＞0;

4)由式(21)計(jì)算u*，則順序函數(shù)fu*(x)=(u*·(k(xT，C1)T-k(xT，C2)T));

5)計(jì)算出 θ(rk)，并且補(bǔ)充 θ(r0)=-∞，θ(rq)=+∞;

6)決策函數(shù)由式(22)給出。

3 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證雙支持向量順序回歸機(jī)的分類(lèi)準(zhǔn)確率，構(gòu)造了幾組人工數(shù)據(jù)。

數(shù)據(jù)1是取一直線(xiàn)上的27個(gè)點(diǎn)，其輸入和輸出如表1所示。

表1 數(shù)據(jù)1

數(shù)據(jù)2是取一平面上的30個(gè)點(diǎn)，根據(jù)這30個(gè)點(diǎn)就可以從直觀上確定分劃線(xiàn)的大致位置。該數(shù)據(jù)對(duì)應(yīng)的輸入和輸出如表2所示。

表2 數(shù)據(jù)2

首先考慮線(xiàn)性情形。數(shù)據(jù)1和數(shù)據(jù)2的運(yùn)行時(shí)間及準(zhǔn)確率如表3所示。

表3 數(shù)據(jù)1和數(shù)據(jù)2的運(yùn)行時(shí)間及準(zhǔn)確率

表3是通過(guò)十折交叉驗(yàn)證方法［16］計(jì)算的分類(lèi)準(zhǔn)確率。

接下來(lái)考察非線(xiàn)性情形。構(gòu)造順序函數(shù)為：f(x)=10(x1-0.5)(x2-0.5)，而決策函數(shù)為：y=i?10(x1-0.5)(x2-0.5)+ε∈［θ(ri-1)，θ(ri)］，其中 ε ～N(0，0.125)，θ=(- ∞，-1，-0.1，0.25，1，+∞)為預(yù)先定義的邊界。

圖2給出了由該順序函數(shù)隨機(jī)產(chǎn)生點(diǎn)的情形。

為了比較雙支持向量順序回歸機(jī)和支持向量順序回歸機(jī)這2個(gè)不同的算法，隨機(jī)選取10～30個(gè)包含每類(lèi)點(diǎn)的數(shù)據(jù)進(jìn)行訓(xùn)練，再隨機(jī)選取150個(gè)點(diǎn)進(jìn)行測(cè)試，得到的結(jié)果如表4所示。

圖2 非線(xiàn)性情形下順序函數(shù)隨機(jī)產(chǎn)生點(diǎn)圖

表4 2種算法對(duì)比結(jié)果

這2種算法都以Matlab(R2008a)為平臺(tái)。

從上述實(shí)驗(yàn)結(jié)果可以看出：雙支持向量順序回歸機(jī)的運(yùn)行時(shí)間和正確率都優(yōu)于支持向量順序回歸機(jī)。

4 結(jié)束語(yǔ)

針對(duì)順序回歸問(wèn)題，本文提出了雙支持向量順序回歸機(jī)。雙支持向量順序回歸機(jī)首先把順序回歸問(wèn)題轉(zhuǎn)化為2類(lèi)分類(lèi)問(wèn)題，然后再對(duì)轉(zhuǎn)化后的2類(lèi)分類(lèi)問(wèn)題運(yùn)用雙支持向量機(jī)進(jìn)行求解。相比支持向量順序回歸機(jī)，雙支持向量順序回歸機(jī)只需求解一個(gè)小規(guī)模的二次規(guī)劃問(wèn)題，因此后者比前者快很多。同時(shí)從數(shù)值實(shí)驗(yàn)的結(jié)果還可以看出，雙支持向量順序回歸機(jī)應(yīng)用于一些數(shù)據(jù)的分類(lèi)具有較高的正確率。

本文雖然提出了雙支持向量順序回歸機(jī)，但對(duì)此方法的理論分析及其在實(shí)際問(wèn)題中的應(yīng)用并沒(méi)有涉及。因此，對(duì)此方法的理論分析、格式改進(jìn)以及在實(shí)際問(wèn)題中的應(yīng)用將是下一步研究的重點(diǎn)。

［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，F(xiàn)reund 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］鄧乃揚(yáng)，田英杰.支持向量機(jī)——理論、算法與拓展［M］.北京：科學(xué)出版社，2009.

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

［14］王越，呂奇峰，王泉，等.一種改進(jìn)的支持向量機(jī)序列最小優(yōu)化算法［J］.重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，27(3)：76-79.

［15］鄔嘯，魏延，吳瑕.基于混合核函數(shù)的支持向量機(jī)［J］重慶理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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］張培林，錢(qián)林方，曹建軍，等.基于蟻群算法的支持向量機(jī)參數(shù)優(yōu)化［J］.南京理工大學(xué)學(xué)報(bào)：自然科學(xué)版，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

國(guó)家自然科學(xué)基金資助項(xiàng)目(11161045)

侯秋玲(1985—)，女，山東菏澤人，碩士研究生，主要從事最優(yōu)化方法的研究。

(責(zé)任編輯 劉 舸)