一種快速加權支持向量機訓練算法

摘要：給出了一種利用目標函數的二階信息選擇工作集訓練加權支持向量機的算法，導出了加權支持向量機的KKT條件。實驗結果表明，與利用目標函數的一階近似信息選擇工作集的訓練算法相比，該算法減少了訓練迭代次數，特別是訓練集規模較大時，該算法的收斂速度有較大幅度的提高。

關鍵詞：加權支持向量機； 工作集； 目標函數

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

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

支持向量機（Support Vector Machine，SVM）是解決分類和回歸問題的一種新的數據挖掘技術。它是基于結構風險最小化原則，根據有限樣本信息在模型的復雜度和學習能力之間尋求最佳的折中，以取得最好的泛化能力[1]。它已廣泛應用于文本分類[2]、人臉識別[3]、語音識別[4]等領域，并取得良好的效果。

標準支持向量機(C－SVM)中參數C的選擇對構造分類函數來說是至關重要的，它是樣本分類誤差的懲罰系數。不過在C－SVM中對于不同的樣本懲罰是相同的。但在實際應用中常常發現某些樣本重要性大，要求小的訓練誤差；而有些樣本的重要性相對低一些，容許一定大小的訓練誤差。例如股市預測、電力負荷預測等動態變化比較劇烈的時間序列預測問題，近期數據的重要性要遠遠高于早期數據的重要性。因此，在描述優化問題時，每個樣本應具有不同的誤差懲罰系數，即每個樣本的C應該是不同的，從而得到更準確的預測效果，即所謂的加權支持向量機。

加權支持向量機的數學模型很早就被提出[5]，但相應的訓練算法卻很少提出。加權支持向量機的訓練是求解一個帶有邊界約束和等式約束的二次規劃問題。對于此類問題的求解，目前主要采用SMO類型的分解算法，工作集的選擇對于該類算法非常重要，它直接關系著收斂速度的快慢。

1W－SVM的數學模型

2加權支持向量機的最優性條件

定理1α滿足最優性條件，當且僅當不存在任何違反對。

3利用目標函數的二階信息進行工作集選擇加權支持向量機訓練算法

加權支持向量機的訓練，即求解一個帶有邊界約束條件和等式約束條件的二次規劃問題。對于此類問題的求解，目前主要采用SMO類型的分解算法[6，7]來完成。

4實驗結果及分析

圖2是在不同的公共數據集上，利用目標函數的一階近似信息和二階信息選擇工作集訓練加權支持向量機的迭代次數和時間比較（緩存大小為0．1 MB和40 MB）。

從圖2中可以得出如下結論：

(1)利用目標函數的二階信息選擇工作集訓練加權支持向量機比利用目標函數的一階近似信息選擇工作集訓練加權支持向量機在迭代次數上有更大的優勢。

5結束語

本文提出了利用目標函數的二階信息選擇工作集訓練加權支持向量機算法。實驗結果表明，當問題規模較大時，它比利用目標函數的一階近似信息選擇工作集訓練加權支持向量機有更快的收斂速度。因此當訓練問題較大時，它是一種更加優秀的加權支持向量機訓練算法。

參考文獻：

[1]VAPNIK V. The nature of statistical learning theory[M]. New York: Springer， 1995.

[2]ZHUANG Dong， ZHANG Benyu， YANG Qiang. Efficient text classification by weighted proximal SVM: proc.of the 5th IEEE International Conference on Data Mining[C].New York: IEEE， 2005:538－545.

[3]HOTTA K. Support vector machine with local summation kernel for robust face recognition: proc.of the 17th International Conference on Pattern Recognition[C].New York: IEEE， 2004:482－485.

[4]GANAPATHIRAJU A， HAMAKER J E， PICONE J. Application of support vector machines to speech recognition[J]. IEEE Transaction on Signal Processing， 2004，52(8):2348－2355.

[5]LIU Shuang， JIA Chuanying， MA Heng. A new weighted support vector machine with GA－based parameter selection: proc.of the 4th International Conference on Machine Learning and Cybernetics[C].New York: IEEE， 2005:4351－4355.

[6]OSUNA E. An improved training algorithm for support vector machines: proc.of IEEE Workshop on Neural Networks for Signal Processing’97[C].New York:IEEE， 1997:276－285.

[7]PLATT J C. Fast training of support vector machines using sequential minimal optimization: Advances in Kernel Method－Support Vector Learning[C].Cambridge: MIT Press， 1998:185－208.

[8]JOACHIMS T. Making large－scale support vector machine learning practical: Advances in Kernel Methods－Support Vector Learning[C].Cambridge: MIT Press， 1998:169－184.

[9]KEERTHI S S， SHEVADE S K， BHATTACHAYYA C， et al. Improvements to Platt’s SMO algorithm for SVM classifier design[J]. Neural Computation， 2001，13(3):637－649.

[10]FAN Rongen， CHEN Paihsuen， LIN Chihjen. Working set selection using second order information for training support vector machines[J]. Journal of Machine Learning Research， 2005(6):1855－1884.

[11]CHANG Chinchang， LIN Chihjen. LIBSVM: a library for support vector machines[EB/OL].[2005].http://www.csie.ntu.tw/~cjlin/libsvm.

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