李紀(jì)麟 謝霖銓

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

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

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：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í)方法，能非常成功地處理回歸問題（時間序列分析問題）和分類問題等諸多問題，并可推廣用于預(yù)測和綜合評價等領(lǐng)域[1]。支持向量機(jī)經(jīng)過多年的發(fā)展，已經(jīng)出現(xiàn)了多種改進(jìn)算法，使得其性能有了很大的改進(jìn)[2]。文獻(xiàn)[3-5]通過實驗證實核函數(shù)的參數(shù)的正確選擇對于SVM的性能有著至關(guān)重要的影響。現(xiàn)在通常使用的核函數(shù)是RBF核函數(shù)[4-8]。SVM的參數(shù)選擇實際上是一個優(yōu)化問題。截至目前，SVM的參數(shù)選擇包括如下方法：經(jīng)驗選擇法、交叉驗證法、網(wǎng)格搜索法、貝葉斯法等[7]。近年來，隨著包括模擬退火算法（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é)者采用上述算法來優(yōu)化選擇SVM的參數(shù)[4，7，13]。

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

1 人工蜂群算法

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

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

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

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

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

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

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

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

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

1.1.2 ABC算法的過程。對于一個解空間的維度為D的問題，ABC算法的過程如下。

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

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

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

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

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

4 試驗分析

4.1 數(shù)據(jù)來源

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

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

4.2 對比和評價標(biāo)準(zhǔn)

4.3 結(jié)果與分析

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

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

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

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

[4]王鵬，郭朝勇，劉紅寧.基于支持向量機(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].無線互聯(lián)科技，2015（19）：111-112.

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

[8]古麗娜孜·艾力木江，孫鐵利，乎西旦.一種基于融合核函數(shù)支持向量機(jī)的遙感圖像分類[J].東北師大學(xué)報（自然科學(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的考生行為自動識別[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é)報，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.