基于特征值分解的中心支持向量机算法

陈素根 吴小俊



基于特征值分解的中心支持向量机算法

陈素根①②吴小俊*①

①(江南大学物联网工程学院 无锡 214122)②(安庆师范学院数学与计算科学学院 安庆 246133)

针对广义特征值中心支持向量机(GEPSVM)训练和决策过程不一致问题，该文提出一类改进的基于特征值分解的中心支持向量机，简称为IGEPSVM。首先针对二分类问题提出了基于特征值分解的中心支持向量机，然后基于“一类对余类”策略将其推广到多类分类问题。将GEPSVM求解广义特征值问题转化为求解标准特征值问题，降低了计算复杂度。引入了一个新的参数，可以调节模型的性能，提高了GEPSVM的分类精度。提出了基于IGEPSVM的多类分类算法。实验结果表明，与GEPSVM算法相比较，IGEPSVM不仅提高了分类精度，而且缩短了训练时间。

支持向量机；广义特征值中心支持向量机；两类分类；多类分类；特征值分解

1 引言

支持向量机(SVM)算法是经典的分类算法[1]，鉴于其坚实的理论基础和良好的泛化性能而被广泛使用于各个领域中[2,3]。SVM在解决小样本、非线性和高维模式问题中表现出了许多特有的优势，标准的SVM算法问题可归结为求解一个受约束的二次规划(QP)问题，对于小规模的QP问题，它表现出了非常优秀的学习能力，但当训练集样本规模巨大时，就会出现训练速度慢、算法复杂和效率低下等问题。为了解决这些问题，一方面，许多学者对SVM求解算法进行了广泛研究，并取得了很多优秀成果，如Chunking算法[4]、分解算法[5]、SMO算法[6]和FD- SVM[7]等；另一方面，新型的SVM算法被大量研究，其中非平行平面支持向量机算法是代表性成果之一。关于非平行平面支持向量机算法的研究开始于2006年，文献[8]提出了广义特征值中心支持向量机算法(GEPSVM)来处理两类分类问题，考虑了最大化类间距离和最小化类内距离，对每一类样本训练一个分类超平面，开辟了新的决策思路。2007年，文献[9]在GEPSVM算法的基础上提出了孪生支持向量机算法(TWSVM)，与GEPSVM求解两个规模较小的广义特征值问题有所不同，TWSVM求解两个规模较小的QP问题，训练速度相当于传统SVM的1/4。然而，许多实际问题都可归结为多类分类问题，传统SVM的多类分类算法大致分为“分解重构法”和“整体法”两大类，代表性研究成果有：“一类对余类”[17]、“一类对一类”[18]和C&S (Crammer and Singer)方法[19]等。近年来，非平行平面支持向量机多类分类算法也开始受到很多学者的关注，涌现了一些优秀成果[20,21]。

GEPSVM算法是最早被提出的非平行平面支持向量机算法，虽然它开辟了新的决策思路，但它依然有一些不足之处。首先，GEPSVM在训练过程和决策过程中出现了不一致性，即：在训练过程中，是通过比较每一个超平面和两类训练样本之间的距离来寻求每一类的最优超平面的；在决策过程中，是通过比较测试样本和两个超平面的距离来实现分类的。因此，这一种不一致性，在一定程度上可能会影响GEPSVM的性能。其次，GEPSVM算法是通过求解两个广义特征值问题来实现的，但求解广义特征值问题的算法复杂度是，从而可能会影响模型的训练速度。最后，GEPSVM算法本身是针对两类分类问题提出的，不能直接处理多类分类问题。针对以上问题，本文首先针对两类分类问题提出一类改进的基于特征分解的中心支持向量机算法(Improved GEPSVM, IGEPSVM)；然后在IGEPSVM的基础上进一步研究多类分类问题，提出多类分类IGEPSVM算法。与GEPSVM算法相比较，IGEPSVM有如下优点：(1)将求解广义特征值问题转化为求解标准特征值问题，降低了算法的复杂度；(2)引入一个新的参数，可以更好地调节模型的性能，提高了GEPSVM算法的分类精度。最后，在标准的UCI分类数据集上验证了本文算法的有效性。

