基于多宽度高斯核的支持向量机特征选取算法研究

罗浪+汪静

摘 要：支持向量机（SVM）作为一种机器学习分类算法应用广泛，但在处理高维度数据集时往往会由于特征维数较多遇到算法分类速度慢且容易陷入局部最优等问题。为了提高支持向量机的性能，提出一种基于多宽度高斯核（GKMW）的支持向量机特征选取算法FSG。FSG算法将泛化能力更强的多宽度高斯核函数引入支持向量机中代替传统的高斯核函数，利用多宽度高斯核函数能体现各个特征对分类贡献程度不同且能区分样本中各个特征重要性的特点，以多宽度高斯核函数的参数优化结果为基础进行特征选取。利用特征选取后的特征子集在多组标准UCI数据集上分类实验，实验结果表明所提算法性能优于有代表性的特征选取法。

关键词：多宽度高斯核；支持向量机；特征选取；基因表达式编程

DOIDOI：10.11907/rjdk.181012

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）002-0080-06

0 引言

大数据时代下数据规模庞杂，特征选取在处理高维度数据集时是一项很重要的前置处理工作，即为一种依据可靠的准则去挑选最佳特征的方法。特征选取将有用的特征保留，移除对分类相关性较低的特征，以分辨哪些特征是人们所需要且有助于进行分类的，以此来决定维度的重要性，并希望使用最佳特征组合所得到的分类效果能接近使用全部特征所得到的分类效果，而只使用最佳特征组合不仅能降低特征空间的复杂度，且能加快分类速度提高分类性能[1]。

特征选取已被应用到许多不同领域，目前在自动文本分类处理、人脸或字符识别、医学图像处理等高维度数据集中均有大量应用[2]。常用的特征选取方法有信息增益（Information Gain，IG）[3]、卡方检验（Chi-square test，CHI）[4]、互信息（Mutual Information，MI）[5]等。然而上述方法均是在原空间中找出具有最大线性分散量或分离量的特征，而且支持向量机（Support Vector Machine，SVM）中传统的高斯核函数存在局限性，其唯一可调宽度参数决定了高斯核函數的泛化规模，同时也限制了支持向量机的泛化性能。高斯核的这种单宽度性使得在样本的稀疏区域会产生欠学习现象，而在样本的稠密区域会产生过学习现象，并直接造成了对样本分布的错误估计[6]。针对上述问题，本文提出一种基于多宽度高斯核的支持向量机特征选取算法——Feature Selection in Support Vector Machine Based on Gaussian Kernel with Multiple Widths（FSG）算法，将泛化能力更强的多宽度高斯核函数引入到支持向量机中代替传统的高斯核函数，由于多宽度高斯核函数的参数组合与特征向量一一对应，因此利用多宽度高斯核函数能体现各个特征对分类贡献程度不同，且能区分样本中各个特征重要性的特点，在多宽度高斯核函数参数优化结果的基础上，根据参数组合的大小对特征进行选取，以此找出具有最大非线性分离量的特征子集，最终达到更好的分类效果，同时减少训练时间以提高效率。利用特征选取后的特征子集在多组标准UCI数据集上进行分类实验。

1 相关概念

1.1 支持向量机

支持向量机（SVM）是由Vapnik等[7]从结构风险最小化概念中所提出的一种基于统计学习理论的分类算法。支持向量机的基本原理是为了寻求最佳的线性分类面，SVM通过定义适当的内积函数进行非线性变换，把原始数据空间变换到某一高维的特征空间，并在高维的特征空间中利用超平面对样本进行准确分类，同时保持分类的间隔最大。

其中，w为权向量，b为分类阈值，φ是一个非线性的映射函数，ξi为松弛变量，是分类错误的容许量。满足以上条件的超平面中分类间隔最大的就是最佳分类面（见图1）。

整理后的最佳分类面问题可以表示成如下约束优化问题，即在式（2）的约束下，求函数：

其中C为惩罚参数，当C值变小时，分类错误的容许量较高，分类精确度较低；反之，当C值变大时，分类错误的容许量较低，则分类精确度较高。最终可以得出最优分类函数：

式（4）中，ai是二次规划优化问题所求解的拉格朗日因子，N为支持向量数。

对于线性不可分问题，可采用在定义的空间中引入核函数K（xi，x），把低维空间变换到高维空间，对应的判别函数为：

