李紀(jì)麟 謝霖銓

摘 要：為了改善現(xiàn)有支持向量機(jī)（Support Vector Machine）的機(jī)器學(xué)習(xí)效果依賴于參數(shù)選擇，而參數(shù)選擇通常依賴于經(jīng)驗(yàn)的問(wèn)題，在現(xiàn)有基礎(chǔ)上，本文結(jié)合一種稱為骨架人工蜂群算法（Bare-bones Artificial Bee Colony）的改進(jìn)的人工蜂群算法對(duì)支持向量機(jī)的2個(gè)參數(shù)進(jìn)行優(yōu)化，并對(duì)該優(yōu)化結(jié)果進(jìn)行試驗(yàn)。試驗(yàn)結(jié)果表明，改進(jìn)的支持向量機(jī)的準(zhǔn)確率、識(shí)別速度均優(yōu)于原本的支持向量機(jī)。

關(guān)鍵詞：支持向量機(jī)；人工蜂群算法；參數(shù)優(yōu)化

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1003-5168（2017）03-0046-05

Abstract： In order to improve the performance of existing support vector machine in machine learning that depends on the parameters of SVM， and the parameters always depend on the experience of the problem， based on the existing conclusion， an SVM that hybrid with an improved artificial bee colony algorithm called bare-bones artificial bee colony algorithm was proposed to optimize the two parameters of SVM， and the optimized results were tested. The results showed that the improved SVM had better accuracy and recognition speed than the original support vector machine.

Keywords： support vector machine；artificial bee colony algorithm；parameter optimizing

支持向量機(jī)（Support Vector Machine，SVM）是一種監(jiān)督式的機(jī)器學(xué)習(xí)方法，能非常成功地處理回歸問(wèn)題（時(shí)間序列分析問(wèn)題）和分類問(wèn)題等諸多問(wèn)題，并可推廣用于預(yù)測(cè)和綜合評(píng)價(jià)等領(lǐng)域[1]。支持向量機(jī)經(jīng)過(guò)多年的發(fā)展，已經(jīng)出現(xiàn)了多種改進(jìn)算法，使得其性能有了很大的改進(jìn)[2]。文獻(xiàn)[3-5]通過(guò)實(shí)驗(yàn)證實(shí)核函數(shù)的參數(shù)的正確選擇對(duì)于SVM的性能有著至關(guān)重要的影響。現(xiàn)在通常使用的核函數(shù)是RBF核函數(shù)[4-8]。SVM的參數(shù)選擇實(shí)際上是一個(gè)優(yōu)化問(wèn)題。截至目前，SVM的參數(shù)選擇包括如下方法：經(jīng)驗(yàn)選擇法、交叉驗(yàn)證法、網(wǎng)格搜索法、貝葉斯法等[7]。近年來(lái)，隨著包括模擬退火算法（Simulate Annealing Algorithm，SA）[9]、遺傳算法（Genetic Algorithm，GA）[10]、粒子群優(yōu)化算法（Particle Swarm Optimization Algorithm，PSO）[11]和人工蜂群算法（Artificial Bee Colony Algorithm，ABC）[12]等優(yōu)化算法的發(fā)展，已有學(xué)者采用上述算法來(lái)優(yōu)化選擇SVM的參數(shù)[4，7，13]。

骨架人工蜂群算法（Bare-bones Artificial Bee Colony，BBABC）是一種改進(jìn)的人工蜂群算法[14]。該種算法相比原始的ABC及其他的優(yōu)化算法，有更好的收斂精度和收斂速度。本文使用BBABC對(duì)使用徑向基函數(shù)（Radial Basis Function，RBF）作為核函數(shù)的SVM的2個(gè)參數(shù)進(jìn)行優(yōu)化，并對(duì)優(yōu)化的結(jié)果進(jìn)行試驗(yàn)，取得了較好的效果。

1 人工蜂群算法

