第三章 判别函数分类器

经过特征抽取之后，一个模式可以用n维特征空间中的一个点X来表示，当特征选择适当时，可以使同一类模式的特征点在特征空间中某个子区域内分布，另一类模式的特征点在另一子区域分布（例如苹果和橙子的问题）。这样，我们就可以用空间中的一些超曲面将特征空间划分为一些互不重叠的子区域，使不同模式的类别在不同的子区域中。这些超曲面称为判别界面，可以用一个方程来表示：dX0，其中的dX是一个从n维空间到一维空间的映射，称为是判别函数(Discriminant Function)。

在所有的函数形式中，线性函数是一种最简单的形式，下面我们就从线性判别函数入手来研究判别函数分类器。

3.0 预备知识

在介绍线性判别函数之前，先来帮助大家复习一下有关于矢量和矩阵的知识。 1. 矢量

这里的矢量X可以看作是N维欧氏空间中的一个点，用一个列矢量表示：

x1xX2

xN2. 矩阵

有的时候矩阵可以看作是由若干个矢量构成的：

TX1TXA2

TXMA是一个MN的矩阵，其中的XTi称为是矩阵的行矢量。

3. 矩阵的秩

矩阵所有行向量中的最大无关组个数称为行秩，矩阵所有列向量中的最大无关组个数称为列秩。一个矩阵的行秩等于列秩，称为矩阵的秩。 4. 转置

TT列矢量W的转置W为一个行矢量，NM的矩阵A的转置A为一个MN的矩

阵。

5. 矢量和矩阵的乘法

设W和X为N维列矢量，A为一个NM的矩阵。则：

17

1)

WXwixi，是一个数值，称为W与X的内积；

Ti1Nw1x1wx21T2) WXwNx1w1x2w2x2wNx2w1xNw2xN，是一个NN的矩阵； wNxNNwaii1i1NwaTii2，是一个N维的列矢量

3) WAi1NwaiiNi16. 正交

设W和X为N维列矢量，如果W和X的内积等于零，WX0，则称W和X正交，也称W垂直于X。

7. 逆矩阵

设A为一个NN的方阵，A的逆阵用A表示，满足AA11TA1AI，I为单位

阵。一个矩阵的逆阵存在条件是，首先是一个方阵，其次是一个满秩矩阵，即矩阵的秩为N。 8. 矩阵的特征值和特征向量

设A为一个NN的方阵，如果存在一个数和一个N维的非零列矢量ξ，使得：

Aξξ成立，则称为A的特征值，ξ为A属于的特征向量。

一般来说一个矩阵应该有N个特征值（可能相等），对应有N个特征向量。 9. 矩阵的迹和行列式值

设A为一个NN的方阵，A的迹为主对角线元素之和：trA式值表示为detA。

如果矩阵A有N个特征值1,2,,N，则有trA10. 矩阵微分

1) 矩阵对数值变量微分

如果矩阵A(t)aijt可微：

ai1Nij；A的行列

，det(A)。

iii1i1NNMN的每一个元素aij(t)是变量t的可微函数，则称A(t) 18

dA(t)d aij(t)dtdtMN其结果还是一个MN的矩阵。

2) 矩阵函数对矩阵的微分

设XxijMN，MN元函数f(X)fx11,x12,x,12x,2,mn，定义1,xf(X)对矩阵X的导数为：

dffdXxijMNffxx1N11 ffxMNxM1其结果是一个MN的矩阵。

特殊的，函数对一个矢量的微分是一个矢量。 3) 常用微分的性质

设X和W是N维的矢量，A是一个MN维的矩阵， i.

fXXTW，

dfXW； dXii.

dfXW； fXWX，

dXTiii.

fXXTAX，

dfX(AAT)X。 dX3.1 线性判别函数

一、两类问题

n维空间中的线性判别函数可以表示为：

TdX0w1x1w2x2wnxnwn1W0X0wn1

