多准则赋权排序与C-SVM相结合的特征选择算法

孙 勤，蒋艳凰，胡 维，张 毅，高 峰

1.国防科学技术大学 高性能计算国家重点实验室，长沙 410073

2.国防科学技术大学 计算机学院，长沙 410073

3.中国人民解放军 91550部队

1 引言

特征选择是数据挖掘中特征降维的重要方式之一[1]，通过特征选择能适当去除无关和冗余特征，降低系统的存储负担和不必要的模型训练开销，同时能提高学习算法的性能。与特征提取相比，特征选择是从原始特征集中选出一组最能替代原始特征的子集达到降维的目的，它不改变原始集合的物理特性，能在降维的同时真正降低系统的存储负担和时间开销。

根据特征选择是否与后续学习算法相关，可将其分为两类：过滤式（Filter）[2]和封装式（Wrapper）[3]特征选择算法。过滤式特征选择独立于学习过程，它直接利用原始数据集的统计特性进行评估从而选出合适的子集，其效率高，但评估准确度低；使用过滤式方法力求某种评价准则最优[4]，而对于不同的特征集，很难确定最适合的评价准则。目前已有的基于过滤式算法的评价标准有信息度量[5-6]、距离度量[6-8]、一致度度量等[8-9]。不同评价方法的复杂度和分类精度各不相同，不同的准则着重于不同的层面反应特征的优劣，单一的准则往往无法全面评估特征集的好坏[10]。封装式算法直接利用学习算法的准确率评价特征子集的好坏，其评估准确率高但是运行速度慢，特征越多，运行速度越慢。

针对两类特征选择算法各自存在的优缺点，本文提出一种过滤式和封装式相组合的特征选择方法mCRC（Feature Selection Algorithm Based on multi-Criterion-Ranking and C-SVM），使用两种准则同时对特征评估赋权，剔除完全冗余和不相关特征，得到重要程度权重降序排列的特征子集，再通过C-SVM分类器[11]采用顺序前向浮动搜索算法（Sequential Forward Floating Selection，SFFS）[12]搜索分类精度高的特征，得到最佳特征子集，从而补充特征选择两大类算法存在的不足。

2 相关定义

2.1 互信息

互信息[5-6]是用来度量两个变量的统计相关性的重要方法，也是目前特征选择中普遍运用的评价准则。互信息的计算公式为：

其中，H(X)和H(Y )为X和Y的信息熵，H(X ,Y)为两者的联合熵。设p(x ,y)为(X ,Y )的联合概率，则：

类别与各特征之间的互信息为：

特征两两之间的互信息为：

通过公式（2）可以计算特征与类别之间的关联程度，I值越大，特征与类别标签的相关性程度越高；I=0时特征与类别不相关，可以剔除。

通过公式（3）可以计算特征两两之间的相关性，I值越大，说明特征之间的冗余度越高；当fi和fj完全冗余时，则二者保留其一即可。

2.2 距离度量

距离度量也可以称作类别可分性度量[7-8]。对于有监督分类，不同类别间距越大类别的相似程度越低，可区分的概率越大，相同类别之间距离越小相似性越大，可区分性越小，分类准确率越高。基于距离度量的特征子集评价能有效提高小样本与线性不可分数据集上特征选择的能力。特征选择应该选择类间间距大且类内间距小的特征。

设第j维特征fj包含N个样本，这N个样本的平均值为avg(j)，则：

其中xt()j为第t个样本的第j维特征。

设第c'类样本个数为M，则第c'类样本的第j维特征的特征均值为avgc'()j，则

第j维特征的类间距离为：

则第j维特征fj的类别可分性度量可表示为：

可用W(fj)来衡量特征的分类能力。W(fj)越大，特征的分类准确率越高。

2.3 C-支持向量机

在机器学习中，C-支持向量机（C-SVM）[11]是一种用于分类的监督式学习算法，其基本思想是样本点在线性不可分的情况下，引入松弛变量ξ和从输入空间Rn到Hilbert空间Hil的变换：

映射为：

这样便得到原始问题：

其中δ为惩罚参数，δ越大表示对错误分类的惩罚越大且δ＞0。

对于多分类问题，C-SVM通常转化为多个两类问题解决。C-SVM作为迄今为止最小错分率和最大泛化能力的分类器，应用于特征选择能用来分辨出分类正确率高的特征。因此，本文采用C-SVM作为分类器对特征集分类，筛选出分类精确度高的特征，从而得到最佳特征子集。

3 mCRC特征选择算法

过滤式特征选择中的互信息和距离两种度量方法各有优缺点，若将两种评价准则结合起来共同对特征进行评价能够综合各方法的优势，能获得比单个评价准则更高的精度。基于以上阐述，本文提出了多准则赋权排序的过滤式算法和C-SVM互补的特征选择算法mCRC。

