模式识别第二章(线性判别函数法).ppt

1、第二章 线性判别函数,2020/7/23,模式识别导论,2,实例：统计模式识别,19名男女同学进行体检，测量了身高和体重，但事后发现其中有4人忘记填写性别，试问（在最小错误的条件下）这4人是男是女？体检数值如下：,2020/7/23,模式识别导论,3,实例：统计模式识别（续）,待识别的模式：性别（男或女） 测量的特征：身高和体重 训练样本：15名已知性别的样本特征 目标：希望借助于训练样本的特征建立判别函数（即数学模型）,2020/7/23,模式识别导论,4,实例：统计模式识别（续）,从图中训练样本的分布情况，找出男、女两类特征各自的聚类特点，从而求取一个判别函数（直线或曲线）。 只要给出待分

2、类的模式特征的数值，看它在特征平面上落在判别函数的哪一侧，就可以判别是男还是女了。,2020/7/23,模式识别导论,5,有关模式识别的3个问题,学习 人们在日常生活中几乎时时刻刻在进行模式识别的活动，从小时候起就开始学习与增强这种能力。如小孩学习认字、认识事物都有一个从不会到会的过程。 确定分类决策的具体数学公式是通过分类器设计这个过程确定的。在模式识别学科中一般把这个过程称为训练与学习的过程。 一般来说，决定使用什么类型的分类函数往往是人为决定的。但数学式子中的参数则往往通过学习来确定,2020/7/23,模式识别导论,6,有关模式识别的3个问题,模式的紧致性 分类器设计难易程度与模式在特

3、征空间的分布方式有密切关系，例如图(a)、(b)与(c)分别表示了两类在空间分布的三种状况。 两类事物分布的区域不要有相互混迭的情况，事物尽管没有混迭，但交界线很复杂。,2020/7/23,模式识别导论,7,1有关模式识别的3个问题,相似性度量 同类物体之所以属于同一类，在于它们的某些属性相似，因此可选择适当的度量方法检测出它们之间的相似性。 在特征空间中用特征向量描述样本的属性，用距离来表示相似性度量。 合适的特征空间情况下，同类样本应具有聚类性，或紧致性好，而不同类别样本应在特征空间中显示出具有较大的距离。,2020/7/23,模式识别导论,8,4.1 引言,分类器设计方法，是根据训练样本

4、集提供的信息，直接进行分类器设计。这种方法省去了统计分布状况分析，直接对特征空间进行划分，也是当前的主要方法之一。,2020/7/23,模式识别导论,9,2.1 引言,决策域的分界面是用数学表达式来描述的，如线性函数和各种非线性函数等，所以分界面的方程主要包括函数类型选择与最佳参数确定。 一般来说，函数类型由设计者选择，其参数的确定则是依据一定的准则函数，通过一个学习过程来实现优化。,2020/7/23,模式识别导论,10,2.1 引言,将模式识别的设计过程，主要是判别函数、决策面方程的确定过程改成,2020/7/23,模式识别导论,11,2.1 引言,线性分类器以及作为设计依据的一些准则函数

5、，准则函数包括：感知准则，最小平方误差准则，最小错分样本数准则，Fisher准则。,2020/7/23,模式识别导论,12,2.2.1 线性判别函数的基本概念,在一个d维的特征空间中，线性判别函数的一般表达式如下,2020/7/23,模式识别导论,13,2.2.1 线性判别函数的基本概念,如果采用增广模式，可以表达如下,若分属于1，2的两类模式可用一方程d(X) =0来 划分，那么称d(X) 为判别函数，或称判决函数、 决策函数。,2.1 判别函数(discriminant function),直接用来对模式进行分类的准则函数。,例：一个二维的两类判别问题，模式分布如图示，这些分属于1，2两类

6、的模式可用一直线方程 d(X)=0来划分。,为坐标变量，,为方程参数。,式中：,图3.2 两类二维模式的分布,1判别函数的定义,若 ，则,若 ，则 类；,若 ，则 类；,或拒绝,将某一未知模式 X 代入：,维数=3时：判别边界为一平面。 维数3时：判别边界为一超平面。,d(X) 表示的是一种分类的标准，它可以是1、2、3维的， 也可以是更高维的。,判别界面的正负侧，是在训练判别函数的权值时确定的。,2判别函数正负值的确定,图3.3 判别函数正负的确定,1）判决函数d(X)的几何性质。它可以是线性的或非线性的函 数，维数在特征提取时已经确定。,如：已知三维线性分类 判决函数的性质就确定了判决函数

