基于支持向量機的分類研究

1、支持向量機在模式分類中的應(yīng)用 謝 駿 胡均川 笪良龍 海軍潛艇學院戰(zhàn)術(shù)水聲環(huán)境數(shù)據(jù)中心，山東青島266071) 摘 要：介紹了支持向量機的基本思想，依據(jù)是否引入核函數(shù)，是否具有懲罰因子，支 持向量分類算法被分為線性分界面硬間隔、線性分界面軟間隔、非線性分界面硬間隔和 非線性分界面軟間隔四類，并討論了它們的數(shù)學模型。以 RBF 為核函數(shù)的非線性支持向 量機對 2類 2維樣本進行的仿真分析，并與最近鄰法分類結(jié)果進行了比較，結(jié)果表明支 持向量機分類能力受核函數(shù)參數(shù)影響較大，當選取適當參數(shù)時，其分類性能與最近鄰法 相當。 關(guān)鍵詞 ：特征提??；最近鄰分類法；支持向量機；模式分類 中圖分類號 ： TP39

2、1.4文獻標識碼 ：A 文章編號： The Application of Support Vector Machines in Pattern Classification XIE Jun ， HUN Junchuan ，DA Lianglong (Naval Submarine Academy， QingDao 266071, China) Abstract ：The foundations of support vector machines are introduced. Four mathematics models of support vector classifications

3、including linearly hard margin SVM, linearly soft margin SVM, non- linearly hard margin SVM and non-linearly soft margin SVM are discussed. Comparison between non-linearly SVM classification with RBF kernel and nearest neighbour classification for a 2-dimension feature data set which contains two ty

4、pes.The results show that the classification performance of SVM is affected by kernel function parameter. the classification performance of SVM is equivalent with nearest neighbour classification while kernel function parameter is selected appropriately. Key words： feature abstract; nearest neighbou

5、r classification ;support vector machines; pattern classification 1、引言 在模式識別領(lǐng)域如何設(shè)計一種具有較好泛化能力的優(yōu)良分類器一直以來是個備受關(guān)注 的問題。 傳統(tǒng)的模式識別或人工神經(jīng)網(wǎng)絡(luò)方法都都是以大樣本統(tǒng)計理論為基礎(chǔ)的，而許多實際 問題中常常面對的是小樣本。 如何從小樣本集出發(fā)， 得到泛化能力較好的模型， 是模式識別研 究領(lǐng)域內(nèi)的一個難點。 Vapnik1 等人早在 20 世紀 60 年代就開始研究有限樣本情況下的機器 學習問題， 但這些研究長期沒有得到充分的重視。 近十年來， 有限樣本情況下的機器學習理 論逐漸成熟起來，

6、形成了一個較完善的統(tǒng)計學習理論(SLT)體系。而同時，神經(jīng)網(wǎng)絡(luò)等較 新興的機器學習方法的研究則遇到一些重要的困難， 比如如何確定網(wǎng)絡(luò)結(jié)構(gòu)的問題、 過擬合 與欠擬合問題、局部極小點問題等。在這種情況下，試圖從更本質(zhì)上研究機器學習的 SLT 體系逐步得到重視。 19921995年，在 SLT 的基礎(chǔ)上發(fā)展了支持向量機( SVM )算法 基金項目： 國防預研基金， 51303060403-01；新世紀優(yōu)秀人才支持計劃 NCET 。 作者簡介：謝 駿(1976-), 男, 安徽潁上 , 漢, 博士生 , 講師 , 研究方向為聲納環(huán)境效應(yīng)仿真、水下目標特性分析。 ， 在解決小樣本、 非線性及高維模式識別

7、問題中表現(xiàn)出許多特有的優(yōu)勢。 尤其是在非線性支持 向量機中通過引入核函數(shù)， 將原始空間的非線性問題轉(zhuǎn)化為特征空間的線性問題來求解， 而 且核方法的引入從理論上較好的解決了經(jīng)驗風險最小化原則下統(tǒng)計學習的一致性條件， 在這 1 些條件下關(guān)于統(tǒng)計學習方法泛化性的界， 在這些界的基礎(chǔ)上建立小樣本歸納推理原則， 以及 在此原則下如何構(gòu)造學習算法等統(tǒng)計學習的基礎(chǔ)理論問題。 2、支持向量機分類器的幾種數(shù)學模型 支持向量機最初思想是對于線性可分問題如何尋求最優(yōu)分類面， 對于特征空間中線性可 分問題， 最優(yōu)分類面就是間隔 最大的分界面， 根據(jù)上述核理論的分析可知， 它的確是在保 證樣本被正確分類前提下，具有最好

