摘要：針對(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à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]。
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)化流程。
傳統(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é)果分析
由表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)：
[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ī)研究[J].北京理工大學(xué)學(xué)報(bào)，2014， 34（7）：705 709.
[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.
【論文：基于粒子群算法的雙子支持向量機(jī)研究】相關(guān)文章：
基于支持向量回歸機(jī)的復(fù)雜產(chǎn)品費(fèi)用估算技術(shù)發(fā)展研究論文02-11
基于遺傳算法的車(chē)牌定位技術(shù)研究論文04-16
基于大氣散射理論的視頻去霧算法的研究論文06-16
向量運(yùn)算法則09-29
基于單片機(jī)溫控智能風(fēng)扇的設(shè)計(jì)研究論文04-15
基于遺傳算法的優(yōu)化設(shè)計(jì)論文04-22