第5章-非线性判别函数分析课件.ppt

1、 模 式 识 别 徐蔚然北京邮电大学信息工程学院北京邮电大学信息工程学院非线性判别函数非线性判别函数n传统的模式识别技术，则侧重于使用分段线性判别函数 n人工神经元网络如多层感知器等网络能够实用非常复杂的非线性分类，以及非线性函数拟和，非线性映射等 n支持向量机则提出了一种基于特征映射的方法，也就是使用某种映射，使本来在原特征空间必须使用非线性分类技术才能解决的问题,映射到一个新的空间以后, 使线性分类技术能继续使用。 5.1非线性判别函数与分段线性判别函数线性辨别函数以下只讨论有关分段线性判别函数设计中的一些基本问题。 分段线性判别 二次函数判别 分段段数问题n分段段数问题 n分段段数过少

2、，分类效果必然要差 n但段数又要尽可能少，以免分类判别函数过于复杂，增加分类决策的计算量 n同一类样本可以用若干个子类来描述n合适的子类划分不知道，需要采用聚类方法分段线性判别函数的一般形式n分段线性判别函数的一般形式 表示第i类第l段线性判别函数 li为i类所具有的判别函数个数， 分别是第l段的权向量与阈值权。 分段线性判别函数的一般形式n相应的判别规则是：如果 其中 则决策 则称为第i类的判别函数。分类的决策面方程: 取决于相邻的决策域，如第i类的第n个子类与第j类的第m个子类相邻，则由它们共同决定的决策面方程为分段线性判别的主要问题n分段线性判别的主要问题n每一类的样本数据在特征空间中的

3、分布呈复杂修正时，使用线性判别函数就会产生很差的效果，n如果能将它们分割成子集，而每个子集在空间聚集成团，那么子集与子集的线性划分就可以取得比较好的效果。n因此分段线性判别的主要问题是如何对数据划分成子集的问题。 5.2 基于距离的分段线性判别函数n正态分布条件下，两类别问题在各特征统计独立、同方差、且先验概率相等情况下，最小错误率决策可按最小距离决策，即基于距离的分段线性判别函数n分段线性距离分类器原理n按距离分类的原理推广n把各类别样本特征向量的均值作为各类的代表点，n而样本的类别按它到各类别代表点的最小距离划分 n在这种判别函数中，决策面是两类别均值连线的垂直平分面基于距离的分段线性判别

4、函数基于距离的分段线性判别函数基于距离的分段线性判别函数n分段线性距离分类器原理n显然这种判别方法只有在各类别密集地分布在其均值附近时才有效。n对于上图所示情况，若企图再用每类一个均值代表点产生最小距离分类器，就会产生很明显的错误率。 n在这种情况下，可以将各类别划分成相对密集的子类，每个子类以它们的均值作为代表点，然后按最小距离分类 基于距离的分段线性判别函数n分段线性距离分类器原理n归纳起来，如果对于i有li个子类，则有li个代表点，或者说把属于i的决策域Ri分成li个子域，即n对每个子区域Ril均值用mil表示，并以此作为该子区域的代表点，n则判别函数定义为：n相应的判别规则是：如果 ，

5、则Xi 基于距离的分段线性判别函数 基于距离的分段线性判别函数n对样本进行子类的合适划分是分段线性距离分类器性能好坏的一个关键问题 5.3错误修正算法 n错误修正法是对感知准则函数的扩展 naiTy与ajTy相比较的含义:nai与aj代表两类增广权向量 ny则代表规范化的增广权向量 n一般来说点积值比较大则表示这两个向量在方向上比较一致，换句话说向量间的夹角较小。 错误修正算法n思路n如果某一类样本比较分散n能用若干个增广权向量表示n使同一类规范化增广样本向量能够做到与代表自己一类的增广权向量的点积的最大值比与其它类增广权向量的点积值要大n就可以做到正确分类。错误修正算法n思路n这种算法就是要

