姜雯吳陳

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江212000）

1 引言

支持向量機(jī)（Support Vector Machine，SVM）是Cortes和Vapnik于1995年提出的，SVM在解決小樣本，非線性以及高維模式識別中有著顯著的優(yōu)勢［1~3］。在支持向量機(jī)模型中，懲罰因子C和核參數(shù)γ是影響分類結(jié)果的主要因素［4］。人工智能算法為啟發(fā)式算法，即不用去遍歷解空間里的所有位置，就可以尋找到問題的最優(yōu)解，因此能夠高效地尋找到最優(yōu)的SVM參數(shù)。傳統(tǒng)的人工智能算法有遺傳算法［5］、粒子群算法［6］、蟻群算法［7］等。本文采用粒子群算法來優(yōu)化SVM參數(shù)，從而提高SVM的分類性能。粒子群算法是一種基于種群的全局優(yōu)化方法，具有算法簡單，易于實(shí)現(xiàn)以及收斂速度快的優(yōu)點(diǎn)。由于粒子群算法在演化過程中很容易過早收斂并陷入局部最優(yōu)，目前已經(jīng)有很多學(xué)者提出對粒子群算法進(jìn)行優(yōu)化［8~11］。針對傳統(tǒng)的粒子群算法在優(yōu)化支持向量機(jī)時(shí)存在著易陷入局部最優(yōu)，分類精度低以及早熟收斂的缺點(diǎn)，本文采取兩種方式對粒子群算法進(jìn)行優(yōu)化，利用改進(jìn)后的算法找到最優(yōu)SVM參數(shù)，提高SVM的分類精度。

2 支持向量機(jī)

支持向量機(jī)的原理是建立一個(gè)最優(yōu)分類超平面，使得該超平面在正確分開不同類別的樣本的同時(shí)，還能使得分類間隔最大化。假設(shè)訓(xùn)練樣本集為

可求得最優(yōu)分類超平面為其中，w為超平面法向量；ξi為松弛因子；C為懲罰因子；xi為第i個(gè)樣本的特征；yi為類別標(biāo)簽；φ（xi）為映射函數(shù)；

利用Lagrange函數(shù)，可得到該問題的對偶形式：

其中，αi為Lagrange乘子；K(xi，xj)∈Rn為核函數(shù)，本文采用高斯核函數(shù)［12］作為SVM模型中的核函數(shù)，其數(shù)學(xué)形式為

其中，γ為核參數(shù)。

3 對粒子群算法進(jìn)行優(yōu)化

3.1 經(jīng)典粒子群算法

粒子群算法是由Eberhart和Kennedy在1995年提出的一種群智能優(yōu)化算法，它是源于對鳥類覓食行為的研究。粒子群算法具有收斂速度快，算法簡單以及效率高的優(yōu)點(diǎn)。在粒子群算法中，每個(gè)粒子具有位置和速度兩個(gè)屬性，粒子的位置表示某個(gè)可行解，粒子的速度則表示與下一個(gè)可行解的差值。每個(gè)粒子可以根據(jù)已經(jīng)尋找到的最優(yōu)解和整個(gè)粒子群的最優(yōu)解不斷調(diào)整自己的速度，以此來尋找到更優(yōu)的解。

假設(shè)所求解問題的空間是d維，種群大小為m，種群中的每個(gè)粒子代表一個(gè)可行解，則第i個(gè)粒子的位置和速度分別為Xi=(xi1，xi2，…，xid)和Vi=(vi1，vi2，…，vid)。記第i個(gè)粒子經(jīng)過的最好位置為Pbest=(ppbest，1，ppbest，2，…，ppbest，d)，整個(gè)種群經(jīng)過的最優(yōu)位置為gbest=(pgbest，1，pgbest，2，…，pgbest，d)。在迭代過程中，粒子可通過個(gè)體極值pbest和群體極值gbest來進(jìn)行更新自己的速度和位置，即：

