特征提取与选择幻灯片.ppt

特征提取与选择特征提取与选择第1页，共35页，编辑于2022年，星期日n n直接选择法直接选择法直接选择法直接选择法分支定界法；分支定界法；用回归建模技术确定相关特征等方法。用回归建模技术确定相关特征等方法。n n变换变换法法法法在使判据在使判据在使判据在使判据Jmax的目标下，对的目标下，对的目标下，对的目标下，对n n n n个原始特征进行变换个原始特征进行变换个原始特征进行变换个原始特征进行变换降维降维降维降维，即对原即对原即对原即对原n n n n维特征空间进行坐标变换，然后再取子空间。维特征空间进行坐标变换，然后再取子空间。主要方法有：主要方法有：基于可分性判据的特征选择基于可分性判据的特征选择基于误判概率的特征选择基于误判概率的特征选择离离散散K-L变换法变换法(DKLT)基于决策界的特征选择等方法。基于决策界的特征选择等方法。第2页，共35页，编辑于2022年，星期日7.2 类别可分性判据(Class Separability Measures)n准则准则类别可分性判据类别可分性判据:刻划特征对分类的贡献。刻划特征对分类的贡献。n构造的可分性判据构造的可分性判据Jij应满足下列要求：应满足下列要求：(1)与误分概率与误分概率P(e)(或误分概率的上界、下界或误分概率的上界、下界)有有单调关系，单调关系，Jij最大值时，最大值时，P(e)最小。最小。(2)当特征相互独立时，判据有当特征相互独立时，判据有可加性可加性，即，即式中式中xk，是对象不同种类特征，是对象不同种类特征的测量值，的测量值，Jij()表示使用括表示使用括号中特征时第号中特征时第i类与第类与第j类的可类的可分性判据函数。分性判据函数。第3页，共35页，编辑于2022年，星期日(3)判据具有判据具有“距离距离”的某些特性：的某些特性：Jij0，当当ij 时时 Jij=0，当当i=j 时时 Jij=Jji(4)Jij ij 对特征数目单调不减对特征数目单调不减，即加入新的，即加入新的特征后，判据值不减特征后，判据值不减 所构造的可分性判据并不一定要求同时具所构造的可分性判据并不一定要求同时具有上述四个性质。有上述四个性质。第4页，共35页，编辑于2022年，星期日7.2.1 基于几何距离的可分性判据基于几何距离的可分性判据 可以用距离或离差测度可以用距离或离差测度(散度散度)来构造类别可分性判来构造类别可分性判据据(一一)点与点的距离点与点的距离在在n维特征空间中，点维特征空间中，点 与与 点之间的欧氏距离为点之间的欧氏距离为(二二)点到点集的距离点到点集的距离点点 到点集到点集 之间的均方欧氏距之间的均方欧氏距离为离为 第5页，共35页，编辑于2022年，星期日(三三)类内及总体的均值矢量类内及总体的均值矢量 设设N个模式分属个模式分属c类类,则各类的均值矢量分别为则各类的均值矢量分别为所有各类模式的总体均值矢量为所有各类模式的总体均值矢量为式中式中Pi为相应类的先验概率。为相应类的先验概率。当用统计量代替先验概率时，有当用统计量代替先验概率时，有 第6页，共35页，编辑于2022年，星期日(四四)类内距离类内距离 n类内均方欧氏距离为类内均方欧氏距离为类内均方距离也可定义为类内均方距离也可定义为(五五)类内离差（散布）矩阵类内离差（散布）矩阵(Scatter)类内离差矩阵定义为类内离差矩阵定义为类内离差矩阵类内离差矩阵SWi的迹等于类内的均方欧氏距离，即的迹等于类内的均方欧氏距离，即类内离差矩阵表示各类模式在类的均值矢量周围的散布类内离差矩阵表示各类模式在类的均值矢量周围的散布情况。情况。第7页，共35页，编辑于2022年，星期日(六六)两类之间的距离两类之间的距离 当式中的距离取欧氏距离时当式中的距离取欧氏距离时,有有(七七)各类模式之间的总的均方距离各类模式之间的总的均方距离 当取欧氏距离时当取欧氏距离时 第8页，共35页，编辑于2022年，星期日(八八)多类情况下总的类内、类间及总体离差（散布）矩阵多类情况下总的类内、类间及总体离差（散布）矩阵 总的类内离差矩阵定义为总的类内离差矩阵定义为总的类间离差矩阵定义为总的类间离差矩阵定义为总体离差矩阵为总体离差矩阵为 易导出易导出 第9页，共35页，编辑于2022年，星期日可分性判据可分性判据 （类内紧，类间开（类内紧，类间开）可以证明可以证明J1、J2与与J4在任何非奇异线性变换下是不在任何非奇异线性变换下是不变的变的，J3与坐标系有关。与坐标系有关。第10页，共35页，编辑于2022年，星期日7.2.2 基于类的概率密度函数的可分性判据基于类的概率密度函数的可分性判据 用两类概密函数的用两类概密函数的重迭程度重迭程度来度量可分性，构造基于类来度量可分性，构造基于类概密的可分性判据概密的可分性判据Jp，它，它应满足：应满足：(1)Jp 0；(2)当两类密度函数完全不重迭时，当两类密度函数完全不重迭时，Jp=max；(3)当两类密度函数完全重合时，当两类密度函数完全重合时，Jp=0；(4)相对两个概密具有相对两个概密具有“对称性对称性”。(a)(b)第11页，共35页，编辑于2022年，星期日(一一)Bhattacharyya判据判据(JB)在最小误分概率准则下，在最小误分概率准则下，误分概率误分概率(受相关定义与应用的启发，构造受相关定义与应用的启发，构造B-判据判据)第12页，共35页，编辑于2022年，星期日(二二)Chernoff判据判据(JC)性质：性质：(1)(1)对一切对一切0s10s1，JcJc 0 0；(2)(2)对一切对一切0s10s1 1 的那个节点，则转入与当前节点左的那个节点，则转入与当前节点左邻的邻的s s深度的那个节点，使该节点成为当前节点，按前深度的那个节点，使该节点成为当前节点，按前面的方法沿它最右边的子树继续搜索。面的方法沿它最右边的子树继续搜索。在搜索过程中先要判该节点的在搜索过程中先要判该节点的J J值是否比值是否比B B值大。若不大值大。若不大于于B B值，该节点以下的各子节点值，该节点以下的各子节点J J值均不会比值均不会比B B大，大，故无需故无需对该子树继续进行搜索对该子树继续进行搜索。第33页，共35页，编辑于2022年，星期日BAB算法算法7.7.2 7.7.2 最优搜索法最优搜索法如果搜索到叶节点，且该如果搜索到叶节点，且该叶节点代表的特征的可分叶节点代表的特征的可分性判据性判据JBJB，则更新界值，则更新界值，即即B=JB=J；否则不更新界值。；否则不更新界值。到达叶节点后，要向上回溯。重复上述过程，直到到达叶节点后，要向上回溯。重复上述过程，直到J J B B为止。而对应当前（最大）界值为止。而对应当前（最大）界值B B的叶节点对应的的叶节点对应的d d个个特征组合就是所求的最优的选择。特征组合就是所求的最优的选择。第34页，共35页，编辑于2022年，星期日BABBAB算法效率高的原因算法效率高的原因：(1)(1)在构造搜索树时，同一父节点的各子树的右边的边在构造搜索树时，同一父节点的各子树的右边的边要比左边的少，即树的结构右边比左边简单；要比左边的少，即树的结构右边比左边简单；(2)(2)在同一级中按最小的在同一级中按最小的J J值从左到右挑选舍弃的特征，值从左到右挑选舍弃的特征，即节点的即节点的J J值是值是左小右大左小右大，而搜索过程是从右至左进，而搜索过程是从右至左进行的；行的；(3)(3)因因J J的的单调性单调性，若树上某节点，若树上某节点A A的可分性判据值的可分性判据值 J JA A B B ，则则A A子树上各节点的子树上各节点的J J值都不会大于值都不会大于B B，因此不需要，因此不需要搜索搜索A A子树。子树。从上可知，有很多特征组合不需计算仍能求得全局最从上可知，有很多特征组合不需计算仍能求得全局最优解。优解。第35页，共35页，编辑于2022年，星期日