《模式识别原理 第三章 判别函数》由会员分享，可在线阅读，更多相关《模式识别原理 第三章 判别函数（47页珍藏版）》请在金锄头文库上搜索。
1、第三章 判别函数第三章 判别函数3.1 线性判别函数 3.2 广义线性判别函数 3.3 分段线性判别函数 3.4 模式空间和权空间 3.5 感知器算法 3.6 采用感知器算法的多类模式的分类 3.7 势函数法 一种确定性的非线性分类算法3.1 线性判别函数3.1.1 用判别函数分类的概念 模式识别系统的主要作用 判别各个模式所属的类别 对一个两类问题的判别，就是将模式x 划分成1和2两类。3.1 线性判别函数3.1.1 用判别函数分类的概念 描述：两类问题的判别函数3.1 线性判别函数3.1.1 用判别函数分类的概念 用判别函数进行模式分类依赖的两个因素 （1）判别函数的几何性质：线性的和非线
2、性的函 数。 线性的是一条直线； 非线性的可以是曲线、折线等； 线性判别函数建立起来比较简单（实际应 用较多）； 非线性判别函数建立起来比较复杂。 （2）判别函数的系数：判别函数的形式确定后， 主要就是确定判别函数的系数问题。 只要被研究的模式是可分的，就能用给定 的模式样本集来确定判别函数的系数。3.1 线性判别函数3.1.2 线性判别函数 n维线性判别函数的一般形式 权向量 增广模式向量 增广权向量 分类问题 两类情况：判别函数d(x) 多类情况：设模式可分成1, 2, M共M类， 则有三种划分方法 多类情况1 多类情况2 多类情况33.1 线性判别函数3.1.2 线性判别函数 分类问题
3、多类情况1 判别函数 图例 例子3.1 线性判别函数3.1.2 线性判别函数 分类问题 多类情况2 判别函数 图例 例子3.1 线性判别函数3.1.2 线性判别函数 分类问题 多类情况3 判别函数 图例 例子3.1 线性判别函数3.1.2 线性判别函数 线性可分 模式分类如可用任一个线性函数来划分， 则这些模式就称为线性可分的，否则就是 非线性可分的。 一旦线性函数的系数wk被确定，这些函数 就可用作模式分类的基础。3.1 线性判别函数3.1.2 线性判别函数 多类情况1和多类情况2的比较 对于M类模式的分类，多类情况1需要M个判别函 数，而多类情况2需要M*(M-1)/2个判别函数，当 M较
4、大时，后者需要更多的判别式（这是多类情 况2的一个缺点）。 采用多类情况1时，每一个判别函数都要把一种 类别的模式与其余M-1种类别的模式分开，而不 是将一种类别的模式仅于另一种类别的模式分开 。 由于一种模式的分布要比M-1种模式的分布更为 聚集，因此多类情况2对模式是线性可分的可能 性比多类情况1更大一些（这是多类情况2的一个 优点）。作业（1） 在一个10类的模式识别问题中，有3类 单独满足多类情况1，其余的类别满足 多类情况2。问该模式识别问题所需判 别函数的最少数目是多少？作业（2） 一个三类问题，其判别函数如下： d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1
5、-x2-1 设这些函数是在多类情况1条件下确定的 ，绘出其判别界面和每一个模式类别的区 域。 设为多类情况2，并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。绘出其判别界 面和多类情况2的区域。 设d1(x), d2(x)和d3(x)是在多类情况3的条件 下确定的，绘出其判别界面和每类的区域 。3.2 广义线性判别函数 出发点 线性判别函数简单，容易实现； 非线性判别函数复杂，不容易实现； 若能将非线性判别函数转换为线性判别函 数，则有利于模式分类的实现。3.2 广义线性判别函数 基本思想 设有一个训练用的模式集x，在模式空间x 中线性不可分，但在
6、模式空间x*中线性可分 ，其中x*的各个分量是x的单值实函数，x* 的维数k高于x的维数n，即若取 x* = (f1(x), f2(x), ., fk(x), kn 则分类界面在x*中是线性的，在x中是非线 性的，此时只要将模式x进行非线性变换， 使之变换后得到维数更高的模式x*，就可以 用线性判别函数来进行分类。 描述3.2 广义线性判别函数 广义线性判别函数的意义 线性的判别函数 fi(x)选用二次多项式函数 x是二维的情况 x是n维的情况 fi(x)选用r次多项式函数， x是n维的情况 例子 d(x)的总项数 说明 d(x)的项数随r和n的增加会迅速增大， 即使原来模式x的维数不高，若采
7、用次数r较高的多项式来 变换，也会使变换后的模式x*的维数很高，给分类带来很 大困难。 实际情况可只取r=2，或只选多项式的一 部分，例如r=2时只取二次项，略去一次项，以减少x*的 维数。3.2 广义线性判别函数 例子：一维样本空间 -二维样本空间 3.3 分段线性判别函数 出发点 线性判别函数在进行分类决策时是最简单有效的 ，但在实际应用中，常常会出现不能用线性判别 函数直接进行分类的情况。 采用广义线性判别函数的概念，可以通过增加维 数来得到线性判别，但维数的大量增加会使在低 维空间里在解析和计算上行得通的方法在高维空 间遇到困难，增加计算的复杂性。 引入分段线性判别函数的判别过程，它比
8、一般的 线性判别函数的错误率小，但又比非线性判别函 数简单。3.3 分段线性判别函数 图例：用判别函数分类 可用一个二次判别函数来分类 也可用一个分段线性判别函数来逼近这个 二次曲线3.3 分段线性判别函数 分段线性判别函数的设计 采用最小距离分类的方法 最小距离分类3.3 分段线性判别函数 图例：分段线性分类设计3.4 模式空间和权空间 分类描述 模式空间 对一个线性方程w1x1+w2x2+w3x3=0，它在 三维空间(x1 x2 x3)中是一个平面方程式， w=(w1 w2 w3)T是方程的系数。 把w向量作为该平面的法线向量，则该线 性方程决定的平面通过原点且与w垂直。3.4 模式空间和
9、权空间 模式空间 若x是二维的增广向量，此时x3=1，则在非增广 的模式空间中即为x1, x2 二维坐标，判别函数 是下列联立方程的解w1x1+w2x2+w3=0x3=1 即为这两个平面相交的直线AB 此时，w =(w1 w2)T为非增广的权向量，它与直线 AB垂直；AB将平面分为正、负两侧，w离开直 线的一侧为正， w射向直线的一侧为负。3.4 模式空间和权空间 模式空间 增广向量决定的平面 非增广向量决定的直线3.4 模式空间和权空间 权空间 若将方程x1w1+x2w2+w3=0绘在权向量w=(w1 w2 w3)T的三维空间中，则x=(x1 x2 1)T为方程的系数 。 若以x向量作为法线
10、向量，则该线性方程所决定 的平面为通过原点且与法线向量垂直的平面，它 同样将权空间划分为正、负两边。 在系数x不变的条件下，若w值落在法线向量离开 平面的一边，则wTx0，若w值落在法线向量射 向平面的一边，则wTx 0，或当xk+1属于2时 ，Kk(xk+1)0，则积累位势不做任何修改就可用 作判别函数。 由于一个模式样本的错误分类可造成积累位 势在训练时的变化，因此势函数算法提供了 确定1和2两类判别函数的迭代过程。 判别函数表达式3.7 势函数法 一种确 定性的非线性分类方法3.7.2 势函数的选择 选择势函数的条件：一般来说，若两 个n维向量x和xk的函数K(x, xk)同时满足下 列
11、三个条件，则可作为势函数。 K(x, xk)= K(xk, x)，并且当且仅当x=xk时达到最大 值； 当向量x与xk的距离趋于无穷时，K(x, xk)趋于零 ； K(x, xk)是光滑函数，且是x与xk之间距离的单调 下降函数。3.7 势函数法 一种确 定性的非线性分类方法3.7.2 势函数的选择 构成势函数的两种方式 第一类势函数 第二类势函数3.7 势函数法 一种确 定性的非线性分类方法3.7.2 势函数的选择 例13.7 势函数法 一种确 定性的非线性分类方法3.7.2 势函数的选择 例23.7 势函数法 一种确 定性的非线性分类方法3.7.2 势函数的选择 讨论 用第二类势函数，当训练样本维数和 数目都较高时，需要计算和存储的指 数项较多。 正因为势函数由许多新项组成，因此 有很强的分类能力。作业（1） 用二次埃尔米特多项式的势函数算法 求解以下模式的分类问题1: (0 1)T, (0 -1)T 2: (1 0)T, (-1 0)T作业（2） 用下列势函数求解以下模式的分类问题1: (0 1)T, (0 -1)T 2: (1 0)T, (-1 0)T
