基于均勻設(shè)計的支持向量機參數(shù)優(yōu)化方法＊

李長云，潘偉強，胡盛龍

（湖南工業(yè)大學(xué)計算機與通信學(xué)院，湖南 株洲 412007)

基于均勻設(shè)計的支持向量機參數(shù)優(yōu)化方法＊

李長云，潘偉強，胡盛龍

（湖南工業(yè)大學(xué)計算機與通信學(xué)院，湖南 株洲 412007)

在實際應(yīng)用中，支持向量機的性能依賴于參數(shù)的選擇。針對支持向量機的參數(shù)選擇問題進行了研究和分析，提出了基于均勻設(shè)計的支持向量機參數(shù)優(yōu)化方法。與基于網(wǎng)格搜索、粒子群算法、遺傳算法等支持向量機參數(shù)優(yōu)化方法進行了比較與分析，采用多個不同規(guī)模的標準的分類數(shù)據(jù)集進行測試，比較了四種方法的分類正確率和運行時間。仿真實驗表明，四種方法都能找到最優(yōu)參數(shù)，使支持向量機的分類正確率接近或超過分類數(shù)據(jù)集的理論精度，本文方法具有尋參時間短的特點。

支持向量機；參數(shù)優(yōu)化方法；均勻設(shè)計；網(wǎng)格搜索；粒子群算法；遺傳算法

1 引言

支持向量機SVM（Support Vector Machine)是由Cortes C和Vapnik V［1］提出來的，是建立在結(jié)構(gòu)風(fēng)險最小化準則和統(tǒng)計學(xué)習(xí)理論的基礎(chǔ)上的一種機器學(xué)習(xí)方法，其主要思想是建立一個超平面作為決策曲面，使得正例和反例之間的隔離邊緣被最大化。與其他傳統(tǒng)機器學(xué)習(xí)方法相比，SVM能較好地克服小樣本、維數(shù)災(zāi)難及過擬合等問題，被廣泛應(yīng)用于文本分類、圖像識別、手寫數(shù)字識別、生物信息學(xué)等領(lǐng)域［2］。

在實際應(yīng)用中，SVM的性能往往依賴于SVM參數(shù)的選擇，本文針對SVM的參數(shù)選擇問題進行了研究與分析。SVM的參數(shù)選擇大多依靠經(jīng)驗，采取試湊（try and error)的方法，比如基于網(wǎng)格搜索的SVM參數(shù)優(yōu)化方法（GS-SVM)、基于粒子群算法的SVM參數(shù)優(yōu)化方法（PSO-SVM)和基于遺傳算法的SVM參數(shù)優(yōu)化方法（GA-SVM)等。

PSO-SVM：將SVM的一個參數(shù)組合定義為一個粒子particle＝（C，g)，用SVM的交叉檢驗函數(shù)作為粒子群算法的適應(yīng)度函數(shù)，其返回值分類準確率作為個體適應(yīng)度，把SVM參數(shù)優(yōu)化問題轉(zhuǎn)化為粒子群算法優(yōu)化問題。例如，王喜賓等人［3］提出了粒子群模式搜索算法來搜索SVM的最優(yōu)參數(shù)，搜索到的最優(yōu)參數(shù)能達到較高的正確率；胡云艷等人［4］提出了一種基于粒子群和SVM的融合算法，此方法應(yīng)用到模擬電路診斷中，提高了模擬電路診斷正確率；郭鳳儀等人［5］提出了基于粒子群算法參數(shù)優(yōu)化的SVM模型，在擬合精度方面有很大的提高，且具有較好的泛化能力。

