核極化的核參數(shù)選擇算法

張文興，陳肖潔，王建國

（內(nèi)蒙古科技大學 機械工程學院，內(nèi)蒙古 包頭 014010）

1 引言

支持向量機（support vector machine，SVM）是在1992年的計算學習理論會議上由文獻[1]引進機器學習領域的新一代智能算法。SVM廣泛應用于模式識別和回歸估計，如金屬結構安全評估[2]、鉚接力的回歸預測[3]。SVM是基于核的學習機器，其核心是通過核函數(shù)隱式定義非線性變換，即不必顯式地計算從輸入空間到高維特征空間的非線性變換，而是在高維特征空間中隱式地高效計算內(nèi)積。顯然，通過核函數(shù)所構建的核矩陣包含了訓練數(shù)據(jù)和高維特征空間隱含的信息，SVM的泛化能力在很大程度上依賴于核函數(shù)的確定，而核參數(shù)直接影響著核函數(shù)的構建。因而，選擇一個適當?shù)暮藚?shù)是求解的第一步。

目前，常用的參數(shù)選擇方法有以下幾種：（1）根據(jù)問題的先驗信息來選擇參數(shù)，但該方法僅對一些特殊問題如圖像識別有效，并不適用于一般問題；（2）k-折交叉驗證法[4]（在實際應用中10折交叉驗證應用最廣）是參數(shù)選擇經(jīng)典的方法，其本質是用參數(shù)空間中每一組可能的參數(shù)組合去訓練和測試SVM，找出效果最好的參數(shù)組合，其特點是經(jīng)驗性強，計算量大，且不適用于優(yōu)化參數(shù)多于兩個的情況；（3）通過梯度下降法最小化泛化誤差來進行多參數(shù)選取[5]，但該方法需要迭代求解對偶問題，計算量較大；（4）一些精度較高，但計算復雜性也較高的優(yōu)化算法，如基于Bayesian方法；（5）基于優(yōu)化核度量標準的方法，其主要出發(fā)點是如何衡量核函數(shù)和學習任務（分類）的一致性[6]。其基礎是一系列獨立于算法的核度量標準的提出，如核排列（kernelalignment）[7-8]、核極化（kernelpolarization）[9]等。核度量標準著力于捕捉訓練數(shù)據(jù)集在高維特征空間中的可分離特性，在不考慮核函數(shù)計算復雜度的前提下，計算復雜度為o（l2），其中，l是訓練樣本的個數(shù)，因而計算是高效率的。遵循上述核度量標準的思路，將核極化直接最大化算法應用于Gaussian核和Polynomial核的核參數(shù)的選擇中，以使多類SVM獲得更好的分類性能。

2 支持向量機（SVM）

2.1 二分類SVM提出及求解

樣本集 D=（xi，yi），xi∈Rn，yi∈｛+1，-1｝，i=1，…，l，能將 D正確地分為兩類的最優(yōu)分類超平面＜ω·x＞+b=0的求解等價于解l1-SVM或C-SVM，其原始問題為：

式中：C—正則化參數(shù)（權衡調和最大化平面間隔和最小化訓練錯誤兩個目標）；ξi—松弛變量；φ（x）—從輸入空間到高維特征空間的映射。

拉格朗日乘子法求解（1）式，得到Wolfe對偶問題：

式中：αi—拉格朗日乘子，解中αi≠0所對應的xi稱為支持向量，即對最優(yōu)分類超平面有貢獻的樣本，αi≠0稱為支持向量值。解上述優(yōu)化問題（2）可以得到如下決策函數(shù)：

2.2 多分類SVM的求解

多分類SVM的求解主要分為兩種[10]：（1）將多分類問題轉化為二分類問題，如one-versus-rest（1-v-r）和one-versus-one（1-v-1）算法；（2）用一個最優(yōu)化問題一次求解所有的超平面實現(xiàn)多分類分類。1-v-r算法：此方法簡單、有效，但當類別較大時，某一類的訓練樣本將大大少于其他類訓練樣本的總和，這種訓練樣本間的不均衡將明顯地影響測試精度。1-v-1算法：測試時采用投票法，類別輸出為得票數(shù)最多的那一類，在實際應用中，一般推薦使用1-v-1方法。而對于在一個最優(yōu)化問題中求解多個分類面的參數(shù)的方法，乍看起來簡潔快捷高效，但是在實際操作過程中，過多的變量和過于復雜的目標函數(shù)導致過高的計算復雜度，在分類準確率上也毫無優(yōu)勢可言。因此，該算法在實際問題中并不適用。

