第4章非参数判别分类方法(线性判别函数)

1、 模 式 识 别 徐蔚然北京邮电大学信息工程学院北京邮电大学信息工程学院非参数判别分类方法 n包括内容n第4章 线性判别函数n第5章 非线性判别函数n第6章 近邻法n第11章 人工神经网络n第13章 统计学习理论和支持向量机学习目的学习目的 n(1) 掌握非参数判别分类法的原理n(2) 掌握机器自学习的原理n(3) 学习线性分类器的典型算法n(4) 用近邻法进行分类(第六章)n(5) 通过相应数学工具的运用进一步提高运用数学的本领重点重点 n(1) 非参数判别分类器的基本原理n(2) 线性分类器的典型方法n以Fisher准则为代表的传统模式识别方法n以感知准则函数为代表的机器自学习方法n(3)

2、 线性分类器扩展到非线性分类器n(4) 近邻法的工作原理及其改进 难点难点 n(1) Fisher准则函数，其中用到向量点积，带约束条件的拉格朗日乘子法以及矩阵的特征值、特征向量等数学工具。要求对这些数学工具较深理解。n(2) 感知器准则函数提出利用错误提供信息实现叠代修正的学习原理(3) 近邻法的改进知知识识点点 贝叶斯决策理论和统计判别方法 n采用统计分布来描述来描述d维特征空间中的样本分布n采用分类器中最重要的指标错误率作为产生判别函数和决策面的依据n给出了最一般情况下适用的“最优”分类器设计方法n对各种不同的分类器设计技术在理论上都有指导意义。 n贝叶斯决策理论设计分类器的步骤n过程n

3、首先得到有关样本总体分布的知识n先验概率n类条件概率密度函数n计算出后验概率贝叶斯决策理论和统计判别方法n问题n获取统计分布及其参数这部分是很困难 n实际问题中并不一定具备获取准确统计分布的条件 贝叶斯决策理论和统计判别方法非参数判别分类方法n模式识别的设计过程n主要关键部分: 是设计判别函数、决策面方程的确定过程n模式识别的设计过程改成： 由于这种方法跳过了统计分布的参数估计，没有使用统计参数作为依据，因此也是非参数判别分类方法。非参数判别分类方法。 而以贝叶斯决策方法为基础的方法则称为参数判别方参数判别方法法。 非参数判别分类方法n主要的方法n线性分类器 (第4章)n非线性判别函数 (第5

4、章)n近邻法 (第6章)n人工神经网络(第11章)n支持向量机(第13章)通常的模式识别方法都属于该类别方法非参数判别分类方法n回顾正态分布概率模型的最小错误率贝叶斯分类器n在特殊情况下，判别函数与决策面方程会呈现某些典型的形式 n当各类协方差矩阵都相等时，可得到线性分类器n如果各类样本的分布为等半径的超球体形式，且先验概率相等，则又可得到最小距离分类器n而在正态分布的一般情况下，决策面为超二次曲面形式，属非线性分类器非参数判别分类方法n线性分类器计算最简单，得到广泛重视与深入研究，并在设计分类器时作为优先考虑的类型n对非线性分类器则着重讨论分段线性判别函数的基本概念与基本做法n近邻法是分段线

5、性判别函数的一种典型方法n主要依据: 同类物体在特征空间具有聚类特性的原理n注意: 这些准则的“最优”并不一定与错误率最小相一致非参数判别分类方法n参数与非参数判别方法的重要不同点n参数分类方法: 判别函数及决策面方程的类别确定是由样本分布规律决定的n非参数判别方法: 使用什么典型的分类决策方法要预先由设计者确定，然后利用训练样本集提供的信息确定这些函数中的参数n非参数判别分类方法的两个过程n选择函数类型n确定参数第4章 线性分类器 线性判别函数的基本概念n线性判别函数模式识别方法的基本思想n设计分类器的关键问题是设计判别函数n假设判别函数是线性函数n用训练样本去估计线性判别函数的参数线性判别

6、函数的基本概念n线性判别函数的表示n设样本d维特征空间中描述，则两类别问题中线性判别函数的一般形式可表示成 n其中 而0是一个常数，称为阈值权。 线性判别函数的基本概念n决策规则 ng(X)0就是相应的决策面方程n在线性判别函数条件下它对应d维空间的一个超平面线性判别函数的基本概念线性判别函数的基本概念n向量W的意义n假设在该决策平面上有两个特征向量X1与X2，则应有 n向量W与该平面上任两点组成的向量(X1-X2)正交，因此W就是该超平面的法线向量。线性判别函数的基本概念n向量W的意义n而g(X)也就是d维空间中任一点X到该决策面距离的代数度量n该决策平面将这两类样本按其到该面距离的正负号确

