《模式识别理论及应用》由会员分享，可在线阅读，更多相关《模式识别理论及应用（45页珍藏版）》请在金锄头文库上搜索。
1、武汉大学电子信息学院第四章 线性判别函数模式识别理论及应用Pattern Recognition - Methods and Applicationa内容目录第四章 线性判别函数67 4.2 Fisher线性判别34.3 感知器准则4.5 多类问题4.6 分段线性判别函数 5 4.1 引言144.4 最小平方误差准则模式识别与神经网络4.7 讨论2a4.1 引言基于基于样样本的本的BayesBayes分分类类器：通器：通过过估估计类计类条条件概率密度函数，件概率密度函数，设设计计相相应应的判的判别别函数函数MAXMAXg g1 1.g g2 2g gc c.x1x2xna(x) 最一般情况下适
2、用的最一般情况下适用的“ “最最优优” ”分分类类器：器：错误错误率最小，率最小，对对分分类类器器设计设计在理在理论论上有上有指指导导意意义义。 获获取取统计统计分布及其参数很分布及其参数很困困难难，实际问题实际问题中并不一中并不一定具定具备获备获取准确取准确统计统计分布分布的条件。的条件。 训练样训练样本集本集样样本分布的本分布的统计统计特征：特征：概率密度函数概率密度函数决策决策规则规则：判判别别函数函数决策面方程决策面方程分类器功能结构3a直接确定判别函数uu基于样本的直接确定判别函数方法：针对针对各种不同的情况，使用不同的准各种不同的情况，使用不同的准则则函数，函数，设计设计出出满满足
3、足这这些不同准些不同准则则要求的分要求的分类类器。器。这这些准些准则则的的“ “最最优优” ”并不一定与并不一定与错误错误率最小相一率最小相一致：次致：次优优分分类类器。器。 实实例：正例：正态态分布最小分布最小错误错误率率贝贝叶斯分叶斯分类类器在特器在特殊情况下，是殊情况下，是线线性判性判别别函数函数g g( (x x)=)=wwT Tx x（决策（决策面是超平面），能否基于面是超平面），能否基于样样本直接确定本直接确定ww? ?引言引言训练样训练样本集本集决策决策规则规则：判判别别函数函数决策面方程决策面方程选择最佳准则4a线性判别函数uud d维维空空间间中的中的线线性判性判别别函函数的
4、一般形式：数的一般形式：uux x是是样样本向量，即本向量，即样样本在本在d d维维特征空特征空间间中的描述，中的描述， ww是是权权向向量，量，ww0 0是一个常数是一个常数( (阈值权阈值权) )。uu两两类问题类问题的分的分类类决策决策规则规则: :引言引言5a线性判别函数的几何意义uu决策面决策面(decision boundary)H(decision boundary)H方程：方程：g g( (x x)=0)=0uu向量向量ww是决策面是决策面H H的法向量的法向量uug g( (x x) )是点是点x x到决策面到决策面H H的距离的一种代数度量的距离的一种代数度量引言引言x1x
5、2wxxprH: g=06a广义线性判别函数uu线线性判性判别别函数是形式最函数是形式最为简单为简单的判的判别别函数，但是它函数，但是它不能用于复不能用于复杂杂情况。情况。 例：例：设计设计一个一一个一维维分分类类器，使其功能器，使其功能为为： uu二次函数的一般形式：uug(x)又可表示成： 引言引言映射XY7a广义线性判别函数(2)uu按照上述原理，任何非按照上述原理，任何非线线性函数性函数g g( (x x) )用用级级数展开成高次多数展开成高次多项项式后，都可式后，都可转转化成化成线线性判性判别别函数来函数来处处理。理。uu一种特殊映射方法：一种特殊映射方法：增广增广增广增广样样样样本
6、向量本向量本向量本向量y y与增广与增广与增广与增广权权权权向量向量向量向量a auu线线性判性判别别函数的函数的齐齐次次简简化：化： uu增广增广样样本向量使特征空本向量使特征空间间增加了一增加了一维维，但保持了，但保持了样样本本间间的的欧氏距离不欧氏距离不变变，对对于分于分类类效果也与原决策面相同，只是在效果也与原决策面相同，只是在Y Y空空间间中决策面是通中决策面是通过过坐坐标标原点的，原点的，这这在分析某些在分析某些问题时问题时具具有有优优点，因此点，因此经经常用到。常用到。 引言引言8a线性分类器设计步骤uu线线性分性分类类器器设计设计任任务务：给给定定样样本集本集K K，确定，确定
7、线线性性判判别别函数函数g g( (x x)=)=w wT Tx x的各的各项项系数系数ww。步。步骤骤：1.1.收集一收集一组样组样本本K K=x x1 1, ,x x2 2,x xNN 2.2.按需要确定一准按需要确定一准则则函数函数J J( (K K, ,ww) )，其，其值值反映分反映分类类器的性器的性能，其极能，其极值值解解对应对应于于“ “最好最好” ”决策。决策。3.3.用最用最优优化技化技术术求准求准则则函数函数J J的极的极值值解解ww* *，从而确定判，从而确定判别别函数，完成分函数，完成分类类器器设计设计。uu对于未知样本x，计算g(x)，判断其类别引言引言9a4.2 F
8、isher线性判别uu线性判别函数y=g(x)=wTx:样样本向量本向量x x各分量的各分量的线线性加性加权权样样本向量本向量x x与与权权向量向量ww的向量点的向量点积积如果如果| | ww |=1 |=1，则视则视作向量作向量x x在向量在向量ww上的投影上的投影 uuFisher准则的基本原理：找到一个最合适的投影轴，使两类样本在该轴上投影之间的距离尽可能远，而每一类样本的投影尽可能紧凑，从而使分类效果为最佳。10aFisher线性判别图例FisherFisher判判别别x1x2w1H: g=0w2FisherFisher准准则则的描述：用投影后数据的的描述：用投影后数据的统计统计性性质
9、质均均值值和离散度的函数作和离散度的函数作为为判判别优别优劣的劣的标标准。准。11ad维空间样本分布的描述量FisherFisher判判别别uu各各类样类样本均本均值值向量向量mmi iuu样样本本类类类类内离散度内离散度内离散度内离散度矩矩阵阵S Si i与与总类总类内离散度矩内离散度矩阵阵S Sww uu样样本本类间类间类间类间离散度离散度离散度离散度矩矩阵阵S Sb b：离散矩阵在形式上与协方差矩阵很相似，但协方差矩阵是一种期望值，而离散矩阵只是表示有限个样本在空间分布的离散程度12a一维Y空间样本分布的描述量FisherFisher判判别别uu各类样本均值uu样样本本类类内离散度和内离
10、散度和总类总类内离散度内离散度uu样样本本类间类间离散度离散度 以上定义描述d维空间样本点到一向量投影的分投影的分散情况散情况，因此也就是对某向量w的投影在w上的分布。样本离散度的定义与随机变量方差相类似 13a样本与其投影统计量间的关系FisherFisher判判别别uu样本x与其投影y的统计量之间的关系：14a样本与其投影统计量间的关系FisherFisher判判别别15aFisher准则函数FisherFisher判判别别uu评评价投影方向价投影方向w w的原的原则则，使原，使原样样本向量在本向量在该该方向上方向上的投影能兼的投影能兼顾类间顾类间分布尽可能分开，分布尽可能分开，类类内内样
11、样本投影本投影尽可能密集的要求尽可能密集的要求uuFisherFisher准准则则函数的定函数的定义义：uuFisherFisher最佳投影方向的求解最佳投影方向的求解16aFisher最佳投影方向的求解FisherFisher判判别别uu采用拉格朗日乘子算法解决 m1-m2是一向量，对与(m1-m2)平行的向量投影可使两均值点的距离最远。但是如从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对m1-m2 向量按Sw-1作一线性变换，从而使Fisher准则函数达到极值点17a判判别别函数的确定函数的确定uu前面讨论
12、了使Fisher准则函数极大的d维向量w*的计算方法，判别函数中的另一项w0（阈值）可采用以下几种方法确定： uu分类规则:FisherFisher判判别别18aFisher公式的推导FisherFisher判判别别19a4.3 感知器准则uu感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。20a基本概念uu感知器：感知器：PerceptronPerceptron，RosenblattRosenblatt，50d/
13、2050d/20ththc cuu线线性可分性：性可分性：训练样训练样本集中的两本集中的两类样类样本在特征空本在特征空间间可以用一个可以用一个线线性分界面正确无性分界面正确无误误地分开。在地分开。在线线性可性可分条件下，分条件下，对对合适的合适的( (广广义义) )权权向量向量a a应应有：有：uu规规范化范化样样本向量本向量 ：将第二：将第二类样类样本取其反向向量本取其反向向量 感知器感知器准准则则21a解向量与解区感知器感知器准准则则22a感知器准则函数uu对于任何一个增广权向量a ，对样对样本本y y正确分正确分类类，则则有：有：a aT Ty y0 0 对样对样本本y y错误错误分分类
14、类，则则有：有：a aT Ty y00uu定义一准则函数JP(a) (感知准则函数)： 感知器感知器准准则则被错分类的规范化增广样本集uu恒有恒有J JP P( (a a)0)0，且，且仅仅当当a a为为解向量，解向量，Y Yk k为为空集（不空集（不存在存在错错分分样样本）本）时时， J JP P( (a a)=0)=0，即达到极小，即达到极小值值。确定向量确定向量a a的的问题变为对问题变为对J JP P( (a a) )求极小求极小值值的的问题问题。23a梯度下降算法uu梯度下降算法：对(迭代)向量沿某函数的负梯度方向修正，可较快到达该函数极小值。 感知器感知器准准则则24a算法(ste
15、p by step)感知器感知器准准则则1. 初值: 任意给定一向量初始值a(1)2. 迭代: 第k+1次迭代时的权向量a(k+1)等于第k次的权向量a(k)加上被错分类的所有样本之和与rk的乘积3. 终止: 对所有样本正确分类任意给定一向量初始值a(1)a(k+1)=a(k)+ rkSum(被错分类的所有样本)所有样本正确分类得到合理的a完成分类器设计NY25a感知器方法例解 uu固定增量法与可固定增量法与可变变增量法增量法uu批量批量样样本修正法与本修正法与单样单样本本修正法修正法 单样单样本修正法：本修正法：样样本集本集视为视为不断重复出不断重复出现现的序列，逐个的序列，逐个样样本本检查
16、检查，修正，修正权权向量向量 批量批量样样本修正法：本修正法：样样本成批本成批或全部或全部检查检查后，修正后，修正权权向量向量感知器感知器准准则则26a感知器方法小结uu感知准则函数方法的思路是：先随意找一个初始向量a(1)，然后用训练样本集中的每个样本来计算。若发现一个y出现aTy0。当然，修改后的a(k+1)还可以使某些y出现a(k+1)Ty 0, i=1,N0, i=1,Nuu线线性分性分类类器器设计设计求一求一组组N N个个线线性不等式的解性不等式的解uu样样本集本集增广矩增广矩阵阵Y Y及及一一组组N N个个线线性不等式的的性不等式的的矩矩阵阵表示：表示：uu引入余量引入余量( (目
17、目标标向量向量) ) b b=b b1 1, , b b2 2, , , , b bNN T T， b bi i任意任意给给定正常数，定正常数， a aT Ty yi i = = b bi i 0 0uuN N个个线线性方程的的性方程的的矩矩阵阵表示：表示：28a平方误差准则函数uu定定义误义误差向量差向量 e e=Y Ya a- -b b：uu定定义义平方平方误误差准差准则则函数函数J Js s( (a a):):MSEMSE准准则则uu最小二乘近似解（最小二乘近似解（MSEMSE解）：解）：MSE方法的思想：对每个样本，设定一个“理想”的判别函数输出值，以最小平方误差为准则求最优权向量29
18、aMSE准则函数的伪逆解MSEMSE准准则则Y Y的的伪伪逆矩逆矩阵阵30aMSE方法与Fisher方法的关系uu与Fisher方法的关系：当MSEMSE准准则则N1个N2个MSE解等价于Fisher解31aMSE方法与Bayes方法的关系MSEMSE准准则则uu当N，b b=u uNN= 1,1, = 1,1, , 1, 1T T 时，则它以最小均方误差逼近Bayes判别函数：32aMSE方法的迭代解uua*=Y+b, Y+=(YTY)-1-1YT，计算量大uu实际中常用梯度下降法：MSEMSE准准则则批量样本修正法单样本修正法33a4.5 多类问题uu两两类别问题类别问题可以推广到多可以推
19、广到多类别问题类别问题 i i/ / i i 法：法：将将C C类别问题类别问题化化为为( (C C-1)-1)个两个两类类（第（第i i类类与与所有非所有非i i类类）问题问题，按两，按两类问题类问题确定其判确定其判别别函数与决策面函数与决策面方程方程 i i/ /j j 法：法：将将C C类类中的每两中的每两类别单类别单独独设计设计其其线线性判性判别别函函数，因此数，因此总总共有共有C C( (C C-1)/2-1)/2个个线线性判性判别别函数函数 R1R3R21非非12非非2R1R3R212133234a多类线性判别函数uu将特征空间确实划分为c个决策域，共有c个判别函数多多类类问题问题
20、uu决策规则：uu决策域的决策域的边边界由相界由相邻邻决策域的判决策域的判别别函数共同决定，函数共同决定，此此时应时应有有g gi i( (x x)=)=g gj j( (x x) ) uu线线性分性分类类器的决策面是凸的，决策区域是器的决策面是凸的，决策区域是单连单连通的通的uu多多类类分分类类器的分界面是分段器的分界面是分段线线性的性的35a多类线性决策面图例R1R3R2g g1 1gg2 2g g1 1gg3 3g g3 3gg1 1g g3 3gg2 2g g2 2gg3 3g g2 2gg1 1R1R3R2R5R4多多类类问题问题36a决策树简介uu决策决策树树：一种多极分：一种多极
21、分类类器，它采用分器，它采用分级级的形式，的形式，综综合用多个决策合用多个决策规则规则，逐步把复逐步把复杂杂的多的多类别类别分分类问题转类问题转化化为为若干个若干个简简单单的分的分类问题类问题来解决来解决多多类类问题问题n1n2n3n4n5t1t2t3t4t5t6t737a二叉决策树uu二叉决策二叉决策树树：除叶：除叶节节点点外，决策外，决策树树的每个的每个节节点点n ni i都有且只有两个子都有且只有两个子节节点点n nil il和和n nir ir。二叉决策。二叉决策树树把复把复杂杂的多的多类别类别分分类问类问题转题转化化为为多极两多极两类类分分类类问题问题来解决。在每个来解决。在每个节节
22、点点n ni i ，都把，都把样样本集分成本集分成两个子集。每个子集可两个子集。每个子集可能仍包含多能仍包含多类别类别的的样样本，本，继续继续分直至分直至仅仅包含包含单类单类别样别样本的叶本的叶节节点点多多类类问题问题n1n2n3n4t1t2t5x25x12x34x2212323t3t438a4.6 分段线性判别函数 uu有些复杂模式识别问题不是线性可分的，需使用非线性的分类方法uu分段线性判别函数：一种特殊的非线性判别函数，它的决策面是若干超平面uu树分类器的各节点上采用线性判别规则，即构成分段线性分类器R1R3R2IIIIIII IIIIII: I: 线线性判性判别别IIII：分段：分段线
23、线性判性判别别III: III: 二次判二次判别别39a基于距离的分段线性判别函数 uu最小距离分最小距离分类类器：把各器：把各类别样类别样本特征的均本特征的均值值向量作向量作为为各各类类的代表点的代表点(prototype)(prototype) ，根据待，根据待识样识样本到各本到各类别类别代表点的最代表点的最小距离判小距离判别别其其类别类别。决策面是两。决策面是两类别类别均均值连线值连线的垂直平分的垂直平分面面uu分段分段线线性距离分性距离分类类器：将各器：将各类别类别划分成相划分成相对对密集的子密集的子类类，每个子每个子类类以它以它们们的均的均值值作作为为代表点，然后按最小距离分代表点，
24、然后按最小距离分类类 uu判判别别函数定函数定义义：i i有有l li i个子个子类类，即属于，即属于i i 的决策域的决策域R Ri i分成分成l li i个子域个子域R Ri i1 1, , R Ri i2 2, , R Ri ili li) )，每个子区域用均，每个子区域用均值值mmi ik k代表点代表点分段分段线线性判性判别别uu判判别规则别规则：or40a分段线性距离分类器图例分段分段线线性判性判别别m1m2xg(x)=0m1m2x41a分段分段线线性判性判别别函数函数 uu分段分段线线性判性判别别函数的一般形式函数的一般形式: : g gi ik k( (x x) )表示第表示第
25、i i类类第第k k段段线线性判性判别别函数，函数，l li i为为i i类类所具有的判所具有的判别别函数个数，函数个数，wwi ik k与与wwi0i0k k分分别别是是第第k k段的段的权权向量与向量与阈值权阈值权 分段分段线线性判性判别别uu第第i i类类的判的判别别函数函数: :uu判判别规则别规则: :uu决策面取决于相决策面取决于相邻邻的决策域，如第的决策域，如第i i类类的第的第n n个子个子类类与第与第j j类类的第的第mm个子个子类类相相邻邻，则则由它由它们们共同决定的决策面方程共同决定的决策面方程为为 42a4.7 讨论uu基于样本的直接确定判别函数方法主要包含两个步骤：1
26、.确定使用的判确定使用的判别别函数函数类类型或决策面方程型或决策面方程类类型，型，如如线线性分性分类类器，分段器，分段线线性分性分类类器等器等2.在在选选定函数定函数类类型的条件下，确定相型的条件下，确定相应应的参数，的参数，从而完成整个分从而完成整个分类类器器设计设计uu线性判别函数计算简单，在一定条件下能实现最优分类，经常是一种“有限合理”的选择uu分段线性分类器可以实现更复杂的分类面43a习题1.1.有一个三次判有一个三次判别别函数：函数：z z= =g g( (x x)=)=x x3 3+2+2x x2 2+3+3x x+4+4。试试建立一映射建立一映射x xy y，使得，使得z z转
27、转化化为为y y的的线线性判性判别别函数。函数。2.2.证证明决策面明决策面H H：w wT Tx x+w+w0 0=0=0的系数向量的系数向量ww是决策面是决策面H H的法向量的法向量3.3.Ex-4.15Ex-4.154.4.设设五五维维空空间间的的线线性方程性方程为为5555x x1 1+68+68x x2 2+32+32x x3 3+16+16x x4 4+26+26x x5 5+10 =0+10 =0，试试求出其求出其权权向量与向量与样样本向量点本向量点积积的表达式的表达式w wT Tx x+ +w w0 0=0=0中的中的w w，x x以及增广以及增广权权向量与增广向量与增广样样本向量形式本向量形式a aT Ty y中的中的a a与与y y44a习题（续）5.5.设在三维空间中一个类别分类问题拟采用二次曲面。如欲采用广义线性方程求解，试问其广义样本向量与广义权向量的表达式，其维数是多少？45a
