1、第七章 特征选择王文伟 Wang Wenwei,Dr.-Ing.Tel:18971562600Email:Web:http:/ 特征选择2Table of Contents7.1 引言7.2 特征的评价准则7.3 特征选择的最优算法7.4 特征选择的次优算法7.5 特征选择的遗传算法7.6 以分类性能为准则的特征选择7.7 讨论 电子信息学院第七章 特征选择37.1 基本概念u特征的选择与提取是模式识别中重要而困难的一个环节：分析各种特征的有效性并选出最具可分性的若干特征是模式识别系统设计的关键步骤。降低特征维数在很多情况下是有效设计分类器的重要课题。u讨论的重点是从一组给定的特征中选择一部分
2、特征进行分类。引言数据获取预处理特征提取与选择分类决策分类器设计信号空间特征空间x xa第七章 特征选择47.1.1 三大类特征u三大类特征：物理、结构和数学特征物理和结构特征：易于为人的直觉感知，但有时难于定量描述，因而不易用于机器判别。数学特征：易于用机器定量描述和判别，如基于统计的特征。u讨论的重点是根据学习样本来选择和提取数学特征，而物理和结构特征的测量与分析涉及研究对象本身的物理规律。引言第七章 特征选择5一个例子：鱼的分拣u两类鱼Sea bassSalmonuPattern Classification,2001引言第七章 特征选择6特征1：长度第七章 特征选择7特征2：亮度第七章
3、 特征选择8模式分类：线性、二次、最近邻分类器第七章 特征选择97.1.2 有关特征的基本概念u特征形成(acquisition)：信号获取或测量原始测量，其值域称为测量空间：对象表示x x=测量空间的点原始特征：通过基本计算产生基本特征y yu实例：数字图象中的各像素灰度值人体的各种生理指标u原始测量和原始特征分析：原始测量往往不能反映对象（类别）本质。高维原始特征不利于分类器设计：计算量大，数据冗余，样本分布十分稀疏。引言第七章 特征选择10特征的选择与提取u两类提取有效信息、压缩特征空间的方法：特征选择和特征提取u特征选择(selection)：从原始特征中挑选出一些最有代表性、分类性能
4、最好的特征。u特征提取(extraction)：用映射（或变换）的方法把高维原始特征变换为较少的新特征。u特征的选择与提取与具体问题有很大关系，目前没有理论能给出对任何问题都有效的特征选择与提取方法。引言第七章 特征选择11特征的选择与提取举例u细胞图像自动分类：原始测量：（正常与异常）细胞的数字图像原始特征（特征的形成，找到一组代表细胞性质的特征）：细胞面积，胞核面积，形状系数，光密度，核内纹理，核浆比 等等压缩特征：原始特征的维数仍很高，需压缩以便于分类 特征选择：挑选最有分类信息的特征，方法有：专家知识，数学方法 特征提取：数学变换傅立叶变换或小波变换用PCA方法作特征压缩引言第七章 特
5、征选择127.2 特征的评价准则u两大类评价特征优劣的方法：Wrapper方法：将特征选择和分类器性能结合在一起，在分类过程中表现优异的的特征子集会被选中为最优特征子集。Filter方法：不考虑所使用的分类器。根据独立于分类器的指标J来评价所选择的特征子集S，在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。u特征有效性=类别可分离性Jij(x)判据：根据Jij(x)衡量不同特征及其组合对分类是否有效的定量准则第七章 特征选择13实用类别可分离性判据u实际的类别可分离性判据应满足的条件：与错误率或其上下界有单调关系度量特性：当特征独立时有可加性：单调性：u常见类别可分离性判据：
6、基于类内类间距离基于概率分布基于熵函数0,if ;0,if ;ijijijjiJij Jij JJ121(,.,)()dijdijkkJx xxJx12121(,.,)(,.,)ijdijddJx xxJx xxx第七章 特征选择147.2.1 基于类内类间距离的可分性判据u类间可分性:=不同类任意两两样本间的平均距离()()111111()(,)2jinnccijdijklijklijJPPnn xxx(7-1)()()()()()()(,)()()ijijTijklklklxxxxxxsquared Euclidian()11iniikkinmx1ciiiPmm()111()(,)(,)i
7、ncidikiiikiJPnxxmm m(7-5)类内平均距离类间距离1111(,)(,)2ccciiijijiijPPP m mm m(7-6)可分性判据第七章 特征选择15基于距离的可分性判据的矩阵形式1()()cTbiiiiSPmm mm()()111()()inciiTwikikiikiSPnxmxm()tr()dwbJSSx基于距离的准则概念直观，计算方便，但与错误率没有直接联系样本类间离散度矩阵样本类内离散度矩阵类间可分离性判据可分性判据第七章 特征选择16特征可分性评价判据可分性判据FEATEVAL Evaluation of feature set for classifica
8、tionJ=FEATEVAL(A,CRIT,T)J=FEATEVAL(A,CRIT,N)A input dataset CRIT string name of a method or untrained mapping T validation dataset(optional)N number of cross-validations(optional)DESCRIPTION Evaluation of features by the criterion CRIT for classification,using objects in the dataset A.The larger J,t
9、he better.Resulting J-values are incomparable over the various methods.第七章 特征选择177.2.2 基于概率的可分性判据u基于概率的可分性判据：用概率密度函数间的距离（交叠程度）来度量类别可分性。1212()(|),(|),pJg ppP P dxxxx可分性判据p(x|1)p(x|2)p(x|1)p(x|2)p(x|1)p(x|2)第七章 特征选择18散度u散度：区分i，j两类的总的平均可分性信息(|)()(|)(|)ln(|)iDijjiijjpJIIppdpxxxxxxx(|)()ln(|)iijjplpxxx(|
10、)()()(|)ln(|)iijijijpIE lpdpxxxxxxx可分性判据对数似然比对第i类的平均可分性信息第七章 特征选择19正态分布条件下的散度u正态分布条件下的散度判据可以用分布参数表示，特别是u一维正态分布：if(,),(,),iiijjjijNN 1()()()TDijijJxMahalanobis距离可分性判据22()()ijDJx第七章 特征选择207.2.3 基于熵函数的可分性判据u熵函数：衡量后验概率分布的集中程度。后验概率越集中，就越有利于分类。1(|),.,(|)ccHJPPxxuShannon熵：121(|)log(|)cciiiJPP xxu平方熵：2212 1
11、(|)cciiJPxu熵函数期望表征类别的分离程度：()()()EJEHHpdxxxx可分性判据熵越小，关于类别的不确定性就越小，可分性越好第七章 特征选择217.2.4 类别可分离性判据应用举例u图像分割：灰度图像二值化，Otsu阈值算法(Otsu thresholding)。u图像有L阶灰度，ni是灰度为i的像素数，图像总像素数 N=n1+n2+nL灰度为i的像素概率：pi=ni/N类间方差：2221122()()()Bk1211112111,1kLLiiiiikiiikLiiiikipipippp可分性判据第七章 特征选择22Otsu thresholdingu灰度图像的最佳阈值:21a
12、 rg m a x()LBktku灰度图像二值化Otsu算法演示及程序分析:可分性判据第七章 特征选择23u特征选择:=从原始特征中挑选出一些最有代表性、分类性能最好的特征进行分类。u从D个特征中选取d个,共有CdD种组合。若不限定特征个数d，则共有2D种组合。典型的组合优化问题u要解决两个问题：选择的标准:可分离性判据快速寻优算法vs.穷举法 7.3 特征选择方法dDC第七章 特征选择24u从是否直接考虑分类器性能看Wrapper方法：将特征选择和分类器结合在一起，在分类过程中表现优异的的特征子集会被选作最优特征子集。Filter方法：不考虑所使用的分类器。根据独立于分类器的指标J来评价所选
13、择的特征子集S，在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。u从选择特征的顺序看：自下而上：特征数从零逐步增加到d。自上而下：特征数从D开始逐步减少到d。特征选择的方法分类dDC第七章 特征选择25经典特征选择算法u许多特征选择算法力求解决搜索问题，经典算法有：分支定界法:最优搜索，设法将所有可能特征组合构建一个树状结构，尽可能早达到最优解，而不必遍历整个树，效率比盲目穷举法高。次优搜索：单独最优特征组合法：顺序前进法 顺序后退法其他组合优化方法：模拟退火法 Tabu搜索法 遗传算法特征选择第七章 特征选择267.4 特征选择的次优算法u单独最优特征组合法u顺序前进法u顺
14、序后退法特征选择第七章 特征选择271）单独最优特征组合u计算各特征单独使用时的可分性判据J并加以排队，取前d个作为选择结果u单独最优，希望组合也最优。但实际情况与此假设不一定相符。u当可分性判据对各独立的特征具有(广义)可加性，该方法可以选出一组最优的特征，例：各类具有正态分布各特征统计独立可分性判据基于Mahalanobis距离1()()()TDijijJx121(,.,)()dijdijkkJx xxJx特征选择W,R=FEATSELI(A,CRIT,K,T)特征选择 INPUT A Training dataset CRIT Name of the criterion or untra
15、ined mapping (default:NN,i.e.the 1-Nearest Neighbor error)K Number of features to select(default:sort all features)T Tuning dataset(optional)OUTPUT W Feature selection mapping R Matrix with criterion values DESCRIPTION Individual selection of K features using the dataset A.CRIT sets the criterion us
16、ed by the feature evaluation routine FEATEVAL.If the dataset T is given,it is used as test set for FEATEVAL.For K=0 all features are selected,but reordered according to the criterion.The result W can be used for selecting features using B*W.第七章 特征选择292）顺序前进法Sequential forward selectionu自下而上搜索方法。u每次从
17、未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的可分性最大，直至特征数增加到d为止。u该方法考虑了所选特征与已入选特征之间的组合因素。特征选择W,R=FEATSELF(A,CRIT,K,T,FID)Forward selection of K features using the dataset A.CRIT sets the criterion used by the feature evaluation routine FEATEVAL.第七章 特征选择303）顺序后退法Sequential backw.selectionu该方法根据特征子集的表现来选择特征u搜索特征子集
18、：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的可分性或分类识别率。u逐次进行，直至可分性或识别率开始下降为止u在高维空间进行计算。结合“leave-one-out”方法估计平均可分性或识别率：用N-1个样本判断余下一个样本的类别，N次操作取平均。特征选择W,R=FEATSELB(A,CRIT,K,T,FID)Backward selection of K features using the dataset A.CRIT sets the criterion used by the feature evaluation routine FEATEVAL.第七章 特征选择317
19、.5 特征选择的遗传算法u从生物进化论得到启迪。遗传，变异，自然选择。基于该思想发展了遗传优化算法：无数可能的重组和突变组合中发现适应性最强的组合。u基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个D位的0/1字符构成的串表示一种特征组合。染色体u群体：若干个个体的集合，即问题的一些待选解的集合。u交叉：由当前群体中的两个个体的链码交叉产生新一代的两个个体。u变异：在一个链码中随机选取若干基因使其翻转。特征选择第七章 特征选择32遗传算法u适应度：每个个体xi的函数值fi，个体xi越好，适应度fi越大。新一代群体对环境的平均适应度比父代高。u遗传算法的基本框架：
20、uStep1:令进化代数t=0，给出初始化群体P(t)，xg为任一个体。uStep2:计算群体P(t)中每个个体xg的适应度值，并将群体中最优解x与xg比较，如果xg 的性能优于x，则x=xguStep3:如果终止条件满足，则算法结束，x为算法的结果。否则继续。uStep4:从P(t)中按一定概率选择个体并进行交叉和变异操作，得到新一代群体P(t+1)。令t=t+1,转到Step2。特征选择第七章 特征选择33u从是否直接考虑分类器性能看Wrapper方法：将特征选择和分类器结合在一起，在分类过程中表现优异的的特征子集会被选中。Filter方法：不考虑所使用的分类器。根据独立于分类器的指标J来
21、评价所选择的特征子集S，在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。u以分类性能为准则的特征选择的方法只适合某些分类器。7.6 以分类性能为准则的特征选择dDC第七章 特征选择347.7 讨论u特征的选择与提取是模式识别中重要而非常困难的一步 模式识别的基础要素：分析各种特征的有效性并选出最有代表性的特征 降低特征维数在很多情况下是有效设计分类器的重要课题u三大类特征：物理、结构和数学特征 物理和结构特征：易于为人的直觉感知，但难于定量描述，因而不易用机器判别 数学特征：易于用机器定量描述和判别第七章 特征选择35习题1.试推导(8-6)式，即：1111(,)(,)2cc
22、ciiijijiijPPP m mm m2.试由(8-1)式推导(8-5)式，即：()111()(,)(,)incidikiiikiJPnxxmm m3.习题8.1 9.习题9.1 第七章 特征选择36附：模拟退火法简介u来源于统计力学。材料粒子从高温开始，非常缓慢地降温(退火)，粒子就可在每个温度下达到热平衡。u假设材料在状态i的能量为E(i)，那么材料在温度T时从状态i进入状态j遵循如下规律：如果E(j)E(i)，接受该状态被转换。如果E(j)E(i)，则状态转换以如下概率被接受：()()E iE jKTe特征选择第七章 特征选择37模拟退火法(II)u在某一温度下，进行了充分转换后，材料
23、达到热平衡，这时材料处于状态i的概率满足：()()()E iKTTEjKTj SePxieu所有状态在高温下具有相同概率。()()1limE iKTEjTKTj SeSe特征选择波尔兹曼分布第七章 特征选择38模拟退火法(III)u当温度降至很低时，材料会以很大概率进入最小能量状态。u模拟退火优化法：min:f(x)，其中xS，表示优化问题的一个可行解。N(x)S表示x的一个邻域集合。minmin()minmin()01lim0E iEKTEjETKTj SiSeSeotherwise特征选择第七章 特征选择39模拟退火法(IV)u首先给定初始温度T0和初始解x0，以概率P生成下一个新解x：u
24、对于温度Ti和该优化问题的解xk，可以生成新解x。u经过多次转换，降低温度得到Ti+1Ti。在Ti+1下重复上述过程。u优化即是交替寻找新解和缓慢降低温度，最终的解是对该问题寻优的结果。000()()01()()()ffTffPeotherwisexxxxxx特征选择第七章 特征选择40模拟退火法(V)u经过有限次转换，在温度Ti下的平衡态xi的分布为：u当温度T降为0时，xi的分布为：()()()ijfxTiifxTjSeP Te*minmin10iixSSPotherwise*min1iixSP特征选择第七章 特征选择41特征选择的模拟退火法uStep1:令i=0,k=0,给出初始温度T0和初始特征组合x(0)。uStep2:在x(k)的邻域N(x(k)中选择一个状态x，即新特征组合。计算其可分性判据J(x)，并按概率P接受为下一个状态x(k+1)=x。uStep3:如果在Ti下还未达到平衡，则转到Step2。uStep4:如果Ti已经足够低，则结束，当时的特征组合即为算法的结果。否则继续。uStep5:根据温度下降方法计算新的温度Ti+1。转到Step2。特征选择
