数据挖掘中的特征选择算法综述及基于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类。