雙支持向量順序回歸機

侯秋玲，楊志霞，周 哲

(新疆大學數學與系統科學學院，烏魯木齊 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—)，女，山東菏澤人，碩士研究生，主要從事最優化方法的研究。

(責任編輯 劉 舸)