采用粒子群優(yōu)化的SVM算法在數(shù)據(jù)分類中的應(yīng)用

鄒心遙， 陳敬偉， 姚若河

(1. 廣東農(nóng)工商職業(yè)技術(shù)學(xué)院 機(jī)電系， 廣東 廣州 510507；

2. 華南理工大學(xué) 電子與信息學(xué)院， 廣東 廣州 510641)

?

采用粒子群優(yōu)化的SVM算法在數(shù)據(jù)分類中的應(yīng)用

鄒心遙1， 陳敬偉1， 姚若河2

(1. 廣東農(nóng)工商職業(yè)技術(shù)學(xué)院 機(jī)電系， 廣東 廣州 510507；

2. 華南理工大學(xué) 電子與信息學(xué)院， 廣東 廣州 510641)

摘要：針對分類數(shù)據(jù)集合線性不可分的問題，改進(jìn)了支持向量機(jī)(SVM)的分類方法，構(gòu)建新的分類決策函數(shù)和高斯核函數(shù).在支持向量機(jī)關(guān)鍵參數(shù)的優(yōu)化環(huán)節(jié)，采用粒子群算法對懲罰參數(shù)和高斯參數(shù)進(jìn)行優(yōu)化，設(shè)計(jì)便于操作的優(yōu)化流程，并針對Iris數(shù)據(jù)集合展開實(shí)驗(yàn)研究.結(jié)果表明：相比于基于遺傳算法優(yōu)化的SVM方法，所提出的方法執(zhí)行速度快、分類準(zhǔn)確率高.

關(guān)鍵詞：數(shù)據(jù)分類； 支持向量機(jī)； 粒子群優(yōu)化； Iris數(shù)據(jù)集； 懲罰參數(shù)； 高斯參數(shù)

數(shù)據(jù)分類作為數(shù)據(jù)庫管理系統(tǒng)的核心技術(shù)，已經(jīng)成為國內(nèi)外學(xué)者廣泛關(guān)注的焦點(diǎn)研究[1].通過數(shù)據(jù)分類，可以將數(shù)據(jù)庫中的各項(xiàng)數(shù)據(jù)分門別類，分類后的數(shù)據(jù)將具有明顯的內(nèi)在聯(lián)系或意義近似性，更利于數(shù)據(jù)管理與維護(hù),尤其是縮小數(shù)據(jù)查找的范圍[2].已經(jīng)成功用于數(shù)據(jù)分類的方法很多，如鄰近算法、貝葉斯算法、決策樹算法、神經(jīng)網(wǎng)絡(luò)算法等[3-5].Agarwal等[6]在Fisher核函數(shù)的基礎(chǔ)上進(jìn)行改進(jìn)，形成一種含有概率特征的離散化形式，對數(shù)字?jǐn)?shù)據(jù)挖掘具有較強(qiáng)的針對性.Durduran[7]構(gòu)建一個新的核函數(shù)空間，并設(shè)計(jì)在全空間上進(jìn)行搜索的分類策略.李婷等[8]以車載激光點(diǎn)云數(shù)據(jù)為分類對象，借助混合核函數(shù)的理念，對傳統(tǒng)的高斯核函數(shù)進(jìn)行修正，建立一種新的支持向量機(jī)(SVM)分類方法.陸慧娟等[9]面向基因表達(dá)數(shù)據(jù)，針對局部分類采用徑向基函數(shù)(RBF)核函數(shù)，針對全局分類采用線性核函數(shù).支持向量機(jī)方法的關(guān)鍵在于如何對關(guān)鍵參數(shù)優(yōu)化，如果能用智能算法實(shí)現(xiàn)這些參數(shù)的優(yōu)化,并獲得最優(yōu)結(jié)果，就可以獲得更高性能的SVM分類結(jié)果[10].本文選擇支持向量機(jī)的方法作為數(shù)據(jù)分類的研究對象，并在參數(shù)優(yōu)化環(huán)節(jié)中選取粒子群(PSO)算法，構(gòu)建出一種新的數(shù)據(jù)分類方法.

1支持向量機(jī)分類方法

在線性可分的情況下，支持向量機(jī)分類方法通過在高維空間構(gòu)造最優(yōu)分類超平面，以最低的結(jié)構(gòu)風(fēng)險(xiǎn)進(jìn)行分類，具有學(xué)習(xí)能力強(qiáng)、訓(xùn)練速度快、分類精度高等諸多優(yōu)點(diǎn).然而，很多分類問題中的數(shù)據(jù)集合并不是線性可分的.此時，數(shù)據(jù)分類過程中的優(yōu)化問題需要的數(shù)學(xué)模型定義為

(1)

