一種改進(jìn)的局部支持向量機(jī)算法＊

朱瑩瑩，尹傳環(huán)，牟少敏

（1.北京交通大學(xué)計算機(jī)與信息技術(shù)學(xué)院，北京 100044；2.山東農(nóng)業(yè)大學(xué)信息科學(xué)與工程學(xué)院，山東 泰安 271018）

1 引言

20世紀(jì)90年代中期，由Vapnik教授根據(jù)統(tǒng)計學(xué)習(xí)理論提出的支持向量機(jī)SVM（Support Vector Machine）思想，可用于模式分類和回歸估計[1～4]。由于支持向量機(jī)與傳統(tǒng)的模式分類、機(jī)器學(xué)習(xí)的方法如人工神經(jīng)網(wǎng)絡(luò)等相比有其顯著優(yōu)越性，如泛化能力強(qiáng)、全局優(yōu)化等，因此獲得了越來越廣泛的應(yīng)用。

從本質(zhì)上來說，支持向量機(jī)是一種二類分類器，能夠求解各種二類分類問題。假設(shè)給定一個獨(dú)立同分布的樣本集X：

根據(jù)結(jié)構(gòu)化風(fēng)險最小化原則，在訓(xùn)練集中構(gòu)造目標(biāo)函數(shù)[5]：

其中，w 是垂直于超平面的向量，φ（xi）相當(dāng)于把xi映射到特征空間中的向量，ξi 是松弛變量（松弛因子），用來懲罰那些不能被正確分開的樣本點(diǎn)；C 是懲罰項常數(shù)，用來權(quán)衡懲罰力度，C 越大，錯誤分類的懲罰越重；b是常數(shù)項。最后，利用決策函數(shù)：

由于二類分類的一致性問題[6]，基于減少參與分類的樣本數(shù)目，以提高分類速度為目的的局部支持向量機(jī)一經(jīng)提出就倍受關(guān)注。除了理論研究之外，局部支持向量機(jī)在實際應(yīng)用方面也得到了廣泛研究，如遙感圖像分類[7]、網(wǎng)絡(luò)流量預(yù)測[8]、腦電圖信號處理[9]等領(lǐng)域。

2 局部支持向量機(jī)及加權(quán)支持向量機(jī)

2.1 局部支持向量機(jī)的思想

局部支持向量機(jī)的思路最早是由Brailovsky等人[10]提出的，他們將兩個乘子添加在核函數(shù)中，使之具有局部性。定義如下：

重新定義一個新的核函數(shù)：

且令：

并且可通過設(shè)定θr的取值定義一個局部核函數(shù)：

2.2 Falk-SVM 算法

傳統(tǒng)的一些局部支持向量機(jī)，例如SVMKNN、KNNSVM 和LSVM 等，都需要為每一個樣本構(gòu)造模型，雖然局部支持向量機(jī)減少了參與建模的樣本數(shù)量，但在測試樣本數(shù)量比較多的情況下，局部支持向量機(jī)的時間復(fù)雜度還是相當(dāng)高的，因為需要構(gòu)造的模型個數(shù)增長更多。因此，如何提高測試效率是近年來局部支持向量機(jī)研究的一個主要內(nèi)容。

在局部支持向量機(jī)中，最直觀的改進(jìn)思路就是減少需要訓(xùn)練的支持向量機(jī)模型的個數(shù)，具體的改進(jìn)方法如算法1所示。

算法1 局部支持向量機(jī)改進(jìn)算法

步驟1 將訓(xùn)練集中的樣本依據(jù)某種原則劃分為k類，并找到k個中心；

步驟2 為每個中心構(gòu)造一個支持向量機(jī)；

但是，Segata和Blanzieri認(rèn)識到這種改進(jìn)仍存在一些問題[11，12]，于是他們在kNNSVM 的基礎(chǔ)上提出了Falk-SVM （FAst Local Kernel Support Vector Machine）算法，該算法的基本思路與算法1相似，區(qū)別在于選取中心點(diǎn)的過程。

Falk-SVM 在訓(xùn)練集上采用類似于求最小覆蓋集[13]的方法來獲得覆蓋所有訓(xùn)練集的中心。定義一個集合A 的最小距離d（A）和最大距離D（A）：

因此，對于訓(xùn)練集X 來說，最小距離和最大距離分別為d（Χ）和D（Χ）。

