基于類中心的SVM訓(xùn)練樣本集縮減改進(jìn)策略

龐首顏,陳 松,魏建猛,張元勝

(1. 重慶交通大學(xué) 信息科學(xué)與工程學(xué)院，重慶 400074；2.重慶第二師范學(xué)院，重慶 400065)

0 引 言

SVM(支持向量機(jī))以其優(yōu)越的性能，在許多領(lǐng)域中得以實(shí)際應(yīng)用。但由于訓(xùn)練樣本集規(guī)模較大引發(fā)的學(xué)習(xí)速度慢、存儲需求量大、泛化能力降低等問題 ,成為直接使用該技術(shù)的瓶頸。究其原因，SVM在模式識別方面的應(yīng)用過程，歸根結(jié)底為一個線性的凸二次規(guī)劃優(yōu)化問題的求解過程(QP)[1]。對于n個訓(xùn)練數(shù)據(jù),n×n維核函數(shù)矩陣的計算和矩陣與向量相乘計算導(dǎo)致求解過程需要大量的時間開銷, 所以樣本數(shù)量越大，求解速度則越慢。如何提高訓(xùn)練速度和減少內(nèi)存開銷則成為研究 SVM 的一個新問題。

總結(jié)近年來研究人員在該優(yōu)化問題上使用的研究方法，主要有以下兩個方面：

1)在不改變訓(xùn)練集大小的前提下，把問題分解成為一系列易處理的子問題來解決，從而提高訓(xùn)練的速度。并按其迭代策略的不同分為Chunking算法[2]、Osuna 算法[3]、SMO 算法[4-5]等。其不足的地方是：這些算法需要通過反復(fù)迭代來尋找最優(yōu)解，當(dāng)訓(xùn)練樣本數(shù)量較大時，收斂速度可能會比較慢。

2)通過去除訓(xùn)練集中與支持向量無關(guān)的樣本來提高支持向量機(jī)的學(xué)習(xí)效率。基本思想是:從訓(xùn)練集中刪減對學(xué)習(xí)沒有幫助甚至有反作用的樣本,縮減訓(xùn)練樣本集,同時保證分類器的分類正確率不降低甚至有所提高, 從而減少訓(xùn)練的代價，提高訓(xùn)練速率。如焦李成，等[6]提出了支撐矢量預(yù)選取的中心距離比值法；汪西莉，等[7]提出了基于馬氏距離的支持向量快速提取算法；李青，等[8]提出了基于向量投影的支撐向量預(yù)選取方法；李紅蓮，等[9]提出了NN_SVM；郭亞琴，等[10]提出了BS_SVM；朱方，等[11]通過點(diǎn)集理論提出一種大規(guī)模訓(xùn)練樣本集縮減策略等。

筆者提出了一種改進(jìn)的縮減訓(xùn)練集的方法。首先根據(jù)各樣本點(diǎn)到樣本集中心的矢量距離，構(gòu)造超球；然后通過只提取超平面及距離超平面較近的樣本實(shí)現(xiàn)邊界樣本的提取，從而實(shí)現(xiàn)樣本集的縮減。

1 支持向量機(jī)

支持向量機(jī)可用于模式識別、回歸分析、主成分分析等。下面以模式分類為例來介紹支持向量機(jī)的含義。

定義1 (最優(yōu)分類超平面)如果訓(xùn)練樣本可以被無誤差地劃分，以及每一類數(shù)據(jù)中離超平面最近的向量與超平面之間的距離最大，則稱這個超平面為最優(yōu)分類超平面。

1.1 線性支持向量機(jī)

在求解兩類線性可分的問題時, SVM實(shí)質(zhì)就是通過在輸入空間求得一個分類超平面w·x+b=0, 使兩類樣本到該超平面之間的距離為最大(即找到其最優(yōu)超平面)，從而實(shí)現(xiàn)兩類樣本的最優(yōu)劃分。

