第3章 线性判别函数

第三章线性判别函数

在上一章中我们讨论了贝叶斯决策理论和统计判别方法。从原理上说贝叶斯决策理论采用了在d维特征空间中样本分布的最一般描述方式，即统计分布来描述，并且采用分类器中最重要的指标——错误率作为产生判别函数和决策面的依据，因此它给出了最一般情况下适用的“最优”分类器设计方法，对各种不同的分类器设计技术在理论上都有指导意义。但是直接使用贝叶斯决策理论需要首先得到有关样本总体分布的知识，具体说来包括各类先验概率P(ω1)及类条件概率密度函数，从而可以计算出样本的后验概率P(ω1|X)，并以此作为产生判别函数的必要数据，设计出相应的判别函数与决策面。

3.1.1线形判别函数的基本概念

在一个d维的特征空间中,线性判别函数的一般表达式如下：其中，，称为权向量是个常数，称为阈值权。（3-1）在两类情况下，仅用一个判别函数：判别规则：若,则,,则,,则可将x分到任一类,或拒绝（3-2）方程g(x)=0定义了一个决策面。当g(x)为线性函数时，这个决策面便是超平面。假设和都在决策面H上，则有或这表明，w和超平面H上任一向量正叫交，即w是H的法向量。（3-3）（3-4）判别函数g(x)可以看成是特征空间中某点x到超平面的距离的一种代数度量，见图4.1。若把x表示成式中：是x在H上的投影向量；r:是x到H的垂直距离；：是w方向上的单位向量。（3-5）

图3.1线性判别函数将式（3-5）代入（3-1），可得

或写作若x为原点，则从原点到超平面的距离（3-6）（3-7）（3-8）3.1.2广义线性判别函数图3.2二次判别函数举例线性判别函数是形式最为简单的判别函数，但是它不能用于稍复杂一些的情况，例如，建立一个二次判别函数决策规则是二次判别函数可写成适当选择从x到y的影射，则可把函数化成y的线性函数（3-9）（3-10）（3-11）

式中称为广义判别函数，叫做广义权向量（3-12）

在Y空间定义了一通过原点的超平面Y空间中任意一点y到超平面的距离为其中Y叫做增广样本向量，a叫做增广权向量。

将非线性函数用映射的方法变成线性函数的形式，如(3-11)，(3-12)式所示，但一个重要问题是维数会增加很多。用传统方法处理模式识别问题是希望降低维数，而不希望增加维数，因此不提倡使用，但支持向量机却注重它能将非线性分类问题转化为线性分类问题，因而主张采用。3.1.3设计线性分类器的主要步骤

所谓设计线性分类器，就是利用训练样本建立线性判别函数式（3-1）或广义线性判别函数式（3-12）。设计线性分类器的过程实际就是找最好的w和w0的过程。设计线性分类器的主要步骤：1.训练样本集常用x={x1,x2,…xn}表示，由训练样本集x所确定的加权向量称为解向量w*。2.确定一个准则函数J,它必须满足：(1)J是样本集和、或a的函数(2)J的值能反映分类器的性能3.求出准则函数的极值解和或。这样就得到线性判别函数换一个方式说，设计线性分类器，是指所用的判别函数、分界面方程的类型已选定为线性类型，因此主要的设计任务是确定线性方程的两个参数，一个是权向量W，另一个是阈值w0。为了使所设计的线性分类器在性能上要满足一定的要求，这种要求通过一种准则来体现，并且要表示成一种准则函数，以便能通过将准则函数值优化的方法确定W与w0。3.2Fisher线性判别由于线性判别函数易于分析，关于这方面的研究工作特别多。历史上，这一工作是从R.A.Fisher的经典论文（1936年）开始的。我们知道，在用统计方法进行模式识别时，许多问题涉及到维数，在低维空间行得通的方法，在高维空间往往行不通。因此，降低维数就成为解决实际问题的关键。Fisher的方法，实际上涉及维数压缩。如果要把模式样本在高(d)维的特征向量空间里投影到一条直线上，实际上就是把特征空间压缩到一维，这在数学上容易办到。另外，即使样本在高维空间里聚集成容易分开的群类，把它们投影到一条任意的直线上，也可能把不同的样本混杂在一起而变得无法区分。也就是说，直线的方向选择很重要。如上所述，设计线性分类器首先要确定准则函数，然后再利用训练样本集确定该分类器的参数，以求使所确定的准则达到最佳。该分类器的参数决定后，在使用线性分类器时，未知样本的分类由其判别函数值决定，而每个样本的判别函数值是其各分量的线性加权和再加上一阈值w0。在一般情况下，总可以找到某个最好的方向，使样本投影到这个方向的直线上是最容易分得开的。如何找到最好的直线方向，如何实现向最好方向投影的变换，是Fisher法要解决的基本问题。这个投影变换就是我们寻求的解向量。

