顧吉峰，王 蓓

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

0 引 言

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

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

1.1 基本粒子群搜索算法

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

(1)

Yid=Yid+Vid

(2)

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

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

(3)

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

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

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

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

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

(4)

(5)

(6)

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

1.2.2 漸變隨機(jī)擾動

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

(7)

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

(8)

(9)

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

(10)

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

2 IPSO-TWSVM算法

2.1 TWSVM基本原理

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

非線性孿生支持向量機(jī)求解優(yōu)化問題的具體形式如式(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ī)懲罰項的系數(shù)，S代表樣本，和η是支持向量機(jī)的松弛變量。其中式(11)、式(12)定義請參見參考文獻(xiàn)[8]。

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

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

(13)

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

(14)

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

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

(15)

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

(16)

2.2 IPSO-TWSVM算法

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

IPSO-TWSVM算法步驟如下：

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

Output：分類器參數(shù)

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

步驟2 以參數(shù)c1、c2和核函數(shù)參數(shù)γ為優(yōu)化對象訓(xùn)練TWSVM，計算粒子的適應(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í)驗驗證

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

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

表1 測試函數(shù)

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

為了驗證IPSO-TWSVM在不同數(shù)據(jù)集上的分類性能，選取來自UCI的4組公共數(shù)據(jù)集和來自Kaggle的Wine industry數(shù)據(jù)集進(jìn)行測試。表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ù)測任務(wù)。

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

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

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

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

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

4 結(jié)束語

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