首先構(gòu)造一系列X 的子集Si，使得Si?Χ，并且滿足：

在構(gòu)造Si時可以更具體地引入一個大于1的數(shù)值b，使得d（Si）＞bi。稱Si中的最小索引i為bot，最大的索引i為top。通過遞歸得到：

其中，choose（A）表示從非空集合A 中選擇一個元素的函數(shù)。這個函數(shù)可以根據(jù)情況有不同定義，即選擇元素的方法不同，例如，可以簡單地將choose（A）定義為取得A 中下標(biāo)最小的元素等，在這里就是這么定義的。該遞歸的真正含義可表示為：Si不僅需要包含Si＋1中所有的元素，還應(yīng)該盡可能多地包含那些不在Si＋1中并且距離Si＋1足夠遠(yuǎn)的樣本，這樣通過式（8）構(gòu)造出來的一系列Si就可以滿足式（7）的要求。

接著從一系列Si中選取中心，使得這些中心的k′-近鄰能夠覆蓋所有的訓(xùn)練樣本。選取中心也是通過一個遞歸公式實現(xiàn)的：

值得注意的是：選取中心時，是所有中心的k′-近鄰能夠覆蓋所有訓(xùn)練樣本，而不是它們的k-近鄰覆蓋所有樣本，而基于某中心構(gòu)造支持向量機(jī)時，是將該中心的k-近鄰選做訓(xùn)練集，k′≤k，因此有一部分訓(xùn)練樣本將被重復(fù)使用。實際上Segata和Blanzieri在他們的工作中設(shè)置k′＝k／2，這是在實驗中通過參數(shù)調(diào)優(yōu)得到的一個經(jīng)驗值。

2.3 加權(quán)支持向量機(jī)

范昕煒等[14]首先提出了對每一類樣本賦予不同權(quán)值的加權(quán)支持向量機(jī) WSVM（Weighted SVM）模型，對類別差異造成的影響進(jìn)行了相應(yīng)的補(bǔ)償，從而提高了小類別樣本的分類精度。其優(yōu)化問題描述為：

其中，υ是v-SVM 中的系數(shù)，用于對每一類的支持向量數(shù)界限分別進(jìn)行調(diào)整；ρ是常數(shù)設(shè)置。

采用拉格朗日乘子法求解式（9）優(yōu)化問題，即：

其中αi、βi 和δ 都是拉格朗日乘子，并且αi≥0，βi≥0和δ≥0。通過微分計算得到對偶表達(dá)式為：

其中，si是為每一個樣本增加的一個系數(shù)作為權(quán)值，它可以是0和1之間的常數(shù)，也可以是函數(shù)，例如，隨樣本到達(dá)時間變化的函數(shù)。

如果某一種樣本是非常重要的或者某些被噪聲污染的樣本點(diǎn)要舍去，都可通過對每個樣本賦予不同的權(quán)值來解決這些問題。例如，對于要舍去的樣本點(diǎn)，可將其權(quán)值賦值為近似零的數(shù)，而將重要的樣本點(diǎn)的權(quán)值賦值為1或者近似為1的數(shù)，這樣就可以克服廣義SVM 算法在權(quán)重方面的缺陷。

3 Weighted Falk-SVM 算法

盡管上述提到的Falk-SVM 取得了比較好的分類精度，但依然存在幾個問題：

（1）在構(gòu)造的每個支持向量機(jī)模型中，存在正負(fù)樣本不均衡的情況，此時，單個模型的分類精度并不理想，盡管在總的分類精度上影響不大。因此，通過某種技術(shù)提高單個支持向量機(jī)的分類精度以進(jìn)一步提高總的分類精度是十分必要的。

（2）對于大規(guī)模數(shù)據(jù)集而言，這樣的k-近鄰數(shù)據(jù)量依然比較龐大，將會導(dǎo)致單個支持向量機(jī)模型的訓(xùn)練速度較低，從而大大增加訓(xùn)練多個支持向量機(jī)的時間復(fù)雜度。因此，大量減少需要構(gòu)造的支持向量機(jī)的數(shù)量來降低整個局部支持向量機(jī)的時間復(fù)雜度是非常必要的。

針對Falk-SVM 中存在的問題，在加權(quán)支持向量機(jī)的啟發(fā)下，本文提出將加權(quán)思想應(yīng)用在Falk-SVM 之上的加權(quán)局部支持向量機(jī)算法WFalk-SVM（Weighted Falk-SVM）。這樣，就可以克服局部支持向量機(jī)中單個模型正負(fù)樣本不均衡的問題，提高單個支持向量機(jī)模型的分類精度。