由此可以看出，核函数及其参数的变化是决定SVM分类器泛化能力的关键因素，所以挑选适当的核函数及其参数成为SVM分类效果的保障。

1.2 多宽度高斯核函数

多宽度高斯核函数形式如下[8]：

多宽度高斯核函数可以针对每一个维度，调整不同的宽度，但如果每个维度的σ都相等，则多宽度的高斯核函数会退化成传统的高斯核函数，所以传统的高斯核函数为多宽度高斯核函数的一个特例。容易证明GKMW是一个正定核，即为SVM的可取核，通过实验验证，GKMW可以通过多参数调节解决高斯核可调参数唯一性导致的过学习问题，提高了核的学习能力和泛化能力，同时GKMW的核参数空间覆盖了单宽度高斯核的参数空间，在搭配SVM的情况下，分类效果提升明显[8]。

根据式（6）展开得到：

其中d为特征空间中特征的维数。可以将宽度参数视为特征的重要程度，1σ2i（i=1，2，…，d）代表其第i个特征的重要程度，即多宽度高斯核函数的参数组合与特征向量一一对应，多宽度高斯核函数不仅能体现各个特征对分类的贡献程度不相同，而且能区分样本中各个特征的重要性。因此，本文先对多宽度高斯核函数进行参数优化，然后在参数优化结果的基础上根据参数组合的大小进行特征选取。

2 FSG算法

2.1 多宽度高斯核函数的参数优化endprint

多宽度高斯核虽比传统的高斯核更加有弹性且能改善分类的泛化能力，但是多宽度高斯核函数所使用的参数数量等于特征的数量，对于高维数据集，传统的参数优化方法如网格搜索法在处理时面对参数的数量增加，计算复杂度会呈现指数增长，难以预先确定多宽度高斯核函数的最佳参数组合[9]。本文以特征空间中类别之间的分散程度为依据设计参数优化法，算法可以确定在固定的参数组合下，相对应的特征空间中类别之间的分散程度，当每一个训练样本在特征空间中与同类样本更加靠近、与不同类样本更加疏远时，SVM的分类效果最优，此时在最佳分类准确率下所对应的参数组合即是最佳参数组合，以此进行参数优化。

如果能通过调整这一组σ的值，即调整核函数K的值，使得特征空间中同一类训练样本的K值更接近于1，即同一类的训练样本在特征空间中更聚拢；同时使特征空间中不同类训练样本的K值（i≠j）更接近于0，即不同类训练样本在特征空间中更加分散，那么此时就能提高SVM的分类效果，图2展示了这一点。

2.2 特征选取

对于最优参数组合的结果，即式（17）的优化问题，考虑到基因表达式编程（Gene Expression Programming，GEP）在多参数优化方面的高效率，以及相较于传统方法如牛顿优化法等，GEP更易跳出局部最优得到全局最优解，本文采用GEP对结果进行寻优[12]。基因表达式编程GEP是一种基于生物基因结构和功能发明的新型自适应演化算法，融合了遗传算法简单线性的个体固定长度编码及遗传编程可变与弹性的树形结构，可以利用简单编码解决复杂问题[13]。

为了提高参数的精确度，染色体编码时采用GEP-PO基因[13]。GEP-PO基因在传统基因结构中增加一个常数区域（DC）和随机常量数组，并通过在大量随机数值常数上通过数学运算符进化参数的值，其中常数区域的长度等于基因的尾部长度。GEP-PO基因结构比起传统基因结构更加复杂，但能够扩大染色体的搜索空间，使搜索的结果更易达到峰值，提高发现全局最优的效率。对于多参数优化问题，染色体采用多基因染色体，每一个子基因均采用GEP-PO基因，GEP-PO基因中的DC域为参数域，随机常量数组为该参数的随机样本集合，取值為该参数满足约束条件的随机样本值。因此每一个基因代表一个参数的编码，每一个参数对应一个独立的随机样本参数集合。

除了采用常规GEP的遗传算子以外，还需考虑到利用GEP-PO基因涉及到的常数域和随机常量数组，因此同时还对常数域进行变异、单点重组、两点重组、倒串、插串操作。考虑到随机常数的进化主要受益于变异，因此随机常量数组采用的遗传算子主要是随机常数变异，变异操作只要保证各参数的样本取值在可行域内，则均能保证基因的合法结构。

