畢業(yè)論文----基于遺傳算法的核支持向量機(jī)研究

1、<p>　　基于遺傳算法的核支持向量機(jī)研究</p><p>　　摘 要：針對(duì)傳統(tǒng)支持向量機(jī)識(shí)別能力的缺陷，本文重點(diǎn)研究了基于支持向量機(jī)和遺傳算法的混合算法，并就適定性函數(shù)做了深入研究。該算法的主要思想是在分類建模時(shí)使用支持向量機(jī)模型，但在求解決策超平面的最優(yōu)化問(wèn)題時(shí)使用遺傳算法。混合算法能夠直接得到分類超平面的系數(shù)，這在經(jīng)典的支持向量機(jī)分類技術(shù)中很難實(shí)現(xiàn)。根據(jù)具體的數(shù)學(xué)模型、染色體及適定性函數(shù)的不同，

2、分別建立了三種混合算法。仿真結(jié)果顯示了這一算法廣闊的發(fā)展前景。</p><p>　　關(guān)鍵詞：支持向量機(jī)；核方法；遺傳算法；分類問(wèn)題</p><p>　　Abstract：Concerning the shortcomings of recognition of traditional support vector machines, this paper focuses on the hy

3、bridization between support vector machines and genetic algorithm and does an in-depth qualitative research on fitness function. The main idea of the algorithm is considering the classification task as in SVM but using a

4、n genetic algorithm to solve the optimization problem of determining the decision function. They can explicitly acquire the coefficients of the separating hyper</p><p>　　Key words：support vector machine ker

5、nel methods genetic algorithm classification problem</p><p><b>　　引 言</b></p><p>　　核支持向量機(jī)(KSVMs)[1]是近幾年發(fā)展起來(lái)的主要用于解決分類問(wèn)題的新算法，它基于嚴(yán)密的統(tǒng)計(jì)學(xué)習(xí)理論，通過(guò)巧妙地引入核函數(shù)，將低維問(wèn)題通過(guò)非線性映射投射到高維特征空間，并在特征空間中采用線性可

6、分支持向量機(jī)解決分類問(wèn)題。KSVMs也是數(shù)據(jù)挖掘技術(shù)的新方法，在模式分類、函數(shù)逼近、概率密度估計(jì)及回歸分析等理論領(lǐng)域，支持向量機(jī)取得了良好的效果，并已成功應(yīng)用到諸如手寫(xiě)數(shù)字識(shí)別、文本分類、語(yǔ)音識(shí)別、人臉檢測(cè)等技術(shù)領(lǐng)域。遺傳算法(GA)[2]是模擬生物在自然環(huán)境下的遺傳和進(jìn)化過(guò)程而形成的一種自適應(yīng)全局優(yōu)化概率搜索方法，與其他尋優(yōu)算法相比，遺傳算法有許多獨(dú)特的優(yōu)點(diǎn)。因此，若我們能將KSVM和GA兩種方法有機(jī)整合到一起，可能得到一個(gè)具有更好分

7、類效果、更高靈活性的混合算法[3]。</p><p>　　基于遺傳算法的核支持向量機(jī)新算法</p><p><b>　　2.1 新算法總說(shuō)</b></p><p>　　圖2-1展示了新算法的基本步驟。</p><p>　　圖2-1 新算法基本步驟</p><p>　　2.2 基于遺傳算法的核支持向

8、量機(jī)新算法</p><p><b>　　1. 混合算法一</b></p><p><b>　　(1) 數(shù)學(xué)模型</b></p><p><b>　　(2-1)</b></p><p>　　其中為訓(xùn)練樣本總數(shù)。求解上面最優(yōu)化問(wèn)題，得到最優(yōu)解，則分類函數(shù)為</p>&

9、lt;p><b>　　(2-2)</b></p><p><b>　　(2) 適定性函數(shù)</b></p><p><b>　　設(shè)定適定性函數(shù)為：</b></p><p><b>　　(2-3)</b></p><p><b>　　函數(shù)為&l

10、t;/b></p><p><b>　　(2-3)</b></p><p>　　其中為(2-1)中模型對(duì)“軟邊界”的懲罰因子，為(2-1)中對(duì)不滿足“約束條件”樣本的懲罰。我們可以很容易理解式(2-3)適定性函數(shù)設(shè)置的理由。</p><p>　　下面說(shuō)明如上定義適定性函數(shù)的原因：式(2-3)中式(1)的最小化就是分類邊界的最大化，目的是增

