王云英，閻滿富

（1. 唐山市第十中學，河北 唐山 063000；2. 唐山師范學院 數(shù)學與信息科學系，河北 唐山 063000）

C-支持向量機及其改進

王云英1，閻滿富2

（1. 唐山市第十中學，河北 唐山 063000；2. 唐山師范學院 數(shù)學與信息科學系，河北 唐山 063000）

支持向量機是19世紀90年代由美國貝爾實驗室的Cortes和Vapnik首先提出來的一種新算法。介紹C-支持向量機，并在此基礎(chǔ)上，構(gòu)建其改進模型，目的是給出易于求解的幾類新算法。

支持向量機；改進；分類

1 引言

支持向量機（Spport Vector Machine，簡稱SVM）是基于統(tǒng)計學習理論[1]借助最優(yōu)化算法[2]來解決機器學習問題的新工具，是由Cortes和Vapni于上個世紀90年代首先提出，現(xiàn)已成為近年來機器學習研究的一項重大成果。目前對支持向量機的研究主要集中在對其本身性的研究和完善以及加大應(yīng)用研究的深度和廣度兩方面。C-支持向量機分類是求解分類問題的最基本算法，為了在解決實際分類問題時，有更有效和針對性更強的支持向量機模型，有必要研究支持向量機更多的分類模型和算法。這里先介紹C-支持向量機，在此基礎(chǔ)上給出三類C-支持向量機分類機的改進算法。

2 C-支持向量分類機及其改進

2.1 C-支持向量分類機

設(shè)已知訓(xùn)練集

其中xi∈X=Rn，yi∈Y={1,-1},i=1,L, l 。對于這樣的分類問題，首先引進從輸入空間Rn到Hilbert空間H的其中K(xi,xj)為應(yīng)于變換(2)的核函數(shù)

通過求解上述對偶問題得最優(yōu)解

選取α*的一個正分量0＜α*j＜C，并據(jù)此計算閾值

最后構(gòu)造決策函數(shù)

該算法稱為C-支持向量分類機。

2.2 C-支持向量分類機的變形

原始問題(4)-(6)中，目標函數(shù)是

如果用

來代替

原始問題就變?yōu)槠渲蠧＞0。

原始問題(13)-(15)的對偶問題為其中

選取α*的一個正分量α*j＞0，并據(jù)此計算閾值

2.3 有唯一解的C-SVM

在[3]中討論了標準C-支持向量分類機解的唯一性，給出了決策函數(shù)中b的不唯一的條件和求解公式，如果將目標函數(shù)(4)中加上一項1/2b2，則原始問題變?yōu)?/p>

其中C＞0。

問題(22)-(24)的對偶問題為

這是有唯一解的優(yōu)化問題，與標準的C-SVM比較，該對偶問題少了等式約束條件，適合迭代求解，同時應(yīng)用矩陣分解技術(shù)，每次只需更新α的一個分量，提高了計算速度。

2.4 無約束的C-SVM[4]

其中函數(shù)(·)+是單變量函數(shù)

把(30)代入到(27)中，就得到了無約束最優(yōu)化問題

上述問題是嚴格凸的無約束最優(yōu)化問題，它有唯一的最優(yōu)解。函數(shù)(·)+是不可微的，需要用非光滑的無約束最優(yōu)化方法求解。

如果希望用通常的無約束最優(yōu)化方法求解，則考慮對目標函數(shù)進行光滑化，得到近似的最優(yōu)化問題

當λ充分大時，光滑無約束問題(33)-(34)的解會近似于非光滑無約束問題(32)的解。

通過引入核函數(shù)，并用

該問題的目標函數(shù)具有連續(xù)的梯度和Hesse矩陣，而且是無約束的，可以用基本的無約束問題算法來求解。求得最優(yōu)解(α*,b*)后，便可構(gòu)造出決策函數(shù)

3 總結(jié)

以上給出的是求解分類問題的支持向量機的幾種主要算法。每種算法都有其特性和優(yōu)勢，或者有一定范圍的優(yōu)化算法來求解。有唯一解的C-支持向量分類機，是在C-支持向量分類機的基礎(chǔ)上，對目標函數(shù)進行了改進，使其對偶問題變?yōu)椴坏仁郊s數(shù)問題，從而更適合于迭代求解，提高了運算速度。無約束的C-支持向量分類機是通過引入核函數(shù)，使一般約束問題轉(zhuǎn)化為帶有核的光滑無約束問題，新的最優(yōu)化問題，具有連續(xù)的梯度和Hesse矩陣，可以用最基本的無約束問題算法求解，而C-支持向量分類機的變形是給出兩種特殊支持向量分類機的基礎(chǔ)和過渡，為構(gòu)造新支持向量分類機提供了基本思想，同時有它自身的應(yīng)用范圍和價值。

[1]Vladimir N Vapnik. Statistical hearning Theory[M]. 北京:電子工業(yè)出版社,2004.

[2]解可新,韓健.林友聯(lián).最優(yōu)化算法[M].天津:天津大學出版社,2004.

[3]鄧乃楊,田英杰.支持向量機理論,算法與推展[M].北京:科學出版社,2009.

[4]楊志民,劉廣利.不確定性支持向量機[M].北京:科學出版社,2012.

（責任編輯、校對：趙光峰）

C-Spport Vector Machine and Its Improvements

WANG Yun-ying1, Yan Man-fu2
4 No. 10 Middle School of Tangshang, Tangshan 063000, China; 2. Department of Mathematics and Information Science, Tangshan Teachers College, Tangshan 063000, China)

Support Vector Machine is a new algorithm first proposed during 1990s by Cortes and Vapnik in American Bell Labs. Here we introduce C-Spport Vector Machine and construct its improvement model on this basis in order to provide several new algorithms which can be easily solved.

support-vector machine; improvement; classification

TJ81+0.35

A

1009-9115(2012)05-0041-03

2012-08-05

王云英（1982-），女，河北撫寧人，中學二級，研究方向為信息技術(shù)。

閻滿富（1958-），男，河北豐南人，博士，教授，研究方向為運籌與優(yōu)化。