6、用错误提供的信息进行叠代修正n它对每类样本集进行具体划分n希望能知道每类所需的增广权向量数目n实际上，该数目也可以在计算过程中按分类效果调整错误修正算法的基本要点n当每类的子类数目已知时n可以采用假设初始权向量n然后由样本提供的错误率信息进行迭代修正，直至收敛n(1)对每个类别的子类赋予一初始增广权向量 ，其中括号中的数目表示迭代次数。 错误修正算法的基本要点n(2)然后对每次迭代所得增广权向量用样本去检测，如发生错误分类，则利用错误分类的信息进行修正。其做法是：na)先将某一j类的增广样本向量yj，与该类所有增广权向量aj-l(k)求内积aj-l(k)Tyj ，找到其中的最大值 aj-m(k

7、)Tyj aj-m(k)Tyj=max aj-l(k)Tyj错误修正算法的基本要点nb) 将该yj与其它类(如i类)的权向量求内积，并将这些内积值与作比较，若aj-m(k)Tyj ai-l(k)Tyj i=1,c, ij, l=1, ,li则表明权向量组，不影响yj的正确分类，因此不需要修改这些权向量错误修正算法的基本要点nb)但是如果存在某个或几个子类不满足上述条件，譬如某个子类的现有权向量使得aj-m(k)Tyj ai-n(k)Tyj ij这表明yj将错分类，而有关权向量需要修正错误修正算法的基本要点nc)此时首先找到导致yj错分类的所有权向量中具有与yj内积最大值的权向量ai-n(k)T

8、 ai-n(k)T=max(ai-n(k)Tyj )接着对aj-m(k)Tyj 与ai-n(k)T作相应修正: 错误修正算法的基本要点nc)然后利用权向量的新值重复以上过程，直到收敛或迫使其收敛。 n收敛条件(训练集错误率为零)n这种算法在样本确实能被分段线性判别函数正确划分的条件下是收敛的n但当该条件不满足时，则需逐步减小k的数值，迫使其“收敛”n会有相应的错误率存在5.4局部训练法 n局部训练法的思路n出发点是类间的分界面必然处在两类样本的交界处n因此只需找出这些交界处的样本，然后对这些邻近的不同类样本,按需要确定分界面即可学习这一段主要能明白它的思路即可局部训练法 局部训练法n局部训练法

9、的思路n实际上决策面都处在不同类别样本分布的交界处或邻接处所在的区域内n用这些区域中的样本来决定判别函数，就可以代替用整个样本集进行训练。n基于这种思想的样本训练法称为“局部训练法”。局部训练法n局部训练法的思路n参加训练的局部样本集由两类样本组成。n这些区域称之为“交遇区”n局部训练法就是基于交遇区内的样本进行设计的 局部训练法n要解决的几个问题 n(1) 如何从样本集中找到“交遇区”；n(2)如何利用“交遇区”中的样本设计线性分类器以及;n(3)如何进行分类决策 5.4.1 紧互对原型与交遇区紧互对原型与交遇区 n寻找“交遇区”的一种思路n其实质是先在每类样本集内进行分片划分，所使用的方法

10、是聚类方法也可以采用别的方法。n划分的目的是使每类样本划分成小片后，找到处在本类样本占领区域边界上的小片原型。n找到边界子集的方法是通过与另一类样本子集中找近邻的方法实现的。5.4.1 紧互对原型与交遇区紧互对原型与交遇区 n寻找“交遇区”的一种思路n如果发现分属两类的两个原型互为最近邻，那么这两个原型就被认定为处在两类样本决策域的交界处，它们所在区域就成为交遇区。n交遇区就是有这些处在边界上的原型集组成。n为了简便计算，每个小片(原型)都找出一质心，用它代表这个小片(也称原型)。通过计算每个原型与其它原型的欧氏距离来计算近邻关系。 紧互对原型与交遇区紧互对原型与交遇区n寻找“交遇区”的具体方

