盧振興，楊志霞，高新豫

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

最小二乘雙支持向量回歸機

盧振興，楊志霞，高新豫

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

1 引言

支持向量機（Support Vector Machine，SVM）[1-2]主要用于解決分類問題和回歸問題[3-4]。它是基于結構風險最小化原則[2]的一種方法，在機器學習領域中備受關注，近些年得到了飛速的發(fā)展。然而，基于支持向量機的回歸算法，并不像分類算法發(fā)展得那么完善。目前基于支持向量機的回歸算法主要有支持向量回歸機[5]（Support Vector Regression，SVR）、最小二乘支持向量回歸機[6-7]（Least Square Support Vector Regression，LSSVR）和雙支持向量回歸機[8]（Twin Support Vector Regression，TWSVR）等。傳統(tǒng)的支持向量回歸機是通過求解一個二次規(guī)劃問題來得到最終的回歸函數(shù)，計算復雜度相對較高。最小二乘支持向量回歸機只需求解一個線性方程組，其計算復雜度比傳統(tǒng)的支持向量回歸機降低了很多。2009年，文獻[8]提出了雙支持向量回歸機。它是受雙支持向量分類機[9]的啟發(fā)，不像傳統(tǒng)支持向量機用兩個平行超平面構造回歸函數(shù)，而是用兩個非平行超平面構造回歸函數(shù)，因此雙支持向量回歸機具有更好的推廣能力。雙支持向量機的另一個優(yōu)點是通過求解兩個較小規(guī)模的二次規(guī)劃得到最終的回歸函數(shù)，比傳統(tǒng)支持向量回歸機的計算復雜度低。

本文提出了最小二乘雙支持向量回歸機（Least Square Twin Support Vector Regression，LSTSVR），它整合了最小二乘思想和雙支持向量回歸機的思想，即在雙支持向量回歸機的基礎之上加入了最小二乘的思想，同樣是通過兩個非平行平面構造最終的回歸函數(shù)。不同的是，最小二乘雙支持向量回歸機只需解兩個較小規(guī)模的線性方程組就能得到最終的回歸函數(shù)，而不是像雙支持向量回歸機那樣求解兩個二次規(guī)劃，這樣就大大降低了計算復雜度。數(shù)值實驗表明，最小二乘雙支持向量回歸機不僅計算速度快，而且有更好的預測精度。

2 背景知識

首先給出回歸問題的數(shù)學描述，給定訓練集：

其中 xi∈Rn是輸入，yi∈R是輸出，i=1，2，…，l。

在本文中，用X表示由所有的輸入xi構成的矩陣，Y表示由所有的輸出 yi構成的列向量。本文的任務是找到如下的回歸函數(shù)[10]：

傳統(tǒng)的支持向量回歸機的思想源于支持向量分類機，它利用最大間隔的思想，通過結構風險最小化原則建立了一個二次規(guī)劃的原始問題，通常求解其對偶問題[11]來得到原始問題的解，即可得式（2）。當引入核函數(shù)[12]后，很容易將線性模型擴展到非線性模型。

文獻[6-7]中提出了最小二乘支持向量回歸機，它主要是將最小二乘的思想融入到支持向量回歸機的模型中，其思想源于最小二乘支持向量分類機[7]，用等式約束代替?zhèn)鹘y(tǒng)的支持向量回歸機中的不等式約束，從而只需解一組線性方程組就可以得到問題的解，即可得到式（2），花費的時間大大減少，計算成本也相應降低，所以常被用于解決樣本點規(guī)模較大的問題。

雙支持向量回歸機于2009年在文獻[8]中被提出，它的靈感來源于雙支持向量分類機[9]。雙支持向量回歸機需要找到兩個非平行超平面，稱之為上界和下界回歸函數(shù)。

雙支持向量回歸機由下面兩個優(yōu)化問題構成：

3 最小二乘雙支持向量回歸機

這一章提出了一個新的回歸算法，它的思想來源于雙支持向量回歸機，稱它為最小二乘雙支持向量回歸機，是將最小二乘的思想運用到雙支持向量回歸機中而建立的。

3.1 線性情形

考慮線性情形，最小二乘雙支持向量機的原始優(yōu)化問題為：