GA-SVM：將SVM的一個參數(shù)組合定義為遺傳算法的一個染色體chrom＝（C，g)，用SVM的交叉檢驗函數(shù)作為遺傳算法的適應(yīng)度函數(shù)，其返回值分類準確率作為個體適應(yīng)度，把SVM參數(shù)優(yōu)化問題轉(zhuǎn)化為遺傳算法優(yōu)化問題。例如，吳景龍等人［6］通過遺傳算法對SVM預(yù)測模型的各參數(shù)進行尋優(yōu)預(yù)處理，提高了SVM的預(yù)測精度；戴上平等人［7］提出了遺傳算法和粒子群算法融合算法對SVM參數(shù)進行優(yōu)化求解，實驗表明該方法是一種有效的方法。

上述方法均能找到合適的參數(shù)組合，使SVM模型具有較強的泛化能力，但是搜索最優(yōu)參數(shù)消耗時間較長，且易陷入局部解。針對這些問題，本文將SVM參數(shù)選擇問題轉(zhuǎn)化為一個均勻設(shè)計問題，提出了基于均勻設(shè)計的SVM參數(shù)優(yōu)化算法UDSVM（parameter optimization method of SVM based on Uniform Design)，并與 GA-SVM、GSSVM、PSO-SVM進行了比較，用多個不同規(guī)模的標準的分類數(shù)據(jù)集進行測試，比較各參數(shù)優(yōu)化方法的分類正確率和運行時間。通過仿真實驗驗證了本文方法的可行性和有效性。

2 SVM的數(shù)學(xué)描述

假設(shè)給定一個訓(xùn)練樣本集 （Xi，yi)，i＝1，2，…，l，Xi∈Rd，yi為樣本標簽，則SVM最優(yōu)分類超平面的二次最優(yōu)化問題如公式（1)所示：其中，W 為權(quán)值向量；ξi為松弛變量，ξi≥0；C為懲罰系數(shù)，b為負閾值。

將輸入空間映射到高維特征空間，得到原始問題（1)的對偶問題，如公式（2)所示：

常用的核函數(shù)有線性核函數(shù)、多項式核函數(shù)、RBF核函數(shù)和Sigmoid核函數(shù)等。本文采用目前使用最廣泛的RBF函數(shù)作為核函數(shù)，即K（Xi，Xj)＝exp｛－（Xi－Xj)2/2σ2｝，令參數(shù)g＝1/2σ2。以懲罰系數(shù)C和核函數(shù)參數(shù)g為研究對象。懲罰系數(shù)C實際上起控制錯分樣本懲罰程度的作用，目的是在錯分樣本的比例與算法復(fù)雜度之間的折衷，即C控制間隔的最大化與分類誤差之間的折衷，C越大，則對于錯分樣本的懲罰越大；C的取值小表示懲罰小，學(xué)習(xí)機器的復(fù)雜度小而經(jīng)驗風(fēng)險值較大，前者稱為過學(xué)習(xí)，而后者則為欠學(xué)習(xí)。C取值范圍為（0，100］，一般取值為1。核參數(shù)g主要影響樣本數(shù)據(jù)在高維特征空間中分布的復(fù)雜程度，g的改變實際上隱含了特征空間的 VC（Vapnik-Chervonenkis)維的改變，從而影響置信范圍，最終影響結(jié)構(gòu)風(fēng)險范圍，g一般取值為屬性個數(shù)的倒數(shù)。

3 相關(guān)工作

文獻［8］運用均勻設(shè)計對蟻群算法的參數(shù)進行成功的設(shè)定，使蟻群算法具有較優(yōu)的運行性能，仿真實驗說明了該方法的可行性和有效性。本文將SVM參數(shù)選擇問題轉(zhuǎn)化為一個均勻設(shè)計實驗的問題，提出了基于均勻設(shè)計的SVM參數(shù)優(yōu)化方法，UD-SVM的計算流程如圖1所示。

