1、第三章 判别函数,第三章 判别函数,3.1 线性判别函数 3.2 广义线性判别函数 3.3 分段线性判别函数 3.4 模式空间和权空间 3.5 感知器算法 3.6 采用感知器算法的多类模式的分类 3.7 势函数法 一种确定性的非线性分类算法,3.1 线性判别函数,3.1.1 用判别函数分类的概念 模式识别系统的主要作用 判别各个模式所属的类别 对一个两类问题的判别，就是将模式x划分成1和2两类。,3.1 线性判别函数,3.1.1 用判别函数分类的概念 描述：两类问题的判别函数,3.1 线性判别函数,3.1.1 用判别函数分类的概念 用判别函数进行模式分类依赖的两个因素 （1）判别函数的几何性质
2、：线性的和非线性的函数。 线性的是一条直线； 非线性的可以是曲线、折线等； 线性判别函数建立起来比较简单（实际应用较多）； 非线性判别函数建立起来比较复杂。 （2）判别函数的系数：判别函数的形式确定后，主要就是确定判别函数的系数问题。 只要被研究的模式是可分的，就能用给定的模式样本集来确定判别函数的系数。,3.1 线性判别函数,3.1.2 线性判别函数 n维线性判别函数的一般形式 权向量 增广模式向量 增广权向量 分类问题 两类情况：判别函数d(x) 多类情况：设模式可分成1, 2, M共M类，则有三种划分方法 多类情况1 多类情况2 多类情况3,3.1 线性判别函数,3.1.2 线性判别函数
3、 分类问题 多类情况1 判别函数 图例 例子,3.1 线性判别函数,3.1.2 线性判别函数 分类问题 多类情况2 判别函数 图例 例子,3.1 线性判别函数,3.1.2 线性判别函数 分类问题 多类情况3 判别函数 图例 例子,3.1 线性判别函数,3.1.2 线性判别函数 线性可分 模式分类如可用任一个线性函数来划分，则这些模式就称为线性可分的，否则就是非线性可分的。 一旦线性函数的系数wk被确定，这些函数就可用作模式分类的基础。,3.1 线性判别函数,3.1.2 线性判别函数 多类情况1和多类情况2的比较 对于M类模式的分类，多类情况1需要M个判别函数，而多类情况2需要M*(M-1)/2
4、个判别函数，当M较大时，后者需要更多的判别式（这是多类情况2的一个缺点）。 采用多类情况1时，每一个判别函数都要把一种类别的模式与其余M-1种类别的模式分开，而不是将一种类别的模式仅于另一种类别的模式分开。 由于一种模式的分布要比M-1种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些（这是多类情况2的一个优点）。,作业（1）,在一个10类的模式识别问题中，有3类单独满足多类情况1，其余的类别满足多类情况2。问该模式识别问题所需判别函数的最少数目是多少？,作业（2）,一个三类问题，其判别函数如下：d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1
5、-x2-1 设这些函数是在多类情况1条件下确定的，绘出其判别界面和每一个模式类别的区域。 设为多类情况2，并使：d12(x)= d1(x), d13(x)= d2(x), d23(x)= d3(x)。绘出其判别界面和多类情况2的区域。 设d1(x), d2(x)和d3(x)是在多类情况3的条件下确定的，绘出其判别界面和每类的区域。,3.2 广义线性判别函数,出发点 线性判别函数简单，容易实现； 非线性判别函数复杂，不容易实现； 若能将非线性判别函数转换为线性判别函数，则有利于模式分类的实现。,3.2 广义线性判别函数,基本思想设有一个训练用的模式集x，在模式空间x中线性不可分，但在模式空间x*
6、中线性可分，其中x*的各个分量是x的单值实函数，x*的维数k高于x的维数n，即若取x* = (f1(x), f2(x), ., fk(x), kn则分类界面在x*中是线性的，在x中是非线性的，此时只要将模式x进行非线性变换，使之变换后得到维数更高的模式x*，就可以用线性判别函数来进行分类。 描述,3.2 广义线性判别函数,广义线性判别函数的意义 线性的判别函数 fi(x)选用二次多项式函数 x是二维的情况 x是n维的情况 fi(x)选用r次多项式函数， x是n维的情况 例子 d(x)的总项数 说明 d(x)的项数随r和n的增加会迅速增大，即使原来模式x的维数不高，若采用次数r较高的多项式来变换
7、，也会使变换后的模式x*的维数很高，给分类带来很大困难。 实际情况可只取r=2，或只选多项式的一部分，例如r=2时只取二次项，略去一次项，以减少x*的维数。,3.2 广义线性判别函数,例子：一维样本空间 -二维样本空间,3.3 分段线性判别函数,出发点 线性判别函数在进行分类决策时是最简单有效的，但在实际应用中，常常会出现不能用线性判别函数直接进行分类的情况。 采用广义线性判别函数的概念，可以通过增加维数来得到线性判别，但维数的大量增加会使在低维空间里在解析和计算上行得通的方法在高维空间遇到困难，增加计算的复杂性。 引入分段线性判别函数的判别过程，它比一般的线性判别函数的错误率小，但又比非线性
8、判别函数简单。,3.3 分段线性判别函数,图例：用判别函数分类 可用一个二次判别函数来分类 也可用一个分段线性判别函数来逼近这个二次曲线,3.3 分段线性判别函数,分段线性判别函数的设计 采用最小距离分类的方法 最小距离分类,3.3 分段线性判别函数,图例：分段线性分类设计,3.4 模式空间和权空间,分类描述 模式空间 对一个线性方程w1x1+w2x2+w3x3=0，它在三维空间(x1 x2 x3)中是一个平面方程式，w=(w1 w2 w3)T是方程的系数。 把w向量作为该平面的法线向量，则该线性方程决定的平面通过原点且与w垂直。,3.4 模式空间和权空间,模式空间 若x是二维的增广向量，此时
9、x3=1，则在非增广的模式空间中即为x1, x2 二维坐标，判别函数是下列联立方程的解w1x1+w2x2+w3=0x3=1即为这两个平面相交的直线AB 此时，w =(w1 w2)T为非增广的权向量，它与直线AB垂直；AB将平面分为正、负两侧，w离开直线的一侧为正， w射向直线的一侧为负。,3.4 模式空间和权空间,模式空间 增广向量决定的平面 非增广向量决定的直线,3.4 模式空间和权空间,权空间 若将方程x1w1+x2w2+w3=0绘在权向量w=(w1 w2 w3)T的三维空间中，则x=(x1 x2 1)T为方程的系数。 若以x向量作为法线向量，则该线性方程所决定的平面为通过原点且与法线向量
10、垂直的平面，它同样将权空间划分为正、负两边。 在系数x不变的条件下，若w值落在法线向量离开平面的一边，则wTx0，若w值落在法线向量射向平面的一边，则wTx 0。,3.4 模式空间和权空间,权空间中判别界面的平面示意图,作业,两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。）,3.5 感知器算法,出发点 一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。 在模式识别中，系数确定的一个主要方法就是通过对已知样本的
11、训练和学习来得到。 感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。,3.5 感知器算法,基本思想 采用感知器算法(Perception Approach)能通过对训练模式样本集的“学习”得到判别函数的系数。 说明 这里采用的算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法。,3.5 感知器算法,背景 “感知器”一词出自于20世纪50年代中期到60年代中期人们对一种分类学习机模型的称呼，它是属于有关动物和机器学习的仿生学领域中的问题。 当时的一些研究者认为感知器是一种学习机的强有力模型，后来发现估计过高了，但发展感知器的一些相关概念仍然沿
12、用下来。,3.5 感知器算法,感知器的训练算法 感知器算法实质上是一种赏罚过程 对正确分类的模式则“赏”，实际上是“不罚”，即权向量不变。 对错误分类的模式则“罚”，使w(k)加上一个正比于xk的分量。 当用全部模式样本训练过一轮以后，只要有一个模式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。 如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。,3.5 感知器算法,例子感知器算法的收敛性 只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。（证明作为练习）,作业及编程,用感知器算法求下列模式分类的解向量w:1: (0 0 0)T, (1 0 0)T,
13、 (1 0 1)T, (1 1 0)T2: (0 0 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T编写求解上述问题的感知器算法程序。,3.6 采用感知器算法的多类模式的分类,采用3.1的多类情况3，将感知器算法推广到多类模式。 多类情况3 感知器算法判别函数的推导 例子,3.6 采用感知器算法的多类模式的分类,讨论 这里的分类算法都是通过模式样本来确定判别函数的系数，但一个分类器的判断性能最终要受并未用于训练的那些未知样本来检验。 要使一个分类器设计完善，必须采用有代表性的训练数据，它能够合理反映模式数据的整体。,3.6 采用感知器算法的多类模式的分类,讨论 要获得一个判
14、别性能好的线性分类器，究竟需要多少训练样本？ 直观上是越多越好，但实际上能收集到的样本数目会受到客观条件的限制； 过多的训练样本在训练阶段会使计算机需要较长的运算时间； 一般来说，合适的样本数目可如下估计：若k是模式的维数，令C=2(k+1)，则通常选用的训练样本数目约为C的1020倍。,作业,用多类感知器算法求下列模式的判别函数：1: (-1 -1)T2: (0 0)T3: (1 1)T,3.7 势函数法 一种确定性的非线性分类方法,目的 用势函数的概念来确定判别函数和划分类别界面。 基本思想 假设要划分属于两种类别1和2的模式样本，这些样本可看成是分布在n维模式空间中的点xk。 把属于1的
15、点比拟为某种能源点，在点上，电位达到峰值。 随着与该点距离的增大，电位分布迅速减小，即把样本xk附近空间x点上的电位分布，看成是一个势函数K(x, xk)。 对于属于1的样本集群，其附近空间会形成一个“高地”，这些样本点所处的位置就是“山头”。 同理，用电位的几何分布来看待属于2的模式样本，在其附近空间就形成“凹地”。 只要在两类电位分布之间选择合适的等高线，就可以认为是模式分类的判别函数。,3.7 势函数法 一种确定性的非线性分类方法,3.7.1 判别函数的产生 模式分类的判别函数可由分布在模式空间中的许多样本向量xk, k=1,2,和 的势函数产生。 任意一个样本所产生的势函数以K(x,
16、xk)表征，则判别函数d(x)可由势函数序列K(x, x1)， K(x, x2)，来构成，序列中的这些势函数相应于在训练过程中输入机器的训练模式样本x1，x2，。 在训练状态，模式样本逐个输入分类器，分类器就连续计算相应的势函数，在第k步迭代时的积累位势决定于在该步前所有的单独势函数的累加。 以K(x)表示积累位势函数，若加入的训练样本xk+1是错误分类，则积累函数需要修改，若是正确分类，则不变。,3.7 势函数法 一种确定性的非线性分类方法,3.7.1 判别函数的产生 逐步分析 从势函数可以看出，积累位势起着判别函数的作用 当xk+1属于1时，Kk(xk+1)0，或当xk+1属于2时，Kk(
17、xk+1)0，则积累位势不做任何修改就可用作判别函数。 由于一个模式样本的错误分类可造成积累位势在训练时的变化，因此势函数算法提供了确定1和2两类判别函数的迭代过程。 判别函数表达式,3.7 势函数法 一种确定性的非线性分类方法,3.7.2 势函数的选择 选择势函数的条件：一般来说，若两个n维向量x和xk的函数K(x, xk)同时满足下列三个条件，则可作为势函数。 K(x, xk)= K(xk, x)，并且当且仅当x=xk时达到最大值； 当向量x与xk的距离趋于无穷时，K(x, xk)趋于零； K(x, xk)是光滑函数，且是x与xk之间距离的单调下降函数。,3.7 势函数法 一种确定性的非线
18、性分类方法,3.7.2 势函数的选择 构成势函数的两种方式 第一类势函数 第二类势函数,3.7 势函数法 一种确定性的非线性分类方法,3.7.2 势函数的选择 例1,3.7 势函数法 一种确定性的非线性分类方法,3.7.2 势函数的选择 例2,3.7 势函数法 一种确定性的非线性分类方法,3.7.2 势函数的选择 讨论 用第二类势函数，当训练样本维数和数目都较高时，需要计算和存储的指数项较多。 正因为势函数由许多新项组成，因此有很强的分类能力。,作业（1）,用二次埃尔米特多项式的势函数算法求解以下模式的分类问题1: (0 1)T, (0 -1)T2: (1 0)T, (-1 0)T,作业（2）,用下列势函数求解以下模式的分类问题1: (0 1)T, (0 -1)T2: (1 0)T, (-1 0)T,
