支持向量機算法的研究及其實現(xiàn)

范玉妹,郭春靜

(北京科技大學(xué)應(yīng)用科學(xué)學(xué)院,北京100083)

支持向量機 (support vector machine,SVM)是數(shù)據(jù)挖掘中的一項新技術(shù),是針對小樣本數(shù)據(jù)提出的,借助于最優(yōu)化方法解決機器學(xué)習(xí)問題的新工具。它最初于20世紀(jì)90年代由Vapnik提出,近年來在其理論和算法實現(xiàn)方面都取得了突破性進展,開始成為克服 “維數(shù)災(zāi)難”和 “過學(xué)習(xí)”等傳統(tǒng)困難的有力手段。雖然它還處于飛速發(fā)展的階段,但是它的理論基礎(chǔ)和實現(xiàn)途徑的基本框架已經(jīng)形成。它是建立在統(tǒng)計學(xué)習(xí)理論基礎(chǔ)之上,對統(tǒng)計學(xué)習(xí)理論的發(fā)展起到巨大的推動作用并被廣泛應(yīng)用。由于其出色的學(xué)習(xí)性能,該技術(shù)已成為機器學(xué)習(xí)界的研究熱點,并在很多領(lǐng)域都得到了成功的應(yīng)用,如人臉檢測、手寫體數(shù)字識別、文本自動分類等。支持向量機與其他的學(xué)習(xí)機相比,具有較好的泛化能力、非線性處理能力和高維處理能力。

1 支持向量分類機算法研究

1.1 C-SVM算法

標(biāo)準(zhǔn)的C-SVM(C-Support Vector Machines,簡稱C-SVM)算法是樣本點線性不可分情況下,引入松弛變量后的支持向量分類機算法。已知訓(xùn)練向量i=1,…,l屬于兩類,即 yi∈{1,-1},把訓(xùn)練數(shù)據(jù)正確分類是指求得的最優(yōu)分類超平面不但要把兩類數(shù)據(jù)正確分開,而且要使分類間隔最大,引進從輸入空間Rn到Hilbert空間H的變換。

把訓(xùn)練集 T={(x1,y1),…,(xl,yl)}映射為={(x1,y1),…,(xl,yl)}={(Φ(x1),y1),…,(Φ(xl),yl)}。由此得到的初始問題為

式中 C—懲罰參數(shù),C越大表示對錯誤分類的懲罰越大,它是算法中唯一可以調(diào)節(jié)的參數(shù);ζ—在訓(xùn)練集線性不可分時引進的松弛因子。

1.2 v-SVM算法

v-SVM(v-Support Vector Machines,簡稱 v-SVM),在2.1中討論的 C-SVM算法中,有兩個相互矛盾的目標(biāo):最大化間隔和最小化訓(xùn)練錯誤。其中常數(shù)C起著調(diào)和這兩個目標(biāo)的作用。定性地講,C值的含義即選取大的C值,意味著更強調(diào)最小化訓(xùn)練錯誤。但定量地講,C值本身并沒有確切的意義,所以 C值的選取比較困難。為此,Scholkoph提出了v-SVM模型。所謂v-SVM,即針對C-SVM算法中唯一可以調(diào)節(jié)的參數(shù)C沒有直觀解釋,在實際應(yīng)用中很難選擇合適的值,v-SVM中用參數(shù)v取代C。在一定條件下,當(dāng)樣本點個數(shù)l→∞時,v以1的概率漸近于支持向量個數(shù)與樣本點個數(shù)之比。v參數(shù)可以控制支持向量的數(shù)目和誤差,也易選擇。

引進從輸入空間到希爾伯特空間的變換,利用這個變換,由原來的訓(xùn)練集得到新的訓(xùn)練集

此訓(xùn)練集對應(yīng)的最優(yōu)化問題為

式中 ζ=(ζ1,…,這里不含參數(shù)C,而是換成了參數(shù)v這個需要實際選定的參數(shù)。模型中還多了一個變量 ρ,我們可以注意到當(dāng) ζ=0的時候,約束條件意味著兩類點以2ρ/‖w‖的間隔被分開。

1.3 One-classSVM算法

One-class SVM最初是用于高維分布估計,即用來尋找超平面VC維的估計值。對于沒有任何分類信息的訓(xùn)練向量∈Rn,i=1,…,l,初始最優(yōu)化問題為

1999年Tax提出用超球面代替超平面來劃分?jǐn)?shù)據(jù)的想法,改變了數(shù)據(jù)集的描述,目標(biāo)函數(shù)的初始最優(yōu)化問題變?yōu)?/p>