7、定其类别。 线性判别函数的基本概念nw0则体现该决策面在特征空间中的位置 n当w0=0时，该决策面过特征空间坐标系原点n而w00时，则w0/|W|表示了坐标原点到该决策面的距离。 线性判别函数的基本概念线性判别函数的基本概念n线性方程向量表示形式的补充说明n二维空间直线方程: w2X2+w1X1+w0=0 nw2X2+w1X1是向量(w1,w2)和(X1,X2)的点集n注意:一条直线可以对应无穷多个直线方程线性判别函数的基本概念n线性方程的规一化表示方法n我们定义 n则直线方程也可表示为:但参数向量模|W|为1 而WTX就是直线上任一点到W向量的投影 广义线性判别函数 n线性判别函数不能用于稍

8、复杂的情况n例如:欲设计这样一个一维样本的分类器，使其性能为：用线性判别函数显然就无能为力了 图像表示图像表示返回广义线性判别函数n设计新判别函数n辨别函数:g(x)(x-a)(x-b) n相应的决策规则:能达到所要求的分类效果，不再是x的线性函数，而是一个二次函数 辨别函数图像表示广义线性判别函数 n线性判别函数优点n具有形式简单n计算方便的优点n已被充分研究 n希望能将其用适当方式扩展至原本适宜非线性判别函数的领域 广义线性判别函数 n广义线性判别函数n选择一种映射XY，即将原样本特征向量X映射成另一向量Y，从而可以采用线性判别函数的方法。例如对于二次函数情况，其一般式可表示成 如果我们采

9、用映射xY，使广义线性判别函数 n广义线性判别函数n则判别函数g(x)又可表示成n此时g(x)被称为广义线性判别函数，a称为广义权向量。 _广义线性判别函数The mapping y = (1,x,x2)t takes a line and transforms it to a parabola in three dimensions.A plane splits the resulting y-space into regions corresponding to2 categories广义线性判别函数n广义线性判别函数n按照这种原理，任何形式的高次判别函数都可转化成线性判别函数来处理。n这

10、种处理非线性分类器的方法，在支持向量机中得到充分的研究。n产生问题: 维数会增加很多 广义线性判别函数 n一种特殊的映射方法 n将X增广至 广义线性判别函数 n一种特殊的映射方法 n并将g(x)中的W向量与w0统一表示成其中w1，w2，w3.wd为向量w各分量 广义线性判别函数 n一种特殊的映射方法n则线性判别函数g(X)可以表示成 这是广义线性判别函数的一个特例 被称为增广样本向量，称为增广权向量。 广义线性判别函数n一种特殊的映射方法n这样,特征空间增加了一维，但保持了样本间的欧氏距离不变n对于分类效果也与原决策面相同n只是在Y空间中决策面是通过坐标原点的，这在分析某些问题时具有优点 广义

11、线性判别函数n例 一维特征空间的分类器 n其决策面方程为： x-c=0 n经齐次简化后可得： 一维空间中为一个点 此时在二维空间中决策面为一过原点的直线 广义线性判别函数线性分类器设计步骤 n线性分类器设计任务n在给定样本集 条件下，确定线性判别函数的各项系数:n关键问题:n确定所需的准则函数，n用最优化技术确定准则函数的极值解W*及W*0 ，或增广权向量a*。_线性分类器设计步骤 n线性分类器设计步骤n1 按需要确定一准则函数J。 n2 确定准则函数J达到极值时W*及W*0的具体数值，从而确定判别函数，完成分类器设计。Fisher线性判别函数n简介nFisher线性判别函数是研究这类判别函数

12、中最有影响的方法之一。n对线性判别函数的研究就是从R.A.Fisher在1936年发表的论文开始的。Fisher线性判别函数nFisher线性判别函数基本原理n设计线性分类器首先要确定准则函数准则函数，然后再利用训练样本集确定该分类器的参数，以求使所确定的准则达到最佳。 n维数问题: 降低维数n线性判别函数把d维空间映射到1维空间Fisher线性判别函数nFisher线性判别函数基本原理n如果我们只考虑各分量的线性加权和，则它是各样本向量与向量W的向量点积。 n如果向量W的幅度为单位长度，则线性加权和又可看作各样本向量在向量W上的投影。 nFisher的基本问题n在1维直线上不一定能够分开样本