3 核函數(shù)

在SVM中，核函數(shù)的構造和選擇尤其重要。在滿足Mercer條件的情況下，在SVM理論研究與實際應用中，最常使用的有以下4類基本核函數(shù)：線性核、多項式核、Gaussian核和Sigmoid核。采用Polynomial核和Gaussian核，其形式如下：

式中：γ、r、d—核參數(shù)。

4 核極化及核參數(shù)選擇算法

Baram在2005年，針對于二分類問題，提出了一種核函數(shù)度量標準—核極化，核極化體現(xiàn)了核矩陣G與理想核矩陣yyT之間的相似度，其形式為：

式中：y=（y1，…yi）T，G—核矩陣，即是理想核矩陣，＜·，·＞F表示具有同樣維數(shù)的一對矩陣之間的Frobenius內(nèi)積。針對多分類問題，文獻[9]提出了一個新的適應于多分類（也適應二分類）情形的核函數(shù)度量標準：

式（7）清楚地顯示，核極化是一個標量值，其值越大意味著在特征空間中同類的數(shù)據(jù)點相互靠近，而異類的數(shù)據(jù)點相互遠離[9]。P可以度量多分類樣本的可分性，P值越大說明其數(shù)據(jù)集樣本在設定的核函數(shù)下具有越好的可分性，以此建立的SVM模型，具有越強的泛化能力。值得關注的另一點是，其計算復雜度為O（l2），具有高效計算性。采用核極化P來指導Gaussian核和Polynomial核的核參數(shù)的選擇，選擇使得Pmax（γ）的γ值，此時，γ值對應的最大值P說明其數(shù)據(jù)集樣本在該γ值時具有較好的可分性。較優(yōu)γ值的選取我們采用網(wǎng)格搜索法，其算法步驟如下：（1）（初始化）核函數(shù)的 Pmax及 γ 值，設置 γ1=γmin=2-8，γmax=28，r=1，d=3；（2）（迭代）對于每一個 γi=γi-1·4，計算其對應的 Pi；（3）若 Pi≥Pmax時，更新 Pmax和γ值；（4）轉到第2步，直到滿足停機條件。實驗對應的算法流程圖，如圖1所示。

圖1 核參數(shù)選擇算法流程圖Fig.1 The Flow Chart of Kernel Parameter Selection Algorithm

5 實驗

5.1 數(shù)據(jù)處理

UCI數(shù)據(jù)庫中的 7 個數(shù)據(jù)集：Breast Cancer Wisconsin，Iris，Wine，Car，glass，Zoo，Balance。其中 Breast Cancer Wisconsin 為二分類數(shù)據(jù)集，其余均為多分類數(shù)據(jù)集。數(shù)據(jù)集的基本情況，如表1所示。每個數(shù)據(jù)集都經(jīng)過歸一化（0，1）預處理，即：

式中：i—樣本的某個輸入特征。選取總樣本數(shù)的70%為訓練集和30%為測試集，采用libsvm軟件包（該軟件包采用1-v-1的方法）實現(xiàn)了多類SVM分類。

表1 實驗使用的數(shù)據(jù)集Tab.1 Data Sets for Experiments

5.2 評價指標

實驗中選用分類正確率（又稱為分類精度）作為算法的評價指標。其表達式為Acc=Cor/Tot，Cor為分類正確的樣本點數(shù)，Tot為總樣本點數(shù)，Acc為分類正確率。

5.3 實驗方法

設置Gaussian核和Polynomial核的核參數(shù)γ的取值范圍為γmin=2-8，γmax=28。首先，利用前面所介紹的核參數(shù)選擇方法，選擇出Pmax（γ）的γ值。然后，用選擇出的γ和設置懲罰系數(shù)C=80，訓練和測試SVM。為驗證所提出基于核極化的核參數(shù)選擇算法的有效性，選擇目前SVM最常用經(jīng)典的10折交叉驗證法作為比較。設置懲罰系數(shù) C=｛2-8，2-6，…，28｝和 γ=｛2-8，2-6，…，26，28｝，利用 10折交叉驗證法選擇出最優(yōu)參數(shù)組合和進行測試。所有實驗的平臺為Intel（R）Core（TM）2 Duo CPU E8200@2.66GHz 2.00GB RAM的個人計算機，Win732位操作系統(tǒng)。實驗流程圖，如圖2所示。

圖2 實驗方法流程圖Fig.2 The Flow Chart of Experimental Methods

