宋小杉，蔣曉瑜，羅建華，姚軍

(1.裝甲兵工程學院 控制工程系，北京100072;2.裝甲兵工程學院 科研部，北京100072)

0 引言

支持向量機(SVM)由Vapnik 于1995年提出［1］，是一種智能學習機器，相對于人工神經(jīng)網(wǎng)絡，具有3 個優(yōu)點:1)SVM 以統(tǒng)計學習理論為基礎，從結構風險最小理論和VC 維理論發(fā)展而來，具有完善的理論基礎;2)SVM 同時考慮了經(jīng)驗風險最小和學習機器的復雜度，并進行了恰當?shù)恼壑校蛊渚哂辛撕芎玫姆夯芰?3)SVM 算法是一個凸二次規(guī)劃問題，因此具有全局最優(yōu)解。正是由于這些優(yōu)點，十幾年來，人們對SVM 的研究一直非?；钴S，從理論到應用被人們不斷完善和擴展。

導致SVM 得到廣泛應用的另一個原因是核函數(shù)的引進。核函數(shù)的引進有2 個好處:1)將樣本空間中線性不可分的樣本映射到更高維的特征空間中，使其線性可分;2)通過核函數(shù)用原空間中的運算實現(xiàn)更高維的特征空間中的運算，避免了“維數(shù)災難”問題。

常用的核函數(shù)有以下幾種

1)高斯徑向基函數(shù)(RBF):K (x，x')=exp(－γ‖x－x'‖2);

2)q 階多項式函數(shù):K(x，x')=［γ(xT，x')+b］q;

3)感知器核函數(shù):K(x，x')=tanh［γ(xT，x')+b］;

4)B 樣條函數(shù):K(x，x')=B2n+1(x－x');

其中RBF 核具有較少的參數(shù)和廣泛的普適性，在SVM 的應用中是首要選擇［2］。本文只針對RBFSVM 進行了研究。核函數(shù)選定后的首要工作是參數(shù)選擇，參數(shù)選擇的優(yōu)劣直接影響SVM 判別模型的泛化能力，是研究SVM 的重要內容，也是SVM 的研究熱點［1－10］。SVM 參數(shù)選擇最基本的方法是網(wǎng)格搜索法［1－2］，下文將詳細介紹。張學工等人最早將SVM 引進國內，2002年提出了基于變異函數(shù)的RBF參數(shù)估計方法［3］;2005年，Ayat［4］提出了一種基于SVM 分類錯誤概率估計的SVM 性能評價準則，并與GACV 和VC 維準則進行了比較，顯示了該方法選擇參數(shù)的有效性，但該方法實現(xiàn)較為復雜;近幾年，人們將遺傳算法和粒子群算法應用到SVM 參數(shù)選擇中［5－8］，文獻［9］將參數(shù)選擇看作非線性動態(tài)系統(tǒng)，利用擴展卡爾曼濾波算法進行選擇，這些算法均得到了較好的結果，但它們并沒有從參數(shù)本身的性質以及參數(shù)在SVM 中的本質作用入手來研究，所以都存在一定的局限;文獻［10］通過比較特征空間中5 種不同的距離定義式，指出了類中心之間的2范數(shù)距離最能有效估計SVM 判別函數(shù)的泛化性，并基于類中心距選擇核函數(shù)，但該文對類中心距的應用缺乏理論推導和深入分析。本文分析了RBF 核參數(shù)γ 對空間映射結果的影響，從分析結論中得到了基于ICMD 的核參數(shù)γ 評價方法，并從理論和實驗兩方面對該方法進行了深入分析，證明了該方法是1 種既有效、又省時的參數(shù)選擇方法。

1 SVM 原理

給定訓練樣本集:{(xi，yi)，i =1，2，…，l}，其中xi∈Rn，yi∈{1，－1}代表類別，l 為樣本集中樣本總數(shù)，則SVM 的原始優(yōu)化問題為

式中:w 是SVM 決策函數(shù)的法向量，ξi稱為松弛變量，是SVM 分類間隔軟化的標志，意味著可以存在被超平面錯分的樣本，C ＞0 是一個自定義的懲罰因子，控制著對錯分樣本的懲罰程度。

引入拉格朗日乘子法，得其對偶優(yōu)化問題為

對(2)式求解得到SVM 判決函數(shù)

