第5章-非线性判别函数

模式识别徐蔚然北京邮电大学信息工程学院非线性判别函数非线性判别函数传统的模式识别技术，则侧重于使用分段线性判别函数人工神经元网络如多层感知器等网络能够实用非常复杂的非线性分类，以及非线性函数拟和，非线性映射等支持向量机则提出了一种基于特征映射的方法，也就是使用某种映射，使本来在原特征空间必须使用非线性分类技术才能解决的问题,映射到一个新的空间以后,使线性分类技术能继续使用。5.1非线性判别函数与分段线性判别函数线性辨别函数以下只讨论有关分段线性判别函数设计中的一些基本问题。分段线性判别二次函数判别分段段数问题分段段数问题分段段数过少，分类效果必然要差但段数又要尽可能少，以免分类判别函数过于复杂，增加分类决策的计算量同一类样本可以用若干个子类来描述合适的子类划分不知道，需要采用聚类方法分段线性判别函数的一般形式分段线性判别函数的一般形式表示第i类第l段线性判别函数li为i类所具有的判别函数个数，分别是第l段的权向量与阈值权。分段线性判别函数的一般形式相应的判别规则是：如果其中则决策则称为第i类的判别函数。分类的决策面方程:取决于相邻的决策域，如第i类的第n个子类与第j类的第m个子类相邻，则由它们共同决定的决策面方程为分段线性判别的主要问题分段线性判别的主要问题每一类的样本数据在特征空间中的分布呈复杂修正时，使用线性判别函数就会产生很差的效果，如果能将它们分割成子集，而每个子集在空间聚集成团，那么子集与子集的线性划分就可以取得比较好的效果。因此分段线性判别的主要问题是如何对数据划分成子集的问题。5.2基于距离的分段线性判别函数正态分布条件下，两类别问题在各特征统计独立、同方差、且先验概率相等情况下，最小错误率决策可按最小距离决策，即基于距离的分段线性判别函数分段线性距离分类器原理按距离分类的原理推广把各类别样本特征向量的均值作为各类的代表点，而样本的类别按它到各类别代表点的最小距离划分在这种判别函数中，决策面是两类别均值连线的垂直平分面基于距离的分段线性判别函数基于距离的分段线性判别函数基于距离的分段线性判别函数分段线性距离分类器原理显然这种判别方法只有在各类别密集地分布在其均值附近时才有效。对于上图所示情况，若企图再用每类一个均值代表点产生最小距离分类器，就会产生很明显的错误率。在这种情况下，可以将各类别划分成相对密集的子类，每个子类以它们的均值作为代表点，然后按最小距离分类基于距离的分段线性判别函数分段线性距离分类器原理归纳起来，如果对于ωi有li个子类，则有li个代表点，或者说把属于ωi的决策域Ri分成li个子域，即对每个子区域Ril均值用mil表示，并以此作为该子区域的代表点，则判别函数定义为：相应的判别规则是：如果，则X∈ωi基于距离的分段线性判别函数基于距离的分段线性判别函数对样本进行子类的合适划分是分段线性距离分类器性能好坏的一个关键问题5.3错误修正算法错误修正法是对感知准则函数的扩展aiTy与ajTy相比较的含义:ai与aj代表两类增广权向量y则代表规范化的增广权向量一般来说点积值比较大则表示这两个向量在方向上比较一致，换句话说向量间的夹角较小。错误修正算法思路如果某一类样本比较分散能用若干个增广权向量表示使同一类规范化增广样本向量能够做到与代表自己一类的增广权向量的点积的最大值比与其它类增广权向量的点积值要大就可以做到正确分类。错误修正算法思路这种算法就是要用错误提供的信息进行叠代修正它对每类样本集进行具体划分希望能知道每类所需的增广权向量数目实际上，该数目也可以在计算过程中按分类效果调整错误修正算法的基本要点当每类的子类数目已知时可以采用假设初始权向量然后由样本提供的错误率信息进行迭代修正，直至收敛(1)对每个类别的子类赋予一初始增广权向量，其中括号中的数目表示迭代次数。错误修正算法的基本要点(2)然后对每次迭代所得增广权向量用样本去检测，如发生错误分类，则利用错误分类的信息进行修正。其做法是：a)先将某一j类的增广样本向量yj，与该类所有增广权向量aj-l(k)求内积aj-l(k)Tyj，找到其中的最大值aj-m(k)Tyjaj-m(k)Tyj=maxaj-l(k)Tyj错误修正算法的基本要点b)将该yj与其它类(如i类)的权向量求内积，并将这些内积值与作比较，若aj-m(k)Tyj≤ai-l(k)Tyji=1,…,c,i≠j,l=1,…,li则表明权向量组，不影响yj的正确分类，因此不需要修改这些权向量错误修正算法的基本要点b)但是如果存在某个或几个子类不满足上述条件，譬如某个子类的现有权向量使得aj-m(k)Tyj≤ai-n(k)Tyji≠j这表明yj将错分类，而有关权向量需要修正错误修正算法的基本要点c)此时首先找到导致yj错分类的所有权向量中具有与yj内积最大值的权向量ai-n’(k)Tai-n’(k)T=max(ai-n(k)Tyj)接着对aj-m(k)Tyj与ai-n’(k)T作相应修正:错误修正算法的基本要点c)然后利用权向量的新值重复以上过程，直到收敛或迫使其收敛。收敛条件(训练集错误率为零)这种算法在样本确实能被分段线性判别函数正确划分的条件下是收敛的但当该条件不满足时，则需逐步减小ρk的数值，迫使其“收敛”会有相应的错误率存在5.4局部训练法局部训练法的思路出发点是类间的分界面必然处在两类样本的交界处因此只需找出这些交界处的样本，然后对这些邻近的不同类样本,按需要确定分界面即可学习这一段主要能明白它的思路即可局部训练法局部训练法局部训练法的思路实际上决策面都处在不同类别样本分布的交界处或邻接处所在的区域内用这些区域中的样本来决定判别函数，就可以代替用整个样本集进行训练。基于这种思想的样本训练法称为“局部训练法”。局部训练法局部训练法的思路参加训练的局部样本集由两类样本组成。这些区域称之为“交遇区”局部训练法就是基于交遇区内的样本进行设计的局部训练法要解决的几个问题(1)如何从样本集中找到“交遇区”；(2)如何利用“交遇区”中的样本设计线性分类器以及;(3)如何进行分类决策5.4.1紧互对原型与交遇区寻找“交遇区”的一种思路其实质是先在每类样本集内进行分片划分，所使用的方法是聚类方法也可以采用别的方法。划分的目的是使每类样本划分成小片后，找到处在本类样本占领区域边界上的小片原型。找到边界子集的方法是通过与另一类样本子集中找近邻的方法实现的。5.4.1紧互对原型与交遇区寻找“交遇区”的一种思路如果发现分属两类的两个原型互为最近邻，那么这两个原型就被认定为处在两类样本决策域的交界处，它们所在区域就成为交遇区。交遇区就是有这些处在边界上的原型集组成。为了简便计算，每个小片(原型)都找出一质心，用它代表这个小片(也称原型)。通过计算每个原型与其它原型的欧氏距离来计算近邻关系。紧互对原型与交遇区寻找“交遇区”的具体方法(1)为了找到两类样本的交遇区，首先对这两类样本进行聚类分析，从而找出它们各自的一些相对密集的子区域，称为“原型区”。(2)在每个原型区中找到一个质心或距质心很近的样本作为各原型区的代表点，称为“原型”。紧互对原型与交遇区紧互对原型与交遇区寻找“交遇区”的具体方法(3)然后在两个类别的原型集合中，分别计算不同类原型对之间的欧氏距离，并找出各原型在对方类型中相距最近的原型对(4)从这些最小距离原型关系中找到互为最小距离的原型对(5)紧互对原型对的集合组成“交遇区”。有时可将紧互对原型对扩展成k-紧互对原型对5.4.2局部训练法局部训练法利用“交遇区”来设计分界面的基本思想边界由若干个交遇区确定，在每个交遇区中只有两种不同类型的样本由这些样本产生一个合适的分界面，一般使用分段线性分界面具体做法是利用处于最紧贴边界的紧互对原型对产生一初始分界面，然后利用交遇区进行调整，这种调整属于局部性的调整局部训练法具体做法步骤一：产生初始超平面首先由紧互对原型对集合中最近的一对，产生一个初始决策面的方程例如可由两个原型的垂直平分平面作为初始界面，表示成H1局部训练法具体做法步骤二：初始决策面最佳化确定H1能正确分类的所有紧互对原型对，并由这些原型对中的样本组成局部训练的样本集按所使用的准则设计出线性决策面H1*，该决策面对现有局部样本集来说是最佳的局部训练法具体做法步骤二：初始决策面最佳化对该H1决策面又可找出它能正确分类的所有紧互对原型对。如果H1*与H1’的分类效果相同，则不需再调整否则由作为初始决策面重复上述过程，直到所包罗的局部训练样本集不再发生变化为止局部训练法具体做法步骤三：新决策面的产生与最佳化在找到一个最佳的决策面段后，将相应的局部训练样本从原紧互对原型对集合中撤走然后在剩下的紧互对原型对集合重复上述步骤，产生另一个超平面分界面如此重复下去直到所有紧互对原型对都被处理完毕，得到一系列超平面，组成分段线性分类器。5.4.3决策规则的确定在使用上述方法得到一组超平面作为分段线性分类器的分界面仅对交遇区的样本集进行性能检测有时不能发现存在的问题需要使用全体样本对其进行性能检验，观察其能否对全体样本作出合理的划分决策规则的确定决策规则的确定用向量表示样本yj的所属区域如果现有的决策界面数为m，需要表示出样本yj的所属区域每个决策超平面的增广权向量为那么每一个样本yj处在哪个区域，可用它们与这些增广权向量的内积符号表示决策规则的确定用向量表示样本yj的所属区域可定义一个由样本Xj(用增广样本向量yj表示)决策的m维向量来表示其中因此处在同一区域的所有样本都有同样的向量值。决策规则的确定决策规则的确定全体样本将被划分若干子集，最大可能的子集数为2m个。每个子集都可能包含两个类别的训练样本但在每个子集中两类样本分布的不同，将作为划分与改进决策域的依据决策规则的确定计算比值函数决策规则的确定根据L值及N1(ZK)与N2(ZK)这三个数据，可对各个区域作相应决定：1如果L1/2，则ZK区域为ω1的决策域；2如果L1/2，则ZK区域为ω2的决策域；3如果L≈1/2，以及N1(ZK)、N2(ZK)很小，则对ZK内样本可作拒绝决策；决策规则的确定根据L值及N1(ZK)与N2(ZK)这三个数据，可对各个区域作相应决定：4如果L≈1/2，但N1(ZK)与N2(ZK)数量不可忽略，则对此区域，用该子集的样本再次进行局部训练法训练，以获得其进一步划分。重复上述过程，直至对所有区域都能合理地确定为哪一类的决策域，或拒识区域为止。