基于ＱＰＳＯ算法訓練ＳＶＭ

摘要：針對群體智能和約束優化問題的特點，提出了將QPSO算法應用于求解約束優化問題，證明QPSO算法在SVM領域中具有很高的應用價值，并為解決大規模的QP問題開辟了一條新的途徑。

關鍵詞：支持向量機； 量子行為粒子群優化； 二次規劃

中圖分類號：TP301.6文獻標志碼：A

文章編號：1001－3695(2007)07－0094－03

支持向量機(Support Vector Machine，SVM)是在統計學習理論基礎上提出的一種全新的機器學習方法，以結構風險最小化原則為理論基礎，將最大分界面分類器思想和基于核的方法結合在一起，表現出了很好的泛化能力。SVM在1995年由Vapnik 等人提出后，由于其出色的學習性能，該技術已成為機器學習界的研究熱點，在機器學習理論和實踐中都有巨大的發展，體現了其重要的意義。

訓練支持向量機主要解決一個二次規劃(QP)問題。經典的二次規劃方法一般無法解決實際問題，尤其是大規模的實際問題，這直接影響著支持向量機的實際應用。因此，近年來很多研究者對SVM優化算法的研究非常重視，將進化算法用于優化二次規劃問題，以期加深和擴大SVM應用領域的研究。在原始的粒子群算法（PSO）基礎上，筆者從量子的角度提出了一種新型的能保證全局收斂的進化算法——具有量子行為的粒子群優化算法（QPSO）。QPSO算法不僅調整參數少、容易實現，而且搜索效率高，比以往進化算法的全局收斂能力都要強，其魯棒性強、實現時間短。

1SVM原理

支持向量機主要解決的是一個二分類問題。該理論最初來源于數據分類問題的處理，SVM 就是要尋找一個滿足要求的分割平面，使訓練集中的點距離該平面盡可能地遠，即尋求一個分割平面使其兩側的Margin盡可能最大。支持向量機從線性可分情況下的最優分類面發展起來，通過將輸入空間映射到一個高維內積空間中，解決一個線性約束的二次規劃問題，得到全局最優解，保證收斂速度。它不存在局部極小值問題。

2支持向量機的優化算法

隨著支持向量機的發展，出現了很多優化算法。如果訓練樣本的規模過大，矩陣H的規模是訓練樣本的平方，求解Lagrange乘子QP問題的優化算法很難處理。為了解決大規模問題，人們提出了以下算法。

最初為解決大規模SVM，Vapnik采用求解矩陣分塊的算法，算法中刪除矩陣中對應Lagrange 乘子為零的行與列，它不會影響最終結果，因此大型QP問題可轉換為一系列的小規模QP問題。該算法的每一步解決一個QP問題，其樣本為上一步所剩的具有非零Lagrange 乘子的樣本與不滿足Kuhn－Tucker 條件的M（事先確定）個樣本（若不滿足Kuhn－Tucker條件的樣本小于M個，則這些樣本全部加入）。每一個子QP 問題都在前一個子QP 問題結果的基礎上進行。這樣，Chunking算法就將矩陣規模由樣本個數的平方減少到具有非零Lagrange乘子的樣本個數的平方，大大提高了算法效率。

與分塊算法不同，分解算法每次迭代只更新若干個Lagrange乘子，而其他的乘子保持不變。將SVM中大型的QP問題轉換為一系列的求解規模一定的子QP問題，每一步都保持問題滿足Kuhn－Tucker條件。迭代過程中將工作集之外情況最糟的樣本點和工作集中的一部分樣本點進行等量交換，重新優化這個子問題，直到所有Lagrange乘子都滿足Kuhn－Tucker條件，得到問題的最優解。

最小優化算法(Sequential Minimal Optimization，SMO)是分解算法的一個特例。它將工作樣本集的規模減小到了兩個樣本，迭代過程中直接進行求解，提高了子問題的運算速度。此外，SMO算法的工作集選擇采用啟發式，通過兩個嵌套的循環來尋找待優化的樣本；外層循環尋找違反KKT條件的樣本，作為工作集的第一個樣本。內層循環開始選擇進入工作集的第二個樣本，選擇的原則是盡量使這樣一對樣本取得最大的優化步長。這種啟發式的樣本選擇策略大大加快了算法收斂速度。