换句话说，Fisher准则的基本原理，就是要找到一个最合适的投影轴，使两类样本在该轴上投影的交迭部分最少，从而使分类效果为最佳。图3.3从d维空间到一维空间的方法设有d维样本，其中个属于类的样本集X1，个属于类的样本集X2，若对的分量做线性组合可得标量这样就得到N个一维样本组成的集合，并可分为两个子集。因此，前述寻找最好投影方向的问题，在数学上就是寻找最好的变换向量的问题。在图3.3中，分析w1方向之所以比w2方向优越，可以归纳出这样一个准则，即向量W的方向选择应能使两类样本投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。这就是Fisher准则函数的基本思路。为了将这个思路变为可计算的函数值，我们先对一些基本参量下定义。

基本参量在d维X空间

(1)各类样本均值向量(2)样本类内离散度矩阵和总类内离散度矩阵

(3)样本类间离散度矩阵其中是对称半正定矩阵，而且当N>d时通常是非奇异的。2.在一维Y空间(1)各类样本均值(2)样本类内离散度和总类内离散度定义准则函数

显然，我们希望在映射之后，两类的平均值之间的距离越大越好，而各类的样本类内离散度越小越好。因此，定义Fisher准则函数

——广义Rayleigh商下面求使取极大值时的令分母等于非零常数，也就是：定义lagrange函数：

对w求偏导数：

令偏倒数为零，得因为非奇异，可得式中从而可得忽略比例因子(3-32)向量就是使Fisher准则函数达极大值的解，也就是按Fisher准则将d维X空间投影到一维Y空间的最佳投影方向。由(3-32)表示的最佳投影方向是容易理解的，因为其中一项(m1-m2)是一向量，显然从两类均值在变换后距离最远这一点看，对与(m1-m2)平行的向量投影可使两均值点的距离最远。但是如从使类间分得较开，同时又使类内密集程度较高这样一个综合指标来看，则需根据两类样本的分布离散程度对投影方向作相应的调整，这就体现在对(m1-m2)

向量按

作一线性变换，从而使Fisher准则函数达到极值点。3.Fisher算法步骤由Fisher线性判别式求解向量的步骤：①把来自两类的训练样本集X分成和两个子集和。②由，计算。③由计算各类的类内离散度矩阵。④计算类内总离散度矩阵。⑤计算的逆矩阵。⑥由求解。分类问题：只要确定一个阀值，将投影点与相比较，便可做出决策。一维分类问题的基本原则：(1)当维数d和样本数N都比较大时，可采用贝叶斯决策规则，从而获得一种在一维空间的“最优”分类器。(2)上述条件不满足，可利用先验知识选定分界阀值点，如选择对于任意给定的未知样本x,只要计算它的投影点y，再根据决策规则就可以判断x属于什么类别。作业：一、设五维空间的线性方程为：55X1＋68X2＋32X3＋16X4＋26X5+10=0试求出其权向量与样本向量点积的表达式WTX+w0=0中的W、X以及增广权向量与增广样本向量形式aTY中的a和Y。同时求出该五维空间超平面到坐标原点的法向距离。二、设两类样本的类内离散矩阵分别为：m1=(2,0)T,m2=(2,2)T,试用fisher准则求其决策面方程。3.3感知准则函数1、线性可分性如果存在一个权向量a，使得对于任何y∈w1，都有aTy>0，而对于任何y∈w2，都有aTy<0，则称这组样本集是线性可分的；反过来，如果样本集是线性可分的，则必然存在一个权向量a，能将每个样本正确的分类。2、样本的规范化感知准则函数使用增广样本向量与增广权向量，即用(3-11)中的d+1维向量y表示样本的齐次化增广向量，用判别函数中的权向量W与阈值权组合成增广权向量a。而判别函数则表示成(3-12)，即

在两类别情况下，判别准则是：

为了计算方便起见，我们可将第二类样本都取其反向向量，即令

那么，对于能将所有样本正确分类的决策面来说，应有

上述过程称为样本的规范化，叫做规范化增广样本向量权向量a可理解为权空间中的一点，每个样本yn对a的位置都起限制，即要求aTyn>0。方程aTyn＝0确定了一个经过权空间原点的超平面，解向量必存在于超平面的正侧；N个样本将产生N个超平面，所以解向量必存在于N个正半空间的重合区，该重合区中的任意向量都是解向量a。讨论完了问题的提法后，下一步要解决如何找到这样一个合适的a。感知准则函数方法的思路是：先随意找一个初始向量a，写作a(0)，然后用训练样本集中的每个样本来计算。一旦发现有的Y‘使aTY’<0，则说明当前的广义权向量a不适合还需要进一步修正。修正的原理也很简单，设当前经k次叠代修正的广义权向量为a(k)，若有发现一个Y'出现aTY'<0，则只要a(k+1)=a(k)+pkY',

pk(步长系数)为正，则必有a(k+1)TY‘=a(k)TY’+pkY‘TY’>a(k)TY‘，

就有趋势做到使a(k+1)TY’>0。

