一種基于支持向量機中分離超平面求取的算法*

易校石， 劉 念

(1.重慶師范大學 數(shù)學科學學院，重慶 401331； 2.重慶大學 數(shù)學科學學院， 重慶 401331)

0 引 言

支持向量機(Support Vector Machines， SVM)是由Vapnik等人提出的一種分類算法。此算法在解決小樣本、高維、非線性的模型中起到關(guān)鍵作用，且這種學習算法在許多領(lǐng)域的分類問題中獲得了成功的應用[1-6]，成為淺層統(tǒng)計學習算法的優(yōu)秀代表。有很多學者將支持向量機進行多方面的改進，作為深度機器學習的算法[7-11]。它歸結(jié)于求解凸二次規(guī)劃問題，雖然該凸二次規(guī)劃問題有唯一的最優(yōu)解，但隨著訓練樣本容量的增加，算法變得比較低效，如何快速高效學習支持向量機就變?yōu)橐粋€重要的且需要解決的問題。有很多的文獻直接調(diào)用數(shù)學軟件或統(tǒng)計軟件進行計算，但對算法本身不了解，更不用說創(chuàng)新。本文對支持向量機分離超平面的求解算法采用迭代算法，充分利用支持向量機的特點，分離超平面首先要將樣本訓練數(shù)據(jù)集完全分開，其次是正類支持向量和負類支持向量到分離超平面的距離相等。將感知機算法獲得的完全分離訓練數(shù)據(jù)集的超平面進行旋轉(zhuǎn)和平移，直到幾何間隔達到最大且完全分離訓練集。此時的分離超平面就是支持向量機的分離超平面。

1 問題的表述

假設(shè)給定一個訓練數(shù)據(jù)集：

T={(x1,y1)，(x2,y2)，…，(xN,yN)}

其中xi∈X=Rn,yi∈{+1,-1}，1≤i≤N，xi為第i個特征向量，也稱為第i個實例，yi為xi的類標記，當yi=+1時，稱xi為正實例，當yi=-1時，稱xi為負實例 ，(xi,yi)稱為訓練樣本點。

感知機是一個二分類器，目標是在特征空間上學習一個分離超平面ωx+b=0，分離超平面由法向量ω和截距b決定，可用(ω,b)來表示。但感知機的分離超平面學習時誤分類點達到最少，因而學習的分離超平面是不唯一的，如圖1所示，x1,x2是正類點，x3是負類點，存在無窮多個超平面將正類點和負類點完全分開，但對測試集就有可能存在誤分類點，因此對測試集和待預測分類集的分類效果不理想。

支持向量機是在感知機的思想上發(fā)展起來的，在特征空間上學習一個分離超平面，但有別于感知機的分離超平面，它引入了函數(shù)間隔和幾何間隔的概念，尋找?guī)缀伍g隔最大的分離超平面，這個分離超平面是唯一的，并將求解間隔最大的分離超平面問題轉(zhuǎn)化成如下的凸二次規(guī)劃(Convex Quadratic Programming)問題。

求得最優(yōu)解ω*,b*，但求解這個凸二次規(guī)劃算法很多，需要較好的基礎(chǔ)，很多文獻是調(diào)用軟件進行計算。此處不去解凸二次規(guī)劃，直接采用迭代方法。

圖1 感知機的分離超平面

圖2 支持向量機的分離超平面

對于給定的數(shù)據(jù)集T和超平面(ω,b)，(xi,yi)為T中的一個實例，則(xi,yi)與超平面的幾何間隔為

定義超平面(ω,b)與數(shù)據(jù)集T的幾何間隔為T中所有實例與超平面(ω,b)的幾何間隔的最小值，即

實例點(xi,yi)與超平面(ω,b)的幾何間隔一般是實例點到超平面的帶符號的距離(Signed Distance)，當實例點被超平面正確分類時就是實例點到超平面的距離。

支持向量機的分離超平面就是求得一個幾何間隔最大的分離超平面。具體地，這個問題可以表示為下面的約束最優(yōu)化問題：

2 迭代算法

由于支持向量機是從感知機發(fā)展而來，由感知機的迭代算法可知：當一個實例點被誤分類，即位于分離超平面的錯誤一側(cè)時，則調(diào)整w和b的值，使分離超平面向該誤分類點的一側(cè)移動，以減少該誤分類點與超平面間的距離，直至超平面越過該誤分類點使其被正確分類。迭代出的分離超平面依賴于初值的選擇和迭代過程中誤分類點的選擇順序，選取不同的初始值和誤分類點的不同順序，將得到不同的分離超平面。為了得到唯一的分離超平面，需要增加約束條件，由感知機發(fā)展為支持向量機，那么可以由感知機的迭代思想迭代出支持向量機的分離超平面。采用兩個階段進行迭代：第一階段用感知機迭代算法迭代出一個能將訓練數(shù)據(jù)集完全正確分開的超平面作為支持向量機分離超平面的初始值；將初始分離超平面進行旋轉(zhuǎn)和平移，直到幾何間隔達到最大。

支持向量機新算法如下：

線性可分數(shù)據(jù)集：

T={(x1,y1)，(x2,y2)，…，(xN,yN)}

xi∈X?Rn,yi∈Y={+1,-1}

i=1,2,…,N

學習率：η(0<η≤1).

輸出：ω和b；

支持向量機模型y=f(x)=sing (ω·x+b)。

階段1 獲取支持向量機的初始超平面。

步驟1 設(shè)置初值ω=ω0和b=b0

步驟2 在數(shù)據(jù)集中選取數(shù)據(jù)(xi,yi),i=1,2,…,N。

步驟3 如果yi(ω·xi+b)≤0，則更新ω和b：