可以看出，SVM 的實質是一個非線性空間的線性分類器。它首先通過核函數(shù)將樣本空間中的樣本向量映射到更高維數(shù)的非線性空間，然后在此非線性空間尋求一個最優(yōu)線性的分類超平面。其結構示意圖如圖1所示。所以SVM 的參數(shù)選擇也可以分為兩步，首先是核參數(shù)的選擇，核參數(shù)影響著對樣本空間的映射結果和特征向量在特征空間中的分布;其次是懲罰因子C，C 影響著SVM 決策函數(shù)對特征向量的錯分程度，C 越大，越不允許錯分。

圖1 SVM 結構示意圖Fig.1 Schematic diagram of the SVM structure

2 RBF 核參數(shù)對空間映射的影響

定義1:(核函數(shù))設χ 是Rn中的一個子集，稱定義在χ×χ 上的函數(shù)K(x，x')是核函數(shù)，如果存在著從χ 到某一個Hilbert 空間H 的映射

使得

其中(，)表示H 中的內積。

在特征空間中可以分別用內積和L2范數(shù)來衡量兩個向量之間的夾角和距離，所以有下面定理。

定理1:設Θi，j表示Hilbert 空間H 中任意兩向量Φ(xi)和Φ(xj)之間的夾角，則有

證明略。

定理2:設Di，j表示Hilbert 空間H 中任意兩向量Φ(xi)和Φ(xj)之間的距離，則有

證明略。

把RBF 表達式分別代入(4)式和(5)式，得到經(jīng)RBF 核映射的特征空間中任意兩向量Φ(xi)和Φ(xj)之間的夾角和距離分別是

和

從(6)式和(7)式可以看出，在RBF 所映射的空間中，γ 是唯一的參數(shù)，調節(jié)γ 的大小可以隱含地影響所映射的特征空間，以及特征向量在其中的分布。下面研究γ 對這對樣本映射結果的影響。

在樣本空間中，任意選取一對xi，xj，總存在ε ＞0，使得‖ xi－xj‖2≤ε.也就是說，樣本空間中兩向量之間的距離是個有限的實數(shù)。那么，在(6)式和(7)式可以中考慮兩種極限情況:

1)當γ→0 時，一方面cosΘi，j→1，從而Φ(xi)和Φ(xj)之間的夾角Θi，j→0，另一方面Φ(xi)和Φ(xj)之間的距離Di，j→0.說明當γ→0 時，RBF 核將樣本空間映射到了一個0 維點;

2)當γ→∞時，一方面cosΘi，j→0，從而Φ(xi)和Φ(xj)之間的夾角Θi，j→π/2，另一方面Φ(xi)和Φ(xj)之間的距離Di，j→說明當γ→∞時，RBF核將樣本空間映射到了一個l 維的空間，在這個空間特征向量兩兩正交，且每兩個特征向量之間的距離相等，這意味著在以距離和角度為相似度度量的特征空間里，所有Φ(xi)被同一化了。

γ 對映射結果的影響曲線如圖2所示。圖2顯示了γ 對映射結果影響的單調性，從而可以得出下面3 個結論

1)隨著γ 的增大，經(jīng)RBF 映射的特征空間的維數(shù)(FSD)單調增大。γ→0 時，F(xiàn)SD→0，γ→∞時，F(xiàn)SD→l.其中l(wèi) 是樣本空間中樣本的個數(shù)。

圖2 γ 對映射結果的影響Fig.2 Effects on the mapping space by γ

2)隨著γ 的增大，經(jīng)RBF 映射的特征空間中各向量之間的夾角Θi，j單調增大。γ→0 時，Θi，j→0，γ→∞時，Θi，j→π/2.

3)隨著γ 的增大，經(jīng)RBF 映射的特征空間中各向量之間的距離Di，j單調增大。γ→0 時，Di，j→0，γ→∞時，Di，j→

3 核空間中的類間距

令m1和m2分別表示核空間中第一類樣本和第二類樣本的中心向量

其中，l1和l2分別表示第1 類和第2 類的樣本個數(shù)，l1+ l2= l，x()i和x()i分別表示原空間中第1 類和第2 類中的樣本向量，那么核空間類間平均距表達式為

核空間類間角余弦值表達式為

核空間類內角余弦值表達式分別為

將(9)式、(10)式和(11)式代入(8)式得

可以看出類間平均距是類間角和類內角的一個綜合度量，當類間角較大、類內角較小時，D(C1，C2)取得較大值，反之則取得較小值。但由(9)式、(10)式和(11)式知，當特征集不變時，類間角和類內角均隨著核參數(shù)γ 的增大單調增大，那么類間平均距會不會也隨著核參數(shù)γ 的單調變化，是否存在一個核參數(shù)γ0，使得類間平均距達到最大。

由(8)式知，類間平均距與核參數(shù)γ 和特征向量xi，(i =1，2，…，l)有關，當特征集不變時xi不變，則類間平均距只與核參數(shù)γ 有關，令