8、泛化能力的分界面。對于特征空間中線性不可分問題， 可通過一個懲罰因子來綜合考慮間隔和松弛因子的影響。 根據(jù)面對的不同問題和采取的不同 優(yōu)化策略可將解決分類問題的支持向量機分為如下四類。 2.1 線性分界面硬間隔 當在原始空間中分界面是線性的，即解決的問題是在原始空間中尋求最優(yōu)分界面問題。 該問題的數(shù)學模型是： min w,b , s.t. yi( w ,xi b ) i, ，1 , 2 w1 其中 為間隔， 是訓練樣本數(shù)， xi是訓練樣本矢量， w是權(quán)矢量， b 是閾值， yi為樣本 標記， yi1 1 構(gòu)造拉格朗日函數(shù)， xi1 i 1 ， i 代表第 i 類。 xi2 得到 L(w,b,

9、,a, )ai yi( w, xi b) ( w 1) i1 分別對 w,b, 求微分，得到 L(w ,b, ,a, ) ai yi xi 2 w 0 i1 L(w,bb, ,a, )ai yi0 i1 L(w ,b, ,a, ) 1a i 0 i1 將上式代入拉格朗日函數(shù)，得到 L(w,b, ,a, )aiyi w, xiw i1 1 =aiaj yi yj(xi xj) 4 i, j 求 得最優(yōu)化，得到 aiaj yiyj(xi 2 i ,j 得到對偶拉格朗日函數(shù) xj) 1/ 2 L(a)aiaj yi yj(xi xj) i,j 原問題轉(zhuǎn)化為如下最優(yōu)化問題 min aL(a) 問題在原

10、始空間是非線性的， 數(shù)學模型是： min w,b, s.t. Ci i1 yi( w ,xi b ) 2 21 i , i 0i, ，1 , s.t.ai 1， aiyi 0，ai 0， i 1， , i 1 i1 根據(jù)最優(yōu)化理論， aiyi( w,xi b) =0為 KKT 附加條件， 只有少量樣本具有非零拉格 朗日乘子，這些樣本即為支持向量，它們是數(shù)據(jù)集中最能提供信息的數(shù)據(jù)。 2.2 線性分界面軟間隔 用線性分界面劃分， 需采用線性分界面軟間隔， 該問題的 其中 C 為懲罰因子， g(xi ) w, xi b 應(yīng)用拉格朗日乘子，得到 L(w,b, ,a, ) C iai yi( w, xi

11、 b)ii i ( w 1) i 1 i 1 i 1 分別對分別對 w, b, , 求微分并設(shè)其值為零，得到 1 L(a, )aiajyi yj(xi xj) 4 i ,j 在關(guān)于 把這個函數(shù)最優(yōu)化，可得到拉格朗日函數(shù)對偶形式 1/2 L(a)aiaj yi yj(xi xj) i,j s.t. 和硬分隔結(jié)果一樣，但要注意此時約束條件有差異。 原問題轉(zhuǎn)化為如下最優(yōu)化問題 min aL(a) ai 1， aiyi 0，0 ai C， i 1， i 1 i1 i 1， , KKT 附加條件為 aiyi( w,xi b)i =0； i(ai C) 0 2.3 非線性分界面硬間隔 通過引入核函數(shù)將問題

12、從原始空間嵌入到特征空間，在特征空間中問題是線性可分的， 求解特征空間中最優(yōu)分界面。該問題數(shù)學模型如下 min w,b, s.t.yi( w , x(i ) b ) i , ，1 , 2 w1 其中函數(shù) 是原始空間到特征空間的映射。 與 2.1 推導過程類似，可得到對偶拉格朗日函數(shù) 1/2 L(a)aiaj yiyj (xi xj ) i,j 其中函數(shù) 是核函數(shù)， (xi xj )(xi), (xj ) 原問題轉(zhuǎn)化為如下最優(yōu)化問題 min a L(a) s.t.ai 1， aiyi 0，ai 0， i 1， , i 1 i1 KKT 附加條件 aiyi( w, (xi) b) =0。 2.4

13、非線性分界面軟間隔 通過引入核函數(shù)將問題從原始空間嵌入到特征空間，在特征空間中問題是非線性可分 的，此時求解特征空間中最優(yōu)分界面要考慮懲罰因子。該問題數(shù)學模型如下 min w,b, C i i1 s.t.yi( w, x( i ) b ) i ,i i0,， 1 , 2 w1 與 2.2 推導過程類似，可得到對偶拉格朗日函數(shù) 1/2 L(a)aiaj yiyj (xi xj ) i,j 原問題轉(zhuǎn)化為如下最優(yōu)化問題 min a L(a) s.t.ai 1， aiyi 0，0 ai C， i 1， , i 1 i1 KKT 附加條件為 aiyi( w, (xi) b)i =0； i(ai C) 0

