基于遗传算法的双子支持向量机的模型选择

曹路+秦传波+洪灿佳

摘 要： 双子支持向量機是在支持向量机的基础上提出的一种新的机器学习方法。与传统支持向量机相比，双子支持向量机寻找的是一对不平行的超平面，计算效率是传统支持向量机的4倍。然而，双子支持向量机的参数较多，在应用过程中存在较大局限性。在研究了惩罚参数和核参数对双子支持向量机分类性能影响的基础上，利用遗传算法来选择双子支持向量机的参数，避免了盲目的模型选择。实验结果显示，所提算法能有效选择合适参数，获得的参数能使双子支持向量机具有较好的泛化性能，同时也更加高效。

关键词： 双子支持向量机； 遗传算法； 核函数； 参数选择

中图分类号： TN98?34； TP273 文献标识码： A 文章编号： 1004?373X（2017）17?0105?04

Genetic algorithm based model selection of TWSVM

CAO Lu， QIN Chuanbo， HONG Canjia

（School of Information Engineering， Wuyi University， Jiangmen 529020， China）

Abstract： Twin support vector machine （TWSVM） is a new machine learning method based on support vector machine. In comparison with traditional support vector machine， TWSVM looks for a pair of non?parallel hyperplane， and its computational efficiency is increased by 3 times. However， the parameters of TWSVM are various， and have some limitations in the application process. On the basis of the research on the influence of the penalty parameter and kernel parameter on classification performance of TWSVM， the genetic algorithm is used to select the parameters of TWSVM to avoid blind model selection. The experimental results show that the algorithm can select appropriate parameters effectively， which can make the TWSVM have high generalization performance and efficient performance.

Keywords： TWSVM； genetic algorithm； kernel function； parameter selection

0 引 言

支持向量机[1]（Support Vector Machine，SVM）是20世纪60年代由V.Vapnik等人提出的基于统计理论的机器学习方法，在小样本的情况下有优良的学习性能，已被广泛应用于模式识别、文本分类及回归分析等众多领域[2?3]。尽管支持向量机克服了传统分类器过学习、局部极值和维数灾难等缺点，但支持向量机的训练时间消耗非常大，复杂度较高，无法适应大数据环境下对分类技术的更高要求。文献[4]提出一种新的学习方法，称为双子支持向量机（Twin Support Vector Machines，TWSVM），将SVM中的一对平行超平面推广到复杂的非平行超平面的情况，因而能处理一些传统SVM难以处理的数据分布，如交叉数据。由于TWSVM所求解的二次规划问题的规模是原SVM的所以，从理论上来说计算效率是传统SVM的4倍，极大地提高了分类效率[5]。

在TWSVM出现以后，人们一直在关注着如何进一步改进TWSVM，从而涌现出了很多方法。文献[6]在经典的TWSVM基础上，提出一种有边界的双子支持向量机（Twin Bounded Support Vector Machines，TBSVM）。该模型参照经典支持向量机，采用结构风险最小原则，在一定程度上提升了原模型的识别率。文献[7]提出基于最小二乘的双子支持向量机（Least Squares Twin Support Vector Machines，LSTSVM），将最小二乘的思想引入TWSVM中，修改原始双子支持向量机二次规划问题，用等式约束取代TWSVM中的不等式约束问题，计算效率得到了显著提高。文献[8]提出一种新型改进型的双子参数边界支持向量机（Twin Parametric?margin Support Vector Machines，TPMSVM），根据参数边界SVM的基本思想，融入TWSVM中，产生两条非平行超平面，具有良好的识别性能。

尽管TWSVM在算法改进和应用领域取得了较大进展，但算法仍存在一定的局限，如TWSVM中的参数较多，参数的选择会影响分类器最终的分类性能。文献[9?10]分别用粒子群算法和量子粒子群算法对TWSVM的参数进行优化，取得了较好的实验结果。目前，大多数文献采用的是参数空间穷尽搜索法在整个参数空间进行搜索，计算复杂度较高。由此，本文提出一种基于遗传算法的TWSVM模型选择方法，首先利用遗传算法获得最优参数，然后将参数用于TWSVM中以提高分类精度。实验结果显示，获得的参数能使双子支持向量机具有较好的泛化性能，同时也更加高效。endprint

1 双子支持向量機

1.1 双子支持向量机分类算法

考虑维实数空间的二值分类问题，训练数据集，其中是输入空间中的样本，是输出分类中的分类标签，。双子支持向量机构造了两个不平行的超平面，使得每一个分类面靠近一类样本而远离其他类样本，两个超平面分别记为：

（1）

