模式识别原理幻灯片第3章判别函数及几何分类法

《模式识别原理幻灯片第3章判别函数及几何分类法》由会员分享，可在线阅读，更多相关《模式识别原理幻灯片第3章判别函数及几何分类法（114页珍藏版）》请在金锄头文库上搜索。

1、第3章 判别函数及几何分类法,第3章 判别函数及几何分类法,3.1 判别函数 3.2 线性判别函数 3.3 广义线性判别函数 3.4 线性判别函数的几何性质 3.5 感知器算法 3.6 梯度法 3.7 最小平方误差算法 3.8 非线性判别函数,3.1 判别函数,聚类分析法（第二章）,判决函数法,几何分类法 确定性事件分类 （第三章）,概率分类法 随机事件分类 （第四章）,线性判决函数法,统 计 决 策 方 法,非线性判决函数法,复习与引申：,若分属于1，2的两类模式可用一方程d(X) =0来 划分，那么称d(X) 为判别函数，或称判决函数、 决策函数。,3.1 判别函数(discriminan

2、t function),直接用来对模式进行分类的准则函数。,例：一个二维的两类判别问题，模式分布如图示，这些分属于1，2两类的模式可用一直线方程 d(X)=0来划分。,为坐标变量，,为方程参数。,式中：,图3.2 两类二维模式的分布,1判别函数的定义,若 ，则,若 ，则 类；,若 ，则 类；,或拒绝,将某一未知模式 X 代入：,维数=3时：判别边界为一平面。 维数3时：判别边界为一超平面。,d(X) 表示的是一种分类的标准，它可以是1、2、3维的， 也可以是更高维的。,判别界面的正负侧，是在训练判别函数的权值时确定的。,2判别函数正负值的确定,图3.3 判别函数正负的确定,1）判决函数d(X)

3、的几何性质。它可以是线性的或非线性的函 数，维数在特征提取时已经确定。,如：已知三维线性分类 判决函数的性质就确定了判决函数 的形式：,3. 确定判别函数的两个因素,例：非线性判决函数,2）判决函数d(X)的系数。用所给的模式样本确定。,3.2 线性判别函数,3.2.1 线性判别函数的一般形式,将二维模式推广到n维，线性判别函数的一般形式为：,(3-2),式中：,：权向量，即参数向量。,增广向量的形式：,式中：,为增广权向量，,为增广模式向量。,3.2.2 线性判别函数的性质,1. 两类情况,对M个线性可分模式类，1， 2， M，有三种 划分方式：,2. 多类情况,两分法,两分法,两分法特例,

4、用线性判别函数将属于i类的模式与其余不属于i类的 模式分开。,识别分类时：,对某一模式区，di(X)0 的条件超过一个，或全部 的di(X)0 ，分类失效。 相当于不确定区(indefinite region ，IR)。,此法将 M 个多类问题分成M个两类问题，识别每一类均 需M个判别函数。识别出所有的M类仍是这M个函数。,例3.1 设有一个三类问题，其判别式为：,现有一模式，X=7,5T，试判定应属于哪类？并画出三类模式的分布区域。,解：将X=7,5T代入上三式，有：,三个判别界面分别为：,图示如下：,步骤：,a) 画出界面直线。,b) 判别界面正负侧：找特殊点带入。,c) 找交集。,例3.

5、2 已知di(X)的位置和正负侧，分析三类模式的分布区域 。,一个判别界面只能分开两个类别，不能把其余所有的类 别都分开。判决函数为： 。这里 。,则 类，而 在判别 类模式时不起作用。,如：对一个三类问题，如果 ，,识别分类时：,判别函数性质：,与 值无关。,例3.3 一个三类问题，三个判决函数为：,解：计算得,可写成：,x2,x1,d23(X)=0,d12(X)=0,d13(X)=0,5,5,3,0,分类时：每分离出一类，需要与I 有关的M-1个判决函数；要分开M类模式，共需M(M-1)/2个判决函数。对三类问题需要3(3-1)/2=3个判决函数。即：每次从M类中取出两类的组合：,例3.4

