第五章 非线性判别函数优秀PPT.ppt

《第五章 非线性判别函数优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第五章 非线性判别函数优秀PPT.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 非线性判别函数第一页，本课件共有30页5.1 5.1 引言引言n对实际的模式识别问题来说，各类在特征空间中的分布往往比较复杂，因此无法用线性分类函数得到好的效果。这就必须使用非线性的分类方法。第五章 非线性判别函数由于样本在特征空间分布的复杂性，许多情况下采用线性判别函数不能取得满意的分类效果。非线性判别非线性判别函数函数例如右图所示两类物体在二维特征空间的分布，采用线性判别函数就无法取得满意的分类效果。在这种情况下，可以采用分段线性判别或二次函数判别等方法，效果就会好得多。第二页，本课件共有30页 5.1 引言n在对待非线性判别分类问题，有三种不同的方法：q第一：传统的模式识别技术，

2、侧重于使用分段线性判别函数。q第二：对基于错误修正法的感知准则函数进行扩展，人工神经元网络（多层感知器等网络）能够实现复杂的非线性分类，以及非线性函数拟和，非线性映射等。q第三：支持向量机则提出了一种基于特征映射的方法，也就是使用某种映射，使本来在原特征空间必须使用非线性分类技术才能解决的问题映射到一个新的空间以后,使线性分类技术能继续使用。第三页，本课件共有30页n一种特殊的非线性判别函数分段线性判别函数q决策面由若干超平面段组成，计算比较简单q能逼近各种形状的超曲面，适应能力强 5.1 引言第四页，本课件共有30页5.25.2基于距离的分段线性判别函数基于距离的分段线性判别函数n n出发点

3、：出发点：出发点：出发点：如果两类样本可以划分为线性可分的若干子类，则可以设计多个线性分类器，实现分段线性分类器。n n基本思想：基本思想：基本思想：基本思想：用均值作为各类的代表点，用通过均值连线中点的垂直线对样本集进行分类第五章 非线性判别函数第五页，本课件共有30页n把把i类可以分成类可以分成li个子类，或者说，把属于个子类，或者说，把属于i 类的样本区域类的样本区域Ri分为分为li个子区域。个子区域。n现在定义mil表示第i类第j个子区域中样本的均值向量，并以此作为该子区域的代表点。定义判别函数判别函数判别函数判别函数如下：（在同类的子类中找最近的均值。）（在同类的子类中找最近的均值。

4、）（在同类的子类中找最近的均值。）（在同类的子类中找最近的均值。）判别规则：判别规则：这是在M类中找最近均值。则把x归于j类完成分类。基于与类心距离的分段线性判别函数 5.2 基于距离的分段线性判别函数第六页，本课件共有30页n例：未知x,如图：n先与1类各子类的均值比较，即 ，找一个最近的 与2各子类均值比较取最近的 因g2(x)g1(x)，所以x2类。5.2 基于距离的分段线性判别函数第七页，本课件共有30页n利用均值代表一类有时有局限性，如下图所示。若用线性判别函数代表一类，就会克服上述情况。5.2 基于距离的分段线性判别函数第八页，本课件共有30页n设 1,2,m。而每一类又可以分为

5、子类。n对每个子类定义一个线性判别函数：n定义i类的线性判别函数为：n在各子类中找最大的判别函数作为此类的代表，则对于M类，可定义M个判别函数gi(x),i=1,2,.M,因此，决策规则为：5.2 基于距离的分段线性判别函数基于与分界面距离的分段线性判别函数对未知模式x，q把x先代入每类的各子类的判别函数中；q找出一个最大的子类判别函数，M类有M个最大子类判别函数；q在M个子类最大判别函数中，再找一个最大的；则x就属于最大的子类判别函数所属的那一类。第九页，本课件共有30页5.3 5.3 每类的子类数目已知每类的子类数目已知错误修正算法错误修正算法n 在感知准则函数中定义过：ai与aj代表两类

6、增广权向量，y则代表增广权向量。n 一般来说点积值比较大则表示这两个向量在方向上比较一致，换句话说向量间的夹角较小。n 如果某一类样本比较分散，但是能用若干个增广权向量表示，使同一类增广样本向量能够做到与代表自己一类的增广权向量的点积的最大值，比与其它类增广权向量的点积值要大点积值要大，就可以做到正确分类。n 因此这种算法就是要用错误提供的信息进行叠代修正用错误提供的信息进行叠代修正。n 是ai向量与y向量的点积n 是aj向量与y向量的点积第五章 非线性判别函数第十页，本课件共有30页 当每类的子类数目已知时，可以采用假设初始权向量，然后由样本提供的错误率信息进行迭代修正，直至收敛。该算法的基

7、本要点是：n对每个类别的子类赋予一初始增广权向量n然后对每次迭代所得增广权向量用样本去检测，如发生错误分类，则利用错误分类的信息进行修正。其做法是：1）在第k次迭代时，将第j类的某个增广样本向量yj，与该类所有增广权向量 求内积，找到其中的最大值 5.3 错误修正算法第十一页，本课件共有30页 求内积，并将这些内积值与求内积，并将这些内积值与 作比较，作比较，2)2)另一方面将该另一方面将该y yj j与其它类与其它类(如如i i类类)的权向量的权向量 3 3）但是如果存在某个或几个子类不满足上述条件，譬如某个子类）但是如果存在某个或几个子类不满足上述条件，譬如某个子类 的现有权向量的现有权向