2 广义特征值中心支持向量机(GEPSVM)

对于两类分类问题，给定训练样本集：

显然，问题式(4)的目标函数是Rayleigh商。故，优化问题式(4)的最优解就是广义特征值问题：

3 基于特征值分解的中心支持向量机(IGEPSVM)

仔细分析GEPSVM算法，我们不难发现，GEPSVM算法在训练过程和决策过程具有一定的不一致性，这可能会影响GEPSVM算法的性能。为此，我们提出一种改进的基于特征值分解的中心支持向量机算法。

3.1 两类分类IGEPSVM

首先考虑线性情形，对于训练样本集式(1)，我们考察优化模型[13]：

显然，直接观察式(7)是比较难以理解的。然而，式(7)有很好的几何解释。假设IGEPSVM寻求的两个非平行超平面也为式(2)，那么在空间中训练样本点到超平面的距离为

这样，结合式(8)，我们分别定义正类和负类训练样本点到正类和负类两个超平面的4个距离：

于是，优化模型式(7)转化为

通过构造Lagrange函数并结合KKT条件，求解模型式(12)可以转化为求解标准特征值问题式(13)：

因此，优化问题式(12)的第1部分可表示为

由Rayleigh定理[22]可知，当且仅当是矩阵最小特征值时，优化问题式(12)的第1部分的目标函数取得全局极小值。此时，最小特征值对应的单位特征向量是优化问题式(12)的第1部分的最优解。同理可证，优化问题式(12)的第2部分的最优解是矩阵的最小特征值所对应的单位特征向量。 证毕于是，当被求出后，对于新的测试样本，它将根据式(16)，被分类到正类或负类。即

类似地，我们也可以分别定义正类和负类训练样本点到正类和负类两个非线性超曲面的4个距离：

于是，建立非线性情形的优化模型为

类似于线性情形，求解模型式(18)可以转化为求解模型式(19)：

通过构造Lagrange函数并结合KKT条件，求解模型式(19)可以转化为求解标准特征值问题式(20)：

类似于线性情形，关于非线性模型，我们可以得定理2。

定理2的证明过程类似于定理1，简单起见，此处省略。于是，当被求出后，对于新的测试样本，它将根据式(21)，被分类到正类或负类。即：

总结上述过程，可以得到两类分类IGEPSVM算法如下：

算法1 两类分类IGEPSVM算法

步骤1 给定训练集式(1)；

步骤3 利用模型式(12)或式(19)训练，求解特征值问题式(13)或式(20)得到最小特征值对应的单位特征向量；

步骤4 利用决策函数式(16)或式(21)进行分类。

3.2 多类分类IGEPSVM

这样，对于线性多类分类问题，基于线性IGEPSVM就可以构造个相互不平行的超平面：

并构造决策函数如下：

的最小特征值对应的单位特征向量。

对于非线性多类分类问题，基于非线性IGEPSVM可以构造个超曲面：

并构造决策函数：

的最小特征值对应的单位特征向量。

总结上述过程，可以得到多类分类IGEPSVM算法如下：

算法2 多类分类IGEPSVM算法

(2)利用模型式(24)或式(28)训练，求解特征值问题式(25)或式(29)得到最小特征值对应的单位特征向量；

End

步骤3 利用决策函数式(23)或式(27)进行分类。

3.3 计算复杂度分析

综上可知，对于两类分类问题，线性IGEPSVM仅需要求解两个标准的特征值问题，其计算复杂度为，其中为训练样本点的特征维数，而线性GEPSVM则需要求解两个广义特征值问题，其计算复杂度为。对于非线性情形，我们的非线性IGEPSVM的计算复杂度为，其中为训练样本点的规模，而非线性GEPSVM的计算复杂度为。对于类多分类问题，IGEPSVM算法无论对线性还是非线性都需要求解个特征值问题，它们的计算复杂度分别为和。因此，由理论分析可知，IGEPSVM训练速度要比GEPSVM快。

4 实验结果与分析

