支持向量機(jī)的改進(jìn)與訓(xùn)練分類器的制備

支持向量機(jī)的改進(jìn)與訓(xùn)練分類器的制備

1改進(jìn)的svm—引言支持向量機(jī)svm（支持向量機(jī)）以其強(qiáng)泛化能力而聞名，并受到人們的喜愛。僅考慮類的邊界，使用較少的向量（支持向量）進(jìn)行分類。另一方面，這兩個邊緣之間的寬度最大（分類邊界位于兩個邊緣之間）。另一方面，需要注意的是，錯誤的成本不應(yīng)該太高?？紤]到這兩個因素的結(jié)果是，以下公式中的最小值為：。1/h+l(e)?其中h表示兩類的邊界之間的寬度,l(e)表示錯分帶來的損失.爭取最大的邊界寬度是為了保證分類器具有較強(qiáng)的泛化能力,同時這里的“最大”是有條件的,就是不能付出太多的錯分代價(jià),SVM是這兩種要求折衷的結(jié)果.在訓(xùn)練分類器時,SVM的著眼點(diǎn)在于兩類的交界部分,那些混雜在另一類中的點(diǎn)往往無助于提高分類器的性能,反而會大大增加訓(xùn)練器的計(jì)算負(fù)擔(dān),同時它們的存在還可能造成過學(xué)習(xí),使泛化能力減弱.基于這種想法,本文提出了一種改進(jìn)的SVM——NN-SVM:它先對訓(xùn)練集進(jìn)行修剪,根據(jù)每個樣本與其最近鄰(nearestneighbor)類標(biāo)的異同決定其取舍,然后再用SVM訓(xùn)練得到分類器.實(shí)驗(yàn)表明,NN-SVM相比SVM在分類正確率、分類速度以及適用的樣本規(guī)模上都較優(yōu).本文第2節(jié)介紹SVM,第3節(jié)給出NN-SVM的算法,第4節(jié)給出實(shí)驗(yàn)結(jié)果及相關(guān)分析,最后是結(jié)論.2支持向量機(jī)的含義SVM是支持向量機(jī)的簡稱,是統(tǒng)計(jì)學(xué)習(xí)理論中最年輕的內(nèi)容,也是最實(shí)用的部分.其核心內(nèi)容是在1992到1995年間提出的,目前仍處在不斷發(fā)展階段.詳細(xì)內(nèi)容參見文獻(xiàn).支持向量機(jī)可用于模式識別、回歸分析、主成分分析等.下面以模式分類為例來介紹支持向量機(jī)的含義.給定一組訓(xùn)練數(shù)據(jù)(x1,y1),?,(xl,yl),xi∈Rn,yi∈{+1,-1},i=1,2??,l.我們要尋找一個分類規(guī)則I(x),使它能對未知類別的新樣本(新樣本與訓(xùn)練樣本獨(dú)立同分布)作盡可能正確的劃分.支持向量機(jī)用于分類問題其實(shí)就是尋找一個最優(yōu)分類超平面,把此平面作為分類決策面.同時它還通過引進(jìn)核函數(shù)巧妙地解決了在將低維空間向量映射到高維空間向量時帶來的“維數(shù)災(zāi)難”問題.2.1sv的分類處理在訓(xùn)練集線性可分情形,SVM就是要構(gòu)造一個最優(yōu)超平面(ω?x)+b=0(1)這個超平面既要滿足下面的約束條件yi[(ω?xi)+b]≥1,i=1,2??,l(2)同時還要使下面的函數(shù)取得最小值?(ω)=12|ω|2=12(ω?ω)(3)通過求解最優(yōu)化問題可得最優(yōu)超平面的形式如下∑SVyiα0i(x?xi)+b0=0(4)其中SV表示支持向量,α0i是拉格朗日乘子.在訓(xùn)練集線性不可分時,我們引進(jìn)松弛因子ξi≥0及懲罰參數(shù)C.這時需要做的是在約束yi((ω·xi)+b)≥1-ξi,i=1,2,…,l下最小化函數(shù)?(ξ)=12?|ω|2+Cl∑i=1ξi.類似可得最優(yōu)超平面.有了最優(yōu)超平面,分類規(guī)則或分類函數(shù)只要取I(x)=sgn∑SVyiα0i(x·xi)+b0即可.2.2kx,y型支持向量機(jī)支持向量機(jī)特點(diǎn)之一在于核函數(shù)的引入.我們知道,低維空間向量集往往難于劃分.因此,自然想把它們映射到高維空間,但隨之而來的是計(jì)算復(fù)雜度的大大增加,核函數(shù)巧妙地解決了這個問題.若函數(shù)K(x,y)滿足Mercer條件,則K(x,y)=?(x)·?(y),其中?表示某個映射(未必知其具體表達(dá)式).這樣,只要適當(dāng)選取核函數(shù)我們就可以得到對應(yīng)高維空間的分類函數(shù)Ι(x)=sgn(∑SVyiα0iΚ(x,xi)+b0)(5)其中,?(x),?(y)是比x,y更高維的向量(注意我們不必知道?的具體形式),由于K(x,y)只涉及x,y,因此計(jì)算沒有涉及高維運(yùn)算.我們將分類函數(shù)(決策函數(shù))類型為式(5)的學(xué)習(xí)機(jī)稱為支持向量機(jī).3改進(jìn)的svm-n-svm盡管支持向量機(jī)追求的目標(biāo)是較強(qiáng)的泛化能力,但相對于具體的樣本集,也可能出現(xiàn)過學(xué)習(xí)的問題.如兩類樣本集混疊較嚴(yán)重時,SVM的決策面可能由于過分復(fù)雜反而降低了其泛化能力.文獻(xiàn)提出了一種ESVM(EditingSupportingVectorMachines),其基本做法是:首先用SVM對訓(xùn)練集學(xué)習(xí)得到?jīng)Q策邊界,去掉決策邊界附近一定區(qū)域內(nèi)的樣本以及錯分的樣本,然后再對新訓(xùn)練樣本集重新用SVM學(xué)習(xí)得到新的決策邊界.在必要的情況下,對最初的訓(xùn)練樣本集用新決策邊界編輯,去掉錯分的樣本,得到另一個新的訓(xùn)練集,再對它訓(xùn)練得到更新的決策邊界.文獻(xiàn)的做法較為復(fù)雜,需要反復(fù)使用SVM訓(xùn)練.本文提出了另一種改進(jìn)的SVM——NN-SVM:它先對訓(xùn)練集進(jìn)行修剪,根據(jù)每個樣本與其最近鄰(nearestneighbor)類標(biāo)的異同決定其取舍,然后再用SVM訓(xùn)練得到分類器.相比文獻(xiàn)的做法,我們的做法非常簡捷,且實(shí)驗(yàn)表明,與SVM相比,NN-SVM不單在分類正確率上有了較大提高,而且分類速度更快,并能適用更大規(guī)模的訓(xùn)練樣本集.我們采取下面的策略對訓(xùn)練集進(jìn)行修剪:首先找出每一個點(diǎn)的最近鄰,然后對每一個點(diǎn),如果該點(diǎn)與其最近鄰屬于同類,則保留此點(diǎn);如果該點(diǎn)與其最近鄰屬于異類,將該點(diǎn)刪除.采用歐氏距離作為兩個向量之間的距離,即設(shè)xi=(x1i,x2i,?,xni)?xj=(x1j,x2j,?,xnj),則xi與xj之間的距離定義為D(xi,xj)=√n∑k=1(xki-xkj)2,一個樣本的最近鄰就是在上述定義下與其距離最近的樣本.下面我們給出上述方法的實(shí)現(xiàn)算法.給定一個訓(xùn)練集(x1,y1),(x2,y2),…,(xm,ym),xi∈Rn,yi∈{1,-1},i=1,2,…,m.將訓(xùn)練集表示為矩陣ΤRm×(n+1)=(XY)?其中X=(x1?xm)?Y=(y1?ym).修剪算法如下:1.找到每個向量的下一個相鄰(1)zij,i,n,nforp=1tom{Z1×m=(zij),zij=∞,i=1,j=1,2,…,m;forq=1tom{ifq≠p,z1q=D(xp,xq);}}(2)類型1,2,1NNm×1=(nnij),nnij=1,i=1,2,…,m,j=1t=1;value=z11;forq=1tom{ifz1q<value{value=z1q;t=q;}nnp1=t;}2.每個向量的類標(biāo)是否與下一個相鄰區(qū)域一致，并標(biāo)記為1和11=lij、lij=1、i.1、2、m和j=1forp=1tom{ifyp≠ynnp,lp1=-1;}3.新矩陣及tr、lforp=1tom{ifl(p-i)1=-1{刪除矩陣TR及L的第p-i行,新矩陣仍設(shè)為TR及L;i=i+1;}}經(jīng)過上述3步后就可得到修剪后的訓(xùn)練集TR.我們把上述先利用最近鄰(nearestneighbor)對訓(xùn)練集進(jìn)行修剪,然后再用SVM訓(xùn)練得到分類器的方法稱為NN-SVM.相對于SVM,NN-SVM有以下優(yōu)點(diǎn):(1)基于nn-svm的分類邊界由于修剪了訓(xùn)練集,NN-SVM的分類邊界相比SVM的過于復(fù)雜的分類邊界有所簡化(見圖1),因而其泛化能力可能更強(qiáng),分類正確率可能更高.第4節(jié)的實(shí)驗(yàn)結(jié)果證實(shí)了這種想法.可見NN-SVM是解決由于兩類混疊嚴(yán)重而造成分類器過學(xué)習(xí)和泛化能力減弱問題的有效途徑.(2)使用時間短訓(xùn)練集經(jīng)過修剪后,分類器的支持向量大大減少,而分類所用時間與支持向量的個數(shù)是成正比的(見式(5)),因此大大節(jié)省了分類時間.(3)更大的訓(xùn)練集由于修剪過程使較大的訓(xùn)練集變小,因此在同樣的硬件條件下,NN-SVM可適用于更大的訓(xùn)練集.當(dāng)然,我們應(yīng)該指出,上述優(yōu)點(diǎn)的獲得也是付出了一定的代價(jià)的:那就是修剪過程需要額外的時間,但是這一點(diǎn)代價(jià)與上述任何一種收益相比都是微不足道的.因?yàn)楦叩恼_率、更快的分類速度以及訓(xùn)練更大的樣本集是我們追求的首要目標(biāo).4結(jié)果(1)vib系統(tǒng)加大因子t值集我們在PC機(jī)(奔騰1.4G,256M內(nèi)存)上,利用http://svm.first.gmd.de/提供的MatlabSVM軟件工具包以及我們所編制的數(shù)據(jù)修剪程序進(jìn)行實(shí)驗(yàn).所采用的測試數(shù)據(jù)如下:數(shù)據(jù)1,ringnorm,該數(shù)據(jù)集是LeoBreiman生成的用于兩類劃分的樣本集,每一類都是取自一個20維的多變量正態(tài)分布.類1的均值為0,方差為單位元的四倍;類2的均值為(a,a,…,a),方差為單位元,其中a=2/sqrt(20).在實(shí)驗(yàn)中通過截取某k維得到相應(yīng)k維正態(tài)分布的樣本集.數(shù)據(jù)2,letter,此數(shù)據(jù)集是26個大寫字母打印體的16維特征向量集.在實(shí)驗(yàn)中把某一個字母作為一類,其它的25個字母作為另一類.數(shù)據(jù)3,SVM工具包自帶的數(shù)據(jù)集iris,它是三種植物的4維特征向量集.以上數(shù)據(jù)都可以從網(wǎng)站http://svm.first.gmd.de/上得到.(2)測試集的檢驗(yàn)及檢驗(yàn)實(shí)驗(yàn)中,核函數(shù)使用高斯核,其中σ=0.5,懲罰參數(shù)C=100.我們重點(diǎn)對正態(tài)分布樣本集進(jìn)行了訓(xùn)練,實(shí)驗(yàn)結(jié)果如圖2～圖5.這些圖都是相對于數(shù)據(jù)集1實(shí)驗(yàn)的結(jié)果,數(shù)據(jù)集1為7400個20維向量的集合,每個向量還附帶一個類標(biāo).我們通常截取20維向量的前K個分量構(gòu)成K維向量,取前N個樣本作為訓(xùn)練集(圖中橫坐標(biāo)對應(yīng)K或N的具體取值),后3400個樣本作為測試集.由于數(shù)據(jù)集1本身是隨機(jī)排列的,向量的各分量之間也是獨(dú)立的,因此這樣選取是合理的,并且我們嘗試了不同的選取方法,實(shí)驗(yàn)結(jié)果類似.圖2表明,NN-SVM分類正確率有了明顯的提高.圖3表明,NN-SVM的支持向量數(shù)大大減少了,從而分類時間也大大減少了(圖4).圖5所示修剪后樣本集有較大程度的減小,表明在樣本集太大(受硬件條件限制)無法直接進(jìn)行訓(xùn)練的情況下,我們有可能通過修剪樣本集使訓(xùn)練能夠進(jìn)行.對其它數(shù)據(jù)實(shí)驗(yàn),得到了類似的結(jié)果.下面指出需要注意的幾個問題:(1)NN-SVM特別適用于混疊較為嚴(yán)重的數(shù)據(jù)集,即兩類的交叉區(qū)域較大不易劃分的情形.對于混疊很輕、容易劃分的情形,NN-SVM雖然仍具備上述優(yōu)點(diǎn),但優(yōu)勢不明顯.(2)我們知道,當(dāng)樣本集足夠多的時候,分類器的正確率將逼近一個極限,這時候SVM與NN-SVM的分類正確率將同時達(dá)到極限,因此這時再比較孰優(yōu)孰劣顯然已沒有意義.而在樣本集嚴(yán)重不足的情況下,顯然保留現(xiàn)有的樣本集更為明智,因此這時候再對樣本集進(jìn)行修剪顯然不合時宜,在這種情況下,沒有必要使用NN-SVM.也就是說,當(dāng)樣本集的規(guī)模處于某一范圍之內(nèi)(既不是充分多也不是特別少)時,NN-SVM會表現(xiàn)出較為明顯的優(yōu)勢.5關(guān)于其他需要研究的問題本文給出了一種改進(jìn)的支持向量機(jī)——NN-SVM:它首先對訓(xùn)練集進(jìn)行修剪,根據(jù)每個樣本與其最近鄰類標(biāo)的異同決定其