分段熵光滑支持向量機性能研究

吳 青，梁 勃

（1.西安郵電大學(xué) 自動化學(xué)院，陜西 西安710121；2.西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安710121）

0 引 言

與標(biāo)準(zhǔn)支持向量機 （SVM）［1－3］相比，光滑支持向量機（SSVM）［4，5］擁有更好的分類性能和效率，其中光滑函數(shù)起到了關(guān)鍵的作用。SSVM 優(yōu)化模型只有當(dāng)光滑參數(shù)α趨于無窮大時，才能逼近精確解。然而當(dāng)α取值較大時，又容易產(chǎn)生數(shù)據(jù)的溢出現(xiàn)象。采用熵函數(shù)法［6，7］訓(xùn)練SVM 的分類問題，可以避免數(shù)值的溢出現(xiàn)象。本文通過分析光滑支持向量機分類方法，應(yīng)用分段熵函數(shù)作為光滑函數(shù)，得到一種新的光滑支持向量機模型。該模型避免了數(shù)據(jù)溢出問題的發(fā)生。通過理論和數(shù)值實驗分析驗證了新模型的分類性能，表明其優(yōu)于SSVM 模型。

1 分段熵函數(shù)

定義1 定義如下分段熵函數(shù)

式中：t——光滑化參數(shù)。分段熵函數(shù)f（x，t）的一階導(dǎo)數(shù)和二階導(dǎo)數(shù)分別為

對于這個分段熵函數(shù)函數(shù)有如下定理：

定理1 對于任意x∈Rn和0＜t≤1，f（x，t）關(guān)于x任意階光滑。

證明：由光滑函數(shù)的定義及指數(shù)函數(shù)和對數(shù)函數(shù)的性質(zhì)，很容易得到f（x，k）≥x＋；當(dāng)x ≤0 時，f（x，t）＝；當(dāng)x＞0時，＝x；故f（x，t）＝x＋。

定理3 對于任意x ∈Rn和0＜t≤1，有f（x，t）2－≤t2。

證明：當(dāng)x≤0時，令Y1＝t2［log（1＋exp（））］2，對Y1求導(dǎo)得：，則Y1是單調(diào)遞增的，所以最大值在x＝0處取得，maxY1＝t2（log2）2≤t2；當(dāng)x＞0時，令由對數(shù)函數(shù)的性質(zhì)log（1＋x）≤x可得

所以Y2≤t2，結(jié)論成立。

2 分段熵光滑支持向量機

2.1 光滑支持向量機模型

考慮如下優(yōu)化問題

式中：C——平衡因子，e——單位矩陣，y——松弛變量，w——分類面法向量，A——訓(xùn)練樣本集，對角陣D——分類情形，b——分類面距原點的距離。該優(yōu)化問題即為標(biāo)準(zhǔn)的支持向量機模型。

標(biāo)準(zhǔn)SVM 模型的等價無約束優(yōu)化模型為

顯然，上述SVM 式 （5）的目標(biāo)函數(shù)F（w，b）具有強凸性，但該函數(shù)F（w，b）是Rn上的非光滑函數(shù)。因此，許多快速算法 （如Newton－Armijo算法）均不適用于該優(yōu)化問題。2001年，Lee等引用sigmoid函數(shù)的積分函數(shù)

對式（5）進行光滑處理得光滑支持向量機模型SSVM

提高了分類性能和效率。

使用光滑式 （1）對上述優(yōu)化式 （5）中的不可微部分進行光滑處理，得到一個新的分段熵函數(shù)光滑支持向量機模型 （PESSVM）如下

2.2 收斂性分析

定義2 給定某實數(shù)v，函數(shù)f（x）的水平集定義為Lv（f（x））＝｛x｜f（x）≤v｝。

定理4 Ft（w，b）是嚴(yán)格凸函數(shù)，對給定的t，存在唯一解。

定理5 標(biāo)準(zhǔn)SVM 優(yōu)化式 （5）解為x＊＝（w＊，b＊），分段熵函數(shù)光滑支持向量機優(yōu)化模型 （6）解為＝，），則：0≤Ft）－F（x＊）≤mt2。

