《模式识别方法总结课件》由会员分享，可在线阅读，更多相关《模式识别方法总结课件（60页珍藏版）》请在金锄头文库上搜索。
1、机器实现自动分类有两大类方法： 模板匹配 对特征空间划分子空间(每类的势力范围) 这里是针对第二种方法而言的。,分类方法总结,贝叶斯判别：基于样本概率，若无概率信息，需参数估计。 非参数判别：利用样本直接计算判决函数中的有关参数。 监督（有教师）：利用某些已知类别的样本进行分类。 Fisher线性判别 近邻分类 无监督ANN SVM 非监督（无教师）：聚类分析、自组织竞争神经网络,非参数判别的思路：设定一组判别函数, 并利用样本直接计算判决函数中的有关参数。,贝叶斯判别的核心问题是： 样本为特征向量X时，它属于哪一类可能性有多大。如能确定属于各个类别的百分比(概率)，分类决策就有了依据。,最大
2、后验概率判决准则 最小风险贝叶斯判决准则,如果P(1|x)P(2|x), 则判决x属于1; 如果P(1|x)P(2|x), 则判决x属于2; 如果P(1|x)=P(2|x), 则判决x属于1或属于2。 这种决策称为最大后验概率判决准则, 也称为贝叶斯(Bayes)判决准则。 假设已知P(i)和p(x|i)(i=1, 2, , m), 最大后验概率判决准则就是把样本x归入后验概率最大的类别中, 也就是, ,则xj。,最大后验概率判决准则,几种最大后验概率判决准则的等价形式: (1) 若,，则xj;,(2) 若,，则xj;,(3) 若,则xj。其中, L(x)称为似然比，lnL(x)称为对数似然比
3、。,由于已知P(i)和p(x|i), 因此我们希望找到P(i|x)与它们之间的关系。假设特征变量为X，由Bayes公式,在最大后验概率判决准则中, xj的决策区域Rj为,(j=1, 2, , m),最大后验概率判决准则的一个优良性质就是使平均错误概率达到最小。 因此, 最大后验概率判决准则又称为最小错误概率判决准则。,基于最小错误概率的贝叶斯决策理论就是按后验概率的大小作判决的。,类条件概率密度通过计算，换算成如下图所示的后验概率分布。可以看出，在X值小时，判断为1 类是比较合理的，判断错误的可能性小。,例如, 假设模式x为一维的情况, 得到的两类分界点为t, 将x轴分为两个区域R1和R2,
4、其中, 纹理区域的面积表示平均错误概率, 即,图中，,，,图2-2 平均错误概率计算示意图,在作出决策时，要考虑所承担的风险。基于最小风险的贝叶斯决策的基本思路是给每一种决策规定一个损失值(或代价), 将其作为因错误决策而导致的损失的度量。,最小风险贝叶斯判决准则,(1) 决策j: 将样本x的类别判为第j类。,(2) 损失函数(j, i): 对真实类别为第i类的样本采取决策j所带来的损失。,(3) 条件风险,当样本x的真实类别未知时, 决策j的条件风险是对 x 为所有可能的真实类别条件下将样本判为第j类的代价求平均, 即,最小风险贝叶斯判决准则: ,如果,则判决xk。,考虑两类别一维特征向量情
5、况，R1与R2两个区域的分界线不再是t，而是向左移了一段距离（t1)。这是由于损失函数12比21大所造成。在发生位移这一区域内，尽管P(x|1)P(1)P(x|2)P(2)，但是为了减少将2错判为1所带来的严重损失，在P(x|2)P(2)不很小的情况下，使将2类样本错判为1的可能性减小，以减小决策所承担的风险。当然平均错误率则明显增大了。,线性分类器 Fisher线性判决 分段线性分类器 近邻分类器 有教师训练的ANN SVM,监督（有教师）分类方法,线性判别函数的形式如下:,线性分类器设计的关键在于确定权向量w和阈值权w0。,线性判别函数,常数,其几何意义为d维欧几里德空间中的一个超平面。,
6、(1) w是超平面的法向量。 对于两类分类问题, 线性判决函数的几何意义在于利用一个超平面实现对特征空间Rd的划分。,超平面示意图,w指向R1, R1中的点在H的正侧。,R2中的点在H的负侧。,(2) g(x)是x到超平面距离的一种代数距离。 x可以分解为,超平面的法向量,x在H上的投影,x到H的垂直距离,w方向上的单位法向量，,该距离有符号, 当符号为正时, 表明x对应的点在超平面的正侧, 反之在负侧。 ,(2) 确定一个准则函数J, 要求满足以下两个条件: J是样本集、 w和w0的函数; J的值反映分类器性能, 它的极值对应于“最好”的决策。 (3) 用最优化技术求解准则函数, 得到极值点
7、对应的w*和w*0。 线性分类器设计, 其关键在于最优准则以及相应的求解方法。,(1) 选择样本集z=x1, x2, , xN。 样本集中的样本来自两类且类别已知。 ,线性判别函数设计的一般步骤,Fisher线性判决 Fisher线性判决的基本思想是寻找一个最好的投影方向, 当特征向量x从d维空间映射到这个方向上时, 两类能最好地分开。 这个方法实际上涉及特征维数的压缩问题。,分析w1方向之所以比w2方向优越，可以归纳出这样一个准则：即向量W的方向选择应能使两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。这就是Fisher准则函数的基本思路。寻找最好的投影方向, 在数学上就表
8、现为寻找最好的变换方向w*。,定义Fisher线性判决函数为,分子反映了映射后两类中心的距离平方, 该值越大, 类间可分性越好; 分母反映了两类的类内离散度, 其值越小越好; 从总体上来讲, JF(w)的值越大越好。 在这种可分性评价标准下, 使JF(w)达到最大值的w即为最佳投影方向。 ,将JF(w)化成w的显示格式,故Fisher线性判决函数化为,求JF(w)的极大值点,利用w*, 将样本x往该方向上投影, 可得,在投影空间内的决策准则为: 若yy0, 则x1, 否则x2。,阈值y0的典型选择有:,第一步：计算参量。 (1) 各类样本的均值向量i: ,(2) 样本类内离散度矩阵Si,总类内
9、离散度矩阵Sw:,第二步：计算最优投影方向， 并 将样本往该方向上投影。,第三步：决策。在投影空间内的决策准则为: 若yy0, 则x1, 否则x2。,Fisher线性判决,分段线性分类器 线性分类器的分界面是一个超平面。 当类与类之间不能用任何一个超平面实现划分时, 类间的分界面应是一个超曲面。 考虑到曲线可以由多个线段近似表达, 曲面可以由多个平面逼近, 因此, 也可以用多个超平面近似表达超曲面, 分段线性分类器正是基于这种思路而设计的一种分类器。,图 4-17两类非线性可分时可用多段超平面分开,分段线性距离分类器 最小距离分类器, 其判决函数为,即,这时类间的决策面为,它是两类均值点连线的
10、垂直平分面。,图 4-18分段线性距离分类器示意图,近 邻 分 类 器 将均值作为代表点时, 最小距离分类器的实质就是将样本判属于与代表点距离最近的类。近邻法最初是由Cover和Hart于1968年提出的, 它的基本特点是将样本集中的任何一个样本都作为代表点, 它实质上是一种分段线性分类器。 ,最近邻法 最近邻法的主要特点就是将样本判属它的最近邻(和它距离最近的代表点)所在的类。 假定有m个类别1, 2, , m的模式识别问题, 每类有Ni(i=1, 2, , m)个样本, 规定类i的判别函数为,其中, xki表示第i类的第k个元素。,判决准则:,若,，则xj,k近邻法 最近邻分类器的判决思想
11、是将样本判属与它距离最小的样本所属的类, 这种方法的特点是概念容易理解, 最近邻样本和待分类样本在距离意义下是最相似的。 其缺点在于受随机噪声影响较大, 尤其是在两类的交叠区内。,图 4-21随机噪声对最近邻分类结果的影响,对于待分类样本x, 在N个样本集中找出它的k个近邻, 设k个样本中属于第i类的为ki个(i=1, 2, , m), 即,定义判别函数:,判决准则为,若,，则 xj,图4-22 8-近邻示意图,多输入、单输出,u1, u2, , un是从外部环境或其他神经元传来的输入信号; k1, k2, , kn是对应于输入的连接权值; 是一个阈值; 函数 g: RR 为传递函数, 也称为
12、激活函数； y表示神经元的输出。,人工神经元模型,(1) 阈值型函数。 阶跃函数：,符号函数：,常用的基本激活函数,(2) 分段线性函数：,(3) Sigmoid函数：,或,Sigmoid函数示意图 (a) 取值在(0, 1)内; (b) 取值在(1, 1)内,神经网络结构 神经网络是由大量的人工神经元广泛互连而成的网络。 根据网络的拓扑结构不同, 神经网络可分为： 层次型网络：前馈网络（感知器、 BP网络、RBF网络）和反馈网络（ Hopfield网络） 网状结构网络（自组织竞争网络）,1. 前馈网络 结构：神经元分层排列，网络由输入层、中间层(也称隐含层)、 输出层组成； 特点：每一层的各
13、神经元只能接受前一层神经元的输出, 作为自身的输入信号。,单层前馈神经网络,多层前馈神经网络,多层前馈网络有一个或多个隐含层。,2. 反馈网络 特点：反馈网络的输出层接有反馈环路, 将网络的输出信号回馈到输入层。,单层反馈神经网络,神经网络的学习方法 神经网络信息处理包括学习和执行两个阶段。(1) 学习阶段也称为训练阶段：给定训练样本集, 按一定的学习规则调整权系数, 使某种代价函数达到最小, 也就是使权系数收敛到最优值。 (2) 执行阶段：利用学习阶段得到的连接权系数, 对输入信息进行处理, 并产生相应的输出。,根据学习过程的组织与管理, 神经网络的学习可分为: 有教师(有监督)学习。 对每
14、一个输入训练样本, 都有一个期望得到的输出值(也称教师信号), 将它和实际输出值进行比较, 根据两者之间的差值不断调整网络的连接权值, 直到差值减小到预定的要求。 无教师(无监督、自组织)学习。 网络的学习完全是一种自我调整的过程, 不存在教师信号。输入模式进入网络后, 网络按照预先设定的某种规则反复地自动调整网络结构和连接权值, 使网络最终具有模式分类等功能。,学习规则 wij(k+1)=wij(k)+wij,单层前馈神经网络,yj,j,xi,i,wij, 输入模式为n维矢量x=(x1, x2, , xn)T，输入层包含n个节点； 输出模式为m个类别1, 2, , m，输出层有m个输出节点
15、y1, y2, , ym, 每个输出 节点对应一个模式类； 输入节点i和输出节点j 的连接权为wij (i=1, 2, , n; j=1, 2, , m)。,单层感知器网络结构图,传递函数 f 采用符号函数。,输出层第j个神经元的输出为,单层感知器网络结构图,若 yj=1, 则将输入模式x判属j类; 若yj=1, 则输入模式x不属于j类。 学习规则：,BP：反向传播(Back Propagation) BP网络是采用误差反向传播算法的多层前馈网络 传递函数为S型函数 学习规则采用梯度下降算法 在网络学习过程中, 把输出层节点的期望输出(目标输出)与实际输出(计算输出)的均方误差, 逐层向输入层
16、反向传播, 分配给各连接节点, 并计算出各连接节点的参考误差, 在此基础上调整各连接权值, 使得网络的期望输出与实际输出的均方误差达到最小。,BP网络,逐个处理的BP算法训练步骤如下: (1) 初始化。 根据实际问题, 设计网络连接结构。 例如, 输入变量和输出变量个数、隐含的层数、各层神经元的个数, 并随机设置所有的连接权值为任意小值。假设输入变量为n个, 输出变量为m个, 每个训练样本的形式为(x1, x2, , xn; y1, y2, , ym), 其中, y=(y1, y2, , ym)是输入为x=(x1, x2, , xn)时的期望输出。,(2) 输入一个样本, 用现有的权值计算网络中各神经元的实际输出。 (3) 计算局部误差(i)p,k(i=1, 2, , l, l+1), l为隐含层的个数。,输出误差,第r隐含层各神经元的输出,输出层,隐含层,输出层传递函数的偏导,(4) 计算权值变化量W(i)p,k(i=1, 2, , l