WFalk-SVM 的算法步驟和Falk-SVM 相似，區(qū)別在于對每個樣本都添加了一個權(quán)重值。具體的WFalk-SVM 算法步驟可描述為：

（1）通過Falk-SVM 中選取中心點(diǎn)的方法選取k個中心點(diǎn)；

（2）按照加權(quán)支持向量機(jī)的思想為每一個中心點(diǎn)進(jìn)行加權(quán)；

（3）按照Falk-SVM 中建模的方法為每一個中心點(diǎn)建模；

（4）采用Falk-SVM 中的方法為每一個測試樣本選取模型進(jìn)行測試。

考慮到加權(quán)思想的目的和數(shù)據(jù)集中正負(fù)樣本的數(shù)目，上述算法采用的權(quán)重值以正負(fù)樣本數(shù)目的比例為基礎(chǔ)，通過其各種變形尋找最佳權(quán)值。當(dāng)然，對于不同的數(shù)據(jù)集獲得的最佳權(quán)值是不同的，如兩者比例的冪次方、多項式形式等。

4 實驗

實驗將算法WFalk-SVM與Falk-SVM 應(yīng)用于同樣的數(shù)據(jù)集，觀察分析結(jié)果。此次實驗的數(shù)據(jù)集ijcnn1、splice、a9a、svmguide3、cov-type都來自LibSVM 數(shù)據(jù)庫，如表1描述。

Table 1 Data sets used in experiment表1 實驗中用到的數(shù)據(jù)集

表2中描述的是五個數(shù)據(jù)集的實驗結(jié)果，其中，F(xiàn)alk-SVM 和WFalk-SVM 分別表示各自算法的分類精度。通過表2可以看出，對于不同的數(shù)據(jù)集，加權(quán)方式對其產(chǎn)生的影響是不同的，對于一些數(shù)據(jù)集有很大提高。例如，對于splice 提高了17%，對于svmguide3，加權(quán)方法甚至使分類精度提高了將近25%，而對于另外一些數(shù)據(jù)集則沒有顯著效果，例如，ijcnn1和cov-type準(zhǔn)確度分別只提高了2.6%和5.2%。

Table 2 Experiment results of Falk-SVM and WFalk-SVM表2 將數(shù)據(jù)集分別應(yīng)用于Falk-SVM 和WFalk-SVM 的實驗結(jié)果

表3是以svmguide3為例，針對每個模型進(jìn)行的使用加權(quán)和不使用加權(quán)的對比實驗。通過表3可知，在每個模型中正負(fù)樣本比例較大的時候，正如我們預(yù)期的那樣，WFalk-SVM 的分類精度要比Falk-SVM 的高很多。通過分析數(shù)據(jù)集合的不同，我們發(fā)現(xiàn)svmguide3中測試樣本中全為同一類樣本（正類樣本），訓(xùn)練集中負(fù)類樣本遠(yuǎn)遠(yuǎn)多于正類樣本，此時正類樣本比較重要，權(quán)值應(yīng)當(dāng)大一些，對于這樣的數(shù)據(jù)集采用加權(quán)的方法可以使準(zhǔn)確度提高。例如，在svmguide3和cov-type中，當(dāng)樣本比例為1∶3或者1∶4左右時，模型分類精度都有顯著提高，coy-type結(jié)果如表4 所示。對于ijcnn1而言，正負(fù)樣本比例相差非常大（近似10∶1），而每個模型中正負(fù)樣本比例很多沒有達(dá)到這么高的比例差，因此分類效果并沒有顯著的改變，這也正是使用加權(quán)思想的目的所在。

Table 3 Different classification models of Falk-SVM and WFalk-SVM in svmguide3表3 svmguide3中Falk-SVM 和WFalk-SVM分類效果不同的模型

Table 4 Different classification models of Falk-SVM and WFalk-SVM in cov-type表4 cov-type中Falk-SVM 和WFalk-SVM分類效果不同的模型

