数据挖掘中的特征选择算法综述及基于WEKA的性能比较
良龙
（大学信息科学与工程学院）
摘要：自进入21世纪以来，随着信息技术的飞速发展，产生了海量的具有潜在应用价值的数据，将这些数据转换成有用的信息和知识的需求也越来越迫切，因此数据挖掘引起了信息产业界和整个社会的极大关注。
特征选择作为一种常见的降维方法，在数据挖掘中起到不可忽视的作用。
本文首先介绍了数据挖掘处理对象的趋势，然后概述了特征选择算法，最后通过数据挖掘软件WEKA比较了分别基于Filter和Wrapper方法的特征选择算法的性能。
关键词：数据挖掘；特征选择；WEKA；Filter；Wrapper；性能比较
A survey of feature selection algorithm in Data Mining and the
performance comparison based on WEKA
Abstract: As the mass of data which have potential application and value have been created by the rapid development of information technology since the 21st century, the needs to transferring these data into useful information and knowledge are being more and more urgent, so the Data Mining caused the whole society and the information industry of great concern. Feature selection is critical to Data Mining for that it is a common method to reduce dimensions. The tendency of Data Mining’s
handler object is first introduced in this paper, then introduction of the feature selection algorithm, and finally compared the performance of algorithms based on methods of Filter and Wrapper, respectively, by using WEKA (i.e. software used in Data Mining).
Keywords: Data Mining; Feature selection; WEKA; Filter; Wrapper; Performance comparison
1 引言
数据挖掘(Data Mining)就是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的。
还有很多和这一术语相近似的术语，如从数据库中发现知识(KDD)、数据分析、数据融合(Data Fusion)以及决策支持等。
人们把原始数据看作形成知识的源泉，就像从矿石中采矿一样。
原始数据可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。
随着信息技术的飞速发展，越来越复杂的数据成为数据挖掘的处理对象，如文本数据、基因序列等。
一般的，这些对象具有几十、几百甚至几万个属性。
通过将这些对象表示成高维属性空间中的点或向量，把客观世界中的对象集用高维数据集合来。
然而，随着不相关属性的增加，训练样本的数目也将急剧。
一种解决的方法是建立高效的面向高维数据的算法，另外一种则是降低维度。
并且由于这些属性之间很有可能存在冗余等问题，选择好的特征算法成为解决这些问题的可行方法。
特征选择(也叫属性约简)能够为特定的应用在不失去数据原有价值的基础上选择最小的属性子集，去除不相关的和冗余的属
性；它能提高数据的质量，加快挖掘的速度并且使得挖掘出的规则更容易理解。
2 特征选择算法的4个要素
一般特征选择算法必须确定以下4个要素：1)搜索起点和方向；2)搜索策略：3)特征评估函数；4)停止准则。
2.1 搜索起点和方向
搜索起点是算法开始搜索的状态点，搜索方向是指评价的特征子集产生的次序。
搜索的起点和方向是相关的，他们共同决定搜索策略。
一般的，根据不同的搜索起点和方向，有以下4中情况：
（1）前向搜索(SFG)：从空集S开始，依据某种评价标准，随着搜索的进行，从未被包含在S里的特征集中选择最佳的属性不断加入S。
（2）后向搜索(SBG)：从全集S开始，依据某种评价标准不断从S中选择最不重要的属性，直到达到某种停止标准。
它是对前向搜索的补充。
（3）双向搜索(BG)：双向搜索同时从两个方向开始搜索。
一般搜索到特征子集空间的中部时，需要评价的子集数将会急剧增加。
当使用单向搜索时，如果搜索要通过子集空间的中部就会消耗掉大量的搜索时间，所以双向搜索是比较常用的搜索方法。
（4）随机搜索(RG)：随机搜索从任意的方向开始，对属性的增加和删除也有一定的随机性。
这样可克服局部极小。
LVF算法比较有代表性。
2.2 搜索策略
假设原始特征集中有n个特征(也称输入变量)，那么存在个可能的非空特征子集。
搜索策略就是为了从包含个候选解的搜索空间中寻找最优特征子集而采取的搜索方法。
一般分为3种搜索策略：（1）穷举式搜索：它可以搜索到每个特征子集。
缺点就是它会带来巨大的计算开销，尤其是当特征数比较大时，计算时间很长。
分支定界法（Branch and Bound，BB）通过剪枝处理缩短搜索时间。
（2）序列搜索：它避免了简单的穷举式搜索，在搜索过程中依据某种次序不断向当前特征子集中添加或剔除特征。
从而获得优
化特征子集。
比较典型的序列搜索算法如：前向后向搜索、浮动搜索、双向搜索、序列向前和序列向后算法等。
序列搜索算法较容易实现，计算复杂度相对较小，但容易陷入局部最优。
（3）随机搜索：由随机产生的某个候选特征子集开始，依照一定的启发式信息和规则逐步逼近全局最优解。
例如：遗传算法(Genetic Algorithm，GA)、模拟退火算法(Stimulated Annealing ，SA)、粒子群算法（Particl Swarm Optimization，PSO）和免疫算法Immune Algorithm，IA)等。
2.3 特征评估函数
评价标准在特征选择过程中扮演着重要的角色，它是特征选择的依据。
评价标准可以分为两种：一种是用于单独地衡量每个特征的预测能力的评价标准；另一种是用于评价某个特征子集整体预测性能的评价标准。
分别对应两种重要的方法类型：Filter 和Wrapper方法。
在方法中，一般不依赖具体的学习算法来评价特征子集，而是借鉴统计学、信息论等多门学科的思想，根据数据集的在特性来评价每个特征的预测能力，从而找出排序最优的的若干特征组成特征子集。
而Wrapper方法中，用后续的学习算法嵌入到特征选择过程总，通过测试特征子集在此算法上的预测性能来决定其优劣，而极少关注特征子集中每个特征的预测性能。
因此，后者并不要求最优特征子集中的每个特征都是最优。
2.4 停止准则
停止准则决定什么时候停止搜索，即结束算法的执行。
它与评价准则或搜索算法以及具体的应用需求均有关联。
常见的停止准则有：
（1）执行时间：事先规定算法执行的时间，到达设定时间就强制终止算法；（2）评价次数：设定算法运算次数，一般用于随机搜索；
（3）设置阈值：设置一个评价阈值，到达设定值就结束执行。
不过这个阈值可能出现过低或过高的情况。
3 特征选择算法分类
从特征选择算法的四个要素可见，重点在于选择最优特征子集所需要的两个步骤上，即搜索策略和评价标准。
下文将分别按照这两个步骤的标准对特征选择算法进行分类。
3.1 按照搜索策略分类
按照算法在进行特征选择过程中所选择的搜索策略，可以把特征选择算法分为全局最优特征选择算法、随机搜索策略的特征选择算法和序列搜索策略的特征选择算法3类。
本文重点介绍序列搜索策略的特征选择算法。
3.1.1 全局最优搜索的特征选择算法
到目前为止，唯一采用全局最优搜索策略得到最优结果的特征选择方法是“分支定界（Branch and Bound）”算。
采用这种搜索策略的特征选择算法，能保证事先确定优化特征子集中特征数目的情况下，找到相对可分性判据而言的最优特征子集。
但是这种策略存在3个主要的问题：1）事先确定最优特征子集中特征数目的多少比较困难；2）合乎问题要求的满足单调性的可分性判据难以设计；3）当处理高维度问题，算法开销大。
3.1.2 随机搜索策略的特征选择算法
特征选择本质上是一个组合优化问题，求解这类问题可采用非全局最优目标搜索方法，其实现是依靠带有一定智能的随机搜索策略。
它在计算过程中把特征选择问题和模拟退火算法、禁忌搜索算法、遗传算法、粒子群算法或随机重采样过程结合，以概率推理和采样过程作为算法基础。
遗传算法在这一领域的应用最为广泛。
W．Siedlechi 等学者提出早期的基于遗传算法和K近邻分类器的特征选择方法。
然后是J．Y柚g 等学者又提出了使用遗传算法结合人工神经网络分类器进行特征选择的方。
通常此类方法是根据特征子集在训练集上的分类性能作为特征子集的评价准则。
该方法可以得到一个近似最优解，有较好的应用效果。
但是，当遇到特征数较多的情况，算法的运行会耗费大量的时间。
3.1.3 序列搜索策略的特征选择算法（1）单独最优特征组合。
该方法基于计
算个特征单独使用时的判据值对特征进行排序。
取前d个特征组合为最优特征子集。
很多情况下，这种算法能去除一些不相关的变量，可以作为一种特征预选方法。
（2）序列向前选择方法（Sequential Forward Selection, SFS）。
一种“自上而下”的搜索方法，即向前搜索。
这种算法计算量相对较小，但是没有充分考虑特征之间的相关性。
（3）广义序列向前选择（Generalized Sequential Forward Selection, GSFS）。
该方法是SFS的加速方法，一次可以加入多个特征。
该方法在特征选择相关性上有一定提高，但是增加了计算量，且相关性的问题没有彻底解决。
（4）序列向后选择（Sequential Backward Selection, SBS）。
一种“自底向上”的搜索方法，即向后搜索。
这种方法的计算量比SFS要大，但是充分考虑了特征之间的相关性。
在采用同样合理的准则函数的时候，它的实际计算性能和鲁棒性优于SFS 算法。
（5）广义序列向后选择（Generalized Sequential Backward Selection, GSBS）。
相对于SBS而言，一次可以剔除多个不合要求的特征。
这种方法的速度较快，性能相对较好。
但是有时候特征剔除操作太快，容易丢失重要的特征。
（6）增l去r选择方法。
这种方法根据l 和r的大小来决定选择SFS还是SBS，它允许特征选择过程中进行回溯。
因而比SFS运算效果要好，比SBS计算速度要快。
（7）广义增l去r选择方法。
用GSFS 和GSBS作为折中，其操作较为复杂，难以制定实际的规则加以利用。
（8）浮动搜索方法。
采用浮动步长进行搜索，这是一种比较实际的改良机制。
从目前来看，随机搜索策略和启发式搜索策略使用较为广泛。
3.2 按照特征子集评价策略分类
根据特征选择过程中是否依赖后续的学习分类方法来评价特征子集，可以分为Filter方法、Wrapper方法以及两者的折中3类。
3.2.1 基于Filter评价策略的特征选择方法
Filter方法是一种计算效率较高的方法，独立于后续的分类方法，采用一些基于信息统计的启发式准来评价特征的预测能力。
目前用的最多的是相关测量法、类间和类距离测量法、信息熵法、ReliefF等等。
其主要问题是当特征和分类器关联较大时，不一定找到规模较小的最优特征子集。
3.2.2基于Wrapper评价策略的特征选择方法
Wrapper方法在特征选择时依赖具体分类方法。
根据测试集在分类器上的性能表现来决定特征子集的优劣。
该方法的效率不及Filter，但是其所选的优化特征子集的规模相对要小一些。
目前，该类方法是研究的重点。
当前有决策树、遗传算法、人工神经网络、支持向量机SVM等作为分类器。
3.3.3 Filter和Wrapper折中的策略
基于Filter方法计算开销较小以及Wrapper方法较好的预测能力，许多学者提出折中的方法，用前者作为分类的预选器，后者在预选特征集上做进一步的特征精选。
如Huang提出的一种两阶段组合式特征选择算。
然而，目前的二阶段组合式特征选择算法的性能还收到以下因素的影响：1）Filter 模型中采用何种特征评价准则较好；2）在高维情况下，第二阶段的Wrapper方法的计算开销仍然较大。
因而，出现了很多单纯利用特征子集的预测能力或者特征及规模作为选择依据的方法，如基于多目标免疫优化的特征方等。
4 WEKA中的特征选择算法及性能比较实例
该软件中根据特征选择过程的重要的两个步骤，即搜索策略和评价策略，嵌入了相关的方法。
本文分别测试了Filter类方法和Wrapper类方法的性能，测试数据为一组银行数据。
4.1 WEKA中的搜索策略方法
按照搜索策略的分类，这里列举各个分类的几种方法：1）全局最优搜索方法：BestFirst（最好优先），ExhaustiveSearch （穷举搜索）；2）随机搜索方法：
RandomSearch（随机搜索），ScatterSearchV1（离散搜索）；3）序列搜索方法：a.单独最优组合：RankSearch（评估器计算属性判据值并排序），Ranker（属性判据值排序）；b.向前搜索：LinearForwardSelection（线性向前搜索）；
c.向后搜索：FCBFSearch（基于相关性分析的特征选择方法）；
d. 增l去r选择方法：RaceSearch（比较特征子集的交叉验证错误情况），GreedyStepwise（向前或向后的单步搜索）；
e. 浮动搜索方法：SubsetSizeForwardSelection（按照特征子集大小向前线性搜索，这是线性搜索的扩展）；
f.启发式搜索：GeneticSearch（基于Goldberg（1989）提出的简单遗传算法），TabuSearch（禁忌搜索）。
4.2 WEKA中的评价策略方法
按照评价策略的两大方法，上文已经提到，这两大方法基于是否使用后续的分类方法来区别，且Filter方法注重对单个属性进行评价，Wrapper方法侧重对特征子集进行评价。
这里列举各个分类的几种方法：1）Filter方法：ChiSquaredAttributeEval——根据与分类有关的每一个属性的卡方值（统计学词汇）进行评估；FilteresAttributeEval——运行在任意过滤器之后的数据上的任意属性评估；GainRatioAttributeEva——根据与分类有关的每一个属性的增益比进行评估；InfoGainAttributeEval——根据与分类有关的每一个属性的信息增益进行评估；SignificanceAttributeEva——计算双向功能的概率意义评估属性值。
2）Wrapper 方法：CfsSubsetEval——根据属性子集中每一个特征的预测能力以及它们之间的关联性进行评估；ClassifierSubsetEval——根据训练集或测试集之外的数据评估属性子集；WrapperSubsetEval——使用一种学习模式对属性集进行评估；ConsistencySubsetEval——根据利用属性子集进行分类时得到的分类值的一致性进行评价。
3）Filter与Wrapper结合：OneRAttributeEval——根据OneR分类器评估属性。
4.3 WEKA中特征选择算法的性能比较实例
本次比较基于的数据集见表1。
根据其中的属性可知，married和single两个属性是冗余，我们通过不同方法来测试是否能够识别出这个冗余，以及比较它们的性能。
下面列举两组算法的测试结果及比较：
（1）评价策略ChiSquaredAttributeEval和搜索策略Ranker：得出的结果是剔除了属性single，选择的属性为其余12个。
（2）评价策略ConsistencySubsetEval和搜索策略GreedyStepwise：可知选择的属性为id。
从两者的结果来看，按照第一组算法的得分情况，属性id是得分最高，与后者的结果意也是一致的。
由于数据集比较小，计算速度上无法获得具体的细节，就精确度来讲，后者是相对而言较好。
因为属性id可以作为最优的特征来描述数据集。
5 结论
本文从特征选择的四个要素出发，综合性的介绍了数据挖掘中的特征选择算法，并且对目前的一些特征选择算法做了具体的分类。
通过WEKA对一组简单的数据在两组特征算法上做了比较，得出的结论符合理论的分析结果。
当然，由于使用的数据集比较小，包括实例数目和属性维度都较小，所以得出的结果不能得出两者之间的开销问题。
表1-测试数据集
参考文献
[1] Jiawei Han，Micheline Kamber著，明，孟小峰译．数据挖掘概念与技术(Data Mining：Concepts and Techniques)．：机械工业，2008．
[2] 婧昊.面向高维数据挖掘的特征选择方法研究.大学硕士论文，2006.
[3] Xing E, Jordan M, Karp R. Feature selection for high-dimensional genomic microarray data [C]// Intl. conf. on Machine Learning, 2001: 601-608.
[4] Inza I,Larranaga P,Blanco R.Filter versus wrapper gene selection approaches in DNA microarray domains[J]. Artificial Intelligence in Medicine,2004,31(2):91-103.
[5] 冯斌.群体智能优化算法及其在生化过程控制中的应用研究[D].：江南大学，2005.
[6] Chen Xue-wen.An improved branch and bound algorithm for feature selection[J].Pattern Recognition Letters,2003,24(12):1925-1933.
[7] Yang J,Honavar V.Feature subset selection using a genetic algorithm[J].IEEE Intelligence Systems,1998,13(2):44-49.
[8] Jain A K,Duin R DW,Mao J C.Staisitical pattern recongnition[J]. A review.IEEE Trans on Pattern Analysis and Machine Intelligence,2000,22(1):4-37.
[9] Huang Chen-jung, Yang Dian-xiu, Chuang Yi-ta. Application of wrapper approach and composite classifier to the stock trend prediction[J]. Expert Systems with Application,2008,4(34):2870-2878.
[10] 计智伟，珉，建新.特征选择算法综述.电子设计工程：第19卷，第9期.2011.。