設(shè)訓(xùn)練樣本為(x1,y1),(x2,y2),…,(xl,yl),xi∈Rn為描述樣本的n維特征向量，yi∈{+1,-1}代表xi所屬的類別。因?yàn)榭赡艽嬖谟袠颖静荒鼙怀矫嬲_分類, 所以引入松弛變量ξ，結(jié)合正則超平面min|ω·x+b|=1，求最優(yōu)超平面的問題則可歸結(jié)為以下優(yōu)化問題:

s.t.yi((xi·ω)+b)≥1-ξi，ξi≥0，

i=1,…,k。

(1)

此時,支持向量機(jī)可以看作是尋找一個分類超平面,該超平面通過設(shè)定一個懲罰因子C, 在最大間隔和最小錯分誤差兩者之間取一個折中；引入Lagrange 乘子α,β,將上述問題轉(zhuǎn)化為對偶形式。

(2)

根據(jù)Karush-Kuhn-Tucker定理，在鞍點(diǎn)有：

(3)

簡化后有：

αi[yi(xi·ω)+b-1]=0

(4)

由式(4)可知,對于大多數(shù)的樣本來說，其αi的值將為0；而αi取值不為0所對應(yīng)的樣本即為該優(yōu)化問題的支持向量sv,它們的數(shù)量通常只占全體樣本數(shù)量較少的比例。

最后根據(jù)支持向量和簡化式可求出b，則決策函數(shù)為(sv為支持向量)：

(5)

因此，在確定的空間中，可以得到定理1，它是SVM進(jìn)行樣本集縮減的主要理論依據(jù)[11]。

定理1 支持向量機(jī)的訓(xùn)練結(jié)果與非支持向量無關(guān)。

1.2 非線性支持向量機(jī)

在求解非線性分類問題時，SVM首先使用一個非線性映射Φ將輸入映射到線性可分的高維特征空間，然后通過在特征空間中求最優(yōu)超平面來實(shí)現(xiàn)問題的求解。因?yàn)樵谶M(jìn)行決策函數(shù)和優(yōu)化問題計算時都只需要進(jìn)行特征空間中的內(nèi)積運(yùn)算，由Mercer定理可知，可以通過選取一個滿足條件的核函數(shù)K(x,xi)，來替代特征空間中的內(nèi)積運(yùn)算Φ(x)·Φ(xi)，從而避免了顯式定義映射Φ的定義。即K(x,xi)=Φ(x)·Φ(xi)，則此時的優(yōu)化問題為：

(6)

則決策函數(shù)為：

(7)

通過引進(jìn)核函數(shù)，SVM巧妙地解決了在將低維空間向量映射到高維空間向量時帶來的“維數(shù)災(zāi)難”問題。

2 基于類中心的樣本集縮減策略

2.1 支持向量機(jī)幾何基礎(chǔ)知識

從文獻(xiàn)[12]的命題可知，假如映射到特征空間后的兩類樣本集是可分的，則最優(yōu)分類超平面位于兩類樣本集的類中心之間(圖1)，并且各類的支持向量(即圖中的帶圈部分)分布于類別中心和最優(yōu)超平面之間。從幾何上直觀地看，支持向量就是在線性可分的空間中兩類樣本的交遇區(qū)內(nèi)那些離最優(yōu)超平面最近的兩類邊界上的樣本[8]。

圖1 最優(yōu)超平面與類中心的關(guān)系Fig.1 Relationship between optimal hyperplane and class-center

筆者的研究主要根據(jù)支持向量本身的結(jié)構(gòu)特點(diǎn)，剔除對超平面構(gòu)造沒有實(shí)際意義的樣本點(diǎn)，保留處于邊界位置的樣本(這部分樣本最有可能成為支持向量)來參與超平面的構(gòu)建，進(jìn)而降低計算量并提高超平面構(gòu)建速度。具體設(shè)計思路如下：

1)如圖2，L1，L2分別為過正類、負(fù)類中心且平行于超平面H的一條直線，S+，S1+分別為過正類中心m+的一個圓，S-，S1-分別為過負(fù)類中心m-的一個圓，S′+，S′-分別為S+，S-彼此靠近的兩個半圓。首先利用文獻(xiàn)[13]中的基于類中心的邊緣方法找到位于L1，L2之間的樣本點(diǎn)，即S1′+，S1′-內(nèi)的點(diǎn)。