首先確定SVM的懲罰參數(shù)C和核函數(shù)參數(shù)g作為均勻設(shè)計實驗的因素，參數(shù)相應(yīng)的取值作為實驗的水平，參數(shù)范圍參照其他參數(shù)選擇方法給出初始范圍；然后根據(jù)因素數(shù)、水平數(shù)生成均勻設(shè)計表，按照參數(shù)取值范圍和均勻設(shè)計表編制實驗方案進行實驗，用訓(xùn)練過程中的5折交叉驗證正確率作為實驗指標；最后從已做的實驗中選擇一個指標最好的，相應(yīng)的參數(shù)組合就是所要求的最優(yōu)參數(shù)組合。UD-SVM的Matlab偽代碼如算法1所示。

Figure 1 Flowchart of SVM parameter optimization based on uniform design圖1 基于均勻設(shè)計的SVM參數(shù)優(yōu)化方法流程圖

4 實驗與分析

4.1 實驗過程

為了驗證 UD-SVM 的可行性和有效性，與GA-SVM、GS-SVM、PSO-SVM 進 行了比 較和分析，并進行了大量的仿真實驗。實驗的硬件平臺是CPU為Intel 2.93GHz、內(nèi)存為2.00GB的 PC機，軟件平臺是Matlab R2012b。采用國立臺灣大學(xué)林智仁的LibSVM工具箱和英國謝菲爾德大學(xué)的遺傳算法GATBX工具箱實現(xiàn)GA-SVM算法，UD-SVM、GS-SVM、PSO-SVM 算法均采用 Matlab編程實現(xiàn)。

從UCI［9］上選取了四個樣本個數(shù)、屬性個數(shù)和類別個數(shù)不同的標準數(shù)據(jù)集，即zoo、iris、wine、heart，各數(shù)據(jù)集的屬性如表1所示。

Table 1 Standard properties of the datasets表1 標準數(shù)據(jù)集的屬性

實驗之前先對所有的數(shù)據(jù)集進行數(shù)據(jù)標準化和主成分分析等數(shù)據(jù)預(yù)處理操作。將主成分分析法的總方差貢獻率設(shè)置為95%，并按照公式（4)進行數(shù)據(jù)標準化，將所有的數(shù)據(jù)規(guī)約到0.1到0.9之間，以消除數(shù)據(jù)量綱影響、變量自身變異大小和數(shù)值大小的影響。其中，xmin和xmax分別為數(shù)據(jù)集中各屬性的最小值和最大值，為標準化后的數(shù)據(jù)。

為了比較不同參數(shù)優(yōu)化方法的性能，對四種參數(shù)優(yōu)化方法進行了相應(yīng)的設(shè)置，參照相關(guān)文獻中參數(shù)C和g取值范圍，取SVM懲罰系數(shù)C的取值范圍為［0.001，100］，SVM 核函數(shù)參數(shù)g的取值范圍為［0.001，10］。在 UD-SVM 中，將SVM 參數(shù)C、g分別取20個水平，此時SVM參數(shù)設(shè)定問題就轉(zhuǎn)化為2因素20個水平的優(yōu)化設(shè)計問題，采用好格子點法生成均勻設(shè)計表U20（202)，根據(jù)均勻設(shè)計表設(shè)計如表2所示的實驗方案，其中，括號前的數(shù)值為均勻設(shè)計表的序號，括號中的數(shù)值為參數(shù)值。

Table 2 Experimental program based on uniform design表2 均勻設(shè)計實驗方案

為了排除偶然因素的影響，每個參數(shù)優(yōu)化方法重復(fù)進行10次，以統(tǒng)計出科學(xué)的實驗結(jié)果。從運行時間、交叉檢驗正確率、測試分類正確率等指標評價各參數(shù)優(yōu)化方法的性能。四種方法的實驗結(jié)果如表3所示。

PSO-SVM和GA-SVM在heart數(shù)據(jù)集上的進化曲線如圖2和圖3所示。

Figure 2 Evolution curve of PSO-SVM圖2 PSO-SVM進化曲線

4.2 實驗分析

根據(jù)圖2、圖3和表3，下面從分類正確率和運行時間兩個方面比較四種參數(shù)優(yōu)化方法的性能。