其中R為超球面的半徑,通過設(shè)定參數(shù)0≤v≤1,使超球面的半徑和它所能包含的訓(xùn)練樣本數(shù)目之間進行折衷。當(dāng)v小的時候,盡量把數(shù)據(jù)放進球里面,當(dāng)v大的時候,盡量壓縮球的尺寸,使用Lagrangian函數(shù)來解這個優(yōu)化問題。

2 支持向量回歸機算法的研究

2.1 ε-SVR 算法

ε-SVR采用了ε-不敏感損失函數(shù),所以它有一個明顯的優(yōu)點即具有稀疏性:所有在ε-帶內(nèi)部的樣本點都不是支持向量,它們對決策函數(shù)沒有貢獻。換句話說,去掉這些樣本點,不會影響最終的決策函數(shù),只有支持向量才會影響決策函數(shù)。

ε-SVR的原始問題如下:

2.2 v-SVR算法

在ε-SVR中,需要事先確定 ε-不敏感損失函數(shù)中的參數(shù)ε。然而在某些情況下選擇合適的ε并不是一件容易的事情。因此,與2.2中的分類算法類似,引進參數(shù)v取代ε,構(gòu)造能夠自動計算ε的一種變形算法—v-SVR。引進參數(shù)v后,則可將3.1中的最優(yōu)化問題修改為如下v-SVR問題:

3 仿真實例及結(jié)果分析

仿真實例是利用matlab軟件和Libsvm2.89版本來實現(xiàn)的,在實驗中所用到的核函數(shù)類型均為徑向基核函數(shù),分類實驗數(shù)據(jù)來源均為UCI學(xué)習(xí)庫,回歸實驗數(shù)據(jù)來源為公司實際數(shù)據(jù)。

3.1 分類實例及結(jié)果

本文采用一個大樣本與一個小樣本數(shù)據(jù)分別用三種不同的算法對其進行訓(xùn)練與預(yù)測。其中,大樣本數(shù)據(jù)集有 83個特征,訓(xùn)練集 train1包含1 605個數(shù)據(jù),測試集test1包含30 956個數(shù)據(jù);小樣本數(shù)據(jù)集只有兩個特征,訓(xùn)練集train2包含500個樣本點,測試集test2包含362個樣本點。

從表1我們可以看到采用C-SVC算法對數(shù)據(jù)train1和test1大樣本數(shù)據(jù)進行訓(xùn)練和測試時,參數(shù)對(C,γ)的變化對實驗結(jié)果的影響,最重要的結(jié)果是對訓(xùn)練集和測試集的分類正確率。正確率越大,說明分類準(zhǔn)確度越高,算法越適用于這個數(shù)據(jù)集。從表1可看出,此算法對train1和test1的分類正確率只能達到80%左右,相對比較低。此算法中,當(dāng)支持向量個數(shù)越多時,對訓(xùn)練集和測試集的分類正確率都越低,這個結(jié)果也是符合前面理論部分的,而且,我們看到對訓(xùn)練集的正確率越高,相應(yīng)的對測試集的測試正確率也越高,這說明我們做十折交叉驗證實驗得到最優(yōu)參數(shù)對,再選擇最優(yōu)參數(shù)對進行訓(xùn)練得到訓(xùn)練模型,最后用測試集進行測試是很有必要的。從表1整體來看,用C-SVC算法對train1數(shù)據(jù)集進行訓(xùn)練支持向量的個數(shù)很多,正確率不高,對測試集test1的分類正確率也不高,說明此算法對所選的大樣本數(shù)據(jù)是不太適用的。

表2反應(yīng)的是采用v-svm算法對數(shù)據(jù)train1和test1大樣本數(shù)據(jù)進行訓(xùn)練和測試時,參數(shù)對(v,γ)的變化對實驗結(jié)果的影響。其中,參數(shù)對的變化對訓(xùn)練集及測試集分類正確率的影響不太明顯,一般在80%左右波動。從表2還可看到,當(dāng)選擇參數(shù)不適當(dāng)時,得到的正確率是很低的,如當(dāng)v=0.01,γ=0.1時,對訓(xùn)練集及測試集的正確率分別只有57%和30%,這個結(jié)果是很差的。因此,根據(jù)特定的數(shù)據(jù)集選擇合適的參數(shù)對進行訓(xùn)練是很有必要的。用v-svm算法對train1數(shù)據(jù)集進行訓(xùn)練支持向量的個數(shù)較多,正確率不高,對測試集test1的分類正確率也不高,說明此算法對所選的大樣本數(shù)據(jù)是不太適用的。

表1 C-SVM算法對train1和test1的訓(xùn)練和測試結(jié)果Tab.1 The training and testing results for train1 and test1 with C-SVM algorithm

