易校石， 劉 念

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

0 引 言

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

1 問題的表述

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

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

其中xi∈X=Rn,yi∈{+1,-1}，1≤i≤N，xi為第i個(gè)特征向量，也稱為第i個(gè)實(shí)例，yi為xi的類標(biāo)記，當(dāng)yi=+1時(shí)，稱xi為正實(shí)例，當(dāng)yi=-1時(shí)，稱xi為負(fù)實(shí)例 ，(xi,yi)稱為訓(xùn)練樣本點(diǎn)。

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

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

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

圖1 感知機(jī)的分離超平面

圖2 支持向量機(jī)的分離超平面

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

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

實(shí)例點(diǎn)(xi,yi)與超平面(ω,b)的幾何間隔一般是實(shí)例點(diǎn)到超平面的帶符號(hào)的距離(Signed Distance)，當(dāng)實(shí)例點(diǎn)被超平面正確分類時(shí)就是實(shí)例點(diǎn)到超平面的距離。

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

2 迭代算法

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

支持向量機(jī)新算法如下：

線性可分?jǐn)?shù)據(jù)集：

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

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

i=1,2,…,N

學(xué)習(xí)率：η(0<η≤1).

輸出：ω和b；

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

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

步驟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，直到訓(xùn)練集中沒有誤分類點(diǎn)，得到支持向量機(jī)的初始分離超平面：

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

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

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

ω*=ω*+εy·x

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

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

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

ω*=ω*+η1y·x

b*=b*+η1·y

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

ω*=ω*-εy·x

b*=b*-ε·y

ω*·x+b*=0

3 算法檢驗(yàn)

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

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

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

Fig.3Theseparatinghyperplanebydifferentalgorithms

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

4 結(jié)束語

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

參考文獻(xiàn)(References)：

[1] 李天宏，張潔，魏江月.基于Bootstrapping支持向量機(jī)算法的森林干擾遙感監(jiān)測(cè)[J].應(yīng)用基礎(chǔ)與工程科學(xué)學(xué)報(bào)，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)勝，王建東.增量和減量式標(biāo)準(zhǔn)支持向量機(jī)的分析[J].軟件學(xué)報(bào)，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ī)的研究進(jìn)展[J].計(jì)算機(jī)科學(xué)，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ī)算法[J].大連理工大學(xué)學(xué)報(bào)，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