由优化函数（17），可设计适应度函数为：

其中，Fitnessi为第i个个体的适应度函数，Ri（σ1，…，σd）为第i个个体对应的目标函数值，M为选择范围，取M=10作为选择范围，精确度为0.1。如果在参数的可行域内，得到的各参数值不满足约束条件，则该个体适应度定义为0。

此时所得到的最优参数组合{σ1，…，σd}的大小被用来确定特征的重要性，算法选取的特征根据{1σ1，1σ2，…，1σd}的大小降序排列。当1σi的值越大时，则代表此对应的特征越重要，是特征选取的优先考量；当1σi的值越小时，则代表此对应的特征越不重要，可以不用优先列入考量。

2.3 FSG算法步骤

综上所述，算法步骤归纳如下：

输出：最优的特征子集。

步骤1 初始化种群，根据式（12）和式（13）进行特征标准化。

步骤2 根据式（17）设置参数组合表达式。

步骤3 根据式（18）计算种群中每个个体的适应度值，若满足进化终止条件则转至步骤6，否则继续下一步。

步骤4 对种群实施最优保存策略，并进行遗传操作生成下一代种群。

步骤5 转至步骤3继续循环。

步骤6 解码最优个体并返回最优参数组合。

步骤7 根据最优参数组合的值对各维度参数大小进行排序。

步骤8 根据排序结果以及降低维度数p进行特征选取并返回最优特征子集。

3 实验结果与分析

3.1 实验环境与实验数据集

本文借助开源的机器学习软件weka进行实验，实验环境为：Intel Core i5-2430M 2.4GHz双核CPU，2GB内存，Windows 7 Service Pack 1（x32）[14]。基因表达式编程的优化过程利用遗传算法工具GeneXproTools 4.0完成，设置函数集合为{+、-、*、/}，终结符集为{？}，基因头长为7，种群大小为20，最大进化代数为100，常量集合大小为10，常量区间为[-2，2]。另外支持向量机的惩罚参数C使用网格搜索法搭配交叉验证法来决定，其中网格搜索法设置C的初始范围为[2-10，27]，交叉验证法设置K为5。各遗传算子参数设置如下：

本文选取标准的UCI数据库中多个不同规模的分类数据集作为实验数据，实验数据集的具体描述如表2所示[15]。

3.2 实验结果与分析

实验1：该实验用于评价FSG算法中多宽度高斯核参数优化结果的有效性，实验数据的训练集为每个数据集随机选取80%的样本，剩下20%的样本作为测试集，评价指标采用5次实验的平均。实验根据每一代种群中的适应度函数值以及其对应的SVM分类准确率作图，其中X轴为种群的迭代次数，两个Y轴的含义如下：第x代种群中适应度函数值的最大值、第x代种群中适应度函数值最大值的染色体所对应的参数组合求得的SVM分类准确率。如果适应度函数值曲线和测试准确率曲线的趋势是基本一致且为上升的，并且最后能稳定收敛，则就能说明多宽度高斯核参数优化的结果是有效的。实验结果如图3-图6所示，点线代表准确率曲线；另一条为适应度曲线。endprint

图3-图6结果显示，随着适应度函数值的变大，其测试准确率也会随之增加。根据FSG算法由类别分散程度所确定的适应度函数值可以指导种群前进的方向，从图中可以看出适应度函数值总体上逐代递增，种群也在向前进化，而与此同时随着种群的进化，支持向量机分类的准确率也逐步提高。因此在算法指导种群前进方向的基础上，参数组合确实得到了优化。迭代开始时，由于各个参数离最优值相差较大，所以测试准确率较低。经过一定次数的迭代以后，适应度函数值曲线和测试准确率曲线的上升已经趋于平缓，并且数值收敛到比较稳定的值，两条曲线共同的趋势以及最后收敛到比较稳定的数值说明本文的参数优化结果是有效的。

实验2：该实验用于评价FSG算法的性能，实验采用在很多分类任务中特征选取性能表现优秀的信息增益法IG进行对比实验[3]。信息增益法将信息增益作为特征选择的一个重要指标，信息增益被定义为一个特征能够为分类系统带来多少信息，带来的信息越多说明该特征越重要，相应的信息增益也就越大，即信息增益法是一个有效的全局特征选取算法。实验结果的评价指标采用分类准确率及分类AUC值，分类AUC（Area Under roc Curve）值表示ROC（Receiver Operating Characteristics）曲线下面积[16]，能客观反映异类样本数量不均匀时的分类结果，分类准确率及分类AUC值是常用的评估分类器性能的指标，其值越高则分类器性能越好。实验结果如表3所示。