表2 v-SVM算法對train1和test1的訓(xùn)練和測試結(jié)果Tab.2 The training and testing results for train1 and test1 with v-SV M algorithm

從表3我們可以看到,此表中的結(jié)果與表1、表2的結(jié)果不太一樣,主要反應(yīng)在對訓(xùn)練集和測試集的分類正確率上。如當(dāng)γ都取0.1,v分別取0.01,0.1,0.9時,對訓(xùn)練集的分類正確率分別為55.977 6%、56.164 4%、72.602 7%,有較大的變化,但對測試集的分類正確率都為75.946 5%,沒有變化,這個結(jié)果跟其它兩個算法是不一樣的。當(dāng)γ都取0.01,v分別取0.01,0.1,0.9時,對訓(xùn)練集的分類正確率分別為26.525 5%、29.078 5%、71.731%,最低為26%,這個正確率是相當(dāng)?shù)偷?而對測試集的分類正確率確有75.365%變化不大。整體來看,此算法對train1和test1數(shù)據(jù)集訓(xùn)練和測試的正確率不高,最低有20%多,最高不到76%,比前面兩個算法的精度都差。說明此算法對這個數(shù)據(jù)集很不適用。另外,也反應(yīng)了參數(shù)選擇的重要性,如果參數(shù)選擇不當(dāng),則最后得到的結(jié)果尤其是正確率會特別不理想。

通過表1、表2與表3之間的對比,三個表反應(yīng)的是三種算法對大樣本數(shù)據(jù)集的訓(xùn)練和預(yù)測結(jié)果,參數(shù)的變化對結(jié)果都有不同程度的影響,說明我們在對具體的數(shù)據(jù)集進行訓(xùn)練和預(yù)測時選擇適當(dāng)?shù)膮?shù)的必要性。另外,通過比較發(fā)現(xiàn),采用C-svm與v-svm算法,正確率最高能達到83%左右,而采用 one-class svm算法正確率最高不到76%,說明對具體的數(shù)據(jù)集選擇適當(dāng)?shù)乃惴ǖ谋匾?也說明了改進的算法不一定適合于所有的數(shù)據(jù)集。從以上分析看,這三種算法的訓(xùn)練和測試正確率并不高,說明它們不太適用于大樣本數(shù)據(jù)集。表4采用C-svm算法對小樣本數(shù)據(jù)集進行訓(xùn)練和測試時,參數(shù)對(C,γ)的變化對實驗結(jié)果的影響。從正確率方面看,算法的結(jié)果比較理想,對訓(xùn)練集的正確率最高達到了99.6%接近100%,對測試集的正確率也達到了99%以上,此算法對這樣的小樣本數(shù)據(jù)的擴展性很好,但當(dāng)參數(shù)取得不合適時,如 γ=0.9,C=1時,正確率只有80%多,再一次說明了參數(shù)選擇的重要性。從表4來看,用C-SVM算法對訓(xùn)練集train2數(shù)據(jù)集進行訓(xùn)練支持向量的個數(shù)不多,能達到的最高正確率很高,對測試集test2能達到的分類正確率也很高,說明此算法對所選的小樣本數(shù)據(jù)是很適用的。

表3 one-class svm算法對train1和test1的訓(xùn)練與測試結(jié)果Tab.3 The training and testing results for train1 and test1 with one-class svm algorithm

表4 C-SVM算法對train2和test2的訓(xùn)練和測試結(jié)果Tab.4 The training and testing results for train2 and test2 with C-svm algorithm

表5反應(yīng)的是采用v-svm算法對數(shù)據(jù)集train2和test2小樣本數(shù)據(jù)進行訓(xùn)練和測試時,參數(shù)(v,γ)的變化對實驗結(jié)果的影響。從分類正確率上來看,參數(shù)的變化對結(jié)果有明顯的影響,對訓(xùn)練集和測試集的最高正確率都達到了99%以上,而最低分別為50%左右和47%左右。從表5同樣可看到,當(dāng)選擇參數(shù)不適當(dāng)時,得到的正確率是很低的,如當(dāng)v=0.05,γ=0.1時,對訓(xùn)練集及測試集的正確率分別只有38%和51%,這個結(jié)果是很差的。因此,根據(jù)特定的數(shù)據(jù)集選擇合適的參數(shù)對即進行模型選擇進行訓(xùn)練是很有必要的。從表5來看,用v-svm算法對train2數(shù)據(jù)集進行訓(xùn)練支持向量的個數(shù)不多,能達到的最高正確率很高,對測試集test2能達到的分類正確率也很高,說明此算法對所選的小樣本數(shù)據(jù)是比較適用的。