为了验证IGEPSVM算法的有效性，分别在8个两类分类和6个多类分类UCI数据集上[23]进行实验，并分别与传统SVM, GEPSVM和TWSVM方法进行对比。所有实验均以Matlab R2013a为实验环境，以Intel P4(3.40 GHz)处理器、4 GB内存的PC为硬件平台。在实验过程中，使用LIBSVM工具包[24]实现传统SVM，使用逐次超松弛技术(SOR)[10]来求解TWSVM中的QPP问题，使用Matlab的“eig”函数求解GEPSVM和IGEPSVM分别对应的广义特征值问题和标准特征值问题。对于非线性情形，选择RBF核为核函数，其中为核参数。参数选择对于各算法性能有一定的影响，因此，对于不同的数据集，使用10-折交叉验证方法为算法选择最优参数，所有算法中的参数选取范围均为。

针对两类分类问题，我们选择了8个UCI数据集来验证本文算法的有效性，表1和表2分别给出了4种算法在线性和非线性情形下的10-折交叉验证结果和训练时间。针对多类分类问题，我们选择了6个UCI数据集来验证本文算法的有效性，表3和表4分别给出了4种算法在线性和非线性情形下的10-折交叉验证结果和训练时间。在表1至表4中，为了更好地体现算法的优越性，用黑体数字代表特定数据集下获得的最高分类精度。同时，我们在表的倒数第2行给出了所有算法的平均分类精度和训练时间，并在表的最后一行用“W-T-L”(win-tie-loss)概括了IGEPSVM算法与其它算法的性能。

对于两类分类问题，从表1和表2中可以发现，从分类精度来说，IGEPSVM算法比GEPSVM和传统的SVM表现出了更好的性能，同时也获得了与TWSVM算法非常类似的性能；但从训练时间上来说，本文算法表现出了更好的优势，虽然在非线性情形下SVM也有较好的结果，那可能是因为LIBSVM工具包实现SVM利用了SMO算法的原因。容易看出，本文方法IGEPSVM在绝大多数的数据集上训练时间相对较少，尤其与GEPSVM方法相比较，训练时间明显减少，进一步验证了本文方法是对GEPSVM方法的一种有效改进。

对于多类分类问题而言，观察表3和表4不难发现，一方面，无论在分类精度还是训练时间，本文IGEPSVM算法比GEPSVM算法都有所提高。另一方面，本文IGEPSVM算法与SVM和TWSVM相比较，从表3和表4的最后两行看出，本文方法在分类精度上要稍微低一点，但也取得了较好的效果；然而，本文方法在训练时间上总体上是有一定

表1 线性IGEPSVM与几种算法在两类分类UCI数据集上性能比较

数据集

IGEPSVM

GEPSVM

SVM

TWSVM

精度±方差(%)时间(s)

精度±方差(%)时间(s)

精度±方差(%)时间(s)

精度±方差(%)时间(s)

Australian(690×14)

86.52±3.21, 3.8563e-04

85.80±4.67, 5.1659e-04

85.51±3.86, 0.0185

86.10±4.55, 0.0381

House votes(435×16)

94.26±2.68, 2.6548e-04

94.03±2.88, 4.4901e-04

94.73±3.77, 0.0033

95.87±3.21, 0.0063

Heart-c(303×14)

84.87±5.85, 2.2177e-04

84.49±7.40, 5.4313e-04

84.83±5.41, 0.0029

85.13±5.07, 0.0277

Heart-Statlog(270×13)

84.70±4.68, 2.2044e-04

84.59±8.20, 3.5033e-04

84.44±4.88, 0.0023

84.81±4.77, 0.0333

Monk3(432×7)

83.47±5.66, 1.3137e-04

80.76±7.00, 2.2355e-04

82.59±6.03, 0.0027

85.91±3.96, 0.0464

Sonar(208×60)

81.98±7.96, 0.0032

79.31±5.59, 0.0052

81.69±6.88, 0.0035

81.93±7.28, 0.0371

Spect(267×44)

80.51±5.78, 0.0016

79.46±7.54, 0.0025

80.45±7.46, 0.0030

80.24±6.21, 0.0691

Wpbc(198×34)

80.32±2.26, 0.0010

78.18±6.88, 0.0015

80.14±6.90, 0.0022

79.89±5.23, 0.0431