3.1 特征排序与筛选

通过互信息和距离两种度量准则同时计算原始特征集S中各特征与类别C的相关性，求得各特征的均值权重，在此过程可删除互信息为零，即与类别不相关的特征，得到去掉不相关特征且含均值权重的特征子集U；对于集合U，本文设定一个初始空集Q，从U每次选择一个特征放入Q中。在第一步，使得

gj∈Q，对于U中未被选中的特征，取任意gj若H(fi)=H(gj)=H(fi,gj)，则 fi与 gj完全冗余，从U 中删除 fi，否则，对于fi取互信息最大值Imax(fi,gj)表示其与子集Q的冗余度，通过最大相关最小冗余标准来评估特征的重要性，并选择当前重要程度最高的特征放入集合Q中，评价公式为：

其中Q的第l（l为Q的大小）个特征被选依据为：

3.2 C-SVM封装及最佳特征子集的确定

在过滤排序阶段，mCRC算法删除了不相关的和完全冗余的特征，并将特征进行重要性降序排序，使得在封装阶段可以直接利用C-SVM对过滤阶段的排序结果采用SFFS策略选择最佳特征子集，在搜索之前设定阈值λ（λ＞0，且λ=1时退化为顺序前向搜索），当搜索到某个特征时子集分类精度上升，则将该特征加入最佳子集中，若搜索到某个特征之后的连续λ个特征都使得子集的分类精度均不大于这个特征的精度，则停止搜索。这种方式能够较快地确定特征选择的结果。相比传统的Wrapper算法利用分类器对整个原始特征集进行评估再做特征选择，mCRC算法节省了特征选择所需的时间。另过滤器排序部分多准则同时评估与单准则评估相比大大提高了权重的可靠性。

3.3 mCRC算法描述

根据以上描述，给出多准则赋权排序与C-SVM相结合的特征选择算法（mCRC）的伪代码描述：

4 实验设置与分析

本文采用UCI[13]机器学习知识库中的数据集进行测试，表1给出了实验所用数据集的基本信息。实验环境为：Intel Core i5-6400 2.70 GHz CPU，8 GB内存，Win10 64位操作系统，Matlab R2010a。

为了使实验结果更具统计意义，采用5次交叉验证[14]实验，同时实验采用LibSVM工具箱[15]，C-SVM的核函数采用径向核函数RBF，并采用网格搜索来选取最优惩罚因子δ和核函数参数g。

表1 实验数据集基本情况表

图1 mCRC、mRMR、CSB在各数据集上排序性能比较图

实验分为两部分，第一部分，分别对mCRC算法、基于互信息排序的mRMR算法[5]及基于类别可分性排序的CSB算法[7]的排序部分进行性能比较，用三种算法将特征进行排序后再用C-SVM对去除了完全冗余和完全不相关并按重要性降序排好的所有特征逐一进行子集分类精度测试，检验各算法能否识别重要特征。图1给出了三种算法的排序阶段在各数据集上的实验结果。

由图1可知，对于表1中的8个数据集，三种算法都表现出随着特征数目的增多，分类精度先不断上升，随后保持相对稳定或下降状态，表明通过mCRC、mRMR、CSB三种算法各自的过滤排序部分对特征进行重要性排序之后可以通过少量特征就达到与全集相同甚至高于全集的分类率，说明三种特征选择算法的过滤排序部分都基本能够识别重要特征。同时几乎在所有数据集上mCRC都可以在比其余两种算法少的特征数目下达到甚至高于初始数据集的分类准确率。但是，从图1中也可以看出，三种算法并不是随特征数据一直递增到某个精度后再稳定或下降，在精度上升过程中个别特征的加入会使得算法的性能突然下降再上升，说明排序过程存在某些误差，因此，本文不用顺序前向搜索算法来获取最佳特征子集，而是通过采用设置一个λ值的顺序前向浮动搜索的方法来得到最佳特征子集，从而避免采用顺序前向搜索时精度在上升过程中因个别特征的加入降低特征集的分类性能而停止搜索达不到最佳性能的情况。λ值不宜设的过大，过大的λ值相当于在整个特征集上进行顺序浮动前向搜索而失去的特征排序的意义。

实验第二部分采用mCRC、mRMR、CSB三种特征选择算法的排序部分分别对特征排序后再通过C-SVM和设阈值λ的SFFS进行性能比较。λ取2和3进行两次实验，实验结果如表2、表3所示。

表2中λ等于2时的SFFS结果显示：mCRC在6个特征集上有规模最小的最佳属性子集，在7个数据集上的最佳属性子集的分类性能高于其余两种算法；mRMR在2个数据集上有最小约减的最佳特征子集，但相比其余两种算法，mRMR在所有数据集上的最佳特征子集的分类性能最低；CSB在3个数据集上有最小约减的最佳属性子集，相比其余二者，CSB在1个数据集上最佳属性子集的分类精度最高。从效率来看，mCRC在4个数据集上有最高效率，而mRMR只有一个，CSB只有两个。