7、 的形式：,3. 确定判别函数的两个因素,例：非线性判决函数,2）判决函数d(X)的系数。用所给的模式样本确定。,18,19,20,多类问题图例（第一种情况）,?,不确定区域,21,1、第一种情况（续）,判别规则为：,如果,则判,比如对图的三类问题,如果对于任一模式 如果它的 则该模式属于1类。,22,1、第一种情况（续）,如果某个X使二个以上的判别函数 di0 。则此模式X就无法作出确切的判决。如图,另一种情况是IR2区域，判别函数都为负值。IR1，IR2，IR3，IR4。都为不确定区域。,23,1、第一种情况（续）,解： 三个判别边界分别为：,24,1、第一种情况（续）,结论： 因为 所以

8、它属于2类。,25,1、第一种情况（续）,26,27,2、第二种情况（续）,多类问题图例（第二种情况）,28,29,d12(x) = - d21(x) = x1 x2 + 5 = 0,d12(x)为正,两分法例题图示,d21(x)为正,30,d23(x)= -d32(x)= x1+x2= 0,d32(x)为正,d23(x)为正,31,d13(x)= -d31(x)= x1+3 = 0,d31(x)为正,d13(x)为正,32,3类判别区域 d31(x)0 d32(x)0,33,34,3、第三种情况（续）,多类问题图例（第三种情况）,35,。,36,上述三种方法小结:,方法判别函数的数目和方法相

9、同，但没有不确定区，分析简单，是最常用的一种方法。,(1) 明确概念：线性可分。,一旦线性判别函数的系数Wk被确定以后，这些函数就可以 作为模式分类的基础。,3. 小结,(2) 分法的比较：,对于M类模式的分类， 两分法共需要M个判别函数，但 两分法需要M(M-1)/2个。当时M3时，后者需要更多个判别式（缺点），但对模式的线性可分的可能性要更大一些（优点）。,原因：,一种类别模式的分布要比M-1类模式的分布更为聚集， 分法受到的限制条件少，故线性可分的可能性大。,2020/7/23,模式识别导论,38,.2.1 线性判别函数的基本概念,线性分类器的设计就是利用训练样本集建立线性判别函数式，也

10、就是寻找最优的权向量w的过程。其主要步骤如下 采集训练样本，构成训练样本集。样本应该具有典型性 确定一个准则J=J(w,x)，能反映分类器性能，且存在权值w*使得分类器性能最优 设计求解w的最优算法，得到解向量w*,2020/7/23,模式识别导论,39,2.2.2 感知器概念及其训练方法,感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。,40,2.3 感知器算法(Perceptron Approach),任选一初

11、始增广权矢量,感知器算法流程图,流程:,2020/7/23,模式识别导论,41,2.2 感知器概念及其训练方法,设训练样本集X=x1,x2,xn，其中xk属于wi或者wj，且xk的类别是已知的。为了确定加权向量w*，执行下面的训练算法 给定初始值：置k=0，权向量w(k)为任意值，可选常数0c1 输入样本xm x1,x2,xn，计算判决函数值g(xm)=wT(k)xm 按如下规则修改权向量 若xm wi，且g(xm) 0，则w(k+1)=w(k)+cxm 若xm wj，且g(xm) 0，则w(k+1)=w(k)-cxm 令k=k+1，返回第二步，直到w对所有样本稳定不变，结束,42,二、收敛定

12、理： 如果训练模式是线性可分的，感知器训练算法在有限次迭代后便可以收敛到正确的解矢量 。,。,证明思路： 如果第k+1次迭代生成的权矢量比第k次迭代生成的权矢量更接近解矢量，则收敛，即：,2020/7/23,模式识别导论,43,例子1,已知两类训练样本，(0,0),(0,1)属于w1，(1,0),(1,1)属于w2，试用感知器算法求解w* 训练样本分量增广化以及符号规范化。将训练样本增加一个分量1，且把来自w2的样本各分量乘以-1，得到训练模式集x1=(0,0,1), x2=(0,1,1), x3=(-1,0,-1), x4=(-1,-1,-1) 运用训练算法，给权向量赋初值w(1)=(1,1

13、,1)T，取增量c=1，置迭代步数k=1，下面是迭代过程,2020/7/23,模式识别导论,44,例子1,K=1,xm=x1,w(k)Txm=10,w(2)=w(1) K=2, xm=x2,w(k)Txm=20,w(3)=w(2) K=3, xm=x3,w(k)Txm=-20,w(9)=w(8),2020/7/23,模式识别导论,45,例子1,K=9,xm=x1,w(k)Txm=0,w(10)=w(9) + x1=(-2,1,1)T K=10, xm=x2,w(k)Txm=20,w(11)=w(10) K=11, xm=x3,w(k)Txm=10,w(12)=w(11) K=12, xm=x4