14、 i 1， , 當 C 1/( ) 時，此時支持向量機稱為支持向量機， (0,1 。 從上述結(jié)果可知， 線性和非線性支持向量機的區(qū)別是是否引入核函數(shù)， 硬間隔和軟件隔 支持向量機的區(qū)別是是否具有懲罰因子。 遺憾的是， 有關(guān)支持向量機核函數(shù)和懲罰因子的選 擇缺乏理論指導 2 。 3、 非線性支持向量機的仿真分析 以下是以 RBF 為核函數(shù)非線性支持向量機對 2 類 2 維樣本進行的仿真分析結(jié)果，兩類 樣本點分別用黑色和淺灰色表示。圖1圖 4 是核函數(shù)參數(shù)，懲罰因子 C 為不同值時的 分類結(jié)果，相應(yīng)分類錯誤率見表 1，圖中淺灰色線是貝葉斯分類器的分類邊界，其分類錯誤 2 xi x j 率為 13%

15、。其中 RBF核定義為： (xi,xj) exp i 2 j 。 2 從分類錯誤率結(jié)果來看，支持向量機性能受核函數(shù)參數(shù)和懲罰因子參數(shù)選擇的影響很 大。文獻 3 針對兩類樣本情況，討論了 RBF 核函數(shù)參數(shù)空間中不同區(qū)域?qū)?yīng)的 SVM 的性 能。 C 越小， SVM 欠訓練，傾向于把樣本分到樣本數(shù)占優(yōu)的一類； C 越大， SVM 過訓練， 越大， SVM 趨向線性分類器。 越小， SVM 視C 的情況出現(xiàn)欠訓練或過訓練。圖 1 圖 4 的仿真結(jié)果驗證了這點。有關(guān)最優(yōu)參數(shù)選擇，文獻4 中提到采用網(wǎng)格方法、雙線性和 改進雙線性法。文獻 5 認為最近鄰算法是一種直推的方法，即是一種直接從已知樣本出發(fā)

16、對特定未知樣本進行識別的方法和原則，不同于 SVM 試圖設(shè)計一種分類器，使其對未來所 有可能樣本的預期性能最優(yōu)的原則， 這使得最近鄰法在面對某一具體問題時， 能夠表現(xiàn)出很 好的分類性能，圖 5 的仿真結(jié)果也說明了這一點，最近鄰法分類錯誤率為15%。 表 1 RBF 核函數(shù)對 2 類 2 維問題的分類錯誤率 C 錯誤率 5 0 26% 5 100 49% 0.2 0 15% 0.2 100 20% 圖 2 5,C 100時 SVM分類結(jié)果圖 圖 1 5,C 0 時 SVM分類結(jié)果圖 4 0.2,C 100 時 SVM分類結(jié)果圖 3 0.2,C 0時 SVM分類結(jié)果圖 圖 5 最近鄰算法分類結(jié)果

17、4、 結(jié)論 本文闡述了支持向量機應(yīng)用于分類問題的幾種情況，分別討論了它們的數(shù)學模型，并通 過仿真試驗進行了分析。理論分析和仿真試驗結(jié)果表明， SVM 作為一種基于結(jié)構(gòu)風險最小 原則的以樣本間的某種距離作為劃分依據(jù)的模式識別方法，它可以在高維空間中構(gòu)造較低 VC 維的函數(shù)集，從而獲得好的推廣能力，解決了神經(jīng)網(wǎng)絡(luò)的局部最優(yōu)問題，它的數(shù)學模型 中樣本僅以點積形式出現(xiàn)，使得這種方法很容易推廣到非線性。但 SVM 也有明顯的不足， 分類性能受核函數(shù)參數(shù)影響大，參數(shù)選擇沒有明確的理論來指導，文獻4 中提出的一些參 數(shù)選擇的方法，本質(zhì)上都是通過劃分參數(shù)區(qū)間，然后進行搜索尋優(yōu)的方法，這使得 SVM 算 法的效率會受到大大影響。仿真結(jié)果也表明，基于直推的最近鄰算法的性能往往不比 SVM 算法差， 因此有必要對 SVM 算法與最近鄰算法等其它分類算法結(jié)合構(gòu)建混合式分類系統(tǒng)做 進一步研究。 參考文獻： 1.V. Vapnik. The Nature of Statistical Learning Theory. Springer, N.Y., 1995. ISBN0-387-94559-8. 2.O.Chapelle,V Vapnik et aI. Choosiog multiple parameters for su