有下面定理。

定理3:當γ∈［0，∞)時，J(γ)存在極大值。

證明:J(γ)在［0，∞)區(qū)間連續(xù)、在(0，∞)區(qū)間可導，又，由羅爾定理知必有ξ∈(0，∞)，使得J'(ξ)=0，即J(γ)存在極值J(ξ).

假設J(ξ)是極小值，則J(ξ)＜J(0)=0，但由J(γ)的定義知，當γ∈［0，∞)時J(γ)≥0.

所以假設不真。

所以，當γ∈［0，∞)時，J(γ)存在極大值。

證畢。

由定理3 知，雖然類間角和類內角均隨著核參數(shù)γ 的增大單調增大，但它們增大的幅度不同，在［0，∞)上存在一個核參數(shù)γ0，使類間平均距達到最大，這時核空間特征向量可分性也達到最好［12］。

為了清楚地觀察γ－J(γ)之間的關系，我們對從加州大學UCI 網(wǎng)站下載的公開實測特征數(shù)據(jù)庫［7］Heart、Australian、German 和Vehicle、Satimage分別作了γ－J(γ)曲線，如圖3所示。γ 的取值為γ={2－15，2－14，…，210}.

圖3 5 個樣本集的γ－ J(γ)曲線Fig.3 γ－ J(γ)Curves of 5 sample sets

Heart、Australian、German 數(shù)據(jù)庫中含有2 個類，而Vehicle 中含有4 個類，Satimage 含有6 個類。對多類數(shù)據(jù)，我們采用一對一計算策略。設數(shù)據(jù)庫中總共有N 個類，一對一計算策略就是從N 個類中依次取出2 個類進行計算，得到N × (N－ 1)/2 組J(γ)，用所有J(γ)的平均值作為最終結果。由圖3可以看出，對于這5 個樣本集，曲線均在一定的γ值處達到了最大，這5 個γ 值就是5 個樣本集對應的最優(yōu)核參數(shù)值。

4 RBF-SVM 參數(shù)選擇實驗

本文提出的核參數(shù)評價方法使得可以把(C，γ)分開來選擇。首先基于ICMD 得到最優(yōu)γ 值，在此基礎上，基于10－折交叉驗證選擇最優(yōu)的C 值，我們稱之為“兩步法”。10－折交叉驗證是一種經(jīng)典的SVM 性能評價準則，它首先把l 個樣本隨機分成10個互不相交的子集，即10－折S1，S2，…，S10，每個折大小大致相同。共進行10 次訓練與測試，第i 次的做法是，選擇Si為測試集，其余S1，…，Si－1，Si+1…，S10的合集為訓練集，算法根據(jù)訓練集求出判別函數(shù)后，即可對測試集Si進行測試。記其中錯誤分類的樣本數(shù)為li，10 次迭代完成后，便得到了l1，…，l10.10－折交叉驗證就是把10 次迭代的平均誤差作為SVM 性能評價準則。為窮極搜索范圍，C 的取值集合為{2－10，2－14，…，215}，γ 為{2－15，2－14，…，210}.這樣，用兩步法在上面的取值集合中完成一次參數(shù)選擇需要(26 +26 ×10)×l2次迭代運算。

網(wǎng)格搜索法是傳統(tǒng)的SVM 參數(shù)選擇方法［2］。網(wǎng)格搜索法就是把兩個參數(shù)取值集合中的值兩兩配對進行10－折交叉驗證，使交叉驗證錯誤率最小的參數(shù)對(C0，γ0)就是最優(yōu)參數(shù)。研究證明，網(wǎng)格搜索法能夠較好的評價SVM 性能，但其時間開銷太大，要在上面的取值集合中完成一次參數(shù)選擇需要26 ×26 ×10 ×l2次迭代運算。

實驗數(shù)據(jù)一部分與上節(jié)相同，來源于加州大學UCI 網(wǎng)站的公開實測特征數(shù)據(jù)庫Heart、Australian、German、Vehicle 和Satimage，另一部分則是我們自己建立的小物件特征庫和裝甲車輛特征庫。其中小物件特征庫中包含4 類目標，分別是充電器、打火機、瓶蓋和鑰匙，裝甲車輛特征庫包含2 類目標，分別是國產(chǎn)某型坦克和某型步戰(zhàn)車。每個特征庫包含一個訓練集和一個測試集，它們是獨立同分布的兩個數(shù)據(jù)集，SVM 基于訓練集進行訓練得到SVM 判別函數(shù)，然后在測試集上進行識別測試。實驗是在CPU 頻率1.7 GHz，內存512 M 的PC 機上用C 語言編程進行的。對含有多類的樣本集，采取了一對一的多類分類策略。表1給出了兩種方法進行核參數(shù)選擇的結果。

