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

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