基于粒子群算法的雙子支持向量機研究

摘要：針對標準支持向量機訓練時間過長與參數(shù)選擇無指導性問題，給出一種通過粒子群優(yōu)化雙支持向量機模型參數(shù)的方法。與標準支持向量機不同，該方法的時間復雜度更小，特別適合不均衡的數(shù)據(jù)樣本分類問題，對求解大規(guī)模的數(shù)據(jù)分類問題有很大優(yōu)勢。將該算法與標準的支持向量機分類器在不同的文本數(shù)據(jù)集上進行仿真實驗對比，以驗證算法的有效性。結(jié)果表明基于粒子群優(yōu)化的雙子支持向量機分類器的分類結(jié)果高于標準支持向量機分類結(jié)果。

關(guān)鍵詞：雙子支持向量機（TWSVM）；分類算法；粒子群優(yōu)化算法（PSO）

DOIDOI：10.11907/rjdk.151455

中圖分類號：TP312

文獻標識碼：A 文章編號：16727800（2015）006007204

基金項目：玉林師范學院校級科研項目（2014YJYB04）

作者簡介作者簡介：劉建明（1986-），男，廣西博白人，碩士，玉林師范學院數(shù)學與信息科學學院助教，研究方向為數(shù)據(jù)挖掘與機器學習。

0 引言

粒子群優(yōu)化算法[1]（Particle Swarm Optimization，PSO）是由美國研究學者Kennedy等人在1995年提出的，PSO算法每一代的種群中的解具有向“他人”學習和“自我”學習的優(yōu)點，該算法能在較少的迭代次數(shù)中找到全局最優(yōu)解，這一特性被廣泛應用于神經(jīng)網(wǎng)絡(luò)方法、函數(shù)優(yōu)化問題、數(shù)據(jù)挖掘、模式識別，工程計算等研究領(lǐng)域。

雙子支持向量機（Twin Support Vector Machines， TWSVM）是Jayadeva[23] 基于傳統(tǒng)支持向量機在2007年提出來的。TWSVM是從SVM演化而來的，是一種新型的基于統(tǒng)計學習理論的機器學習算法。TWSVM具有SVM優(yōu)點，同時適合處理像文本自動分類、基因表達、空間信息遙感數(shù)據(jù)、語音識別等這樣的大規(guī)模數(shù)據(jù)分類問題。

針對TWSVM對懲罰參數(shù)和核函數(shù)參數(shù)缺乏指導性問題，本文結(jié)合PSO算法的優(yōu)點，給出一種基于PSO的

算法優(yōu)化改進策略，對TWSVM分類器進行優(yōu)化。PSO是一種基于群體智能的全局尋優(yōu)算法，該算法能在較少的迭代次數(shù)中找到全局最優(yōu)解，通過利用粒子群優(yōu)化算法對雙子支持向量機進行優(yōu)化后，分類器較之標準支持向量機有更好的分類效果。

1 PSO算法

PSO算法步驟：①初始化粒子群，利用隨機函數(shù)法給每一個粒子的初始位置和速度賦值；②根據(jù)第①步的賦值及初始位置與速度更新每一個粒子新的位置；③利用選定的適應度函數(shù)計算每一個粒子的適應度值；④對每一個粒子，對比其個體和群體的適應度值，并找出粒子經(jīng)過的最好位置的適應度值，如果發(fā)現(xiàn)更好的位置及適應度值，那么就更新其位置；⑤根據(jù)公式更新每個粒子的速度與位置，如果找到最優(yōu)的位置或者是到了最大的迭代次數(shù)，算法終止，否則轉(zhuǎn)入第3步繼續(xù)迭代求解。

2 雙子支持向量機（TWSVM）

與SVM不同，TWSVM求解的是一對分類超平面，SVM求解一個QP問題而TWSVM解決的是兩個QP問題，而這兩個QP問題的求解規(guī)模比SVM小很多。傳統(tǒng)SVM構(gòu)造兩個平行的超平面，并且使兩個超平面之間的距離最大即最大間隔化，TWSVM雖然也是構(gòu)造超平面，但超平面之間不需要平行。TWSVM對每一個樣本都構(gòu)造一個超平面，每個樣本的超平面要最大限度地靠近該類的樣本數(shù)據(jù)點，而同時盡可能地遠離另一類樣本數(shù)據(jù)點。新數(shù)據(jù)樣本將會分配給離兩個超平面中最近的一個平面。事實上，該算法還可以沿著非平行面聚集，而且樣本聚集方式是根據(jù)完全不同的公式聚合而成的。實際上，在TWSVM中的兩個QP問題與標準SVM的QP問題除了求解約束問題不同外，求解公式是相同的。TWSVM的二分類算法通過求解下面的一對QPP（Quadratic Program Problem）問題進行二次規(guī)劃優(yōu)化[5]。

