《模式识别原理幻灯片第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