李紀麟 謝霖銓

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

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

中圖分類號：TP18 文獻標識碼：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

支持向量機（Support Vector Machine，SVM）是一種監(jiān)督式的機器學習方法，能非常成功地處理回歸問題（時間序列分析問題）和分類問題等諸多問題，并可推廣用于預測和綜合評價等領域[1]。支持向量機經過多年的發(fā)展，已經出現(xiàn)了多種改進算法，使得其性能有了很大的改進[2]。文獻[3-5]通過實驗證實核函數(shù)的參數(shù)的正確選擇對于SVM的性能有著至關重要的影響。現(xiàn)在通常使用的核函數(shù)是RBF核函數(shù)[4-8]。SVM的參數(shù)選擇實際上是一個優(yōu)化問題。截至目前，SVM的參數(shù)選擇包括如下方法：經驗選擇法、交叉驗證法、網格搜索法、貝葉斯法等[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ā)展，已有學者采用上述算法來優(yōu)化選擇SVM的參數(shù)[4，7，13]。

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

1 人工蜂群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

通過使用支持向量機的分類準確率作為基礎計算適應度，則準確率越高，適應度越小。因此可以據此將BBABC和SVM相結合，算法步驟如下。

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

4 試驗分析

4.1 數(shù)據來源

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

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

4.2 對比和評價標準

4.3 結果與分析

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

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

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

5 結語

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

參考文獻：

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

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

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

[4]王鵬，郭朝勇，劉紅寧.基于支持向量機的槍彈外觀缺陷識別與分類[J].計算機工程與科學，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].無線互聯(lián)科技，2015（19）：111-112.

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

[8]古麗娜孜·艾力木江，孫鐵利，乎西旦.一種基于融合核函數(shù)支持向量機的遙感圖像分類[J].東北師大學報（自然科學版），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].計算機系統(tǒ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)學報，2014（2）：127-135.

[18]王慧穎，王文彬.基于改進搜索策略的混合蜂群算法[J].系統(tǒng)工程與電子技術，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.