2)在1)基礎(chǔ)上通過樣本點(diǎn)到樣本中心點(diǎn)的距離來縮減支持向量的預(yù)選范圍，從而獲得邊界樣本信息。

3)以2)中得到的邊界樣本為訓(xùn)練樣本完成SVM訓(xùn)練。

4)利用3)訓(xùn)練得到的SVM對樣本點(diǎn)進(jìn)行分類。

圖2 最優(yōu)超平面與樣本點(diǎn)結(jié)構(gòu)的關(guān)系Fig.2 Relationship between optimal hyperplane and data structure

2.2 線性可分的支持向量預(yù)選取

2.2.1 文中用到的定義

定義1 某一類樣本的平均特征稱為該類樣本的中心m，已知樣本向量組{x1,x2,…,xl}，其中l(wèi)為其樣本個數(shù)，那么其中心為:

(8)

定義2 樣本距離是指兩個樣本之間的特征差異，已知兩個N維樣本向量x1,x2，則其樣本距離為:

(9)

2.2.2 基于類中心邊界向量預(yù)取算法

1)將原始訓(xùn)練樣本根據(jù)標(biāo)號的不同分成兩類S+,S-。l+為正類樣本的個數(shù),l-為負(fù)類樣本的個數(shù), 其中l(wèi)=l++l-。

2)分別計算正類樣本的類中心m+、負(fù)類樣本的類中心m-，各個樣本點(diǎn)到各自樣本中心點(diǎn)的距離d(xi,m±)；

4)由文獻(xiàn)[13]的去邊緣方法使得與支持向量相關(guān)的兩個半球內(nèi)的樣本點(diǎn)：

S′+={x|(m--m+)·(x-m+)≥0,x∈s+}

S′-={x|(m+-m-)·(x-m-)≥0,x∈s-}

(10)

5)通過公式：

(11)

來確定正類、負(fù)類樣本集中各自所對應(yīng)的邊界樣本。其中0 <λ1±,λ2±< 1，其具體的取值取決于樣本的分布情況?？紤]樣本點(diǎn)分布的結(jié)構(gòu)特點(diǎn)，文中λ1與各自均值距離與其半徑的比值相關(guān)。同時，為了進(jìn)一步減少孤立樣本點(diǎn)對訓(xùn)練結(jié)果的不良影響，引人了λ2，其取值與處于樣本邊緣且個數(shù)小于樣本總個數(shù)1/100的樣本相關(guān)。

2.3 非線性可分的支持向量預(yù)選取

由非線性支持向量機(jī)可知，在進(jìn)行非線性可分的問題求解時,首先通過某個非線性映射Φ將訓(xùn)練樣本從輸入空間映射到某一高維(甚至無窮維)的特征空間H，使其在特征空間中呈現(xiàn)線性(或近似線性)可分，然后再在特征空間中構(gòu)造最優(yōu)分類超平面。則映射到特征空間后任意兩點(diǎn)間的距離可由以下引理1求出。

引理1[4]已知兩個向量x=(x1,x2,…,xn)和y=(y1,y2,…,yn)，經(jīng)過非線性映射Φ(x)作用映射到特征空間H中，則這兩個向量在特征空間中的Euclidean 距離為：

(12)

其中K(·,·)是以上提到的核函數(shù)。在這里需要注意的是：在輸入空間中的樣本類中心經(jīng)映射后得到的值不再是特征空間中的樣本的中心矢量。設(shè)n是樣本的個數(shù)，則特征空間樣本的中心矢量mΦ須在特征空間中求得：

(13)

但是因?yàn)橛成洇?x)沒有進(jìn)行顯式的定義，所以無法直接根據(jù)式(13)來得到特征空間中樣本集的中心矢量。至今也仍沒有一個統(tǒng)一的計算公式來進(jìn)行直接的計算，為此，焦李成，等[6]給出了一個引理來計算該樣本的中心矢量，但計算復(fù)雜，且運(yùn)算量較大。為了避免該難題，目前更多的方法是通過聚類方法來得到特征空間的類中心，如模糊SVM，超球SVM等都是通過聚類的方法來確定類中心等。羅瑜[12]則是根據(jù)統(tǒng)計學(xué)的觀點(diǎn)和樣本信號的離散型，在訓(xùn)練集樣本是i.i.d.的條件下，從訓(xùn)練集中隨機(jī)抽取部分樣本代替整體樣本來計算類別質(zhì)心。為了簡化運(yùn)算及提高運(yùn)算的速度，本人利用近似替代的方法來獲取樣本中心，也就是通過在特征空間中尋找能生成最小超球的樣本點(diǎn)來代替特征樣本的中心矢量。其具體的算法如下：