式(1)中:(pi，qi)為第i個訓(xùn)練樣本，i=1，2，…n；v∈Rd為SVM分類中超平面的法向向量；z∈R為閾值；ρ為懲罰參數(shù)，其值越大表示對不正確分類結(jié)果的懲罰程度越大，但過大的ρ值會降低SVM方

法的泛化能力，所以ρ的選取要在分類精度和泛化能力之間尋求平衡.

式(1)是一個典型的二次規(guī)劃問題，對此問題的求解可以采用拉格朗日乘子算法，即

(2)

式(2)中:θi，?i都是不小于0的拉格朗日乘子.

針對式(2)，分別對變量v，z，ηi求偏導(dǎo)，并讓3個偏導(dǎo)值為0，將此時求得的結(jié)果代入式(1)，可得

(3)

對于式(3)，能夠滿足θi≤ρ的情況稱為支持向量.據(jù)此，最終可以得到用于分類的決策函數(shù)為

(4)

要判斷任意一個樣本數(shù)據(jù)的類別情況，只要將其代入式(4)進(jìn)行計(jì)算即可.

核函數(shù)是構(gòu)造SVM分類方法的另一個關(guān)鍵問題.因?yàn)榭疾斓氖且话惴诸惽闆r，所以選取高斯核函數(shù)作為文中SVM分類方法的核函數(shù)，其簡化形式為

(5)

式(5)中:參數(shù)κ=1/σ2，σ稱為高斯核函數(shù)的高斯系數(shù).

2SVM分類中的粒子群參數(shù)優(yōu)化

要提升SVM分類方法的精度和效率，對關(guān)鍵參數(shù)的設(shè)置和優(yōu)化至關(guān)重要[11].因此，采用粒子群算法對2個關(guān)鍵參數(shù)進(jìn)行優(yōu)化調(diào)整，以達(dá)到最佳的分類效果[12].粒子群算法在執(zhí)行過程上類似于遺傳算法，也需要對粒子群進(jìn)行初始化，并根據(jù)適應(yīng)度函數(shù)進(jìn)行優(yōu)化操作.相比于遺傳算法，粒子群算法的實(shí)現(xiàn)更為簡單，一方面,粒子群算法無需執(zhí)行交叉和變異操作，另一方面,粒子群算法需要調(diào)整的參數(shù)沒有遺傳算法多.基于這些情況，粒子群算法可以以更快的速度達(dá)到收斂、獲得最優(yōu)解[13-15].

粒子群算法的基本實(shí)現(xiàn)過程如下.

在一個維度為m的待查找空間上，假設(shè)粒子群的初始狀態(tài)為S=(s1，s2，…，sn)，si代表優(yōu)化問題的第i個解，它在待查找空間上的多維表示為si=(si，1，si，2，…，si，m).若各個粒子的速度為Vi=(v1，v2，…，vm)T，群內(nèi)的粒子個體位置最優(yōu)解為Li=(li，1，li，2，…，li，m)T，能使種群整體達(dá)到最優(yōu)狀態(tài)的解為Lg=(lg，1，lg，2，…，lg，m)T，找到當(dāng)前狀態(tài)下的Li和Lg以后，需要對群內(nèi)的粒子進(jìn)行位置更新和速度更新，其處理過程為

(6)

(7)

式(6)，(7)中:G為粒子飛行過程中的慣性權(quán)重；a1，a2為加速度參數(shù)；r1，r2為隨機(jī)數(shù).

對于文中SVM分類方法，要優(yōu)化的參數(shù)主要有懲罰參數(shù)ρ和κ=1/σ2.根據(jù)粒子群優(yōu)化方法的執(zhí)行過程，為這2個參數(shù)的優(yōu)化設(shè)置了6個優(yōu)化步驟.

步驟1用(σ，κ)構(gòu)建每一個粒子的初始狀態(tài)，并完成種群內(nèi)全部n個粒子的位置初始化和速度初始化，同時設(shè)定2個加速度參數(shù)a1，a2的數(shù)值為2，以及最大迭代次數(shù)T.

步驟2根據(jù)當(dāng)前的各個粒子狀態(tài)，計(jì)算適應(yīng)度，并以SVM分類正確的比率作為評價(jià)各個粒子適應(yīng)度高低的依據(jù).

步驟3比較每一個粒子的適應(yīng)度和其出現(xiàn)過的最優(yōu)狀態(tài)，選出Li并更新最優(yōu)狀態(tài)，以便于下一次迭代過程的比較.

步驟4比較各個粒子的適應(yīng)度和整個種群出現(xiàn)過的最優(yōu)狀態(tài)，選出Lg并更新最優(yōu)狀態(tài)，以便于下一次迭代過程的比較.

