1、第7期王克奇等：采用遺傳算法優(yōu)化最小二乘支持向童機(jī)屛數(shù)的方法111計(jì)算機(jī)應(yīng)用與軟件Computer Applications and Software采用遺傳算法優(yōu)化最小二乘支持向量機(jī)參數(shù)的方法王克奇楊少春戴天虹白雪冰(東北林業(yè)大學(xué)機(jī)電工程學(xué)院黑龍江哈爾濱15OCMO)摘¥ 支持向*機(jī)是建立在統(tǒng)計(jì)學(xué)習(xí)理論上的一種學(xué)習(xí)算法較好地解決了小樣本學(xué)習(xí)問題。由不同的券數(shù)和核函數(shù)構(gòu)遺的 支持向量機(jī)在性能上存在很大差異而在參敕和核函數(shù)的選擇上目前還沒有明確的理論依據(jù)。針對(duì)支持向it機(jī)的參數(shù)選擇問題提 出了一種采用遺傳算法優(yōu)化最小二乘支持向量機(jī)參數(shù)的方法。結(jié)合LS-SVMlabXlS.在MATLKB

2、實(shí)驗(yàn)平臺(tái)的仿真實(shí)驗(yàn)最明該 方法提離了支持向量機(jī)的參數(shù)選擇效率得到的參數(shù)對(duì)測(cè)試樣本的分類結(jié)果走最優(yōu)的從而譴免？人為設(shè)定套數(shù)的不足，同時(shí)縮短 了優(yōu)化片何。關(guān)鼻詞 最小二乘支持肉量機(jī)遺傳算法券數(shù)逸擇LS-SVMlab工具繪METHOD OF OPTIMIZING PARAMETER OF LEAST SQUARES SUPPORTVECTOR MACHINES BY GENETIC ALGORITHMWang Keqi Yang Shaochun Dai Tianhong Bai Xuebing(College cf Machinery and EUdron Engineering v Northa

3、ui For a try Univenuy, Harbin 150Q40, Hdbngjiang .CAina)Abstract Support vector machines(SVM) ta learning method based on sutistical learning theory(SLT) fcan solve small-sample learning problems better. SVM» with different parameters or kernel functions display very different performances. and

4、 there isnt a manifest theory supporting the ftelection of them up to now. In this paper a method that optimises the parameters of Leas* Squares Support Vector Machines( LSS- VM) by using Genetic Algorithm is presented. The simulative experiment executed on MATLAB experimental platform with LS-SVMIa

5、b toolbox shows that this method greatly improves the efficiency of SVMs parameters selection t and with the parameters selected .the clarification result for the testing samples is the oplimum ll avoids the disadvantage <rf manually specifying the parametera.and also scales down the optimisation

6、 time.Keywords Least 8quare» support vector machines Genetic algorithm Parameters selection LS-SVMlab toolbox第7期王克奇等：采用遺傳算法優(yōu)化最小二乘支持向童機(jī)屛數(shù)的方法111第7期王克奇等：采用遺傳算法優(yōu)化最小二乘支持向童機(jī)屛數(shù)的方法111o引s統(tǒng)計(jì)學(xué)習(xí)理論是由VVapnik等人建立的一種專門研究小 樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論為解決有限樣本學(xué)習(xí)問題提 供了一個(gè)統(tǒng)一的框架，支持向址機(jī)就是在這一理論基礎(chǔ)上發(fā)展 而來的一種新的通用學(xué)習(xí)方法。支持向量機(jī)通過結(jié)構(gòu)風(fēng)險(xiǎn) 最小化原理來提髙

7、泛化能力，較好地解決了小樣本、非線性、高 維數(shù)尊實(shí)際問題已在模式識(shí)別、值號(hào)處理、函數(shù)擬合等領(lǐng)域得 到了成功應(yīng)用，成為機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)之一。然而用支 持向fit機(jī)求解分類冋題其本質(zhì)上是一個(gè)二次規(guī)劃何題當(dāng)樣本 數(shù)據(jù)傲較大時(shí)，常規(guī)的數(shù)值優(yōu)化算法及軟件很難實(shí)現(xiàn)二次規(guī)劃 問題的求解。因此運(yùn)行時(shí)間和計(jì)算內(nèi)存是支持向址機(jī)求解的 主要IK頸。而作為支持向昱機(jī)的改講算法如小二乘支持向 債機(jī)在運(yùn)行速度上有了很大提高同時(shí)減少了求解所需的計(jì)算 資源，而其準(zhǔn)確率并未明旻下降因此在模式識(shí)別和非線性函數(shù) 擬合上得到了很好的應(yīng)用，和其它算法一樣支持向量機(jī)的性 能也依賴于模熨的蠻數(shù)研究人員對(duì)支持向量機(jī)的參數(shù)選擇已 作了很

