一種快速加權(quán)支持向量機訓(xùn)練算法

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

關(guān)鍵詞：加權(quán)支持向量機； 工作集； 目標(biāo)函數(shù)

中圖分類號：TP301文獻標(biāo)志碼：A

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

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

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

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

1W－SVM的數(shù)學(xué)模型

2加權(quán)支持向量機的最優(yōu)性條件

定理1α滿足最優(yōu)性條件，當(dāng)且僅當(dāng)不存在任何違反對。

3利用目標(biāo)函數(shù)的二階信息進行工作集選擇加權(quán)支持向量機訓(xùn)練算法

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

4實驗結(jié)果及分析

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

從圖2中可以得出如下結(jié)論：

(1)利用目標(biāo)函數(shù)的二階信息選擇工作集訓(xùn)練加權(quán)支持向量機比利用目標(biāo)函數(shù)的一階近似信息選擇工作集訓(xùn)練加權(quán)支持向量機在迭代次數(shù)上有更大的優(yōu)勢。

5結(jié)束語

本文提出了利用目標(biāo)函數(shù)的二階信息選擇工作集訓(xùn)練加權(quán)支持向量機算法。實驗結(jié)果表明，當(dāng)問題規(guī)模較大時，它比利用目標(biāo)函數(shù)的一階近似信息選擇工作集訓(xùn)練加權(quán)支持向量機有更快的收斂速度。因此當(dāng)訓(xùn)練問題較大時，它是一種更加優(yōu)秀的加權(quán)支持向量機訓(xùn)練算法。

參考文獻：

[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.

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