11、強(qiáng)算法的魯棒性，提高預(yù)測(cè)正確率；式(2)最小化就是降低訓(xùn)練樣本分類邊界的模糊程度，目的是提高訓(xùn)練樣本分類正確性；式(3)最小化目的是使種群中個(gè)體盡可能滿足模型(2-1)中的限制條件。</p><p>　　(3) 算法具體步驟</p><p>　　1) 編碼方案及染色體設(shè)置</p><p>　　由于和都是實(shí)數(shù)，所以我們采用浮點(diǎn)編碼方式("double vec

12、tor")。由于松弛變量在適定性函數(shù)中出現(xiàn)，我們也將它體現(xiàn)在染色體的結(jié)構(gòu)中。和人工設(shè)定它的值（如10，100，1000等），值的大小體現(xiàn)了對(duì)約束條件的重視程度。在本模型的仿真中，設(shè)定，當(dāng)然可以根據(jù)自己需要在程序中改變這兩個(gè)“懲罰因子”。</p><p>　　這樣，染色體結(jié)構(gòu)為：</p><p><b>　　(2-4)</b></p><p

13、>　　其中，為特征數(shù)，為樣本數(shù)目。</p><p><b>　　初始種群設(shè)定</b></p><p>　　初始種群由滿足下列條件的染色體向量隨機(jī)生成：</p><p><b>　　(2-5)</b></p><p><b>　　遺傳算子的設(shè)定</b></p>

14、<p>　　遺傳算子選擇如下：Tournament Selection(錦標(biāo)賽選擇)和Elitist Selection(最佳個(gè)體保存法)、Intermediate Crossover(中間交叉)、Uniform Mutation(均勻變異)。</p><p><b>　　停機(jī)條件設(shè)定</b></p><p>　　a)某固定代數(shù)；b)某固定停滯代數(shù)；c)適

15、定性函數(shù)平均變化率小于某一固定值；d)適定性函數(shù)值小于某一固定值。</p><p>　　以上任意一個(gè)條件達(dá)到算法就停止。</p><p><b>　　2. 混合算法二</b></p><p>　　混合算法二將核參數(shù)加入進(jìn)化，這樣可能通過(guò)一次進(jìn)化得到最優(yōu)核參數(shù)，同時(shí)達(dá)到更好的分類和預(yù)測(cè)效果。</p><p>　　混合算法二

16、的數(shù)學(xué)模型、適定性函數(shù)、遺傳算子和停機(jī)條件的設(shè)定同混合算法一。</p><p>　　(1) 編碼方案及染色體設(shè)定</p><p>　　由于加入染色體的“基因”也是普通的實(shí)數(shù)，所以仍采用浮點(diǎn)方式編碼染色體。</p><p>　　這樣，染色體結(jié)構(gòu)變?yōu)椋?lt;/p><p><b>　　(2-6)</b></p>&

17、lt;p>　　其中，為特征數(shù)；為樣本數(shù)目；為RBF核參數(shù)；和為多項(xiàng)式核參數(shù)，其中為多項(xiàng)式指數(shù)，為正整數(shù)；和為核的兩個(gè)實(shí)參數(shù)。</p><p>　　(2) 初始種群設(shè)定</p><p>　　初始種群由滿足下列條件的染色體向量隨機(jī)生成：</p><p>　　2-7)

18、 </p><p>　　但是，上面設(shè)定的種群的搜索空間過(guò)大，必然導(dǎo)致收斂速度過(guò)慢，甚至由于初始種群數(shù)量太小、種進(jìn)化群代數(shù)不夠等情況無(wú)法得到收斂解。因此，綜合考慮核參數(shù)的實(shí)際意義以及的運(yùn)行特點(diǎn)，設(shè)定實(shí)際搜索空間為：</p><p>　　(2-8)

19、 </p><p>　　需要說(shuō)明的是，多項(xiàng)式核參數(shù)的實(shí)際搜索空間比原始空間大大減少。最初仿真實(shí)驗(yàn)中，設(shè)定的范圍是，然而實(shí)驗(yàn)得到的訓(xùn)練和預(yù)測(cè)的正確率都不到50%。跟蹤調(diào)試后發(fā)現(xiàn)，所有的分類結(jié)果都是正數(shù)，且進(jìn)化得到的值很大。進(jìn)一步研究發(fā)現(xiàn)，分類效果不好，是的初始種群范圍過(guò)大所致。將c范圍縮小到0和10之間，得到了較好的分類效果?？梢?jiàn)初始種群的設(shè)定也是相當(dāng)重要的。</p><p>

20、<b>　　3. 混合算法三</b></p><p><b>　　(1) 數(shù)學(xué)模型</b></p><p>　　無(wú)論是混合算法一還是混合算法二，我們都假設(shè)每一個(gè)訓(xùn)練樣本對(duì)預(yù)測(cè)的貢獻(xiàn)是一樣大的。但是實(shí)際應(yīng)用中，每個(gè)樣本對(duì)分類正確性的影響是不相同的，為了正確體現(xiàn)這種差別，我們可以對(duì)樣本進(jìn)行加權(quán)，這樣就得到了如下的數(shù)學(xué)模型：</p>&l

