基于改進(jìn)粒子群算法的孿生支持向量機(jī)

顧吉峰，王 蓓

(華東理工大學(xué) 化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，上海 200237)

0 引 言

在工業(yè)生產(chǎn)中，對(duì)生產(chǎn)工藝中的數(shù)據(jù)進(jìn)行分析和建?？梢蕴岣咂髽I(yè)的經(jīng)濟(jì)效益[1]。例如在電力行業(yè)，判斷用戶是否存在偷電漏電的行為非常必要[2]，尋找合適的方法對(duì)已收集的數(shù)據(jù)實(shí)施分類任務(wù)是值得關(guān)注的問(wèn)題。與人工神經(jīng)網(wǎng)絡(luò)[3]、決策樹[4]、樸素貝葉斯[5]等分類算法相比，支持向量機(jī)[6,7](supported vector machine，SVM)以更優(yōu)越的綜合分類性能和可解釋性被廣泛應(yīng)用在工業(yè)目標(biāo)檢測(cè)與分類建模任務(wù)中。孿生支持向量機(jī)[8](twin support vector machine，TWSVM)是在SVM的基礎(chǔ)上發(fā)展而產(chǎn)生的一種新二分類的分類器，與SVM相比提升了3/4的效率，而其中的參數(shù)選擇對(duì)TWSVM的分類效果有著重要影響，因此利用搜索算法與TWSVM結(jié)合進(jìn)行參數(shù)尋優(yōu)是一種可行的方案。粒子群優(yōu)化搜索算法[9](particle swarm optimization，PSO)以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)在解決實(shí)際問(wèn)題中展示了其優(yōu)越性，PSO算法與SVM相結(jié)合構(gòu)成的分類器也經(jīng)常被應(yīng)用于各種數(shù)據(jù)分類任務(wù)中[10,11]。然而，PSO算法在運(yùn)算迭代過(guò)程中，固定部分參數(shù)，容易陷入局部最小問(wèn)題，并且搜索能力較弱。本文提出一種引入適應(yīng)值增益反饋和漸變隨機(jī)擾動(dòng)的改進(jìn)型粒子群優(yōu)化搜索算法(improved particle swarm optimization，IPSO)，并利用IPSO優(yōu)化TWSVM的參數(shù)，構(gòu)建了IPSO-TWSVM分類模型。通過(guò)4個(gè)標(biāo)準(zhǔn)基準(zhǔn)函數(shù)進(jìn)行仿真，對(duì)IPSO的搜索性能進(jìn)行驗(yàn)證。同時(shí)，選取了UCI的4組數(shù)據(jù)集和Kaggle中的Wine industry數(shù)據(jù)集對(duì)IPSO-TWSVM分類模型進(jìn)行了測(cè)試，計(jì)算并比較了分類準(zhǔn)確率和平均訓(xùn)練時(shí)間兩個(gè)指標(biāo)，來(lái)驗(yàn)證IPSO-TWSVM在不同數(shù)據(jù)集上的分類性能和效果。

1 改進(jìn)的粒子群搜索算法

1.1 基本粒子群搜索算法

粒子群搜索算法是基于鳥類覓食原理產(chǎn)生的一種搜索算法，將優(yōu)化問(wèn)題的解空間看作覓食中的鳥群，稱之為“粒子”。每一個(gè)粒子由優(yōu)化問(wèn)題函數(shù)決定一個(gè)適應(yīng)值，當(dāng)前最優(yōu)適應(yīng)值即代表當(dāng)前某種鳥距離食物最近，其余粒子追尋當(dāng)前最優(yōu)粒子進(jìn)行搜索，每個(gè)粒子都有一個(gè)初始狀態(tài)、飛行速度和飛行距離。假設(shè)對(duì)于在隨機(jī)選擇的n個(gè)粒子的搜索空間中，第i個(gè)粒子在d維上的位置與速度更新公式如下

(1)

Yid=Yid+Vid

(2)

其中，ω稱為慣性因子；C1和C2稱為加速常數(shù)；random(0,1) 表示區(qū)間[0,1]上的隨機(jī)數(shù)；Pid表示第i個(gè)變量的個(gè)體極值的第d維；Pgd表示全局最優(yōu)解的第d維。其中式(1)、式(2)定義請(qǐng)參見參考文獻(xiàn)[9]。

為了限制速度的迭代大小并限定迭代位置的發(fā)散性，一般添加以下限制條件