其中 C1，C2＞0 是懲罰參數(shù)，ε1，ε2＞0 是 ε不敏感損失函數(shù)[11]的參數(shù)，ξ，η是松弛因子。最小二乘雙支持向量回歸機的目的是找到兩個函數(shù)來構造最終的回歸函數(shù)。首先，在問題（7）～（8）的目標函數(shù)中，第一項表示極小化樣本點到超平面f1(x)=0的距離，第二項是極小化誤差。應當指出，由于誤差項是平方項，所以不需要限定松弛變量ξ，η非負。約束條件表示讓樣本點盡量地圍繞在超平面 f1(x)=0的ε1不敏感下界超平面，即 f1(x)-ε1=0的周圍。直觀的幾何解釋如圖1所示。兩個超平面 f1(x)=0與 f1(x)-ε1=0之間的帶子類似于標準支持向量回歸機的半ε1帶。對于問題（9）～（10）有相似的解釋，只是超平面 f2(x)=0決定了它的上界ε2不敏感上界超平面 f2(x)+ε2=0，它們之間構成了另外一個半ε2帶。

圖1 最小二乘雙支持向量回歸機幾何解釋

為了求解問題（7）～（8），可將約束條件代入目標函數(shù)中得到如下的拉格朗日函數(shù)：

最小二乘雙支持向量機的線性情形求解過程具體可見流程圖2。

圖2 最小二乘雙支持向量回歸機流程框圖

3.2 非線性情形

根據(jù)線性最小二乘雙支持向量回歸機的思想，下面來考慮非線性最小二乘雙支持向量回歸機，其任務是求解如下兩個非線性超平面，即 f1(x)=uT1K(X，x)+γ1和f2(x)=uT2K(X，x)+γ2為了得到這兩個超平面建立如下兩個優(yōu)化問題：

其中 C1，C2＞0 是懲罰參數(shù)，ε1，ε2＞0 是 ε不敏感損失函數(shù)的參數(shù)，ξ，η是松弛因子。將問題（18）～（19）的約束條件代入目標函數(shù)可得：

從上面可以看出，對于非線性情況，只需引入核函數(shù)就可以得到問題的解，非線性問題的流程圖與線性的不同就是所要求解的線性方程組不同，即非線性情況需求解線性方程組式（26）和式（27），且得出的 f1(x)=

4 實驗與討論

為了檢驗最小二乘雙支持向量歸機，并與支持向量回歸機、最小二乘支持向量回歸機和雙支持向量回歸機作對比，利用了人工數(shù)據(jù)和UCI數(shù)據(jù)庫中的幾個數(shù)據(jù)。在實驗中參數(shù)均選自于集合{2i|i=-8，…，8}，同時令C1=C2，ε1= ε2，并通過十折交叉檢驗法[12]來選取參數(shù)。文中核函數(shù)定為高斯核 K(u，v)=exp(-‖u-v‖2/2p21)，為了縮減選擇參數(shù)的時間，令參數(shù) p1=1。數(shù)值實驗在Windows 7系統(tǒng)上完成，處理器為英特爾酷睿雙核，主頻為2.2 GHz，內存為2 GB。程序編輯基于Matlab R2010a平臺上完成。并且所有的算法都使用的是Matlab中的求解二次規(guī)劃和線性方程組的函數(shù)。

4.1 人工數(shù)據(jù)實驗

在這個數(shù)值實驗中，用最小二乘雙支持向量回歸機去逼近函數(shù)sinc(x)，函數(shù)定義為：

對這個函數(shù)加入一個噪音，會產(chǎn)生一組新的樣本點，這里只用到兩種噪音，定義這組數(shù)據(jù)(xi，yi)，如下：i=1，2，…，200，U[a，b]表示在區(qū)間 [a，b]之間產(chǎn)生一組隨機的數(shù)，記式（30）中的 ξi為noise1，記式（31）中的 ξi為noise2。

表1中列出了在兩種不同噪聲的擾動下最小二乘雙支持向量回歸機和雙支持向量回歸機的回歸效果，其中最好的結果由黑體表示。在實驗中，對每個數(shù)據(jù)進行了10次10折交叉過程，最后的結果由10次數(shù)據(jù)結果的平均值加減方差構成，表1中可以看出最小二乘雙支持向量回歸機能夠得到最小的SSE/SST最大的SSR/SST，對比數(shù)據(jù)結果中±后的方差可以看出，最小二乘雙支持向量回歸機得到的方差均小于雙支持向量回歸機，說明最小二乘雙支持向量回歸機預測相對比較穩(wěn)定，更接近于真實值，由于求解最小二乘雙支持向量回歸機只需要解兩組線性方程組，所以它的運算時間也明顯少于雙支持向量回歸機。從圖3、圖4中可以直觀地看出來，在這兩個噪聲的擾動下，最小二乘雙支持向量回歸機的回歸效果較好。