表3取λ等于3时的SFFS结果与表2相比精度总体稍有变化，在多个数据集上mCRC的精度仍然最高，说明λ变化，mCRC的分类性能仍然最优；相比表2，表3中λ取3使得各算法在个别数据集上对低精度的特征个数容忍度稍微增大，但在所有数据集上运行时间都有所增长，由此得出对于效率要求高的学习算法，λ的取值应尽量小。总体来看，在表3中，mCRC无论在从最佳子集规模、分类精度还是运行时间来看，mCRC算法都占优势。

表2、表3表明无论在效率、最佳特征子集大小还是分类精度上，mCRC的性能都优于mRMR和CSB，说明基于多准则赋权排序选择的最佳特征子集不仅规模小，泛化能力好，而且运行效率高。对于时间性要求很高的学习算法，数据处理的速度稍有提高都能大大提高学习算法的性能。而对于所有学习算法，数据集的分类精度越高越好。本文提出的mCRC算法能兼顾快速识别重要特征、得出小规模的最佳特征子集的同时减轻计算机的存储负担。

表2 λ取2时mCRC、mRMR、CSB的性能比较

表3 λ取3时mCRC、mRMR、CSB的性能比较

5 结论

本文提出了一种基于两种准则赋权排序的过滤式和C-SVM混合的特征选择方法，该方法使用两种准则同时评估特征与类别的相关度及特征间的冗余度来对特征进行赋权排序，并使用C-SVM对按重要性降序排列的特征子集通过设容忍度阈值λ的顺序前向浮动搜索策略（SFFS）搜索最优特征子集。实验结果表明，mCRC能够识别重要特征，相较于单准则赋权排序，mCRC能在相对较短的时间内得到分类精度更高的特征子集，并较大力度地降低了数据集的特征数，为快速并高效地对海量及高维数据进行挖掘提供了有力保障。

本文中两种准则对特征进行赋权后采用平均值得到特征的最终权重，这样面临某个准则对某一特征集的评估很好，而另一准则对此特征集的评估效果很差，取平均权重会使得效果较差的准则拉低效果较好的准则的评估性能，如表2中的数据集segment。下一步，计划采取某种方式对两种准则进行加权，使得对某个数据集评估效果较好的准则占较重权重，评估效果较差的准则占较小权重，从而使得本文提出的mCRC特征选择算法更具适应性。

[1]Kantardzic M，坎塔尔季奇，王晓海，等.数据挖掘：概念，模型，方法和算法[M].北京：清华大学出版社，2013.

[2]Saeys Y，Inza I，Larrañaga P.WLD：review of feature selection techniques in bioinformatics[J].Bioinformatics，2007，23（19）：2507-2517.

[3]John G H，Kohavi R，Pfleger K.Irrelevant features and the subset selection problem[C]//11th International Conference on Machine Learning，1994：121-129.

[4]Li Y，Lu B L.Feature selection based on loss-margin of nearest neighbor classification[J].Pattern Recognition，2009，42（9）：1914-1921.

[5]Peng H，Long F，Ding C.Feature selection based on mutual information criteria of max-dependency，max-relevance，and min-redundancy[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（8）：1226-1238.

[6]姚旭，王晓丹，张玉玺，等.特征选择方法综述[J].控制与决策，2012，27（2）：161-166.

[7]张岐龙，单甘霖，段修生，等.基于特征空间中类别可分性判据的特征选择[J].火力与指挥控制，2010，35（6）：118-120.

[8]任双桥，傅耀文，黎湘，等.基于分类间隔的特征选择算法[J].软件学报，2008，19（4）：842-850.

[9]Dash M，Liu H.Consistency-based search in feature selection[J].Artificial Intelligence，2003，151（1/2）：155-176.

[10]李勇明，张素娟，曾孝平，等.轮询式多准则特征选择算法的研究[J].系统仿真学报，2009，21（7）：2010-2013.

[11]邓乃扬，田英杰.数据挖掘中的新方法：支持向量机[M].北京：科学出版社，2004.

[12]Pudil P，Novovičová J，Kittler J.Floating search methods in feature selection[J].Pattern Recognition Letters，1994，15（11）：1119-1125.

[13]Blake C.UCI repository of machine learning databases[C]//Neural Information Processing Systems，1998.

[14]Bengio Y，Grandvalet Y.No unbiased estimator of the variance of k-fold cross-validation[J].Journal of Machine Learning Research，2004，5（3）：1089-1105.

[15]Chang C C，Lin C J.LIBSVM：A library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology（TIST），2011，2（3）：389-396.