基于改進(jìn)蜂群算法優(yōu)化的支持向量機(jī)研究與應(yīng)用

朱范炳， 陳 澤， 張 翔

（信陽學(xué)院大數(shù)據(jù)與人工智能學(xué)院， 河南 信陽 464000）

0 引 言

支持向量機(jī)［1］（Support Vector Machine， SVM）是一種應(yīng)用廣泛的機(jī)器學(xué)習(xí)方法，其基礎(chǔ)是Vapnik［2］創(chuàng)立的統(tǒng)計(jì)學(xué)習(xí)理論。 可以解決小樣本和非線性的實(shí)際問題，現(xiàn)已廣泛應(yīng)用于智能故障診斷［3］、圖像識(shí)別［4］、負(fù)荷預(yù)測(cè)［5］等領(lǐng)域。 在使用支持向量機(jī)進(jìn)行分類時(shí)，模型參數(shù)的選擇對(duì)分類準(zhǔn)確率影響很大。 如何選擇模型參數(shù)以優(yōu)化模型的性能是支持向量機(jī)研究領(lǐng)域的一個(gè)熱點(diǎn)問題。 目前常用的模型參數(shù)優(yōu)化方法有遺傳算法［6］、高斯函數(shù)［7］、模擬退火算法［8］、粒子群優(yōu)化算法［9］等。 在優(yōu)化過程中，上述方法都不同程度地進(jìn)入局部最優(yōu)解，導(dǎo)致分類模型的性能不能最大化。 文獻(xiàn)［10］提出了一種多維更新的人工蜂群算法，該方法很好地保持了挖掘搜索寬度和深度上的平衡，有效地避免了問題陷入局部最優(yōu)解，但求解方法采用全維搜索策略會(huì)大大增加時(shí)間成本。

基于以上分析，本文提出一種進(jìn)一步改進(jìn)人工蜂群算法的方法，通過選擇最優(yōu)的搜索方向，在保證搜索精度的同時(shí)，能夠降低算法的時(shí)間復(fù)雜度。 基于RBF 核函數(shù)，采用改進(jìn)的人工蜂群算法對(duì)支持向量機(jī)模型參數(shù)進(jìn)行優(yōu)化。 本文首先通過在標(biāo)準(zhǔn)數(shù)據(jù)集上的分類實(shí)驗(yàn)，驗(yàn)證改進(jìn)人工蜂群算法優(yōu)化支持向量機(jī)的有效性；然后通過人體活動(dòng)數(shù)據(jù)分類識(shí)別，說明所提方法的實(shí)用性；最后得出結(jié)論。

1 人工蜂群算法分析與改進(jìn)

1.1 基本人工蜂群算法

人工蜂群算法［11-12］（ Artificial Bee Colony Algorithm， ABC）是Karaboga 等學(xué)者于2005 年提出的一種仿生計(jì)算算法，主要應(yīng)用于函數(shù)極值優(yōu)化問題。 該算法模仿了蜂群的覓食行為，并將蜜蜂分為3 種不同的工作類型：采蜜蜂、觀察蜂和偵察蜂。 采蜜蜂、觀察蜂分別占蜜蜂總數(shù)的一半，一個(gè)蜜源對(duì)應(yīng)一只蜜蜂。 蜜源優(yōu)劣由適應(yīng)度值評(píng)價(jià)，一個(gè)蜜源有最大開采次數(shù)。 算法通過迭代搜索蜜源，進(jìn)行目標(biāo)問題解的尋優(yōu)，能夠以較大的概率找到全局最優(yōu)解。

人工蜂群算法的基本原理：設(shè)有N個(gè)蜜源｛x1，x2，…，xN｝，每個(gè)蜜源xi（i＝1，2，…，N） 有D個(gè)分量，即待優(yōu)化問題的解空間包含N個(gè)可行解，每個(gè)可行解是D維向量。 設(shè)定蜂群循環(huán)搜索的最大次數(shù)和每個(gè)蜜源的可重復(fù)開采次數(shù)，同一蜜源開采超過可重復(fù)開采次數(shù)則放棄該蜜源。 人工蜂群算法包括以下階段：

（1）蜂群的初始化階段：利用式（1）對(duì)任一解的任一分量進(jìn)行全局隨機(jī)初始化：

其中，xidmin和xidmax分別表示可行解空間第d維分量的上下限，rand（0，1） 為［0，1］之間的隨機(jī)數(shù)。

（2）采蜜蜂搜索階段：采蜜蜂在初始蜜源鄰域，通過式（2）搜索產(chǎn)生一個(gè)新解，作為候選蜜源進(jìn)行開采：