表1 在噪音noise1、noise2擾動下，TSVR和LSTSVR對函數(shù)sinc(x)的回歸效果

圖3 在noise1擾動下TSVR，LSTSVR的回歸效果

圖4 在noise2擾動下TSVR，LSTSVR的回歸效果

表2 LSTSVR、TSVR、LSSVR在7組UCI數(shù)據(jù)中的表現(xiàn)

4.2 UCI數(shù)據(jù)

在實驗中，利用UCI數(shù)據(jù)中的7個數(shù)據(jù)來做數(shù)值實驗，包括 Boston housing、Machine CPU、Auto price、Concrete Compressive Strength、Wisconsin Breast Cancer、Motorcycle、Auto-Mpg，這些數(shù)據(jù)經(jīng)常會被用來檢測回歸算法的優(yōu)劣。具體地，Boston housing數(shù)據(jù)包括506個樣本，每個樣本有13個特征，Machine CPU是反映計算機中CPU表現(xiàn)的一組數(shù)據(jù)，它包含209個樣本，每個樣本點含有7個特征，Auto price由159個樣本點構成，每個樣本點有15個特征，Motorcycle中含有133個樣本，Auto-Mpg包含398個樣本點，每個樣本點有7個特征，Concrete Compressive Strength中含有1 030個樣本點，Wisconsin Breast Cancer中擁有699個樣本點，其中每個樣本點都有10個特征。

在UCI數(shù)據(jù)實驗中，同樣對每個數(shù)據(jù)做10次10折交叉過程，最終的結果由10次實驗結果的平均值加減方差構成，這樣的結果既可以說明預測精度的高低，又可以說明算法預測的穩(wěn)定性。表2中給出了具體的數(shù)值結果，其中表現(xiàn)最好的用黑體表示。從表2可以看出，在時間上，最小二乘雙支持向量回歸機占絕對優(yōu)勢，其計算時間均遠遠小于其他所有算法，相比于最小二乘支持向量回歸機，它將原來的規(guī)模較大的線性方程組變?yōu)閮蓚€規(guī)模較小的線性方程組來解，其時間大大縮短了。就精度而言，只有雙支持向量回歸機的精度可以與它相媲美，7組數(shù)據(jù)結果中，雙支持向量機兩個SSE/SST的值小于最小二乘雙支持向量回歸機，其他算法的精度均遠遠不如它，只有在Auto-Mpg這一數(shù)據(jù)中，支持向量機得到了最小的SSE/SST，但計算時間方法卻遠遠優(yōu)于其他的回歸算法，在表2中，最小二乘雙支持向量機算出數(shù)據(jù)Auto Price和Wisconsin B.C最小的SSE/SST和最大的SSR/SST，最小二乘雙支持向量回歸機得到的大部分的SSE/SST都比其他算法所得的小，同時可以看出最小二乘雙支持向量回歸機的預測穩(wěn)定性也相對較好，足以說明最小二乘雙支持向量回歸機比其他算法更高效，精度更高，而且有很好的推廣能力。

5 結束語

在本文中，提出了最小二乘雙支持向量回歸機，求解它只需解兩個較小規(guī)模的線性方程組，而不同于雙支持向量回歸機中求解兩個二次規(guī)劃問題，更不像支持向量回歸中求解一個大規(guī)模的二次規(guī)劃問題，它的靈感來源于雙支持向量回歸機，對雙支持向量回歸機的模型加入了最小二乘的思想，在約束條件里只有等式約束，所以在求解時只需將約束條件代入到目標問題中，這樣只需要解兩個線性方程組。因此它顯然繼承了雙支持向量回歸機和最小二乘支持向量回歸機的優(yōu)點，并且優(yōu)于它們。對于未來的研究中，應該致力于特征選擇來減少計算代價，才能更有利于支持向量機進一步的發(fā)展。

[1]Vapnik V N.The natural of statistical learning theory[M]. New York：Springer，1995.

[2]Vapnik V N.Statistical learning theory[M].New York：Wiley，1998.