(3)

其中，ω為限定Vid基礎(chǔ)值的慣性因子，可以限制每次變化中Vid慣性大小，C1,C2決定了每次速度更新中沿個(gè)體最優(yōu)點(diǎn)與全局最優(yōu)點(diǎn)方向的前進(jìn)路線長(zhǎng)度。

1.2 改進(jìn)的粒子群搜索算法

PSO主要存在以下兩個(gè)問(wèn)題：第一是限定迭代速度后，全局搜索的速度慢且效率低；第二是在樣本多樣性較大的情況下，易陷入局部最優(yōu)而造成過(guò)早收斂的情況。針對(duì)以上兩個(gè)問(wèn)題，本文提出了相應(yīng)的改進(jìn)，并分別在1.2.1節(jié)和1.2.2節(jié)中具體描述。

1.2.1 適應(yīng)值增益反饋

針對(duì)算法全局搜索速度慢的不足的問(wèn)題，不再將位置更新步長(zhǎng)固定，而是利用參數(shù)λ來(lái)調(diào)整位置的更新步長(zhǎng)，由此將式(2)寫成以下形式

(4)

(5)

(6)

其中，α1、α2和α3分別為第t次、第t-1次和第t-2次的適應(yīng)值增益系數(shù)，μ為歷史信息殘留，為固定常數(shù)。

1.2.2 漸變隨機(jī)擾動(dòng)

針對(duì)算法易陷入局部最優(yōu)而造成過(guò)早收斂的情況，將漸變隨機(jī)擾動(dòng)引入速度迭代式(1)中，漸變隨機(jī)擾動(dòng)T的定義如下

(7)

其中，N為設(shè)置的最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)，Accgbest表示全局最優(yōu)適應(yīng)值，Accpbest表示第i個(gè)粒子的個(gè)人最優(yōu)解。將漸變隨機(jī)擾動(dòng)引入慣性因子ω，ω可改寫為如下形式

(8)

(9)

為了進(jìn)一步防止過(guò)早局部收斂，增加以下限制條件

(10)

通過(guò)引入適應(yīng)值增益反饋與漸變隨機(jī)擾動(dòng)，IPSO能充分利用適應(yīng)值變化信息改變迭代步長(zhǎng)，并通過(guò)擾動(dòng)項(xiàng)增加粒子隨機(jī)性，跳出局部最優(yōu)。

2 IPSO-TWSVM算法

2.1 TWSVM基本原理

孿生支持向量機(jī)以廣義特征值向量機(jī)為基礎(chǔ)，分別構(gòu)造正負(fù)兩個(gè)超平面，要求一類樣本點(diǎn)盡量接近，另一類樣本盡量遠(yuǎn)離?；谶@個(gè)特性，TWSVM對(duì)不平衡數(shù)據(jù)集有著較好的分類性能。工藝生產(chǎn)中的數(shù)據(jù)來(lái)源于各個(gè)工藝段，數(shù)據(jù)一般具有非線性的特點(diǎn)。因此，非線性孿生支持向量機(jī)將會(huì)在處理過(guò)程數(shù)據(jù)中有更好的分類性能。

非線性孿生支持向量機(jī)求解優(yōu)化問(wèn)題的具體形式如式(11)、式(12)