步驟5根據(jù)式(6)，(7)更新粒子的位置和速度.

步驟6不斷重復(fù)從步驟2到步驟5的工作，直到迭代過程達(dá)到最大迭代次數(shù)T，此時的Lg下各個粒子的狀態(tài)，就是最終優(yōu)化的結(jié)果.

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

在分類方法的驗(yàn)證性實(shí)驗(yàn)中，選取數(shù)據(jù)分類領(lǐng)域中常用的標(biāo)準(zhǔn)測試數(shù)據(jù)集合Iris.該數(shù)據(jù)集合是根據(jù)鳶尾花這種植物的外形特征構(gòu)建數(shù)據(jù)集合，包含3個種類的鳶尾花，分別是山鳶尾花(Irissetosa)、雜色鳶尾花(Irisversicolour)、維吉尼亞鳶尾花(Irisvirginica).Iris數(shù)據(jù)集合從鳶尾花的花萼長度特征、花萼寬度特征、花瓣長度特征和花瓣寬度特征等4個方面對上述3種鳶尾花進(jìn)行特征區(qū)分.整個數(shù)據(jù)集合內(nèi)共含有50個樣本數(shù)據(jù)，有標(biāo)準(zhǔn)的正確分類作為分類方法分類結(jié)果測試的判斷依據(jù).

在分類性能測試過程中，采用了常見的交叉驗(yàn)證手段.即將Iris數(shù)據(jù)集合隨機(jī)分作J個子集合，先用1到(J-1)和子集對分類方法進(jìn)行訓(xùn)練，確定分類決策模型后，對第J個子集進(jìn)行分類以考察分類模型的正確性；然后，用第2到J個子集對分類方法進(jìn)行訓(xùn)練，確定分類決策模型后，對第1個子集進(jìn)行分類以考察分類模型的正確性；以此類推，遍歷所有可能的交叉驗(yàn)證.

在分類方法的參數(shù)設(shè)置上，設(shè)定初始種群的規(guī)模是20個粒子，設(shè)定加速度參數(shù)a1，a2為2，粒子飛行過程中的慣性權(quán)重G為1，設(shè)定最大迭代次數(shù)T為100.對于交叉子集J的設(shè)定則分別設(shè)置為3，5，7，9這4種情況.同時，選擇遺傳算法優(yōu)化的SVM分類方法(簡稱SVM-GA)，作為提出的粒子群算法優(yōu)化的SVM分類方法(簡稱SVM-PSO)的對比方法.兩種方法的分類準(zhǔn)確率和執(zhí)行時間的對比結(jié)果，如表1所示.表1中：η為分類準(zhǔn)確率；t為執(zhí)行時間.

由表1可知：所提出的基于粒子群優(yōu)化的SVM分類方法的分類準(zhǔn)確率明顯優(yōu)于基于遺傳算法的SVM分類方法.隨著交叉驗(yàn)證的分類子集數(shù)目增多，文中方法的分類準(zhǔn)確率一直保持在90%以上.由表1還可知：所提出的基于粒子群優(yōu)化的SVM分類方法的執(zhí)行時間明顯低于基于遺傳算法的SVM分類方法；隨著交叉驗(yàn)證的分類子集數(shù)目增多，基于遺傳算法的SVM分類方法的執(zhí)行時間增加較為明顯，而文中方法的執(zhí)行時間增加幅度則不大.

表1　不同分類方法準(zhǔn)確率和執(zhí)行時間對比數(shù)據(jù)

4結(jié)束語

在考察數(shù)據(jù)集合線性不可分的情況下，設(shè)計(jì)SVM方法的分類決策函數(shù)和高斯核函數(shù).為了進(jìn)一步提升SVM方法的分類性能，采用粒子群算法對SVM方法的2個重要參數(shù)進(jìn)行優(yōu)化，包括對懲罰參數(shù)的優(yōu)化和高斯系數(shù)的優(yōu)化.以Iris為分類實(shí)驗(yàn)的測試數(shù)據(jù)集，并選擇基于遺傳算法優(yōu)化的SVM方法作為比較方法.數(shù)據(jù)分類的驗(yàn)證實(shí)驗(yàn)表明，所提出的基于粒子群算法優(yōu)化的SVM分類方法，具有更高的分類準(zhǔn)確性和更快的分類速度.

參考文獻(xiàn)：

[1]PALACIOS A，MARTINEZ A，SANCHEZ L.Sequential pattern mining applied to aeroengine condition monitoring with uncertain health data[J].Engineering Applications of Artifical Intelligence，2015(44):10-24.