6、 已知dij(X)的位 置和正负侧，分析三 类模式的分布区域 。,当i /j两分法中的判别函数dij(X) ，可以分解为,时，那么di(X) dj(X)就相当于多类情况2中的dij(X) 0。,因此对具有判别函数,的M类情况，判别函数性质为：,或：,识别分类时：,判别界面需 要做差值。对i 类，应满足： di其他所有d, 除边界区外，没有不确定区域。,特点：, 是第二种情况的特例。由于dij(X)= di (X) dj(X) ，若在第三 种情况下可分，则在第二种情况下也可分，但反过来不一定。, 把 M 类情况分 成了(M -1)个两类 问题。并且 类 的判别界面全部与 类的判别 界面相邻（向无

7、穷 远处延伸的区域除 外）。,例3.5 一个三类模式（M=3）分类器，其判决函数为：,试判断X0=1,1T属于哪一类，且分别给出三类的判决界面。,解：,判决界面如图所示。,类的判决函数：,类的判决函数：,例3.6 已知判决界面的位置和正负侧，分析三类模式的分布 区域 。,(1) 明确概念：线性可分。,一旦线性判别函数的系数Wk被确定以后，这些函数就可以 作为模式分类的基础。,3. 小结,(2) 分法的比较：,对于M类模式的分类， 两分法共需要M个判别函数，但 两分法需要M(M-1)/2个。当时M3时，后者需要更多个判别式（缺点），但对模式的线性可分的可能性要更大一些（优点）。,原因：,一种类别

8、模式的分布要比M-1类模式的分布更为聚集， 分法受到的限制条件少，故线性可分的可能性大。,1非线性多项式函数 非线性判别函数的形式之一是非线性多项式函数。,3.3 广义线性判别函数,目的： 对非线性边界：通过某映射，把模式空间X变成X*，以便 将X空间中非线性可分的模式集，变成在X*空间中线性可分的 模式集。,设一训练用模式集，X在模式空间X中线性不可分，非线 性判别函数形式如下：,(3-9),式中 是模式X的单值实函数， 。,fi(X)取什么形式及d(X)取多少项，取决于非线性边界的复杂程度。,广义形式的模式向量定义为：,(3-10),这里X*空间的维数k高于X空间的维数n，(3-9)式可写

9、为,上式是线性的。讨论线性判别函数并不会失去一般性的意义。,(3-11),随着小样本学习理论和支持向量机的迅速发展，广义线性 判别函数的 “维数灾难”问题在一定程度上找到了解决的办法。,非线性变换可能非常复杂 。,问题：,维数大大增加： 维数灾难。,例3.7 假设X为二维模式向量， fi(X)选用二次多项式函数，原判 别函数为,定义：,d(X)线性化为：,即：,广义线性判别函数：,3.4 线性判别函数的几何性质,3.4.1 模式空间与超平面,模式空间：以n维模式向量X的n个分量为坐标变量的欧氏空间。,模式向量的表示：点、有向线段。,线性分类：用d(X)进行分类，相当于用超平面d(X)=0把模式

10、空 间分成不同的决策区域。,2. 讨论,1. 概念,式中， ， 。,设判别函数：,超平面：,(1) 模式向量X1和X2在超平面上, W0是超平面的法向量， 方向由超平面的负侧指向正侧。,设超平面的单位法线向量为U：,(2) X不在超平面上,将X向超平面投影得向量Xp， 构造向量R：,r：X到超平面的垂直距离。有,(r), 判别函数d(X) 正比于点X到超平面的代数距离。,X到超平面的距离：, 点X到超平面的代数距离（带正负号）正比于d(X)函数值。,(3) X在原点,得, 超平面的位置由阈值权wn+1决定：,wn+1 0时，原点在超平面的正侧；,wn+1 0时，原点在超平面负侧；,wn+1=