人工蜂群算法是一種啟發(fā)式群體智能優(yōu)化算法。該算法的基本思想是通過(guò)模擬蜂群中個(gè)體之間的分工和信息交流，相互協(xié)作尋找蜜源的過(guò)程。與經(jīng)典的優(yōu)化方法相比，ABC算法對(duì)目標(biāo)函數(shù)和約束幾乎沒(méi)有要求，在搜索過(guò)程中基本不利用外部信息，僅以適應(yīng)度函數(shù)作為進(jìn)化的依據(jù)，即是使用“生成+檢驗(yàn)”的方式[12]，這種方式十分適合用于解決NP完全問(wèn)題。ABC算法具有操作簡(jiǎn)單、控制參數(shù)少、搜索精度較高和魯棒性較強(qiáng)的特點(diǎn)[15-17]。Karaboga等[16]指出與遺傳算法、差分演化算法（Differential Evolution，DE）和粒子群優(yōu)化算法相比較，ABC算法的求解質(zhì)量相對(duì)較好。

Bare-Bones人工蜂群算法（BBABC，又稱BABC或BCABC）[14]是一種新型的基于ABC的改進(jìn)算法。該算法針對(duì)原始ABC具有較強(qiáng)的搜索性能和較弱的收斂性，引入了移動(dòng)距離參數(shù)自適應(yīng)，基于適應(yīng)度的最近鄰，以及在跟隨蜂階段引入高斯搜尋方程這三種方式來(lái)提高算法的收斂性。通過(guò)結(jié)合這三種方式，該算法能夠極大地提升ABC的收斂性，從而提升ABC的性能。

1.1 人工蜂群算法的基本原理

1.1.1 群體智能模型的組成。對(duì)于一個(gè)給定的優(yōu)化問(wèn)題，ABC算法使用一個(gè)模擬蜂群尋找更好的食物源的群體智能模型來(lái)尋找該優(yōu)化問(wèn)題的解。這個(gè)群體智能模型由3種類型的蜜蜂及食物源組成。具體的定義如下。

1.1.1.1 食物源。ABC算法中的食物源是連續(xù)或離散的解空間中的點(diǎn)。對(duì)于每一個(gè)點(diǎn)i，定義一個(gè)函數(shù)fit（xi）作為評(píng)價(jià)該點(diǎn)處蜜源的標(biāo)準(zhǔn)，這個(gè)標(biāo)準(zhǔn)也稱為適應(yīng)值。

ABC算法把蜂群分為2個(gè)部分，2種蜜蜂分別使用不同的策略來(lái)尋找新的食物源。將蜂群劃分的方式通常是50%為雇傭蜂，50%為跟隨蜂。

1.1.1.2 雇傭蜂（Employed Bees）。蜂群的兩種分類的其中一種是雇傭蜂。雇傭蜂尋找新的食物源的方式是在現(xiàn)有食物源的基礎(chǔ)上進(jìn)行開(kāi)采，在這個(gè)過(guò)程中可能雇傭跟隨蜂或不雇傭；雇傭跟隨蜂的過(guò)程即是“雇傭蜂”這個(gè)名字的由來(lái)。

1.1.1.3 跟隨蜂（Onlooker Bees）。蜂群的另一個(gè)部分是跟隨蜂。顧名思義，跟隨蜂的任務(wù)是選擇一個(gè)雇傭蜂并和該雇傭蜂一起對(duì)雇傭蜂所處的蜜源進(jìn)行開(kāi)發(fā)。

1.1.1.4 偵察蜂（Scout Bees）。雇傭蜂在認(rèn)為一個(gè)蜜源沒(méi)有繼續(xù)開(kāi)采的價(jià)值時(shí)（通常認(rèn)為該蜜源已陷入局部最優(yōu)的情況），他就會(huì)轉(zhuǎn)變?yōu)閭刹旆洳⒃谌炙阉饕粋€(gè)新的蜜源。偵察蜂在選擇了一個(gè)新的蜜源之后將會(huì)重新轉(zhuǎn)變?yōu)楣蛡蚍洹?/p>

1.1.2 ABC算法的過(guò)程。對(duì)于一個(gè)解空間的維度為D的問(wèn)題，ABC算法的過(guò)程如下。

如上所述，使用RBF作為核函數(shù)的支持向量機(jī)具有2個(gè)參數(shù)：懲罰因子C和RBF參數(shù)σ。王鵬等[4，5]實(shí)驗(yàn)論證了這兩個(gè)參數(shù)的正確選擇對(duì)SVM的準(zhǔn)確性具有重要影響。