其中，j∈｛1，2，…，N｝，j≠i表示在N個(gè)蜜源中隨機(jī)選取一個(gè)不同于xi的蜜源，rand（- 1，1） 是在［-1，1］之間均勻分布的隨機(jī)數(shù)，決定采蜜蜂更新位置的擾動(dòng)幅度。 計(jì)算新解的適應(yīng)度fiti評(píng)價(jià)蜜源質(zhì)量，在vi和xi之中采用貪婪策略進(jìn)行選擇。

（3）觀察蜂跟隨階段：所有采蜜蜂完成搜索后，采蜜蜂會(huì)把解的信息及適應(yīng)度分享給觀察蜂。 觀察蜂通過選擇概率Pi決定每只采蜜蜂被跟隨的概率：

或者

觀察蜂通過輪盤賭策略選擇采蜜蜂跟隨。 如果采蜜蜂對(duì)應(yīng)蜜源的選擇概率值較大，則會(huì)被更多的觀察蜂跟隨，即適應(yīng)度較大的蜜源附近會(huì)有更多的觀察蜂進(jìn)行搜索，蜜源對(duì)應(yīng)解的鄰域搜索范圍更廣。若新解的適應(yīng)度比之前的好，觀察蜂將會(huì)更新解；反之，觀察蜂會(huì)將之前的解保留，同時(shí)解的迭代搜索次數(shù)會(huì)加1。

（4）偵察蜂階段：所有觀察蜂完成跟隨搜索后，如果某一蜜源在被搜索最大開采次數(shù)后仍沒有被更新，則認(rèn)為該蜜源已被開采枯竭，對(duì)應(yīng)的解陷入局部最優(yōu)。 相應(yīng)的采蜜蜂和觀察蜂則會(huì)放棄該蜜源，轉(zhuǎn)換為偵察蜂模式，按照式（1）進(jìn)行全局隨機(jī)搜索新蜜源。 這是人工蜂群算法跳出局部最優(yōu)的有效手段。 然后返回到采蜜蜂的搜索階段，3 種蜜蜂依次工作，重復(fù)循環(huán)搜索，最終找到目標(biāo)問題的最優(yōu)解。

1.2 改進(jìn)人工蜂群算法

基本人工蜂群算法中，采蜜蜂和觀察蜂隨機(jī)選擇蜜源的一個(gè)維度，按照式（2）進(jìn)行搜索。 如果在這個(gè)維度上有更好的解，但下一次迭代隨機(jī)選擇另外一個(gè)維度，這可能會(huì)導(dǎo)致無法進(jìn)一步開發(fā)當(dāng)前維度更優(yōu)的解，后因達(dá)到最大開采次數(shù)而放棄這個(gè)蜜源。 這會(huì)使算法錯(cuò)過很多尋找全局最優(yōu)解的機(jī)會(huì)，增加算法的收斂時(shí)間，也會(huì)影響最終解的精度。

為此，本文提出了一種改進(jìn)的多維搜索策略。該方法在第一次迭代時(shí)搜索蜜源的每個(gè)維度進(jìn)行貪婪選擇。 如果當(dāng)前維度選擇成功，則在保留當(dāng)前維度更新的基礎(chǔ)上，將該維度保存到外部文檔Dim中，然后進(jìn)行下一個(gè)維度的選擇。 如果選擇失敗，更新將不會(huì)被保留，外部文檔也不會(huì)存儲(chǔ)該維度。 結(jié)合上述想法，本文將式（2）中隨機(jī)更新一個(gè)維度替換為同時(shí)更新Dim中的維度，即可得到新的更新公式如下：

其中，m表示Dim中保存維度的個(gè)數(shù)。

每次搜索迭代搜索都會(huì)進(jìn)行貪婪選擇，將每個(gè)蜜源中有價(jià)值的維度存儲(chǔ)到Dim中。 在下一次迭代中，對(duì)Dim中存儲(chǔ)的維度執(zhí)行上述操作。 多次迭代后，Dim存儲(chǔ)維度的數(shù)量將減少，說明算法進(jìn)化搜索的方向更加明確，直至算法達(dá)到穩(wěn)定收斂。

2 支持向量機(jī)參數(shù)選擇

支持向量機(jī)在面對(duì)非線性分類問題時(shí)，通過高維空間變換將非線性分類問題轉(zhuǎn)化為高維空間的線性分類問題，并引入拉格朗日函數(shù)來解決不等式約束下二次函數(shù)的極值問題。 在使用支持向量機(jī)進(jìn)行數(shù)據(jù)分類之前，應(yīng)選擇核函數(shù)類型、懲罰因子C和核函數(shù)參數(shù)［13］。 本文采用RBF 徑向基函數(shù)作為核函數(shù)，以RBF 核函數(shù)中的寬度參數(shù)g和懲罰因子C為優(yōu)化目標(biāo)。 為了說明懲罰因子C和參數(shù)g對(duì)模型性能的影響，表1 和表2 給出了不同參數(shù)下數(shù)據(jù)分類準(zhǔn)確率。

