2-模式识别原理课件-第3章--判别函数及几何分类法.ppt

2-模式模式识别原理原理课件件-第第3章章-判判别函函数及几何分数及几何分类法法第第3章章 判别函数及几何分类法判别函数及几何分类法3.1 判别函数判别函数3.2 线性判别函数线性判别函数3.3 广义线性判别函数广义线性判别函数3.4 线性判别函数的几何性质线性判别函数的几何性质3.5 感知器算法感知器算法3.6 梯度法梯度法3.7 最小平方误差算法最小平方误差算法3.8 非线性判别函数非线性判别函数2021/5/222021/5/222 23.1 判别函数判别函数聚类分析法（第二章）判决函数法几何分类法确定性事件分类（第三章）概率分类法随机事件分类（第四章）线性判决函数法统 计 决 策 方 法非线性判决函数法复习与引申：复习与引申：模式识别统计2021/5/222021/5/223 3若分属于1，2的两类模式可用一方程d(X)=0来划分，那么称d(X)为判别函数，或称判决函数、决策函数。3.1 判别函数判别函数(discriminant function)直接用来对模式进行分类的准则函数。例：一个二维的两类判别问题，模式分布如图示，这些分属于1，2两类的模式可用一直线方程 d(X)=0来划分。为坐标变量，为方程参数。式中：图3.2 两类二维模式的分布1判别函数的定义判别函数的定义2021/5/222021/5/224 4若 ，则若 ，则 类；若 ，则 类；或拒绝将某一未知模式 X 代入：维数=3时：判别边界为一平面。维数3时：判别边界为一超平面。2021/5/222021/5/225 5 d(X)表示的是一种分类的标准，它可以是1、2、3维的，也可以是更高维的。判别界面的正负侧，是在训练判别函数的权值时确定的。2判别函数正负值的确定判别函数正负值的确定图3.3 判别函数正负的确定2021/5/222021/5/226 61）判决函数d(X)的几何性质。它可以是线性的或非线性的函 数，维数在特征提取时已经确定。如：已知三维线性分类 判决函数的性质就确定了判决函数 的形式：3.确定判别函数的两个因素确定判别函数的两个因素例：非线性判决函数2）判决函数d(X)的系数。用所给的模式样本确定。2021/5/222021/5/227 73.2 线性判别函数线性判别函数3.2.1 线性判别函数的一般形式线性判别函数的一般形式将二维模式推广到n维，线性判别函数的一般形式为：(3-2)式中：权向量，即参数向量。增广向量的形式：式中：为增广权向量，为增广模式向量。2021/5/222021/5/228 83.2.2 线性判别函数的性质线性判别函数的性质1.两类情况d(X)=0：不可判别情况，可以）对M个线性可分模式类，1，2，M，有三种划分方式：2.多类情况 两分法两分法两分法特例2021/5/222021/5/229 9两分法(1)多类情况1：用线性判别函数将属于i类的模式与其余不属于i类的模式分开。将某个待分类模式 X 分别代入 M 个类的d(X)中，若只有di(X)0，其他d(X)均0，则判为i类。识别分类时：2021/5/222021/5/221010 全部不属任何类 IR，可能 属于1w或3w 1w2w3w0)(2=Xd0)(3=Xd+IR，可能 属于3w或2w+-0)(1=Xd0,0312ddd0,0321ddd0,0,321dddIR，可能属于1w或2w 0,0213ddd2x1x+对某一模式区，di(X)0的条件超过一个，或全部的di(X)dd001312dd002321dd3w+-d23(X)=0d12(X)=0d13(X)=0IR000231312dd001312dd002321dd3w+-d23(X)=0d12(X)=0d13(X)=0IR000231312dj(X)就相当于多类情况2中的dij(X)0。两分法特例(3)多类情况3：因此对具有判别函数 的M类情况，判别函数性质为：或：2021/5/222021/5/222020识别分类时：判别界面需要做差值。对i类，应满足：di其他所有d2313dddd01w2w2x1x()0)(21=-XdXd+-()0)(31=-XdXd()0)(32=-XdXd3212dddd3121dddd3w2021/5/222021/5/222121 除边界区外，没有不确定区域。特点：是第二种情况的特例。由于dij(X)=di(X)dj(X)，若在第三种情况下可分，则在第二种情况下也可分，但反过来不一定。2313dddd01w2w2x1x()0)(21=-XdXd+-()0)(31=-XdXd()0)(32=-XdXd3212dddd3121dddd3w 把 M 类情况分成了(M-1)个两类问题。并且 类的判别界面全部与 类的判别界面相邻（向无穷远处延伸的区域除外）。2021/5/222021/5/222222例例3.5 一个三类模式（M=3）分类器，其判决函数为：试判断X0=1,1T属于哪一类，且分别给出三类的判决界面。解：2021/5/222021/5/222323类的判决函数：判决界面如图所示。类的判决函数：类的判决函数：-()0)(21=-XdXd2313dddd0.5x2+-()0)(31=-XdXd()0)(32=-XdXd3212dddd3121dddd110.5w1w2w3x1+2021/5/222021/5/222424-O2x1x()0)(21=-XXdd+-()0)(31=-XXdd()0)(32=-XXdd例例3.6 已知判决界面的位置和正负侧，分析三类模式的分布 区域。2021/5/222021/5/222525(1)明确概念：线性可分。一旦线性判别函数的系数Wk被确定以后，这些函数就可以作为模式分类的基础。3.小结小结(2)分法的比较：对于M类模式的分类，两分法共需要M个判别函数，但 两分法需要M(M-1)/2个。当时M3时，后者需要更多个判别式（缺点），但对模式的线性可分的可能性要更大一些（优点）。原因：一种类别模式的分布要比M-1类模式的分布更为聚集，分法受到的限制条件少，故线性可分的可能性大。2021/5/222021/5/2226261非线性多项式函数非线性多项式函数 非线性判别函数的形式之一是非线性多项式函数。3.3 广义线性判别函数广义线性判别函数目的：对非线性边界：通过某映射，把模式空间X变成X*，以便将X空间中非线性可分的模式集，变成在X*空间中线性可分的模式集。设一训练用模式集，X在模式空间X中线性不可分，非线性判别函数形式如下：(3-9)式中 是模式X的单值实函数，。fi(X)取什么形式及d(X)取多少项，取决于非线性边界的复杂程度。2021/5/222021/5/222727广义形式的模式向量定义为：(3-10)这里X*空间的维数k高于X空间的维数n，(3-9)式可写为上式是线性的。讨论线性判别函数并不会失去一般性的意义。(3-11)随着小样本学习理论和支持向量机的迅速发展，广义线性判别函数的“维数灾难”问题在一定程度上找到了解决的办法。非线性变换可能非常复杂。问题：维数大大增加：维数灾难。2021/5/222021/5/222828例例3.7 假设X为二维模式向量，fi(X)选用二次多项式函数，原判别函数为定义：d(X)线性化为：即：广义线性判别函数：2021/5/222021/5/2229293.4 线性判别函数的几何性质线性判别函数的几何性质3.4.1 模式空间与超平面模式空间与超平面模式空间：以n维模式向量X的n个分量为坐标变量的欧氏空间。模式向量的表示：点、有向线段。线性分类：用d(X)进行分类，相当于用超平面d(X)=0把模式空 间分成不同的决策区域。2.讨论1.概念式中，。设判别函数：超平面：2021/5/222021/5/223030(1)模式向量X1和X2在超平面上 W0是超平面的法向量，方向由超平面的负侧指向正侧。设超平面的单位法线向量为U：2021/5/222021/5/223131(2)X不在超平面上 将X向超平面投影得向量Xp，构造向量R：r：X到超平面的垂直距离。有(r)判别函数d(X)正比于点X到超平面的代数距离。2021/5/222021/5/223232X到超平面的距离：点X到超平面的代数距离（带正负号）正比于d(X)函数值。(3)X在原点得 超平面的位置由阈值权wn+1决定：wn+1 0时，原点在超平面的正侧；wn+1 0时。用负梯度向量的值对权向量W进行修正，实现使准则函数达到极小值的目的。2021/5/222021/5/225555基本思路：定义一个对错误分类敏感的准则函数J(W,X)，在J的梯度方向上对权向量进行修改。一般关系表示成从W(k)导出W(k+1)：其中c是正的比例因子。梯度法求解步骤：（1）将样本写成规范化增广向量形式，选择准则函数，设置初始权向量W(1)，括号内为迭代次数k=1。2021/5/222021/5/225656权向量修正为：迭代次数k加1，输入下一个训练样本，计算新的权向量，直至对全部训练样本完成一轮迭代。（3）在一轮迭代中，如果有一个样本使 ，回到(2)进行下 一轮迭代。否则，W不再变化，算法收敛。（2）依次输入训练样本X。设第k次迭代时输入样本为Xi，此时 已有权向量W(k)，求 ：2021/5/222021/5/225757例例3.10 选择准则函数，简单地考虑X为一维增广模式的情况X=1，此时W=w，两者均为标量，错误分类时：，对权向量校正。正确分类时：，对权向量不做修正。2021/5/222021/5/225858说明：随着权向量W向理想值接近，准则函数关于W的导数()越来越趋近于零，这意味着准则函数J 越来越接近最小值。当 最终 时，J达到最小值，此时W不再改变，算法收敛。将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题。c)梯度算法是求解权向量的一般解法，算法的具体计算形式取决于准则函数J(W,X)的选择，J(W,X)的形式不同，得到的具体算法不同。a)b)c值的选择很重要，如c值太小，收敛太慢；但若太大，搜索又可能过头，甚至引起发散。2021/5/222021/5/2259593.6.2 固定增量法固定增量法准则函数：求W(k)的递推公式：1.求J的梯度方法：函数对向量求导=函数对向量的分量求导，即该准则函数有唯一最小值“0”，且发生在 的时候。设 ，2021/5/222021/5/226060部分：首先求另：矩阵论中有2021/5/222021/5/226161其中 由的结论 有：2021/5/222021/5/2262622.求W(k+1)将 代入得：2021/5/222021/5/226363 由此可以看出，感知器算法是梯度法的特例。即：梯度法是将感知器算法中联立不等式求解W的问题，转换为求函数J极小值的问题，将原来有多个解的情况，变成求最优解的情况。上式即为固定增量算法，与感知器算法形式完全相同。即：只要模式类是线性可分的，算法就会给出解。2021/5/222021/5/2264643.7 最小平方误差算法最小平方误差算法（least mean square error,LMSE；亦称Ho-Kashyap算法）上述的感知器算法、梯度算法、固定增量算法或其他类似方法，只有当模式类可分离时才收敛，在不可分的情况下，算法会来回摆动，始终不收敛。当一次次迭代而又不见收敛时，造成不收敛现象的原因分不清，有两种可能：a)迭代过程本身收敛缓慢b)模式本身不可分对可分模式收敛。对于类别不可分的情况也能指出来。LMSE算法特点：2021/5/222021/5/2265651.分类器的不等式方程分类器的不等式方程 两类分类问题的解相当于求一组线性不等式的解。如果给出分属于 ，两个模式类的训练样本集 ，应满足：其中，Xi是规范化增广样本向量，。上式分开写为：2021/5/222021/5/226666写成矩阵形式为：令N(n+1)的长方矩阵为X，则 变为：2021/5/222021/5/226767式中：0为零向量 感知器算法是通过解不等式组 ，求出W。2021/5/222021/5/2268682.LMSE算法算法1)原理原理的求解。式中：两式等价。为各分量均为正值的矢量。LMSE算法把对满足 XW 0 的求解，改为满足 在方程组中当行数列数时，通常无解，称为矛盾方程组，一般求近似解。在模式识别中，通常训练样本数N总是大于模式的维数n，因此方程的个数(行数)模式向量的维数(列数)，是矛盾方程组，只能求近似解W*，即说明：2021/5/222021/5/226969 LMSE算法的出发点：选择一个准则函数，使得当J达到最小值时，XW=B 可得到近似解（最小二乘近似解）。LMSE算法的思路：转化为转化为准则函数定义为：“最小二乘”：最小：使方程组两边误差最小，也即使J最小。二乘：次数为2，乘了两次最小平方（误差算法）2021/5/222021/5/227070考察向量(XWB)有：2021/5/222021/5/227171可以看出：当函数J达到最小值，等式XW=B有最优解。即又将问题转化为求准则函数极小值的问题。因为J有两个变量W和B，有更多的自由度供选择求解，故可望改善算法的收敛速率。XW=B 的近似解也称“最优近似解”：使方程组两边所有误差之和最小（即最优）的解。准则函数：2021/5/222021/5/227272使J 对W求最小，令 ，得：2)推导推导LMSE算法递推公式算法递推公式与问题相关的两个梯度：(3-46)(3-47)由(3-47)式可知：只要求出B，就可求出W。求递推公式：(1)求W 的递推关系X为N(n+1)长方阵，X#为(n+1)N 长方阵。称为X的伪逆，式中：(3-45)2021/5/222021/5/227373(2)求B(k+1)的迭代式(3-46)代入，得 令，定义(3-49)(3-50)(3-46)利用梯度算法公式有：2021/5/222021/5/227474(3)求W(k+1)的迭代式将(3-50)代入(3-47)式W=X#B 有：=0(3-49)(3-50)2021/5/222021/5/227575总结：设初值B(1)，各分量均为正值，括号中数字代表迭代次数。W(k+1)、B(k+1)互相独立，先后次序无关。求出B，W后，再迭代出下一个e，从而计算出新的B，W。或另一算法：先算B(k+1)，再算W(k+1)。2021/5/222021/5/2276763）模式类别可分性判别）模式类别可分性判别 如果e(k)0 ，表明XW(k)B(k)0，隐含有解。继续迭代，可使e(k)0。如果e(k)0，有解。分以下几种情况：2021/5/222021/5/227777情况分析：e(k)0，线性可分，若进入(5)可使e(k)0，得最优解。如果e(k)0，线性不可分，停止迭代，无解，算法结束。如果e(k)=0，线性可分，解为W(k)，算法结束。否则，说明e(k)的各分量值有正有负，进入(5)。2021/5/222021/5/228080(5)计算W(k+1)和B(k+1)。方法1：分别计算方法2：先计算再计算迭代次数k加1，返回(4)。3.算法特点算法特点(1)算法尽管略为复杂一些，但提供了线性可分的测试特征。(2)同时利用N个训练样本，同时修改W和B，故收敛速度快。(3)计算矩阵 复杂，但可用迭代算法计算。2021/5/222021/5/228181例3.11 已知两类模式训练样本：试用LMSE算法求解权向量。解：(1)写出规范化增广样本矩阵：2021/5/222021/5/228282 Aij是aij的代数余子式，注意两者的行和列的标号互换。(2)求伪逆矩阵求逆矩阵：若，则|A|A的行列式A*A的伴随矩阵2021/5/222021/5/228383 划去aij所在的行和列的元素，余下元素构成的行列式做aij的余子式，记作Mij，将 叫做元素aij的代数余子式。例：代数余子式定义：行列式:2021/5/222021/5/228484(3)取 和 c=1 开始迭代：.解为 W(1)，判断函数为：2021/5/222021/5/228585图示如下：2021/5/222021/5/228686例3.12 已知模式训练样本：，(2)求 ：解：(1)规范化增广样本矩阵：(3)取 和c=1，迭代：用LMSE算法求解权向量。2021/5/222021/5/228787 e(1)全部分量为负，无解，停止迭代。为线性不可分模式。2021/5/222021/5/228888小结：小结：(1)感知器法、梯度法、最小平方误差算法讨论的分类算法都是通过模式样本来确定判别函数的系数，所以要使一个分类器设计完善，必须采用有代表性的数据，训练判别函数的权系数。它们能合理反映模式数据的总体。(2)要获得一个有较好判别性能的线性分类器，所需要的训练样本的数目的确定。用指标二分法能力N0来确定训练样本的数目：通常训练样本的数目不能低于N0，选为 N0的510倍左右。二维：不能低于6个样本，最好选在3060个样本之间。三维：不能低于8个样本，最好选在4080个样本之间。n为模式维数如2021/5/222021/5/2289893.8 非线性判别函数非线性判别函数3.8.1 分段线性判别函数分段线性判别函数线性判别函数的特点：形式简单，容易学习；用于线性可分的模式类。非线性判别函数：用于线性不可分情况。分段线性、超曲面。特点基本组成为超平面。*相对简单；*能逼近各种形状的超曲面。2021/5/222021/5/2290901一般分段线性判别函数一般分段线性判别函数设有M类模式，将i类（i=1,2,M）划分为li个子类：其中第n个子类的判别函数：i类的判别函数定义为：M类的判决规则：若，则用各类判别函数进行分类判决实际是用各类选出的子类判别函数进行判决判别面由各子类的判别函数决定2021/5/222021/5/229191若i类的第n个子类和j类的第m个子类相邻，判别界面方程为：子类之间的判别界面组成各类之间的判别界面类间判别界面分段线性2021/5/222021/5/2292922基于距离的分段线性判别函数基于距离的分段线性判别函数设 1类均值向量：2类均值向量：N1，N2：两类样本数。任一模式X到M1和M2的欧氏距离平方：判决规则：若，则若，则判别界面方程：1）最小距离分类器2021/5/222021/5/229393化简得：X的线性方程，确定一个超平面。最小距离分类器 2021/5/222021/5/2294942）分段线性距离分类器 设：M类模式，其中i类划分为li个子类，第n个子类的均值向量为 。每个子类的判别函数：每类的判别函数：判决规则：若则2021/5/222021/5/2295953.8.2 分段线性判别函数的学习方法分段线性判别函数的学习方法1已知子类划分时的学习方法已知子类划分时的学习方法*每个子类看成独立的类；*在一类范围内根据多类情况3，学习各子类判别函数；*继而得到各类判别函数。2已知子类数目时的学习方法已知子类数目时的学习方法 用类似于固定增量算法的错误修正算法学习分段线性判别函数 3未知子类数目时的学习方法未知子类数目时的学习方法树状分段线性分类器 2021/5/222021/5/229696 树状分段线性分类器判别函数的学习及分类过程 2021/5/222021/5/229797暂停点暂停点：，；：，2021/5/222021/5/2298983.8.3 势函数法势函数法1.势函数概念势函数概念划分属于1和2类模式样本：样本是模式空间中的点，将每个点比拟为点能源，在点上势能达到峰值，随着与该点距离的增大，势能分布迅速减小。1类样本势能为正势能积累形成“高地”；2类样本势能(-1)势能积累形成“凹地”；在两类电势分布之间，选择合适的等势面（如零等势面），即可认为是判别界面了。借用点能源的势能概念解决模式分类问题。2021/5/222021/5/229999一个样本xk的势能分布用势函数K(x,xk)表示积累势函数一维情况示例2021/5/222021/5/221001002.势函数法判别函数的产生势函数法判别函数的产生依次输入样本，利用势函数逐步积累势能的过程。判别函数由模式空间中样本向量 的势函数K(X,Xk)累加产生，分类器计算积累势K(X)，最后取d(X)=K(X)。设初始积累势函函数 ，下标为迭代次数。势函数法：势函数法：第一步：加入训练样本 X1，K1(X)描述了加入第一个样本后的边界划分。2021/5/222021/5/22101101第二步：加第二个训练样本X2，分三种情况：分类正确，势函数不变：，错误分类，修改势函数：，错误分类，修改势函数：2021/5/222021/5/22102102第k步：设Kk(X)为加入训练样本X1，X2，Xk后的积累势函数，则加入第k+1个样本，有：正确分类，错误分类：，错误分类：以上决定积累位势的迭代算法可写为：其中rk+1 为校正项系数，定义为：(3-57)(3-58)2021/5/222021/5/22103103从所给的训练样本集 中略去不使积累势发生变化的那些样本，可得一简化样本序列 （校正错误的样本），算法可规纳为：即：由(k+1)个训练样本产生的积累势，等于两类中校正错误 的样本的总势能之差。式中，(3-59)(3-60)2021/5/222021/5/22104104 从势函数算法可看出，积累势函数起着判别函数的作用，因此可直接用作判别函数，故取 d(X)=K(X)。由(3-57)式得：式中rk+1按(3-58)式取值：也可简写成：式中 取值同(3-60)：(3-57)(3-61)2021/5/222021/5/22105105 两个n维向量 X 和 Xk 的函数K(X,Xk)，如同时满足下列三个条件，都可做为势函数：3.势函数的选择势函数的选择，当且仅当 X=Xk 时达到最大值。当向量 X 与 Xk 的距离趋于无穷时，K(X,Xk)趋于零。K(X,Xk)是光滑函数，且是X与Xk之间距离的单调下降函数。1）势函数应具备的条件2）构成势函数的两种方法式中 ，在模式定义域内应为正交函数集。型势函数：用对称的有限项多项式展开，即：2021/5/222021/5/22106106a)内积：定义为 ，是一个实数。“正交函数”概念：已知函数y(x)和z(x)，b)正交：满足(y,z)=0。例：将这类势函数代入(3-61)式，有判别函数：型势函数：直接选择双变量 X 和 Xk 的对称函数作为势函数，即 ，如：2021/5/222021/5/22107107(3-67)(3-68)曲线 c 含有正弦函数，具有振荡特点，只有第一个振荡周期可用。式中 为正常数。(3-66)图3.25 一维型势函数举例曲线a (3-66)曲线b (3-67)曲线c (3-68)2021/5/222021/5/22108108例例3.14 设两类训练样本集样本分布如图所示。用型势函数进行分类，求判别函数。解：两类模式不是线性可分的，这里选择指数型的势函，。二维情况下势函数为：开始迭代：w1 w 2 式中，2021/5/222021/5/22109109第一步：第二步：分类正确,不修正。第三步：，分类错误，修正。第四步：分类错误，修正。2021/5/222021/5/22110110第五步：，不修正。第六步：，修正。第七步：不修正。第八步：不修正。2021/5/222021/5/22111111第九步：不修正。第十步：不修正。从X7至X10的四次迭代中，所有训练样本皆被正确分类，故算法已收敛于判别函数，分类器设计完毕。判别函数：判别界面：d(X)=0第七步：第八步：2021/5/222021/5/22112112 当训练样本的维数和数目较高时，需要计算和存储更多的指数项，但正因为判别函数由许多新项组成，故有很强的分类能力。用型势函数构成判别函数的特点：2021/5/222021/5/22113113结束结束2021/5/222021/5/22114114谢谢观赏！2020/11/5115