13、n希望在1维直线上不同类别的样本分得越开越好n如何找到这条最好的、最易于分类的投影线Fisher线性判别函数nFisher线性判别函数基本原理Fisher线性判别函数基本原理例nFisher准则就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。n分析w1方向之所以比w2方向优越，可以归纳出这样一个准则 n向量W的方向选择应能使两类样本投影的均值之差尽可能大些 n而使类内样本的离散程度尽可能小这就是Fisher准则函数的基本思路。 Fisher线性判别函数n基本参量n样本在d维特征空间的一些描述量。(1) 各类样本均值向量mi (2) 样本类内离散度矩阵S

14、i与总类内离散度矩阵Sw Fisher线性判别函数n基本参量n样本在d维特征空间的一些描述量。(3) 样本类间离散度矩阵Sb Fisher线性判别函数n基本参量n在一维Y空间(1) 各类样本均值(2) 样本类内离散度 和总类内离散度 Fisher线性判别函数nFisher准则函数但是上式并不是W的显函数，需进一步化为W的显函数。 需要进一步演化 Fisher线性判别函数nFisher准则函数式中的 为:因而 Fisher线性判别函数nFisher准则函数同样 也可推出与W的关系 因此 Fisher线性判别函数nFisher准则函数代入 ，得Fisher线性判别函数n最佳W值的确定n最佳W值的确

15、定实际上就是对JF(W)求取其达极大值时的W* n对于这个问题可以采用拉格朗日乘子算法解决 n为此可设计一拉格朗日函数Fisher线性判别函数n最佳W值的确定n向量W*就是使Fisher准则函数JF(W)达极大值的解，n也就是按Fisher准则将d维X空间投影到一维Y空间的最佳投影方向， n该向量W*的各分量值是对原d维特征向量求加权和的权值 图例Fisher线性判别函数n判别函数的确定n目前的问题讨论了线性判别函数加权向量W的确定方法讨论了使Fisher准则函数极大的W*的计算方法判别函数中的另一项w0尚未确定Fisher线性判别函数n判别函数的确定n确定w0有以下几种方法或 或当P(w1)

16、与P(w2)已知时可用Fisher线性判别函数n判别函数的确定当W0确定之后，则可按以下规则分类， 感知准则函数n简介n感知准则函数是五十年代由Rosenblatt提出的一种自学习判别函数生成方法，n由于Rosenblatt企图将其用于脑模型感知器，因此被称为感知准则函数。n其特点是随意确定的判别函数初始值，在对样本分类训练过程中逐步修正直至最终确定。感知准则函数设计线性分类器是一种十分重要的方法，是学习的重点。 感知准则函数n线性决策面方程另外的形式n感知准则函数使用增广样本向量与增广权向量 nWT+w0=0 改成 aTY=0 感知准则函数在两类别情况下，判别准则是： 为简单起见，我们不考虑

17、g(X)0的情况。 为了讨论原理方便，这一节在线性可分条件下讨论问题，并且只谈两类识别问题。 感知准则函数n线性可分 n线性可分是说该训练样本集中的两类样本可以用一个线性分界面正确无误的分开。n在线性可分条件下，广义权向量a合适的话应有： 感知准则函数为了方便起见，如果我们令 则合适的a能使所有的Y满足需要解决的问题: 找到满足上式的aT_例感知准则函数返回感知准则函数返回感知准则函数n分析n根据训练样本确定增广权向量 an在给定一个规范化增广样本集Y1,YN的条件下，对于任何一个增广权向量a ，可计算n显然如果该向量是一个能将此样本集正确分类的增广权向量，则应有 _感知准则函数n分析n而对可

18、导致错分类的增广权向量，则必有若干个yi ,使 n我们令被错分类的规范化增广样本组成的集用yk表示，并定义一准则函数 感知准则函数n分析n则能将该样本集正确分类的增广权向量a 使得n即达到a极小值。 n因此确定向量的问题变为求极小值的问题 n这个准则函数 就是感知准则函数 _感知准则函数n求准则函数的极小值n可以采用迭代法进行n一个常用的方法是梯度下降算法n即对第k次迭代值，求其梯度向量，n并令迭代向量沿此负梯度向量方向修正，可以较快速度到达其极小值 感知准则函数n求准则函数的极小值n将准则函数对a求偏导数，得 n可见感知准则函数的梯度向量是所有被错分类的规范化增广样本向量之和n将迭代公式写成_步长系数 感知准则