平均精度/平均时间

84.58/0.0009

83.33/0.0014

84.30/0.0048

84.99/0.0376

W-T-L(胜-平-负)

8-0-0

7-0-1

4-0-4

表2 非线性IGEPSVM与几种算法在两类分类UCI数据集上性能比较

数据集

IGEPSVM

GEPSVM

SVM

TWSVM

精度±方差(%)时间(s)

精度±方差(%)时间(s)

精度±方差(%)时间(s)

精度±方差(%)时间(s)

Australian(690×14)

86.67±5.19, 0.7215

86.10±2.51, 5.2741

86.23±4.70, 0.5162

86.96±4.27, 0.7381

House votes(435×16)

95.42±2.85, 0.1356

94.12±5.05, 0.8937

95.24±4.07, 0.1112

96.32±2.49, 0.1641

Heart-c(303×14)

84.86±5.20, 0.0810

82.52±7.49, 0.2952

83.19±8.27, 0.0652

85.13±2.47, 0.0834

Heart-Statlog(270×13)

84.07±4.64, 0.0165

83.33±7.25, 0.2023

83.59±7.21, 0.0140

84.81±7.08, 0.0184

Monk3(432×7)

98.72±4.80, 0.2135

95.84±3.29, 0.8769

97.25±3.18, 0.1045

98.26±1.32, 0.2450

Sonar(208×60)

87.24±6.33, 0.0153

86.55±8.08, 0.1533

86.10±8.51, 0.0257

89.26±7.19, 0.0289

Spect(267×44)

82.71±8.96, 0.0675

80.48±8.09, 0.3178

82.46±8.54, 0.0549

82.07±5.91, 0.0709

Wpbc(198×34)

82.76±6.33, 0.0353

81.26±8.24, 0.1137

82.56±5.38, 0.0534

82.74±5.23, 0.0504

平均精度/平均时间

87.81/0.1608

86.28/1.0159

87.08/0.1181

88.19/0.1749

W-T-L(胜-平-负)

8-0-0

8-0-0

3-0-5

表3 线性IGEPSVM与几种算法在多类分类UCI数据集上性能比较

数据集

IGEPSVM

GEPSVM

SVM

TWSVM

精度±方差(%)时间(s)

精度±方差(%)时间(s)

精度±方差(%)时间(s)

精度±方差(%)时间(s)

Iris(150×4×3)

96.67±5.67, 0.0012

95.33±4.66, 0.0028

95.33±4.50, 0.0034

96.53±5.84, 0.0209

Wine(178×13×3)

96.76±5.17, 0.0017

94.71±7.92, 0.0042

97.78±3.88, 0.0028

98.33±2.68, 0.0669

Seeds(210×7×3)

93.71±1.23, 0.0015

89.05±5.96, 0.0018

92.86±5.14, 0.0027

95.71±4.74, 0.0474

Dermatology(358×34×6)

95.03±6.79, 0.0080

94.14±4.97, 0.0099

95.83±3.00, 0.0121

95.25±2.63, 0.2177

Balance(625×4×3)

88.48±3.77, 0.0017

89.69±3.72, 0.0020

87.52±3.54, 0.0031

87.66±3.18, 0.2026

Car(1278×6×4)

77.78±2.85, 0.0045

73.59±2.84, 0.0068

84.78±4.13, 0.0329

77.26±4.27, 2.1232

平均精度/平均时间

91.41/0.0031

89.42/0.0046

92.35/0.0095

91.79/0.4465

W-T-L(胜-平-负)

5-0-1

3-0-3

3-0-3

表4 非线性IGEPSVM与几种算法在多类分类UCI数据集上性能比较

数据集

IGEPSVM

GEPSVM

SVM

TWSVM

精度±方差(%)时间(s)

精度±方差(%)时间(s)

精度±方差(%)时间(s)

精度±方差(%)时间(s)

Iris(150×4×3)

97.33±3.51, 0.0100

96.67±4.71, 0.0399

96.67±3.51, 0.0121

97.33±3.44, 0.0162

Wine(178×13×3)

97.78±2.87, 0.0444

95.49±5.20, 0.0766

98.30±2.74, 0.0463

