一種提高SVM分類速度的新方法

任逸卿，朱昌杰，吳 波

(淮北師范大學 計算機科學與技術(shù)學院，安徽 淮北 235000)

支持向量機(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解決小樣本、非線性及高維模式識別中表現(xiàn)出許多優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機器學習問題中[1].它的分類方法是建立在統(tǒng)計學習理論的VC維理論和結(jié)構(gòu)風險最小化原理基礎(chǔ)上的.

本文提出一種改進的SVM分類器.改進分類器的主要功能是通過引入分類圓心，分類半徑，分類圓心距的概念，從而快速地對非支持向量點進行刪除，提高分類速度.引入混消度的概念，保證在訓練樣本嚴重混淆時的算法泛化性[2].

1 現(xiàn)有的一些SVM改進算法

SVM具有很強的泛化能力.但是實際問題中，兩類訓練樣本時?；煜龂乐?這種情況下，SVM分類面就非常復雜，分類效率低下.現(xiàn)有的解決這個問題的辦法有使用NN-SVM-KNN[3]分類器以及使用SVMKNN[4]等.SVM對于數(shù)據(jù)量很大的樣本的訓練效率都很低，針對大規(guī)模樣本的分類辦法有Light-SVM，最遠鄰等.但是這些方法分類精度都有所下降，而且效率不高[5]，刪減后依然有大量數(shù)據(jù).

2 改進算法

解決樣本混淆嚴重的分類問題時，算法需要既能快速地對樣本中非支持向量的混淆點進行刪減，又能保證訓練的結(jié)果泛化能力.然而在支持向量機中，不會出現(xiàn)在兩個樣本集間隔以外的正確劃分區(qū).我們就引入下面幾個概念:

一個類 S=｛t1，t2，t3，…，tn｝包含有 N個點，其中 t是 S中的一個樣本，這里每個樣本都是 m維向量.

分類圓心距:S=|C1-C2|，表示兩個分類圓心之間的距離.

混淆度:計算每個樣本 ti與它距離最近的 L個樣本的幾何距離.設(shè)這 L個樣本 ti的距離分別為 D1，D2，…， DL.分下面幾種情況:

這個概念表示了一樣本點周圍點的混淆程度.

分類方法:假設(shè)一個訓練集為兩類，一類為正，一類為負，分別用+和-表示，算法步驟如下:

(1)計算兩類樣本的分類圓心 C+，C-;分類半徑 R+，R-;分類圓心距 L.

(2)分情況比較:

正類中，若 R+＞L，則刪去對應(yīng)分類圓心 C+大于 R+的+類樣本.

若 R+＜L，則刪去對應(yīng)分類圓心 C+大于 L的+類樣本.

負類中，若 R-＞L，則刪去對應(yīng)分類圓心 C-小于 R-的-類樣本.

若 R-＜L，則刪去對應(yīng)分類圓心 C-小于 L的-類樣本.

(3)經(jīng)過上面修剪剩下的樣本成為支持向量的概率就很高.對這些剩下的每個樣本 ti計算混淆度 Ei，進行進一步的刪減提高泛化性.這里我們給每個樣本的混淆度設(shè)定一個因子 ε(ε＞0)

當 Ei＞ε，混淆程度在接受范圍，保留樣本點;

當 Ei＜ε，混淆嚴重，刪除樣本該樣本點.

經(jīng)過兩次修剪以后，使用支持向量機對剩下的樣本進行分類.

由此可見，前兩步是進行選取出那些可能成為支持向量的樣本，算法復雜度為 O(n)(n為樣本數(shù)量)，最遠鄰算法的復雜度為 O(n2)，分類效率已經(jīng)有很大提高.NN-SVM-KNN分類器和SVM-KNN分類器處理混淆樣本問題的時，對周圍樣本進行數(shù)量上的考察，第三步在此基礎(chǔ)上增加了對距離的考察，算法復雜度依然是 O(n2)，本步效率沒有提高，但是三步綜合來看分類速度明顯提高，滿足了設(shè)計之初的要求.

3 實驗結(jié)果及分析

在PC機上(I7，Q720處理器，4G內(nèi)存)上，利用已有的LIBSVM軟件工具包(軟件包是采用SMO快速算法實現(xiàn)SVM)以及http:∥ir.hitede.cn/上的兩組數(shù)據(jù)進行刪減實驗.具體如下:

(1)鳶尾屬植物樣本實驗.鳶尾屬植物數(shù)據(jù)集的樣本，共有150個樣本分為3類，分別是:S類，Ve類，Vi類.每類有50個樣本，每類都有4個屬性是4維向量.這個樣本各類別之間樣本混淆不嚴重.

用修剪程序?qū)?shù)據(jù)集進行測試，實驗結(jié)果如下(其中取 ε=0，L=5):