8、多研究，但至今還未提出明確的理論依據(jù)。如何實(shí)現(xiàn)模 型的參數(shù)優(yōu)化成為提高支持向債機(jī)學(xué)習(xí)性能和泛化能力的主耍 問題之一。本文結(jié)合I A. K. Suyken等人開發(fā)的基于MATLAB 語言的最小二乘支持向量機(jī)工具ffi( LS-SVMlab),利用遺傳算 法實(shí)現(xiàn)了對(duì)支持向段機(jī)模型的參數(shù)優(yōu)化并基于一組木材表面 顏色特征得到了很好的實(shí)臉效果。1最小二乘支持向量機(jī)rr支持向Bi機(jī)的基本思想是通過非線性變換將輸入空間變換 到一個(gè)髙維空間然后在這個(gè)新空間中求取最優(yōu)線性分類超平 面。支持向債機(jī)具有全局最優(yōu)性和很強(qiáng)的泛化能力能夠很好 地解決小樣本學(xué)習(xí)問題因此在模式識(shí)別、隕數(shù)擬合等領(lǐng)域得到 了廣泛的應(yīng)用。但同時(shí)由

9、于統(tǒng)計(jì)學(xué)習(xí)理論尚有很多問題需要 進(jìn)一步研究在支持向最機(jī)結(jié)構(gòu)、參數(shù)和核兩數(shù)選擇上還未有明 確的理論指導(dǎo)。最小二乘支持向懾機(jī) LSSVM( Least Squares Support Vector Machine)是在標(biāo)準(zhǔn)支持向赧機(jī)上的一種擴(kuò)展，由J. A. K. SuyKens和J. VandewalJe提出。它采用廉小二乘線性系統(tǒng)誤 差平方和作為損失匣數(shù)將求解過程變成了解一組等式方程加 快了求解速度求解所需的計(jì)算資源較少，在模式識(shí)別和非線性收稿口期：2007-0912。黑龍江省自然科學(xué)基金碘目(C2004 - 03)。王克奇教授主研領(lǐng)域：自動(dòng)化監(jiān)測(cè)與計(jì)算機(jī)控制。曲數(shù)擬合的應(yīng)用中取得了很好的效果