其中，c1，c2>0并且e1和e2是適當維數(shù)且屬性值是全為1的向量。TWSVM算法為每一個類構(gòu)建超平面時，樣本點根據(jù)與各個超平面的距離大小作為與平面靠近程度的評價指標，目標函數(shù)（2）和（3）計算樣本點與超平面距離的平方。因此，它的最小值能保證樣本數(shù)據(jù)點最大限度地靠近其中一類（類一），同時盡可能地遠離另一類。誤差變量用于測量超平面距離間隔的誤差。目標函數(shù)公式（2）和（3）的第二項是誤差之和，它的作用是使錯分樣本的數(shù)據(jù)極小化，盡量減少錯分的誤差情況。為求解公式（2）和（3），分別對TWSVM1和TWSVM2引入拉格朗日函數(shù)，通過KKT條件分別求得其對偶問題如公式（4）和（5）[6]所示。

3 基于PSO的TWSVM分類算法

在TWSVM中，與SVM相同，都需要對參數(shù)進行確定，TWSVM對每個類均有一個懲罰參數(shù)和核函數(shù)參數(shù)。不同的懲罰參數(shù)和核函數(shù)參數(shù)影響分類的準確率，而PSO算法擁有全局的優(yōu)化能力，因此，本文將PSO算法引入TWSVM中，解決TWSVM參數(shù)的選擇問題，PSOTWSVM算法不僅能提高TWSVM的準確率同時又能降低SVM的訓練時間，提高訓練效率。圖2展示了應用PSO算法對TWSVM參數(shù)選擇的優(yōu)化流程。

基于PSOTWSVM分類算法：①根據(jù)樣本訓練數(shù)據(jù)集每個類別，隨機選定懲罰參數(shù)Cm，m=1，2，…，k以及核函數(shù)；②應用PSO算法對訓練進行參數(shù)優(yōu)化，找出最佳懲罰參數(shù)和核函數(shù)參數(shù)的最優(yōu)值；③利用公式（3）、（4）求解樣本數(shù)據(jù)對偶問題，構(gòu)造樣本空間的逼近超平面F（x）i=1，2，…k=K（x，c）wi+bi；④對每一類樣本數(shù)據(jù)求得逼近超平面后，再求解判別函數(shù)（10）；⑤將測試樣本數(shù)據(jù)集利用判別函數(shù)進行分類預測。

傳統(tǒng)SVM是基于二分類提出的，其復雜度為O（n3），其中n為樣本數(shù)目[2]。然而在TWSVM二分類算法中，設(shè)每類樣本數(shù)據(jù)為n/2，因此，求解兩個優(yōu)化問題時間復雜度為：O（2*（n/2）3），所以在二分類問題中的TWSVM時間復雜度為傳統(tǒng)SVM的1/4。推廣到多分類問題時，可以發(fā)現(xiàn)在時間復雜度方面，TWSVM求解優(yōu)化問題的時間更少。例如樣本類別數(shù)為k類，那么該樣本的時間復雜度為O（k*（n/k）3）。由于TWSVM分類算法對每類都構(gòu)造一個超平面，因此該算法在處理不平衡數(shù)據(jù)時，即一類的樣本數(shù)目比另一類的樣本大得多情況時，TWSVM分別實施不同的懲罰因子，TWSVM克服了傳統(tǒng)的SVM處理不均衡樣本的局限性，這一點非常適用于大規(guī)模的不均衡分類問題。

4 算法仿真實驗

為驗證基于PSO的TWSVM分類算法的有效性，本文利用該算法構(gòu)建一個文本分類器，運用不同數(shù)據(jù)集在該分類器上進行實驗并與標準支持向量機構(gòu)建的分類器進行對比仿真實驗。

4.1 分類器性能評價

常用的分類器評價方法包括：準確率和召回率。這兩個指標廣泛應用于文本分類系統(tǒng)的評價標準。準確率（Precision）是指全部分類文本中劃分的類別與實際類別相同的文本數(shù)量占全部文本的比率。召回率（Recall）是指分類正確的文本數(shù)占應有文檔數(shù)的比率。文本分類輸出結(jié)果見表1。

4.2 實驗結(jié)果分析