Table 3 Experimental results表3 實驗的結(jié)果

Figure 3 Evolution curve of GA-SVM圖3 GA-SVM進化曲線

（1)分類正確率。

由圖2和圖3可知，PSO-SVM 和 GA-SVM均能收斂到最優(yōu)解，即搜索到的最優(yōu)參數(shù)，使SVM的分類準確率接近理論精度。由表3可知，四種SVM參數(shù)優(yōu)化方法雖然運行時間上有差異，但都能找到合適的參數(shù)組合，使得SVM的分類正確率接近或者超過理論分類正確率。

（2)運行時間。

由表3可知，在SVM的分類正確率接近或者超過理論分類正確率的前提下，參數(shù)優(yōu)化方法運行時間從小到大依次是 UD-SVM、GS-SVM、GASVM、PSO-SVM，UD-SVM 利用20次實驗代表GS-SVM中20＊20次實驗的信息，而GA-SVM、PSO-SVM除了要訓(xùn)練SVM之外，還要消耗時間搜索最優(yōu)參數(shù)，UD-SVM 尋參的時間最短，GA-SVM、PSO-SVM尋參的時間較長。

5 結(jié)束語

本文比較和分析了四種SVM參數(shù)優(yōu)化方法，

針對PSO-SVM、GA-SVM尋參時間長和易陷入局部解的問題，提出了基于均勻設(shè)計的SVM參數(shù)優(yōu)化方法，將SVM參數(shù)優(yōu)化問題轉(zhuǎn)化為均勻設(shè)計的問題。與 GS-SVM、PSO-SVM、GA-SVM 在分類正確率和運行時間上進行了比較。大量仿真實驗表明，四種參數(shù)優(yōu)化方法雖然在運行效率上存在差異，但均能找到最優(yōu)參數(shù)組合，使得SVM的分類正確率接近或者超過理論分類正確率，此外，本文方法具有尋參時間短的特點。

［1］ Cortes C，Vapnik V.Support-vector networks［J］.Machine Learning，1995，20（3)：273-293.

［2］ Cristianini N，Shawe-Taylor J.An introduction to support vector machines and other kernel-based learning methods［M］.Cambridge：Cambridge University Press，2000.

［3］ Wang Xi-bin，Zhang Xiao-ping，Wang Han-hu.Parameter optimization of support vector machine and application based on particle swarm optimization mode search［J］.Journal of Computer Applications，2011，31（12)：3302-3304.（in Chinese)

［4］ Hu Yun-yan，Peng Min-fang，Tian Cheng-lai，et al.Analog circuit fault diagnosis based on particle swarm optimization SVM ［J］.Application Research of Computers，2012，29（11)：4053-4054.（in Chinese)

［5］ Guo Feng－yi，Guo Chang-na，Wang Ai-jun，et al.The forecast model of mine water discharge based on particle swarm optimization and support vector machines［J］.Computer Engineering ＆Science，2012，34（7)：177-181.（in Chinese)

［6］ Wu Jing-long，Yang Shu-xia，Liu Cheng-shui.Parameter selection for support vector machines based on genetic algorithms to short-term power load forecasting［J］.Journal of Central South University（Science and Technology)，2009，40（1)：180-184.（in Chinese)

［7］ Dai Shang－ping，Song Yong-dong.Parameter selection of support vector machines based on the fusion of genetic algorithm and the particle swarm optimization［J］.Computer Engineering ＆Science，2012，34（10)：113-117.（in Chinese)

［8］ Huang Yong－qing，Liang Chang－yong，Zhang Xiang-de.Parameter establishment of an ant system based on uniform design［J］.Control and Decision，2006，21（1)：93-96.（in Chinese)

［9］ UC irvine machine learning repository［EB/OL］.［2013-06-20］.http：//archive.ics.uci.edu/ml/.

附中文參考文獻：

