第八章-特征选择与提取PPT课件.pptx

1、,特征选择与特征提取,1,问题,1、为什么要做特征选择和特征提取？ 2、特征选择和特征提取的区别在哪儿？ 3、怎么做特征选择和特征提取？,2,目录,背景 特征选择简介 特征子集搜索与子集评估 特征提取 特征选择与特征提取讨论 总结,3,背景,好瓜还是坏瓜?,分类任务,原始特征: 西瓜颜色, 根蒂, 敲声, 纹理, 触感,以往研究，是特征固定，研究重点是分类器,4,背景,举例: 对于一个有经验的瓜农，怎么判断西瓜是好还是坏？,5, 相比 ，部分特征冗余，需要选择特征,背景,特征: 根蒂，敲声，纹理,注意：原始特征是已知的,6,特征: 西瓜颜色, 根蒂, 敲声,纹理, 触感,除此之外，还有一种处理

2、特征的方式，叫特征提取,从原始特征中选择出部分和任务相关的特征，是特征选择,特征选择： 从原始特征中选择出和任务相关的特征 特征提取： 将原始特征通过线性或者非线性组合的方式转化为新的特征表示 For example:= =1 作用: 降维 特征优化 提升分类性能,7,背景,目录,背景 特征选择简介 特征子集搜索与子集评估 特征提取 特征选择与特征提取讨论 总结,8,特征选择,特征：对象所具有的属性 例如: 西瓜颜色, 根蒂, 敲声, 纹理, 触感,根蒂: 蜷缩 敲声: 清脆 纹理: 清晰,恩，这是一个好瓜,9,有经验瓜农判断：,特征选择,相关特征: 和任务相关的属性，且属性之间互相不相关,比

3、如：根蒂、敲声、纹理,无关特征: 和任务不相关的属性,比如：颜色、触感,特征选择：从所有的已知属性中选择出和任务相关，且相互之间不相关的属性,10,好而不同,特征选择,11,一般来说，特征选择步骤如下，主要包括子集搜索和子集评估,目录,背景 特征选择简介 特征子集搜索与子集评估 特征提取 特征选择与特征提取讨论 总结,12,子集搜索,1) 前向搜索: 依次在候选集合中增加相关特征,2) 后向搜索: 在候选集合中，依次去除不相关特征,Question: How to evaluate the searched feature?, 2 2 , 4 .,Optimal feature:,Optima

4、l feature:,13,These strategies are greedy, only consider optimization of this round 这些方法是贪心的策略，因为是在上一轮的基础上考虑本轮最优，所以不一定得到最优特征组合,其他子集搜索方法：,子集评估,类可区分性判据(Separation Criterion) 用于评估特征子集的类别区分性的能力,基于距离的类可区分性判据 Distance based separation criterion 基于概率分布的类可区分性判据 Probability distributions based separation cri

5、terion 基于熵的类可区分性判据 Entropy based separation criterion,14,搜索一个特征子集，我们希望 : 样本类内的距离尽可能小 样本类间距离尽可能大,基于距离的判据,15,Far away,Far away,Class1,Class2,基于距离的判据,样本均值向量: 协方差矩阵: 类内散度矩阵: 类间散度矩阵:,类可区分性判据:, ( ) ( ),16,注：协方差矩阵的迹等同于方差,基于概率密度的判据,17,Class1,Class2,类条件概率密度曲线,重叠,分离,x,x, 1, 2,根据搜索到的特征子集，分析一下两个类的类条件概率密度曲线分布情况,

6、类条件概率密度,Class1,Class2, 1, 2,类条件概率密度,基于概率密度的判据,= 1 , 2 , 1 , 2 ,18,重叠度 J：两个概率密度分布曲线的重叠程度,类条件概率,先验概率,J 满足的条件: 0 If 1 =0 ,19,满足以上条件的任何函数都可以作为基于概率密度的类可区分性判据的距离度量! 概率密度距离的常用函数: 巴氏距离（Bhattacharyya distance） Chernoff 界限（Chernoff bound ） 散度（Divergence） 参考书: 边肇祺模式识别第8章,基于概率密度的判据,基于概率密度的判据,巴氏距离 (Bhattacharyya

7、 distance) J= 1 2 1 2 对于高斯分布下： 1 = 1 (2) 2 |1| 1 2 exp 1 2 ( 1 ) 1 1 ( 1 ) 2 = 1 (2) 2 |2| 1 2 exp 1 2 ( 2 ) 2 1 ( 2 ),20,基于概率密度的判据,巴氏距离 (Bhattacharyya distance) = 1 8 1 2 1 + 2 2 1 ( 1 2 ) + 1 2 | 1 2 1 + 2 | | 1 | 2 | 1 2,21,22,熵（Entropy）:,基于熵的判据,熵值越大，说明样本的类别不确定性越大,23,贝叶斯分类器中，分类的结果由后验概率确定 对于一个样本，如

