模式识别-5--特征选择与提取

第五章特征选择与提取•基本概念•模式类别可分性的测度•特征选取•离散K-L变换•采用K－L变换的分类特征提取基本概念•特征形成根据被认识的对象产生出一组基本特征，这些基本特征可以是通过计算得到的，也可以是通过一定的工具测量出来的，这些特征我们叫做原始特征。通常到从物理量到原始特征需要经过很多的过程，如识别物体，要对物体影像进行数字化，得到数字图像，再对数字图像进行各种预处理，从而得到物体的几何的、颜色的特征。基本概念•特征选择和提取是模式识别中的一个关键问题–前面讨论分类器设计的时候，一直假定已给出了特征向量维数确定的样本集，其中各样本的每一维都是该样本的一个特征；–这些特征的选择是很重要的，它直接影响到分类器的设计及其性能；–假若对不同的类别，这些特征的差别很大，则比较容易设计出具有较好性能的分类器。基本概念•特征选择和提取是构造模式识别系统的一个重要课题–在很多实际问题中，往往不容易找到那些最重要的特征，或受客观条件的限制，不能对它们进行有效的测量；–因此在测量时，由于人们心理上的作用，只要条件许可总希望把特征取得多一些；–另外，由于客观上的需要，为了突出某些有用信息，抑制无用信息，有意加上一些比值、指数或对数等组合计算特征（在数据上作一些处理）；–如果将数目很多的测量值不做分析，全部直接用作分类特征，不但耗时，而且会影响到分类的效果，产生“特征维数灾难”问题。基本概念•为了设计出效果好的分类器，通常需要对原始的测量值集合进行分析，经过选择或变换处理，组成有效的识别特征；•在保证一定分类精度的前提下，减少特征维数，即进行“降维”处理，使分类器实现快速、准确和高效的分类。•为达到上述目的，关键是所提供的识别特征应具有很好的可分性，使分类器容易判别。为此，需对特征进行选择。–应去掉模棱两可、不易判别的特征；–所提供的特征不要重复，即去掉那些相关性强且没有增加更多分类信息的特征。基本概念•说明–实际上，特征选择和提取这一任务应在设计分类器之前进行；–但从通常的模式识别学习过程来看，在讨论分类器设计之后讲述特征选择和提取，更有利于加深对该问题的理解。信息获取预处理特征选取分类器设计模式分类错误率检测改进分类器(参数)识别结果输出基本概念•所谓特征选择，就是从n个度量值集合{x1,x2,…,xn}中，按某一准则选取出供分类用的子集，作为降维（m维，mn）的分类特征；•所谓特征提取，就是使(x1,x2,…,xn)通过某种变换，产生m个特征(y1,y2,…,ym)(mn)，作为新的分类特征（或称为二次特征）；•其目的：都是为了在尽可能保留识别信息的前提下，降低特征空间的维数，已达到有效的分类。基本概念•以细胞自动识别为例–通过图像输入得到一批包括正常细胞和异常细胞的图像，我们的任务是根据这些图像区分哪些细胞是正常的，哪些细胞是异常的；–首先找出一组能代表细胞性质的特征，为此可计算•细胞总面积•总光密度•胞核面积•核浆比•细胞形状•核内纹理•……第四章特征选择和提取•以细胞自动识别为例–这样产生出来的原始特征可能很多（几十甚至几百个），或者说原始特征空间维数很高，需要降低（或称压缩）维数以便分类；–一种方式是从原始特征中挑选出一些最有代表性的特征，称之为特征选择；–另一种方式是用映射（或称变换）的方法把原始特征变换为较少的特征，称之为特征提取。5.1模式类别可分性的测度•5.1.1距离和散布矩阵–点到点之间的距离–点到点集之间的距离(距离平方、均方距离)babaD),(nkkktbabababaD122)())((),(nkikkaxiaxD12)(2)())(,(KinkikkKiiaxkiaxDkaxD112)(12)(2)(1))(,(1),(5.1模式类别可分性的测度•类内距离nkkiajaD1222)(,)(2)(211kikkaakKiikkaKa1)(1K分量的无偏方差K分量的均值5.1模式类别可分性的测度•类内散布矩阵因为xi和xj是同一类中的不同样本，他们应该是独立的模式样本向量，因此样本距离的均方值为：其中R是该类模式分布的相关矩阵，m为均值向量，C为协方差矩阵。对属于同一类的模式样本，类内散布矩阵表示各样本点围绕其均值周围的散布情况，这里即为该分布的协方差矩阵。nkktttttCtrmmRtrmmxxEtrxExExxEiajaD1222][2][2222)(,)(5.1模式类别可分性的测度类间距离和类间散布矩阵和为两类模式样本集合类间距离表示：通常取一些简单的表达式来定义：其中m1和m2是两个类模式样本集合的各自均值向量，m1k和m2k是m1和m2的第k分量，n为维数。可以写成矩阵相乘的形式)(ia)(ibKbiKajbaDij,...,3,2,1;,...,3,2,1,,)()(2nkkkmmD12212)(tbmmmmS))((212125.1模式类别可分性的测度•表示1和2两类模式的类间散布矩阵•当三类或者更多的时候就引入先验概率作为加权:其中为多类模式（这里共c类）分布总体的均值向量。tbmmmmS))((21212tiiciibmmmmPS))(()(0011iciimPxEm10)(5.1模式类别可分性的测度多类模式集散布矩阵其中Ci第i类的协方差矩阵定义总体散布矩阵为：Sb、St、Sw之间满足以上各类散布矩阵反映了各类模式在模式空间的分布情况，但它们与分类的错误率没有直接联系。ciiiciitiiiwCPmxmxEPS11)(|))(()(tmxmxESt))((00SbSwSt5.1.2散度•散度的定义前面定义过似然函数和似然比，这些都提供了两种模式可分的度量，也就是在错误概率最小意义下的模式样本的分类。求该式的值，需要和的确切的表达式，这个要求较高，我们转而求)|()|(ln)(jiijxpxpx)|(ixp)|(jxpxjiiijijdxxpxpxpxEixI)|()|(ln)|()]([)(5.1.2散度同理定义散度该式子是散度的一般表达式。当ωi和ωj的分布是一些特殊的表达式子，那么对数似然比函数和散度可以得到一些很简单形式。xijjjijidxxpxpxpxEjxI)|()|(ln)|()]([)(xijiijjidxjxpxpxpxpIIJij)|()|(ln)]|()|([5.1.2散度当ωi和ωj服从正态分布，散度为：（1）如果Cj＝Ci＝C，那么这正好是两类模式之间的马氏距离平方)Cj,(N~)|(),(~)|(mjjxPCimiNixP和))()[(21)])([(211111mjmimjmiCCtrCCCCtrIjiIijJijjijiij（)]()211mjmiCmjmiIijt（)]()1jitjiijmmCmmJ（5.1.2散度（2）如果两类均为正态分布且数学期望值相等mi＝mj，那么当Ci和Cj之间越相近则散度越小。)]([21ln2111ijCCCitrCiCjIij)])([2111ijCCCjCitrJij（5.1.2散度从上面的定义我们可以看出散度Jij具有如下性质：(i)Jij=Jji,(ii)当ωi和ωj的分布不同时，Jij0（iii）当ωi和ωj的分布完全同时，Jij＝0（iv）在模式特征的各个分量都相互独立的情况下,有：(v)当新加入特征的时候，永远不会使散度减小（vi)散度与分类错误概率有比较密切的关系.mkkijxJxmxxJijxJij1)(),...,2,1()(),,...,,(),...,,(12121mmijmijxxxxJxxxJ5.1.3巴氏（Bhattacharyya）距离•在分析分类器的错误概率时候，引入函数用它作为类别可分性的一个判别准则，当概率密度函数都是正态分布情况，可以得到及其简化的表达式。xsisidxxpxps)|()|(ln)(1212112)(ln21)(2)(81)21(CjCiCCmmCCmmjijijitjissjijijiijiCjCisCCsmmsCCsmmsss11)1(ln21)()1())(1(21)(并记为通常称为Bhattacharyya距离（平方）。如果Ci=Cj就会得到更加简单的表达式它与马氏距离平方只是差一个系数。前面给大家介绍的各种表征量，就是在于给出一个参考量，用于对类的可分性的度量)21(ija5.1.3巴特查雅（Bhattacharyya）距离)()(811jitjiijmmCmma5.2特征选择•设有n个可用作分类的测量值，为了在不降低（或尽量不降低）分类精度的前提下，减小特征空间的维数以减少计算量，需从中直接选出m个作为分类的特征。•问题：在n个测量值中选出哪一些作为分类特征，使其具有最小的分类错误？5.2特征选择•从n个测量值中选出m个特征，一共有中可能的选法。–一种“穷举”办法：对每种选法都用训练样本试分类一下，测出其正确分类率，然后做出性能最好的选择，此时需要试探的特征子集的种类达到种，非常耗时。–需寻找一种简便的可分性准则，间接判断每一种子集的优劣。•对于独立特征的选择准则•一般特征的散布矩阵准则)!(!!mnmnCmnmnC5.2特征选择•对于独立特征的选择准则–类别可分性准则应具有这样的特点，即不同类别模式特征的均值向量之间的距离应最大，而属于同一类的模式特征，其方差之和应最小。–假设各原始特征测量值是统计独立的，此时，只需对训练样本的n个测量值独立地进行分析，从中选出m个最好的作为分类特征即可。•[例：对于i和j两类训练样本的特征选择]5.2特征选择•如果不同类别模式特征的均值向量之间的距离较大，而同属于一个类的模式特征的的方差和较小，那么我们认为模式具有良好的可分性，直观的表示就是类与类之间的距离较大，每个类的所有样本的聚合性非常的好，因此我们可以从下面的角度出发，来考察n测量值中需要去除的部分。•假设各个原始测量值是统计独立的，我们对n个测量值逐一独立分析，从中选出m个最好的作为分类特征即可。测量方法和选取原则如下：5.2特征选择5.2特征选择P(xk)ωiωjmikmjkxkP(xk)ωiωjmikmjkxkP(xk)ωixkωjωimjk=mjk5.2特征选择•讨论：上述基于距离测度的可分性准则，其适用范围与模式特征的概率分布有关。–三种不同模式分布的情况•(a)中特征xk的分布有很好的可分性，通过它足以分离i和j两种类别；•(b)中的特征分布有很大的重叠，单靠xk达不到较好的分类，需要增加其它特征；•(c)中的i类特征xk的分布有两个最大值，虽然它与j的分布没有重叠，但计算Gk约等于0，此时再利用Gk作为可分性准则已不合适。–因此，假若类概率密度函数不是或不近似正态分布，均值和方差就不足以用来估计类别的可分性，此时该准则函数不完全适用。5.2特征选择•一般特征的散布矩阵准则（a）类内、类间和总体的散布矩阵Sw、Sb和St其中Sw表示类内样本之间的聚合性，Sb表示类与类之间的相距大小，Sw的量度的行列式值越小且Sb的行列式值越大，可分性越好。行列式形式：ciitiiiwmmmmEPS100|))(()(tiiciibmmmmPS))(()(0011}))({(00tmxmxESbSwStjibtSSJ)det(11iibtSStrJ)(215.2特征选择（b）散度和变换准则J1和J2形式当两类情况是正态分布的时，使Jij最大的子集，就是适合分离和两类模式的特征推广到多类，计算其平均散度：选出使平均散