[3]Burges C J.A tutorial on support vector machines for pattern recognition[J].Data Mining Knowledge Discovery，1998，2（2）：121-167.

[4]Christianini V.Shawe-Taylor J.An introduction to support vector machines[M].Cambridge：Cambridge University Press，2002.

[5]Smola A J，Scholkopf B.A tutorial on support vector regression[J].Statistics and Computing，2004，14（3）：199-222.

[6]Suykens J A K，Tony V G，Jos D B，et al.Least squares supportvectormachines[M].Singapore：World Scientific Pub Co，2002.

[7]Suykens J A K，Vandewalle J.Least squares support vector machine classifiers[J].Neural Process Letter，1999，9（3）：293-300.

[8]Peng X.TSVR：an efficient twin support vector machine for regression[J].Neural Networks，2009，23：356-372.

[9]Jayadeva，Khemchandani R，Chandra S.Twin support vector machines for pattern classification[J].IEEE Trans on Pattern Anal Mach Intell，2007，29：905-910.

[10]業(yè)寧，梁作鵬，董逸生，等.一種SVM非線性回歸算法[J].計算機工程，2005，31（20）：19-21.

[11]鄧乃揚，田英杰.數(shù)據(jù)挖掘中的新方法-支持向量機[M].北京：科學出版社，2004.

[12]鄧乃揚，田英杰.支持向量機-理論、算法與拓展[M].北京：科學出版社，2009.

[13]Allen D M.The relationship between variable selection and prediction[J].Technometrics，1974，16：125-127.

[14]Weisberg S.Applied linear regression[M].New York：Wiley，1985.

[15]Bates D M，Watts D G.Nonlinear regression analysis and its applications[M].New York：Wiley，1988.

LU Zhenxing,YANG Zhixia,GAO Xinyu

College of Mathematics and System Sciences,Xinjiang University,Urumqi 830046,China

In this paper Least Square Twin Support Vector Regression（LSTSVR）is proposed,which is formulated via the idea of Twin Support Vector Regression（TSVR）.LSTSVR breaks the idea which ε-band is constructed by two parallel hyperplanes in traditional Support Vector Regression（SVR）.Actually,LSTVR employes two non-parallel hyperplanes to construct the ε-band,in which each hyperplane determinates a halfε-bond,and obtain the final regression.So the regression function fits the distribution of dataset and the algorithm has better generalization ability.In addition,in LSTSVR, the main computing cost is to solve two smaller systems of linear equations,so the computational complexity is low.The experimental results indicate that the proposed algorithm has certain advantage in generalization ability and computational efficiency.

regression problem;support vector regression;twin support vector regression;least square twin support vector regression

提出了一個最小二乘雙支持向量回歸機，它是在雙支持向量回歸機基礎之上建立的，打破了標準支持向量回歸機利用兩條平行超平面構造ε帶的思想。事實上，它是利用兩條不一定平行的超平面構造ε帶，每條超平面確定一個半ε-帶，從而得到最終的回歸函數(shù)，這使該回歸函數(shù)更符合數(shù)據(jù)本身的分布情況，回歸算法有更好的推廣能力。另外，最小二乘雙支持向量機只需求解兩個較小規(guī)模的線性方程組就能得到最后的回歸函數(shù)，其計算復雜度相對較低。數(shù)值實驗也表明該回歸算法在推廣能力和計算效率上有一定的優(yōu)勢。

回歸問題；支持向量回歸機；雙支持向量回歸機；最小二乘雙支持向量回歸機

A

O235

10.3778/j.issn.1002-8331.1301-0136

LU Zhenxing,YANG Zhixia,GAO Xinyu.Least square twin support vector regression.Computer Engineering and Applications,2014,50（23）：140-144.

國家自然科學基金（No.11161045）。

盧振興（1985—），男，碩士研究生，研究領域為支持向量機；楊志霞（1977—），通訊作者，女，博士，副教授，研究方向為最優(yōu)化方法、支持向量機；高新豫（1988—），女，碩士研究生，研究領域為支持向量機。E-mail：yangzhixia@gmail.com

2013-01-14

2013-03-25

1002-8331（2014）23-0140-05

CNKI網(wǎng)絡優(yōu)先出版：2013-04-26,http://www.cnki.net/kcms/detail/11.2127.TP.20130426.1018.010.html