第六章模式特征的选择与提取PPT讲稿.ppt

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