表6的結(jié)果與表4、表5的結(jié)果不太一樣。主要反應(yīng)在對訓(xùn)練集和測試集的分類正確率上。從表中結(jié)果我們看到,采用one-class svm算法對train2訓(xùn)練集的正確率最高只能達到67%左右,對test2測試集的正確率最高也只能達到60%左右,這樣的結(jié)果是很不理想的。從表5可以看到參數(shù)的變化并不能提高正確率,說明此算法對所選取的數(shù)據(jù)集是不適用的。

通過表4、表5與表6之間的對比,參數(shù)的變化對結(jié)果都有不同程度的影響,說明我們在對具體的數(shù)據(jù)集進行訓(xùn)練和預(yù)測時選擇適當(dāng)參數(shù)的必要性。另外,通過比較發(fā)現(xiàn),采用C-svm與vsvm算法,正確率最高能達到99%以上,而采用one-class svm算法正確率最高不到70%,說明對具體的數(shù)據(jù)集選擇適當(dāng)?shù)乃惴ǖ谋匾?也說明了改進的算法不一定適合于所有的數(shù)據(jù)集。C-svm與v-svm的訓(xùn)練和測試正確率都能達到理想的結(jié)果,說明它們適用于這樣的小樣本數(shù)據(jù)集。一般,在實際問題中要具體問題具體分析,盡量選擇合適的參數(shù)對,使得正確率盡量高,提高算法的精度。然而,我們可以看到,對C-svm算法而言,C的變化范圍很大,對具體實力來說是比較難選取合適的C值的,v-svm作為C-svm算法的改進算法,用參數(shù)v代替參數(shù)C,v的選取相對較容易且在算法迭代過程中,C值作為結(jié)果的一部分自動計算。用兩種算法對小樣本數(shù)據(jù)集的訓(xùn)練結(jié)果正確率都能達到理想的效果,精確度都很高。

表5 v-SVM算法對train2和test2的訓(xùn)練和測試結(jié)果Tab.5 The training and testing results for train2 and test2 with v-svm algorithm

表6 one-class svm算法對train2和test2的訓(xùn)練和測試結(jié)果Tab.6 The training and testing results for train2 and test2 with one-class svm algorithm

最后,比較同一種算法對不同的訓(xùn)練集和測試集的結(jié)果。通過表1與表4的結(jié)果我們不難發(fā)現(xiàn),采用C-svm算法不管對大樣本數(shù)據(jù)集train1、test1還是對小樣本數(shù)據(jù)train2、test2來說,選擇不同的參數(shù)對對實驗結(jié)果都有不同程度的影響,而從分類正確率的角度來看,對大樣本數(shù)據(jù)集的最高正確率達到83%左右,對小樣本數(shù)據(jù)的最高正確率能達到99%以上,接近100%,這充分說明了此算法較適用于小樣本數(shù)據(jù)。同樣,通過表2與表5的對比發(fā)現(xiàn)v-svm算法較適用于小樣本數(shù)據(jù)集,只是它在參數(shù)選擇上更容易一些。通過表3與表5的比較發(fā)現(xiàn),one-class svm算法對本文選取的大樣本與小樣本數(shù)據(jù)集的分類正確率都不理想,即它對一般的數(shù)據(jù)集并不適用,還不如最基本的C-svm與v-svm算法效果好。

3.2 回歸實例及結(jié)果

此部分本文選用公司實際數(shù)據(jù),數(shù)據(jù)集train3有3個特征,共有130個樣本點。

表7反應(yīng)的是采用 ε-SVR算法對數(shù)據(jù)集進行訓(xùn)練時,參數(shù)變化對實驗結(jié)果的影響。最重要的結(jié)果是均方誤差和平方相關(guān)系數(shù),其中均方誤差越小,說明回歸的準(zhǔn)確度也越高,即擬合曲線與實際的越接近,平方相關(guān)系數(shù)的大小是對變量與特征之間的相關(guān)程度的一種度量,其值越大即越接近1,表示變量與特征之間相關(guān)程度也越大。從表8的結(jié)果可以看到,γ一定C變化時,對均方誤差和平方相關(guān)系數(shù)沒有影響。均方誤差的值很小,都為0.004 054 63,說明此算法對train4的訓(xùn)練結(jié)果準(zhǔn)確度較高。平方相關(guān)系數(shù)的值都為0.976 418,比較接近1,說明變量與三個變量間的相關(guān)程度很高。當(dāng)均方誤差越小時,平方相關(guān)系數(shù)相對變大,這也是符合實際情況的,當(dāng)均方誤差越小時,說明算法回歸的準(zhǔn)確度越高,自然變量與特征之間的平方相關(guān)系數(shù)越大。

