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

吳 青，梁 勃

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

0 引 言

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

1 分段熵函數

定義1 定義如下分段熵函數

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

對于這個分段熵函數函數有如下定理：

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

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

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

證明：當x≤0時，令Y1＝t2［log（1＋exp（））］2，對Y1求導得：，則Y1是單調遞增的，所以最大值在x＝0處取得，maxY1＝t2（log2）2≤t2；當x＞0時，令由對數函數的性質log（1＋x）≤x可得

所以Y2≤t2，結論成立。

2 分段熵光滑支持向量機

2.1 光滑支持向量機模型

考慮如下優化問題

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

標準SVM 模型的等價無約束優化模型為

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

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

提高了分類性能和效率。

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

2.2 收斂性分析

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

定理4 Ft（w，b）是嚴格凸函數，對給定的t，存在唯一解。

定理5 標準SVM 優化式 （5）解為x＊＝（w＊，b＊），分段熵函數光滑支持向量機優化模型 （6）解為＝，），則：0≤Ft）－F（x＊）≤mt2。

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

定理6 設A ∈Rm×n，b∈Rm×1實函數定義如下

證明：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得。。從而結論得證。

3 數值實驗

3.1 Newton－Armijo算法

分段熵函數支持向量機具有任意階可微的性質，而Newton下降法［8］有二次收斂速度。因此，可以用快速Newton－Armijo算法進行訓練，以使目標函數全局收斂。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）＋，轉到 （2）繼續計算。

3.2 線性可分情況

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

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

表1 NDC數據集實驗 （t＝0.1α＝10）

表2 NDC數據集實驗 （t＝0.01α＝100）

表3 NDC數據集實驗 （t＝0.005α＝200）

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

表4 UCI數據庫的數據集實驗 （t＝0.01α＝100）

3.3 線性不可分情況

Chekerboard棋盤數據如圖1所示。

圖1 Chekerboard棋盤數據

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

表5 Checkerboard數據集實驗（t＝0.01α＝100 C ＝0.001）

4 結束語

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

［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］.電子科技大學學報，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）. ［劉葉青，劉三陽，谷明濤.光滑支持向量機多項式函數的研究 ［J］.系統工程與電子技術，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］.計算機科學，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）. ［吳青，劉三陽，張樂友.回歸型支持向量機的調節熵函數法 ［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］.計算機工程與應用，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）. ［涂文根，熊金志，袁華強.三種訓練光滑支持向量機分類器方法的比較 ［J］.計算機工程與應用，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）. ［唐耀華，高靜懷，包乾宗.一種新的選擇性支持向量機集成學習算法 ［J］.西安交通大學學報，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.