11、0 时，超平面通过原点。,3.4.2 权空间与权向量解,1. 概念,权空间：以 的权系数为 坐标变量的（n+1）维欧氏空间,增广权向量的表示：点、有向线段。,2. 线性分类,判别函数形式已定，只需确定权向量。,类：X11，X12，X1p,类： X21，X22，X2q,设增广样本向量：,使d(X)将1和 2分开，需满足,给2的q个增广模式乘以（1），统一为, 其中, 样本的规范化过程。,对每个已知的X，d(X)=0在权空间确定一个超平面，共(p+q)个。,在权空间中寻找向量W使判别函数d(X)能把1类和2类 分开，就是寻找一个权向量，其在（p+q）个超平面的正侧的 交迭区域里(W的解区)。,X：

12、规范化增广样本向量。,例：二维权空间，超平面的方程为：,超平面：过原点的直线；,阴影部分：解区。,3.4.3 二分法,二分法（Dichotomies）：用判别函数d(X)将给定的N个模式 分成两类的方法。是一种基本的分类方法。,判别函数的不同分类能力可以通过二分法总数衡量。,若不限制判别函数的形式，N个n维模式用判别函数分成两 类的二分法总数为2N。,若限定用线性判别函数，并且样本在模式空间是良好分布 的，即在n维模式空间中没有(n+1)个模式位于(n1)维子空间 中，可以证明，N个n维模式用线性判别函数分成两类的方法总 数，即线性二分法总数为,或线性二分法概率：,只要模式的个数N小于或等于增

13、广模式的维数（n+1）， 模式类总是线性可分的，,例：4个良好分布的2维模式，若用线性判别函数分类,线性二分法总数：,线性二分法概率：,图3.14 线性二分法的概率,将=2时的N值定义为阈值N0，称为二分法能力，即,通过N0，可以对任意N个样本的线性可分性进行粗略估计。,3.5 感知器算法,1. 概念理解,训练：用已知类别的模式样本指导机器对分类规则进行反复修 改，最终使分类结果与已知类别信息完全相同的过程。,1）训练与学习,只要求出权向量，分类器的设计即告完成。本节开始介绍如何通过各种算法，利用已知类别的模式样本训练出权向量W。,对线性判别函数，当模式维数已知时，判别函数的形式实际上已经确定

14、，如：三维时,3）感知器 对一种分类学习机模型的称呼，属于有关机器学习的仿生学领域中的问题，由于无法实现非线性分类而下马。但“赏罚概念（ reward-punishment concept）” 得到广泛应用。,2）确定性分类器,处理确定可分情况的分类器。通过几何方法将特征空间 分解为对应不同类的子空间，又称为几何分类器。,2. 感器算法（perception approach）,两类线性可分的模式类： ，设,其中， ，,应具有性质,对样本进行规范化处理，即2类样本全部乘以(1)，则有：,感知器算法通过对已知类别的训练样本集的学习，寻找 一个满足上式的权向量。,感知器算法步骤：,（1）选择N个分

15、属于1和 2类的模式样本构成训练样本集 X1, , XN 构成增广向量形式，并进行规范化处理。任取权向量初始 值W(1)，开始迭代。迭代次数k=1 。,（2）用全部训练样本进行一轮迭代，计算WT(k)Xi 的值，并修 正权向量。,分两种情况，更新权向量的值：,c：正的校正增量。,分类器对第i个模式做了错误分类，,权向量校正为：,统一写为：,（3）分析分类结果：只要有一个错误分类，回到（2），直至 对所有样本正确分类。,分类正确时，对权向量“赏”这里用“不罚”，即权向量不变； 分类错误时，对权向量“罚”对其修改，向正确的方向转换。,感知器算法是一种赏罚过程：,3. 收敛性,收敛性：经过算法的有限次迭代运算后，求出了一个使所有样本都能正确分类的W，则称算法是收敛的。,可以证明感知器算法是收敛的。 收敛条件：模式类别线性可分。,例3.8 已知两类训练样本,解：所有样本写成增广向量形式； 进行规范化处理，属于2的样本乘以(1