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

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

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

DOIDOI：10.11907/rjdk.151455

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：16727800（2015）006007204

基金項(xiàng)目：玉林師范學(xué)院校級(jí)科研項(xiàng)目（2014YJYB04）

作者簡(jiǎn)介作者簡(jiǎn)介：劉建明（1986-），男，廣西博白人，碩士，玉林師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院助教，研究方向?yàn)閿?shù)據(jù)挖掘與機(jī)器學(xué)習(xí)。

0 引言

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

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

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

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

1 PSO算法

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

2 雙子支持向量機(jī)（TWSVM）

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

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

3 基于PSO的TWSVM分類(lèi)算法

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

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

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

4 算法仿真實(shí)驗(yàn)

為驗(yàn)證基于PSO的TWSVM分類(lèi)算法的有效性，本文利用該算法構(gòu)建一個(gè)文本分類(lèi)器，運(yùn)用不同數(shù)據(jù)集在該分類(lèi)器上進(jìn)行實(shí)驗(yàn)并與標(biāo)準(zhǔn)支持向量機(jī)構(gòu)建的分類(lèi)器進(jìn)行對(duì)比仿真實(shí)驗(yàn)。

4.1 分類(lèi)器性能評(píng)價(jià)

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

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

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

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

5 結(jié)語(yǔ)

通過(guò)基于PSO的TWSVM分類(lèi)算法與TWSVM算法的分類(lèi)對(duì)比實(shí)驗(yàn)可知，應(yīng)用PSO算法的全局尋優(yōu)能力提高了TWSVM分類(lèi)的能力。PSO優(yōu)化后TWSVM分類(lèi)器的性能更為優(yōu)越?；赑SO的TWSVM分類(lèi)算法比標(biāo)準(zhǔn)的SVM時(shí)間復(fù)雜度更小，比TWSVM的準(zhǔn)確率更高，基于PSO的TWSVM算法在分類(lèi)問(wèn)題上較之傳統(tǒng)的SVM算法有更大的優(yōu)越性。

參考文獻(xiàn)：

[1]許國(guó)根，賈瑛.模式識(shí)別與智能計(jì)算的MATLAB實(shí)現(xiàn)[M]. 北京：北京航空航天大學(xué)出版社，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ī)研究[J].北京理工大學(xué)學(xué)報(bào)，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]王振.基于非平行超平面支持向量機(jī)的分類(lèi)問(wèn)題研究[D].長(zhǎng)春：吉林大學(xué)，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.

責(zé)任編輯（責(zé)任編輯：杜能鋼）

英文摘要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）