特征提取与选择.ppt

第七章特征提取与选择 特征形成特征提取特征选择 目的 7 1概述 直接选择法分支定界法 用回归建模技术确定相关特征等方法 变换法在使判据J max的目标下 对n个原始特征进行变换降维 即对原n维特征空间进行坐标变换 然后再取子空间 主要方法有 基于可分性判据的特征选择基于误判概率的特征选择离散K L变换法 DKLT 基于决策界的特征选择等方法 7 2类别可分性判据 ClassSeparabilityMeasures 准则 类别可分性判据 刻划特征对分类的贡献 构造的可分性判据Jij应满足下列要求 1 与误分概率P e 或误分概率的上界 下界 有单调关系 Jij最大值时 P e 最小 2 当特征相互独立时 判据有可加性 即 式中xk 是对象不同种类特征的测量值 Jij 表示使用括号中特征时第i类与第j类的可分性判据函数 3 判据具有 距离 的某些特性 Jij 0 当i j时Jij 0 当i j时Jij Jji 4 Jij对特征数目单调不减 即加入新的特征后 判据值不减所构造的可分性判据并不一定要求同时具有上述四个性质 7 2 1基于几何距离的可分性判据 可以用距离或离差测度 散度 来构造类别可分性判据 一 点与点的距离在n维特征空间中 点与点之间的欧氏距离为 二 点到点集的距离点到点集之间的均方欧氏距离为 三 类内及总体的均值矢量 设N个模式分属c类 则各类的均值矢量分别为所有各类模式的总体均值矢量为式中Pi为相应类的先验概率 当用统计量代替先验概率时 有 四 类内距离 类内均方欧氏距离为类内均方距离也可定义为 五 类内离差 散布 矩阵 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 对一切0 s 1 Jc 0 2 对一切0 s 1 3 当参数s和 1 s 互调时 才有对称性 即 比JB更广义的判据 二 Chernoff判据 JC 性质 4 当各分量x1 x2 xn相互独立时 5 当各分量x1 x2 xn相互独立时 6 最小误分概率 JC不具有三点距离不等式的性质 三 散度JD Divergence 对 1类的平均可分性信息为对 2类的平均可分性信息为对于 1和 2两类总的平均可分性信息称为散度 其定义为两类平均可分性信息之和 即 类别可分性判据小结 几何可分性判据类概率密度可分性判据 一 Bhattacharyya判据 JB 二 Chernoff判据 JC 三 散度JD 第七章特征提取与选择 7 7特征选择中的直接挑选法 特征的选择可以在原坐标系中依据某些原则直接选择特征 从n个特征中挑选出d个使其Jd最大 7 7 1次优搜索法7 7 2最优搜索法 7 7 1次优搜索法 一 单独最优的特征选择 基本思路 计算各特征单独使用时的判据值J并以递减排序 选取前d个分类效果最好的特征 一般地讲 即使各特征是统计独立的 这种方法选出的个特征也不一定是最优的特征组合 只有可分性判据J是可分的 即 这种方法才能选出一组最优特征 二 增添特征法 7 7 1次优搜索法 SequentialForwardSelection 三 剔减特征法 7 7 1次优搜索法 设已剔除了k个特征 剩下的特征组记为 将中的各特征xj j 1 2 n k 分别逐个剔除 并同时计算值 若 7 7 1次优搜索法 四 增l减r法 l r法 6选2的特征选择问题 a 搜索树 b 搜索回溯示意图 7 7 2最优搜索法 BAB算法 s 0s 1s 2s 3s 4 树的每个节点表示一种特征组合 树的每一级各节点表示从其父节点的特征组合中去掉一个特征后的特征组合 其标号k表示去掉的特征是xk 7 7 2最优搜索法 BAB算法 由于每一级只舍弃一个特征 因此整个搜索树除根节点0级外 还需要n d级 即全树有n d级 例如 6个特征中选2个 整个搜索树有4级 第n d级是叶节点 共有Cnd个叶节点 BAB算法 7 7 2最优搜索法 表示特征数目为l的特征集合 表示舍弃s个特征后余下的特征集合 表示当前节点的子节点数 表示集合 s中元素的数目 表示第s级当前节点上用来作为下一级可舍弃特征的特征集合 由于从根节点要经历n d级才能到达叶节点 s级某节点后继的每一个子节点分别舍弃 s中互不相同的一个特征 从而考虑在s 1级可以舍弃的特征方案数 即子节点数 qs时 必须使这一级舍弃了特征后的Xs 1还剩 n d s 1 个特征 除了从树的纵向上每一级舍弃一个特征 实际上从树的横向上 一个分支也轮换舍弃一个特征 因此后继子节点数qs rs n d s 1 BAB算法 7 7 2最优搜索法 BAB算法 7 7 2最优搜索法 rs BAB算法 7 7 2最优搜索法 BAB算法 7 7 2最优搜索法 BAB算法 7 7 2最优搜索法 目标 找出叶节点Lk 使其对应的d个特征的判据J的值最大 即 注意到每个节点 包括非叶节点 都可以计算相应的J值 由于判据J值具有单调性 即 该不等式表明 任何节点的J值均不小于其任何后继节点 子节点 的J值 BAB算法 7 7 2最优搜索法 搜索顺序 从上至下 从右至左 四个步骤 1 向下搜索2 更新界值3 向上回溯4 停止回溯再向下搜索 BAB算法 7 7 2最优搜索法 向下搜索 初始 置界值B 0从树的根节点沿最右边的一支自上而下搜索 对于一个节点 它的子树最右边的一支总是无分支的 此时可直接到达叶节点 计算该叶节点的J值 并更新界值B 即图中的虚线可省略而得到最小搜索树 BAB算法 7 7 2最优搜索法 最小搜索树 BAB算法 7 7 2最优搜索法 向上回溯和停止回溯 回溯到有分支的那个节点则停止回溯转入向下搜索 例如回溯到qs 1 1的那个节点 则转入与当前节点左邻的s深度的那个节点 使该节点成为当前节点 按前面的方法沿它最右边的子树继续搜索 在搜索过程中先要判该节点的J值是否比B值大 若不大于B值 该节点以下的各子节点J值均不会比B大 故无需对该子树继续进行搜索 BAB算法 7 7 2最优搜索法 如果搜索到叶节点 且该叶节点代表的特征的可分性判据J B 则更新界值 即B J 否则不更新界值 到达叶节点后 要向上回溯 重复上述过程 直到J B为止 而对应当前 最大 界值B的叶节点对应的d个特征组合就是所求的最优的选择 BAB算法效率高的原因 1 在构造搜索树时 同一父节点的各子树