可以通过求解两个优化问题获得两个不平行的超平面，两个优化问题可描述为：

（2）

（3）

式中：为参数；和为列向量。

式（2）和式（3）的对偶问题分别为：

（4）

（5）

式中：；；和分别为拉格朗日乘数。

式（6），式（7）有求解矩阵的逆，为了解决矩阵的异常性和病态矩阵，双子支持向量机引入因子使矩阵的逆可解。通过求解式（4），式（5），可获得式（1）定义的两个超平面：

（6）

一个新的样本点类别的判定依赖于样本点与两个超平面之间的距离，具体可描述为：

（7）

与传统支持向量机一样，为了求解非线性情况，TWSVM通过核函数将原始特征空间中的非线性分界面映射到高维空间中以获得更好的分类效果。

1.2 支持向量机和双子支持向量机性能比较

图1和图2是二维不交叉数据和二维交叉数据在SVM和TWSVM的分类效果图，其中，“+”表示正类样本，“○”表示负类样本。图1为二维不交叉数据时的情况，其中图1（a）为SVM的分类效果图，分类面是能将两类数据分开且满足最大间隔的超平面；图1（b）为TWSVM的分类效果图，与传统SVM不一样，TWSVM最终获得的是两个不平行的分类面，其中实线为正类分类面，虚线为负类分类面。图2为二维交叉数据的情况，其中图2（a）为SVM的分类效果图，可以看到，线性情形下的SVM只有一条分类面，无法将两类样本很好地分开；而在图2（b）中，采用TWSVM有两个分类面，可有效识别两类样本。

2 参数对TWSVM的影响

2.1 惩罚参数和对TWSVM的影响

为了研究惩罚参数对TWSVM的影响，对两类符合多维正态分布的人工数据集进行分类，采用的两类数据均值分别为[-5，20]，[15，2]，协方差矩阵为[10，0；0，2]，[10，0；0，1]的205×2维的随机向量，每一类中含有15个噪声点。如图3所示，分别为[0.01，0.01]，[0.483 9，0.494 4]，[1，1]，[10，10]，其中图3（b）是使用交叉验证获得的最优参数，分类准确度为98.78%。惩罚参数是特征空间中置信区间和经验风险的折衷，其目的是使TWSVM的泛化能力达到最佳。如图3（a）所示，和的值越小，表示经验风险的误差越小。在这种情况下，TWSVM的复杂度较低，但容错能力较差。如图3（c）和图3（d）所示，当两个惩罚参数的值较大时，数据拟合程度较高，易出现过拟合的情况，不能很好地泛化新数据。

2.2 核参数对TWSVM的影响

TWSVM是一种基于核的学习方法，核函数及核参数的选择直接影响到TWSVM的泛化能力。常用的核函数有线性核、多项式核和高斯核，其中以高斯核函数最为普遍。高斯核可描述为：其中为高斯核参数。核函数参数和特征子空间是相互对应的。高斯核参数不同，数据所对应的特征子空间不同，分类效果也就不同，因此高斯核参数的选取对TWSVM性能影响很大。当很小时，TWSVM构造的分类面过于简单，不能很好地拟合数据；当很大时，特征子空间维度很高，TWSVM的模型比较复杂，没有很好的泛化能力。因此，只有选择合适的核函数参数，将数据投影到合适的特征子空间，TWSVM才能获得良好的推广能力。

3 基于遗传算法的双子支持向量机

用常规的遍历方法如网格搜索法来寻找TWSVM的最优参数需要大量的运算，计算复杂度高，训练过程十分耗时，因此采用先进的寻优算法对TWSVM的参数进行优化是很重要的。在各种参数优化算法中，遗传算法（Genetic Algorithm，GA）是一种比较高效的寻优算法[11]。本文将遗传算法应用到TWSVM的参数优化中，称为GA?TWSVM。通过遗传的优化功能，快速准确地确定TWSVM的惩罚参数和高斯核函数参数，从而最终确定TWSVM的模型。具体实现步骤如下：

（1） 初始化双子支持向量机参数并对其进行二进制编码，产生遗传算法的初始群体。

（2） 设定遗传算法的参数。

（3） 将初始群体解码后送入双子支持向量机进行训练并计算个体的适应度。

（4） 应用最优保存策略，在进行遗传操作之前保存适应度较高的个体。

（5） 进行遗传操作，选择算子采用赌轮选择法，通过选择、交叉和变异操作产生新群体。

（6） 重复执行步骤（3）～步骤（5）操作，直至最大迭代次数满足适应度要求。

4 实 验