14、,w(k)Txm=0,w(13)=w(12)+ x4=(-3,0,0)T K=13, xm=x1,w(k)Txm=0,w(14)=w(13)+ x1=(-3,0,1)T K=14, xm=x2,w(k)Txm=10,w(15)=w(14) K=15, xm=x3,w(k)Txm=20,w(16)=w(15) K=16, xm=x4,w(k)Txm=20,w(17)=w(16) K=17, xm=x1,w(k)Txm=10,w(18)=w(17),2020/7/23,模式识别导论,46,例子1,通过上面的结果可以看出，经过对x1, x2, x3, x4一轮迭代后，使用w(14)已经能够对所有训练

15、样本正确分类，增广权矢量的值不再发生变化，所以算法收敛于w(14)， w(14)就是所求的解向量，即w*=(-3,0,1)T。由此可以得到区分界面为：-3x1+1=0,采用多类情况3的方法时，应有：,2. 感知器算法用于多类情况,对于M类模式应存在M个判决函数：,算法主要内容：,设有 M 种模式类别：,设其权向量初值为：,第k次迭代时，一个属于i类的模式样本 X 被送入分类器， 计算所有判别函数,训练样本为增广向量形式，但不需要规范化处理。,分二种情况修改权向量：, 若第l个权向量使 ，则相应的权向量作调整，即：,可以证明：只要模式类在情况3判别函数时是可分的，则 经过有限次迭代后算法收敛。,

16、， c为正的校正增量,例3.9 设有三个线性可分的模式类，三类的训练样本分别为, 若 则权向量不变；,现采用多类情况3的方式分类，试用感知器算法求出判别函数。,解：增广向量形式：,注意，这里任一类的样本都不能乘以（1）。,任取初始权向量,；c=1,第一次迭代：,三个权向量都需要修改：,第二次迭代：,第三次迭代：,修改为权向量。,以上进行的一轮迭代运算中，三个样本都未正确分类，进 行下一轮迭代。,第四次迭代： ,在第五、六、七迭代中，对所有三个样本都已正确分类。,权向量的解：,判别函数：,2020/7/23,模式识别导论,52,2.2.3 感知器准则函数及其梯度法,在两类样本线性可分的情况下，通

17、过上面的例子可知，如果将属于wj的样本各分量同时乘以-1，则可以由所有满足wTx0的样本求出解w*，即可确定决策函数。 但是，对于求解问题，可能存在多个可行解，因此问题进一步转化成如何按一定条件利用优化算法求得最优解的问题。 感知器准则函数与梯度法。,2020/7/23,模式识别导论,53,2.2.3 感知器准则函数及其梯度法,梯度法 采用最优化技术求线性判别函数中的增广权向量，首先需要构造准则函数。其次再通过优化算法求得最优解，这里选用梯度法求解。 一个可微函数某点的梯度给出函数在该点的变化率最大的方向；负梯度给出下降最快的方向。那么对于有极小值的函数而言，可以沿着负梯度的方向选择适当的步长

18、进行搜索，求解函数的极小值点。,2020/7/23,模式识别导论,54,梯度法 如果我们定义一个准则函数J(w,x)，它的最小值对应着最优解w*，那么完全可以运用数学分析中这种求极值的方法来进行求解，这便是梯度法的基本思想。 由于是迭代算法，所以它有一个迭代公式，并且可以找到数值解。迭代公式如下：,2.2.3 感知器准则函数及其梯度法,2020/7/23,模式识别导论,55,感知器准则函数 构造准则函数如下： 当|wTx|- wTx=0，该准则函数可以达到最小值，此时有wTx0，所以可以得到最优解，也就是最优权向量w*。,2.2.3 感知器准则函数及其梯度法,2020/7/23,模式识别导论,