表1 對鳶尾屬樣本計算結(jié)果

表2 對鳶尾屬樣本修剪結(jié)果

由上面數(shù)據(jù)可以看出，步驟(1)(2)刪除的樣本占總數(shù)的42%，效果很好，而且算法復雜度由 O(n2)下降到O(n).

(2)鮑魚樣本實驗.數(shù)據(jù)集也是包含3類，分別用M，F(xiàn)，I標示進行區(qū)分，每類都是8維的向量，共有M類樣本1 530個，F(xiàn)樣本1 310個，I樣本1 340個，總數(shù)4 180個.取其中M，F(xiàn)類進行實驗.鮑魚樣本的特點是各樣本之間混淆嚴重.

對鮑魚樣本中的兩類進行測試，結(jié)果如下:

表3 對鮑魚樣本計算結(jié)果

表4 對鮑魚樣本修剪結(jié)果

表5 算法步驟(3)固定 ε=3改變 L的值結(jié)果

表6 算法步驟(3)固定 L=5改變 ε的值結(jié)果

由上面數(shù)據(jù)看出，經(jīng)過步驟(1)(2)刪除的樣本數(shù)占總樣本數(shù)的近一半，效果很好，而且算法復雜度由最遠鄰法的 O(n2)下降到 O(n).

經(jīng)過步驟(3)刪除的樣本占到(1)(2)之后剩余樣本的40%左右，說明算法對于混淆嚴重的樣本分類效果很明顯.而 ε和 L兩個參數(shù)的取值對于混淆度的影響如下:

1)隨著 ε值的增大，可以刪除的混淆點越來越少，ε是由我們?nèi)藶樵O(shè)定的混淆因素，ε值取值越大說明我們對每個樣本數(shù)據(jù)的重視程度越高，不會輕易地刪除樣本數(shù)據(jù).

2)L值增大以后，剛開始時混淆點的刪除率是增大的，L值達到5以后，混淆點的刪除率開始基本維持不變.

4 結(jié)語

本文提出一種改進的新支持向量機分類方法，使得對于不同的數(shù)據(jù)集分類算法的效率有不同程度的提高，同時可以根據(jù)數(shù)據(jù)需要改變參數(shù)選擇混淆點刪除程度，有一定靈活性.進一步的工作是從SVM分類機理出發(fā)，在提高分類速度的同時提高分類正確率.

[1]VAPNIK V.An overview of statistical learning theory[J].Ieee Trans，1999，2(6):57-58.

[2]VAPNIK V，LEVIN E.Measuring the VC dimension of a learning machine[M].Neural Computation，1994:851-876.

[3]鄧乃揚.數(shù)據(jù)挖掘中的新方法:支持向量機[M].北京:科學出版社，2004.

[4]鄭春穎.一種改進SVM算法[J].航空計算技術(shù)，2005，35(2):6-8.

[5]李蓉，葉世偉，史忠植.SVM-KNN分類器——一種提高SVM精度的新方法[J].電子學報，2002(5):745-748.