論文：基于粒子群算法的雙子支持向量機研究
摘要：針對標(biāo)準(zhǔn)支持向量機訓(xùn)練時間過長與參數(shù)選擇無指導(dǎo)性問題，給出一種通過粒子群優(yōu)化雙支持向量機模型參數(shù)的方法。與標(biāo)準(zhǔn)支持向量機不同，該方法的時間復(fù)雜度更小，特別適合不均衡的數(shù)據(jù)樣本分類問題，對求解大規(guī)模的數(shù)據(jù)分類問題有很大優(yōu)勢。將該算法與標(biāo)準(zhǔn)的支持向量機分類器在不同的文本數(shù)據(jù)集上進(jìn)行仿真實驗對比，以驗證算法的有效性。結(jié)果表明基于粒子群優(yōu)化的雙子支持向量機分類器的分類結(jié)果高于標(biāo)準(zhǔn)支持向量機分類結(jié)果。
關(guān)鍵詞：雙子支持向量機（TWSVM）；分類算法；粒子群優(yōu)化算法（PSO）
DOIDOI：10.11907/rjdk.151455
中圖分類號：TP312
基金項目：玉林師范學(xué)院校級科研項目（2014YJYB04）
作者簡介作者簡介：劉建明（1986-），男，廣西博白人，碩士，玉林師范學(xué)院數(shù)學(xué)與信息科學(xué)學(xué)院助教，研究方向為數(shù)據(jù)挖掘與機器學(xué)習(xí)。
0 引言
粒子群優(yōu)化算法[1]（Particle Swarm Optimization，PSO）是由美國研究學(xué)者Kennedy等人在1995年提出的，PSO算法每一代的種群中的解具有向“他人”學(xué)習(xí)和“自我”學(xué)習(xí)的優(yōu)點，該算法能在較少的迭代次數(shù)中找到全局最優(yōu)解，這一特性被廣泛應(yīng)用于神經(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)計學(xué)習(xí)理論的機器學(xué)習(xí)算法。TWSVM具有SVM優(yōu)點，同時適合處理像文本自動分類、基因表達(dá)、空間信息遙感數(shù)據(jù)、語音識別等這樣的大規(guī)模數(shù)據(jù)分類問題。
針對TWSVM對懲罰參數(shù)和核函數(shù)參數(shù)缺乏指導(dǎo)性問題，本文結(jié)合PSO算法的優(yōu)點，給出一種基于PSO的
算法優(yōu)化改進(jìn)策略，對TWSVM分類器進(jìn)行優(yōu)化。PSO是一種基于群體智能的全局尋優(yōu)算法，該算法能在較少的迭代次數(shù)中找到全局最優(yōu)解，通過利用粒子群優(yōu)化算法對雙子支持向量機進(jìn)行優(yōu)化后，分類器較之標(biāo)準(zhǔn)支持向量機有更好的分類效果。
1 PSO算法
PSO算法步驟：①初始化粒子群，利用隨機函數(shù)法給每一個粒子的初始位置和速度賦值；②根據(jù)第①步的賦值及初始位置與速度更新每一個粒子新的位置；③利用選定的適應(yīng)度函數(shù)計算每一個粒子的適應(yīng)度值；④對每一個粒子，對比其個體和群體的適應(yīng)度值，并找出粒子經(jīng)過的最好位置的適應(yīng)度值，如果發(fā)現(xiàn)更好的位置及適應(yīng)度值，那么就更新其位置；⑤根據(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ù)點，而同時盡可能地遠(yuǎn)離另一類樣本數(shù)據(jù)點。新數(shù)據(jù)樣本將會分配給離兩個超平面中最近的一個平面。事實上，該算法還可以沿著非平行面聚集，而且樣本聚集方式是根據(jù)完全不同的公式聚合而成的。實際上，在TWSVM中的兩個QP問題與標(biāo)準(zhǔn)SVM的QP問題除了求解約束問題不同外，求解公式是相同的。TWSVM的二分類算法通過求解下面的一對QPP（Quadratic Program Problem）問題進(jìn)行二次規(guī)劃優(yōu)化[5]。
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)確率同時又能降低SVM的訓(xùn)練時間，提高訓(xùn)練效率。圖2展示了應(yīng)用PSO算法對TWSVM參數(shù)選擇的優(yōu)化流程。
傳統(tǒng)SVM是基于二分類提出的，其復(fù)雜度為O（n3），其中n為樣本數(shù)目[2]。然而在TWSVM二分類算法中，設(shè)每類樣本數(shù)據(jù)為n/2，因此，求解兩個優(yōu)化問題時間復(fù)雜度為：O（2*（n/2）3），所以在二分類問題中的TWSVM時間復(fù)雜度為傳統(tǒng)SVM的1/4。推廣到多分類問題時，可以發(fā)現(xiàn)在時間復(fù)雜度方面，TWSVM求解優(yōu)化問題的時間更少。例如樣本類別數(shù)為k類，那么該樣本的時間復(fù)雜度為O（k*（n/k）3）。由于TWSVM分類算法對每類都構(gòu)造一個超平面，因此該算法在處理不平衡數(shù)據(jù)時，即一類的樣本數(shù)目比另一類的樣本大得多情況時，TWSVM分別實施不同的懲罰因子，TWSVM克服了傳統(tǒng)的SVM處理不均衡樣本的局限性，這一點非常適用于大規(guī)模的不均衡分類問題。 4 算法仿真實驗
為驗證基于PSO的TWSVM分類算法的有效性，本文利用該算法構(gòu)建一個文本分類器，運用不同數(shù)據(jù)集在該分類器上進(jìn)行實驗并與標(biāo)準(zhǔn)支持向量機構(gòu)建的分類器進(jìn)行對比仿真實驗。
4.1 分類器性能評價
常用的分類器評價方法包括：準(zhǔn)確率和召回率。這兩個指標(biāo)廣泛應(yīng)用于文本分類系統(tǒng)的評價標(biāo)準(zhǔn)。準(zhǔn)確率（Precision）是指全部分類文本中劃分的類別與實際類別相同的文本數(shù)量占全部文本的比率。召回率（Recall）是指分類正確的文本數(shù)占應(yīng)有文檔數(shù)的比率。文本分類輸出結(jié)果見表1。
4.2 實驗結(jié)果分析
由表2可知，PSOTWSVM的分類性能比TWSVM要好。因此，基于PSO的TWSVM是一個有效算法。該算法不但比標(biāo)準(zhǔn)的SVM算法訓(xùn)練時間更短，而且比TWSVM有更好的準(zhǔn)確率，PSOTWSVM解決了TWSVM的參數(shù)選擇問題，提高了TWSVM的泛化性。
5 結(jié)語
通過基于PSO的TWSVM分類算法與TWSVM算法的分類對比實驗可知，應(yīng)用PSO算法的全局尋優(yōu)能力提高了TWSVM分類的能力。PSO優(yōu)化后TWSVM分類器的性能更為優(yōu)越。基于PSO的TWSVM分類算法比標(biāo)準(zhǔn)的SVM時間復(fù)雜度更小，比TWSVM的準(zhǔn)確率更高，基于PSO的TWSVM算法在分類問題上較之傳統(tǒng)的SVM算法有更大的優(yōu)越性。
參考文獻(xiàn)：
[2]JAYADEVA，R KHEMCHANDAN， S CHANDRA.Twin support vector machines for pattern Classification[J]. IEEE Trans. Pattern and Machine Intelligence，2007，29（5）：905910.
[4]谷文成，柴寶仁，騰艷平. 基于粒子群優(yōu)化算法的支持向量機研究[J].北京理工大學(xué)學(xué)報，2014， 34（7）：705 709.
[6]王振.基于非平行超平面支持向量機的分類問題研究[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.
【論文：基于粒子群算法的雙子支持向量機研究】相關(guān)文章：
基于支持向量回歸機的復(fù)雜產(chǎn)品費用估算技術(shù)發(fā)展研究論文02-11
基于大氣散射理論的視頻去霧算法的研究論文06-16
向量運算法則09-29
基于單片機溫控智能風(fēng)扇的設(shè)計研究論文04-15
計數(shù)查找算法研究精選論文04-05