min(ω1,b1,
s.t-(K(B,ST)ω1+e2b1)+≥e2,≥0

(11)

(12)

其中，ω1和ω2分別為超平面的法向量，b1和b2分別為超平面的偏移向量，e1和e2是列向量，維度與支持向量一致，c1和c2代表支持向量機(jī)懲罰項(xiàng)的系數(shù)，S代表樣本，和η是支持向量機(jī)的松弛變量。其中式(11)、式(12)定義請(qǐng)參見參考文獻(xiàn)[8]。

對(duì)上述式(11)、式(12)進(jìn)行求解從而確定兩個(gè)超平面

K(xT,ST)ω1+b1=0

(13)

K(xT,ST)ω2+b2=0

(14)

式(13)、式(14)分別表示為正負(fù)兩個(gè)超平面。對(duì)新樣本進(jìn)行分類時(shí)，分別計(jì)算樣本到兩個(gè)超平面的距離，從而確定樣本類別。離正類超平面近的樣本劃分為正類，離負(fù)類超平面近的樣本劃分為負(fù)類，決策函數(shù)如式(15)所示

Classi=min|K(xT,ST)ωi+bi|,i=1,2

(15)

本文選取了RBF作為支持向量機(jī)的核函數(shù)，可以解決沒有先驗(yàn)知識(shí)的非線性樣本函數(shù)，其形式如式(16)所示

(16)

2.2 IPSO-TWSVM算法

TWSVM的分類性能由參數(shù)c1、c2和核函數(shù)參數(shù)γ的選取決定。參數(shù)c1和c2選取會(huì)影響兩個(gè)超平面間的距離。參數(shù)選取過(guò)小，則超平面距離會(huì)過(guò)近，從而導(dǎo)致分類效果較差；而參數(shù)選取過(guò)大，則樣本本身與超平面之間的距離就會(huì)被忽略，從而導(dǎo)致分類準(zhǔn)確度降低。核函數(shù)參數(shù)γ選取過(guò)小，則無(wú)法保證訓(xùn)練時(shí)的準(zhǔn)確率，進(jìn)而影響最終的分類準(zhǔn)確率；核函數(shù)參數(shù)γ選取過(guò)大，則會(huì)使得TWSVM分類作用樣本僅在支持向量附近，雖然樣本訓(xùn)練的準(zhǔn)確率高但最終的預(yù)測(cè)率較差。因此，本文利用IPSO算法的搜索能力結(jié)合TWSVM，對(duì)式(11)、式(12)中的c1、c2和式(16)中的核函數(shù)參數(shù)γ進(jìn)行參數(shù)尋優(yōu)，從而提高TWSVM的分類性能。

IPSO-TWSVM算法步驟如下：

Input：公共分類數(shù)據(jù)集

Output：分類器參數(shù)

步驟1 初始化粒子群個(gè)數(shù)、隨機(jī)位置、速度和迭代終止條件；

步驟2 以參數(shù)c1、c2和核函數(shù)參數(shù)γ為優(yōu)化對(duì)象訓(xùn)練TWSVM，計(jì)算粒子的適應(yīng)度值，取訓(xùn)練精度的相反數(shù)作為適應(yīng)值；

步驟3 更新全局最優(yōu)值與當(dāng)前最優(yōu)值；

步驟4 判斷是否達(dá)到迭代終止條件，若沒有返回步驟2進(jìn)行下一輪迭代；

步驟5 選擇最終的全局最佳粒子作為TWSVM的參數(shù)構(gòu)建IPSO-TWSVM模型。

3 實(shí)驗(yàn)驗(yàn)證

3.1 改進(jìn)粒子群搜索算法的驗(yàn)證

本文選用了4個(gè)標(biāo)準(zhǔn)適應(yīng)度評(píng)估函數(shù)來(lái)評(píng)估所提的 IPSO 算法的性能。表1給出了適應(yīng)度評(píng)估函數(shù)的表達(dá)式及其搜索區(qū)間和最小值，其中函數(shù)1和函數(shù)4位多峰函數(shù)，函數(shù)2和函數(shù)3位單峰函數(shù)，搜索區(qū)間即表示函數(shù)維度。

表1 測(cè)試函數(shù)

圖1至圖4分別為IPSO、PSO和引力搜索算法(gravi-tational search algorithm，GSA)算法對(duì)Ackley、Girewank、Rosenbrock、Sphere這4個(gè)測(cè)試函數(shù)的測(cè)試結(jié)果圖。結(jié)果表明，IPSO算法能夠在前期進(jìn)行快速收斂，在后期進(jìn)一步收斂至全局最優(yōu)點(diǎn)。通過(guò)圖1可以觀察到，對(duì)于Ackley函數(shù)，當(dāng)?shù)?00次時(shí)，GSA算法和PSO算法陷入局部最小且無(wú)法繼續(xù)進(jìn)行搜索，而改進(jìn)后的粒子群算法能夠繼續(xù)以較快的速度逼近全局最優(yōu)。圖2至圖4可以驗(yàn)證，改進(jìn)后的粒子群算法具有前期搜索速度快，收斂效果更好的特點(diǎn)?？傮w來(lái)說(shuō)，IPSO算法對(duì)以上4個(gè)搜索函數(shù)，在前期收斂速度和全局搜索精度上，均優(yōu)于標(biāo)準(zhǔn)粒子群搜索算法和標(biāo)準(zhǔn)引力算法。

圖1 Ackley函數(shù)搜索效果

圖2 Rosenbrock函數(shù)搜索效果

圖3 Sphere函數(shù)搜索效果