通过表3的实验结果可以发现，在除Image Segmentation数据集外的其他3个数据集上，FSG算法的分类准确率比传统的IG算法有所提高，SVM获得更优的分类性能。同时在分类AUC值的比较上，FSG算法对样本进行特征选取的效果也比IG算法要好，从标准差的值可以看出FSG算法与IG算法均具有较好的稳定性。对于所选用的数据集，与IG算法相比，FSG算法虽然在运行时间上有一些损失，但是与提高的分类准确率相比，这些损失是可以接受的。

4 结语

本文为提高支持向量机的分类性能引入泛化能力更强的多宽度高斯核函数，并针对多宽度高斯核的特点设计了参数优化法，通过实验验证了本文参数优化结果的有效性。同时根据多宽度高斯核能区分样本中各个特征重要性的特点，提出了基于多宽度高斯核的支持向量机特征选取算法FSG，FSG算法以参数优化的结果为基础进行特征选取，以此提高支持向量机的性能。通过与传统的信息增益特征选取法在多组标准UCI数据集上进行对比实验，结果显示FSG算法能在保证稳定性的同时有效提高分类准确率。

参考文献：

[1] LIU H，SUN J，LIU L，et al.Fearure selection with dynamic mutual information[J].Pattern Recognition，2009，42（7）：1330-1339.

[2] MEI DU，YAN LIANG，LU ZHAO.On feature selection and its application to twenty newsgroups text classification[C].Proceedings of 2016 2nd International Conference on Education and Management Science （ICEMS 2016），2016：361-364.

[3] GUOHUA WU，JUNJUN XU.Optimized approach of feature selection based on information gain[J].Computer Science and Mechanical Automation （CSMA） International Conference on 2015，2015：23-25.

[4] 劉海峰，苏展，刘守生.一种基于词频信息的改进CHI文本特征选择[J].计算机工程与应用，2013，49（22）：110-114.

[5] LIU T H.Mutual information based feature selection for multivari-ate time series forecasting[C].中国自动化学会控制理论专业委员会、中国系统工程学会第35届中国控制会议论文集（E），2016：140-144.

[6] SADEEP JAYASUMANA，RICHARD HARTLEY，MATHIEU SALZMANN.Kernel methods on riemannian manifolds with gaussian RBF kernels[C].IEEE Transactions on Pattern Analysis and Machine Intelligence， 2015：2464-2477.

[7] VAPNIK V.Universal learning technology：support vector machines[C].NEC Journ of Adv Tech，2005，2（2）：137-144.

[8] 常群.支持向量机的核方法及其模型选择[D].哈尔滨：哈尔滨工业大学，2007.

[9] TAIJIA XIAO，DONG REN，SHUANGHUI LEI.Based on grid-search and PSO parameter optimization for Support Vector Machine[C]. Intelligent Control and Automation （WCICA） 2014 11th World Congress，2014.

[10] 李巍，孙涛，陈建孝，等.基于加权余弦相似度的XML文档聚类研究[J].吉林大学学报（信息科学版），2010，28（1）：68-76.

[11] 秦建强，孔祥玉，孙喜荣.数据标准化对Sevcik分形维数算法的性能影响[J].仪器仪表学报，2016，37（7）：1485-1491.

[12] 鲍莹莹.基于二阶拟柯西方程的对角拟牛顿算法研究[D].太原：太原科技大学，2013.

[13] 孟艳.基于GEP的工程结构优化设计[D].焦作：河南理工大学，2011.

[14] WITTEN I H，FRANK E.Data mining-practical machine learning tools and techniques with java implementation[M].San Francisco：Morgan Kaufmann Publishers，2000.

[15] BLAKE C L，MERZ C J. UCI machine learning repository[EB/OL].2006 Available http：//www.ics.uci.edu/～mlearn/MLSummary.html.

[16] PROVOST F，FAWCETT T.Analysis and visualization of classifier performance： comparison under imprecise class and cost distributions[C].Proceedings of 3rd International Conference on Know ledge Discovery and Data Mining，1997：43-48.endprint