10、。設(shè)訓(xùn)練樣本D=| （備力）1 "1,2嚴(yán),"仁其中和eR為 輸人數(shù)據(jù)，力wR足輸岀類別。在權(quán)3空間（原始空間）中的最 小二乘支持向址機(jī)分類問題可以描述為求解馬下問題： min（P（a）9b9f） = +丿® +(D約束條件：力&。（引）* = 1 - e, k = lf. 9N （2） 定義拉格朗日函數(shù)：L（u）9b9e；a） =0（ft>t6.e）-若如朮/諷勺）+6 -1 *ej(3)其中,拉格朗日乘子wR。對(duì)上式進(jìn)行優(yōu)化: 參=03 = 力卩（勺） 警=0-家"0普=0 T a = YS% 2 0 一*力«/卩（勺）今 6

11、 - 1 * 6 dot、上式可化為求解下面的矩陣方程：0Y其中,Z =卩（刼）'人，卩（衍）,，卩（和）兒丫二yltyJt %" =ltlt ,lrfe ei.wJ.a = aMa2t »a.vr,同時(shí)將Mercer條件代入到C = ZZr，可得： 仏/=齊（血）。（引=力力飲引內(nèi)）因此式（1）的分類冋題通過式（5）和式（6）的線性問題得 到最終解而不是解二次規(guī)劃問題。核阪數(shù)可采用高斯徑向基 核函數(shù)、多項(xiàng)式核阪數(shù)、多層感知器核更數(shù)和線性核函數(shù)等多種 符合Mercer條件的核換數(shù):“】。常用的核函數(shù)的表示形式如表 I所示叭«1康用的核畫敷孩函數(shù)表達(dá)式線性核

12、函數(shù)K(x.Xi)ax xt多頊丈核旳數(shù)K(x.xJ « ( x - x(高斯袒向基孩曲數(shù)K(*暫)=exp( |x-x, IlVtr2)Sigmoid核函數(shù)K(x.ii) =tanA(*(x - xt) »)最小二乘支持向fit機(jī)將不等式約束轉(zhuǎn)化為等式約束將誤 迫平方和損失函數(shù)作為訓(xùn)練集的經(jīng)驗(yàn)損失，這樣就將二次規(guī)劃 問越轉(zhuǎn)化成線性方程組的求解簡(jiǎn)化了計(jì)算復(fù)雜性提髙了支持 向址機(jī)求解冋題的速度和收斂將度。但同時(shí)也必須指出由于 每個(gè)樣本數(shù)據(jù)對(duì)分類期部有員獻(xiàn).LSSVM失去了標(biāo)準(zhǔn)SVM稀 嫌性的優(yōu)點(diǎn)。2最小二乘支持向機(jī)的參數(shù)優(yōu)化21支持向機(jī)的參數(shù)選擇問題采用支持向機(jī)求解模式識(shí)別或

13、函數(shù)擬合問題需要選擇一 個(gè)核函數(shù)由于不周的核西數(shù)構(gòu)成的分類器的性能不同因此選 擇哪種核函數(shù)對(duì)于支持向fit機(jī)的設(shè)計(jì)是非常重要的。研究表 明懲罰因子和核西數(shù)的參數(shù)是形響支持向量機(jī)性能的主要原 因其中核函數(shù)的參數(shù)響樣本數(shù)據(jù)在髙維特征空間中分 布的復(fù)雜程度而懲罰因子的作用杲在確定的特征空間中調(diào)節(jié) 支持向量機(jī)的信范闔和經(jīng)驗(yàn)風(fēng)險(xiǎn)的比例.所以要擔(dān)獲得 泛化能力良好的支持向就機(jī)首先要選擇合適的核函數(shù)參數(shù)將 數(shù)據(jù)映射到合適的待征空間然后針對(duì)該確定的特征空間尋找 合適的懲罰因子以使支持向雖機(jī)的置信范圍和經(jīng)驗(yàn)風(fēng)險(xiǎn)具有最 佳比例。作為支持向量機(jī)的一種擴(kuò)展最小二乘支持向徵機(jī)同樣存 在參數(shù)選擇問越冃前應(yīng)用較多的是采用網(wǎng)

14、格搜索和交叉驗(yàn)證 相結(jié)合的支持向議機(jī)參數(shù)優(yōu)化算法該算法由初始給定的參數(shù) 出發(fā),在給定的參數(shù)范圍內(nèi)采用網(wǎng)格搜索算法和交叉驗(yàn)證尋找 最優(yōu)參數(shù)。首先網(wǎng)格搜索算法選擇要優(yōu)化的參數(shù)對(duì)（*p）, 然后用交叉瞼證法對(duì)目標(biāo)函數(shù)（如均方差最小）進(jìn)行尋優(yōu)直至 找到最佳的參數(shù)對(duì)便交叉驗(yàn)證的精度最高。其中網(wǎng)格搜索算 法要將懲罰因子，和核甌數(shù)參數(shù)形成MxN個(gè)（y.p）組合（其 中M和N分別為y和p的個(gè)數(shù)），分別訓(xùn)練不同的支持向伙機(jī), 估計(jì)其學(xué)習(xí)精度從而在M x N個(gè)（人p）的組合中得到學(xué)習(xí)精 度展離的一個(gè)組合作為最優(yōu)值。其計(jì)算秋較大，尤其是訓(xùn)練樣 本集較大時(shí)搜索過程非常費(fèi)時(shí)因此這種方法在使用上受到一 定程度的限制。在最

15、優(yōu)化方法眾多的算法中遺傳算法以其強(qiáng) 大的全局搜索能力.并行性、高效性的優(yōu)點(diǎn)得到了廣泛的應(yīng)用。 本文正是利用遺傳算法的優(yōu)點(diǎn)優(yōu)化最小二乘支持向故機(jī)的參 數(shù)得到了較好的結(jié)果。2.2用遺傳算法優(yōu)化最小二乘支持向機(jī)參數(shù)遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨 機(jī)搜索算法能夠在搜索過程中自動(dòng)獲取和積累有關(guān)搜索空間 的知識(shí)并自適應(yīng)地控制搜賞過程以求得最優(yōu)解。它模擬自然 選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象從任一初始種群 出發(fā)通過隨機(jī)選擇、交叉和變異操作產(chǎn)生一群更適應(yīng)環(huán)境的 個(gè)體使群體進(jìn)化到搜索空間中越來越好的區(qū)域這樣一代一代 不斷繁衍下去最后收斂到群最適應(yīng)環(huán)境的個(gè)體求得問題的 最優(yōu)解。用遺傳算

16、法優(yōu)化聶小二粟支持向豪機(jī)參數(shù)主要過程如下：步驟1：設(shè)宜初始值如遺傳算法的初始種群規(guī)模、最大遺 傳代數(shù)八交叉概率、變異概率等。步驟2：對(duì)要優(yōu)化的參數(shù)根據(jù)其設(shè)定的范圍進(jìn)行二進(jìn)制編 碼隨機(jī)產(chǎn)生初始種群。染色體為各參數(shù)二逬制順序排列組成, 長(zhǎng)度即為各參數(shù)二進(jìn)制長(zhǎng)度之和。設(shè)賢遺傳代數(shù)忡數(shù)器心0。步驟3：計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度°這里將用小二篥 支持向愉機(jī)的分類正確率作為目標(biāo)函數(shù)值即個(gè)體的適應(yīng)度個(gè) 體對(duì)應(yīng)的參數(shù)的分類正綸率建高.則該個(gè)體的適應(yīng)度越大。步驟4：根據(jù)個(gè)體適應(yīng)度按照一定規(guī)則（這里采用輪盤賭 快）從當(dāng)前種群中選出個(gè)體進(jìn)入下一代。步驟矢選擇群體中的兩個(gè)個(gè)體引、衍作為父體以某個(gè)槪率 （交叉

17、槪率）進(jìn)行交叉操作產(chǎn)生兩個(gè)新個(gè)體。這里采用單點(diǎn)交 叉，交叉概率設(shè)為08。步驟6：隨機(jī)選擇種群中的個(gè)體以一定的槪率（變異概率） 進(jìn)行變異操作通過隨機(jī)改變個(gè)體中某些基因而產(chǎn)生新個(gè)體。 變異概率設(shè)為0.05o步驟7：終止條件判斷。若則轉(zhuǎn)到步驟2；若f>7'或 平均適應(yīng)度偵變化持續(xù)小亍某一常數(shù)超過一定代數(shù)則所得到 的具有最大適應(yīng)的個(gè)體作為最優(yōu)解輸出算法終止。步費(fèi)8：對(duì)得到的最優(yōu)解譯碼得到優(yōu)化的參數(shù)。3實(shí)驗(yàn)及結(jié)果這里選擇r東北常見的五種樹種的木材樣本建立了包含 1000幅圖像的圖像庫。其中包括白樺、紅松、落葉松、水曲柳和 柞木五種樹種的徑切和弦切樣本，共十類，毎類各100個(gè)樣本。 提取了這

18、些木材圖像的19個(gè)Lab顏色空間的顏色特征(包 括""丄分償、色相角心.色飽和度C，、色差dE、色相 追AH，七個(gè)fit的均值與標(biāo)準(zhǔn)差以及前5個(gè)分量與其均值的差 的均值)以此作為支持向址機(jī)的輸入。選擇每類樣本中的30 個(gè)作為參數(shù)優(yōu)化及最終分類的訓(xùn)練樣本另外的30個(gè)作為參數(shù) 優(yōu)化時(shí)的測(cè)試樣本,剩余的40個(gè)作為最終分類的測(cè)試樣本。實(shí) 驗(yàn)基于MATLAB R2007a實(shí)驗(yàn)平臺(tái)所用計(jì)算機(jī)配豪為:P4 3.00 CPU、256M內(nèi)存、80G磧盤、中文Windows XP操作系統(tǒng)。本文采用LS-SVMlab 具箱中提供的最小二乘支持向*機(jī) 模型將用遺傳算法優(yōu)化最小二乘支持向最機(jī)參數(shù)的方

19、法與此 工具箱中網(wǎng)格搜索優(yōu)化參數(shù)的方法進(jìn)行比較每種方法分別運(yùn) 行10次，初始參數(shù)值均在設(shè)定范圍內(nèi)隨機(jī)產(chǎn)生,最后將優(yōu)化得 到的參數(shù)構(gòu)造支持向發(fā)機(jī)模型進(jìn)行分類比較比較結(jié)果如表2 所示。«2 aftx法和網(wǎng)«S5RM優(yōu)化支持向機(jī)參魏flilURBF垓國(guó)數(shù))次敷逮傳算法兩格捜索算醫(yī)平均正«!*(%)優(yōu)蝕何()平均正«*(%)優(yōu)化時(shí)間()195.754425.3125"2510269.7188295.755764.406293.0011762.6719395.754807.343894.751 $482.6406495.5S062.703194.5014

20、415.9062596.254682.843893.759453.3438696.253019.9375M.5012183.59M796.257546.031294.2513166.6406895.55162.406294.0011284.125996.255846.937593.5013391.65621095.754835.031294.2513157.5平均值95.9345.295394.07512456.7797從表2的結(jié)果町以看d 用遺傳算法進(jìn)行優(yōu)化得到的總體 結(jié)果優(yōu)于網(wǎng)格搜索的優(yōu)化方法得到的結(jié)果井且在運(yùn)行時(shí)間上 大大縮短了。由于篇幅有限僅列出其它三種核因數(shù)參數(shù)優(yōu)化 的平均分類正確率

21、和優(yōu)化時(shí)間作為比較(10次)如表3所示。 哀3的結(jié)果中采用線性垓函數(shù)和務(wù)項(xiàng)式核函數(shù)用遺傳算快進(jìn) 行參數(shù)優(yōu)化在結(jié)果上優(yōu)于網(wǎng)格搜索的優(yōu)化方法得到的結(jié)果而 采用遺傳算法也實(shí)現(xiàn)了對(duì)多層感知器核負(fù)數(shù)參數(shù)的優(yōu)化.10次 的平均分類正確率達(dá)到了 80%以上。從各種核函數(shù)的結(jié)果對(duì) 比也可以看出，采用不同的核函數(shù)對(duì)支持向fit機(jī)分類器的分類 性能也有很大基舁其中采用高斯徑向基核西數(shù)和多層感知器 核更數(shù)的結(jié)果都比較好而采用線性核函數(shù)的分類結(jié)果并不理 想(僅有70悅左右)這也充分說明了核函數(shù)選擇的重要性。*3其它核Stttt化后的分類結(jié)果比較類旳塗傳算法網(wǎng)格捜索算醫(yī)平均 iE«*(«)優(yōu)比時(shí)何(

22、)平均正確車()優(yōu)化時(shí)間()多頊?zhǔn)浇雍瘮?shù)M.72512640.27593.35161.55線性核顒散71.3661.981269.00562.5344Sijmuid82.67242.00164結(jié)論本文提出了i種采用遺傳算法優(yōu)化最小二乘支持向應(yīng)機(jī)參 數(shù)的方法。對(duì)于支持向最機(jī)多數(shù)的選擇現(xiàn)在也只能采用各種 優(yōu)化算法進(jìn)行優(yōu)化而各種算法的尋優(yōu)性能不同采用遺傳算法 優(yōu)化支持向量機(jī)參數(shù)的方法充分利用了遺傳算法全局尋優(yōu)和很 強(qiáng)的搜索能力的優(yōu)點(diǎn)試驗(yàn)表明其在優(yōu)化結(jié)果和時(shí)間上均優(yōu)于 采用網(wǎng)格搜索算法，取得了較為満童的效果。參考文獻(xiàn)(1 )張學(xué)工關(guān)于統(tǒng)計(jì)學(xué)習(xí)理論與支持向機(jī)J口動(dòng)化學(xué)報(bào).2000, 26(1) ：32-

23、422杜樹新矣鐵軍模式識(shí)別中的支持向機(jī)方槎J浙江大學(xué)學(xué) 報(bào)：工學(xué) «,2003,37(5 )：521 -527.3 Suykcn J A K, Vandewallc J L«urt squarai support vector machine clasaifienf J . Neural Processing latere J999.9( 3) ：293 * 3004朱家元陳開支持向機(jī)算法研究J計(jì)算 機(jī)科學(xué).2003.30(7):157-1595 鄧乃揚(yáng)田英杰數(shù)據(jù)挖療中的新方 一支持向機(jī)M北京： 科學(xué)出版社.2004.6 Vapnik V. Sutistical Learning Theory M. New York： Wiley - Inter- science, 1998 7 王興玲李占域.基于網(wǎng)格搜索的支持向機(jī)核函的確定 J 中國(guó)海洋大學(xué)學(xué)報(bào)