證明：由f（x，t）≥x＋知，F(xiàn)t）－F（x＊）≥0，又因為f（x，t）2－≤t2，所以Ft）－F（x＊）≤mt2，得證。

定理6 設(shè)A ∈Rm×n，b∈Rm×1實函數(shù)定義如下

證明：f（x，t）≥x＋水平集Lv（h（x）），Lv（f（x，t））對任意的v≥0，Lv（f（x，t））Lv（h（x））｛x≤2v｝，因此Lv（h（x））和Lv（f（x，k））是Rn中的緊子集，并且f（x，t）和h（x）具有強凸性，解唯一

將上面兩式相加有

由f（x，t）2－≤t2得。。從而結(jié)論得證。

3 數(shù)值實驗

3.1 Newton－Armijo算法

分段熵函數(shù)支持向量機具有任意階可微的性質(zhì)，而Newton下降法［8］有二次收斂速度。因此，可以用快速Newton－Armijo算法進行訓(xùn)練，以使目標(biāo)函數(shù)全局收斂。Newton－Armijo算法步驟如下：

（1）初始化（w0，b0）∈Rn＋1，ε＞0，迭代步驟i＝0，最大迭代步驟imax＝200；

（3）計算2F（wi，bi）di＝－F（wi，bi）′，確定下降方向di∈Rn＋1；

（5）令（wi＋1，bi＋1）＝（wi，bi）＋，轉(zhuǎn)到 （2）繼續(xù)計算。

3.2 線性可分情況

光滑支持向量機是用來處理二分類問題的有效方法，其重點是判別函數(shù)的建立。線性可分的判別函數(shù)是建立在歐式距離基礎(chǔ)上的。實驗1和實驗2是基于線性可分?jǐn)?shù)據(jù)集進行的。實驗1采用NDC數(shù)據(jù)集對新光滑支持向量機模型進行訓(xùn)練，數(shù)據(jù)集的樣本數(shù)最少為10000。實驗分3次進行，取不同的參數(shù)t和α進行對比。實驗2采用UCI數(shù)據(jù)庫中的數(shù)據(jù)集，數(shù)據(jù)集規(guī)模大小不等，是常用的標(biāo)準(zhǔn)測試數(shù)據(jù)集。為了得到精確的數(shù)據(jù)結(jié)果，訓(xùn)練數(shù)據(jù)時使用10折交叉驗證方法［9，10］。

表1和表2說明分段熵函數(shù)光滑支持向量機具有解決大規(guī)模問題的能力，并且具有較好的分類性能。在解決大規(guī)模問題時，相對SSVM 模型，新模型在時間消耗上有明顯的降低。表3說明當(dāng)α超過一點界限的時候，SSVM 模型會造成數(shù)據(jù)溢出，失去分類作用，而新光滑支持向量機模型則不會產(chǎn)生數(shù)據(jù)溢出現(xiàn)象。

表1 NDC數(shù)據(jù)集實驗 （t＝0.1α＝10）

表2 NDC數(shù)據(jù)集實驗 （t＝0.01α＝100）

表3 NDC數(shù)據(jù)集實驗 （t＝0.005α＝200）

表4表明新光滑支持向量機模型具有處理任意規(guī)模樣本數(shù)據(jù)集的能力，和SSVM 模型相比，它處理數(shù)據(jù)的時間有明顯提升，因此新光滑支持向量機模型比SSVM 模型的性能更好。

表4 UCI數(shù)據(jù)庫的數(shù)據(jù)集實驗 （t＝0.01α＝100）

3.3 線性不可分情況

Chekerboard棋盤數(shù)據(jù)如圖1所示。

圖1 Chekerboard棋盤數(shù)據(jù)

表5表明新的光滑支持向量機模型在處理非線性數(shù)據(jù)時所耗費的CPU 時間較少，而分類和測試正確率卻有所提高。由此說明新光滑支持向量機模型處理非線性數(shù)據(jù)集的性能更好。

表5 Checkerboard數(shù)據(jù)集實驗（t＝0.01α＝100 C ＝0.001）

4 結(jié)束語

