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

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

DOIDOI：10.11907/rjdk.151455

中圖分類號：TP312

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

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

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

0 引言

粒子群優(yōu)化算法[1]（Particle Swarm Optimization，PSO）是由美國研究學(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)化問題、數(shù)據(jù)挖掘、模式識別，工程計(jì)算等研究領(lǐng)域。

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

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

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

1 PSO算法

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

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

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

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

3 基于PSO的TWSVM分類算法

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

基于PSOTWSVM分類算法：①根據(jù)樣本訓(xùn)練數(shù)據(jù)集每個類別，隨機(jī)選定懲罰參數(shù)Cm，m=1，2，…，k以及核函數(shù)；②應(yīng)用PSO算法對訓(xùn)練進(jìn)行參數(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ù)進(jìn)行分類預(yù)測。

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

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

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

4.1 分類器性能評價(jià)

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

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

本實(shí)驗(yàn)所采用的文本數(shù)據(jù)為搜狗分類新聞?wù)Z料庫（Sogounews）（選取其中一類進(jìn)行）和20組新聞數(shù)據(jù)（經(jīng)典的文本分類數(shù)據(jù)集）。搜狗新聞數(shù)據(jù)預(yù)處理的特征詞選擇方法為IG（信息增益），該實(shí)驗(yàn)數(shù)據(jù)包含150個文本特征屬性，樣本數(shù)據(jù)為1600，其中1000為訓(xùn)練集，600為測試集，數(shù)據(jù)集分別為新聞、非新聞兩類。News20選擇臺灣大學(xué)林智仁教授整理后的News20數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，整理后的News20樣本數(shù)規(guī)模和特征項(xiàng)較高，所以只選取了其中的800個文本樣本并對特征項(xiàng)進(jìn)行降維處理后進(jìn)行實(shí)驗(yàn)，驗(yàn)證TWSVM分類算法和基于PSO的TWSVM分類算法性能。實(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的分類性能比TWSVM要好。因此，基于PSO的TWSVM是一個有效算法。該算法不但比標(biāo)準(zhǔn)的SVM算法訓(xùn)練時(shí)間更短，而且比TWSVM有更好的準(zhǔn)確率，PSOTWSVM解決了TWSVM的參數(shù)選擇問題，提高了TWSVM的泛化性。

5 結(jié)語

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

參考文獻(xiàn)：

[1]許國根，賈瑛.模式識別與智能計(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ī)的分類問題研究[D].長春：吉林大學(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）