圖4 Girewank函數(shù)搜索效果

3.2 仿真數(shù)據(jù)集

為了驗(yàn)證IPSO-TWSVM在不同數(shù)據(jù)集上的分類性能，選取來(lái)自UCI的4組公共數(shù)據(jù)集和來(lái)自Kaggle的Wine industry數(shù)據(jù)集進(jìn)行測(cè)試。表2給出了不同數(shù)據(jù)集的樣本數(shù)量等相關(guān)信息。其中，Sonar為高維樣本數(shù)據(jù)集，Breast cancer為大容量樣本數(shù)據(jù)集，Ionosphere和Thyroid為中等規(guī)模樣本數(shù)據(jù)集。Wine industry將產(chǎn)品質(zhì)量一等二等構(gòu)成優(yōu)秀標(biāo)簽，其余分為一般標(biāo)簽，從而構(gòu)成二分類標(biāo)簽，本文從中隨機(jī)抽取了1000組樣本進(jìn)行訓(xùn)練和預(yù)測(cè)任務(wù)。

表2 公共數(shù)據(jù)集分析

3.3 實(shí)驗(yàn)結(jié)果及分析

由于算法與初始隨機(jī)的粒子好壞有關(guān)，為了評(píng)估IPSO算法的優(yōu)越性，本文計(jì)算了訓(xùn)練準(zhǔn)確率與平均訓(xùn)練時(shí)間兩個(gè)指標(biāo)。準(zhǔn)確率是最終分類正確的樣本數(shù)與總體樣本數(shù)的比值，平均訓(xùn)練時(shí)間為多次不同的訓(xùn)練過(guò)程中訓(xùn)練結(jié)果到達(dá)90%準(zhǔn)確度所需要的時(shí)間的多次均值。將IPSO與改進(jìn)前的PSO 算法與GSA算法進(jìn)行了比對(duì)，分別對(duì)TWSVM算法進(jìn)行參數(shù)尋優(yōu)，并在5個(gè)數(shù)據(jù)集中進(jìn)行分類任務(wù)。GSA算法中，令交叉概率為0.65，變異概率為0.06。PSO算法中固定c1=c2=2，慣性權(quán)重取0.8，具體算法實(shí)驗(yàn)結(jié)果見表3。

通過(guò)表3可以看出，利用IPSO對(duì)TWSVM進(jìn)行參數(shù)尋優(yōu)時(shí)，該算法在高維、高樣本量的數(shù)據(jù)集上均獲得了較高的準(zhǔn)確率，且在收斂速度上高于其它兩種算法。這是因?yàn)樵贗PSO算法迭代的過(guò)程中，加入了適應(yīng)值增益反饋與隨機(jī)漸變擾動(dòng)，可以快速跳出局部最小，從而加快收斂速度，在迭代后期，隨機(jī)漸變擾動(dòng)又能夠保證算法有更高的精度。特別是針對(duì)Wine industry數(shù)據(jù)集，其準(zhǔn)確率高達(dá)95.85%，且訓(xùn)練時(shí)間為521 s，高于PSO-TWSVM算法和GSA-TWSVM。

表3 算法實(shí)驗(yàn)結(jié)果

4 結(jié)束語(yǔ)

本文通過(guò)將適應(yīng)度反饋和漸變隨機(jī)擾動(dòng)融入粒子群算法，提出了一種改進(jìn)的粒子群搜索算法，利用其對(duì)孿生支持向量機(jī)進(jìn)行參數(shù)尋優(yōu)構(gòu)建分類器。首先利用適應(yīng)值增益反饋增加前期粒子群搜索算法的快速收斂性，然后將漸變隨機(jī)擾動(dòng)引入算法，防止局部最優(yōu)解并調(diào)整迭代后期的粒子位置。4個(gè)基準(zhǔn)搜索函數(shù)上的搜索測(cè)試結(jié)果表明，本文所提出的IPSO算法在搜索能力上，收斂效果和收斂速度相比于傳統(tǒng)標(biāo)準(zhǔn)搜索算法有提高。將改進(jìn)后的IPSO算法結(jié)合TWSVM構(gòu)成分類器，在5個(gè)不同公共數(shù)據(jù)集上進(jìn)行測(cè)試，驗(yàn)證了IPSO算法參數(shù)尋優(yōu)效果較好，IPSO-TWSVM分類器的準(zhǔn)確率與前期收斂速度均高于其它兩種算法。