W0w1,w2,,wn称为权矢量。其中X0x1,x2,,xn为待识模式的特征矢量，

一般为了处理方便，我们可以将特征矢量和权矢量改为另外一种方式表示：

TTXx1,x2,,xn,1称为增广的特征矢量，Ww1,w2,,wn,wn1称为增广的权矢

量。则线性判别函数可以以一种简单的内积形式表示：dXWX。

TTT在二维空间中，判别界面可以用一个直线方程来表示：dXw1x1w2x2w30；

19

在三维空间中，判别界面为一个平面；在高维空间中，判别界面为一个超平面。

当我们已知线性判别函数的权矢量W时，可以构造这样一个分类器：

0,X1dXWTX0,X2

0,拒识但模式X处在分类界面上时，dX0，这是一种极端情况，可以采用两种办法来处理，一种是认为它既不属于1类，也不属于2，拒绝识别；另一种办法是认为X1。

对于线性判别函数来说，权向量在线性空间中是一个垂直于分类界面的矢量。 二、多类问题

设有M个类别1,2,,M，模式X为n维空间中的矢量。

情况一：每一类模式可以用一个超平面与其它类别分开，即可用线性判别函数将属于i和不属于i类的模式（记为i）分开。这种情况可以把M个类别的多类问题分解为M个两类问题解决，需要M个判别函数。此时判别函数为：

0,Xi diXWX0,XiTi例如在二维空间中的三类问题，判别函数分别为：

d1Xx1x2，d2Xx1x25，d3Xx21