［3］ 王喜賓，張小平，王翰虎.基于粒子群優(yōu)化模式搜索的支持向量機參數(shù)優(yōu)化及應(yīng)用［J］.計算機應(yīng)用，2011，31（12)：3302-3304.

［4］ 胡云艷，彭敏放，田成來，等.基于粒子群算法優(yōu)化支持向量機的模擬電路診斷［J］.計算機應(yīng)用研究，2012，29（11)：4053-4054.

［5］ 郭鳳儀，郭長娜，王愛軍，等.基于粒子群優(yōu)化支持向量機的煤礦水位預(yù)測模型［J］.計算機工程與科學(xué)，2012，34（7)：177-181.

［6］ 吳景龍，楊淑霞，劉承水.基于遺傳算法優(yōu)化參數(shù)的支持向量機短期負荷預(yù)測方法［J］.中南大學(xué)學(xué)報（自然科學(xué)版)，2009，40（1)：180-184.

［7］ 戴上平，宋永東.基于遺傳算法與粒子群算法的支持向量機參數(shù)選擇［J］.計算機工程與科學(xué)，2012，343（10)：113-117.

［8］ 黃永青，梁昌勇，張祥德.基于均勻設(shè)計的蟻群算法參數(shù)設(shè)定［J］.控制與決策，2006，21（1)：93-96.

Parameter optimization method of SVM based on uniform design

LI Chang－yun，PAN Wei-qiang，HU Sheng-long
（School of Computer and Communication，Hunan University of Technology，Zhuzhou 412007，China)

In practical applications，the performance of Support Vector Machine（SVM)depends on the selection of parameters.SVM parameter selection problems are studied and analyzed，and a parameter optimization method of SVM based on uniform design is proposed.Our method is compared with the parameter optimization methods of SVM based on grid search，particle swarm optimization，and genetic algorithms.Multiple classification data sets with different sizes are used for testing，so as to compare the classification accuracy and runtime of the four methods.Simulation results show that all the four methods can find the optimal parameters，which make the classification accuracy of SVM approach or exceed the theoretical accuracy of categorical datasets，and our proposed method has the characteristic of finding parameters in short time.

support vector machine；parameter optimization method；uniform design；grid search；particle swarm optimization；genetic algorithm

TP301.6

A

10.3969/j.issn.1007-130X.2014.04.022

2013-09-20；

2013-12-05

國家科技部科技支撐計劃項目（2013BAJ10B14-5)；國家住建部科研項目（2010FJ3041)；湖南省科技計劃資助項目（2012GK3091，2012GK3086)；湖南工業(yè)大學(xué)自然科學(xué)研究資助項目（2011HZX31)；湖南工業(yè)大學(xué)研究生創(chuàng)新基金資助項目（CX1308)

通訊地址：412007湖南省株洲市湖南工業(yè)大學(xué)計算機與通信學(xué)院

Address：School of Computer and Communication，Hunan University of Technology，Zhuzhou 412007，Hunan，P.R.China.

1007-130X（2014)04-0702-05

李長云（1971-)，男，湖南耒陽人，博士 后， 教 授，CCF 高 級 會 員（E200008765S)，研究方向為軟件方法學(xué)和軟件自動化。E-mail：lcy469＠163.com

LI Chang－yun，born in 1971，Post doctor，professor，CCF senior member（E200008765S)，his research interests include software methodology，and software automation.

潘偉強（1987-)，男，湖南湘鄉(xiāng)人，碩士生，CCF會員（E200034706G)，研究方向為人工智能算法。E-mail：bang1130＠126.com

PAN Wei-qiang，born in 1987，MS candidate，CCF member（E200034706G)，his research interest includes artificial intelligence algorithm.

胡盛龍（1988-)，男，湖南邵陽人，碩士生，CCF會員（E200034707G)，研究方向為人工智能算法。E-mail：candysee.hu＠gmail.com

HU Sheng-long，born in 1988，MS candidate，CCF member（E200034707G)，his research interest includes artificial intelligence algorithm.