21、t;p><b>　　(2-9)</b></p><p>　　其中，是第個(gè)樣本的權(quán)值，體現(xiàn)了我們對(duì)第個(gè)樣本能否被正確分類的重視程度；為對(duì)“軟邊界”的懲罰因子；為訓(xùn)練樣本總數(shù)。</p><p><b>　　(2) 適定性函數(shù)</b></p><p>　　相應(yīng)地，適定性函數(shù)設(shè)置為：</p><p>

22、<b>　　(2-10)</b></p><p><b>　　函數(shù)為</b></p><p><b>　　(2-11)</b></p><p>　　其中為(3-9)中模型對(duì)“軟邊界”的懲罰因子，為(3-9)中不滿足“約束條件”樣本的懲罰因子，是第個(gè)樣本的權(quán)值。</p><p>

23、　　(3) 算法具體步驟</p><p>　　編碼方案、染色體設(shè)定、初始種群、遺傳算子選擇等，可以參照混合算法一或者混合算法二。</p><p><b>　　(4) 算法預(yù)處理</b></p><p>　　綜合上面分析可知，我們需要預(yù)先確定每個(gè)訓(xùn)練樣本的權(quán)值。這需我們對(duì)訓(xùn)練樣本有一個(gè)充分的了解或者通過(guò)“預(yù)處理”技術(shù)得到。</p>

24、<p><b>　　算法仿真及分析</b></p><p>　　為了驗(yàn)證本文提出新算法的有效性，本章使用數(shù)據(jù)庫(kù)中的數(shù)據(jù)集進(jìn)行仿真。數(shù)據(jù)集共270個(gè)數(shù)據(jù)樣本，特征數(shù)為13，共2類。將數(shù)據(jù)集合分成訓(xùn)練集和預(yù)測(cè)集合兩部分，隨機(jī)選前200個(gè)樣本作為訓(xùn)練數(shù)據(jù)，剩下70個(gè)作為預(yù)測(cè)樣本。仿真結(jié)果如下。</p><p><b>　　1. 混合算法一</b&g

25、t;</p><p>　　每個(gè)核函數(shù)分別進(jìn)行10次仿真，其中核參數(shù)設(shè)置如表，統(tǒng)計(jì)結(jié)果下表：</p><p>　　從表中可以看出，在沒(méi)有用到“k-折交叉驗(yàn)證”的情況下，得到的分類結(jié)果是非常好的。在如表所設(shè)的核參數(shù)和懲罰因子條件下，多項(xiàng)式核和核的訓(xùn)練樣本和預(yù)測(cè)樣本的平均正確率都達(dá)到了80%以上，簡(jiǎn)單內(nèi)積核的平均正確率也達(dá)到了70%以上。從表還可以看出本算法的實(shí)時(shí)性是很好的。</p>

26、<p>　　2. 混合算法一改進(jìn)</p><p>　　遺傳算法還有一個(gè)好處，就是它可以與一些其它的尋優(yōu)算法結(jié)合使用，這樣可能達(dá)到更好的搜索結(jié)果。本節(jié)以"模式搜索"算法與遺傳算法結(jié)合為例，研究這種改進(jìn)混合算法的優(yōu)劣。</p><p>　　對(duì)四個(gè)核函數(shù)分別進(jìn)行10次、10次、5次、5次仿真，其中核參數(shù)設(shè)置如表，仿真結(jié)果如下：</p><p&

27、gt;　　對(duì)比表3-1和表3-2，可知簡(jiǎn)單內(nèi)積核函數(shù)的訓(xùn)練和預(yù)測(cè)的正確率都有所提高，這體現(xiàn)了加入模式搜索算法的效果。但是，同樣可以明顯地觀察到，改進(jìn)算法平均運(yùn)行時(shí)間比混合算法一長(zhǎng)了十倍以上。綜上可知，對(duì)分類正確率要求高的問(wèn)題，可以考慮加入其它尋優(yōu)算法提高分類正確率，并且需要經(jīng)過(guò)嚴(yán)格驗(yàn)證。然而對(duì)于時(shí)效性要求較高的問(wèn)題，這樣的改進(jìn)意義不是很大。</p><p><b>　　3. 混合算法二</b>

