一種近似于支持向量機的分類模型

簡國明，朱森華

（韶關學院 數學與信息科學學院，廣東 韶關 512005）

分類問題是通過已知的數據建立分類模型，對未知類別的數據進行預測判斷.支持向量機通過尋找使得兩類點集具有最大間隔的思想來建立分類模型，此模型在對線性可分的點集進行求解時較容易，但是在對非線性可分的點集時，需要引入核函數進行求解，且分類效果依賴核函數及參數的選擇，而核函數及參數的選擇并沒有較成熟的算法，只能依靠使用者的先驗知識進行選擇并多次試驗選取較優的核函數和對應的參數，這個問題在一定程度限制了支持向量機的使用.

基于這樣的原因，為尋找一種較為簡便有效的分類方法，提出一種近似支持向量機的分類模型，通過求解線性方程組的近似解來確定分類平面方程，使得求解會更加簡潔.最后利用心臟病診斷的13項數據對新模型進行檢驗，并與支持向量機模型進行了對比，新模型具有不錯的分類效果.

1 支持向量機分類模型

1.1 線性可分

若有樣本G={(X1,y1),(X2,y2),…,(Xn,yn)}，其中Xi∈Rm表示數據向量，yi=±1用于標識不同的種類，若兩類點集是線性可分的，如圖1所示.

圖1 樣本線性可分圖

如果存在一線性平面能夠完全把不同的兩類點集分開，建立支持向量的分類模型［1-2］為：

作為非線性規劃問題，對該問題的求解，引入Lagrange函數：

其中α=(α1,…,αn)T∈Rn+為Lagrange乘子.通過對原問題中各個變量的偏導取零可得：

代入Lagrange函數化為原問題的Lagrange對偶問題：

分類函數為：f(X)=sign(WTX+b).

1.2 非線性可分

當已知樣本G={(X1,y1),(X2,y2),…,(Xn,yn)}在原空間是非線性可分時，則需要通過把點集映射到特征空間（或高維或無窮維空間），使得在特征空間是線性可分的，如圖2所示.

圖2 樣本非線性可分

在原空間是非線性可分的，但是通過映射到特征空間之后是線性可分的［3-4］.則原問題轉化為：

映射φ(X)不容易通過顯式形式表示出來，或者有時需要將原空間中的點集映射到高維或無窮維空間中，則內積(φ(X),φ(y))的計算量將會大大增加，而如果不能夠顯式的表示出φ(x)，則無法計算(φ(x),φ(y)).引入核函數 K(x,y)，使得 K(Xi,Xj)=(φ(xi,),φ(xj,))，則對應的 Lagrange問題轉化為：

若不可分則需引入懲罰參數.

2 近似于支持向量機的模型

在支持向量機問題中，若兩類點集是線性可分的，則一定存在支持向量的點，如圖3所示.

圖3 支持向量機示意圖

若此時平行直線具有最大距離，則中間的為劃分直線，落在直線上的點稱為支持向量的點.故對于問題：

總是存在唯一的解WTX+b=0.但是對于非線性可分的點集，顯然不存在解，于是希望通過映射，通過核函數等一系列的手段來解決這一問題.但是核函數的參數的選擇具有一定的困難，需要有一個簡單有效的分類模型.

支持向量機的模型是在線性可分的情況下，通過最大間隔來確定唯一的解，但是在非線性可分中不適用.對支持向量機模型的改進是：可以完全分開兩類點集是直線并不是唯一的，支持向量機模型則通過最大間隔確定唯一的一條直線認為是最合理的，但是事實上是不是，并不能確定，如圖3所示.所以顯然一個對已知數據驗證正確率100%的分類直線應該都具有一定的合理性；且在支持向量機的模型中，如果全部的點都是支持向量，顯然分類的正確率可以達到100%.

基于這樣的思想，建立新的支持向量機分類模型：

此時非齊次線性方程組顯然不一定有解，在無解的情況下，取近似數值解代替，即求得的解不能夠使得原線性方程組的等式全部成立，最后的結果可能在1附近.而對于線性可分的點集，顯然存在直線WTX+b=0使得WTXi+b>0,i=1,2,…,n和WTXi+b<0,i=1,2,…,n.這樣在線性可分的點集中顯然可以做到正確率100%，這樣方程WTX+b=0顯然也是合理的，同樣可以建立對新數據的判別函數f(x)=sign(WTX+b).

對非線性可分的點集，不需要如支持向量機那樣需要引入核函數，只需直接對方程組求解最接近原方程的近似解即可，使得yi(WTXi+b)>0,i=1,2,…,n成立的點盡可能多，滿足不等式的點都能正確分類.

3 心臟病預測實例

為了降低對心臟病確診的體檢程序及成本，通過一些較容易獲得的指標來確定心臟病人的患病情況.通過年齡、性別、胸痛類型、靜息血壓、血清中膽固醇含量、空腹時血糖、靜息時心電圖結果、最大心跳速率、運動是否誘發心絞痛、運動心電圖ST下降程度、ST段斜坡、大血管屬性、地中海貧血等13項指標，利用已獲得的心臟病患者和健康者的數據［5］，應用支持向量機的分類模型，通過MATLAB軟件進行求解,得到多項式核函數、高斯核函數、Sigmoid核函數的計算結果（見表1、表2、表3）.

表1 多項式核函數計算結果：K(x,xi)=［γ(x·xi)+c］q

表2 高斯核函數計算結果：K(x,xi)=exp(-‖x-xi‖2/σ2)

表3 Sigmoid核函數計算結果：K(x,xi)=tanh(+r)

表3 Sigmoid核函數計算結果：K(x,xi)=tanh(+r)

隨機取值γ 0.5 0.2 1.41421 r-1-1-1檢驗正確率/%55.56 55.56 55.56

近似支持向量機分類模型對心臟病預測的求解結果：

W=(0.007 69,-0.335 49,-0.194 33,-0.003 79,-0.000 94,0.010 09,-0.045 94,0.005 36,

-0.178 60,-0.088 12,-0.024 647,-0.379 23,-0.101 76),b=1.419 36；

構造預測函數f(x)=sign((W,X)+b).檢驗正確率為：87.78%.

通過實驗，可以看到隨機選取核函數參數的分類效果并不太好，而新模型卻有不錯的分類效果.目前有的一些利用計算機來尋找最優參數的方法如網格搜索法，但它只能夠找到一個相對的最優參數，即通過網格搜索法得到最優參數取決于所給的初始區間和循環的步長，初始區間越大，步長越小，能夠獲得更好的相對最優值，但同時計算量也會隨之增大.而且參數個數越多，需要循環的層數越多，計算量越大.

［1］鄧乃揚，田英杰.支持向量機—理論、算法與拓展［M］.北京：科學出版社，2009.

［2］Nello Cristianini,John Shawe-Taylor.支持向量機導論［M］.李國正,王猛,曾華軍,譯.北京：電子工業出版社，2004.

［3］John Shawe-Taylor,Nello Cristianini.模式分析的核方法［M］.趙玲玲，翁蘇明，曾華軍,等,譯.北京：機械工業出版社，2006.

［4］劉明.支持向量機中Sigmoid核函數的研究［D］.西安：西安電子科技大學，2009.

［5］數據堂.Heart Disease Data Set(UCI)［EB/OL］.2010-12-04［2013-8-6］.http://down.datatang.com/download.aspx?key= 028433f625 d2cd1adc2fda878d949d1b&url=/datafile/ 100141/dataset.rar&expire=6d8cb0&id=543&filename=dataset_ 100141.rar.