其中w為慣性權(quán)重；c1，c2為學(xué)習(xí)因子，為常數(shù)；r1，r2為［0，1］區(qū)間內(nèi)的隨機(jī)數(shù)；k為進(jìn)化的代數(shù)，1≤i≤m，1≤j≤d。

3.2 改進(jìn)慣性權(quán)重的粒子群優(yōu)化算法

在粒子群算法中，慣性權(quán)重w的大小影響粒子群算法尋找最優(yōu)解的能力［13~14］。若w較大，則有利于提高粒子的全局最優(yōu)能力，使得算法跳出局部最優(yōu)點(diǎn)；若w較小，則會(huì)提高粒子的局部最優(yōu)能力，使得算法趨于收斂。本文采用自適應(yīng)權(quán)重來取代慣性權(quán)重，從而平衡粒子的全局和局部最優(yōu)能力：

其中，wmax為權(quán)重的最大值，wmin為權(quán)重的最小值，通常取wmax=0.9，wmin=0.4；fi為第i個(gè)粒子的適應(yīng)度值，favg為種群平均適應(yīng)度值，fg為種群最優(yōu)適應(yīng)度值。

3.3 引入自適應(yīng)變異的粒子群優(yōu)化算法

本文將粒子群中的每個(gè)粒子位置變量設(shè)定為二維，兩個(gè)分量為x(i，1)和x(i，2)。其中，x(i，1)的范圍為(Cmin，Cmax)，x(i，2)的范圍為(γmin，γmax)，分別對應(yīng)SVM的懲罰因子C和核參數(shù)γ，用粒子的適應(yīng)度值來評價(jià)粒子所處位置的好壞程度。

本文采用自適應(yīng)變異對粒子群算法進(jìn)行優(yōu)化，賦予部分粒子一定的變異概率，從而增強(qiáng)粒子的種群多樣性［15~16］，在一定程度上跳出局部最優(yōu)解，達(dá)到全局最優(yōu)。具體變異算法如下：

其 中，k=ceil(2*rand)，rand的 范 圍 為(0，1)，

改進(jìn)后的粒子群算法具體步驟如下：

步驟1：初始化PSO的相關(guān)參數(shù)。在一定范圍內(nèi)隨機(jī)生成粒子的初始位置。

步驟2：計(jì)算粒子的適應(yīng)度值。利用臺(tái)灣林智仁教授開發(fā)的LIBSVM工具箱里的svmtrain函數(shù)來計(jì)算各個(gè)粒子的適應(yīng)度值。將每個(gè)粒子的位置分量x(i，1)和x(i，2)代入適應(yīng)度函數(shù)中得到適應(yīng)度值，計(jì)算過程如下：

教學(xué)的意義在于使學(xué)生擁有終身發(fā)展，并且適應(yīng)社會(huì)的知識儲(chǔ)備以及能力。利用網(wǎng)絡(luò)的發(fā)展與高中物理教學(xué)相結(jié)合，能夠有效提升學(xué)生對于社會(huì)科技發(fā)展的敏感度，這對于學(xué)生個(gè)人未來發(fā)展具有重要意義。同時(shí)，多樣化的網(wǎng)絡(luò)技術(shù)也產(chǎn)生了各具風(fēng)格和內(nèi)涵軟件平臺(tái)，可以有效改善一些現(xiàn)實(shí)的限制，諸如試驗(yàn)的設(shè)備等，也可以增強(qiáng)教師與學(xué)生和家長的聯(lián)系，使教學(xué)活動(dòng)范圍從局限于學(xué)校，到建立真正的學(xué)校家庭學(xué)習(xí)體系，更重要的是教師可以從新利用這些平臺(tái)，實(shí)現(xiàn)對學(xué)生多方面能力的綜合培養(yǎng)。

其中，v表示交叉驗(yàn)證數(shù)，c表示懲罰因子C，g表示核參數(shù)γ，f(i)表示第i個(gè)粒子在當(dāng)前位置的適應(yīng)度值，算法中用fi表記。train_label表示訓(xùn)練數(shù)據(jù)集標(biāo)簽，train表示訓(xùn)練數(shù)據(jù)集。