表1 C＝2 分類結(jié)果隨g 值的變化Tab. 1 Change of classification results with g when C＝2

表2 g ＝2 分類結(jié)果隨C 值的變化Tab. 2 Change of classification results with C when g ＝2

懲罰因子C起到控制錯(cuò)誤子樣本懲罰的作用，從而實(shí)現(xiàn)錯(cuò)誤子樣本比例與算法復(fù)雜度之間的權(quán)衡。 當(dāng)C較小時(shí)，支持向量機(jī)對(duì)誤差的容忍度較高，模型的精度會(huì)降低，但泛化能力增強(qiáng)。 當(dāng)C較大時(shí)，模型的精度提高，但復(fù)雜度增加，泛化能力也降低。參數(shù)g決定了數(shù)據(jù)樣本在高維特征空間中的復(fù)雜度，稱為空間維數(shù)。 該維數(shù)決定在空間中可以構(gòu)造的線性分類曲面的最大維數(shù)。 維數(shù)越高，線性分類面越復(fù)雜，經(jīng)驗(yàn)風(fēng)險(xiǎn)越小，置信范圍越大，反之亦然。 從表1 和表2 可以看出，懲罰因子C和參數(shù)g對(duì)分類準(zhǔn)確率有顯著影響。 因此，為了得到性能較好的支持向量機(jī)，需要選擇合適的寬度參數(shù)g，并在確定的特征空間中尋找合適的懲罰因子C，使模型的擬合能力和泛化能力得到最佳的結(jié)合。

3 改進(jìn)人工蜂群算法優(yōu)化支持向量機(jī)參數(shù)

利用智能計(jì)算方法優(yōu)化支持向量機(jī)需要設(shè)置適應(yīng)度函數(shù)和尋優(yōu)解空間。 由于使用算法對(duì)支持向量機(jī)進(jìn)行優(yōu)化的目的是為了獲得更高的分類準(zhǔn)確率，所以本文用分類準(zhǔn)確率來設(shè)計(jì)算法的適應(yīng)度函數(shù)；由前文的分析可知，懲罰因子C和寬度參數(shù)g會(huì)對(duì)支持向量機(jī)的分類性能產(chǎn)生很大的影響。 因此，設(shè)定懲罰因子C和寬度參數(shù)g為優(yōu)化參數(shù)。

為了驗(yàn)證本文改進(jìn)的人工蜂群算法的有效性和優(yōu)越性，使用UCI 標(biāo)準(zhǔn)數(shù)據(jù)集中3 組數(shù)據(jù)集進(jìn)行支持向量機(jī)的訓(xùn)練和測(cè)試驗(yàn)證。 使用的數(shù)據(jù)集名稱、樣本規(guī)模、維度信息，見表3。 本文設(shè)計(jì)了不同改進(jìn)方法的人工蜂群算法優(yōu)化支持向量機(jī)的縱向比較實(shí)驗(yàn)和不同算法優(yōu)化支持向量機(jī)的橫向比較實(shí)驗(yàn)。

表3 UCI 測(cè)試數(shù)據(jù)集信息Tab. 3 The information of UCI test data sets

3.1 不同方法改進(jìn)蜂群算法優(yōu)化支持向量機(jī)參數(shù)

分別采用本文改進(jìn)的人工蜂群算法（IABC）、文獻(xiàn)［10］提出的多維更新的人工蜂群算法（MABC）和基本人工蜂群算法（ABC）對(duì)支持向量機(jī)模型參數(shù)進(jìn)行優(yōu)化。 實(shí)驗(yàn)結(jié)果由10 次實(shí)驗(yàn)計(jì)算平均值所得。表4 記錄不同人工蜂群算法優(yōu)化的支持向量機(jī)在不同數(shù)據(jù)集下的分類準(zhǔn)確率，表5 記錄對(duì)應(yīng)算法的運(yùn)行時(shí)間。 由結(jié)果數(shù)據(jù)可以看出，本文改進(jìn)人工蜂群算法優(yōu)化的支持向量機(jī)在保證分類準(zhǔn)確率的同時(shí)，能夠有效降低算法收斂時(shí)間。

表4 改進(jìn)蜂群算法優(yōu)化支持向量機(jī)分類準(zhǔn)確率Tab. 4 Classification accuracy of SVM optimized by IABC %

表5 改進(jìn)蜂群算法優(yōu)化支持向量機(jī)運(yùn)行時(shí)間Tab. 5 Running time of SVM optimized by IABCs

3.2 不同算法優(yōu)化支持向量機(jī)參數(shù)

