4a-非线性分类器.ppt

第四章 非线性分类器 4.1 分段线性分类器 4.2 二次函数分类器 4.3 近邻法 4.1分段线性分类器 4.1.1 分段线性判别函数 4.1.2 线性分类器的训练 4.1.1分段线性判别函数 1 基于距离的分段线性判别函数 2 分段线性判别函数 3 分段线性分类器设计的一般考虑 前面我们讨论了用线性判别函数设计分类器的方法。 在实际中有很多模式识别问题并不是线性可分的，这时就需要采用非线性分类器。比如当两类样本分布具有多峰性质并互相交错时，简单的线性判别函数往往会带来较大的分类错误。这时，树分类器作为一种分段线性分类器，常常能有效的应用于这种情况。本节重点讨论分段线性分类器的算法。 如图所示两类样本不能用线性分类器分开, 但可用分段线性判别函数和二次判别函数分开。 分段线性判别函数是一种特殊的非线性判别函数，它确定的决策面是由若干超平面段组成的。 由于它的基本组成仍然是超平面，因此，与一般超曲面相比是简单的；又由于它是由多段超平面组成的，所以它能逼近各种形状的超曲面，具有很强的适应能力。 1基于距离的分段线性判别函数 3分段线性分类器设计的一般考虑 分类器设计的基本问题是，在一定判别函数类内利用训练样本集确定分类器的参数，即确定判别函数中的系数。设计线性分类器，就是确定权向量 和阈值权 或广义权向量 。而设计分段线性分类器，则是利用样本集确定一组 和 。下面我们分几种不同的情况来讨论这个问题。 1) 子类数及子类划分已知 若已知样本的子类划分情况，可把子类看作独立的类，然后利用多类线性判别函数算法把各个子类分开，自然也就把各类分开了。 前提：已知子类划分。 划分子类的方法： 1).根据先验知识直观判定，如字符识别中，可把同一字符看作一类，而把其中不同的字体看作它的不同子类。 2).借助于聚类分析方法来解决。 2) 子类数已知.子类划分未知 利用下面的错误修正算法设计分段线性分类器，它与多类线性判别函数的固定增量算法很相似，其步骤为 3)未知子类数目 当每类应分成的子类数目也未知时，这是最一般的情况。在这种情况下，设计分段线性分类器的方法很多.下面介绍二分树分段线性分类器. 树状分段线性分类器 4.1.2线性分类器的训练 1 算法基本思想 2 紧互对原型对与交通区 3 局部训练法 1算法基本思想 这是一种实现最少分段线性分类器的方法。当两类样本非线性可分时，贝叶斯分界面一般通过两类样本十分靠近或相互交迭的区域，我们称之为“交遇区”。把这些区域找出来，利用这些区域中的样本作为新的样本集设计线性判别函数，然后把它们连在一起，就构成了一个分段线性判别函数。这种方法称为“局部训练法”，所得的分界面是分段线性分解面，它可以很好的逼近贝叶斯分界面。 2 紧互对原型对与交遇区 假设有两类样本集 X1 和X2,为找出交遇区，可先将每一类样本用聚类分析方法分为若干子集。每个子集在特征空间中占据一定区域，称为“原型区”，每个子集的重心，或最靠近重心的一个样本，称为该子集的“原型”。 3 局部训练法 4.2 二次判别函数 二次判别函数也是一种常用的非线性判别函数，而且它的适用范围比简单的线性判别函数要广。但是由于二次判别函数及其确定的分界面比较复杂，我们只简单介绍一下它的基本概念。 定义：二次函数的一般表达式为 二次判别函数确定的决策面是一个超二次曲面，包括椭球面、超椭球面、超双曲面等。 （2）定义二次判别函数 我们记这一超平面为 现在利用紧互对原型对集设计局部超平面，方法如下： 步骤1 首先在紧互对原型对集合中找出最近的一对，用 (vm1 ,vn2) 表示，很容易找到一个超平面把这一对原型分开，为简单起见，可以选择 vm1和 vn2连线的垂直平分面，这个超平面的方程是 步骤2 以 H01作为初始平面，找出 H01正确分类的紧互对原型对，用这些原型所代表的子类中的所有样本作为局部训练样本集，并利用它设计第一个超平面段.并记最后得到的超平面为H1 步骤3 将被 H1正确分类的紧互对原型对拿走，对剩下的紧互对原型对重复1和2两个步骤，以得到第二个超平面段 H2 步骤4 重复上述步骤，直到所有的紧互对原型对都被处理完毕为止。这样我们就可以序贯地得到一组（共m个）超平…面 H1 H2 … Hm ，它们构成一个分段线性分类器. 其中W是d×d实对称矩阵，w 为 d 维向量。为确定判别函数 g(x)，需要确定L个不同系数。 例如，对于一类（设 ω1 类）样本分布比