第三章 非参数判别分类方法

获得增广权向量的方法不少，其中感知准则函数方法是一种利用错分类对现决策权向量进行修正直至收敛的方法。这种方法只对线性可分情况适用。 线性可分是指两类训练样本在特征空间各自分布的区域，可用一线性函数隔开。

在给定一个规范化增广样本集量，可以计算向量，则应有

，我们令

，

的条件下，对于任何一个增广权向

，显然如果该向量是一个能将此样本集正确分类的增广权

而对可导致错分类的增广权向量，则必有若干个yi ,使被错分类的规范化增广样本组成的集用yk表示，并定义一准则函数

(3-40)

，即达到极小值。因

则能将该样本集正确分类的增广权向量，使 此确定向量的问题变为对数。 求

求极小值的问题，这个准则函数就是感知准则函

准则函数的极小值问题，可以采用迭代法进行。一个常用的方法是

梯度下降算法，即对第k次迭代值，求其梯度向量，并令迭代向量沿此负梯度向量方向修正，可以较快速度到达其极小值。 将(3-40)式，对求偏导数，得

(3-41)

可见感知准则函数的梯度向量是所有被错分类的规范化增广样本向量之和，如果将迭代公式写成 其中

为一步长系数，将(3-41)代入可得

(3-43)

综上所述，感知准则函数利用梯度下降算法求增广权向量的做法，可简单

叙述为： 任意给定一向量初始值次的权向量

，第k+1次迭代时的权向量等于第k

加上被错分类的所有样本之和与的乘积。可以证明，对于线

性可分的样本集，经过有限次修正，一定可以找到一个解向量，即算法能在有限步内收敛。其收敛速度的快慢取决于初始权向量和系数 。

下面就一个只有三个样本的样本集为例，说明该算法。该三个样本y1,y2及y3如图3.6所示。而其解区则由两个分别与y1,y3正交的向量所包围的区域组成。为了简便起见，我们设a(1)为y1，并令

=1。如果我们反复地将y1到y3依次送

到分类器检验，并在发生错分类时对向量a(k)作出修正，则y3将在a(1)＝y1时被错分类，故

；然而紧接着的y1又被a(2)错分类，故权向量值又

一次修正，迭代下去直至该解向量进入解区内，如图3.6中的点“8”所示。

图3.6图3.7

实际上(3-43)所示迭代修正过程是很容易理解的，这可用图3.7表示。由于所有被a(k)错分类的样本必然都在以a(k)为法线的超平面的负侧，因而它们的总和也必然处于该侧，则a(k+1)按(3-43)修正，就会使a(k+1)向错分类向量和趋近，有可能使这些错分类向量之和穿过超平面，或至少朝有利方向变动。 感知准则函数方法只是对线性可分样本集有效，而对线性不可分的样本集，该算法不能收敛。因此又研究出其它方法，如最小错分样本数准则等，我们不再讨论，读者可参考有关书籍。

这一节对感知准则函数的讨论，只是很初步的，并且只讨论了线性可分的情况。但这种利用错误提供的信息，进行自修正的思想意义是十分深远的。这种只解决线性分类的感知器称为单层感知器，由它基础上发展起来的多层感知器在原理上能解决非线性分类、多类划分，以及非线性拟和非线性映射等多种功能，这些将在人工神经元网络这一章中进一步讨论。

3.2.6 多类问题

以上讨论的都是两类别问题，但是实际问题中常遇到的是多类别问题。在两类别问题中使用的线性判别函数方法可以推广到多类别问题中，但可有不同做法。

一种最简单作法是将C类别问题化为(C-1)个两类问题，即将第i类与所有非i类样本，按两类问题确定其判别函数与决策面方程。因此对于C类，则总共有(C-1)个两类别问题，如图3.8(a)所示。这种做法存在两个问题，一是可能会出现一些不定区域，如图中阴影所示，在这些区域中的样本无法确定其类别。另一方面用线性判别函数对i类及所有非i类进行划分并不能保证获得性能良好的划分，硬性使用线性分类器可能会产生很不好的效果。

图3.8(a)图3.8（b）

另一种相对麻烦些的做法是将C类中的每两类别单独设计其线性判别函数，因此总共有C(C-1)/2个线性判别函数。这种方法如图3.8(b)所示。这种方法由于每个判别函数针对每两类别样本设计，预期可有好效果，但仍有不定区域，在该区域内样本类别无法确定。

因此一个比较合适的作法是将特征空间确实划分为C个决策域，共有C个判别函数

每个决策域Ri按以下规则划分 如果

(3-44)

因此落在Ri区域内的样本被划分成ωi类，如果发生gi(X)＝gj(X)，即处于决策域的边界上，则作出拒绝决策。这种分类器被称为线性机器。线性机器中决策域的边界由相邻决策域的判别函数共同决定，此时应有 成

(3-46)

或写

(Wi-Wj)是该边界超平面的法线向量。在线性机器中最多有C(C-1)/2个超平面，但实际的超平面数目往往要少很多。图3.9(a)是一个二维特征空间三类别线性机器的示意图，(b)则是一个五类别情况，但其分界面的数量远比C(C-1)/2要小得多。

图3.9

§3.3 非线性判别函数

3.3.1 非线性判别函数与分段线性判别函数

由于样本在特征空间分布的复杂性，许多情况下采用线性判别函数不能取得满意的分类效果。例如对图3.10所示两类物体在二维特征空间的分布，采用线性判别函数就无法取得满意的分类效果。在这种情况下，可以采用分段线性判别或二次函数判别等方法，效果就会好得多。与一般超曲面相比，分段线性判别函数是最为简单的形式，是非线性判别函数情况下最为常用的形式。除此之外二次判别函数是除线性及分段线性外最简单的形式。以下只讨论有关分段线性判别函数设计中的一些基本问题。

对实际的模式识别问题来说，各类在特征空间中的分布往往比较复杂，因此无法用线性分类函数得到好的效果。这就必须使用非线性的分类方法。在对待非线性判别分类问题，提到的三种不同的方法。传统的模式识别技术，则侧重于使用分段线性判别函数，因此基本上是沿用了线性判别函数的方法。这在3.3.1到3.3.4中讨论。3.3.2的错误修正法是对感知准则函数的扩展，但人工神经元网络如多层感知器等网络能够实用非常复杂的非线性分类，以及非线性函数拟和，非线性映射等，这将在人工神经元网络这一章讨论。支持向量机则提出了一种基于特征映射的方法，也就是使用某种映射，使本来在原特征空间