本文在分析優(yōu)化問題的基礎(chǔ)上，提出一種分段熵函數(shù)作為光滑函數(shù)用來逼近正號函數(shù)，并結(jié)合支持向量機模型，得到分段熵函數(shù)光滑支持向量機模型，避免了參數(shù)較大時SSVM 模型的數(shù)據(jù)溢出現(xiàn)象。理論證明了該光滑支持向量機模型的可行性和正確性。實驗結(jié)果表明，該光滑支持向量機模型具有對任意規(guī)模數(shù)據(jù)集進行分類的能力。而且該光滑支持向量機模型相比SSVM 模型在時間的損耗上有所降低，分類正確率有所提高。由此說明其分類性能相比SSVM 模型性能更優(yōu)越。

［1］DING Shifei，QI Bingjuan，TAN Hongyan.An overview on theory and algorithm of support vector machines［J］.Journal of University of Electronic and Technology of China，2011，40（1）：2－10 （in Chinese）.［丁世飛，齊丙娟，譚紅艷.支持向量機理論與算法研究綜述 ［J］.電子科技大學(xué)學(xué)報，2011，40（1）：2－10.］

［2］Li Xuehua，Shu Lan.Fuzzy theory based support vector machine classifier ［C］／／Proceedings of the Fifth International Conference on Fuzzy Systems and Knowledge Discovery，2008：600－604.

［3］Yu Hwanjo，Kim Yongdae，Hwang Seungwon.RV－SVM：An efficient method for learning ranking SVM ［C］／／Pacific－Asia Conference on Knowledge Discovery and Data Mining，2009：426－438.

［4］LIU Yeqing，LIU Sanyang，GU Mingtao.Research on polynomial functions for smoothing support vector machines ［J］.Systems Engineering and Electronics，2009，31 （6）：1450－1453 （in Chinese）. ［劉葉青，劉三陽，谷明濤.光滑支持向量機多項式函數(shù)的研究 ［J］.系統(tǒng)工程與電子技術(shù)，2009，31（6）：1450－1453.］

［5］YUAN Huaqiang，TU Wengen，XIONG Jinzhi，et al.New polynomial smooth support vector machine ［J］.Computer Science，2011，38 （3）：243－247 （in Chinese）. ［袁華強，涂文根，熊金志，等.一個新的多項式光滑支持向量機 ［J］.計算機科學(xué)，2013，38 （3）：243－247.］

［6］WU Qing，LIU Sanyang，ZHANG Leyou.Adjustable entropy function method for support vector regression ［J］.Control and Decision，2009，24 （11）：1609－1614 （in Chinese）. ［吳青，劉三陽，張樂友.回歸型支持向量機的調(diào)節(jié)熵函數(shù)法 ［J］.控制與決策，2009，24 （11）：1609－1614.］

［7］LI Chaoyan，QIN Xiaoming，LAI Honghui.Maximum entropy differential evolution algorithm to nonlinear l－1norm minimization problems［J］.Computer Engineering and Applications，2011，47 （8）：41－43 （in Chinese）.［李超燕，秦曉明，賴紅輝.非線性l－1模極小化問題的極大熵差分進化算法 ［J］.計算機工程與應(yīng)用，2011，47 （8）：41－43.］

［8］TU Wengen，XIONG Jinzhi，YUAN Huaqiang.Comparison of three methods for training smooth support vector classification ［J］.Computer Engineering and Applications，2011，47（3）：190－195 （in Chinese）. ［涂文根，熊金志，袁華強.三種訓(xùn)練光滑支持向量機分類器方法的比較 ［J］.計算機工程與應(yīng)用，2011，47 （3）：190－195.］

［9］TANG Yaohua，GAO Jinghuai，BAO Qianzong.Novel selective support vector machine ensemble learning algorithm ［J］.Journal of Xi’an Jiaotong University，2008，42 （10）：1221－1225 （in Chinese）. ［唐耀華，高靜懷，包乾宗.一種新的選擇性支持向量機集成學(xué)習(xí)算法 ［J］.西安交通大學(xué)學(xué)報，2008，42 （10）：1221－1225.］

［10］Yuan YB.Forecasting the movement direction of exchange rate with polynomial smooth support vector machine ［J］.Mathematical and Computer Modelling，2013，57 （3－4）：932－944.

［11］Christmann A，Hable R.Consistency of support vector machines using additive kernels for additive models［J］.Computational Statistics and Data Analysis，2012，56 （4）：854－873.