模式识别理论及应用.ppt
,武汉大学电子信息学院,IPL,第六章 模式特征的选择与提取,模式识别理论及应用Pattern Recognition-Methods and Application,内容目录,IPL,第六章 模式特征的选择与提取,6.1 引言,3,2,4,5,6.2 类别可分离性判据,6.3 特征提取与K-L变换,6.4 特征的选择,6.5 讨论,1,第六章 模式特征的选择与提取,3,6.1 引言,特征的选择与提取是模式识别中重要而困难的一个环节：分析各种特征的有效性并选出最有代表性的特征是模式识别的关键一步降低特征维数在很多情况下是有效设计分类器的重要课题三大类特征：物理、结构和数学特征物理和结构特征：易于为人的直觉感知，但有时难于定量描述，因而不易用于机器判别数学特征：易于用机器定量描述和判别，如基于统计的特征,第六章 模式特征的选择与提取,4,特征的形成,特征形成(acquisition)：信号获取或测量原始测量原始特征实例：数字图象中的各像素灰度值人体的各种生理指标原始特征分析：原始测量不能反映对象本质高维原始特征不利于分类器设计：计算量大，冗余，样本分布十分稀疏,引言,第六章 模式特征的选择与提取,5,特征的选择与提取,两类提取有效信息、压缩特征空间的方法：特征提取和特征选择特征提取(extraction)：用映射（或变换）的方法把原始特征变换为较少的新特征特征选择(selection)：从原始特征中挑选出一些最有代表性，分类性能最好的特征特征的选择与提取与具体问题有很大关系，目前没有理论能给出对任何问题都有效的特征选择与提取方法,引言,第六章 模式特征的选择与提取,6,特征的选择与提取举例,细胞自动识别：原始测量：（正常与异常）细胞的数字图像原始特征（特征的形成，找到一组代表细胞性质的特征）：细胞面积，胞核面积，形状系数，光密度，核内纹理，和浆比压缩特征：原始特征的维数仍很高，需压缩以便于分类特征选择：挑选最有分类信息的特征特征提取：数学变换傅立叶变换或小波变换用PCA方法作特征压缩,引言,第六章 模式特征的选择与提取,7,6.2 类别可分离性判据,类别可分离性判据：衡量不同特征及其组合对分类是否有效的定量准则理想准则：某组特征使分类器错误概率最小实际的类别可分离性判据应满足的条件：度量特性：与错误率有单调关系当特征独立时有可加性：单调性：常见类别可分离性判据：基于距离、概率分布、熵函数,第六章 模式特征的选择与提取,8,基于距离的可分性判据,类间可分性:=所有样本间的平均距离：,可分性判据,(8-1),squared Euclidian,(8-5),类内平均距离,类间距离,(8-6),第六章 模式特征的选择与提取,9,基于距离的可分性判据矩阵形式,可分性判据,基于距离的准则概念直观，计算方便，但与错误率没有直接联系,样本类间离散度矩阵,样本类内离散度矩阵,类间可分离性判据,第六章 模式特征的选择与提取,10,基于概率的可分性判据,基于概率的可分性判据：用概率密度函数间的距离来度量,可分性判据,散度：,第六章 模式特征的选择与提取,11,正态分布的散度,可分性判据,Mahalanobis,第六章 模式特征的选择与提取,12,基于熵函数的可分性判据,熵函数：,可分性判据,Shannon熵：,平方熵：,熵函数期望表征类别的分离程度：,第六章 模式特征的选择与提取,13,类别可分离性判据应用举例,图像分割：Otsu灰度图像阈值算法(Otsu thresholding)图像有L阶灰度，ni是灰度为i的像素数，图像总像素数 N=n1+n2+nL灰度为i的像素概率：pi=ni/N类间方差：,可分性判据,第六章 模式特征的选择与提取,14,Otsu thresholding,灰度图像阈值:,可分性判据,Otsu灰度图像二值化算法演示及程序分析:,第六章 模式特征的选择与提取,15,6.3 特征提取与K-L变换,特征提取：用映射（或变换）的方法把原始特征变换为较少的新特征PCA(Principle Component Analysis)方法：进行特征降维变换，不能完全地表示原有的对象，能量总会有损失。希望找到一种能量最为集中的的变换方法使损失最小K-L(Karhunen-Loeve)变换：最优正交线性变换，相应的特征提取方法被称为PCA方法,第六章 模式特征的选择与提取,16,K-L变换,离散K-L变换：对向量x用确定的完备正交归一向量系uj展开,特征提取,第六章 模式特征的选择与提取,17,离散K-L变换的均方误差,用有限项估计x：,特征提取,该估计的均方误差：,第六章 模式特征的选择与提取,18,求解最小均方误差正交基,用Lagrange乘子法：,特征提取,结论：以相关矩阵R的d个本征向量为基向量来展开x时，其均方误差为：,K-L变换：当取矩阵R的d个最大本征值对应的本征向量来展开x时，其截断均方误差最小。这d个本征向量组成的正交坐标系称作x所在的D维空间的d维K-L变换坐标系，x在K-L坐标系上的展开系数向量y称作x的K-L变换,第六章 模式特征的选择与提取,19,K-L变换的表示,K-L变换的向量展开表示：,特征提取,K-L变换的矩阵表示：,第六章 模式特征的选择与提取,20,K-L变换的性质,y的相关矩阵是对角矩阵：,特征提取,第六章 模式特征的选择与提取,21,K-L变换的性质,特征提取,K-L坐标系把矩阵R对角化，即通过K-L变换消除原有向量x的各分量间的相关性，从而有可能去掉那些带有较少信息的分量以达到降低特征维数的目的,第六章 模式特征的选择与提取,22,K-L变换图解,二次曲线方程,标准二次曲线方程,特征提取,第六章 模式特征的选择与提取,23,K-L变换的数据压缩图解,取2x1变换矩阵U=u1，则x的K-L变换y为：y=UTx=u1T x=y1变换的能量损失为,特征提取,第六章 模式特征的选择与提取,24,K-L变换的产生矩阵,数据集KN=xi的K-L变换的产生矩阵由数据的二阶统计量决定，即K-L坐标系的基向量为某种基于数据x的二阶统计量的产生矩阵的本征向量K-L变换的产生矩阵可以有多种选择：x的相关函数矩阵R=ExxTx的协方差矩阵C=E(x-)(x-)T样本总类内离散度矩阵：,特征提取,第六章 模式特征的选择与提取,25,未知类别样本的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变换式为：,特征提取,第六章 模式特征的选择与提取,26,6.4 特征的选择,特征选择:=从原始特征中挑选出一些最有代表性、分类性能最好的特征进行分类从D个特征中选取d个,共 种组合。若不限定特征选择个数，则共2D种组合 典型的组合优化问题特征选择的方法大体可分两大类：Filter方法：根据独立于分类器的指标J来评价所选择的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作为最优特征子集。不考虑所使用的学习算法。Wrapper方法：将特征选择和分类器结合在一起，在学习过程中表现优异的的特征子集会被选中。,第六章 模式特征的选择与提取,27,经典特征选择算法,许多特征选择算法力求解决搜索问题，经典算法有：分支定界法单独最优特征组合法顺序后退法顺序前进法模拟退火法Tabu搜索法遗传算法,特征选择,第六章 模式特征的选择与提取,28,单独最优特征组合,计算各特征单独使用时的可分性判据J并加以排队，取前d个作为选择结果不一定是最优结果当可分性判据对各特征具有(广义)可加性，该方法可以选出一组最优的特征来，例：各类具有正态分布各特征统计独立可分性判据基于Mahalanobis距离,特征选择,第六章 模式特征的选择与提取,29,顺序后退法,该方法根据特征子集的分类表现来选择特征搜索特征子集：从全体特征开始，每次剔除一个特征，使得所保留的特征集合有最大的分类识别率依次迭代，直至识别率开始下降为止用“leave-one-out”方法估计平均识别率：用N-1个样本判断余下一个的类别，N次取平均,特征选择,第六章 模式特征的选择与提取,30,6.5 讨论,特征的选择与提取是模式识别中重要而困难的一步模式识别的第一步：分析各种特征的有效性并选出最有代表性的特征降低特征维数在很多情况下是有效设计分类器的重要课题三大类特征：物理、结构和数学特征物理和结构特征：易于为人的直觉感知，但难于定量描述，因而不易用机器判别数学特征：易于用机器定量描述和判别,第六章 模式特征的选择与提取,31,习题,1.试推导(8-6)式，即：,2.试由(8-1)式推导(8-5)式，即：,3.习题8.1,9.习题9.1,