本實驗所采用的文本數(shù)據(jù)為搜狗分類新聞語料庫（Sogounews）（選取其中一類進行）和20組新聞數(shù)據(jù)（經(jīng)典的文本分類數(shù)據(jù)集）。搜狗新聞數(shù)據(jù)預處理的特征詞選擇方法為IG（信息增益），該實驗數(shù)據(jù)包含150個文本特征屬性，樣本數(shù)據(jù)為1600，其中1000為訓練集，600為測試集，數(shù)據(jù)集分別為新聞、非新聞兩類。News20選擇臺灣大學林智仁教授整理后的News20數(shù)據(jù)集作為實驗數(shù)據(jù)，整理后的News20樣本數(shù)規(guī)模和特征項較高，所以只選取了其中的800個文本樣本并對特征項進行降維處理后進行實驗，驗證TWSVM分類算法和基于PSO的TWSVM分類算法性能。實驗采用的核函數(shù)是線性核函數(shù)，初始懲罰參數(shù)和核參數(shù)分別為2和0.1，粒子群種群數(shù)量為30，迭代次數(shù)200，c1和c2取值均為1.5，實驗結(jié)果如表2所示。

由表2可知，PSOTWSVM的分類性能比TWSVM要好。因此，基于PSO的TWSVM是一個有效算法。該算法不但比標準的SVM算法訓練時間更短，而且比TWSVM有更好的準確率，PSOTWSVM解決了TWSVM的參數(shù)選擇問題，提高了TWSVM的泛化性。

5 結(jié)語

通過基于PSO的TWSVM分類算法與TWSVM算法的分類對比實驗可知，應用PSO算法的全局尋優(yōu)能力提高了TWSVM分類的能力。PSO優(yōu)化后TWSVM分類器的性能更為優(yōu)越。基于PSO的TWSVM分類算法比標準的SVM時間復雜度更小，比TWSVM的準確率更高，基于PSO的TWSVM算法在分類問題上較之傳統(tǒng)的SVM算法有更大的優(yōu)越性。

參考文獻：

[1]許國根，賈瑛.模式識別與智能計算的MATLAB實現(xiàn)[M]. 北京：北京航空航天大學出版社，2012.

[2]JAYADEVA，R KHEMCHANDAN， S CHANDRA.Twin support vector machines for pattern Classification[J]. IEEE Trans. Pattern and Machine Intelligence，2007，29（5）：905910.

[3]SHIFEI DING， JUNZHAO YU， BINGJUAN QI，et al. An overview on twin support vector machines[J]. Springer Science Business Media. August 2014，2（42）： 245252.

[4]谷文成，柴寶仁，騰艷平. 基于粒子群優(yōu)化算法的支持向量機研究[J].北京理工大學學報，2014， 34（7）：705 709.

[5]M A KUMAR，M GOPAL.Application of smoothing technique on twin support vector machines[J]. Pattern Recognition Letters， 2008，29（13）：18421848.

[6]王振.基于非平行超平面支持向量機的分類問題研究[D].長春：吉林大學，2014.

[7]M ARUN KUMAR，M GOPAL. Least squares twin support vector machines for pattern classification[J]. Expert Systems with Applications， 2009，4（ 36）： 75357543.

[8]YUAN HAI SHAO，ZHEN WANG，WEI JIE CHEN，et al. A regularization for the projection twin support vector machine[J]. KnowledgeBased Systems，2013：3（37）：203210.

[9]QIAOLIN CHUN， XIAZHAO YE， SHANGBING GAO，et al. Weighted twin support vector machines with local information and its application[J].Neural Networks，2012：12（8）：3139.

責任編輯（責任編輯：杜能鋼）

英文摘要Abstract：This paper researches on the Support Vector Machines training time for long， This paper proposes a twin support vector machine algorithm based on particle warm optimization. Different from the standard support vector machine， The time complexity of the twin support vector machine algorithm based on particle warm optimization is less than the standard support vector machine and it is particularly suitable for uneven data sample classification problems. In particular， having a great advantage for solving largescale data classification problem. In order to verify the validity of the algorithm the paper proposed， Comparison of experimental on text datasets show that twin support vector machine algorithm based on particle swarm optimization is better than the standard support vector machine classifier. Comparison of experimental data on different text datasets show that TWSVM algorithm based on particle swarm optimization and better performance than standard SVM.

英文關(guān)鍵詞Key Words： Twin Support Vector Machine（TWSVM）；Text Categorization；Particle Swarm Optimization（PSO）