x22X)=0 IR类别一类别二 IRd3(X)=0 IR类别三 IRd1(X)=0d(x1

分类器可以按照如下规则设计：

1. 当d1X0，而d2X0且d3X0时，判别X1； 2. 当d2X0，而d1X0且d3X0时，判别X2；

20

3. 当d3X0，而d1X0且d2X0时，判别X3；

4. 其它情况，拒识（对应IR区域）。 情况二：每两类之间可以用一个超平面分开，但是不能用来把其余类别分开。这是需要将M2个类别的多类问题转化为CMMM12个ij两类问题。判别函数为：

TdijXWijX，i,j1,2,,M，ij

其中：dijXdjiX。分类器可以采用如下规则：如果dijX0，ji，则决策Xi。

在这种情况下，同样存在着拒识区域，例如图中的阴影区域，d12X0，d31X0，

d23X0，所以它不属于任何一个类别。

d12(X)=0类别一+-类别二+)=0d13(X-d类别三23(X)=0-+

例3.1：一个三类问题，有三个判别函数：

d12Xx1x35，d13Xx13，d23Xx1x2

现有模式X4,3，判别它属于哪一类？ 带入三个判别函数：

Td12X2，得d21X20； d13X1，得d31X10； d23X1，得d32X10。

可见d3jX0,j1,2，所以可以判别X4,33。

情况三：在情况一和情况二中都存在着拒识区域。拒识区域的存在，对某些问题来说是必要

T 21

的，而对某些问题来说是不必要的。情况三是情况二的一个特例，在这种情况下不存在拒识区域。

d1(X2)=0类别一类别二)=0d13(X类别三d23(X)=0

首先我们需要对M个类别分别M个线性函数：

diXWiTXwi1x1wi2x2wiNxNwi(N1)，i1,2,,M，

然后按照如下的规则作出判别：

diXmaxdjX，则Xi。

1jM这样构造的分类器也称为是最大值分类器。它也可以看作是一种特殊形式的情况二的分类器，第i类与第j类之间的判别函数可以写成：

dijXdiXdjXWiWjX，i,j1,,M，ij。

T实际上，情况三的分类器我们在距离分类器中已经遇到过，使用欧氏距离的独立标准样本距离分类器就是一个最大值分类器。

i有1,2,,MM个类别，其标准样本分别为T1,T2,,TM，我们可以定义第类

的函数为：diXdX,Ti，diX经过简化之后可以变为一个线性函数。

diXdX,Tixjtijj1N212XTiTXTi12

首先考虑到开方的单调性，可以去掉开方，对比较大小不会产生任何影响，则：

diXXTiTTXTiXTX2TiTXTiTTi

其次考虑到XX在每一类别的判别函数中都存在且相等，也可以简化掉，对比较大小不会产生影响，则：

2 diX2TXTTi2tijxjtijTiTij1j1NN对比一下线性判别函数，令：wij2tij，j1,,N，wi(N1)

22

tj1N2ij，则diX可

以看作是一个线性函数。判别界面也是一个超平面：

dijXdiXdjXTiTjXT1Ti22Tj20

其中Ti2TiTTi表示Ti的模长的平方。分类界面的超平面刚好是垂直于Ti和Tj的连

线，并且平分两点之间的连线。（首先垂直于矢量TiTj，其次经过点

1。 TiTj）

2

经过上述分析我们可以看出，线性分类器可以用于处理线性可分的两类问题或多类问题，而类别之间的线性可分的条件是：各个类别的区域为互不相交的凸集（如不是凸集，则包含此集合的最小凸集因满足互不相交）。

在线性可分的条件下，都可以用一系列的线性函数实现分类器。这样的线性函数并不是唯一的，可能存在无穷多个。下面的问题就是如何得到这样一个或一组线性函数，这就是下面要讨论的线性分类器的训练问题。

3.2 两类别问题线性判别函数的学习

我们先来介绍一种最简单的情况，用线性函数来判别两类问题。 一、问题的表达

现有M个训练样本，分为两个集合，1类的训练样本集X1,X2,,XL和2类的训练样本集XL1,XL2,,XM。要求一个向量W，使dXWX能够区分1和2，

T即对于X1，有WX0；对于X2，有WX0，所以有：

TTX1W0,XT2W0,,XLW0 TTXTL1W0,XL2W0,,XMW0

TT即：

Tx12X1x11XTxL1xL2LTWXL1x(L1)1x(L1)2TxM2xM1XMx1NxLNx(L1)NxMN1w101wL0 1wL1010wM写成矩阵形式：XW0，其中X称为增广矩阵，0为零矢量。

由此可见，求取权向量的问题已经转化为了求解线性不等式组的问题。这个解只有在线性可分的条件下才存在，并且也不唯一。下面我们介绍几种求解上述线性不等式组的算法。 二、感知器算法

求解线性不等式方程组，不可能用一个公式来求得，必须要有一个迭代搜索的过程。下

23

面先以一种比较直观的方式来介绍一下感知器算法。

首先我们先来看一下分类界面WX0，分类界面与权矢量W垂直，现在我们要求

TW，实际上关心的是它的方向，而不是关心它的长度。其次这个分类界面是一个经过坐标

原点的超平面。如下图所示。

Y-+-W(k+1)+W(k)

开始的时候，我们不知道W的值是多少，可以先随便设一个不全为零的初始值W0，这样可以得到一个初始的分类界面W0X0；然后从训练样本集中拿出一个样本Y进行训练，将Y带入到辨别函数，计算W0Y，如果大于等于0，说明现在的分类界面已经能够正确分类Y，不需要任何调整，可以从训练样本集中取出下一个样本进行训练，如果小于0，说明现在的分类界面不能够正确分类Y，需要对分类界面W0X0进行调整。

所谓对分类界面进行调整，就是要调整权向量W0，我们可以按照下面的方式进行调整：W1W0Y，从图中可以看出来新的分类界面W1X0已经能够正确分类样本Y了。这就是感知器算法的主要思想，如果分类界面能够正确分类当前的训练样本时，不需要对其进行调整；如果分类错误时，需要进行调整，调整后的权向量是将原来的权向量与当前的训练样本相加得到的。

图中所表示的情况是经过一次调整，新的分类界面就可以正确分类训练样本，在某些情况下，只经过一次调整并不一定就能够达到目的，需要多次进行调整，但是如果按照上面的方法进行调整，总是向着好的方向发展。因为我们可以看到：

TTTTWk1YWkYYWkYYTYWkYYWkY

TTT2TT前面的讨论都是以一种形式化的方式给出了感知器算法的思想，下面我们从一个规范的数学方法来推导出感知器算法。

首先我们把求解线性不等式组的问题等价为一个最优化的问题，定义一个准则函数：

24

1WTXWTX 2其中X是我们已知的，由训练样本集构成的增广矩阵，W是我们所有求的权值向量。

JW,X当W满足不等式组时，JW,X达到最小值0。计算JW,X对W的偏导数：

J1XsgnWTXX W21,WTX0其中：sgnWX T1,WX0TJ0不可能直接进行求解（解不唯一），但是我们可以采用最优化方法中的梯度下W降法来迭代求取W的值。迭代算法可以表示为：

W1W0J， Wk1WkCWWWk其中W0为一个随机的初始值，C为一个常数。

梯度下降法的思路也比较简单，俗称为瞎子下山法，在Wk这一点上沿着这一点梯度的正方向前进，可以使J上升的最快，因此，沿着梯度的负方向前进，可以使J下降的

最快。常数C用来控制下降的速度，应该选择一个比较合适的值，太小则收敛速度太慢，太大则容易不收敛。

0,WTX0J1T由于，所以完整的感知器算法如下： XsgnWXXTW2X,WX01. 初始化，置W1为一个小的随机数，不能为0矢量； 2. 在第k步输入训练样本Xk，按照如下公式修正权值W：

WTkXk0Wk,Wk1 TWkCX,WkX0kk3. 重复第2步，直到所有训练样本被正确识别。

例3.2

可以证明，当训练样本集满足线性可分条件时，感知器算法经过有限步迭代收敛。 二、最小均方误差算法(LMSE)

感知器算法只有当模式类别线性可分的条件下才能在有限步收敛，在线性不可分的情况下，算法会来回摆动，始终不收敛。同时在线性可分的情况下，也不可能预先知道达到收敛所需要的步数。因此，当迭代多次还不收敛时，我们无法判断类别是否线性可分。

下面介绍一种称为最小均方误差法，可以避免上述问题。此方法也称为Ho-Kashyap算法（H-K算法）。

首先我们把求解线性不等式组XW0的问题等价转换为求解线性方程组XWB的

25

问题，其中Bb1,b2,,bMT，bi0。一般情况下MN1，X为一个M(N1)阶

的长方阵，所以W无解，只能求取一个近似解。

定义一个误差矢量eXWB，建立一个优化的准则函数：

JW,B12112TeXWBXWBXWB 222我们所有求的近似解应满足JW,Bmin，即误差矢量的模最小。

J0且WJ0是的W即为所求的解向量。先来求JW,B对W的梯度： B211MTJW,BXWBXWBWTXibi

22i1MJWTXibiXiXTXWB Wi1令：

J0，则： WXTXWBXTXWXTB0，即：XTXWXTB。

其中XX为一个NN的方阵，当XX非奇异时（当M比较大时，很容易成立），

TTXXT1存在，则：

WXTXXTB

1记：XXXT1XT，称为X的伪逆矩阵。WXB。X可以通过X计算得到，

J： B现在如果我们知道B，则可求得W。但B也是一个为止变量。下面来求

MJWTXibiXWB Bi1J0，则B是W的函数，所以不可能直接求得B和W，还是需要一B个迭代算法来求解。下面还是使用梯度下降法来迭代求解B：

如果直接求解

JBk1BkCBkCXWBk

BBBk一般来说，我们选择0C1，由于我们的寻优结果需要满足条件：bi0,i1,,M，而XWBk有可能大于0也可能小于0，所以上述梯度下降法的迭代规则应修改为：

26

XWBk0Bk,Bk1

BkCXWBk,XWBk0完整的H-K算法如下：

1. 由训练样本集X1,,XM构造增广矩阵X，求伪逆矩阵XXXT1XT；

2. 初始化B0，其中每一个分量bi为一个较小的正值，选取常数C，置步数k0； 3. 计算WkXBk，ekXWkBk； 4. 若ek0，停止迭代，得到WWk；

若ek0，即ek的全部分量均为负值，则停止，说明线性不可分； 其它情况，即ek的分量中有正有负，则继续5； 5. 计算

ek0Bk,Bk1

BkCek,ek06.

kk1，转到第3步，继续。

算法中的第5步，需要对ek的每一个分量进行判断，大于0的分量修改Bk1相应的分量，小于等于0，则不修改。可以写成下述表达式：

1Bk1BkCekek 2通过第5步的修正规则我们可以看到，当ek的全部分量均小于等于0时，Bk1的修改就会停止，但此时，JW,B12e还没有收敛与最小值0，所以知训练样本集线2性不可分。

例3.3

LMSE算法的优点是收敛速度快，同时可以监视收敛过程，即使判断出线性不可分的情况。可以证明当模式是线性可分时，如果取0C1，则e1,e2,单调下降，并且limekk2220。

3.3 多类别问题线性判别函数的学习

前面已经讲过多类别的识别问题个一转化为多个两类别问题，同样多类别的线性判别函数学习问题也可以转化为多个两类问题线性函数的学习问题。我们还是分成三种情况来讨论。

情况一：一个M类的问题可以看作是M个两类别问题，设有M个类别

27

1,2,,M，转化为两类别问题ii，由diXWiTX作为判别函数。训练过程

可以将i类的样本作为一类，而i之外的其它类别样本作为一类进行训练。

情况二：设有M个类别1,2,,M，将M类问题转化为MM12个两类问

T题，以dijXWijX作为判别函数，训练是以i类样本和j类样本进行训练。

情况三：对于情况三，我们可以扩展以下感知器算法来进行学习。

对于M类的情况需要建立M个线性判别函数diX，假如diXdjX,ji，则判别Xi。下面给出扩展的感知器学习算法：

现有L个训练样本，分别属于不同的类别，X1,X2,,XL，首先对每一个样本进行增广的特征矢量（只须增加一维特征1，而不需要改变符号）。

1. 初始化，L个权矢量Wi1,i1,2,,L，选择一个迭代常数C，置步数k1； 2. 输入训练模式的增广特征矢量Xk，计算L个判别函数：

diXkWiTkXk，i1,2,,L

3. 修改权矢量，规则为：

若Xki，并且diXkdjXk，ji

则Wik1Wik，i1,2,,L；

若Xki，而dlXkdiXk

则Wik1WikCXk； WCXk； lk1Wlk Wjk1Wjk，ji,l；

kk1

4. 重复2，3步骤，当kL时，检测当前的L个判别函数是否能够对全部的训练样

本正确分类（亦即权值未经过任何修改），若是，则结束；否则

3.4 非线性判别函数的学习

对于有些问题来说。可以在N维空间中构造线性函数来进行分类，而有一些问题，在N

维空间中是可分的，但不是线性可分的，对于这一类问题就需要使用非线性判别函数进行分类。然而非线性判别函数的构造却是一个比较困难的问题，在本节中我们给出一些学习非线

28

性判别函数的思路。

一、二次判别函数

对于某些问题来说，我们无法用N维空间中的一次线性函数进行区分，但是可以一个二次函数来区分。比如说“异或问题”，我们就可以用一个椭圆的二次判别函数来进行分类，椭圆内部的是一类，椭圆外部的是一类。

现在的问题是如何来学习这样的二次判别函数。现在我们以2维空间中的两类问题为例来说明，2维欧氏空间中一个一般的二次函数可以表示为：

2dXa1x1a2x2a3x12a4x2a5x1x2a6

解决上述问题，我们可以将一个2维空间中的分类问题转化为5维空间中的分类问题，

22其它3维由x1，x2和x1x2构成，如果这个问题在2维空间中是2次判别函数可分的，那么

在新的5维空间中，就应该是线性可分的，我们可以首先将训练样本进行扩展，转换到5维空间中，然后利用前面介绍的线性分类器的学习算法训练出一个5维空间中的线性分类器，在转换到2维空间中，就构成了一个2次判别函数。

下面以“异或”问题为例来加以说明：

在2维空间中的训练样本：1：

0,0,(1,1)，：0,1,(1,0)，转化到5维空

2间中：1：0,0,0,0,0,(1,1,1,1,1)，2：0,1,0,1,0,(1,0,1,0,0)，采用感知器算法进行训练，得到一个2次的判别函数：

2dX0.6636x11.0056x20.4189x120.8578x23.3908x1x20.6207

判别界面如下图所示，是一个双曲线：

29

这种方法也存在着一定的缺陷，并不是说所有的问题都可以用二次判别函数来解决，当判别函数的次数升高时，相应的特征维数会增加的很多；即使是二次函数，当原始特征维数比较大时，为数增长的也会比较快，对N特征矢量来说，进行二次扩展后，维数变为：

2NN12。一般来说，随着特征维数的增加，训练问题的解决也越难，算法的收敛

的速度也越慢。

二、分段线性函数

对于有一些问题来说，我们可以采用分段线性函数来进行分类，比如下图所示的问题：

子类1类别1子类1子类2类别2子类2类别1子类3 类别1和类别2无法用一个线性函数区分，但是我们可以用五个线性函数构成一个分段线性函数来建立分类器。但是分段线性函数的确定也还是一个比较困难的问题，下面介绍几种解决方案。

1. 基于聚类的方法

我们可以采用上一章中介绍的聚类分析的办法，现将每个类别聚成若干个子类，比如上图中，类别1聚成两个子类，类别2聚成3个子类，两个类别中的不同子类之间线性可分。这样我们就可以分别对两个类别中的子类建立线性判别函数，然后将这些线性判别函数组合到一起就可以构成一个分段线性的分类界面。

实际上，上一章中介绍的多个标准样本的距离分类器就是一个分段线性的判别函数分类器。只不过分类界面垂直平分对应的两个标准样本的连线。 2. 逐块两分法

如下图所示，首先选择一个超平面将空间分为两部分，由于两类线性不可分，所以在每一个空间中必然都有两类的样本，但是在其中的一个空间中有可能两类已经线性可分了，比如左面的一半空间，那么在这一块空间中可以建立一个线性分类器将两类分开；然而在右面的一半空间中还是线性不可分的，仍然可以采用同样的办法，选择一个超平面，在将这一半空间分为两部分；重复上述过程，直至所有的空间中，两类样本都线性可分为止。将这些选择的超平面和最后建立的线性判别函数组合到一起，就可以构成一个分段线性的判别函数。

这里存在的问题就是，如何来选择超平面将空间分为两部分。选择的好，用很少的线性判别函数就可以解决问题，选择得不好，所用的线性判别函数就会很多。到目前为止还没有一个完美的算法能够找到这种最优的解决方案。只能采用一些次优的方法进行搜索。比如每次选择超平面时，尽量使得同一块空间中同类样本的数目尽量多。

30

类别1类别2类别1类别2

三、其它非线性判别函数方法

非线性判别函数的训练方法还有很多，例如可以用一些比较简单的函数的线性组合来逼近所求的非线性判别函数，可以用多项式函数来逼近非线性函数，也可以用指数函数的线性组合逼近非线性函数。

另外一种比较实用的办法是采用多层感知器，即前馈神经网络来实现非线性的分类问题。

31