为了测试基于遗传算法的TWSVM的有效性，本文采用UCI标准数据集进行验证，实验数据集的描述见表1，实验中所采用的数据可以从http：//archive.ics.uci.edu/ml/datasets.html下载。本文实验环境为IntelCoreTM i7?37， CPU 3.4 GHz，4 GB内存和Matlab R2013a。实验中将选取60%的数据作为训练数据，保证足够的数据用于模型的学习；40%的数据作为测试数据，验证模型的效果。本文实验采取五折交叉确认的方法，在实验过程中，每个数据集被随机分为5等分，取其中1个子集为测试集，其他4个子集为训练集。为了避免偶然性，本文将算法分别执行5次，最后取平均值作为最后的输出。遗传算法的参数设置如下：群体规模为500，最大进化代数为1 000次，交叉概率为0.8，变异概率为0.05。和的优化区间均为[0.1，100]，高斯核参数的区间为[0.01，50]。endprint

表2列出了GA?TWSVM获得最佳训练精度时的惩罚参数和的值，及高斯核参数的取值，同时，表2中还列出了利用遗传算法获得最优参数后，将最优参数用于测试数据所得到的分类准确率。

表3为SVM、基于网格搜索法的TWSVM和基于遗传算法的TWSVM三种算法在分类精度和搜索时间上的比较。需要特别说明的是，本文中SVM采用二次规划的方法进行分类。从理论上讲，TWSVM的运行时间应是SVM运行效率的4倍，在实验中发现，实验结果和理论值存在一定的差距。尽管如此，从表3中可以看到，基于网格搜索法的TWSVM和基于遗传算法的TWSVM在分类精度和搜索时间上相较于SVM存在非常明显的优势。同时，实验结果也显示，基于网格搜索法和遗传算法的TWSVM在搜索精度上没有明显的差别，但是优化参数的搜索速度不相同。很明显，遗传算法的搜索速度更快，這在实际运用中有巨大的优势。因此，遗传算法相对于网格搜索算法在基于RBF核的TWSVM分类器的参数优化运用中具有更好的可行性。

5 结 论

与传统的支持向量机相比，双子支持向量机是解决大规模数据集的有效方法，其分类精度和训练速度均优于传统的支持向量机。双子支持向量机中参数众多，参数的选择对分类的精度有较大影响。本文提出一种基于遗传算法的双子支持向量机模型选择，通过遗传算法的良好寻优性能对双子支持向量机众多参数进行寻优，实验结果显示该方法是有效的。然而遗传算法容易受到随机初值的影响，利用改进的遗传算法对双子支持向量机的参数进行优化是下一步的研究方向，同时，探索新的应用领域，推广基于遗传算法的双子支持向量机的应用也是值得考虑的问题。

参考文献

[1] 邓乃扬，田英杰.支持向量机：理论、算法、与拓展[M].北京：科学出版社，2009.

[2] 瓦普尼克.统计学习理论[M].许建华，张学工，译.北京：电子工业出版社，2004.

[3] 王文剑，门昌骞.支持向量机建模及应用[M].北京：科学出版社，2014.

[4] KHEMCHANDANI R， CHANDRA S. Twin support vector machines for pattern classification [J]. IEEE transactions on pattern analysis and machine intelligence， 2007， 29（5）： 905?910.

[5] 储茂祥，王安娜，巩荣芬.一种改进的最小二乘孪生支持向量机分类算法[J].电子学报，2014，42（5）：998?1003.

[6] SHAO Y H， ZHANG C H， WANG X B， et al. Improvements on twin support vector machines [J]. IEEE transactions on neural networks， 2011， 22（6）： 962?968.

[7] KUMAR M A， GOPAL M. Least squares twin support vector machines for pattern classification [J]. Expert systems with applications， 2009， 36（4）： 7535?7543.

[8] PENG X. TPMSVM： a novel twin parametric?margin support vector machine for pattern recognition [J]. Pattern recognition， 2011， 44（10）： 2678?2692.

[9] DING S F， YU J Z， HUANG H J， et al. Twin support vector machines based on particle swarm optimization [J]. Journal of computers， 2013， 9（8）： 2296?2303.

[10] DING S F， WU F L， NIE R， et al. Twin support vector machines based on quantum particle swarm optimization [J]. Journal of software， 2013， 8（7）： 1743?1750.

[11] 梁旭，黄明，宁涛，等.现代智能优化混合算法及其应用[M].北京：电子工业出版社，2014.

[12] HUANG H J， DING S F， ZHU H， et al. Invasive weed optimization algorithm for optimizating the parameters of mixed kernel twin support vector machines [J]. Journal of computers， 2013， 8（8）： 2077?2084.endprint