8、果所有类的后验概率是相同的，则分类结果不可知 例如: = 1 , 分类错误率: =1 1 = 1 =1 , =0, 分类错误率: =0,基于熵的判据,熵值可以度量后验概率的分布!,24,平方熵（Square Entropy）:,基于熵的判据, 2 = 1 , 2 , =21 =1 2 ( |) ,后验概率分散性越大，熵值越大，分类错误率越高,香农熵（Shannon Entropy）:, = =1 ( |) log 2 ( |),特征选择,过滤式 (Filter) 包裹式（Wrapper） 嵌入式（Embedding）,特征选择策略: 特征子集搜索和子集评估组合起来的过程,25,特征选择,过滤式

9、 ：特征选择发生在训练过程之前 （无训练过程） 代表性方法: Relief 包裹式：直接将分类器的性能作为特征选择中的子集评估方法（无训练过程） 代表性方法: LVW（拉斯维加斯算法） 嵌入式：特征选择和学习器训练同时嵌入到一个优化过程中，特征选择在学习器训练过程中完成（有训练过程）,L1 norm,易获得稀疏解，是一种嵌入式特征选择方法,26,过滤式,过滤式 ：特征选择发生在训练过程之前,Relief (Relevant Features) Kira and Rendell, 1992 给定相关统计量，度量特征的重要性 设置一个阈值t, 如果某一个特征的相关统计量大于阈值t, 那么就将其加入

10、特征子集 特征子集的重要性等于特征子集相关统计量的和,27,过滤式,特征j 的相关统计量：,猜中近邻（near-hit instance） = similar class,猜错近邻（near-miss instance ）= different class,instances belongs to similar class should stay closer together than those in a different class,越大，说明特征j 的类别区分能力越强,28,Relief-FKononenko, 1994,过滤式,Relief的扩展，处理多分类问题,数据集D中第L类

11、的比例,29,包裹式,包裹式：直接将分类器的性能作为特征选择中的子集评估方法 LVW(Las Vegas Wrapper) 是一种典型的包裹式算法,1）在候选特征集中自由选择特征子集 2）在特征子集表示的数据集上，运行学习算法 3）用分类的错误率来评估特征子集的好坏,30,包裹式,连续T次不更新，就停止,31,循环的条件,终止条件,分类错误率比上一轮减小,分类错误率跟上一轮相等，但特征维数减少,包裹式,LVW 可以减少特征的维数，并且提高分类的准确率 由于每次都要运行分类器，复杂性高 算法运行速度慢,32,特点：,嵌入式,嵌入式：特征选择和学习器训练同时嵌入到一个优化过程中，特征选择在学习器训

12、练过程中完成,目标函数,L2 norm,L1 norm,易获得稀疏解，是一种嵌入式特征选择方法,L1范数比L2范数更易获得稀疏解,33,特征选择+特征提取,并行的思路,嵌入式,34,总结,背景 特征子集搜索方法 前向搜索，后向搜索，双向搜索 特征子集评估方法 基于距离的判据，基于概率密度的判据，基于熵的判据 特征选择的策略 过滤式，包裹式，嵌入式,35,目录,背景 特征选择介绍 特征子集搜索与子集评估 特征提取 特征选择与特征提取讨论 总结,36,特征提取,特征提取不同于特征选择 特征提取是将原始特征通过组合转换到新的特征空间 特征提取是特征工程的一种,37,特征提取的方法,线性方法,Prin

13、cipal Component Analysis (PCA)Pearson , 1901 Linear Discriminant Analysis (LDA) Ronald Fisher , 1936 Belhumeur, 1996,非线性方法,Multidimensional Scaling (MDS) Torgerson, W.S. et al. ,1958 Kernel principal component analysis (KPCA) Scholkopf et al., 1998 Principal Curves Hastie, 1989 Self-Organizing Featu

14、re Map (SOM) Kohonen et al., 1995 Generative topographic map (GTM) Bishop et al., 1998 Manifold Learning：Isomap,LLE,LE. .,38,39,PCA,PCA:(主成分分析法),=11+22,x1,x2,Z 是1维的数值 W 是投影向量 x=(x1;x2) 是一个向量 w 未知 Question：如何求得最好的W,= ,线性组合就相当于几何中的投影,PCA,40, =(1;2;3;.;),= W T ,Z= 1;2; , ,=(1；2；3；. ；d),Question: W和Z如何计

15、算呢?,Where， Z= 1;2; 是主成分, zi 是个标量 wj=(wj1,wj2,.,wjn) 是个向量 W 是d*n的矩阵,注： 每个主成分都是原始特征的线性组合 主成分的数量小于原始特征维数 主成分可以保留原始特征的最大信息量 主成分之间互相不相关,41,目标函数：,目标： 最大可分性,特征值分解,PCA,求解： 特征值分解,=(1；2；3；. ；d),前d个最大的特征值对应的特征向量组成W,方差最大化,拉格朗日乘子法,min +( ),(可理解成向量)对应的是信息量的大小，w对应的是投影方向,PCA,Algorithm,Let be the mean vector (taking

16、 the mean of all rows),Adjust the original data by the mean X = X ,Compute the covariance matrix XXT of adjusted X,Find the eigenvectors and eigenvalues of XXT,Get a matrix W consisted of d ordered eigenvectors,= T is the result that want to get,42,去中心化,中心化,PCA,以2维的数据集为例：,43,PCA,PCA保证新空间中特征之间不相关的情况下

