特征提取与选择.ppt

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