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

吴 青，梁 勃

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