《[信息与通信]第三章 线性与非线性判别函数》由会员分享，可在线阅读，更多相关《[信息与通信]第三章 线性与非线性判别函数（53页珍藏版）》请在金锄头文库上搜索。
1、第三章 线性与非线性判别函数模式识别 Pattern Recognition武汉理工大学信息工程学院内容目 录第三章63.3 Fisher线性判别33.5 多类问题3.4 分段线性判别函数 53.1 感知准则函数143.2 最小平方误差准则模式识别3.6 讨论23.1 感知准则函数u感知准则函数是五十年代由Rosenblatt提出的 一种自学习判别函数生成方法，由于 Rosenblatt企图将其用于脑模型感知器 (Perceptron)，因此被称为感知准则函数。其特点 是随意确定的判别函数初始值，在对样本分类训 练过程中逐步修正直至最终确定。3第三章 线性与非线性判别函数知识点非参数分类方法的
2、基本原理 有监督学习方法近邻法改进的近邻法Fisher准则线性分析器感知准则函数线性分析器支持向量机的基本原理线性分析器非线性分析器的扩 展分段线性多层感知器特性映射方法实现 非线性方法分析器4第三章 线性与非线性判别函数基本概念u感知器：Perceptron，Rosenblatt， 50d/20thcu线性可分性：训练样本集中的两类样本在特征空 间可以用一个线性分界面正确无误地分开。在线 性可分条件下，对合适的(广义)权向量a应有：u规范化样本向量 ：将第二类样本取其反向向量 感知器感知器 准则准则5第三章 线性与非线性判别函数解向量与解区感知器感知器 准则准则6第三章 线性与非线性判别函数
3、直接确定判别函数u基于样本的直接确定判别函数方法： 设定判别函数形式，用样本集确定参数。 使用准则函数，表达分类器应满足的要求。 这些准则的“最优”并不一定与错误率最小相一 致：次优分类器。 实例：正态分布最小错误率贝叶斯分类器在 特殊情况下，是线性判别函数g(x)=wTx（ 决策面是超平面），能否基于样本直接确定 w?引言引言训练样本集训练样本集决策规则：决策规则： 判别函数判别函数 决策面方程决策面方程选择最佳准则7第三章 线性与非线性判别函数线性判别函数ud维空间中的线性判别函数的一般形式 ：ux是样本向量，即样本在d维特征空间中的 描述， w是权向量，w0是一个常数(阈值 权)。引言引
4、言8第三章 线性与非线性判别函数两类问题的分类决策规则引言引言9第三章 线性与非线性判别函数线性判别函数的几何意义u决策面(decision boundary)H方程：g(x)=0u向量w是决策面H的法向量ug(x)是点x到决策面H的距离的一种代数度量引言引言x1x2wxxprH: g=0R1: g0R2: g0 对样本y错误分类，则有：aTy0。当然，修改后的a(k+1)还可以使某些y出现 a(k+1)Ty 0中W的求解改成对满足XW=b 的求解。MSEMSE 准则准则21第三章 线性与非线性判别函数u引入余量(目标向量) b=b1, b2, , bNT ， bi任意给定正常数， aTyi
5、= bi 0uN个线性方程的的矩阵表示：最小平方误差准则u规范化增广样本向量yi，增广权向量a，正确分类要求： aTyi0, i=1,Nu线性分类器设计求一组N个线性不等式的解u样本集增广矩阵Y及一组N个线性不等式的的矩阵表示：MSEMSE 准则准则22第三章 线性与非线性判别函数平方误差准则函数u定义误差向量 e=Ya-b：u定义平方误差准则函数Js(a):MSEMSE 准则准则u最小二乘近似解（MSE解）：MSE方法的思想：对每个样本，设定一个“理想”的 判别函数输出值，以最小平方误差为准则求最优权向 量23第三章 线性与非线性判别函数MSE准则函数的伪逆解MSEMSE 准则准则Y Y的的
6、 伪逆矩阵伪逆矩阵24第三章 线性与非线性判别函数MSE方法与Fisher方法的关系u与Fisher方法的关系：当MSEMSE 准则准则N1个N2个MSEMSE解等价于解等价于FisherFisher解解25第三章 线性与非线性判别函数MSE方法与Bayes方法的关 系MSEMSE 准则准则 当N，b=uN= 1,1, , 1T 时，则它以最小 均方误差逼近Bayes判别函数：26第三章 线性与非线性判别函数MSE方法的迭代解ua*=Y+b, Y+=(YTY)-1YT，计算量大u实际中常用梯度下降法：MSEMSE 准则准则批量样本批量样本 修正法修正法单样本修单样本修 正法正法27第三章 线性
7、与非线性判别函数例3.1：已知两类的训练样本： ， ，试用最小均方误差算法求解向量解：训练样本的增广矩阵： 求X的伪逆矩阵： MSE方法的例解MSEMSE 准则准则28第三章 线性与非线性判别函数令 则误差向量： e1的各分量均为0，则w*就是所求的解向量因此决策面方程： MSE方法的例解MSEMSE 准则准则29第三章 线性与非线性判别函数3.3 Fisher线性判别Fisher线性判别函数是研究这类判别函数中最有影响 的方法之一。对线性判别函数的研究就是从R.A.Fisher在 1936年发表的论文开始的。如上所述，设计线 性分类器首先要确定准则函数，然 后再利用训练样 本集确定该分类器的
8、参数，以求使所确定 的准则达到最佳。在使用线性分类器时，样本的分类由其 判别函数值决定，而每个样本的判别函数值是其各分量的 线性加权和再加上一个阈值wn+1。如果我们只考虑各分量 的线性加权和，则它是各样本向量与向量W的向量点积。 如果向量W的幅度为单位长度，则线性加权和又可看作各 样本向量在向量W上的投影。显然样本集中向量投影的分 布情况与所选择的W向量有关。FisherFisher 判别判别30第三章 线性与非线性判别函数其中用红红点及蓝蓝点分别别表示不同类别类别 的样样本。显显然对对 向量 w1的投影能使这这两类类有明显显可分开的区域，而对对向量w2的投 影，则则使两类类数据部分交迭在一
9、起，无法找到一个能将它们们 截然分开的界面。Fisher准则则的基本原理，就是要找到一个 最合适的投影轴轴，使两类样类样 本在该轴该轴 上投影的交迭部分最少 ，从而使分类类效果为为最佳。Fisher线性判别w2x2x1w1FisherFisher 判别判别31第三章 线性与非线性判别函数Fisher线性判别u线性判别函数y=g(x)=wTx: 样本向量x各分量的线性加权 样本向量x与权向量w的向量点积 如果| w |=1，则视作向量x在向量w上的投 影 uFisher准则的基本原理：找到一个最合适的 投影轴，使两类样本在该轴上投影之间的距 离尽可能远，而每一类样本的投影尽可能紧 凑，从而使分类
10、效果为最佳。FisherFisher 判别判别32第三章 线性与非线性判别函数Fisher线性判别图例FisherFisher 判别判别x1x2w1H: g=0w2 FisherFisher准则的描述：用投影后数据的统计性质准则的描述：用投影后数据的统计性质 均值和离散度的函数作为判别优劣的标准。均值和离散度的函数作为判别优劣的标准。33第三章 线性与非线性判别函数d维空间样本分布的描述量FisherFisher 判别判别u各类样本均值向量miu样本类内离散度矩阵Si与总类内离散度矩阵Sw u样本类间离散度矩阵Sb：离散度矩阵在形式上与协方差矩阵很相似，但协 方差矩阵是一种期望值，而离散矩阵只
11、是表示有 限个样本在空间分布的离散程度34第三章 线性与非线性判别函数一维Y空间样本分布的描述量FisherFisher 判别判别u各类样本均值u样本类内离散度和总类内离散度u样本类间离散度 以上定义描述d维空间样本点到一向量投影的分 散情况，因此也就是对某向量w的投影在w上的 分布。样本离散度的定义与随机变量方差相类似 35第三章 线性与非线性判别函数样本与其投影统计量间的关系FisherFisher 判别判别u样本x与其投影y的统计量之间的关系：36第三章 线性与非线性判别函数样本与其投影统计量间的关系FisherFisher 判别判别37第三章 线性与非线性判别函数Fisher准则函数F
12、isherFisher 判别判别u评价投影方向w的原则，使原样本向量在 该方向上的投影能兼顾类间分布尽可能分 开，类内尽可能密集的要求uFisher准则函数的定义：uFisher最佳投影方向的求解38第三章 线性与非线性判别函数Fisher最佳投影方向的求解FisherFisher 判别判别u采用拉格朗日乘子算法解决 m1-m2是一向量，对与(m1-m2)平行的向量投影可使两 均值点的距离最远。但是如从使类间分得较开，同时又使 类内密集程度较高这样一个综合指标来看，则需根据两类 样本的分布离散程度对投影方向作相应的调整，这就体现 在对m1-m2 向量按Sw-1作一线性变换，从而使Fisher准
13、 则函数达到极值点39第三章 线性与非线性判别函数判别函数的确定u前面讨论了使Fisher准则函数极大的d维 向量w*的计算方法，判别函数中的另一 项w0（阈值）可采用以下几种方法确定： u分类规则:FisherFisher 判别判别40第三章 线性与非线性判别函数Fisher公式的推导FisherFisher 判别判别41第三章 线性与非线性判别函数多类问题u两类别问题可以推广到多类别问题 i/i 法：将C类别问题化为(C-1)个两类（第i类与 所有非i类）问题，按两类问题确定其判别函数与决策 面方程 i/j 法：将C类中的每两类别单独设计其线性判别 函数，因此总共有C(C-1)/2个线性判
14、别函数 R1R3R21非非12非非2R1R3R212133242第三章 线性与非线性判别函数多类线性判别函数u将特征空间确实划分为c个决策域，共有c 个判别函数多类多类 问题问题u决策规则 ：u决策域的边界由相邻决策域的判别函数共同决定 ，此时应有gi(x)=gj(x) u线性分类器的决策面是凸的，决策区域是单连通 的u多类分类器的分界面是分段线性的43第三章 线性与非线性判别函数多类线性决策面图例R1R3R2g g1 1gg2 2g g1 1gg3 3g g3 3gg1 1 g g3 3gg2 2g g2 2gg3 3g g2 2gg1 1R1R3R2R5R4多类多类 问题问题44第三章 线
15、性与非线性判别函数决策树简介u决策树：一种多极分 类器，它采用分级的 形式，综合用多个决 策规则，逐步把复杂 的多类别分类问题转 化为若干个简单的分 类问题来解决多类多类 问题问题n1n2n3n4n5t1t2t3t4t5t6t745第三章 线性与非线性判别函数二叉决策树u二叉决策树：除叶节 点外，决策树的每个 节点ni都有且只有两 个子节点nil和nir。二 叉决策树把复杂的多 类别分类问题转化为 多极两类分类问题来 解决。在每个节点ni ，都把样本集分成两 个子集。每个子集可 能仍包含多类别的样 本，继续分直至仅包 含单类别样本的叶节 点多类多类 问题问题n1n2n3n4t1t2t5x25x
16、12x34x2212323 t3t446第三章 线性与非线性判别函数3.4 分段线性判别函数 u有些复杂模式识别问 题不是线性可分的， 需使用非线性的分类 方法u分段线性判别函数： 一种特殊的非线性判 别函数，它的决策面 是若干超平面u树分类器的各节点上 采用线性判别规则， 即构成分段线性分类 器R1R3R2IIIIIII IIIIII I: : 线性判别线性判别 IIII：分段：分段线性判别线性判别 III: III: 二次判别二次判别47第三章 线性与非线性判别函数基于距离的分段线性判别函 数 u最小距离分类器：把各类别样本特征的均值向量作为各 类的代表点(prototype) ，根据待识样本到各类别代表点 的最小距离判别其类别。决策面是两类别均值连线的垂 直平分面u分段线性距离分类器：将各类别划分成相对密集的子类 ，每个子类以它们的均值作为代表点，然后按最小距离 分
