基于改進粒子群算法的孿生支持向量機

顧吉峰，王 蓓

(華東理工大學 化工過程先進控制和優化技術教育部重點實驗室，上海 200237)

0 引 言

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

1 改進的粒子群搜索算法

1.1 基本粒子群搜索算法

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

(1)

Yid=Yid+Vid

(2)

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

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

(3)

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

1.2 改進的粒子群搜索算法

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

1.2.1 適應值增益反饋

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

(4)

(5)

(6)

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

1.2.2 漸變隨機擾動

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

(7)

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

(8)

(9)

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

(10)

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

2 IPSO-TWSVM算法

2.1 TWSVM基本原理

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

非線性孿生支持向量機求解優化問題的具體形式如式(11)、式(12)

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

(11)

(12)

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

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

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

(13)

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

(14)

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

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

(15)

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

(16)

2.2 IPSO-TWSVM算法

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

IPSO-TWSVM算法步驟如下：

Input：公共分類數據集

Output：分類器參數

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

步驟2 以參數c1、c2和核函數參數γ為優化對象訓練TWSVM，計算粒子的適應度值，取訓練精度的相反數作為適應值；

步驟3 更新全局最優值與當前最優值；

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

步驟5 選擇最終的全局最佳粒子作為TWSVM的參數構建IPSO-TWSVM模型。

3 實驗驗證

3.1 改進粒子群搜索算法的驗證

本文選用了4個標準適應度評估函數來評估所提的 IPSO 算法的性能。表1給出了適應度評估函數的表達式及其搜索區間和最小值，其中函數1和函數4位多峰函數，函數2和函數3位單峰函數，搜索區間即表示函數維度。

表1 測試函數

圖1至圖4分別為IPSO、PSO和引力搜索算法(gravi-tational search algorithm，GSA)算法對Ackley、Girewank、Rosenbrock、Sphere這4個測試函數的測試結果圖。結果表明，IPSO算法能夠在前期進行快速收斂，在后期進一步收斂至全局最優點。通過圖1可以觀察到，對于Ackley函數，當迭代至200次時，GSA算法和PSO算法陷入局部最小且無法繼續進行搜索，而改進后的粒子群算法能夠繼續以較快的速度逼近全局最優。圖2至圖4可以驗證，改進后的粒子群算法具有前期搜索速度快，收斂效果更好的特點?？傮w來說，IPSO算法對以上4個搜索函數，在前期收斂速度和全局搜索精度上，均優于標準粒子群搜索算法和標準引力算法。

圖1 Ackley函數搜索效果

圖2 Rosenbrock函數搜索效果

圖3 Sphere函數搜索效果

圖4 Girewank函數搜索效果

3.2 仿真數據集

為了驗證IPSO-TWSVM在不同數據集上的分類性能，選取來自UCI的4組公共數據集和來自Kaggle的Wine industry數據集進行測試。表2給出了不同數據集的樣本數量等相關信息。其中，Sonar為高維樣本數據集，Breast cancer為大容量樣本數據集，Ionosphere和Thyroid為中等規模樣本數據集。Wine industry將產品質量一等二等構成優秀標簽，其余分為一般標簽，從而構成二分類標簽，本文從中隨機抽取了1000組樣本進行訓練和預測任務。

表2 公共數據集分析

3.3 實驗結果及分析

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

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

表3 算法實驗結果

4 結束語

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