19、56,感知器准则函数 当p=c时，梯度下降法与感知器训练算法的修正公式一致，因此感知器训练算法是梯度下降法的一种特例，一般将p为常数的梯度法称为固定增量法。 当p在迭代运算时随k变化，称为可变增量法。,2.2.3 感知器准则函数及其梯度法,2.7 最小平方误差算法,（least mean square error, LMSE；亦称Ho-Kashyap算法）,上述的感知器算法、梯度算法、固定增量算法或其他类 似方法，只有当模式类可分离时才收敛，在不可分的情况下， 算法会来回摆动，始终不收敛。当一次次迭代而又不见收敛 时，造成不收敛现象的原因分不清，有两种可能：,a) 迭代过程本身收敛缓慢 b)

20、模式本身不可分,对可分模式收敛。 对于类别不可分的情况也能指出来。,LMSE算法特点：,2020/7/23,模式识别导论,58,2.3 最小平方误差准则,在两类样本线性可分的情况下，如果将属于wj的样本各分量同时乘以-1，则应该有权向量w，对所有样本满足wTxi 0，设计分类器就是求解一组线性不等式。 如果任意给定一个向量b=b1,b2,bnT0，那么上述问题可以转化成求解w，使之满足wTxibi。,2020/7/23,模式识别导论,59,2.3 最小平方误差准则,设分别属于wi与wj的样本数为n1与n2，n= n1+n2 W为d+1维列向量，通常有：nd+1，那么方程是没有精确解存在的。 定

21、义误差向量：e=xw-b 最小平方误差准则函数如下：,2020/7/23,模式识别导论,60,2.3 最小平方误差准则,此时的w*并不是最小平方误差准则函数下的解，因为w*还依赖于b。 根据平方误差准则函数，使用固定增量的梯度下降法建立b的迭代公式如下（即b的初始值可以任意给定）。,1. 分类器的不等式方程,上式分开写为：,写成矩阵形式为 ：,令N (n+1) 的长方矩阵为X，则 变为：,式中：,0为零向量,感知器算法是通过解不等式组 ，求出W。,2. LMSE算法,1) 原理,的求解。式中：, 两式等价。,为各分量均为正值的矢量。,LMSE算法把对满足 XW 0 的求解，改为满足,准则函数定

22、义为：,“最小二乘”： 最小：使方程组两边误差最小， 也即使J最小。 二乘：次数为2，乘了两次,考察向量(XWB) 有：,可以看出： 当函数J达到最小值，等式XW=B有最优解。即又将问题转化为求准则函数极小值的问题。 因为J有两个变量W和B，有更多的自由度供选择求解，故可望改善算法的收敛速率。,XW=B 的近似解也称“最优近似解”： 使方程组两边所有误差之和最小（即最优）的解。,准则函数：,使J 对W求最小，令 ，得：,2) 推导LMSE算法递推公式,与问题相关的两个梯度：,(3-46),(3-47),由(3-47)式可知：只要求出B，就可求出W。,求递推公式：,(1) 求W 的递推关系,X为

23、N(n+1)长方阵，X#为(n+1) N 长方阵。,称为X的伪逆，,式中：,(3-45),(2) 求B(k+1)的迭代式,(3-46)代入，得,令,，定义,(3-49),(3-50),(3) 求W(k+1)的迭代式,将(3-50)代入(3-47)式W=X#B 有：,总结：设初值B(1)，各分量均为正值，括号中数字代表迭代次数 。,W(k+1)、B(k+1)互相独立，先后次序无关。,求出B，W后，再迭代出下一个e，从而计算出新的B， W。,或另一算法：先算B(k+1)，再算W(k+1)。,3）模式类别可分性判别, 如果e(k)0 ，表明XW(k)B(k) 0， 隐含有解。继续迭代， 可使e(k)

24、 0 。, 如果e(k)0（所有分量为负数或零，但不全为零），停止迭 代，无解。此时若继续迭代，数据不再发生变化。,可以证明：当模式类线性可分，且校正系数c满足 时，该算法收敛，可求得解W。,理论上不能证明该算法到底需要迭代多少步才能达到收 敛，通常在每次迭代计算后检查一下XW(k) 和误差向量e(k) ， 从而可以判断是否收敛。, 如果e(k)=0 ，表明XW(k)=B(k) 0，有解。,分以下几种情况：,情况分析：,e(k)0,综上所述：只有当e(k)中有大于零的分量时，才需要继续迭 代，一旦e(k)的全部分量只有0和负数，则立即停止。事实上，往 往早在e(k)全部分量都达到非正值以前，就