11、法n(1)为了找到两类样本的交遇区，首先对这两类样本进行聚类分析，从而找出它们各自的一些相对密集的子区域，称为“原型区”。 n(2)在每个原型区中找到一个质心或距质心很近的样本作为各原型区的代表点，称为“原型”。 紧互对原型与交遇区紧互对原型与交遇区紧互对原型与交遇区紧互对原型与交遇区n寻找“交遇区”的具体方法n(3)然后在两个类别的原型集合中，分别计算不同类原型对之间的欧氏距离，并找出各原型在对方类型中相距最近的原型对 n(4)从这些最小距离原型关系中找到互为最小距离的原型对 n(5)紧互对原型对的集合组成“交遇区”。 n有时可将紧互对原型对扩展成k-紧互对原型对 5.4.2 局部训练法局部

12、训练法 局部训练法局部训练法n利用“交遇区”来设计分界面的基本思想n边界由若干个交遇区确定，在每个交遇区中只有两种不同类型的样本n由这些样本产生一个合适的分界面，一般使用分段线性分界面n具体做法是利用处于最紧贴边界的紧互对原型对产生一初始分界面，然后利用交遇区进行调整，这种调整属于局部性的调整局部训练法具体做法n步骤一： 产生初始超平面 n首先由紧互对原型对集合中最近的一对， 产生一个初始决策面的方程n例如可由两个原型的垂直平分平面作为初始界面，表示成H1 局部训练法具体做法n步骤二： 初始决策面最佳化n确定H1能正确分类的所有紧互对原型对，并由这些原型对中的样本组成局部训练的样本集n按所使用

13、的准则设计出线性决策面H1* ，该决策面对现有局部样本集来说是最佳的局部训练法具体做法n步骤二： 初始决策面最佳化n对该H1决策面又可找出它能正确分类的所有紧互对原型对。如果H1*与H1的分类效果相同，则不需再调整n否则由作为初始决策面重复上述过程，直到所包罗的局部训练样本集不再发生变化为止局部训练法具体做法n步骤三： 新决策面的产生与最佳化 n在找到一个最佳的决策面段后，将相应的局部训练样本从原紧互对原型对集合中撤走n然后在剩下的紧互对原型对集合重复上述步骤，产生另一个超平面分界面n如此重复下去直到所有紧互对原型对都被处理完毕，得到一系列超平面，组成分段线性分类器。 5.4.3 决策规则的确

14、定决策规则的确定 n在使用上述方法得到一组超平面作为分段线性分类器的分界面n仅对交遇区的样本集进行性能检测有时不能发现存在的问题n需要使用全体样本对其进行性能检验，观察其能否对全体样本作出合理的划分 决策规则的确定决策规则的确定 决策规则的确定决策规则的确定n用向量表示样本yj的所属区域n如果现有的决策界面数为m， 需要表示出样本yj的所属区域n每个决策超平面的增广权向量为 n那么每一个样本yj处在哪个区域，可用它们与这些增广权向量的内积符号表示 决策规则的确定决策规则的确定n用向量表示样本yj的所属区域n可定义一个由样本Xj(用增广样本向量yj表示)决策的m维向量来表示其中 因此处在同一区域

15、的所有样本都有同样的向量值。 决策规则的确定决策规则的确定决策规则的确定决策规则的确定n全体样本将被划分若干子集，最大可能的子集数为2m个。n每个子集都可能包含两个类别的训练样本n但在每个子集中两类样本分布的不同，将作为划分与改进决策域的依据 决策规则的确定决策规则的确定n计算比值函数 决策规则的确定决策规则的确定n根据L值及N1(ZK)与N2(ZK)这三个数据，可对各个区域作相应决定：n1 如果L1/2，则ZK区域为1的决策域；n2 如果L1/2，则ZK区域为2的决策域；n3 如果L1/2，以及N1(ZK)、N2(ZK)很小，则对ZK内样本可作拒绝决策；决策规则的确定决策规则的确定n根据L值及N1(ZK)与N2(ZK)这三个数据，可对各个区域作相应决定：n4 如果L1/2，但N1(ZK)与N2(ZK)数量不可忽略，则对此区域，用该子集的样本再次进行局部训练法训练，以获得其进一步划分。n重复上述过程，直至对所有区域都能合理地确定为哪一类的决策域，或拒识区域为止。