表1 網(wǎng)格搜索法和兩步法進行參數(shù)選擇結果比較Tab.1 Comparison between the grid search method and the two－stage method

表1給出了對上述對7 個數(shù)據(jù)庫分別用兩種方法進行SVM 參數(shù)選擇的結果，其中，Heart、German、Australian 和裝甲車輛均為2 類數(shù)據(jù)，Vehicle 和小物件均為4 類數(shù)據(jù)庫，而Satimage 則是包含了6 類目標的多類數(shù)據(jù)，實驗對多類分類采取一對一策略。從表1可以看出:1)對所有7 組實驗，基于ICMD 的二步參數(shù)選擇所用運算時間更短、速度更快;2)兩種SVM 參數(shù)選擇結果，對測試集的識別率非常接近，但本文提出的方法用時大大減少;3)本文提出的方法對2 類和多類均適用。說明基于ICMD 的二步參數(shù)選擇方法是一種既有效省時的好方法。

該結果同時也驗證了基于ICMD 方法進行核參數(shù)選擇的可靠性。

5 結論

參數(shù)選擇是SVM 研究的重要內容，其結果直接影響著SVM 決策函數(shù)的識別能力。本文針對RBFSVM，詳細分析了核參數(shù)γ 對空間映射結果的影響，得出了3 個重要結論?；诮Y論提出了一種新的核參數(shù)評價方法—最大ICMD 方法，使ICMD 值最大的核參數(shù)就是最優(yōu)核參數(shù)。文中對該方法進行了理論分析和實驗討論。該方法使得RBF－SVM 的參數(shù)選擇可分兩步進行:首先基于ICMD 找到最優(yōu)核參數(shù)γ，其次基于10－折交叉驗證得到最優(yōu)懲罰因子C。文中將兩步法與傳統(tǒng)的網(wǎng)格搜索法進行了實驗比較，結果顯示兩種方法選擇均選擇出了適當?shù)膮?shù)，但前者花費的時間遠遠小于后者，是一種更適合實際操作的方法。該實驗同時也驗證了基于ICMD方法進行核參數(shù)選擇的可靠性。

References)

［1］ Vapnik V.The nature of statistics learning theory ［M］.New York:Springer Verlag，1995.

［2］ Hsu C W，Chang C C，Lin C J.A practical guide to support vector classification［EB/OL］.Available at:http:∥www.csie.ntu.edu.tw/cjlin/ papers/ guide/guide.pdf，2003.

［3］ 閻輝，張學工，馬云潛，等.基于變異函數(shù)的徑向基核函數(shù)參數(shù)估計［J］.自動化學報，2002，28 (3):450－455.YAN Hui，ZHANG Xue－gong，MA Yu－qian，et al.The parameter estimation of RBF kernel function based on variogram［J］.Acta Automatica Sinica，2002，28(3):450－455.(in Chinese)

［4］ Ayat N E，Cheriet M，Suen C Y.Automatic model selection for the optimization of SVM kernels［J］.Pattern Recognition，2005，38(10):1733－1745.

［5］ Huang C L，Wang C J.A GA－based feature selection and parameters optimization for support vector machines［J］.Expert Systems with Applications，2006，31(2):231－240.

［6］ Yu Q，Zhang B H，Wang J L.Parameter optimization of e－SVM by Genetic Algorithm［C］∥The Fifth International Conference on Natural Computation，Tian Jin:ICNC，2009:540－542.

［7］ Guo X C，Yang J H ，Wu C G，et al.A novel LS－SVM hyper－parameter selection based on particle swarm optimization［J］.Neurocomputing，2008，71(16－18):3211－3215.

［8］ Zhang X Y，Guo Y L.Optimization of SVM parameters based on PSO Algorithm［C］∥The Fifth International Conference on Natural Computation，Tian Jin:ICNC，2009:536－539.

［9］ Mu T T，Nandi A K.Automatic tuning of L2－SVM parameters employing the Extended Kalman Filter［J］.Expert Systems，2009，26(2):160－175.

［10］ Wu K P，Wang S D.Choosing the kernel parameters for support vector machines by the inter－cluster distance in the feature space［J］.Pattern Recognition，2009，42(5):710－717.

［11］ Blake C L，Merz C J.UCI Repository of machine learning databases［EB/OL］.http:∥www.ics.uci.edu/～mlearn/MLRepository.html.2003.