17、，使变换后的特征维数更少，实现降维和特征提取.(不包含类别区分性) 局限： 无监督 被忽略掉的成分可能也包含一些相对独立的信息,44,优点:,LDA（线性判别分析） LDA是Fisher线性判别分析的一般形式，通过特征的线性组合实现两类或者多类数据的分离。LDA在统计、模式识别和机器学习中具有广泛应用,线性判别分析,45,46,线性判别分析,2维映射到1维,2维映射到1维,线性判别分析,数据集: ：第一类数据样本集 ：第一类数据样本个数 ：第二类数据样本集 ：第二类数据样本个数,47,N 2,N 1,LDA 就是FLD (Fisher 线性判别),如果特征是从n维映射到1维:,以二分类为例：,

18、48,线性判别分析,均值向量: 协方差矩阵: 类内散度矩阵: 类间散度矩阵:,原始特征空间（n维特征）,线性判别分析,49,新的特征空间（1维）,均值： = 1 , (=1,2) 方差： S = ( i ) 2 , =1,2 类内散度： S w = S 1 + S 2 类间散度： S b = ( 1 2 ) 2,目标函数: max = ( 1 2 ) 2 S 1 + S 2,其中： i = 1 = 1 = 1 = ( 1 2 ) 2 = ( 1 2 ) 2 = 1 2 1 2 = ,Linear Discriminant Analysis,广义瑞利商:,类间散度,类内散度,50,W如何求解?,

19、S = ( ) 2 = ( ) 2 = = S 1 + S 2 = ( 1 + 2 )= ,线性判别分析,拉格朗日乘子法,51,min +( ),求导 (Derivative) 使导数为0, = , 1 = ,特征值分解（eigenvalue decomposition）, ,最大的特征值对应的特征向量就是 ,注: 1） 需要可逆 2）如果 不可逆, 那么先 PCA 再 LDA,不可逆出现在维数高，样本量少的情况，这时可先做PCA，然后LDA,如果特征从n维映射到d维: 原始特征: n 维 新的维数: 1(维度上限) 映射的维数和类别数C有关,52,线性判别分析,注: 如果特征由n维映射到1维

20、，不能满足多分类任务 那么需要映射到d维,53,线性判别分析,= 1 , 2 ,., ,= 1 , 2 ,., ,= , 是n维向量, 是 d*n 的矩阵, 是d维向量,均值向量: 协方差矩阵: 类内散度矩阵: 类间散度矩阵:,线性判别分析,新空间（d维）：,54,= = ,目标函数:,求解: 1 = ,= 1 , 2 ,., ,注: 不是正交的,为什么维度上限是C-1？,55,线性判别分析,存在这种情况,( 1 )min 1 ,( ), = =1 ( ) =1 )( ) = =1 / )( ) = =1 =,=1 =0, 1, 1 1,特点： 监督的方法，可提取出具有判别性的特征 LDA最多

21、只能将特征降低到C-1维 LDA方法需要数据服从高斯分布 容易出现过拟合,线性判别分析,56,57,Kernel-PCA,低维空间中线性不可分,高维空间中线性可分,Kernel-PCA,本真二维结构,PCA降维后的数据分布,三维空间中的数据分布,58,59,Kernel-PCA,PCA 目标函数：,Kernel PCA 目标函数：,max . =,max (,) . =,低维空间上的Kernel变换代替高维空间上的内积,Kernel trick：,Kernel-PCA,对于一个新样本x, 映射后的第j维表示如下 ,特征值分解,此时，W没法求解。但是可以证明，W是新的特征空间中样本的线性组合,

22、通过求得的a 和核函数求解,推导：,60,Kernel-PCA,常用的核函数 线性核 多项式核 高斯核 指数核 .,61,Kernel-PCA,Kernel PCA是PCA的扩展，可有效解决低维空间中数据无法准确线性映射的问题 核技巧可以很巧妙地将低维空间上的PCA扩展到高维空间上，实现数据的非线性映射，不会增加计算复杂度 没有固定的选择核函数的方法,62,Isomap,Isomap （ 等距离映射） 目标是通过保持数据点对之间的测地距离，来保持数据的全局结构,测地距离,Joshua B. Tenenbaum, Vin de Silva, John C. Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 2000,63,欧氏距离,64,Isomap,65,最短路径近似原始空间测地距离,映射空间的欧氏距离,测地距离,Isomap,优点： 对于流形分布的数据，在低维空间中保留了数据 之间的本质距离，全局结构得以保持 缺点： 降维过程没有考虑类别区分性保持 现实的测地距离较难计算,66,Isomap,LLE,LLE (局部线性嵌入) Roweis et al., 2000,Sam T. Roweis, Lawrence K.Saul. Nonlonea