[2]范士俊，張愛武，胡少興，等.基于隨機(jī)森林的機(jī)載激光全波形點(diǎn)云數(shù)據(jù)分類方法[J].中國激光，2013，40(9):1-7.

[3]劉紅巖，陳劍，陳國青.數(shù)據(jù)挖掘中的數(shù)據(jù)分類算法綜述[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2002，42(6):727-730.

[4]楊帆，林琛，周奇鳳，等.基于隨機(jī)森林的潛在k鄰近算法及其在基因表達(dá)數(shù)據(jù)分類中的應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐，2012，32(4):815-825.

[5]TABKHI S，NAJAFI A，RANJBAR R.Gene selection for microarray data classification using a novel ant colony optimization[J].Neurocomputing，2015,168:1024-1036.

[6]AGARWAL S K，SHAH S，KUMAR R.Classification of mental tasks from EEG data using backtracking search optimization based neural classifier[J].Neurocomputing，2015，166:397-403.

[7]DURDURAN S S.Automatic classification of high resolution land cover using a new data weighting procedure: The combination of K-means clustering algorithm and central tendency measures (KMC-CTM)[J].Applied Soft Computing，2015，35:136-150.

[8]李婷，詹慶明，喻亮.基于地物特征提取的車載激光點(diǎn)云數(shù)據(jù)分類方法[J].國土資源遙感，2012，92(1):17-21.

[9]陸慧娟，安春霖，馬小平，等.基于輸出不一致測度的極限學(xué)習(xí)機(jī)集成的基因表達(dá)數(shù)據(jù)分類[J].計(jì)算機(jī)學(xué)報(bào)，2013，36(2):341-348.

[10]ELYASIGOMARI V，MIRJAFARI M S，SCREEN H R C.Cancer classification using a novel gene selection approach by means of shuffling based on data clustering with optimization[J].Applied Soft Computing，2015，35:43-51.

[11]喻小光，陳維斌，陳榮鑫.一種數(shù)據(jù)規(guī)約的近似挖掘方法的實(shí)現(xiàn)[J].華僑大學(xué)學(xué)報(bào)(自然科學(xué)版)，2008，29(3):370-374.

[12]王江海，武林仙，吳揚(yáng)揚(yáng).基于刻畫得數(shù)據(jù)空間數(shù)據(jù)源管理子系統(tǒng)[J].華僑大學(xué)學(xué)報(bào)(自然科學(xué)版)，2012，33(5):509-513.

[13]彭京,唐常杰,元昌安,等.一種基于概念相似度的數(shù)據(jù)分類方法[J].軟件學(xué)報(bào)，2007,18(2):311-322.

[14]楊帆,林琛,周綺鳳.基于隨機(jī)森林的潛在k近鄰算法及其在基因表達(dá)數(shù)據(jù)分類中的應(yīng)用[J].系統(tǒng)工程理論與實(shí)踐,2012,32(4):815-826.

[15]陸慧娟,安春霖,馬小平，等.基于輸出不一致測度的極限學(xué)習(xí)機(jī)集成的基因表達(dá)數(shù)據(jù)分類[J].計(jì)算機(jī)學(xué)報(bào),2013,36(2):341-348.

(責(zé)任編輯： 錢筠 英文審校： 吳逢鐵)

Application of SVM Algorithm Based on Particle Swarm Optimization in Data Classification

ZOU Xinyao1， CHEN Jingwei1， YAO Ruohe2

(1. Department of Mechanical and Electronic， Guangdong AIB Polytechnic College， Guangzhou 510507, China；2. School of Electronic and Information Engineering， South China University of Technology， Guangzhou 510641, China)

Abstract：According to the problem that the classification data set can not be divided, the classification method of support vector machine (SVM) is improved, and the new classification decision function and Gauss kernel function are constructed. Using particle swarm algorithm to optimize the penalty parameters and Gauss parameters, the optimization process is easy to operate. To experimental study the Iris data set, the results show that compared with the SVM method based on genetic algorithm, the proposed method performs fast and has high classification accuracy.

Keywords：data classification； support vector machine； particle swarm optimization； Iris data set; penalty parameter; Gauss parameter

中圖分類號：TP 181

文獻(xiàn)標(biāo)志碼：A

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(61274085)； 廣東省大學(xué)生科技創(chuàng)新培育專項(xiàng)(PDJH2015A0718)

通信作者：鄒心遙(1978-)，女，副教授，博士，主要從事新型光電器件、物聯(lián)網(wǎng)技術(shù)的研究.E-mail:madelinexy@163.com.

收稿日期：2015-12-22

doi:10.11830/ISSN.1000-5013.2016.02.0171

文章編號：1000-5013(2016)02-0171-04