特征选择

特征选择
1.背景
数据集的大小可以从两方面衡量:特征的数目n和样本 的数目P, n和P可能很大，而n的庞大常会引起维数灾难 ((Curse of Dimensionality)等问题。特征选择是常用的数据降 维方法之一。特征选择是指从原始特征集中选择使某种评 估标准最优的特征子集。
最早的特征选择研究是上世纪60年代初开始的，当时的研 究主要是集中于统计学及信号处理问题，而且一般涉及到的特 征较少，并且通常假定特征之间是独立的。上个世纪90年代以 来涌现的大规模机器学习问题，使得已有的算法受到严峻的挑 战，迫切需要适应大规模数据的准确性和运行效率等综合性能 较好的特征选择算法。特征选择已引起机器学习等领域学者广 泛的研究兴趣。
( 2) 距离 (Distance Metrics ) 运用距离度量进行特征选择是基于这样的假设：好的特征 子集应该使得属于同一类的样本距离尽可能小，属于不同类的 样本之间的距离尽可能远。 (3) 信息度量 信息度量通常采用信息增益或互信息衡量。信息增益定义 为先验不确定性与期房的后验不确定性之间的差异，它能有效 地选出关键特征，剔除无关特征。互信息描述两个随机变量之 间相互依存关系的强弱
(4)一致性( Consistency ) 若样本1与样本2属于不同的分类，但在特征A、 B上的取值 完全一样，那么特征子集{A，B}不应该选作最终的特征集。 (5)分类器错误率 (Classifier error rate ) 使用特定的分类器，用给定的特征子集对样本集进行分类， 用分类的精度来衡量特征子集的好坏
4、增L去R选择算法 该算法有两种形式: <1> 算法从空集开始，每轮先加入L个特征，然后从中去除R个特 征，使得评价函数值最优。( L> R ) <2> 算法从全集开始，每轮先去除R个特征，然后加入L个特征， 使得评价函数值最优。( L< R ) 5、序列浮动选择 算法描述：序列浮动选择由增L去R选择算法发展而来，该 算法与增L去R选择算法的不同之处在于：序列浮动选择的L与R 不是固定的，而是“浮动”的，也就是会变化的。 6、决策树 算法描述：在训练样本集上运行C4.5或其他决策树生成算法， 待决策树充分生长后，再在树上运行剪枝算法。则最终决策树 各分支处的特征就是选出来的特征子集了。
在机器学习的实际应用中，特征数量往往较多，其中可能 存在不相关的特征，特征之间也可能存在相互依赖，容易导致 如下的后果： 1)、特征个数越多，分析特征、训练模型所需的时间就越长。 2)、特征个数越多，容易引起“维度灾难”，模型也会越复杂， 其推广能力会下降。 特征选择能剔除不相关或冗余的特征，从而达到减少特征 个数，提高模型精确度，减少运行时间的目的。另一方面，选 取出真正相关的特征简化了模型，使研究人员易于理解数据产 生的过程。
思路：对每一维的特征打分，即给每一维的特征赋予权重，这样的 权重就代表该维特征的重要性，然后依据权重排序。
Filter
主 要 方 法
相关系数 卡方检验
信息增益，互信息
思路：将子集的选择看作是一个搜索寻优的问题，生成不同的 组合，对组合进行评价，再与其他的组合进行比较。这 样 就将子集的选择看作是一个优化问题。
4.1.3随机搜索
随机产生序列选择算法(RGSS, Random Generation plus Sequential Selection) 模拟退火算法( SA, Simulated Annealing ) 遗传算法( GA, Genetic Algorithms )
4.2评价函数
评价函数的作用是评价产生过程所提供的特征子集的好坏。 评价函数根据其工作原理，主要分为筛选器(Filter)、封装器 ( Wrapper )两大类。 筛选器通过分析特征子集内部的特点来衡量其好坏。 封装器实质上是一个分类器，封装器用选取的特征子集对 样本集进行分类，分类的精度作为衡量特征子集好坏的标准。 筛选器和封装器是两种互补的模式，两者可以结合。混合 特征选择过程一般可以由两个阶段组成，首先使用筛选器初步 剔除大部分无关或噪声特征，只保留少量特征。第二阶段将剩 余的特征连同样本数据作为输入参数传递给封装器，以进一步 优化选择重要的特征。
5.发展与展望
特征选择得到广泛研究并应用于Web文档处理(文本分类、 文本检索、文本恢复）基因分析、药物诊断等领域。 现在的社会是信息爆炸的社会，越来越多、形式多样的数 据出现在我们面前，比如基因数据、数据流，如何设计出更好 的特征选择算法来满足社会的需求，是一个长期的任务，特征 选择算法的研究在未来的一段时间仍将是机器学习等领域的研 究热点问题之一。目前研究热点及趋势主要集中于以下方面: 1)特征与样本选择的组合研究。不同的样本集合区域，也 许应该选择不同的特征选择算法。 2) 特征及其与目标(分类、回归、聚类等)的相关性受到越 来越多的重视。 3)将过滤和封装方法结合，根据特定的环境选出所需要的 度量准则和分类器。 4)采用启发式搜索策略的封装方法进行特征选择。
4.1产生过程
产生过程是搜索特征子集的过程。搜索的算法分为完全搜 索(Complete)，启发式搜索(Heuristic)，随机搜索(Random) 3大类。
4.1.1 完全搜索
完全搜索分为穷举搜索(Exhaustive)与非穷举搜索(NonExhaustive)两类。算法具体包括： 广度优先搜索( Breadth First Search ) 分支限界搜索( Branch and Bound ) 定向搜索 (Beam Search ) 最优优先搜索 ( Best First Search )
Wrapper
生成特征子集wenku.baidu.com
完全搜索 启发式搜索
随机搜索
思路：在模型既定的情况下学习出对提高模型准确性最好的 属性，即在确定模型的过程中，挑选出那些对模型由 重要意义的属性。
Embedded
主 要 方 法 正则化
决策树
4. 特征选择的一般过程
特征选择的一般过程可用下图表示。首先从特征全集中产 生出一个特征子集，然后用评价函数对该特征子集进行评价， 评价的结果与停止准则进行比较，若评价结果比停止准则好就 停止，否则就继续产生下一组特征子集，继续进行特征选择。 选出来的特征子集一般还要验证其有效性。
4.2.1常见评价函数
(1) 相关性( Correlation) 运用相关性来度量特征子集的好坏是基于这样一个假设： 好的特征子集所包含的特征应该是与分类的相关度较高（相关 度高），而特征之间相关度较低的（亢余度低）。可以使用线 性相关系数(correlation coefficient) 来衡量向量之间线性相关度。
2. 特征选择的定义
特征选择 ( Feature Selection )也称特征子集选择( Feature Subset Selection , FSS ) ，或属性选择( Attribute Selection ) ，是指 从全部特征中选取一个特征子集，使构造出来的模型更好。
3. 特征选择的目的和方法
4.1.2 启发式搜索
1、序列前向选择 算法描述：特征子集X从空集开始，每次选择一个特征x加入 特征子集X，使得特征函数J( X)最优 2、序列后向选择 算法描述：从特征全集O开始，每次从特征集O中剔除一个 特征x，使得剔除特征x后评价函数值达到最优。 3、双向搜索 算法描述：使用序列前向选择(SFS)从空集开始，同时使用 序列后向选择(SBS)从全集开始搜索，当两者搜索到一个相同的 特征子集C时停止搜索。