2)則該樣本集的超球的半徑為：Rs=min(Ri),i=1,…,n。而該Ri所對應(yīng)的圓心樣本點(diǎn)便可作為該樣本集在特征空間中的中心矢量。

3 實(shí)驗(yàn)結(jié)果

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)采用臺灣林智仁LIBSVM官方學(xué)習(xí)網(wǎng)站http://www.csie.ntu.edu.tw/～cjlin/數(shù)據(jù)庫里的breast-cancer，heart-statlog，a7a，german.-number，iris數(shù)據(jù)集，其具體信息見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集

表中iris的類別為3類，實(shí)驗(yàn)中，以1類為+1類，2類和3類一起作為-1類進(jìn)行實(shí)驗(yàn)。此外訓(xùn)練樣本數(shù)目與測試樣本數(shù)目的比例中，除heart數(shù)據(jù)集的比例為170 ∶100，和另外的german數(shù)據(jù)集的比例為750 ∶250以外，其他樣本集均按8 ∶2的比例進(jìn)行實(shí)驗(yàn)。且所有實(shí)驗(yàn)都是在PC機(jī)(奔騰2.0 GHz，2.0 G內(nèi)存)，MATLAB R2011b，LIBSVM-3.12環(huán)境下進(jìn)行的。

3.2 與SVM比較

表2中列出了各種數(shù)據(jù)集在文中方法和SVM方法下的樣本數(shù)目，訓(xùn)練樣本數(shù)目，訓(xùn)練時間，訓(xùn)練準(zhǔn)確率及預(yù)測準(zhǔn)確率等。其結(jié)果均為10次實(shí)驗(yàn)后取的平均值。

表2 文中方法與SVM的比較

從表2的結(jié)果可以發(fā)現(xiàn)，就訓(xùn)練準(zhǔn)確率和預(yù)測準(zhǔn)確率而言，通過文中方法，iris數(shù)據(jù)集的訓(xùn)練準(zhǔn)確率和預(yù)測準(zhǔn)確率均為100%；heart、breast數(shù)據(jù)集的訓(xùn)練準(zhǔn)確率和預(yù)測準(zhǔn)確率均提高了1%左右； german、a7a數(shù)據(jù)集則在和準(zhǔn)確率上降低了0.5%～5.0%之間?？梢?，文中方法更適用于樣本數(shù)目中等的訓(xùn)練樣本集。此外，就訓(xùn)練樣本數(shù)目和訓(xùn)練時間而言，通過本文方法大大縮減了訓(xùn)練樣本集且較大的提高了訓(xùn)練時間，這個特點(diǎn)在大樣本數(shù)據(jù)集上表現(xiàn)較為明顯。

4 結(jié) 語

采用改進(jìn)的基于類中心的支持向量機(jī)訓(xùn)練樣本縮減策略，篩選出超平面附近的邊界樣本來訓(xùn)練分類器，在樣本集數(shù)目適中的情況下，其訓(xùn)練準(zhǔn)確率和預(yù)測準(zhǔn)確率稍優(yōu)于標(biāo)準(zhǔn)支持向量機(jī)，而且訓(xùn)練速度則提高了許多。但仍存有不足，改進(jìn)的算法需要消耗時間進(jìn)行邊界樣本尋找，無形地增加了時間開銷。此外，筆者還就非線性可分時，無法直接計算特征空間中的類中心問題，提出了利用近似替代方法。通過在特征空間中尋找能生成最小超球的樣本點(diǎn)來代替特征樣本的中心矢量，實(shí)驗(yàn)證明，該方法是現(xiàn)實(shí)可行的。

