高雷阜,趙世杰,高 晶
遼寧工程技術(shù)大學(xué) 理學(xué)院,遼寧 阜新 123000
人工魚群算法在SVM參數(shù)優(yōu)化選擇中的應(yīng)用
高雷阜,趙世杰,高 晶
遼寧工程技術(shù)大學(xué) 理學(xué)院,遼寧 阜新 123000
20世紀(jì)70年代,Vapnik等人提出的統(tǒng)計(jì)學(xué)習(xí)理論[1]是一種研究有限樣本情況下機(jī)器學(xué)習(xí)規(guī)律的理論,而支持向量機(jī)正是以該理論為基礎(chǔ)發(fā)展起來的,在解決小樣本、非線性及高維數(shù)據(jù)的模式識(shí)別問題中表現(xiàn)出許多特有的優(yōu)勢(shì),克服了過學(xué)習(xí)、欠學(xué)習(xí)和“維數(shù)災(zāi)難”等問題,并能夠較好地推廣應(yīng)用到其他機(jī)器學(xué)習(xí)問題中。作為新興學(xué)習(xí)機(jī)器,支持向量機(jī)仍存在許多有待完善的地方。
支持向量機(jī)的改進(jìn)研究主要集中在核函數(shù)、核矩陣的構(gòu)造[2];核參數(shù)的優(yōu)化選擇和核函數(shù)的性質(zhì)[3]的研究等方面,而對(duì)于核參數(shù)的選擇到目前為止也沒有一套完整的理論,但參數(shù)的選擇卻直接影響著支持向量機(jī)的分類精度和泛化性能等。傳統(tǒng)的參數(shù)選擇方法主要是通過反復(fù)實(shí)驗(yàn)參數(shù)的方法,人工選取出較好的參數(shù),這必然導(dǎo)致較高的時(shí)間代價(jià),并且得到的可能不是最優(yōu)的參數(shù)。
對(duì)于參數(shù)的優(yōu)化選擇一直是支持向量機(jī)的一個(gè)研究熱點(diǎn),研究方法有基于樣本數(shù)據(jù)分析或?qū)嶒?yàn)設(shè)計(jì)的[4-6]、基于仿生智能算法用于支持向量機(jī)參數(shù)優(yōu)化選擇的:有進(jìn)化算法[7-10]、粒子群算法[11-13]、蟻群算法[14-15]以及多種智能算法相融合用于參數(shù)優(yōu)化的方法[16]等。
而人工魚群算法[17-19]同樣作為一種新興的仿生智能算法,具有較強(qiáng)的并行處理能力,尋優(yōu)速度快;對(duì)初始值不敏感,具備全局尋優(yōu)能力等優(yōu)點(diǎn)。本文將人工魚群算法應(yīng)用于支持向量機(jī)的參數(shù)優(yōu)化選擇中,利用人工魚群的并行性能夠更快地收斂于全局極值點(diǎn),并以分類準(zhǔn)確率最大化作為優(yōu)化原則建立目標(biāo)函數(shù),實(shí)現(xiàn)對(duì)支持向量機(jī)的核參數(shù)和罰參數(shù)進(jìn)行優(yōu)化選取,以增強(qiáng)支持向量機(jī)對(duì)數(shù)據(jù)的分類準(zhǔn)確率和對(duì)參數(shù)的尋優(yōu)收斂速度。
支持向量機(jī)[20]就是將待分類問題的輸入變量樣本,通過構(gòu)造最優(yōu)分割超平面,使位于超平面一側(cè)的為一類;超平面另一側(cè)的為另一類,從而實(shí)現(xiàn)樣本的分類問題。
對(duì)于線性不可分的情況,可以通過非線性映射將低維空間映射到高維特征空間(一般為Hilbert空間)中,使其在該高維空間中線性可分。雖然在低維空間是線性不可分的,但總可找到適合的核函數(shù)K(xi,xj),將數(shù)據(jù)由低維空間映射到高維空間使其線性可分。常見的SVM核函數(shù)主要有多項(xiàng)式核函數(shù)、高斯核函數(shù)(RBF核函數(shù))、Sigmoid核函數(shù),同時(shí)也可以根據(jù)具體問題構(gòu)造相應(yīng)的核函數(shù)。
線性不可分問題的Lagrange對(duì)偶函數(shù)為:
核函數(shù)選擇也是影響支持向量機(jī)性能的一個(gè)重要影響因素,而高斯核函數(shù)具有較好的適應(yīng)性,無論對(duì)于低維空間數(shù)據(jù)還是高維空間都具有較好的收斂域,是較為理想的核函數(shù),因此選取高斯核函數(shù)作為SVM的分類預(yù)測(cè)核函數(shù),故高斯核函數(shù)支持向量機(jī)分類性能的影響參數(shù)主要有罰參數(shù)C和高斯核函數(shù)σ需要進(jìn)行優(yōu)化。
人工魚群算法通過多條人工魚同時(shí)進(jìn)行尋優(yōu),從中選取最優(yōu)值作為此次優(yōu)化的結(jié)果實(shí)現(xiàn)了并行操作,從而使人工魚群算法能夠快速收斂到最優(yōu)值附近,而且對(duì)給定的初始值不敏感,具備全局尋優(yōu)能力,因此將其應(yīng)用于支持向量機(jī)參數(shù)的優(yōu)化選擇中,優(yōu)化目標(biāo)是確定最優(yōu)的參數(shù)組合(C,σ)使SVM的分類準(zhǔn)確率達(dá)到最大化?;谌斯~群算法的SVM參數(shù)優(yōu)化選擇步驟為:
步驟1參數(shù)設(shè)置。人工魚群算法參數(shù)設(shè)置,主要包括人工魚群的種群規(guī)模 Fish_num、魚群最大迭代次數(shù)Max_gen、覓食最大試探次數(shù)Try_num、感知距離Visual、移動(dòng)步長Step_leg和魚群擁擠度因子δ;支持向量機(jī)相關(guān)參數(shù)上下限取值設(shè)置,包括SVM罰參數(shù)C和高斯核函數(shù)參數(shù)σ。
步驟2初始化人工魚。每條人工魚為SVM待優(yōu)化參數(shù)組合(C,σ),第一行為罰參數(shù)C的取值,第二行為核參數(shù)σ的取值;根據(jù)步驟1中罰參數(shù)C和核參數(shù)σ的取值范圍隨機(jī)初始化人工魚,整個(gè)魚群是一個(gè)2×Fish_num的矩陣,每次行為操作都使Fish_num條人工魚并行尋優(yōu),提高了尋優(yōu)性能。
步驟3設(shè)置支持向量機(jī)相應(yīng)數(shù)據(jù)集,主要包括訓(xùn)練數(shù)據(jù)集Train_data、訓(xùn)練數(shù)據(jù)集標(biāo)簽Train_label、目標(biāo)數(shù)據(jù)集T_data和目標(biāo)標(biāo)簽數(shù)據(jù)集T_num。
步驟4計(jì)算初始魚群的食物濃度值。選取高斯核函數(shù)作為支持向量機(jī)的核函數(shù),根據(jù)訓(xùn)練集Train_data和訓(xùn)練集標(biāo)簽Train_label訓(xùn)練支持向量機(jī)模型,并將該模型用于目標(biāo)集T_data和目標(biāo)標(biāo)簽集T_num的分類預(yù)測(cè)中,將支持向量機(jī)的分類準(zhǔn)確率作為各人工魚的食物濃度值并比較大小,將最大者作為當(dāng)前魚群的最優(yōu)值,并保存當(dāng)前最優(yōu)值所對(duì)應(yīng)的人工魚的參數(shù)組合(C,σ)。
步驟5對(duì)魚群中各人工魚的行為操作。各人工魚分別模擬覓食行為、追尾行為和聚群行為,并按食物濃度值最大的行為執(zhí)行,缺失行為為隨機(jī)行為,按照人工魚的感知距離Visual和移動(dòng)步長Step_leg進(jìn)行隨機(jī)游走。
步驟6最優(yōu)食物濃度值的選擇。魚群每進(jìn)行一次行為操作,便計(jì)算一次當(dāng)前魚群的最大食物濃度值:如果有一條人工魚的食物濃度值大于已保存的食物濃度值,則用當(dāng)前的食物濃度值替代原保存的最優(yōu)食物濃度值,并保存該最優(yōu)值所對(duì)應(yīng)的人工魚的參數(shù)組合(C,σ),否則仍保存原食物濃度值和最優(yōu)值所對(duì)應(yīng)的人工魚的參數(shù)組合(C,σ)。
步驟7判斷是否滿足算法的終止條件:判斷是否達(dá)到預(yù)設(shè)的魚群最大迭代次數(shù)Max_gen,若是則輸出魚群的最大食物濃度值和最優(yōu)值所對(duì)應(yīng)的人工魚的參數(shù)組合(C,σ),否則迭代次數(shù)加1,并跳轉(zhuǎn)執(zhí)行步驟5。
基于人工魚群算法的SVM參數(shù)優(yōu)化選擇的流程圖見圖1。
為了驗(yàn)證基于人工魚群算法對(duì)支持向量機(jī)參數(shù)優(yōu)化的性能,本文利用支持向量機(jī)的交叉檢驗(yàn)法和基于遺傳算法、基于粒子群算法和基于蟻群算法的SVM參數(shù)尋優(yōu)法作為對(duì)比實(shí)驗(yàn),來說明該方法在SVM參數(shù)優(yōu)化選擇中是有效的和可行的。
圖1 基于人工魚群算法優(yōu)化SVM參數(shù)流程圖
4.1 實(shí)驗(yàn)數(shù)據(jù)
實(shí)驗(yàn)數(shù)據(jù)選自UCI標(biāo)準(zhǔn)數(shù)據(jù)庫中的Statlog、liver-disorders(簡記LD)、seeds、Iris、glass、wine、Image-Segmentation(簡記IS)和Hayes-Roth(簡記HR)共8個(gè)數(shù)據(jù)集,各數(shù)據(jù)集的具體屬性等情況見表1。
表1 數(shù)據(jù)集的屬性
訓(xùn)練數(shù)據(jù)集是采用隨機(jī)選取的方式,其具體操作是按照原始數(shù)據(jù)集Orig_Data的大小數(shù)目N,將整數(shù)數(shù)集{1,2,…,N}的 N個(gè)整數(shù)進(jìn)行隨機(jī)排列,然后根據(jù)所需訓(xùn)練數(shù)據(jù)集Train_Data的數(shù)目n選取隨機(jī)排列的前n個(gè)位置的隨機(jī)排列,并以此n個(gè)排列順序依次從原始數(shù)據(jù)集Orig_Data中選取出相應(yīng)位置的樣本放入訓(xùn)練數(shù)據(jù)集Train_Data中,最終得到由n個(gè)樣本組成的訓(xùn)練數(shù)據(jù)集Train_Data;同時(shí)對(duì)于各樣本數(shù)目均等的數(shù)據(jù)集可以采用均勻隨機(jī)選取,即對(duì)各數(shù)據(jù)集按各類別比例從各類中選取出滿足比例關(guān)系的樣本組成訓(xùn)練數(shù)據(jù)集。8個(gè)數(shù)據(jù)集的訓(xùn)練數(shù)據(jù)集選取情況見表2。
4.2 實(shí)驗(yàn)參數(shù)設(shè)置
支持向量機(jī)的交叉驗(yàn)證法的罰參數(shù)C的取值范圍設(shè)置為 [0,10],步長設(shè)置為0.1;高斯核函數(shù)相關(guān)參數(shù) γ的取值范圍設(shè)置為[0,1],步長為0.01。仿生智能算法中遺傳算法、粒子群算法、蟻群算法和人工魚群算法中種群進(jìn)化代數(shù)Max_gen為50,種群規(guī)模Size_pop為5(以與人工魚群算法相比較驗(yàn)證其較好效果),罰參數(shù)C的取值范圍為(0,10],核函數(shù)相關(guān)參數(shù) γ的取值范圍為(0,1],另外GA算法的其他參數(shù)設(shè)置為:交叉概率P_cross為0.8,變異概率P_mutation為0.008;粒子群算法其他參數(shù)設(shè)置為:速度最大值為Vmax為0.5,速度最小值為Vmin為-0.5,速度更新參數(shù)α和β分別為1.494 45和0.494 45;蟻群算法其他參數(shù)設(shè)置為:信息素?fù)]發(fā)系數(shù)Rho為0.8,信息素增加強(qiáng)度Q為0.9,螞蟻爬行速度V為0.3;人工魚群算法其他參數(shù)設(shè)置為:人工魚最大試探次數(shù)Try_num為5,魚群擁擠度因子δ為0.618,人工魚的感知距離Visual為0.5和移動(dòng)步長Step_leg為0.1。
表2 各數(shù)據(jù)集的訓(xùn)練數(shù)據(jù)集選取情況
4.3 實(shí)驗(yàn)結(jié)果
利用Statlog、liver-disorders、seeds、Iris、glass、wine、Image-Segmentation和Hayes-Roth共8個(gè)數(shù)據(jù)集,分別通過SVM交叉驗(yàn)證法、基于遺傳算法的SVM參數(shù)尋優(yōu)法(GA-SAM)、基于粒子群算法的SVM參數(shù)尋優(yōu)法(PSO-SAM)、基于蟻群算法的SVM參數(shù)尋優(yōu)法(ACO-SAM)和本文提出的基于人工魚群算法的SVM參數(shù)尋優(yōu)法(AF-SVM)5種方法對(duì)建立的SVM分類模型進(jìn)行最優(yōu)參數(shù)組合(C,γ)的選取,并按照各方法所獲得的最優(yōu)參數(shù)組合(C,γ)再利用SVM模型對(duì)各數(shù)據(jù)集進(jìn)行預(yù)測(cè),并記錄相應(yīng)的分類準(zhǔn)確率,具體結(jié)果見表3。
從表3看以看出:利用5種方法通過8組數(shù)據(jù)集對(duì)SVM參數(shù)組合(C,γ)優(yōu)化選擇的結(jié)果分析得出,基于人工魚群算法的SVM法比基于遺傳算法、粒子群算法和蟻群算法的SVM參數(shù)尋優(yōu)法以及SVM的交叉驗(yàn)證法具有更好的實(shí)驗(yàn)效果,具有更高的分類準(zhǔn)率,表明基于人工魚群算法對(duì)支持向量機(jī)的參數(shù)組合(C,γ)具有較強(qiáng)的尋優(yōu)能力,所得的分類結(jié)果也更為準(zhǔn)確。為進(jìn)一步分析人工魚群算法與其他仿生智能算法在SVM參數(shù)組合尋優(yōu)中的收斂性問題,根據(jù)4種仿生智能算法對(duì)8組數(shù)據(jù)集的分類效果以可視化的形式展示四算法的分類對(duì)比圖見圖2~圖9。
由圖2~圖9可知:利用UCI中8個(gè)數(shù)據(jù)集,對(duì)SVM最優(yōu)參數(shù)組合(C,γ)的尋優(yōu)實(shí)驗(yàn)結(jié)果的分析中可以得出基于人工魚群算法的SVM參數(shù)尋優(yōu)法比基于遺傳算法、粒子群算法和蟻群算法的參數(shù)尋優(yōu)法具有更高的分類準(zhǔn)確率,同時(shí)收斂性也較好,具有更快的收斂速度,說明多條人工魚并行搜索最優(yōu)參數(shù)組合的性能較強(qiáng)。由表3和圖2~圖9可以看出基于人工魚群算法的支持向量機(jī)參數(shù)尋優(yōu)法具有更好的學(xué)習(xí)性能。
表3 五方法所選取SVM最優(yōu)對(duì)數(shù)據(jù)集分類結(jié)果對(duì)比表
圖2 四種仿生智能算法對(duì)Statlog數(shù)據(jù)分類效果圖
圖3 四種仿生智能算法對(duì)LD數(shù)據(jù)分類效果圖
圖4 四種仿生智能算法對(duì)seeds數(shù)據(jù)分類效果圖
圖5 四種仿生智能算法對(duì)Iris數(shù)據(jù)分類效果圖
支持向量機(jī)核參數(shù)σ和罰參數(shù)C的選取對(duì)于其分類性能具有重要影響,同時(shí)考慮到人工魚群算法作為新興的群體智能優(yōu)化算法,具有較好的并行性不易陷入局部極值,同時(shí)具有對(duì)初始值不敏感和全局尋優(yōu)性能等優(yōu)點(diǎn),而提出了基于人工魚群算法的支持向量機(jī)參數(shù)優(yōu)化選取方法。實(shí)驗(yàn)結(jié)果表明,AF算法比GA、PSO和ACO算法具有更快的尋優(yōu)性能,同時(shí)所得的最優(yōu)參數(shù)組合的分類性能也更好,具有更高的分類準(zhǔn)確率,說明該方法對(duì)SVM的參數(shù)優(yōu)化選取是可行的和有效的,從而為支持向量機(jī)的核函數(shù)參數(shù)優(yōu)化提供了一種可行的方法。但針對(duì)不同的具體問題只是通過現(xiàn)有核函數(shù)的選取,可能會(huì)對(duì)支持向量機(jī)的性能具有一定影響,而且AF算法能較快收斂到最優(yōu)解的鄰域中,進(jìn)一步搜索尋優(yōu)的性能有待改善,因此接下來的工作一方面是如何根據(jù)具體研究問題構(gòu)造或選取較好的核函數(shù),以進(jìn)一步提高支持向量機(jī)的分類性能;另一方面是在AF算法尋得最優(yōu)解鄰域后再利用Monte-Carlo法等統(tǒng)計(jì)方法進(jìn)行局部尋優(yōu),以獲得更好的最優(yōu)解。
圖6 四種仿生智能算法對(duì)glass數(shù)據(jù)分類效果圖
圖7 四種仿生智能算法對(duì)wine數(shù)據(jù)分類效果圖
圖8 四種仿生智能算法對(duì)IS數(shù)據(jù)分類效果圖
圖9 四種仿生智能算法對(duì)HR數(shù)據(jù)分類效果圖
[1]Vapnik V.The nature of statistical learning theory[M].New York:Wiley,1998.
[2]汪廷華,陳峻婷.核函數(shù)的選擇研究綜述[J].計(jì)算機(jī)工程與設(shè)計(jì),2012,33(3):1181-1186.
[3]王奇,呂震宙,崔利杰.核函數(shù)的性質(zhì)及其在靈敏度分析上的應(yīng)用[J].西北工業(yè)大學(xué)學(xué)報(bào),2010,28(5):797-802.
[4]楊紫微,王儒敬,檀敬東,等.基于幾何判據(jù)的SVM參數(shù)快速選擇方法[J].計(jì)算機(jī)工程,2010,36(17):206-209.
[5]黃景濤,馬龍華,錢積新.基于統(tǒng)計(jì)試驗(yàn)設(shè)計(jì)方法的支持向量機(jī)參數(shù)選取[J].電路與系統(tǒng)學(xué)報(bào),2008,13(6):18-22.
[6]郭立力,趙春江.十折交叉檢驗(yàn)的支持向量機(jī)參數(shù)優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(8):55-57.
[7]Avci E.Selecting of the optimal feature subset and kernel parameters in digital modulation classification by using hybrid geneticalgorithm-supportvectormachines:HGASVM[J]. Expert Systems with Applications,2009,36:1391-1402.
[8]趙明淵,唐 勇,傅翀,等.基于帶特征染色體遺傳算法的支持向量機(jī)特征選擇和參數(shù)優(yōu)化[J].控制與決策,2010,25(8):1133-1138.
[9]Ilhan I,Tezel G.A genetic algorithm-support vector machine method with parameter optimization for selecting the tag SNPs[J].Journal of Biomedical Informatics,2013,46:328-340.
[10]陳濤,雍龍泉,鄧方安,等.基于差分進(jìn)化算法的支持向量機(jī)參數(shù)選擇[J].計(jì)算機(jī)工程與應(yīng)用,2011,47(5):24-26.
[11]邵信光,楊慧中,陳 剛.基于粒子群優(yōu)化算法的支持向量機(jī)參數(shù)選擇及其應(yīng)用[J].控制理論與應(yīng)用,2006,23(5):740-748.
[12]Melgani F,Bazi Y.Classification of Electrocardiogram signals with support vector machines and particle swarm optimization[J].IEEE Transactionson Information Technology in Biomedicine,2008,12(5):667-677.
[13]Abdi M J,Giveki D.Automatic detection of erythematosquamous diseases using PSO-SVM based on association rules[J].Engineering Applications of Artificial Intelligence,2013,(26):603-608.
[14]劉春波,王鮮芳,潘豐.基于蟻群優(yōu)化算法的支持向量機(jī)參數(shù)選擇及仿真[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版,2008,39(6):1309-1313.
[15]Li Zhan-Chao,Zhoua Xuan,Dai Zong,et al.Identification of protein methylation sites by coupling improved ant colony optimization algorithm and support vector machine[J].Analytica Chimica Acta,2011,703:163-171.
[16]戴上平,宋永東.基于遺傳算法與粒子群算法的支持向量機(jī)參數(shù)選擇[J].計(jì)算機(jī)工程與科學(xué),2012,34(10):113-117.
[17]李曉磊.一種新型的智能優(yōu)化方法—人工魚群算法[D].杭州:浙江大學(xué),2003.
[18]Li Xiaolei,Shao Zhijiang,Qian Jixin.An optimizing method based on autonomous animats:fish-swarm algorithm[J].Systems Engineering-Theory&Practice,2002,22(11):32-38.
[19]Li Xiaolei,Qian Jixin.Studies on artificial fish swarm optimization algorithm based on decomposition and coordination techniques[J].Journal of Circuits and Systems,2003,8(1):1-6.
[20]鄧乃揚(yáng),田英杰.數(shù)據(jù)挖掘中的新方法:支持向量機(jī)[M].北京:科學(xué)出版社,2004.
GAO Leifu,ZHAO Shijie,GAO Jing
College of Science,Liaoning Technical University,Fuxin,Liaoning 123000,China
As considering that the parameter optimization of support vector machine lacks theory support and the SVM cross-validation method spends lots of time on selecting parameters,the parameter optimization selection method of support vector machine is proposed based on artificial fish-swarm algorithm.This method puts the SVM classification prediction accuracy rate as the optimization principle and uses the better parallelism of artificial fish-swarm algorithm and the stronger global optimization ability to achieve the optimal target and obtain optimal parameter combination of SVM.The results of numerical value experiments show that the artificial fish-swarm algorithm has faster performance optimization and higher classification accuracy rate in SVM parameters’optimization selection.This method has the better parallelism and the stronger global optimization ability. Key words:support vector machine;artificial fish-swarm algorithm;parameter optimization;genetic algorithm
針對(duì)支持向量機(jī)的參數(shù)優(yōu)化缺乏理論支持,而SVM交叉檢驗(yàn)法選取又較為費(fèi)時(shí)的情況下,提出了基于人工魚群算法的支持向量機(jī)參數(shù)優(yōu)化選取算法,并以SVM分類預(yù)測(cè)準(zhǔn)確率最大為優(yōu)化原則,利用人工魚群算法的較好并行性和較強(qiáng)的全局尋優(yōu)能力,以實(shí)現(xiàn)最優(yōu)目標(biāo)并得到SVM的最優(yōu)參數(shù)組合。數(shù)值實(shí)驗(yàn)結(jié)果表明:人工魚群算法在SVM參數(shù)優(yōu)化選取中具有更快的尋優(yōu)性能,同時(shí)具有較高的分類準(zhǔn)確率。該方法具有較好的并行性和較強(qiáng)的全局尋優(yōu)能力。
支持向量機(jī);人工魚群算法;參數(shù)優(yōu)化;遺傳算法
A
TP18
10.3778/j.issn.1002-8331.1304-0066
GAO Leifu,ZHAO Shijie,GAO Jing.Application of artificial fish-swarm algorithm in SVM parameter optimization selection.Computer Engineering and Applications,2013,49(23):86-90.
遼寧省教育廳基金項(xiàng)目(No.L2012105)。
高雷阜(1963—),男,教授,博士生導(dǎo)師,研究方向:最優(yōu)化理論與方法;趙世杰(1987—),男,碩士研究生,研究方向:最優(yōu)化理論與應(yīng)用、數(shù)據(jù)挖掘;高晶(1989—),女,碩士研究生,研究方向:最優(yōu)化理論與應(yīng)用。E-mail:zhao2008shijie@126.com
2013-04-07
2013-05-27
1002-8331(2013)23-0086-05
CNKI出版日期:2013-08-27 http://www.cnki.net/kcms/detail/11.2127.TP.20130827.1603.011.html