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