[1] 奉國和,李擁軍,朱思銘.邊界臨近支持向量機(jī)[J].計算機(jī)應(yīng)用研究,2006(4):11-12.

Feng Guohe,Li Yongjun,Zhu Siming.Boundary nearest support vector machines [J].Application Research of Computers,2006(4):11-12.

[2] Cortes C,Vapnik V.Support-vector networks [J].Machine Learning,1995,20(3):273-297.

[3] Osuna E,Freund R,Girosi F.An improved training algorithm for support vector machines[C]// Principe J,Gile L,Morgan N,et al.Neural Networks for Signal Processing Ⅶ.Amelia Island,F L:Proceedings of the 1997 IEEE Workshop,1997:276-285.

[4] Platt J C.Fast training of support vector machines using sequentia1 minima1 optimization[C]//Sch?lkopf B,Burges C J C,Smola A J.Advances in Kernel Methods-Support Vector Learning.Cambridge:MIT Press,1998:185-208.

[5] Platt J C.Using analytic QP and sparseness to speed training of support vector machines [C]//Kearns M S,Solla S A,Cohn D A.Advances in Neural Information Processing Systems.Cambridge: MIT Press,1999:557-563.

[6] 焦李成,張莉,周偉達(dá).支撐矢量預(yù)選取的中心距離比值法[J].電子學(xué)報,2001,29(3):383-386.

Jiao Licheng,Zhang Li,Zhou Weida.Pre-extracting support vectors for support vector machine [J].Chinese Journal of Electronics,2001,29 (3):383-386.

[7] 汪西莉,焦李成.一種基于馬氏距離的支持向量快速提取算法[J].西安電子科技大學(xué)學(xué)報:自然科學(xué)版,2004,31(4):639-643.

Wang Xili,Jiao Licheng.A fast algorithm for extracting the support vector on the mahalanobis distance [J].Journal of Xidian University:Natural Science,2004,31(4):639-643.

[8] 李青,焦李成,周偉達(dá).基于向量投影的支撐向量預(yù)選取[J].計算機(jī)學(xué)報,2005,28(2):145-152.

Li Qing,Jiao Licheng,Zhou Weida.Pre-extracting support vector for support vector machine based on vector projection [J].Chinese Journal of Computers,2005,28(2):145-152.

[9] 李紅蓮,王春花,袁保宗.一種改進(jìn)的支持向量機(jī)NN_SVM [J] .計算機(jī)學(xué)報,2003,26(8):1015-1020.

Li Honglian,Wang Chunhua,Yuan Baozong.An improved SVM:NN_SVM [J].Chinese Journal of Computers,2003,26(8):1015-1020.

[10] 郭亞琴,王正群.一種改進(jìn)的支持向量機(jī)BS_SVM[J].微電子學(xué)與計算機(jī),2010,27(6):54-56.

Guo Yaqin,Wang Zhengqun.An improved SVM:BS_SVM [J]. Microelectronics & Computer,2010,27(6):54-56.

[11] 朱方,顧軍華,楊欣偉,等.一種新的支持向量機(jī)大規(guī)模訓(xùn)練樣本集縮減策略[J] .計算機(jī)應(yīng)用,2009,29(10) :2736-2740.

Zhu Fang,Gu Junhua,Yang Xinwei,et al.New reduction strategy of large-scale training sample set for SVM [J].Journal of Computer Applications,2009,29(10):2736-2740.

[12] 羅瑜.支持向量機(jī)在機(jī)器學(xué)習(xí)中的應(yīng)用研究[D].成都:西南交通大學(xué),2007.

Luo Yu.Study on Application of Machine Learning Based on Support Vector Machine [D].Chengdu:Southwest Jiaotong University,2007.

[13] 曹淑娟,劉小茂,張鈞,等.基于類中心思想的去邊緣模糊支持向量機(jī)[J].計算機(jī)工程與應(yīng)用,2006,42(22):146-149.

Cao Shujuan,Liu Xiaomao,Zhang Jun,et al.Fuzzy support vector machine of dismissing margin based on the method of class-center [J].Computer Engineering and Applications,2006,42(22):146-149.