特征选择.ppt

数据挖掘中的特征选择算法,陈良龙 2011年10月,主要内容,特征选择概述 特征选择在数据挖掘中的重要性 特征选择算法概述,什么是特征选择,特征选择是模式识别与数据挖掘领域的重要数据处理方法之一。 特征选择定义为从有N个特征的集合中选出具有M个特征的子集，并满足条件M≤N。 特征选择(也叫属性约简)能够为特定的应用在不失去数据原有价值的基础上选择最小的属性子集，去除不相关的和冗余的属性。,,它包括特征提取和特征选择两个方面。 特征提取广义上指的是一种变换，将处于高维空间的样本通过映射或变换的方式转换到低维空间，达到降维的目的. 特征选择指从一组特征中去除冗余或不相关的特征来降维。,为什么需要特征选择,特征选择作为统计学领域的经典问题，自上个世纪60年代起就有学者对此进行了研究；同时，它也是机器学习领域的重要问题；自90年代以来，特征选择的研究引起了机器学习领域众多学者前所未有的重视。,,1）许多学习算法的性能受到不相关或冗余特征的负面影响。大多数学习算法所需训练样本的数目随不相关特征的增多而急剧增加。因此，选择好的特征不仅可以减小计算复杂度，提高预测精度，而且有助于寻找更精简的算法模型。,,2)大规模数据处理问题的不断出现，如信息检索，遗传基因分析等刚。所谓大规模，一方面指样本数目的庞大，另一方面指描述样本的特征维数高。3)随着应用领域的不断扩大。所遇到的数据类型也将不断变化。因此．特征选择算法的设计需要适应新的数据类型。,数据挖掘的过程回顾,1）数据清理：消除噪音或不一致数据 2）数据集成：多种数据源可以组合在一起 3）数据选择：从数据库中提取与分析任务相关的数据 4）数据变换：数据变换或统一成适合挖掘的形式；如，通过汇总或聚集操作,,5）数据挖掘：基本步骤，使用智能方法提取数据模式 6）模式评估：根据某种兴趣度度量，识别提供知识的真正有趣的模式 7）知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识特征选择是整个知识发现(KDD)处理过程中的一环，对KDD的预处理、挖掘、后处理都有帮助。,趋势,数据挖掘就是从海量数据中发现知识，面临的信息越来越复杂 文本信息 基因表达信息 从低维度信息到高维度信息,特征选择算法的4个要素,一般而言，特征选择可以看做一个搜索寻优的问题。 对大小为n的特征集合，搜索空间由2的n次方减1种可能的状态构成。 Davie8等证明最小特征子集的搜索是一个NP问题嘲．即除了穷举式搜索，不能保证找到最优解。,,实际应用中，当特征数目较多的时候．穷举式搜索因为计算量太大而无法应用。因此人们致力于用启发式搜索算法寻找次优解。 4个要素：搜索的起点和方向；搜索策略；特征评估函数；停止原则。,,搜索方向即评价的特征子集产生的次序。搜索的方向有从空集开始的前向搜索、从全集开始的后向搜索、双向搜索和随机搜索等。,搜索方向,1）前向搜索：搜索起点是空集S。依据某种评价标准，随着搜索的进行，从未被包含在S里的特征集中选择最佳的特征不断加入S。2)后向搜索：搜索起点是全集S．依据某种评价标准不断从S中剔除最不重要的特征。直到达到某种停止标准。,,3)双向搜索双向搜索同时从前后两个方向开始搜索。一般搜索到特征子集空间的中部时，需要评价的子集将会急剧增加。当使用单向搜索时。如果搜索要通过子集空间的中部就会消耗掉大量的搜索时间。所以双向搜索是比较常用的搜索方法。 4)随机搜索随机搜索从任意的起点开始，对特征的增加和删除也有一定的随机性。,搜索策略,假设原始特征集中有n个特征(也称输入变量)，那么存在2N-1（N为次方）个可能的非空特征子集。搜索策略就是为了从包含2N-1个候选解的搜索空间中寻找最优特征子集而采取的搜索方法。 一般有三种策略：,,1)穷举式搜索它可以搜索到每个特征子集。缺点是它会带来巨大的计算开销，尤其当特征数较大时，计算时间很长。通过分支定界法剪枝处理缩短搜索时间。2)序列搜索它避免了简单的穷举式搜索，在搜索过程中依据某种次序不断向当前特征子集中添加或剔除特征。从而获得优化特征子集。如：前向后向搜索研。3)随机搜索由随机产生的某个候选特征子集开始，依照一定的启发式信息和规则逐步逼近全局最优解，如遗传算法。,特征评估函数,评价标准在特征选择过程中扮演着重要的角色，它是特征选择的依据。评价标准可以分为两种：一种是用于单独地衡量每个特征的预测能力的评价标准：另一种是用于评价某个特征子集整体预测性能的评价标准。,停止准则,停止标准决定什么时候停止搜索，即结束算法的执行。它与评价准则或搜索算法的选择以及具体应用需求均有关联。常见的停止准则一般有：1)执行时间即事先规定了算法执行的时间．当到达所制定的时间就强制终止算法运行，并输出结果。,,2)评价次数即制定算法需要运算多少次。通常用于规定随机搜索的次数。尤其当算法运行的结果不稳定的情况下，通过若干次的运行结果找出其中稳定的因素。3)设置阈值一般是给算法的目标值设置一个评价阈值，通过目标与该阈值的比较决定算法停止与否。不过，要设置一个合适的阈值并不容易。需要对算法的性能有十分清晰的了解。否则。设置阈值过高会使得算法陷入死循环．阈值过小则达不到预定的性能指标。,特征算法的分类,根据在特征选择的过程中，特征子集的评价是否用到在决策机器构造过程中所使用的学习算法可以分成三大类：1）Filter方法2）Wrapper方法3）Filter和Wrapper组合式方法,,Filter方法糊是一种计算效率较高的方法．它独立于后续的学习算法，采用一些基于信息统计的启发式准则来评价特征的预测能力，目前用的最多是相关测量法、类间和类内距离测量法、信息熵法等等。 Filter方法通常根据特征评价准则选取预测能力较优的那些特征组成特征子集．其中存在的一个主要问题是它并不能保证选择出一个规模较小的优化特征子集．一般特征子集规模较大。 该方法的一个明显优势在于可以很快地排除一部分非关键性的噪声特征，缩小优化特征子集搜索范围。可作为特征的预选器。,,Wrapper方法在特征选择时依赖具体机器学习算法。它在筛选特征的过程中直接用所选特征子集来训练学习器，根据测试集在学习器上的性能表现来评价该特征子集的优劣。该方法在计算效率上不如Filter方法，但其所选的优化特征子集的规模相对要小一些。目前，此类方法是特征选择研究领域的热点。,,Filter和Wrapper组合式方法的基本思想：先用Filter模型作特征预选，剔除部分不相关特征，降低数据集维度；再用Wrapper模型在预选特征集上进一步的特征精选。,