模式识别7-特征选择和提取.ppt

特征选择和提取,特征选择和提取,特征选择和提取是模式识别中的一个关键问题 前面讨论分类器设计的时候，一直假定已给出了特征向量维数确定的样本集，其中各样本的每一维都是该样本的一个特征； 这些特征的选择是很重要的，它强烈地影响到分类器的设计及其性能； 假若对不同的类别，这些特征的差别很大，则比较容易设计出具有较好性能的分类器。,特征选择和提取,特征选择和提取是构造模式识别系统时的一个重要课题 在很多实际问题中，往往不容易找到那些最重要的特征，或受客观条件的限制，不能对它们进行有效的测量； 因此在测量时，由于人们心理上的作用，只要条件许可总希望把特征取得多一些； 另外，由于客观上的需要，为了突出某些有用信息，抑制无用信息，有意加上一些比值、指数或对数等组合计算特征； 如果将数目很多的测量值不做分析，全部直接用作分类特征，不但耗时，而且会影响到分类的效果，产生“特征维数灾难”问题。,特征选择和提取,为了设计出效果好的分类器，通常需要对原始的测量值集合进行分析，经过选择或变换处理，组成有效的识别特征； 在保证一定分类精度的前提下，减少特征维数，即进行“降维”处理，使分类器实现快速、准确和高效的分类。 为达到上述目的，关键是所提供的识别特征应具有很好的可分性，使分类器容易判别。为此，需对特征进行选择。 应去掉模棱两可、不易判别的特征； 所提供的特征不要重复，即去掉那些相关性强且没有增加更多分类信息的特征。,特征选择和提取,说明 实际上，特征选择和提取这一任务应在设计分类器之前进行； 从通常的模式识别教学经验看，在讨论分类器设计之后讲述特征选择和提取，更有利于加深对该问题的理解。,特征选择和提取,所谓特征选择，就是从n个度量值集合x1, x2, xn中，按某一准则选取出供分类用的子集，作为降维（m维，mn）的分类特征； 所谓特征提取，就是使(x1, x2, xn)通过某种变换，产生m个特征(y1, y2, ym) (mn) ，作为新的分类特征（或称为二次特征）； 其目的都是为了在尽可能保留识别信息的前提下，降低特征空间的维数，已达到有效的分类。,特征选择和提取,以细胞自动识别为例 通过图像输入得到一批包括正常细胞和异常细胞的图像，我们的任务是根据这些图像区分哪些细胞是正常的，哪些细胞是异常的； 首先找出一组能代表细胞性质的特征，为此可计算 细胞总面积 总光密度 胞核面积 核浆比 细胞形状 核内纹理 ,特征选择和提取,以细胞自动识别为例 这样产生出来的原始特征可能很多（几十甚至几百个），或者说原始特征空间维数很高，需要降低（或称压缩）维数以便分类； 一种方式是从原始特征中挑选出一些最有代表性的特征，称之为特征选择； 另一种方式是用映射（或称变换）的方法把原始特征变换为较少的特征，称之为特征提取。,7.1 模式类别可分性的测度,距离和散布矩阵 点到点之间的距离 点到点集之间的距离 类内距离,7.1 模式类别可分性的测度,距离和散布矩阵 类内散布矩阵 对属于同一类的模式样本，类内散布矩阵表示各样本点围绕其均值周围的散布情况，这里即为该分布的协方差矩阵。 类间距离和类间散布矩阵 多类模式集散布矩阵 以上各类散布矩阵反映了各类模式在模式空间的分布情况，但它们与分类的错误率没有直接联系。 （若与分类错误率联系起来，可采用散度作为类别可分性的度量，在此不详细介绍）,类别可分离性判据：衡量不同特征及其组合对分类是否有效的定量准则 理想准则：某组特征使分类器错误概率最小 实际的类别可分离性判据应满足的条件： 度量特性： 与错误率有单调关系 当特征独立时有可加性： 单调性： 常见类别可分离性判据：基于距离、概率分布、熵函数,类间可分性:=所有样本间的平均距离：,(8-1),squared Euclidian,(8-5),类内平均距离,类间 距离,(8-6),基于距离的准则概念直观，计算方便，但与错误率没有直接联系,样本类间 离散度矩阵,样本类内 离散度矩阵,类间可分离性判据,7.2 特征选择,设有n个可用作分类的测量值，为了在不降低（或尽量不降低）分类精度的前提下，减小特征空间的维数以减少计算量，需从中直接选出m个作为分类的特征。 问题：在n个测量值中选出哪一些作为分类特征，使其具有最小的分类错误？,特征选择:=从原始特征中挑选出一些最有代表性、分类性能最好的特征进行分类。 从D个特征中选取d个,共CdD种组合。若不限定特征选择个数，则共2D种组合 典型的组合优化问题 特征选择的方法大体可分两大类： Filter方法：根据独立于分类器的指标J来评价所选择的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。不考虑所使用的学习算法。 Wrapper方法：将特征选择和分类器结合在一起，在学习过程中表现优异的的特征子集会被选中。,经典特征选择算法,许多特征选择算法力求解决搜索问题，经典算法有： 分支定界法: 最优搜索，效率比盲目穷举法高。 单独最优特征组合法：次优搜索。 顺序后退法 顺序前进法 模拟退火法 Tabu搜索法 遗传算法,特征 选择,单独最优特征组合,计算各特征单独使用时的可分性判据J并加以排队，取前d个作为选择结果 不一定是最优结果 当可分性判据对各特征具有(广义)可加性，该方法可以选出一组最优的特征来，例： 各类具有正态分布 各特征统计独立 可分性判据基于Mahalanobis距离,特征 选择,顺序前进法,自下而上搜索方法。 每次从未入选的特征中选择一个特征，使得它与已入选的特征组合在一起时所得的J值为最大，直至特征数增加到d为止。 该方法考虑了所选特征与已入选特征之间的相关性。,特征 选择,顺序后退法,该方法根据特征子集的分类表现来选择特征 搜索特征子集：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率 依次迭代，直至识别率开始下降为止,特征 选择,遗传算法,从生物进化论得到启迪。遗传，变异，自然选择。 基因链码：待解问题的解的编码，每个基因链码也称为一个个体。对于特征选择，可用一个D位的0/1构成的串表示一种特征组合。 群体：若干个个体的集合，即问题的一些解的集合。 交叉：由当前两个个体的链码交叉产生新一代的个体。 变异：由一个链码随机某基因使其翻转。,特征 选择,遗传算法,适应度：每个个体xi的函数值fi，个体xi越好，fi越大。新一代群体对环境的平均适应度比父代高。 遗传算法的基本框架：,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。,特征 选择,6.5 讨论,特征的选择与提取是模式识别中重要而困难的一步 模式识别的第一步：分析各种特征的有效性并选出最有代表性的特征 降低特征维数在很多情况下是有效设计分类器的重要课题 三大类特征：物理、结构和数学特征 物理和结构特征：易于为人的直觉感知，但难于定量描述，因而不易用机器判别 数学特征：易于用机器定量描述和判别,7.2 特征选择,从n个测量值中选出m个特征，一共有 中可能的选法。 一种“穷举”办法：对每种选法都用训练样本试分类一下，测出其正确分类率，然后做出性能最好的选择，此时需要试探的特征子集的种类达到 种，非常耗时。 需寻找一种简便的可分性准则，间接判断每一种子集的优劣。 对于独立特征的选择准则 一般特征的散布矩阵准则,7.2 特征选择,对于独立特征的选择准则 类别可分性准则应具有这样的特点，即不同类别模式特征的均值向量之间的距离应最大，而属于同一类的模式特征，其方差之和应最小。 假设各原始特征测量值是统计独立的，此时，只需对训练样本的n个测量值独立地进行分析，从中选出m个最好的作为分类特征即可。 例：对于i和j两类训练样本的特征选择,7.2 特征选择,讨论：上述基于距离测度的可分性准则，其适用范围与模式特征的概率分布有关。 三种不同模式分布的情况 (a) 中特征xk的分布有很好的可分性，通过它足以分离i和j两种类别； (b) 中的特征分布有很大的重叠，单靠xk达不到较好的分类，需要增加其它特征； (c) 中的i类特征xk的分布有两个最大值，虽然它与j的分布没有重叠，但计算Gk约等于0，此时再利用Gk作为可分性准则已不合适。 因此，假若类概率密度函数不是或不近似正态分布，均值和方差就不足以用来估计类别的可分性，此时该准则函数不完全适用。,7.2 特征选择,一般特征的散布矩阵准则 类内、类间和总体的散布矩阵Sw、Sb和St Sw的行列式值越小且Sb的行列式值越大，可分性越好。 散布矩阵准则J1和J2形式 使J1或J2最大的子集可作为所选择的分类特征。 注：这里计算的散布矩阵不受模式分布形式的限制，但需要有足够数量的模式样本才能获得有效的结果。,作业,设有如下三类模式样本集1，2和3，其先验概率相等，求Sw和Sb 1：(1 0)T, (2 0) T, (1 1) T 2：(-1 0)T, (0 1) T, (-1 1) T 3：(-1 -1)T, (0 -1) T, (0 -2) T,7.3 离散K-L变换,全称：Karhunen-Loeve变换（卡洛南-洛伊变换） 前面讨论的特征选择是在一定准则下，从n个特征中选出k个来反映原有模式。 这种简单删掉某n-k个特征的做法并不十分理想，因为一般来说，原来的n个数据各自在不同程度上反映了识别对象的某些特征，简单地删去某些特征可能会丢失较多的有用信息。 如果将原来的特征做正交变换，获得的每个数据都是原来n个数据的线性组合，然后从新的数据中选出少数几个，使其尽可能多地反映各类模式之间的差异，而这些特征间又尽可能相互独立，则比单纯的选择方法更灵活、更有效。 K-L变换就是一种适用于任意概率密度函数的正交变换。,6.3 特征提取与K-L变换,特征提取：用映射（或变换）的方法把原始特征变换为较少的新特征 PCA (Principle Component Analysis)方法： 进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小。 K-L (Karhunen-Loeve)变换：最优正交线性变换，相应的特征提取方法被称为PCA方法,K-L变换,离散K-L变换：对向量x用确定的完备正交归一向量系uj展开,特征 提取,离散K-L变换的均方误差,用有限项估计x ：,该估计的均方误差：,特征 提取,求解最小均方误差正交基,用Lagrange乘子法：,结论：以相关矩阵R的d个本征向量为基向量来展开x时，其均方误差为：,K-L变换：当取矩阵R的d个最大本征值对应的本征向量来展开x时，其截断均方误差最小。这d个本征向量组成的正交坐标系称作x所在的D维空间的d维K-L变换坐标系， x在K-L坐标系上的展开系数向量y称作x的K-L变换,特征 提取,求解最小均方误差正交基,用Lagrange乘子法：,结论：以相关矩阵R的d个本征向量为基向量来展开x时，其均方误差为：,K-L变换：当取矩阵R的d个最大本征值对应的本征向量来展开x时，其截断均方误差最小。这d个本征向量组成的正交坐标系称作x所在的D维空间的d维K-L变换坐标系， x在K-L坐标系上的展开系数向量y称作x的K-L变换,特征 提取,K-L变换的表示,K-L变换的向量展开表示：,K-L变换的矩阵表示：,特征 提取,K-L变换的性质,y的相关矩阵是对角矩阵：,特征 提取,K-L变换的性质,K-L坐标系把矩阵R对角化，即通过K-L变换消除原有向量x的各分量间的相关性，从而有可能去掉那些带有较少信息的分量以达到降低特征维数的目的,特征 提取,K-L变换的数据压缩图解,取2x1变换矩阵U=u1，则x的K-L变换y为： y = UTx = u1T x = y1 变换的能量损失为,特征 提取,K-L变换的产生矩阵,数据集KN=xi的K-L变换的产生矩阵由数据的二阶统计量决定，即K-L坐标系的基向量为某种基于数据x的二阶统计量的产生矩阵的本征向量 K-L变换的产生矩阵可以有多种选择： x的相关函数矩阵R=ExxT x的协方差矩阵C=E(x-) (x-)T 样本总类内离散度矩阵：,特征 提取,未知类别样本的K-L变换,用总体样本的协方差矩阵C=E(x-) (x-)T 进行K-L变换，K-L坐标系U=u1,u2,.,ud按照C的本征值的下降次序选择 例：设一样本集的协方差矩阵是： 求最优2x1特征提取器U 解答：计算特征值及特征向量V, D=eig(C); 特征值D=24.736, 2.263T,特征向量: 由于12，故最优2x1特征提取器 此时的K-L变换式为：,特征 提取,7.3 离散K-L变换,5.3.1 离散的有限K-L展开 展开式的形式 如果对c种模式类别ii=1,c做离散正交展开，则对每一模式可分别写成：xi= ai，其中矩阵 取决于所选用的正交函数。 对各个模式类别，正交函数都是相同的，但其展开系数向量ai则因类别的不同模式分布而异。 K-L展开式的性质 K-L展开式的根本性质是将随机向量x展开为另一组正交向量j的线性和，且其展开式系数aj（即系数向量a的各个分量）具有不同的性质。 在此条件下，正交向量集j的确定 K-L展开式系数的计算步骤,7.3 离散K-L变换,5.3.2 按K-L展开式选择特征 K-L展开式用于特征选择相当于一种线性变换。 若从K个特征向量中取出m个组成变换矩阵，即 = (1 2 m)，mK 此时，是一个n*m维矩阵，x是n维向量，经过Tx变换，即得到降维为m的新向量。 选取变换矩阵，使得降维后的新向量在最小均方差条件下接近原来的向量x,7.3 离散K-L变换,5.3.2 按K-L展开式选择特征 结论 从K-L展开式的性质和按最小均方差的准则来选择特征，应使Eaj=0。由于Ea=ETx= TEx，故应使Ex=0。基于这一条件，在将整体模式进行K-L变换之前，应先将其均值作为新坐标轴的原点，采用协方差矩阵C或自相关矩阵R来计算特征值。如果Ex0，则只能得到“次最佳”的结果。,7.3 离散K-L变换,5.