但是，在splice中，當(dāng)模型中樣本比例接近于1的時候，WFalk-SVM 的分類效果同樣比Falk-SVM 的好。并且盡管a9a與svmguide3這兩個數(shù)據(jù)集總體上的正負(fù)樣本比例相同，單個模型中樣本比例也相似，但是a9a 的實驗結(jié)果并不如svmguide3的結(jié)果那樣令人滿意。這也是需要我們進(jìn)一步研究的內(nèi)容。實驗進(jìn)一步說明了加權(quán)思想在處理數(shù)據(jù)類型不均衡或者某一類樣本比較重要時的作用，也證實了我們提出將加權(quán)思想應(yīng)用于局部支持向量機(jī)，即WFalk-SVM 對改善模型中樣本不均衡的數(shù)據(jù)集分類效果的可行性和有效性，但對于不適合于所有數(shù)據(jù)集的問題有待我們進(jìn)一步討論研究。

5 結(jié)束語

在眾多局部支持向量機(jī)中存在諸如時間復(fù)雜度過高、分類精度不夠滿意等缺點(diǎn)，基于局部支持向量機(jī)算法kNNBSVM 提出的Falk-SVM 從理論和實驗中都驗證了Falk-SVM 的快速性和準(zhǔn)確性。實際上，該算法是目前為止見諸報端的各種局部支持向量機(jī)中，訓(xùn)練和測試速度以及分類精度最好的一種局部支持向量機(jī)。

即便這樣，對于類別數(shù)目比例差異較大或者樣本集中存在重要性差異較大的樣本類別的數(shù)據(jù)集，僅僅使用Falk-SVM 的分類精度并不理想，在加權(quán)支持向量機(jī)的啟發(fā)下提出的將加權(quán)思想應(yīng)用于Falk-SVM 的思路可以對類別差異造成的影響進(jìn)行相應(yīng)的補(bǔ)償，從而可以提高小類別樣本的分類精度。今后的工作主要集中在對加權(quán)權(quán)值的判斷和選取上，以及其適用的數(shù)據(jù)集的研究上，以期對分類精度做進(jìn)一步的改進(jìn)。

[1]Burges C J C.A tutorial on support vector machines for pattern recognition[J].Data Mining and Knowledge Discovery，1998，2.2）：121-167.

[2]Scholkopf B，Smola A.Learning with kernels[M].Cambridge，MA：MIT Press，2001.

[3]Smola A，Sch?lkopf B.A tutorial on support vector regression[J].Statistics and Computing，2004，14（3）：199-222.

[4]Vapnik V.The nature of statistical learning theory[M].Berlin：Springer Verlag，2000.

[5]Vapnik V N.Statistical learning theory[M].New York：John Wiley and Sons，1998.

[6]Zakai A，Ritov Y.Consistency and localizability[J].Journal of Machine Learning Research，2009（10）：827-856.

[7]Blanzieri E，Melgani F.Nearest neighbor classification of remote sensing images with the maximal margin principle[J].IEEE Transactions on Geoscience and Remote Sensing，2008，46（6）：1804-1811.

[8]Meng Qing-fang，Chen Yue-hui，Peng Yu-hua.Small-time scale network traffic prediction based on a local support vector machine regression model[J].Chinese Physics B，2009，18（6）：2194-2199.

[9]Shen Min-fen，Chen Jia-liang，Lin Chun-hao.Modeling of nonlinear medical signal based on local support vector machine[C]∥Proc of International Instrumentation and Measurement Technology Conference，2009：675-679.

[10]Brailovsky V L，Barzilay O，Shahave R.On global，local，mixed and neighborhood kernels for support vector machines[J].Pattern Recognition Letters，1999，2.（11-13）：1183-1190.

[11]Segata N，Blanzieri E.Fast and scalable local kernel machines[J].Journal of Machine Learning Research，2010（11）：1883-1926.

[12]Segata N.Local approaches for fast，scalable and accurate learning with kernels[D].Trento：University of Trento，2009.

[13]Chen L.New analysis of the sphere covering problems and optimal polytope approximation of convex bodies[J].Journal of Approximation Theory，2005，133（1）：134-145.

[14]Fan Xin-wei，Du Shu-xin，Wu Tie-jun.Reimbursable class differences weighted support vector machine algorithm[J].Chinese Journal of Graphics，2008，8A（9）：1037-1042.（in Chinese）

附中文參考文獻(xiàn)：

[14]范晰煒，杜樹新，吳鐵軍.可補(bǔ)償類別差異的加權(quán)支持向量機(jī)算法[J].中國圖像圖形學(xué)報，2008，8A（9）：1037-104.