3 通過(guò)BBABC進(jìn)行參數(shù)選擇的支持向量機(jī)

如上文所述，支持向量機(jī)的參數(shù)選擇對(duì)其計(jì)算的準(zhǔn)確性和泛化能力有重要影響。截至目前，支持向量機(jī)的參數(shù)選擇法主要包含：經(jīng)驗(yàn)選擇法、交叉驗(yàn)證法、網(wǎng)格搜索法、貝葉斯法以及包括SA、GA、PSO、ABC等優(yōu)化算法。其中，經(jīng)驗(yàn)選擇法依賴于問(wèn)題描述和使用者的經(jīng)驗(yàn)，依賴于問(wèn)題本身；交叉驗(yàn)證法、網(wǎng)格搜索法等算法較為盲目，時(shí)間復(fù)雜度較高，收斂性較差?，F(xiàn)有的優(yōu)化算法雖然具有一定的收斂性，但仍然稍顯不足。

通過(guò)使用支持向量機(jī)的分類準(zhǔn)確率作為基礎(chǔ)計(jì)算適應(yīng)度，則準(zhǔn)確率越高，適應(yīng)度越小。因此可以據(jù)此將BBABC和SVM相結(jié)合，算法步驟如下。

①預(yù)處理數(shù)據(jù)集，將數(shù)據(jù)集分為訓(xùn)練集A和測(cè)試集B。Cycle=1。

4 試驗(yàn)分析

4.1 數(shù)據(jù)來(lái)源

試驗(yàn)使用加州大學(xué)歐文分校（University of CaliforniaIrvine）提供的UCI數(shù)據(jù)集其中之一的Wine Quality數(shù)據(jù)集。該數(shù)據(jù)集包含產(chǎn)自北葡萄牙的葡萄牙青酒隨機(jī)取樣的4 898個(gè)樣本，每個(gè)樣本包含通過(guò)物理化學(xué)方式測(cè)量的密度、pH值、酒精度等12項(xiàng)特征。最終的質(zhì)量評(píng)級(jí)包含10個(gè)等級(jí)[19]。試驗(yàn)前已將所有特征歸一至[0，1]區(qū)間。試驗(yàn)分為2次，一次以前3/5的數(shù)據(jù)作為訓(xùn)練集，后2/5的數(shù)據(jù)作為測(cè)試集。另一次以前4/5的數(shù)據(jù)作為訓(xùn)練集，后1/5的數(shù)據(jù)作為測(cè)試集。

ABC的參數(shù)作如下設(shè)置：種群數(shù)為50，引領(lǐng)蜂數(shù)量為25，最大搜索次數(shù)設(shè)置為30， 最大迭代次數(shù)為150。

4.2 對(duì)比和評(píng)價(jià)標(biāo)準(zhǔn)

4.3 結(jié)果與分析

4.3.1 優(yōu)化速率和識(shí)別準(zhǔn)確率對(duì)比。使用隨機(jī)數(shù)、ABC、BBABC算法對(duì)SVM參數(shù)進(jìn)行優(yōu)化，優(yōu)化速率見(jiàn)圖1。使用優(yōu)化所得的參數(shù)建立識(shí)別模型，識(shí)別準(zhǔn)確率見(jiàn)表1，支持向量數(shù)見(jiàn)表2。結(jié)果表明，使用BBABC的算法效率、支持向量數(shù)及識(shí)別準(zhǔn)確率均優(yōu)于ABC算法。

相對(duì)于原始ABC SVM，BBABC-SVM的平均預(yù)測(cè)時(shí)間較少，識(shí)別速度較快。這主要由于BBABC-SVM減少了支持向量的數(shù)量，加快了算法的收斂速度。

4.3.2 識(shí)別時(shí)間對(duì)比。在實(shí)際運(yùn)用中，許多應(yīng)用需要保證實(shí)時(shí)性，因而預(yù)測(cè)速度也十分重要。為此，對(duì)上述數(shù)據(jù)的平均預(yù)測(cè)時(shí)間（單位s）進(jìn)行仿真試驗(yàn)，結(jié)果如表3所示。

5 結(jié)語(yǔ)

