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

第五章 特征选择与提取 基本概念 模式类别可分性的测度 特征选取 离散K-L 变换 采用K L 变换的分类特征提取基本概念 特征形成 根据被认识的对象产生出一组基本特征，这些基本特征可以是通过计算得到的，也可以是通过一定的工具测量出来的，这些特征我们叫做原始特征。通常到从物理量到原始特征需要经过很多的过程，如识别物体，要对物体影像进行数字化，得到数字图像，再对数字图像进行各种预处理，从而得到物体的几何的、颜色的特征。基本概念 特征选择和提取是模式识别中的一个关键问题 前面讨论分类器设计的时候，一直假定已给出了特征向量维数确定的样本集，其中各样本的每一维都是该样本的一个特征；这些特征的选择是很重要的，它直接影响到分类器的设计及其性能；假若对不同的类别，这些特征的差别很大，则比较容易设计出具有较好性能的分类器。基本概念 特征选择和提取是构造模式识别系统的一个重要课题 在很多实际问题中，往往不容易找到那些最重要的特征，或受客观条件的限制，不能对它们进行有效的测量；因此在测量时，由于人们心理上的作用，只要条件许可总希望把特征取得多一些；另外，由于客观上的需要，为了突出某些有用信息，抑制无用信息，有意加上一些比值、指数或对数等组合计算特征（在数据上作一些处理）；如果将数目很多的测量值不做分析，全部直接用作分类特征，不但耗时，而且会影响到分类的效果，产生“特征维数灾难”问题。基本概念 为了设计出效果好的分类器，通常需要对原始的测量值集合进行分析，经过选择或变换处理，组成有效的识别特征；在保证一定分类精度的前提下，减少特征维数，即进行“降维”处理，使分类器实现快速、准确和高效的分类。为达到上述目的，关键是所提供的识别特征应具有很好的可分性，使分类器容易判别。为此，需对特征进行选择。应去掉模棱两可、不易判别的特征；所提供的特征不要重复，即去掉那些相关性强且没有增加更多分类信息的特征。基本概念 说明 实际上，特征选择和提取这一任务应在设计分类器之前进行；但从通常的模式识别学习过程来看，在讨论分类器设计之后讲述特征选择和提取，更有利于加深对该问题的理解。信息获取 预处理 特征选取分类器设计模式分类错误率检测改进分类器(参数)识别结果输出基本概念 所谓特征选择，就是从n个度量值集合x1,x2,xn中，按某一准则选取出供分类用的子集，作为降维（m维，mn）的分类特征；所谓特征提取，就是使(x1,x2,xn)通过某种变换，产生m个特征(y1,y2,ym)(mn)，作为新的分类特征（或称为二次特征）；其目的：都是为了在尽可能保留识别信息的前提下，降低特征空间的维数，已达到有效的分类。基本概念 以细胞自动识别为例 通过图像输入得到一批包括正常细胞和异常细胞的图像，我们的任务是根据这些图像区分哪些细胞是正常的，哪些细胞是异常的；首先找出一组能代表细胞性质的特征，为此可计算 细胞总面积 总光密度 胞核面积 核浆比 细胞形状 核内纹理 第四章特征选择和提取 以细胞自动识别为例 这样产生出来的原始特征可能很多（几十甚至几百个），或者说原始特征空间维数很高，需要降低（或称压缩）维数以便分类；一种方式是从原始特征中挑选出一些最有代表性的特征，称之为特征选择；另一种方式是用映射（或称变换）的方法把原始特征变换为较少的特征，称之为特征提取。5.1模式类别可分性的测度 5.1.1距离和散布矩阵 点到点之间的距离 点到点集之间的距离(距离平方、均方距离)5.1模式类别可分性的测度 类内距离K分量的无偏方差K分量的均值5.1模式类别可分性的测度类内散布矩阵 因为xi和xj是同一类中的不同样本，他们应该是独立的模式样本向量，因此样本距离的均方值为：其中R是该类模式分布的相关矩阵，m为均值向量，C为协方差矩阵。对属于同一类的模式样本，类内散布矩阵表示各样本点围绕其均值周围的散布情况，这里即为该分布的协方差矩阵。5.1模式类别可分性的测度类间距离和类间散布矩阵 和 为两类模式样本集合类间距离表示：通常取一些简单的表达式来定义：其中m1和m2是两个类模式样本集合的各自均值向量，m1k和m2k是m1和m2的第k分量，n为维数。可以写成矩阵相乘的形式 5.1模式类别可分性的测度 表示1和2两类模式的类间散布矩阵 当三类或者更多的时候就引入先验概率作为加权:其中为多类模式（这里共c类）分布总体的均值向量。5.1模式类别可分性的测度多类模式集散布矩阵其中Ci第i类的协方差矩阵定义总体散布矩阵为：Sb、St、Sw之间满足以上各类散布矩阵反映了各类模式在模式空间的分布情况，但它们与分类的错误率没有直接联系。5.1.2 散度 散度的定义 前面定义过似然函数和似然比，这些都提供了两种模式可分的度量，也就是在错误概率最小意义下的模式样本的分类。求该式的值，需要 和的确切的表达式，这个要求较高，我们转而求 5.1.2 散度同理定义散度该式子是散度的一般表达式。当i和j的分布是一些特殊的表达式子，那么对数似然比函数和散度可以得到一些很简单形式。5.1.2 散度当i和j服从正态分布，散度为：（1）如果CjCiC，那么这正好是两类模式之间的马氏距离平方 5.1.2 散度（2）如果两类均为正态分布且数学期望值相等mimj，那么 当Ci和Cj之间越相近则散度越小。5.1.2 散度 从上面的定义我们可以看出散度Jij具有如下性质：(i)Jij=Jji,(ii)当i和j的分布不同时，Jij0（iii）当i和j的分布完全同时，Jij0（iv）在模式特征的各个分量都相互独立的情况下,有：(v)当新加入特征的时候，永远不会使散度减小（vi)散度与分类错误概率有比较密切的关系.5.1.3 巴氏（Bhattacharyya）距离在分析分类器的错误概率时候，引入函数用它作为类别可分性的一个判别准则，当概率密度函数都是正态分布情况，可以得到及其简化的表达式。并记为 通常称为Bhattacharyya距离（平方）。如果Ci=Cj就会得到更加简单的表达式它与马氏距离平方只是差一个系数。前面给大家介绍的各种表征量，就是在于给出一个参考量，用于对类的可分性的度量5.1.3巴特查雅（Bhattacharyya）距离5.2特征选择 设有n个可用作分类的测量值，为了在不降低（或尽量不降低）分类精度的前提下，减小特征空间的维数以减少计算量，需从中直接选出m个作为分类的特征。问题：在n个测量值中选出哪一些作为分类特征，使其具有最小的分类错误？5.2特征选择 从n个测量值中选出m个特征，一共有中可能的选法。一种“穷举”办法：对每种选法都用训练样本试分类一下，测出其正确分类率，然后做出性能最好的选择，此时需要试探的特征子集的种类达到种，非常耗时。需寻找一种简便的可分性准则，间接判断每一种子集的优劣。对于独立特征的选择准则 一般特征的散布矩阵准则5.2特征选择 对于独立特征的选择准则 类别可分性准则应具有这样的特点，即不同类别模式特征的均值向量之间的距离应最大，而属于同一类的模式特征，其方差之和应最小。假设各原始特征测量值是统计独立的，此时，只需对训练样本的n个测量值独立地进行分析，从中选出m个最好的作为分类特征即可。例：对于i和j两类训练样本的特征选择5.2特征选择 如果不同类别模式特征的均值向量之间的距离较大，而同属于一个类的模式特征的的方差和较小，那么我们认为模式具有良好的可分性，直观的表示就是 类与类之间的距离较大，每个类的所有样本的聚合性非常的好，因此我们可以从下面的角度出发，来考察n测量值中需要去除的部分。假设各个原始测量值是统计独立的，我们对n个测量值逐一独立分析，从中选出m个最好的作为分类特征即可。测量方法和选取原则如下：5.2特征选择5.2特征选择P(xk)ijmikmjkxkP(xk)ijmikmjkxkP(xk)ixkjimjk=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的行列式值越大，可分性越好。行列式形式：5.2特征选择（b）散度和变换准则J1和J2形式 当两类情况是正态分布的时，使Jij最大的子集，就是适合分离和两类模式的特征推广到多类，计算其平均散度：选出使平均散度最大的子集作为c类的分类特征缺点：加权求和，并以所求和J来作为评估标准是无法避免Jij之间的大小抵消的，或者说大的值会掩盖掉数值小的情况。5.2特征选择解决方法：引入变换散度 和 之间的变化关系：（1）随着的增加而增加，先快后慢。（2）的取值范围有限度（饱和度）。作用：中和、抵消、保留。平均变换散度：和 之间的变化关系？5.2特征选择（C）巴氏距离和詹夫利斯马特西斯距离（J-M距离）对正态分布模式的巴特查斯距离，如果Ci=Cj时候，能得到非常简单的形式 对aij取平均值但是会存在数值大aij的掩盖数值小aij的情况，5.2特征选择因此我们可以引用前面的变换方法，作一个类似的简单的变换来消除这种情况再取平均值 5.2特征选择5.2.4穷举式特征选取 方法3中介绍的一般原则，只是给出了比较科学的准则函数，但是还没有给出比较好的算法解决从n中测量值中选出m个作为分类特征量。这时采用1中介绍的思路，即按照中特征组合方案来进行穷举，得到选择最优。但是穷举法有个不利因素就是，计算量大，一则来之与当n很大的时候，计算量大，二则来自于本身可能要作矩阵运算或者求幂次运算。这可以从下面两种方法来降低运算量或者进一步简单化。5.2特征选择5.2.4 穷举式特征选取a）最大最小类对距离法 对多类问题，不是直接采用散度或者J-M准则来计算，而是计算类对距离来选择特征，或者采用更简单的方式（b）分支定界搜索法 核心思想是：逐一降维 要求：准则函数按照特征维数单调变化性质 方法：在分支树中找到J最大的节点。5.3离散K-L变换 全称：Karhunen-Loeve变换（卡洛南-洛伊变换）前面讨论的特征选择是在一定准则下，从n个特征中选出k个来反映原有模式。这种简单删掉某n-k个特征的做法并不十分理想，因为一般来说，原来的n个数据各自在不同程度上反映了识别对象的某些特征，简单地删去某些特征可能会丢失较多的有用信息。如果将原来的特征做正交变换，获得的每个数据都是原来n个数据的线性组合，然后从新的数据中选出少数几个，使其尽可能多地反映各类模式之间的差异，而这些特征间又尽可能相互独立，则比单纯的选择方法更灵活、更有效。K-L变换就是一种适用于任意概率密度函数的正交变换。5.3离散K-L变换 我们在前面的特征选取中，从最终的结果来看，无非就是从n个测量值中选出了m个作为特征分量。从而就丢掉了nm个分量，这一丢实际上就是丢掉了nm个分量所带的信息。下面给大家介绍的K-L正交变换，就能够把n个测量信息都充分的利用起来,并且力图保持，变换后的n分量特征是相互独立的。这是我们讨论K-L变换的两个目标。5.3离散K-L变换5.3.1离散的有限K-L展开展开式的形式有一连续的随机实函数用一已知的正交函数集 的线性组合来展开:是正交函数，满足正交性条件：而aj是展开式的随机系数5.3.1离散的有限K-L展开将展开式写成离散形式，即将连续的随机函数和连续的正交函数在定义域内等间隔的采样为n个离散点写成向量的形式：取前面m项，做近似其中5.3.1离散的有限K-L展开在这里我们可以将向量x看成于一个模式样本，经过展开，这实际上是一个离散变换，而且是正交的。如果对c中模式类别，作离散正交展开，则对每一模式类别可分别写成xi=ai，其中取决于所选的正交函数集。对各个模式类别，正交函数都是相同的，但其展开系数向量ai则因类别的不同模式分布而异5.3离散K-L变换5.3.1离散的有限K-L展开K-L展开式的性质K-L展开式的根本性质是:将随机向量x展开为另一组正交向量j的线性和，且其展开式系数aj（即系数向量a的各个分量）具有不同的性质NOTE:(1)x是随机变量，而正交向量j是确定的，换句话说一旦选定了某个函数集,那么j就是确定的，而不是随机的。(2)x是向量，表现出随机性，而且x的各个分量很大程度上表现出相关性，而展开之后的系数向量a的各个分量不具有相关性，这一点的考察可以从x和a的自相关矩阵来看。下面我们就进一步推导在x已知的情况下，如何找到正教函数集或者说变换矩阵，使之得到的a的分量具有完全的或者较好的独立性。5.3离散K-L变换K-L展开式系数的计算 设随机向量的总体自相关矩阵为,将 带入其中，得到 要求a的各个分量都具有统计独立性，也就是说满足如下关系：写成矩阵形式 5.3离散K-L变换因此同时i都是归一正交的，由此可以得到：写成向量形式：就是x的自相关矩阵R的本征根 是本征向量 到此我们就能够知道，选择什么样的向量来组成来5.3离散K-L变换K-L展开式系数的计算步骤 1）计算 向量X的相关矩阵，如果是多类的话，则用全体相关矩阵 2）求出相关矩阵R的本征根和对应的本征向量 3）展开式5.3离散K-L变换5.3.2按K-L展开式选择特征 K-L展开式用于特征选择相当于一种去相关的线性变换。若从n个本征向量中取出m个组成变换矩阵，即=(12m)，mn此时，是一个n*m维矩阵，x是n维向量，经过Tx变换，即得到降维为m的新向量。5.3.2按K-L展开式选择特征选取变换矩阵，使得降维后的新向量在最小均方差条件下接近原来的向量x 原展开式为：如果只是取用前面m项，则产生的误差为：的均方误差为：选择适合的b使 最小，应该满足：5.3.2按K-L展开式选择特征因此bEaj,此时误差为：接着要考虑选择适合的，使 的值最小5.3.2按K-L展开式选择特征因为 满足正交性，所以利用拉格朗日乘法可以求出引入的修正函数其最小决方误差为本征值越小，则误差越小。5.3离散K-L变换5.3.2按K-L展开式选择特征结论（1）从K-L展开式的性质和按最小均方差的准则来选择特征，应使Eaj=0。由于Ea=E Tx=TEx，故应使Ex=0。基于这一条件，在将整体模式进行K-L变换之前，应先将其均值作为新坐标轴的原点，采用协方差矩阵C或自相关矩阵R来计算特征值。如果Ex0，则只能得到“次最佳”的结果。5.3离散K-L变换5.3.2按K-L展开式选择特征结论(2)将K-L展开式系数aj（亦即变换后的特征）用yj表示，写成向量形式：y=Tx。此时变换矩阵用m个本征向量组成。为使误差最小，不采用的特征向量，其对应的本征值应尽可能小。因此，将本征值按大小次序标号，即1 2 m n=0若首先采用前面的m个特征向量，便可使变换误差最小。此时的变换矩阵为T（1T、2T、，mT）T5.3离散K-L变换5.3.2按K-L展开式选择特征结论(3)K-L变换是在均方误差最小的意义下获得数据压缩的最佳变换，且不受模式分布的限制。对于一种类别的模式特征提取，它不存在特征分类问题，只是实现用低维的m个特征来表示原来高维的n个特征，使其误差最小，亦即使其整个模式分布结构尽可能保持不变。5.3离散K-L变换5.3.2按K-L展开式选择特征 结论(4)通过K-L变换能获得互不相关的新特征。若采用较大本征值对应的本征向量组成变换矩阵，则能对应地保留原模式中方差最大的特征成分，所以K-L变换起到了减小相关性、突出差异性的效果。在此情况下，K-L变换也称为主成分变换。5.3离散K-L变换5.3.2按K-L展开式选择特征 例题1 原始模式分布 特征提取5.4采用KL变换的分类特征提取 K-L变换的优点我们在前面给大家介绍过:通过K-L变换能获得互不相关或者相关性非常差的新的特征，因此，如果我们选用大本征值对应的向量组成的变换矩阵，则能对应的保留原模式中方差最大的特征成分.下面分析K-L变换的具体应用。在本征向量选取的中不能简单丢弃，较小本征值对应的本征向量，加入到变换矩阵中会带来的影响，可能对分类也会有利的因素。所以在特征提取时候要特别注意，保留不同类别的模式信息。单纯考虑尽可能准确的代表原来模式的成分，又是有并不一定有利于分类的鉴别，因此下面我们就选用不同的散布矩阵（因为不同的散布矩阵是从不同的角度来表示模式分布的统计特性）5.4采用KL变换的分类特征提取5.4采用KL变换的分类特征提取（1）把模式总体的协方差矩阵作K-L变换 采用总体矩阵能保留模式原有分布的主要结构，会尽量多的保留可分信息。其应用之一就是，将高维的样本，映射到二维或者三维上来，直观的可视化大致可分类的情况。（2）广义K-L变换采用类内散布矩阵Sw做KL变换 Sw等于各模式的协方差矩阵之和，不但包含了不同类的信息，还包括类间（类差异）的信息。将Sw作K-L变换，得到的本征值，大本征值对应的本征向量组成的变换矩阵能突出各类模式的主要特征分量，而小本征值对应的本征向量组成的变换，经过变换后，能突出原模式总体中同一类模式所聚集的最小的特征空间范围5.4采用KL变换的分类特征提取（3）以类间距离为出发点的KL变换 为了强调不同类别之间的差异，类别之间的平均距离是一个重要的指标，因此可以采用类间散布矩阵。Sb1由不大于c1个独立向量组成，只有c1个非零本征值，通常维数n是大于类别数c，所以sb1是对称正定的，但是奇异的，同样求出sb1的本征根排成1 2 c-10,而c=n=0,选出m个与大本征根对应的本征向量组成的变换矩阵。5.4采用KL变换的分类特征提取（3）以类间距离为出发点的KL变换 类间散布矩阵也可以写成更加直接的形式（c类模式中各类之间的距离平方和）式 中为类模式的自相关矩阵。一般类间距离比类内距离要大得多的多类问题，采用类间散布矩阵比较好。5.4采用KL变换的分类特征提取若设n维原模式的类内和类间散布矩阵为Sw和，Sb,经过特征提取后得m维降维模式，它的类内和类间散布矩阵为Swm和Sbm，此时有为所选用的变换矩阵，取迹 来计算出不同的变换矩阵的J值，J值最大者具有较好的类别可分性。这也是一个较好的测试，作为进行可分性判别的一个测度。Jz值最大者具有较好的类别可分性。5.4采用KL变换的分类特征提取例题2：要求：试用不同的散布矩阵作K-L变换的特征提取，并计算相应的J值求解：（1）采用自相关矩阵R（2）采用类内散布矩阵Sw（3）采用类间散布矩阵Sb（4）采用总体散布矩阵St5.4采用KL变换的分类特征提取从这些例子中得到一些结论：（1）KL变换能在最小均方误差的意义上获得最优的正交变换，能够消除模式特征之间的相关性、突出差异有很好的效果，当类别的数目很多，维数较高，性能就不是很好了。（2）表示类之间或者类内的分布的散布矩阵很多，很难找到一个统一的某种散布矩阵作为K-L变换。（3）正交变换的方式很多，比如我们有FFT FDCT等，但是FKLT还没有，计算量较大。5.4采用KL变换的分类特征提取作业1.设有如下三类模式样本集1，2和3，其先验概率相等，求Sw和Sb 1：(10)t,(20)t,(11)t2：(-10)t,(01)t,(-11)t3：(-1-1)t,(0-1)t,(0-2)t作业2.设有如下两类样本集，其出现的概率相等：1：(000)T,(100)T,(10-1)T,(110)T2：(00-1)T,(010)T,(01-1)T,(11-1)T用K-L变换，分别把特征空间维数降到二维和一维，并画出样本在该空间中的位置。