SVMlight算法是分解算法的一個推廣。其基本思想是：將所求問題的Lagrange乘子分為工作集和非工作集；如果存在不滿足Kuhn－Tucker條件的樣本，基于某種方式選擇q個樣本的拉格朗日乘子作為工作集，其余樣本的拉格朗日乘子保持不變，作為非工作集。在這個工作集上解決QP問題。重復以上操作，直到所有樣本點都滿足Kuhn－Tucker條件。工作集的選取基于可行方向法。

3QPSO

QPSO是Sun等人[2，3]從量子力學的角度，通過對粒子收斂行為的研究，基于粒子群算法提出的一種新的算法模型。在QPSO算法中，由于粒子滿足聚集態的性質完全不同，使粒子在整個可行解空間中進行搜索尋求全局最優解。QPSO算法在搜索能力上遠遠優于所有已開發的PSO算法。

在QPSO算法中，粒子的狀態只需用位置向量來描述，并且算法中只有一個控制參數a。對這個參數的選擇和控制是非常重要的，它關系到整個算法的收斂速度。

4基于QPSO算法訓練支持向量機

求解二次規劃問題是SVM訓練算法最核心、最主要的問題。工作集的選擇策略、最優性能的Kuhn－Tucker條件，用QPSO算法優化SVM子問題構成了實現支持向量分類的主體框架。

其中：g(a(t))為式（2）目標函數在a(t)點的一階偏導數；d為所求的可行方向。第一個約束是為了使所選擇的樣本點對應的di和yi符號相同的數量與di和yi符號不同的數量相等。方向d的選擇使函數g(a(t))′d達到最小值。第四個約束使可行性方向標準化。最后一個約束要求使所求得的方向包含q個Lagrange乘子。完整的方法可參考文獻[4]。

5實驗結果

本實驗采用檢驗分類算法性能的標準數據集鳶尾屬植物數據集(Iris Data Set)。該數據集共150個樣本點，分為三種，每種樣本集各50個樣本點，每個樣本有萼片長度、萼片寬度、花瓣長度和花瓣寬度四個特征值。

為了體現工作集規模的選擇對結果的影響，表1給出了核函數為徑向基核函數，QPSO算法在選擇不同規模的工作集時，運行的時間及支持向量的數目。同時，把PSO算法和QPSO算法進行了比較，如表2所示。兩種算法參數設置簡單、容易操作，但在求解QP問題時，PSO算法在訓練時間上明顯不如QPSO算法，最后所得到的W（αB）更小。

實驗顯示QPSO算法對訓練SVM有更好的效果。在實驗中也觀察到，核函數的選取和懲罰參數C的選擇同樣對實驗結果有重要的影響。

6結束語

實驗結果表明，QPSO具有優良的性能，可用于訓練支持向量機，有效地對樣本進行分類；QPSO算法的一些性能對優化約束QP問題有很好的表現。其參數設置少、操作簡單、收斂速度快，可以有效地應用在大規模樣本的二次規劃問題中，為訓練大規模樣本提供一條新途徑。

參考文獻：

[1]RAQUET U， ENGELBRECHT A P. Training support vector machines with particle swarms: proc.of the Int Joint Coreference on Neural Network[C]. Portland: IEEE Worold Congresson Computer Intelligence， 2003:1593－1598.

[2]SUN Jun， XU Wenbo. A global search strategy of quantum－behaved particle swarm optimization: proc.of IEEE Conference on Cybernetics and Intelligent Systems[C].Singapore:[s.n.]， 2004:111－116.

[3]SUN Jun， FENG Bin， XU Wenbo. Particle swarm optimization with particles having quantum behavior: proc.of Congress on Evolutionary Computation. 2004:325－331.

[4]JOACHIMS T. Making large－scale SVM learning practical[C]//SCHOLKOPF B， BURGES C J C， SMOLA A J. Advances in Kernel MethodsSupport Vector Learning. Cambridge: MIT Press， 1999:169－184.

[5]鄧乃揚，田英杰.數據挖掘中的新方法——支持向量機[M].北京:科學出版社，2004:328－335.

[6]曾建潮，介婧，崔志華.微粒群算法[M].北京:科學出版社，2004:85－87.

[7]宋曉峰，陳德釗，俞歡軍，等.支持向量機中優化算法[J].計算機科學，2003，30(3):1029－1035.

[8]王平，毛劍琴.支持向量機訓練算法及其應用[J].信息與電子工程，2005，3(4):309－314.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”