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