從表8的結(jié)果可以看出v一定γ變化時,對均方誤差的影響并不明顯,其值基本在0.001左右波動,但也有特殊情況,如 γ=0.01時,均方誤差達到了0.018,γ對平方相關(guān)系數(shù)的影響也不太明顯,其值都在0.9以上,但整體來說平方相關(guān)系數(shù)的值很接近1,說明變量與特征之間的相關(guān)程度很高。對均方誤差、平方相關(guān)系數(shù)結(jié)果無明顯影響。從以上分析可以看出,此算法對train4數(shù)據(jù)集的訓(xùn)練結(jié)果是比較穩(wěn)定的,無明顯偏差。

表7 ε-SVR算法對train4的訓(xùn)練結(jié)果Tab.7 The training results for train4 with ε-SVR algorithm

表8 v-SVR算法對train4的訓(xùn)練結(jié)果Tab.8 The training results for train4 with v-svr algorithm

從表7與表8的結(jié)果對比發(fā)現(xiàn),無論是ε-svr還是v-svr算法,選取不同的參數(shù)對對實驗結(jié)果都有不同程度的影響。因此,在實際問題中要具體問題具體分析,盡量選擇合適的參數(shù)對,使得均方誤差盡量小,提高算法的精確度。對ε-svr算法而言,C的變化范圍很大,對具體實例來說是比較難選取合適的C值的,作為ε-svr算法的改進算法,用參數(shù)v代替參數(shù)C,v的選取相對較容易且在算法迭代過程中,C值作為結(jié)果的一部分自動計算。用兩種算法對train4這個小樣本數(shù)據(jù)集的訓(xùn)練結(jié)果均方誤差都很小,精確度都很高,而且當(dāng)參數(shù)變化時,對均方誤差的大小無明顯影響,說明算法都比較穩(wěn)定。

用Matlab實現(xiàn)ε-SVR算法,對train4數(shù)據(jù)集做5折交叉驗證實驗的擬合結(jié)果如圖1所示。

4 結(jié)論

1)標(biāo)準(zhǔn)的支持向量機C-SVM是一個基礎(chǔ)算法,可以對所有的數(shù)據(jù)進行分類。但是,從正確率來看,比較適用于小樣本數(shù)據(jù)集。

2)v-SVM中支持向量的取值可以通過選擇合適的v來得到一個好的結(jié)果,但是對于大樣本問題還是需要核函數(shù)中參數(shù)的調(diào)節(jié)才能得到比較滿意的結(jié)果。

3)One-class SVM對一般數(shù)據(jù)集的分類正確率并不高,所以不適用于一般的數(shù)據(jù)集。

4)對于所選取的小樣本數(shù)據(jù)集,兩種回歸算法的結(jié)果都是比較理想的,即分類均方誤差較小,平方相關(guān)系數(shù)都接近1,且結(jié)果隨參數(shù)對的變化是不明顯的,算法比較穩(wěn)定。

5)不論分類算法還是回歸算法,參數(shù)的變化對實驗結(jié)果都有不同程度的影響。

[1] 鄧乃楊,田英杰.數(shù)據(jù)挖掘中的新方法-支持向量機[M] .北京:科學(xué)出版社,2004.

[2] 云潛,張學(xué)工.支持向量機函數(shù)擬合在分形插值中的應(yīng)用[J] .清華大學(xué)學(xué)報(自然科學(xué)版),2000,40(3):76-78.

[3] 劉華富.一種快速支持向量機分類算法[J] .長沙大學(xué)學(xué)報,2004,17(7):40-41.

[4] VAPNIK N.The nature of statistical learning theory[M] .New York:Springer-Verlag,1995.

[5] REYZIN L,SCHAPIRE R E.How boosting the margin can also boost classifier complexity[C] //ICML'06,the 23rd Int.Conf.,on MachineLearningPittsburgh,Pennsylvania,USA,2006:753-760.

[6] PLATT J.Fast training of support vector machines using sequential minimal optimization[C] //in Advances in Kernel Methods--Support Vector Learning,B.Schoelkopf,C.Burges,and A.Smola Eds.,1999:185-208.

[7] VAPNIK V.Statistical learning theory[M] .New York:John Wiley&Sons,1998.

[8] COTTES C,VAPNIK V N.Support vector networks[M] .Mach Learn,1995.

[9] YU H,YANG J,HAN J.Classifying large data sets using SVMswith hierarchical clusters[C] //in proc.of the ACM SIGKDD Int.Conf.on KDD,2003:306-315.