由上述優(yōu)化效果可見(jiàn)，使用BBABC優(yōu)化的SVM因?yàn)槔昧薆BABC的自適應(yīng)機(jī)制向最優(yōu)解方向收斂，在時(shí)間上和識(shí)別準(zhǔn)確率上均優(yōu)于使用ABC優(yōu)化的SVM，但識(shí)別準(zhǔn)確率仍稍顯不足。這可能是由于兩方面的原因：一是由于支持向量機(jī)的優(yōu)化是一個(gè)多峰值的問(wèn)題，算法可能由于早熟收斂陷入了局部最優(yōu)；二是分類樣本各類的分布不均勻。接下來(lái)的研究將圍繞避免早熟收斂、使算法跳出局部最優(yōu)的方向展開(kāi)。

參考文獻(xiàn)：

[1]VN Vapnik. The Nature of Statistical Learning Theory[M].New York：John Wiley and Sons，1998.

[2]丁世飛，齊丙娟，譚紅艷.支持向量機(jī)理論與算法研究[J].電子科技大學(xué)學(xué)報(bào)，2011（1）：2-10.

[3]陳健飛，蔣剛，楊劍鋒.改進(jìn)ABC-SVM的參數(shù)優(yōu)化及應(yīng)用[J].機(jī)械設(shè)計(jì)與制造，2016（1）：24-28.

[4]王鵬，郭朝勇，劉紅寧.基于支持向量機(jī)的槍彈外觀缺陷識(shí)別與分類[J].計(jì)算機(jī)工程與科學(xué)，2016（9）：1943-1949.

[5]M Zuriani，Y Yuhanis，SK Siti. Enhanced artificial bee colony for training least squares support vector machines in commodity price forecasting[J].Journal of Computational Science，2014（5）：196-205.

[6]張博洋.支持向量機(jī)理論與應(yīng)用研究綜述[J].無(wú)線互聯(lián)科技，2015（19）：111-112.

[7]寧愛(ài)平，張雪英，劉俊芳.ABC-PSO算法優(yōu)化混合核SVM參數(shù)及應(yīng)用[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2014（18）：158-165.

[8]古麗娜孜·艾力木江，孫鐵利，乎西旦.一種基于融合核函數(shù)支持向量機(jī)的遙感圖像分類[J].東北師大學(xué)報(bào)（自然科學(xué)版），2016（3）：60-66.

[9]AG Khachaturyan，SV Semenovskaya，BK Vainshtein. Statistical-Thermodynamic Approach to Determination of Structure Amplitude Phases[J].Sov. Phys. Crystallography，1979（5）：519-524.

[10]AE Eiben，PE Raué，Z Ruttkay. Genetic algorithms with multi-parent recombination[A]//International Conference on Evolutionary Computation，1994：78-87.

[11]KennedyJ，Eberhart R. Particle Swarm Optimization[A]//IEEE International Conference on Neural Networks，1995：1942-1948.

[12]Dervis Karaboga. An Idea Based On Honey Bee Swarm for Numerical Optimization[D].Erciyes：Erciyes University，2005.

[13]蔡麗霞，馬琰.基于ABC-SVM的考生行為自動(dòng)識(shí)別[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2015（5）：129-134.

[14]W Gao，F(xiàn)TS Chan，L Huang，et al. Bare bones artificial bee colony algorithm with parameter adaptation and fitness-based neighborhood[J].Information Sciences，2015（C）：180-200.

[15]D Karaboga，B Akay. A comparative study of artificial bee colony algorithm[J].Applied Mathematics and Computation，2009（14）：108-132.

[16]D Karaboga，B Basturk. On the performance of artificial bee colony（ABC）algorithm[J].Applied Soft Computing，2008（1）：687-697.

[17]秦全德，程適，李麗，等.人工蜂群算法研究綜述[J].智能系統(tǒng)學(xué)報(bào)，2014（2）：127-135.

[18]王慧穎，王文彬.基于改進(jìn)搜索策略的混合蜂群算法[J].系統(tǒng)工程與電子技術(shù)，2014（10）：2094-2101.

[19]P Cortez，A Cerdeira，F(xiàn) Almeida，et al. Modeling wine preferences by data mining from physicochemical properties[J]. Decision Support Systems，2009（4）：547-553.