論文：基於粒子群演算法的雙子支援向量機研究
論文：基於粒子群演算法的雙子支援向量機研究
摘要：針對標準支援向量機訓練時間過長與引數選擇無指導性問題，給出一種透過粒子群最佳化雙支援向量機模型引數的方法。與標準支援向量機不同，該方法的時間複雜度更小，特別適合不均衡的資料樣本分類問題，對求解大規模的資料分類問題有很大優勢。將該演算法與標準的支援向量機分類器在不同的文字資料集上進行模擬實驗對比，以驗證演算法的有效性。結果表明基於粒子群最佳化的雙子支援向量機分類器的分類結果高於標準支援向量機分類結果。
關鍵詞：雙子支援向量機（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.