ω←ω+ηyixi

b←b+ηyi

步驟4 轉(zhuǎn)至步驟2，直到訓練集中沒有誤分類點，得到支持向量機的初始分離超平面：

階段2：獲取支持向量機的分離超平面。

步驟6：在正例數(shù)據(jù)集和負例數(shù)據(jù)集中分別尋找到分離超平面距離最近的點，設(shè)正例集和負例集分別為T1和T2，計算

步驟7：若|d1-d2|<ε，選取距離d1和d2中任意一對應點(x,y)：

ω*=ω*+εy·x

b*=b*+ε·y，轉(zhuǎn)至步驟6；

若d1,d2同時增大，轉(zhuǎn)至步驟8；

若d1,d2一個增大，一個減小，轉(zhuǎn)至步驟9。

ω*=ω*+η1y·x

b*=b*+η1·y

步驟9：輸出支持向量機的分離超平面

ω*=ω*-εy·x

b*=b*-ε·y

ω*·x+b*=0

3 算法檢驗

為了檢驗算法的有效性，選取鳶花數(shù)據(jù)中setosa和versicolor作為樣本數(shù)據(jù)集，將setosa作為負類(記為-1)，versicolor作為正類(記為+1)，每個鳶花數(shù)據(jù)包含Sepal.Length ，Sepal.Width 兩個特征。記第i個樣本點為xi=(xi1,xi2)，其中xij表示第i個樣本點的j個特征，樣本容量取100。選取了感知機迭代算法分離超平面的3個，包括任取誤分類點、取誤分類點與分離超平面最近點和最遠點進行迭代與本文算法迭代的分離超平面進行比較。迭代算法的分離超平面和線條顏色如表1所示，繪出的圖形如圖3所示。

表1 迭代算法及線條顏色Table 1 The iteration algorithms and line colors

圖3不同算法的分離超平面

Fig.3Theseparatinghyperplanebydifferentalgorithms

從圖3可以看出，本文算法的分離超平面接近支持向量機的分離超平面，分離的效果最好。

4 結(jié)束語

針對支持向量機的分離超平面有各種不同的優(yōu)化算法，搜索的近優(yōu)解往往不是實質(zhì)上的最優(yōu)解，本文構(gòu)建的算法是依據(jù)正類支持向量和負類支持向量到支持向量機分離超平面的距離相等，避免參數(shù)的優(yōu)化選擇，其思想和原理非常簡單，當然本文的算法是針對線性可分的支持向量機分離超平面的算法，對于線性不可分的訓練數(shù)據(jù)集，通過核技巧，將輸入空間對應于一個特征空間(希爾伯特空間)，使得在輸入空間中的超曲面模型對應于特征空間中的超平面模型，分類問題的學習任務通過在特征空間中求解線性支持向量機就可以完成，使得本文構(gòu)建的新算法具有廣闊的應用前景。

參考文獻(References)：

[1] 李天宏，張潔，魏江月.基于Bootstrapping支持向量機算法的森林干擾遙感監(jiān)測[J].應用基礎(chǔ)與工程科學學報，2015，23(2)： 308-317

LI T H， ZHANG J， WEI J Y.Monitoring Forest Disturbances with Bootstrapping Support Vector Machine Algorithm[J].Journal of Basic Science and Engineering，2015,23(2)： 308-317

[2] ZHANG Z， GUO H. Research on Fault Diagnosis of Diesel Engine Based on PSO-SVM [C]∥Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation. Atlantis Press， 2016： 509-517

[3] HUANG J，HU X G， YANG F. Support Vector Machine with Genetic Algorithm for Machinery Fault Diagnosis of High Voltage Circuit Breaker [J]. Measurement， 2011 (44) ： 1018-1027

[4] LONG B， TIAN S L， MIAO Q， et al. Research on Features for Diagnostics of Filtered Analog Circuits Based on LS-SVM [J]. IEEE Autotestcon， Baltimore， MD， 2011(9)：360-366

[5] LONG B， TIAN S L， WANG H J. Diagnostics of Filtered Analog Circuits with Tolerance Based on LS-SVM Using Frequency Features[J]. Journal of Electronic Testing， 2012(28)： 291-300

[6] 顧彬，鄭關(guān)勝，王建東.增量和減量式標準支持向量機的分析[J].軟件學報，2013，24(7)：1601-1613

GU B， ZHENG G S， WANG J D. Analysis of Incremental and Decrement Standard Support Vector Machines[J]. Journal of Software， 2013，24 (7)： 1601-1613

[7] 尹傳環(huán)，牟少敏，田盛豐，等. 局部支持向量機的研究進展[J].計算機科學，2012，39(1)：170-174

YIN C H， MOU S M， TIAN S F，et al. Advances in Research on Local Support Vector Machines[J]. Computer Science， 2012，39(1)： 170-174

[8] 鞠哲，曹雋喆，顧宏.用于不平衡數(shù)據(jù)分類的模糊支持向量機算法[J].大連理工大學學報，2016，56(5)： 525-531

JU Z， CAO J Z， GU H.Fuzzy Support Vector Machines Algorithm for Imbalanced Data Classification [J]. Journal of Dalian University of Technology，2016，56(5)： 525-531

[9] HUANG Y H.Deep Understanding of Big Data：Big Data Processing and Programming Practice[M].Beijing：China Machine Press，2014

[10] GUO X X. SVM Algorithm Optimization Based on

Distributed Computing[D].Xi’an：Xidian University，2014

[11] ZHAO Q.Efficient Algorithm of Canopy K-means Based on Hadoop Platform[J].Electronic Science and Technology，2014，27(2)：2-3