99.44±1.76, 0.1237

Seeds(210×7×3)

94.33±6.02, 0.0546

92.38±7.17, 0.1377

93.86±4.63, 0.0510

96.67±3.21, 0.1508

Dermatology(358×34×6)

96.23±4.22, 0.3165

96.39±2.64, 1.0836

96.01±5.19, 0.2205

96.65±4.11, 0.6842

Balance(625×4×3)

94.25±2.26, 0.5918

96.65±2.74, 3.7493

93.97±4.11, 0.3067

99.20±1.13, 1.2449

Car(1278×6×4)

96.20±1.47, 3.8730

94.04±1.07, 18.4988

98.67±1.22, 0.8437

98.44±0.67, 7.8442

平均精度/平均时间

96.02/0.8150

95.27/3.9310

96.25/0.2467

97.96/1.6773

W-T-L(胜-平-负)

4-0-2

4-0-2

0-1-5

优势的，只有在与非线性SVM比较时稍微差一些，主要原因可能是SVM采取了LIBSVM工具包和“一类对一类”的策略实现多类分类。总而言之，本文IGEPSVM算法是对GEPSVM算法的一种改进，无论在分类精度还是在训练时间上都取得了比GEPSVM较好的实验效果。

5 结束语

本文针对两类分类问题提出了一类改进的基于特征值分解的中心支持向量机算法(IGEPSVM)，并将其推广到多类分类问题。与GEPSVM算法相比较，本文的主要贡献在于：首先，解决了GEPSVM模型训练过程和决策过程不一致的问题；其次，将GEPSVM求解广义特征值问题转化为求解标准的特征值问题，降低了计算复杂度；最后，通过引入新的参数，可以方便调节IGEPSVM模型的性能，提高了分类精度。在UCI数据集上的实验结果表明，本文算法比GEPSVM算法更优越，但与SVM或TWSVM算法相比较，它们各有优势。近几年来，非平行平面支持向量机已经逐渐成为模式识别和机器学习领域新的研究热点之一，将已有的针对两类分类问题所提出的非平行平面支持向量机算法推广到多类分类问题以及在不同领域的应用是今后研究的重点。

[1] CORTES C and VAPNIK V N. Support vector machine[J]., 1995, 20(3): 273-297.

[2] OSUNA E, FREUND R, and GIROSI F. Training support vector machines: an application to face detection[C]. Proceedings of Computer Vision and Pattern Recognition, San Juan, 1997: 130-136.

[3] ISA D, LEE L H, KALLIMANI V P,. Text document preprocessing with the Bayes formula for classification using the support vector machine[J]., 2008, 20(9): 1264-1272.

[4] BOSER B, GUYON I, and VAPNIK V N. A training algorithm for optimal margin classifiers[C]. Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, New York, 1992: 144-152.

[5] OSUNA E, FREUND R, and GIROSI F. An improved training algorithm for support vector machines[C]. Proceedings of IEEE Workshop on Neural Networks for Signal Processing, New York, USA, 1997: 276-285.

[6] PLATT J. Fast Training of Support Vector Machines Using Sequential Minimal Optimization[M]. Advances in Kernel Methods: Support Vector Machines, Cambridge, MA, MIT Press, 1998: 41-65.

[7] 张战成, 王士同, 邓赵红, 等. 支持向量机的一种快速分类算法[J]. 电子与信息学报, 2011, 33(9): 2181-2186.

ZHANG Zhancheng, WANG Shitong, DENG Zhaohong,. Fast decision using SVM for incoming samples[J].&, 2011, 33(9): 2181-2186.

[8] MANGASARIAN O L and WILD E W. Multisurface proximal support vector machine classification via generalized eigenvalues[J]., 2006, 28(1): 69-74.

[9] JAYADEVA, KHEMCHANDAI R, and CHANDRA S. Twin support vector machine classification for pattern classification [J]., 2007, 29(5): 905-910.

[10] SHAO Y H, ZHANG C H, WANGX B,. Improvements on twin support vector machines[J]., 2011, 22(6): 962-968.

[11] PENG X J. TPMSVM: A novel twin parametric-margin support vector machine for pattern recognition[J]., 2011, 44(10): 2678-2692.