8、量 使得使得 这表明这表明y yj j将错分类，而有关权向量需要修正。将错分类，而有关权向量需要修正。如何修正呢？如何修正呢？5.3 错误修正算法第十二页，本课件共有30页 n首先找到导致首先找到导致y yj j错分类的所有权向量中具有与错分类的所有权向量中具有与y yj j内积最大值的权内积最大值的权向量向量 接着对接着对 和和 作相应修正。作相应修正。n然后利用权向量的新值重复以上过程，直到收敛或迫使其收敛。然后利用权向量的新值重复以上过程，直到收敛或迫使其收敛。n这种算法在样本确实能被分段线性判别函数正确划分的条件下是收敛这种算法在样本确实能被分段线性判别函数正确划分的条件下是收敛的。的

9、。5.3 错误修正算法第十三页，本课件共有30页 5.3 错误修正算法第十四页，本课件共有30页 5.3 错误修正算法第十五页，本课件共有30页 5.3 错误修正算法第十六页，本课件共有30页 5.3 错误修正算法第十七页，本课件共有30页 5.3 错误修正算法第十八页，本课件共有30页 5.3 错误修正算法第十九页，本课件共有30页 5.3 错误修正算法第二十页，本课件共有30页5.4 非线性可分条件下的支持向量机n1维空间第二十一页，本课件共有30页一维一维x空间中非线性判别函数例空间中非线性判别函数例作非线性变换：作非线性变换：通过非线性变换，非线性判决函数转变通过非线性变换，非线性判决

10、函数转变成了线性判决函数；特征空间也由一维成了线性判决函数；特征空间也由一维x空间映射成二维空间映射成二维y空间。执行非线性空间。执行非线性变换，特征空间维数的增长往往不可避免。变换，特征空间维数的增长往往不可避免。此时此时g(x)被称为被称为广义线性判别函数广义线性判别函数，a称为称为广义权向量广义权向量。广义线性判别函数第二十二页，本课件共有30页n 二维二维 y 空间决策方程空间决策方程：n 判决函数的正负侧判决函数的正负侧：正侧区正侧区g(y)=0二维二维 y 空间中广义性判决函数空间中广义性判决函数广义线性广义线性判决规则判决规则变量代换变量代换第二十三页，本课件共有30页n广义线性

11、判别函数的一般式：因此，在因此，在 y 特征空间可线特征空间可线性表示一个非常复杂的性表示一个非常复杂的 x 空间的决策函数，广义空间的决策函数，广义线性函数线性函数.n按照上述原理，任何非线性函数按照上述原理，任何非线性函数g(x)用级数展开成高次多项式后，用级数展开成高次多项式后，都可转化成都可转化成广义线性判别函数广义线性判别函数来处理。来处理。n nw wT Ty=0y=0在在在在Y Y空间确定了一个通过原点的超平面空间确定了一个通过原点的超平面空间确定了一个通过原点的超平面空间确定了一个通过原点的超平面。这样我们就可以。这样我们就可以利用线性判别函数的简单性来解决复杂的问题。利用线性

12、判别函数的简单性来解决复杂的问题。n这样一来，线性分类方法就可以直接采用。这条路子在传统的这样一来，线性分类方法就可以直接采用。这条路子在传统的模式识别技术中并没有持续研究下去，因为一个突出的问题模式识别技术中并没有持续研究下去，因为一个突出的问题是维数会急剧增加，在高维的空间中进行计算是传统方法所是维数会急剧增加，在高维的空间中进行计算是传统方法所忌讳的。但支持向量机方法的提出者们对这个问题进行了更忌讳的。但支持向量机方法的提出者们对这个问题进行了更深入一步的研究，他们坚持了利用特征映射的方法，从而保深入一步的研究，他们坚持了利用特征映射的方法，从而保留了线性划分的计算框架。留了线性划分的计

13、算框架。第二十四页，本课件共有30页n通过特征映射，非线性可分的数据样本在高维空间有可能转通过特征映射，非线性可分的数据样本在高维空间有可能转化为线性可分。化为线性可分。第二十五页，本课件共有30页SVM问题求解对非线性问题,可以通过非线性变换转化为某个高维空间中的线性问题,在变换空间求最优分类面.这种变换可能比较复杂,因此这种思路在一般情况下不易实现。.n核:例如2维向量维向量x=x1 x2;非线性映射(x)=1 x12 2 x1x2 x22 2x1 2x2设 K(xi,xj)=(1+xiTxj)2,；我们看看是否K(xi,xj)=(xi)T(xj)？K(xi,xj)=(1+xiTxj)2,

14、=1+xi12xj12+2 xi1xj1 xi2xj2+xi22xj22+2xi1xj1+2xi2xj2=1 xi12 2 xi1xi2 xi22 2xi1 2xi2T 1 xj12 2 xj1xj2 xj22 2xj1 2xj2 =(xi)T(xj),第二十六页，本课件共有30页n这样，我们通过核函数将原始空间的样本映射到高维特征空间，而根本就不用知道映射函数的具体形式。n核函数实际上等价于样本在高维特征空间中的内积。n常用的核函数有：第二十七页，本课件共有30页例题2：XOR问题的SVM解：第二十八页，本课件共有30页第二十九页，本课件共有30页本章小结本章小结n非线性判别函数与分段线性判别函数n基于距离的分段线性判别函数n分段线性分类器的设计n支持向量机第三十页，本课件共有30页