基于支持向量機(jī)的分類研究

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

2、1.4文獻(xiàn)標(biāo)識碼 ：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è)計(jì)一種具有較好泛化能力的優(yōu)良分類器一直以來是個(gè)備受關(guān)注 的問題。 傳統(tǒng)的模式識別或人工神經(jīng)網(wǎng)絡(luò)方法都都是以大樣本統(tǒng)計(jì)理論為基礎(chǔ)的，而許多實(shí)際 問題中常常面對的是小樣本。 如何從小樣本集出發(fā)， 得到泛化能力較好的模型， 是模式識別研 究領(lǐng)域內(nèi)的一個(gè)難點(diǎn)。 Vapnik1 等人早在 20 世紀(jì) 60 年代就開始研究有限樣本情況下的機(jī)器 學(xué)習(xí)問題， 但這些研究長期沒有得到充分的重視。 近十年來， 有限樣本情況下的機(jī)器學(xué)習(xí)理 論逐漸成熟起來，

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

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

8、泛化能力的分界面。對于特征空間中線性不可分問題， 可通過一個(gè)懲罰因子來綜合考慮間隔和松弛因子的影響。 根據(jù)面對的不同問題和采取的不同 優(yōu)化策略可將解決分類問題的支持向量機(jī)分為如下四類。 2.1 線性分界面硬間隔 當(dāng)在原始空間中分界面是線性的，即解決的問題是在原始空間中尋求最優(yōu)分界面問題。 該問題的數(shù)學(xué)模型是： min w,b , s.t. yi( w ,xi b ) i, ，1 , 2 w1 其中 為間隔， 是訓(xùn)練樣本數(shù)， xi是訓(xùn)練樣本矢量， w是權(quán)矢量， b 是閾值， yi為樣本 標(biāo)記， 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ù)學(xué)模型是： 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)于 把這個(gè)函數(shù)最優(yōu)化，可得到拉格朗日函數(shù)對偶形式 1/2 L(a)aiaj yi yj(xi xj) i,j s.t. 和硬分隔結(jié)果一樣，但要注意此時(shí)約束條件有差異。 原問題轉(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ù)學(xué)模型如下 min w,b, s.t.yi( w , x(i ) b ) i , ，1 , 2 w1 其中函數(shù) 是原始空間到特征空間的映射。 與 2.1 推導(dǎo)過程類似，可得到對偶拉格朗日函數(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ù)將問題從原始空間嵌入到特征空間，在特征空間中問題是非線性可分 的，此時(shí)求解特征空間中最優(yōu)分界面要考慮懲罰因子。該問題數(shù)學(xué)模型如下 min w,b, C i i1 s.t.yi( w, x( i ) b ) i ,i i0,， 1 , 2 w1 與 2.2 推導(dǎo)過程類似，可得到對偶拉格朗日函數(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， , 當(dāng) C 1/( ) 時(shí)，此時(shí)支持向量機(jī)稱為支持向量機(jī)， (0,1 。 從上述結(jié)果可知， 線性和非線性支持向量機(jī)的區(qū)別是是否引入核函數(shù)， 硬間隔和軟件隔 支持向量機(jī)的區(qū)別是是否具有懲罰因子。 遺憾的是， 有關(guān)支持向量機(jī)核函數(shù)和懲罰因子的選 擇缺乏理論指導(dǎo) 2 。 3、 非線性支持向量機(jī)的仿真分析 以下是以 RBF 為核函數(shù)非線性支持向量機(jī)對 2 類 2 維樣本進(jìn)行的仿真分析結(jié)果，兩類 樣本點(diǎn)分別用黑色和淺灰色表示。圖1圖 4 是核函數(shù)參數(shù)，懲罰因子 C 為不同值時(shí)的 分類結(jié)果，相應(yīng)分類錯(cuò)誤率見表 1，圖中淺灰色線是貝葉斯分類器的分類邊界，其分類錯(cuò)誤 2 xi x j 率為 13%

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

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

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