[12] QI Z Q, TIAN Y J, and SHI Y. Robust twin support vector machine for pattern classification[J]., 2013, 46(1): 305-316.

[13] SHAO Y H, DENG N Y, and CHEN W J. A proximal classifier with consistency[J]., 2013, 49: 171-178.

[14] Tian Y J, Qi Z Q, Ju X C,. Nonparallel support vector machines for pattern classification[J]., 2014, 44(7): 1067-1079.

[15] DING S F, HUA X P, and YU J Z. An overview on nonparallel hyperplane support vector machine algorithms[J]., 2014, 25(5): 975-982.

WANG Na and LI Xia. A new dualsupport vector machine based on class-weighted[J].&, 2007, 29(4): 859-862.

[17] BOTTOU L, CORTES C, DENKER J S,. Comparison of classifier methods: a case study in handwritten digit recognition[C]. Proceedings of IEEE International Conference on Pattern Recognition, Paris, 1994: 77-82.

[18] KREßEL U. Pairwise Classification and Support Vector Machines[M]. Advances in Kernel Methods-Support Vector Learning, Cambridge, MA, MIT Press, 1999: 255-268.

[19] CRAMMER K and SINGER Y. On the learn ability and design of output codes for multi-class problems[J]., 2002, 47(2/3): 201-233.

[20] XU Y T, GUO R, and WANG L S. A twin multi-class classification support vector machine[J]., 2013, 5(4): 580-588.

[21] NASIRI J A, CHARKARI N M, and JALILI S. Least squares twin multi-class classification support vector machine[J]., 2015, 48(3): 984-992.

[22] PARLETT B. The Symmetric Eigenvalue Problem[M]. Upper Saddle River, NJ, USA, SIAM Press, 1998: 61-80.

[23] BLAKE C L and MERZ C J. UCI repository of machine learning databases[R]. Irvine, CA: Department of Information and Computers Science, University of California, 1998.

[24] CHANG C and LIN C. LIBSVM: A library for support vector machine[J]., 2011, 2(3): 1-27.

陈素根： 男，1982年生，副教授，博士生，研究方向为模式识别与智能系统.

吴小俊： 男，1967年生，教授，博士生导师，研究方向为模式识别、人工智能与计算机视觉.

Foundation Items: The National Natural Science Foundation of China (61373055, 61103128), 111 Project of Chinese Ministry of Education (B12018), Industrial Support Program of Jiangsu Province (BE2012031)

Eigenvalue Proximal Support Vector Machine Algorithm Based on Eigenvalue Decoposition

CHEN Sugen①②WU Xiaojun①

①(School of IoT Engineering, Jiangnan University, Wuxi 214122, China)②(School of Mathematics & Computational Science, Anqing Normal University, Anqing 246133, China)

To deal with the consistency problem of training process and decision process in Generalized Eigenvalue Proximal Support Vector Machine (GEPSVM), an improved version of eigenvalue proximal support vector machine, called IGEPSVM for short is proposed. At first, IGEPSVM for binary classification problem is proposed, and then Multi-IGEPSVM is also presented for multi-class classification problem based on “one-versus-rest” strategy. The main contributions of this paper are as follows. The generalized eigenvalue decomposition problems are replaced by the standard eigenvalue decomposition problems, leading to simpler optimization problems. An extra parameter is introduced, which can adjust the performance of the model and improve the classification accuracy of GEPSVM. A corresponding multi-class classification algorithm is proposed, which is not studied in GEPSVM. Experimental results on several datasets illustrate that IGEPSVM is superior to GEPSVM in both classification accuracy and training speed.

Support Vector Machine (SVM); Generalized Eigenvalue Proximal SVM (GEPSVM); Binary classification; Multi-class classification; Eigenvalue decoposition

TP391

A

1009-5896(2016)03-0557-08

10.11999/JEIT150693

2015-06-08；改回日期：2015-09-17；网络出版：2015-11-19

吴小俊 wu_xiaojun@jiangnan.edu.cn

国家自然科学基金(61373055, 61103128), 111引智计划项目(B12018)，江苏省工业支持计划项目(BE2012031)