25、能看出其中有些分量 向正值变化得极慢，可及早采取对策。,通过反证法可以证明：在线性可分情况下，算法进行过程中不会出现 e(k)的分量全为负的情况；若出现e(k)的分量全为负，则说明模式类线性不可分。,4) LMSE算法描述,(1) 根据N个分属于两类的样本，写出规范化增广样本矩阵X。,(2) 求X的伪逆矩阵 。,(3) 设置初值c和B(1)，c为正的校正增量，B(1)的各分量大于零， 迭代次数k=1 。开始迭代：,计算,(4) 计算 ，进行可分性判别。,如果e(k)0，线性可分，若进入(5)可使e(k) 0 ，得最优解。,如果e(k)0，线性不可分，停止迭代，无解，算法结束。,如果e(k)=0

26、，线性可分，解为W(k)，算法结束。,否则，说明e(k)的各分量值有正有负，进入(5)。,(5) 计算W(k+1)和B(k+1)。,方法1：分别计算,方法2：先计算,再计算,迭代次数k加1，返回(4)。,3. 算法特点,(1) 算法尽管略为复杂一些，但提供了线性可分的测试特征。,(2) 同时利用N个训练样本，同时修改W和B，故收敛速度快。,(3) 计算矩阵 复杂，但可用迭代算法计算。,例3.11 已知两类模式训练样本：,试用LMSE算法求解权向量。,解：(1) 写出规范化增广样本矩阵：,Aij是aij的代数余子式，注意两者的行和列的标号互换。,(2) 求伪逆矩阵,求逆矩阵：,划去aij所在的行

27、和列的元素，余下元素构成的行列式做aij的余子式，记作Mij ，将 叫做元素aij的代数余子式。例：,代数余子式定义：,行列式:,(3) 取 和 c=1 开始迭代：,.,解为 W(1) ，判断函数为：,图示如下：,例3.12 已知模式训练样本： ，,( 2) 求 ：,解：(1) 规范化增广样本矩阵：,(3) 取 和c=1，迭代：,用LMSE算法求解权向量。,e(1)全部分量为负，无解，停止迭代。为线性不可分模式。,小结：,(1) 感知器法、梯度法、最小平方误差算法讨论的分类算法 都是通过模式样本来确定判别函数的系数，所以要使一个分 类器设计完善，必须采用有代表性的数据，训练判别函数的 权系数。

28、它们能合理反映模式数据的总体。,(2) 要获得一个有较好判别性能的线性分类器，所需要的训 练样本的数目的确定。,用指标二分法能力N0来确定训练样本的数目：,通常训练样本的数目不能低于N0 ，选为 N0的510倍左右。,二维：不能低于6个样本，最好选在3060个样本之间。 三维：不能低于8个样本，最好选在4080个样本之间。,n为模式维数,如,2020/7/23,模式识别导论,85,2.4 Fisher线性判别准则,2020/7/23,模式识别导论,86,2020/7/23,模式识别导论,87,2020/7/23,模式识别导论,88,2020/7/23,模式识别导论,89,2.4 Fisher线

29、性判别准则,是将d维空间的样本映射到了一维样本集，这个一维空间的方向是相对于Fisher准则为最好的。 我们还需要解决分类问题。将d维分类问题转化为一维分类问题后，只需要确定一个阈值点，将投影点与阈值点比较，就可以做出决策。,90,2.4 Fisher线性判别,91,二维模式向一维空间投影示意图,92,二维模式向一维空间投影示意图,93,二维模式向一维空间投影示意图,o,x,y,o,x,y,94,（1)求解Fish准则函数,95,96,类间离差度为：,97,并使其最大,上式称为Fisher准则函数。,98,利用二次型关于矢量求导的公式可得：,（2) 求解Fisher最佳鉴别矢量,令,可得：,99,100,上式右边后两项因子的乘积为一标量，令其为 ，于是可得 式中 为一标量因子，其不改变轴的方向，可以取为1,于是有,101,此时的 可使Fisher准则函数取最大值，即是n 维空间到一维空间投影轴的最佳方向，由,和,JF 最大值为:,102,即 称 为Fisher变换函数,JF=,103,由于变换后的模式是一维的，因此判别界面实际上是各类模式所在轴上的一个点，所以可以根据训练模式确定一个阈值 yt，于是Fisher判别规则为:,（3) 求解Fisher判别函数,判别阈值可取两个类心