09特征选择与提取

*第九章特征提取与选择尺寸重量颜色* 对分类器设计来说，使用什么样的特征描述事物，也就是说使用什么样的特征空间是个很重要的问题。 这个问题称之为描述量的选择问题，意思是指保留哪些描述量，删除哪些描述量的问题。 本章节研究对特征空间进行改造,目的在于提高其某方面的性能，因此又称特征的优化问题。基本概念***对特征空间的改造、优化,主要的目的是降维，即把维数高的特征空间改成维数低的特征空间，降维主要有两种途径。 一种是筛选掉一些次要的特征，问题在于如何确定特征的重要性，以及如何筛选。 另一种方法是使用变换的手段，限定在线性变换的方法上，通过变换来实现降维。*本章节重点 弄清对特征空间进行优化的含义。 对特征空间进行优化的两种基本方法——特征提取与特征选择。 对特征空间进行优化的一些常用判据。 常用的特征选择方法。*对特征空间进行优化的概念和意义、目的对特征空间进行优化的两种基本方法特征选择与特征的组合优化特征的组合优化需要评价标准(设计优化使用判据)基于距离度量的判据基于概率分布的判据*特征组合优化特征选取基于距离度量判据的典型优化方法基于K-L变换的特征空间优化方法最优搜索方法次优搜索方法*8.1基本概念□特征的选择与提取：■ 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 各种特征的有效性并选出最有代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 性的特征是模式识别系统设计的关键步骤。■降低特征维数在很多情况下是有效设计分类器的重要课题。数据获取预处理特征提取与选择分类决策分类器设计信号空间特征空间*三大类特征□三大类特征：物理、结构和数字的■物理和结构特征：易于为人的直觉感知，但有时难于定量描述，因而不易用于机器判别。■数字特征：易于用机器定量描述和判别，如基于统计的特征。 物理量的获取与转换 描述事物方法的选择与设计* 对初始的特征空间进行优化是为了降维。即初始的特征空间维数较高。能否改成一个维数较低的空间，称为优化。特征空间的优化*特征优化两种方法区别 特征提取(特征组合优化)：通过映射(或变换)的方法把高维的特征向量变换为低维的特征向量。 特征选择：从一组特征中挑选出一些最有效的特征以达到降低特征空间维数的目的的过程。筛选*8.2类别可分性判据 特征选择或特征提取任务是从n个特征中求出对分类最有效的m个特征(m＜n)。 对于特征选择来讲，从n个特征中选择出m个特征，有种组合方式。 哪一种特征组的分类效果最好？ 这需要有一个比较标准，即需要一个定量的准则来衡量选择结果的好坏。* 对于特征提取来讲，把n维特征向量变换成m维特征向量，有各种变换 哪一种变换得到的m维特征向量对分类最有效? 需要用一个准则来衡量。*很自然地会想到，既然模式识别的目的是设计分类器，那么用分类器的错误概率作为准则就行了，也就是说，使分类器错误概率最小的那组特征，就应当是一组最有效的特征。从理论上讲，这是完全正确的，但在实际使用中却有很大困难。从第二章中错误概率的计算公式就会发现，即使在类条件概率密度已知的情况下错误概率的计算就很复杂，何况实际问题中概率分布常常不知道，这使得直接用错误概率作为准则来评价特征的有效性比较困难。*找出一些更实用的准则来衡量各类间的可分性，并希望可分性准则满足下列几条要求：8.2类别可分性判据（1）与错误概率有单调关系（2）当特征独立时有可加性（3）度量特性（4）单调性*设计分类器错误概率最小新的标准目的理论最理想×*8.2.1基于距离的可分性判据 基于距离的可分性判据的实质是Fisher准则的延伸，即综合考虑不同类样本的类内聚集程度与类间的离散程度这两个因素。 判据的优化体现出降维特征空间较好地体现类内密集。一些不能体现类间分隔开的特征很可能被排除掉了。 掌握利用离散矩阵来描述数据离散程度的方法。具体的准则学习J2准则。** 基于距离度量是常用来进行分类的重要依据，因为一般情况下同类物体在特征空间呈聚类状态，即从总体上说同类物体内各样本由于具有共性，因此类内样本间距离应比跨类样本间距离小。 Fisher准则是以使类间距离尽可能大同时又保持类内距离较小这一种原理为基础的。同样在特征选择与特征提取中也使用类似的原理，这一类被称为基于距离的可分性判据。 为了度量类内、类间的距离，可用其他方法描述方法，即描述样本的离散程度的方法。8.2.1基于距离的可分性判据*各类样本之间的距离越大，则类别可分性越大。因此，可以用各类样本之间的距离的平均值作为可分性准则8.2.1基于距离的可分性判据均值向量总平均向量*基于距离的准则概念直观，计算方便，但与错误率没有直接联系样本类间离散度矩阵样本类内离散度矩阵类间可分离性判据8.2.1基于距离的可分性判据*各类之间的平均平方距离也可表示为：8.2.1基于距离的可分性判据*■基于概率的可分性判据：用概率密度函数间的距离（交叠程度）来度量■概率距离度量8.2.2基于概率分布的可分性判据Bhattacharyya距离：Chernoff界限：(1).(2).完全不交叠时，最大(3).时，8.2.2基于概率分布的可分性判据■散度：区分i，j两类总的平均信息*对wi类的平均可分信息对wj类的平均可分信息散度JD为两类平均可分信息之和wi，wj对数似然比*■正态分布条件下的散度判据可以用分布参数表示，特别是■一维正态分布：Mahalanobis距离8.2.2基于概率分布的可分性判据*最佳分类器由后验概率确定，所以可由特征的后验概率分布来衡量它对分类的有效性。如果对某些特征，各类后验概率是相等的，即错误率为：8.2.3基于熵函数的可分性判据*后验概率越集中，错误概率就越小。后验概率分布越平缓(接近均匀分布)，则分类错误概率就越大。为了衡量后验概率分布的集中程度，需要规定一个定量准则，借助于信息论中关于熵的概念---对不确定性的信息的度量。8.2.3基于熵函数的可分性判据*从特征抽取的角度看，显然用具有最小不确定性的那些特征进行分类是有利的。为了对所提取的特征进行评价，计算空间每一点的熵函数。在熵函数取值较大的那一部分空间，不同类的样本必然在较大的程度上互相重叠。因此熵函数的期望值可以表征类别的分离程度，它可用来作为所提取特征的分类性能的准则函数。8.2.3基于熵函数的可分性判据*■熵函数：衡量后验概率分布的集中程度■Shannon熵：■平方熵：■熵函数期望表征类别的分离程度：8.2.3基于熵函数的可分性判据*8.2.4类别可分离性判据的直接应用举例□图像分割：Otsu灰度图像阈值算法(Otsuthresholding)□图像有L阶灰度，ni是灰度为i的像素数，图像总像素数N=n1+n2+…+nL■灰度为i的像素概率：pi=ni/N■类间方差： 其中8.3特征提取 要在低维空间中更好的分类，变换的有效性最好用错误概率来衡量，然而其计算复杂。上节课所讨论的距离度量，概率可分性度量及熵度量，其概念在直观上不难理解，然而大多数情况下与错误概率无直接关系，则以这些度量为基础所设计的分类器的错误概率未必最小。 从计算观点看，用其中的一些判据进行特征提取往往是唯一可行的方法。*8.3.1按欧式距离度量的特征提取方法基于距离可分性判据的特征优化过程是通过一个线性变换实现的。设在原特征空间一个样本向量表示成Y(D维)，在优化特征空间中，样本向量表示成X(d维)。X与Y之间的关系是： 其中W是一个D×d维矩阵，现在的问题是要利用判据找出一种线性变换，利用这种变换，实现这种判据的极值化。*8.3.1按欧式距离度量的特征提取方法两个特征向量间的距离为其相似度的很好度量*用表示第wi类的第k个样本与第wj类第l个样本间的距离，选特征x*,使c个类别各样本间的平均距离J(x)为最大：ni表示S中wi类的训练样本数，Pi是第i类的先验概率，若其未知，也可用训练样本数进行估计：各种距离度量计算*8.3.1按欧式距离度量的特征提取方法（1）s阶Minkowski度量当s=1时（2）欧式距离当s=2时（3）Chebychev距离（4）平方距离（5）非线性度量当只有一个下标时，此下标表示样本号，有两个下标时，第一个为样本号，第二个为表示该样本的特征序号。8.3.1按欧式距离度量的特征提取方法欧式距离较常用，用期望值代替样本均值，可得到一种距离度量：*Sb为类间离散度矩阵，Sw为类内离散度矩阵。希望变换后的Sb尽量大，w尽量小，可提出以下判据：8.3.1按欧式距离度量的特征提取方法 离散度矩阵：度量了一个聚类的散布程度设a是d维空间中所选取的中心点，从聚类的N个点中取出d个点，以a为引点，做超平行四边形。对所有N中的d个点求出相应的个超平行四边形的体积平方和对N个点的均值，就是该聚类对于中心点a的离散度。假使以均值点作为引点，则离散度*C是聚类的协方差矩阵8.3.1按欧式距离度量的特征提取方法对特征空间实行一个d×d矩阵的非奇异线性变换，J2，J3与J5保持不变，J4与坐标系有关*以J2为例：例如若对原特征空间实行一d×d线性变换A，J2(d)不变。8.3.1按欧式距离度量的特征提取方法 用以上判据进行特征提取的步骤：*假设有D个原始特征：通过线性映射压缩为d个特征：变换关系为：W为D×d矩阵令Sw,Sb为y的离散度矩阵，为映射后x的离散矩阵：变换后的J2为：将此式对W的各分量求偏导并令其为0可以确定一个W8.3.1按欧式距离度量的特征提取方法对*来说使其判据达最大的变换W如下：设矩阵的本征值为，按大小顺序排列选前d个本征值对应的本征向量作为W此时J2（w）为：8.3.1按欧式距离度量的特征提取方法*例：给定先验概率相等的两类，其均值向量分别为协方差矩阵为：求用判据的最优特征提取。8.3.1按欧式距离度量的特征提取方法 解：先求*再求此矩阵的本征阵。的秩是，因此只有一个8.3.2按概率距离判据的特征提取方法 这一节只是在正态分布条件下的一种特殊情况进行分析。 在讨论如何按概率距离判据进行特征提取时，与前面讨论欧氏距离为基础的判据的基本方法是一样的。 设原始特征为y，而经变换后的特征为x，两者之间有映射关系： 利用这种关系，可以将有关判据的表达式表示成映射关系的函数，例如，然后求表达式对 各分量的偏导数，并令其为零，得到所需的方程式组，并用相应方法求解。*8.3.2按概率距离判据的特征提取方法 的情况：令为的本征值矩阵， *W为单个本征向量： 的情况：为的本征值。8.3.2按概率距离判据的特征提取方法 一般情况：*为避免用数值优化方法求解，分别考虑两类均值和协方差矩阵有差别时的分类作用■先假设均值向量相等，得到候选坐标系，然后用包含在类均值向量中的信息选d个坐标轴；■假设类均值向量相等，选d-1个坐标轴，再加1个考虑类均值向量判别信息的坐标轴。8.3.4多类情况 最优特征提取器W应使广义类别可分判据*最大求最优特征变换的解析解不大可能。可行方法是先求取一个候选坐标轴集合{v}。它可以包括：（1）（2）的所有本征向量（3）的本征向量系统。假设候选坐标轴的总数是D.用搜索算法从D个坐标轴中选出使J(W)达最大的d个坐标轴8.3.5基于判别熵最小化的特征提取 Shannon熵* 相对熵相对熵越小，两类概率分布的差别就越大；当两类概率分布完全相同时，相对熵达最大值（等于0）定义判别熵W(p,q)来表征两类分布p(xi)和q(xi)的差别大小 在多类情况下，可以用来表示各类分布之间的分离程度。 对于特征提取来说，在给定维数d条件下，应求得这样d个特征，使上述判别上最小。 为计算简单，可用下式来代替W(p,q),而不影响选取d个最优特征的结果。*8.4特征选择 特征选择在概念上十分简单，即对原有特征进行删选优化. 一般人常想，只要逐个分析每个特征，判断它对分类的价值，然后根据其价值删去或保留，这是人们常采用的方法，但是这种方法并不能保证特征空间的最优组合优化，因此本节仅讨论一些原理上更好的方法，由于方法本身比较繁琐，本节不作为学习重点。**特征选择:从原始特征中挑选出一些最有代表性、分类性能最好的特征进行分类。要解决两个问题：选择的标准，如可分离性判据快速寻优算法从个特征中选取个，共种组合。若不限定特征选择个数，则共种组合－典型的组合优化问题8.4特征的选择8.4特征的选择特征选择的方法：是否直接考虑分类器性能 Filter方法：根据独立于分类器的指标J来评价所选择的特征子集S，在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。不考虑所使用的学习算法。 Wrapper方法：将特征选择和分类器结合在一起，在分类过程中表现优异的的特征子集会被选中。选择特征的顺序： 自下而上：特征数从零逐步增加到d。 自上而下：特征数从D开始逐步减少到d。**经典特征选择算法许多特征选择算法力求解决搜索问题，经典算法有：􀂄最优搜索：分支定界法 次优搜索： 单独最优特征组合法： 顺序前进法 顺序后退法 其他组合优化方法： 模拟退火法 Tabu搜索法 遗传算法*单独最优特征组合计算各特征单独使用时的可分性判据J并加以排队，取前d个作为选择结果组合起来不一定是最优结果当可分性判据对各特征具有(广义)可加性，该方法可以选出一组最优的特征来，例：各类具有正态分布各特征统计独立可分性判据基于Mahalanobis距离*顺序前进法（SFS）:最简单的自下而上搜索算法自下而上搜索方法。每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的可分性或分类识别率为最大，直至特征数增加到d为止。该方法考虑了所选特征与已入选特征之间的相关性。比单独最优特征组合效果好。 缺点：一旦某特征已入选，即使由于后加入的特征使它变为多余也无法再把它剔除。 推广：广义顺序前进法（GSFS），每次从未入选的特征中选择出r个特征，使得这r个特征加入后J值达最大。 SFS每次只增加一个特征，它未考虑未入选特征之间的统计相关性；GSFS法可以克服这个缺点，计算量增大，它比SFS更可靠，但仍然无法拿出已入选的特征。**顺序后退法（SBS）：自上而下的方法该方法根据特征子集的分类表现来选择特征搜索特征子集：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的可分性或分类识别率。和顺序前进法比较，顺序后退法有两个特点：计算过程中可以估计每次去掉一个特征所造可分性的降低；由于顺序后退法的计算是在高维空间进行的，所以计算量比顺序前进法要大 推广：广义顺序后退法增l减r法（l-r） 避免上述方法的一旦被选入（或剔除）就不能再剔除（或选入）的缺点，可在选择过程中加入局部回溯过程。 在第k步可先用SFS法一个个加入特征到k+l个，然后再用SBS法一个个剔除r个特征。* 步骤：假设已经选了k个特征，得出特征组Xk1.用SFS法在未入选特征组XD-Xk中逐个选入特征l个，形成新特征组Xk+l，置k=k+l,Xk=Xk+l2.用SBS法从Xk中逐个剔除r个最差的特征，形成新特征组Xk-r，置k=k-r,若k=d则终止算法，否则，置Xk=Xk-r,转向第一步。* 说明：当l>r时，l-r法是自下而上的算法，先执行第一步，然后执行第二步，起始时应置k=0,X0从空开始。 当l<r时，l-r法是自上而下的算法，先执行第二步，然后执行第一步，起始时应置k=D,X0从全部特征开始。 推广：广义l-r法**遗传算法从生物进化论得到启迪。遗传，变异，自然选择。基于该思想发展了遗传优化算法。基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个D位的0/1构成的串表示一种特征组合。群体：若干个个体的集合，即问题的一些解的集合。交叉：由当前两个个体的链码交叉产生新一代的两个个体。变异：由一个链码随机选取某基因使其翻转。*遗传算法适应度函数f(x)：每个个体xi的适应度f(xi)越大，个体xi越好。新一代群体对环境的平均适应度比父代高。遗传算法的基本框架： Step1:令进化代数t=0。 Step2:给出初始化群体P(t)，令xg为任一个体。 Step3:对P(t)中每个个体估值，并将群体中最优解x’与xg比较，如果x’的性能优于xg，则xg=x’ Step4:如果终止条件满足，则算法结束，xg为算法的结果。否则继续。 Step5:从P(t)中选择个体并进行交叉和变异操作，得到新一代群体P(t+1)。令t=t+1,转到Step3。*