基于RBF核的SVM學(xué)習(xí)算法的優(yōu)化計算

基于漢科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，武漢430081)摘 要在文對基于，y)的選定做了深入研究。分別探討了網(wǎng)格搜索法和雙線性搜索法以對它們進(jìn)行了改進(jìn)。通過結(jié)合雙線性搜索法和網(wǎng)格搜索法。提出了一種雙線性網(wǎng)格搜索法。實驗表明，雙線性網(wǎng)格搜索法能有效地結(jié)合雙線性搜索法訓(xùn)練量小和網(wǎng)格搜索法學(xué)習(xí)精度高的優(yōu)點提高學(xué)習(xí)精度和學(xué)習(xí)性能。關(guān)鍵詞 支持向量機(jī)331(2006)29019003 文獻(xiàn)標(biāo)識碼A 中圖分類號VM 3008 1)VM，is no a to n to VM BF a of to BF 言支持向量機(jī)(VM)結(jié)構(gòu)風(fēng)險最小化原則為理論基礎(chǔ)的一種新的機(jī)器學(xué)習(xí)方法。統(tǒng)計學(xué)習(xí)理論對有限樣本情況下模式識別中的一些根本性問題進(jìn)行了系統(tǒng)的理論研究，很大程度上解決了模型選擇與過學(xué)習(xí)問題、非線性和維數(shù)災(zāi)難問題、局部極小點等問題。支持向量機(jī)在手寫字符識別、網(wǎng)頁或文本自動分類、說話人識別、人臉檢測、計算機(jī)入侵檢測、基因分類、函數(shù)回歸、估計、函數(shù)逼近、時間序列預(yù)測及數(shù)據(jù)壓縮、文本過濾、數(shù)據(jù)挖掘、非線性系統(tǒng)控制等問題中，都有非常成功的應(yīng)用121。但是，沒有形成一個統(tǒng)一的模式。驗對比、大范圍的搜尋或者利用交叉驗證功能進(jìn)行尋優(yōu)。本文針對此現(xiàn)狀，分析了現(xiàn)有的模型選擇方法，并對其中的網(wǎng)格搜索法和雙線性搜索法進(jìn)行了改進(jìn)，改進(jìn)后的方法減少了且具有比網(wǎng)格搜索法更高的學(xué)習(xí)精度。本文第二章簡單地介紹了支持向量機(jī)的原理和支持向量機(jī)解決實際問題的基本步驟：第三章介紹了網(wǎng)格搜索和雙線性搜索兩種方法進(jìn)行參數(shù)選擇提出了對兩者的改進(jìn)方法：第四章詳細(xì)介紹了本文提出的雙線性網(wǎng)格搜索法。第五章為實驗，通過實驗對六章為結(jié)論。2支持向量機(jī)學(xué)習(xí)方法21支持向量機(jī)簡介二維兩類線性可分情況下，有很多可能的線性分類器可以把這組數(shù)據(jù)分割開，但是只有一個使兩類的分類間隔個線性分類器就是最優(yōu)分類超平面，與其它分類器相比，具有更好的泛化性。若樣本集x。，i=1，8(一1，+1)是線性可分的。則存在分類超平面b=O菇樣本集，b+l b一1艫一1在空間尺4中樣本搿=(筇1，一，舶)到分類超平面的距離d=x+|W 0，其中擴(kuò)塒。當(dāng)存在茗使得加；+6=1，則超平面的分類間隔m 】l W 1|。使分類間隔m 找最優(yōu)分類超平面的問題將轉(zhuǎn)化為求如下一個二次規(guī)劃問題：)=(礦戈。舶)1，i=1，2，式如下：f )=嘶一曇y(1)i=1 z 滿足約束條件：0nf，i=1，=ol=據(jù)育部留學(xué)回國人員科研啟動基金資助；湖北省教育廳重點項目(編號：2004者簡介：李琳(1981一)，女，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘；張曉龍(1963一)，男，教授，研究生導(dǎo)師，主要研究方向：機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘和生物信息學(xué)。190 200629計算機(jī)工程與應(yīng)用萬方數(shù)據(jù)個優(yōu)化的解必須滿足：啦(“礦省舶卜1)=0，i=1，為O少部分不為0的a對應(yīng)的樣本就是支持向量。最后得到分類判別函數(shù)為：1 g(x)=。，省)+6) (2)支持向量以通過兩類中任意一對支持向量取中值求得。根據(jù)上述易知，對于空間R。中任意樣本髫=(算l-，當(dāng)If(x)因為以處理當(dāng)類標(biāo)簽(特征之間的關(guān)系是非線性時的樣例。，y)(其中某些參數(shù)，1。另外，為參數(shù)的個數(shù)直接影響到模型選擇的復(fù)雜性。非常重要的一點是01)或者O。+rl，跨度非常大。而且，必須注意的是如，沒有兩個向量的內(nèi)積)163。(4)用交叉驗證找到最好的參數(shù)使用考慮兩個參數(shù)為參數(shù)的選擇并沒有一定的先驗知識，必須做某種類型的模型選擇(參數(shù)搜索)。目的是確定好的(C，y)使得分類器能正確地預(yù)測未知數(shù)據(jù)(即測試集數(shù)據(jù))，有較高的學(xué)習(xí)精度。值得注意的是得到高的訓(xùn)練正確率(即是分類器預(yù)測類標(biāo)簽已知的訓(xùn)練數(shù)據(jù)的正確率)不能保證在測試集上具有高的預(yù)測精度。因此，通常采用交叉驗證方法提高預(yù)測精度。將訓(xùn)練集合分成中一個子集用于測試。其它|一1個子集用于對分類器進(jìn)行訓(xùn)練。這樣，整個訓(xùn)練集中的每一個子集被預(yù)測一次，交叉驗證的正確率是可以防止過擬合的問題。本文使用了網(wǎng)格搜索和雙線性搜索兩種方法進(jìn)行參數(shù)(C，y)的選擇，通過綜合兩種方法的優(yōu)點，對原有的方法進(jìn)行了改進(jìn)。(5)用第(4)步得出的適合于此分類問題的最好參數(shù)6)在數(shù)據(jù)集上進(jìn)行測試得出該分類問題的學(xué)習(xí)精度。3 ，y)，有多種方法可以選擇171。本文主要應(yīng)用網(wǎng)格搜索法和雙線性搜索兩種方法來取得最佳(C，y)。31雙線性搜索法雙線性搜索法求解最優(yōu)參數(shù)是利用不同的(C，y)取值對應(yīng)的不同獻(xiàn)4】中提到，參數(shù)空間可分為欠訓(xùn)練過訓(xùn)練區(qū)和“好區(qū)”。以作為參數(shù)空間的坐標(biāo)，經(jīng)大量實驗證明，學(xué)習(xí)精度最高的參數(shù)組合(C，y)將集中出現(xiàn)在“好區(qū)”中的直線附近。由此，雙線性搜索法采用如下步驟81：(1)對線性得以之為參數(shù)的線性之為C。(2)對定C，對滿足y=，y)，訓(xùn)練據(jù)對其學(xué)習(xí)精度的估算，得到最優(yōu)參數(shù)。32網(wǎng)格搜索法網(wǎng)格搜索法是將值，對M個(C，y)的組合，分別訓(xùn)練不同的估計其學(xué)習(xí)精度，從而在，y)的組合中得到學(xué)習(xí)精度最高的一個組合作為最優(yōu)參數(shù)。本文取M=N=27，4，2“，216】，7的取值范圍為【2。5，2。14，210 2“】，共729個(C，7)的組合。由此可知，完成一個完全的網(wǎng)格搜索是非常費時的，作為網(wǎng)格搜索法的一種改進(jìn)我們可以設(shè)定：首先用一個步長為22的(C，y)組合，得到學(xué)習(xí)精度最高的的值。然后在這兩個值旁的一定范圍內(nèi)進(jìn)行一次更細(xì)致的網(wǎng)格搜索。為詳細(xì)說明此方法，我們將其應(yīng)用于數(shù)據(jù)庫文對于所有學(xué)習(xí)精度的估計，均采用k=5)。在對該數(shù)據(jù)集進(jìn)行歸一化后先用網(wǎng)格搜索法對數(shù)據(jù)集進(jìn)行交叉驗證求得最高的學(xué)習(xí)精度為99243 9，最好的參數(shù)組合為(23，22)。對于改進(jìn)的網(wǎng)格搜索法，先用一個步長為22的(C，y)組合，求得最高的學(xué)習(xí)精度為986767，最好的參數(shù)為(24，2-)(見圖1)。然后在這個最好參數(shù)旁正負(fù)22的范圍內(nèi)，以磐25為步長進(jìn)行一次更精細(xì)的網(wǎng)格搜索。如第一步求得最好的參數(shù)為(24，21)，圖2即第二步在C22 26】，【2，23的范圍內(nèi)以2”為步長求得最高的學(xué)習(xí)精度為99432 9，最好的參數(shù)為(24，2蟛)。從圖可以看出，改進(jìn)的網(wǎng)格搜索法在減少了訓(xùn)練量的情況下，可以達(dá)到比網(wǎng)格搜索法更高的學(xué)習(xí)精度。計算機(jī)工程與應(yīng)用200629 191萬方數(shù)據(jù)表1 不同方法得到的學(xué)習(xí)精度，括號中列出了對應(yīng)的參數(shù)(C，)圈l 改進(jìn)的網(wǎng)格搜索法第一步(4，26 y=2“，2“，211】lg(0 990，985980一20 9751510|g(5O0一1)圖2改進(jìn)的網(wǎng)格搜索法第二步(C=22，2”，26 T=2一，24”，23)4雙線性網(wǎng)格搜索法41 雙線性搜索法與網(wǎng)格搜索法的比較與雙線性搜索法相比網(wǎng)格搜索法的優(yōu)點是可以并行處理每個為它們是相互獨立的。而雙線性搜索法需要先得到線性能開始計算量上(基于網(wǎng)格搜索法為O(雙線性搜索法僅為O(N)。但由于雙線性搜索法對線性C、05C、2練相應(yīng)參數(shù)的為改進(jìn)的雙線性搜索法圈。42雙線性網(wǎng)格搜索法由以上的比較可知：網(wǎng)格搜索法具有較高的學(xué)習(xí)精度但計算量較大，費時較多；雙線性搜索法計算量較小，費時少，但與網(wǎng)格搜索法相比，學(xué)習(xí)精度略低。為了在計算量小、費時少的基礎(chǔ)上，得到較高的學(xué)習(xí)精度，現(xiàn)將以上兩種方法的優(yōu)點結(jié)合起來，稱為雙線性網(wǎng)格搜索法。具體步驟如下：(1)對線性得以之為參數(shù)的線性之為C。由于雙線性搜索法對線性C、05C、2練相應(yīng)參數(shù)的2)對別將上一步中得到的C、05001629計算機(jī)工程與應(yīng)用2滿足，y)，訓(xùn)練據(jù)對其學(xué)習(xí)精度的估算，得到最優(yōu)參數(shù)。(3)在上一步中得到的最優(yōu)參數(shù)(C，y)旁正負(fù)22的范圍內(nèi)，以202見3。2節(jié)中改進(jìn)的網(wǎng)格搜索法第二步)，此時得到的就是雙線性網(wǎng)格搜索法的學(xué)習(xí)精度。由以上步驟可見。該方法是將雙線性搜索法和網(wǎng)格搜索法結(jié)合起來。首先用改進(jìn)的雙線性搜索法得到最優(yōu)參數(shù)(C，y)，然后用改進(jìn)的網(wǎng)格搜索法第2步進(jìn)行網(wǎng)格搜索(即在這個最好參數(shù)旁以20這樣就得到了雙線性網(wǎng)格搜索法的學(xué)習(xí)精度。5 實驗該文的實驗樣本采用別用網(wǎng)格搜索法、雙線性搜索法、改進(jìn)的雙線性搜索法和雙線性網(wǎng)格搜索法進(jìn)行了測試。測試結(jié)果如表1、表2所示。襲2不同方法導(dǎo)致的訓(xùn)練量(訓(xùn)練練量 網(wǎng)格搜索法雙線性搜索法改進(jìn)的雙線性搜索法雙線性網(wǎng)格搜索法表1中列出了4種不同方法的學(xué)習(xí)精度。其中雙線性網(wǎng)格搜索法與網(wǎng)格搜索法相比。數(shù)據(jù)集據(jù)集線性網(wǎng)格搜索法與改進(jìn)的雙線性搜索法相比，6個數(shù)據(jù)集的學(xué)習(xí)精度前者均高于后者。而從表2列出的這4種不同方法的訓(xùn)練量可以看出雙線性網(wǎng)格搜索法的訓(xùn)練量較網(wǎng)格搜索法有了較大的減少，因此總的來說它的性能是最好的。從以上實驗可以看出網(wǎng)格搜索法訓(xùn)練量最大，有較高的學(xué)習(xí)精度。雙線性搜索法訓(xùn)練量最小，與其它方法相比，學(xué)習(xí)精度略低：而雙線性網(wǎng)格搜索法綜合了雙線性搜索法和網(wǎng)格搜索法的優(yōu)點，訓(xùn)練量介于兩者之問，而學(xué)習(xí)精度幾乎全部達(dá)到網(wǎng)格搜索法的高度。因此，對訓(xùn)練樣例少的數(shù)據(jù)集，可以采用網(wǎng)格搜索法或者雙線性網(wǎng)格搜索法，得到高的學(xué)習(xí)精度；對訓(xùn)練樣例龐大的數(shù)據(jù)集。網(wǎng)格搜索法常常非常耗時，此時可采用雙線性網(wǎng)格搜索法在相對較少的時間內(nèi)獲得相似的學(xué)習(xí)精度。6結(jié)論本文提出以非線性函數(shù)為核的學(xué)習(xí)情形中雙線性網(wǎng)格搜索法可以有效地改進(jìn)學(xué)習(xí)性能和提高學(xué)習(xí)精度。對轉(zhuǎn)204頁)|I|三505050鰩鴝卯卯貼萬方數(shù)據(jù)(4)每一個任務(wù)樹和服務(wù)實例都注冊了一個監(jiān)聽器(采用異步通知機(jī)制(現(xiàn)任務(wù)的協(xié)同工作。服務(wù)實例運行期間可以發(fā)送數(shù)據(jù)給客戶端任務(wù)樹的監(jiān)控器，從而指導(dǎo)任務(wù)樹結(jié)構(gòu)的動態(tài)更新以執(zhí)行新的任務(wù)，也可以在客戶端將接收到的數(shù)據(jù)進(jìn)行處理，再發(fā)給指定子服務(wù)節(jié)點集，實現(xiàn)服務(wù)節(jié)點集之間的協(xié)同工作。任務(wù)監(jiān)控器還可以發(fā)送監(jiān)控命令(例如通過各服務(wù)節(jié)點查詢服務(wù)運行狀態(tài)。(5)全局信息中心(務(wù)器上的全局資源監(jiān)控器對所有相關(guān)注冊資源進(jìn)行監(jiān)控當(dāng)發(fā)現(xiàn)已分配資源不可用、或無法保證服務(wù)質(zhì)量(，采用選)。(6)所有的服務(wù)及系統(tǒng)控制管理器和服務(wù)提供者組件可以通過全局信息中心服務(wù)器的版本控制服務(wù)(行在線升級。4系統(tǒng)基本流程根據(jù)上述系統(tǒng)邏輯層次結(jié)構(gòu)和基本框架，本系統(tǒng)的基本流程如圖3所示。(1)系統(tǒng)將前端設(shè)備收集到的各種數(shù)據(jù)或經(jīng)過整理的數(shù)據(jù)進(jìn)行預(yù)處理。主要包括文件格式識別、不同編碼格式的解碼、碼制歸一和格式清洗、多語種自動識別和自動分詞等處理，如果是加密信息還需對其進(jìn)行解密。(2)使用分布式數(shù)據(jù)庫或數(shù)據(jù)倉庫技術(shù)對預(yù)處理后的數(shù)據(jù)進(jìn)行存儲并建立索引。(3)對數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行分類和聚類處理，以利快速檢索和數(shù)據(jù)挖掘處理。(4)利用圖2所示基本框架對反洗錢線索進(jìn)行數(shù)據(jù)檢索和關(guān)聯(lián)挖掘。(5)對檢索和挖掘的結(jié)果進(jìn)行評價，并使用用戶可識別的知識表達(dá)方式將結(jié)果返回給用戶。前端收集的文件或經(jīng)整理的數(shù)據(jù)數(shù)據(jù)預(yù)處理經(jīng)鋸密、碼制歸一后的數(shù)據(jù)數(shù)據(jù)存儲與建立索據(jù)分類與聚類、數(shù)據(jù)檢索與挖掘時將使用數(shù)據(jù)庫，在進(jìn)行數(shù)據(jù)分類和聚類、數(shù)據(jù)檢索與關(guān)聯(lián)挖掘、結(jié)構(gòu)評價與知識表達(dá)處理時將使用專家系統(tǒng)和知識庫。(收稿日期：2006年4月)參考文獻(xiàn)1李瑞軒，盧正鼎多數(shù)據(jù)庫系統(tǒng)原理與技術(shù)【M】北京：電子工業(yè)出版社，20042“u u u 001；5(4)3H G W H in I 9989984陳云開電匯監(jiān)控：反洗錢利器金融電子化，2004；(6)：58595李東榮，馮菊平，陳云開等澳大利亞反洗錢與信息技術(shù)應(yīng)用【J中國外匯管理，2004；(8)：24255陳云開，羅強(qiáng)】金融電子化，2004；(8)：7476(上接186頁)4A 997：4275，a in 000：33446 HA 005；(173)：227達(dá)時間序列數(shù)據(jù)挖掘與應(yīng)用M浙江：浙江大學(xué)出版社，20048 R，in 1of an994：4194299a 994(上接192頁)最優(yōu)參數(shù)(C，7)的選定中，比較了網(wǎng)格搜索法、雙線性搜索法以及雙線性闌格搜索法。實驗證明雙線性網(wǎng)格搜索法將雙線性搜索法訓(xùn)練量小和網(wǎng)格搜索法學(xué)習(xí)精度高的優(yōu)點很好地集于一身，可以改進(jìn)學(xué)習(xí)性能、提高學(xué)習(xí)精度。我們將來的：進(jìn)一步驗證它的實用性。(收稿日期：2005年12月)參考文獻(xiàn)1V N 9952張曉龍，李琳支持向量機(jī)及其應(yīng)用研究【J】計算機(jī)應(yīng)用研究200522(增刊)：912204 200629計算機(jī)工程與應(yīng)用3 Sto i 9974 S， Ja003；15：166716895 T， JA VM MO0036，995；20：27329370 et 002；46：1311598王鵬，朱小燕基于計算機(jī)工程與應(yīng)用，2003；39(24)：72739重墅戛鯉贏萬方數(shù)據(jù)基于李琳， 張曉龍， 武漢科技大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院,武漢,430081刊名： 計算機(jī)工程與應(yīng)用英文刊名： (期)： 2006,42(29)被引用次數(shù)： 17次參考文獻(xiàn)(9條) 持向量機(jī)及其應(yīng)用研究 2005( S to J 文期刊 J A VM 文期刊 于刊論文003(24)條)1. 于刊論文9(24)2. 種快速的刊論文6(15)3. 刊論文7(11)4. 于刊論文然科學(xué)版）2009,26(3)引證文獻(xiàn)(17條)用兩級分