当然，修改后的a(k+1)还可以使某些Y‘出现a(k+1)TY’<0的情况，理论证明，只要训练样本集线性可分，无论a(0)的初值是什么，经过有限次叠代，都可得到满意的a。

3.4多类问题以上讨论的都是两类别问题，但是实际问题中常遇到的是多类别问题。在两类别问题中使用的线性判别函数方法可以推广到多类别问题中，但可有不同做法。一种最简单作法是将C类别问题化为(C-1)个两类问题，即将第i类与所有非i类样本，按两类问题确定其判别函数与决策面方程。因此对于C类，则总共有(C-1)个两类别问题这种做法存在两个问题，一是可能会出现一些不定区域，如图中绿色阴影所示，在这些区域中的样本无法确定其类别。另一方面用线性判别函数对i类及所有非i类进行划分并不能保证获得性能良好的划分，硬性使用线性分类器可能会产生很不好的效果。另一种相对麻烦些的做法是将C类中的每两类别单独设计其线性判别函数，因此总共有C(C-1)/2个线性判别函数。这种方法如图所示。这种方法由于每个判别函数针对每两类别样本设计，预期可有好效果，但仍有不定区域，在该区域内样本类别无法确定。

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

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

如果

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

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

3.3.1

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

1

由于样本在特征空间分布的复杂性，许多情况下采用线性判别函数不能取得满意的分类效果。例如对上图所示两类物体在二维特征空间的分布，采用线性判别函数就无法取得满意的分类效果。在这种情况下，可以采用分段线性判别或二次函数判别等方法，效果就会好得多。与一般超曲面相比，分段线性判别函数是最为简单的形式，是非线性判别函数情况下最为常用的形式。除此之外二次判别函数是除线性及分段线性外最简单的形式。以下只讨论有关分段线性判别函数设计中的一些基本问题。与线性判别函数相比，分段线性判别函数设计中首先要解决的问题是分段线性判别函数的分段段数问题，显然这是一个与样本集分布有关的问题。分段段数过少，其分类效果必然要差；但段数又要尽可能少，以免分类判别函数过于复杂，增加分类决策的计算量。在有些实际的分类问题中，同一类样本可以用若干个子类来描述，这些子类的数目就可作为确定分段段数的依据。但多数情况下样本分布及合适子类划分并不知道，则往往需要采用一种聚类的方法(在以后讨论),设法将样本划分成相对密集的子类，然后用各种方法设计各段判别函数。由于在后面章节要讨论聚类问题，这一章主要讨论在样本分布及子类划分大体已定的情况下，设计分段线性判别函数的问题，着重讨论几种典型的设计原理。则分段线性判别函数的一般形式可定义为：

若把每一类分为若干个子类，即令其中

表示第i类第l段线性判别函数，li为i类所具有的判别函数个数，

与

分别是第l段的权向量与阈值权。相应的判别规则是：

至于分类的决策面方程取决于相邻的决策域，如第i类的第n个子类与第j类的第m个子类相邻，则由它们共同决定的决策面方程为：

结论：当每一类的样本数据在特征空间中的分布呈复杂修正时，使用线性判别函数就会产生很差的效果，如果能将它们分割成子集，而每个子集在空间聚集成团，那么子集与子集的线性划分就可以取得比较好的效果。因此分段线性判别的主要问题是如何对数据划分成子集的问题，或者说如何利用样本集确定子类数目以及如何求解各子类的权向量和阈值权。3.3.2基于距离的分段线性判别函数在正态分布条件下，两类别问题在各特征统计独立、同方差、且先验概率相等情况下，最小错误率决策可按最小距离决策，即：其中

与

为各类的均值。这样的分类器叫最小距离分类器

最小距离分类器用多个最小距离分类器组成分段线性分类面。尽管这是在一种很特殊的情况下得到的，但是按距离分类的原理是可以推广的，即把各类别样本特征向量的均值作为各类的代表点，而样本的类别按它到各类别代表点的最小距离划分。在这种判别函数中，决策面是两类别均值连线的垂直平分面。对于上图所示情况，若企图再用每类一个均值代表点产生最小距离分类器，就会产生很明显的错误率。在这种情况下，可以将各类别划分成相对密集的子类，每个子类以它们的均值作为代表点，然后按最小距离分类，把未知样本x归到离它最近的代表点所属的类，则可以有比较满意的效果。

例：未知x,如图：先与ω1类各子类的均值比较，即，找一个最近的与ω2各子类均值比较取最近的因g2(x)<g1(x)，所以x∈ω2类。归纳起来，分段线性距离分类器可理解为：如果对于ωi有li个子类，则有li个代表点，或者说把属于ωi的决策域Ri分成li个子域，对每个子区域Ril均值用表示，并以此作为该子区域的代表点，则判别函数定义为：

3.3.3错误修正算法错误修正算法原理：

ai与aj代表两类增广权向量，y则代表规范化的增广样本向量，这在感知准则函数中已定义过。aiTy是ai向量与y向量的点积，ajTy是aj向量与y向量的点积。一般来说点积值比较