步驟3：根據(jù)粒子初始適應(yīng)度值，可得到粒子的個(gè)體極值pbest和群體極值gbest。

步驟4：根據(jù)式（7）更新權(quán)重；根據(jù)式（5）和式（6）更新粒子的速度和位置。

步驟5：根據(jù)式（8），對部分粒子進(jìn)行變異。

步驟6：計(jì)算粒子當(dāng)前適應(yīng)度值，并更新粒子個(gè)體極值pbest和群體極值gbest。

步驟7：判斷是否達(dá)到最大迭代次數(shù)，若滿足則轉(zhuǎn)至步驟7，否則轉(zhuǎn)至步驟2。

步驟8：輸出種群最優(yōu)位置（對應(yīng)SVM的懲罰因子C和核參數(shù)γ）。

步驟9：輸入最佳SVM參數(shù)，進(jìn)行分類。

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

本文采用UCI標(biāo)準(zhǔn)數(shù)據(jù)集（Seeds，Wine，Iris）對改進(jìn)的算法進(jìn)行驗(yàn)證分析。其中，實(shí)驗(yàn)參數(shù)設(shè)置如下：在SVM中，懲罰因子C的范圍為0.1~100，核參數(shù)γ的范圍為0.01~10；在粒子群算法中，進(jìn)化次數(shù)為200，種群數(shù)目為20，學(xué)習(xí)因子C1=1.5，C2=1.7，慣性權(quán)重wmax=1.5，wmin=1.7。

Seeds數(shù)據(jù)集有三個(gè)類別，共計(jì)210個(gè)樣本。每個(gè)類別有70個(gè)樣本，將每個(gè)類別隨機(jī)抽取40組作為訓(xùn)練集，30組作為測試集，測試集共計(jì)90組。分別用PSO-SVM和本文改進(jìn)的算法GPSO-SVM進(jìn)行試驗(yàn)，實(shí)驗(yàn)結(jié)果如表1所示。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法（GPSO-SVM）可糾正5個(gè)錯(cuò)分樣本，分類精度提高了5.56%

表1 Seeds數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

Wine數(shù)據(jù)集一共有三個(gè)類別，共計(jì)178個(gè)樣本。隨機(jī)抽取108組作為訓(xùn)練集，70組作為測試集。實(shí)驗(yàn)結(jié)果如表2所示。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法（GPSO-SVM）可糾正5個(gè)錯(cuò)分樣本，分類精度提高了7.14%。

表2 Wine數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

Iris數(shù)據(jù)集一共有三個(gè)類別，共計(jì)150個(gè)樣本。將每個(gè)類別隨機(jī)抽取30組作為訓(xùn)練集，剩下來的作為測試集，測試集共計(jì)60組。實(shí)驗(yàn)結(jié)果如表3所示，實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法（GP?SO-SVM）可糾正4個(gè)錯(cuò)分樣本，分類精度提高了6.67%。

表3 Iris數(shù)據(jù)集實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法的分類精度明顯優(yōu)于PSO-SVM算法，改進(jìn)后的算法不僅能有效地避免粒子陷入局部最優(yōu)，更增強(qiáng)了粒子的種群多樣性，具有較高的分類精度。

5 結(jié)語

本文針對粒子群算法在優(yōu)化支持向量機(jī)分類時(shí)易陷入局部最優(yōu)，早熟收斂的問題，利用自適應(yīng)權(quán)重和引入自適應(yīng)變異對粒子群算法進(jìn)行改進(jìn)，使得粒子的全局搜索能力和局部搜索能力能夠達(dá)到良好的平衡，從而達(dá)到全局最優(yōu)。本文使用UCI標(biāo)準(zhǔn)數(shù)據(jù)集對改進(jìn)后的算法進(jìn)行實(shí)驗(yàn)論證。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法提高了算法的分類性能。在今后的研究中，不僅要尋找更好的改進(jìn)方法來優(yōu)化粒子群算法，更要從效率和精度兩方面提高分類的性能。