李長云，潘偉強(qiáng)，胡盛龍

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

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

李長云，潘偉強(qiáng)，胡盛龍

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

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

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

1 引言

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

在實(shí)際應(yīng)用中，SVM的性能往往依賴于SVM參數(shù)的選擇，本文針對(duì)SVM的參數(shù)選擇問題進(jìn)行了研究與分析。SVM的參數(shù)選擇大多依靠經(jīng)驗(yàn)，采取試湊（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的一個(gè)參數(shù)組合定義為一個(gè)粒子particle＝（C，g)，用SVM的交叉檢驗(yàn)函數(shù)作為粒子群算法的適應(yīng)度函數(shù)，其返回值分類準(zhǔn)確率作為個(gè)體適應(yīng)度，把SVM參數(shù)優(yōu)化問題轉(zhuǎn)化為粒子群算法優(yōu)化問題。例如，王喜賓等人［3］提出了粒子群模式搜索算法來搜索SVM的最優(yōu)參數(shù)，搜索到的最優(yōu)參數(shù)能達(dá)到較高的正確率；胡云艷等人［4］提出了一種基于粒子群和SVM的融合算法，此方法應(yīng)用到模擬電路診斷中，提高了模擬電路診斷正確率；郭鳳儀等人［5］提出了基于粒子群算法參數(shù)優(yōu)化的SVM模型，在擬合精度方面有很大的提高，且具有較好的泛化能力。

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

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

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

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

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

常用的核函數(shù)有線性核函數(shù)、多項(xiàng)式核函數(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為研究對(duì)象。懲罰系數(shù)C實(shí)際上起控制錯(cuò)分樣本懲罰程度的作用，目的是在錯(cuò)分樣本的比例與算法復(fù)雜度之間的折衷，即C控制間隔的最大化與分類誤差之間的折衷，C越大，則對(duì)于錯(cuò)分樣本的懲罰越大；C的取值小表示懲罰小，學(xué)習(xí)機(jī)器的復(fù)雜度小而經(jīng)驗(yàn)風(fēng)險(xiǎn)值較大，前者稱為過學(xué)習(xí)，而后者則為欠學(xué)習(xí)。C取值范圍為（0，100］，一般取值為1。核參數(shù)g主要影響樣本數(shù)據(jù)在高維特征空間中分布的復(fù)雜程度，g的改變實(shí)際上隱含了特征空間的 VC（Vapnik-Chervonenkis)維的改變，從而影響置信范圍，最終影響結(jié)構(gòu)風(fēng)險(xiǎn)范圍，g一般取值為屬性個(gè)數(shù)的倒數(shù)。

3 相關(guān)工作

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

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

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

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)過程

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

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

Table 1 Standard properties of the datasets表1 標(biāo)準(zhǔn)數(shù)據(jù)集的屬性

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

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

Table 2 Experimental program based on uniform design表2 均勻設(shè)計(jì)實(shí)驗(yàn)方案

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

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

Figure 2 Evolution curve of PSO-SVM圖2 PSO-SVM進(jìn)化曲線

4.2 實(shí)驗(yàn)分析

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

Table 3 Experimental results表3 實(shí)驗(yàn)的結(jié)果

Figure 3 Evolution curve of GA-SVM圖3 GA-SVM進(jìn)化曲線

（1)分類正確率。

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

（2)運(yùn)行時(shí)間。

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

5 結(jié)束語

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

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

［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/.

附中文參考文獻(xiàn)：

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

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

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

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

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

［8］ 黃永青，梁昌勇，張祥德.基于均勻設(shè)計(jì)的蟻群算法參數(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

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

通訊地址：412007湖南省株洲市湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(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 高 級(jí) 會(huì) 員（E200008765S)，研究方向?yàn)檐浖椒▽W(xué)和軟件自動(dòng)化。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.

潘偉強(qiáng)（1987-)，男，湖南湘鄉(xiāng)人，碩士生，CCF會(huì)員（E200034706G)，研究方向?yàn)槿斯ぶ悄芩惴ā-mail：bang1130＠126.com

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

胡盛龍（1988-)，男，湖南邵陽人，碩士生，CCF會(huì)員（E200034707G)，研究方向?yàn)槿斯ぶ悄芩惴?。E-mail：candysee.hu＠gmail.com

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