28、;</p><p>　　每個(gè)核函數(shù)分別進(jìn)行10次仿真，得到的最優(yōu)核參數(shù)和分類正確率結(jié)果如下：</p><p>　　對(duì)比表3-1和表3-3，可知訓(xùn)練集和預(yù)測(cè)集的分類正確率總體來(lái)說(shuō)有所提高，尤其對(duì)混合算法一中分類正確率較低的核。雖然多項(xiàng)式核函數(shù)分類正確率有一點(diǎn)降低，但平均運(yùn)行時(shí)間卻減少了。</p><p>　　4. 混合算法二改進(jìn)</p><p>

29、;　　本節(jié)將“優(yōu)化工具箱”和遺傳算法結(jié)合，進(jìn)一步研究這種改進(jìn)混合算法的優(yōu)劣。為了方便與前面的結(jié)果進(jìn)行比較，其它設(shè)定不變。對(duì)四個(gè)核函數(shù)分別運(yùn)行了5次實(shí)驗(yàn)，得到的最優(yōu)核參數(shù)和分類正確率結(jié)果如下：</p><p>　　對(duì)比表3-3和表3-4，可知到對(duì)數(shù)據(jù)集，最優(yōu)核參數(shù)大約為3；多項(xiàng)式最優(yōu)核參數(shù)在2附近，為1。加入“優(yōu)化工具箱”的混合算法二的分類正確率并沒(méi)有明顯的提高，甚至對(duì)于有些核函數(shù)還降低了很多，比如多項(xiàng)式核。<

30、;/p><p>　　縱觀上面四個(gè)仿真實(shí)驗(yàn)結(jié)果，簡(jiǎn)單內(nèi)積核的分類效果很好，說(shuō)明數(shù)據(jù)復(fù)雜度不是很高，基本線性可分。核的效果也不錯(cuò)，多項(xiàng)式核的效果還算可以但不是很穩(wěn)定，而核在四個(gè)實(shí)驗(yàn)中表現(xiàn)都不是很好。</p><p><b>　　結(jié) 論</b></p><p>　　支持向量機(jī)自從90年代中期興起以來(lái)由于其優(yōu)良的性能迅速成為研究熱點(diǎn)，然而支持向量機(jī)的解法

31、一直是一個(gè)難題。本文參考國(guó)內(nèi)外支持向量機(jī)技術(shù)最新研究進(jìn)展，將遺傳算法的“優(yōu)勝劣汰，適者生存”思想應(yīng)用到支持向量機(jī)解法中，提出了一種新的基于遺傳算法的核支持向量機(jī)技術(shù)，在應(yīng)用智能算法解決支持向量機(jī)求解方面做出了自己的貢獻(xiàn)。</p><p><b>　　本文主要工作如下：</b></p><p>　　(1) 針對(duì)傳統(tǒng)的支持向量機(jī)解法不能實(shí)時(shí)求出分類超平面系數(shù)這一問(wèn)題進(jìn)行了

32、分析，根據(jù)支持向量機(jī)原問(wèn)題的數(shù)學(xué)模型，建立了混合算法一。設(shè)定了相關(guān)的適定性函數(shù)，并將分類超平面的系數(shù)和松弛變量編入染色體中進(jìn)行進(jìn)化尋優(yōu)。最后用仿真，并得到了很好的分類結(jié)果。</p><p>　　(2) 將核參數(shù)也加入到染色體編碼中，使算法得到最優(yōu)分類超平面的同時(shí)，進(jìn)化得到最優(yōu)核參數(shù)，這就是混合算法二。通過(guò)仿真，混合算法二的分類效果優(yōu)于混合算法一。</p><p>　　(3) 混合算法三：考

33、慮到單個(gè)樣本對(duì)分類正確性的貢獻(xiàn)不同，引入“樣本權(quán)值”的概念，改進(jìn)了經(jīng)典支持向量機(jī)數(shù)學(xué)模型，并重新設(shè)定了適定性函數(shù)。</p><p>　　(4) 針對(duì)混合算法一和混合算法二各自提出改進(jìn)算法：在遺傳算法中加入其它尋優(yōu)算法。如將“模式搜索”加入混合算法一、“最優(yōu)化工具箱”加入混合算法二。并分別對(duì)這兩個(gè)改進(jìn)算法進(jìn)行了仿真，對(duì)比、分析了仿真結(jié)果。</p><p><b>　　參考文獻(xiàn)<

34、;/b></p><p>　　鄧乃揚(yáng), 田英杰. 數(shù)據(jù)挖掘中的新方法--支持向量機(jī). 2004:49-342</p><p>　　朱劍英. 智能系統(tǒng)非經(jīng)典數(shù)學(xué)方法. 華中科技大學(xué)出版社，1999:239-283</p><p>　　R. Stoean, M. Preuss and C. Stoean. Concerning the Potential of