基于類中心的SVM訓練樣本集縮減改進策略

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

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

0 引 言

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

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

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

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

筆者提出了一種改進的縮減訓練集的方法。首先根據各樣本點到樣本集中心的矢量距離，構造超球；然后通過只提取超平面及距離超平面較近的樣本實現邊界樣本的提取，從而實現樣本集的縮減。

1 支持向量機

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

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

1.1 線性支持向量機

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

設訓練樣本為(x1,y1),(x2,y2),…,(xl,yl),xi∈Rn為描述樣本的n維特征向量，yi∈{+1,-1}代表xi所屬的類別。因為可能存在有樣本不能被超平面正確分類, 所以引入松弛變量ξ，結合正則超平面min|ω·x+b|=1，求最優超平面的問題則可歸結為以下優化問題:

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

i=1,…,k。

(1)

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

(2)

根據Karush-Kuhn-Tucker定理，在鞍點有：

(3)

簡化后有：

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

(4)

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

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

(5)

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

定理1 支持向量機的訓練結果與非支持向量無關。

1.2 非線性支持向量機

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

(6)

則決策函數為：

(7)

通過引進核函數，SVM巧妙地解決了在將低維空間向量映射到高維空間向量時帶來的“維數災難”問題。

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

2.1 支持向量機幾何基礎知識

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

圖1 最優超平面與類中心的關系Fig.1 Relationship between optimal hyperplane and class-center

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

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

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

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

4)利用3)訓練得到的SVM對樣本點進行分類。

圖2 最優超平面與樣本點結構的關系Fig.2 Relationship between optimal hyperplane and data structure

2.2 線性可分的支持向量預選取

2.2.1 文中用到的定義

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

(8)

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

(9)

2.2.2 基于類中心邊界向量預取算法

1)將原始訓練樣本根據標號的不同分成兩類S+,S-。l+為正類樣本的個數,l-為負類樣本的個數, 其中l=l++l-。

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

4)由文獻[13]的去邊緣方法使得與支持向量相關的兩個半球內的樣本點：

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

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

(10)

5)通過公式：

(11)

來確定正類、負類樣本集中各自所對應的邊界樣本。其中0 <λ1±,λ2±< 1，其具體的取值取決于樣本的分布情況。考慮樣本點分布的結構特點，文中λ1與各自均值距離與其半徑的比值相關。同時，為了進一步減少孤立樣本點對訓練結果的不良影響，引人了λ2，其取值與處于樣本邊緣且個數小于樣本總個數1/100的樣本相關。

2.3 非線性可分的支持向量預選取

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

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

(12)

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

(13)

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

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

3 實驗結果

3.1 實驗環境

實驗采用臺灣林智仁LIBSVM官方學習網站http://www.csie.ntu.edu.tw/～cjlin/數據庫里的breast-cancer，heart-statlog，a7a，german.-number，iris數據集，其具體信息見表1。

表1 實驗數據集

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

3.2 與SVM比較

表2中列出了各種數據集在文中方法和SVM方法下的樣本數目，訓練樣本數目，訓練時間，訓練準確率及預測準確率等。其結果均為10次實驗后取的平均值。

表2 文中方法與SVM的比較

從表2的結果可以發現，就訓練準確率和預測準確率而言，通過文中方法，iris數據集的訓練準確率和預測準確率均為100%；heart、breast數據集的訓練準確率和預測準確率均提高了1%左右； german、a7a數據集則在和準確率上降低了0.5%～5.0%之間。可見，文中方法更適用于樣本數目中等的訓練樣本集。此外，就訓練樣本數目和訓練時間而言，通過本文方法大大縮減了訓練樣本集且較大的提高了訓練時間，這個特點在大樣本數據集上表現較為明顯。

4 結 語

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

[1] 奉國和,李擁軍,朱思銘.邊界臨近支持向量機[J].計算機應用研究,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] 焦李成,張莉,周偉達.支撐矢量預選取的中心距離比值法[J].電子學報,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].西安電子科技大學學報:自然科學版,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] 李青,焦李成,周偉達.基于向量投影的支撐向量預選取[J].計算機學報,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] 李紅蓮,王春花,袁保宗.一種改進的支持向量機NN_SVM [J] .計算機學報,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] 郭亞琴,王正群.一種改進的支持向量機BS_SVM[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] .計算機應用,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] 羅瑜.支持向量機在機器學習中的應用研究[D].成都:西南交通大學,2007.

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

[13] 曹淑娟,劉小茂,張鈞,等.基于類中心思想的去邊緣模糊支持向量機[J].計算機工程與應用,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.