為了進(jìn)一步驗(yàn)證改進(jìn)算法的性能，利用IABC算法與網(wǎng)格搜索算法（GS）、遺傳算法（GA）和粒子群算法（PSO）優(yōu)化支持向量機(jī)的參數(shù)。 分別進(jìn)行10 次實(shí)驗(yàn)計(jì)算結(jié)果平均值。 表6 記錄的是4 種算法在不同數(shù)據(jù)集下的分類準(zhǔn)確率。 由結(jié)果數(shù)據(jù)可以看出，對(duì)于不同樣本規(guī)模和維度的數(shù)據(jù)集，IABC 優(yōu)化的SVM 模型都比其他算法具有更高的分類準(zhǔn)確率。 因此，采用IABC 優(yōu)化的SVM 模型將局部最優(yōu)解的搜索與全局最優(yōu)解的搜索結(jié)合起來，具有較好的收斂性。

表6 不同算法優(yōu)化支持向量機(jī)分類準(zhǔn)確率Tab. 6 Classification accuracy of SVM optimized by different algorithms%

4 實(shí)例分析

4.1 實(shí)驗(yàn)方案設(shè)計(jì)

應(yīng)用改進(jìn)蜂群算法優(yōu)化的支持向量機(jī)對(duì)人體活動(dòng)的實(shí)測(cè)數(shù)據(jù)進(jìn)行分類，驗(yàn)證改進(jìn)算法的實(shí)用性。數(shù)據(jù)采集過程中參與者需佩戴帶有加速度、溫度和高度傳感器的智能手表。 從加速度傳感器采集的數(shù)據(jù)包括X，Y和Z方向的加速度。 溫度和高度傳感器的數(shù)據(jù)包括參與者的體表溫度和佩戴手表距地面的距離。 采樣頻率設(shè)置為52 Hz，采集7 種不同的人體活動(dòng)數(shù)據(jù)，數(shù)據(jù)的詳細(xì)內(nèi)容見表7。

表7 人體活動(dòng)數(shù)據(jù)信息Tab. 7 Activity data information

4.2 實(shí)驗(yàn)與結(jié)果分析

在采集的人體活動(dòng)數(shù)據(jù)中每類抽取100 組樣本，共計(jì)700 組；在支持向量機(jī)訓(xùn)練和測(cè)試中，隨機(jī)抽取490 個(gè)樣本作為訓(xùn)練集，其余210 個(gè)樣本作為測(cè)試集。 本文主要運(yùn)用ABC 和IABC 算法對(duì)SVM模型參數(shù)進(jìn)行優(yōu)化，從而進(jìn)行人體活動(dòng)識(shí)別。 實(shí)驗(yàn)中設(shè)置蜂群算法的種群規(guī)模為20，最大迭代次數(shù)為500。 ABC 和IABC 算法優(yōu)化的SVM 模型分類準(zhǔn)確率的迭代變化曲線分別如圖1 和圖2 所示。

圖1 ABC-SVM 分類準(zhǔn)確率變化曲線Fig. 1 Classification accuracy curve of ABC-SVM

圖2 IABC-SVM 分類準(zhǔn)確率變化曲線Fig. 2 Classification accuracy curve of IABC-SVM

由圖1 和圖2 可見，在算法迭代次數(shù)均為500的情況下，ABC 算法優(yōu)化的SVM 模型（ABC-SVM）分類準(zhǔn)確率收斂速度快，最高可達(dá)84.31%；IABC 算法優(yōu)化的SVM 模型（IABC-SVM）分類準(zhǔn)確率收斂速度較ABC-SVM 慢，但分類準(zhǔn)確率最高可達(dá)85.73%，有顯著提高。 對(duì)上述實(shí)驗(yàn)數(shù)據(jù)分別采用SVM、ABC-SVM、IABC-SVM 進(jìn)行10 次分類實(shí)驗(yàn)，計(jì)算分類準(zhǔn)確率平均值記錄于表8 中。

表8 不同算法模型的分類準(zhǔn)確率Tab. 8 Classification accuracy under different algorithms

5 結(jié)束語

支持向量機(jī)模型參數(shù)是影響分類精度的重要因素。 針對(duì)目前支持向量機(jī)訓(xùn)練算法計(jì)算量大、運(yùn)行時(shí)間長(zhǎng)、分類準(zhǔn)確率待提高的問題，本文提出了一種改進(jìn)的人工蜂群算法對(duì)支持向量機(jī)參數(shù)優(yōu)化的方法。 通過標(biāo)準(zhǔn)數(shù)據(jù)集的實(shí)驗(yàn)表明，改進(jìn)的人工蜂群算法優(yōu)化的支持向量機(jī)模型提高了分類準(zhǔn)確率，降低了算法收斂時(shí)間。 將該方法應(yīng)用于實(shí)測(cè)的人體活動(dòng)數(shù)據(jù)分類，獲得了良好的分類精度，說明改進(jìn)人工蜂群算法優(yōu)化的支持向量機(jī)具有較好的實(shí)際應(yīng)用價(jià)值。