5.4 實驗結果及其分析

實驗方法的多類SVM分類準確率的平均值（采用10次實驗的平均值），如表2所示。對應于表2各數(shù)據(jù)集實驗結果的運行時間，如表3所示。

表2 數(shù)據(jù)集上的實驗結果Tab.2 Experimental Results of Data Sets

表3 實驗結果的運行時間Tab.3 Running Time of Experimental Results

表2的2～3列或4～5列的數(shù)據(jù)顯示，對于Gaussian核或Polynomial核采用方法的SVM的泛化能力并不弱于10折交叉驗證法，大部分數(shù)據(jù)集的準確率高于10折交叉驗證法。表3說明采用方法計算的高效性。表2的第2列與第4列和第3列與第5列說明，只有一個核參數(shù)r的Gaussian核比有三個核參數(shù)的Polynomial核在分類方面具有更高的準確率，但是，不可忽視的是，在分類準確率上略遜于Gaussian核的Polynomial核的運行時間遠小于Gaussian核。以上分析說明，所提出的基于核極化的核參數(shù)選擇算法的有效性，計算的高效性。同時，也說明了Polynomial核雖然沒有Gaussian核的調整核參數(shù)少，分類精度高等優(yōu)點，但是其運行速度的高效性也同樣值得我們關注。

6 結論

在深入分析核極化這個核度量標準的基礎上，提出了利用直接最大化核極化來選擇核參數(shù)值的算法，并將其運用到Gaussian核和Ploynomial核的核參數(shù)r選擇中，提升了多類SVM的分類性能。在整個核函數(shù)的核參數(shù)選擇過程中無須反復地訓練和測試SVM，也不需要求解一個額外的、復雜的二次規(guī)劃問題，因而計算是高效的。

［1］Boser B E，Guyon I M，Vapnik V N.A training algorithm for optimal margin classifiers［C］.5th Annual ACM Conference on Computational Learning Theory.Pittsburgh，PA，ACM Press，1992：144-152.

［2］舒文杰，徐桂芳，魏國前.SVM的起重機金屬結構安全評估研究［J］.機械設計與制造，2014（12）：269-272.（Shu Wen-jie，Xu Gui-fang，Wei Guo-qian.Metal structure safety assessment of crane based on SVM［J］.Machinery Design＆Manufacture，2014（12）：269-272.）

［3］陳健飛，蔣剛，楊劍鋒.改進ABC-SVM的參數(shù)優(yōu)化及應用［J］.機械設計與制造，2016（1）：24-28.（Chen Jian-fei，Jiang Gang，Yang Jian-feng.Improved ABC-SVM parameter optimizationand application［J］.MachineryDesign ＆ Manufacture，2016（1）：24-28.）

［4］Duan K B，Keerthi S S，Poo A N.Evaluation of simple performance measures for tuning SVM hyperparameters［J］.Neurocomputing，2003（51）：41-59.

［5］常群，王曉龍，林沂蒙.支持向量分類和多寬度高斯核［J］.電子學報，2007，35（3）：484-487.（Chang Qun，Wang Xiao-long，Lin Qi-meng.Support vector classification and Gaussain kernel with multiple widths［J］.Acta Electronica Sinica，2007，35（3）：484-487.）

［6］汪廷華，陳峻婷.核函數(shù)的度量研究進展［J］.計算機應用研究，2011，28（1）：25-28.（Wang Ting-hua，Chen Jun-ting.Survery of research on kernel function evaluation［J］.Application Research of Computers，2011，28（1）：25-28.）

［7］Cortes C，Mohri M，Rostamizadeh A.Algorithms for learning kernel based on centered alignment［J］.J Mach Learn Res，2012（13）：795-828.

［8］Wang Ting-hua，Zhao Dong-yan，Tian Shen-feng.An overview of kernel alignment and its applications［J］.Artif Intell Rev，2015（43）：149-192.

［9］汪廷華，趙東巖，張瓊.多類核極化及其在多寬度RBF核參數(shù)選擇中的應用［J］.北京大學學報：自然科學版，2012，48（5）：727-731.（Wang Ting-hua，Zhao Dong-yan，Zhang Qiong.Multiclass kernel polarization and its application to parameter selection of RBF kernel with multiplewidths［J］.ActaScientiarumNaturaliumUniversitatisPekinensis，2012，48（5）：727-731.）

［10］Hsu C W，Lin C J.A comparison of methods for multiclass support vector machines［J］.IEEETransactions on Neural Networks，2002，13（2）：415-425.