武汉大学模式识别第三章课件

《武汉大学模式识别第三章课件》由会员分享，可在线阅读，更多相关《武汉大学模式识别第三章课件（75页珍藏版）》请在金锄头文库上搜索。

1、第三章 判别函数,第三章 判别函数,3.1 线性判别函数 3.2 广义线性判别函数 3.3 分段线性判别函数 3.4 模式空间和权空间 3.5 Fisher线性判别 3.6 感知器算法 3.7 采用感知器算法的多类模式的分类 3.8 可训练的确定性分类器的迭代算法 3.9 势函数法 一种确定性的非线性分类算法 3.10 决策树简介,3.1 线性判别函数,3.1.1 用判别函数分类的概念 模式识别系统的主要作用 判别各个模式所属的类别 对一个两类问题的判别，就是将模式x划分成1和2两类。,3.1 线性判别函数,3.1.1 用判别函数分类的概念 描述：两类问题的判别函数,3.1 线性判别函数,3.

2、1.1 用判别函数分类的概念 用判别函数进行模式分类依赖的两个因素 （1）判别函数的几何性质：线性的和非线性的函数。 线性的是一条直线； 非线性的可以是曲线、折线等； 线性判别函数建立起来比较简单（实际应用较多）； 非线性判别函数建立起来比较复杂。 （2）判别函数的系数：判别函数的形式确定后，主要就是确定判别函数的系数问题。 只要被研究的模式是可分的，就能用给定的模式样本集来确定判别函数的系数。,3.1 线性判别函数,3.1.2 线性判别函数 n维线性判别函数的一般形式 权向量 增广模式向量 增广权向量 分类问题 两类情况：判别函数d(x) 多类情况：设模式可分成1, 2, M共M类，则有三种

3、划分方法 多类情况1 多类情况2 多类情况3,3.1 线性判别函数,3.1.2 线性判别函数 分类问题 多类情况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和多

4、类情况2的比较 对于M类模式的分类，多类情况1需要M个判别函数，而多类情况2需要M*(M-1)/2个判别函数，当M较大时，后者需要更多的判别式（这是多类情况2的一个缺点）。 采用多类情况1时，每一个判别函数都要把一种类别的模式与其余M-1种类别的模式分开，而不是将一种类别的模式仅于另一种类别的模式分开。 由于一种模式的分布要比M-1种模式的分布更为聚集，因此多类情况2对模式是线性可分的可能性比多类情况1更大一些（这是多类情况2的一个优点）。,作业（1）,在一个10类的模式识别问题中，有3类单独满足多类情况1，其余的类别满足多类情况2。问该模式识别问题所需判别函数的最少数目是多少？,作业（2）,

5、一个三类问题，其判别函数如下： d1(x)=-x1, d2(x)=x1+x2-1, d3(x)=x1-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

6、.2 广义线性判别函数,基本思想 设有一个训练用的模式集x，在模式空间x中线性不可分，但在模式空间x*中线性可分，其中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)的总项

7、数 说明 d(x)的项数随r和n的增加会迅速增大，即使原来模式x的维数不高，若采用次数r较高的多项式来变换，也会使变换后的模式x*的维数很高，给分类带来很大困难。 实际情况可只取r=2，或只选多项式的一部分，例如r=2时只取二次项，略去一次项，以减少x*的维数。,3.2 广义线性判别函数,例子：一维样本空间 -二维样本空间,作业,两类模式，每类包括5个3维不同的模式，且良好分布。如果它们是线性可分的，问权向量至少需要几个系数分量？假如要建立二次的多项式判别函数，又至少需要几个系数分量？（设模式的良好分布不因模式变化而改变。）,3.3 分段线性判别函数,出发点 线性判别函数在进行分类决策时是最简

8、单有效的，但在实际应用中，常常会出现不能用线性判别函数直接进行分类的情况。 采用广义线性判别函数的概念，可以通过增加维数来得到线性判别，但维数的大量增加会使在低维空间里在解析和计算上行得通的方法在高维空间遇到困难，增加计算的复杂性。 引入分段线性判别函数的判别过程，它比一般的线性判别函数的错误率小，但又比非线性判别函数简单。,3.3 分段线性判别函数,图例：用判别函数分类 可用一个二次判别函数来分类 也可用一个分段线性判别函数来逼近这个二次曲线,3.3 分段线性判别函数,分段线性判别函数的设计 采用最小距离分类的方法 最小距离分类,3.3 分段线性判别函数,图例：分段线性分类设计,3.4 模式

9、空间和权空间,分类描述 模式空间 对一个线性方程w1x1+w2x2+w3x3=0，它在三维空间(x1 x2 x3)中是一个平面方程式，w=(w1 w2 w3)T是方程的系数。 把w向量作为该平面的法线向量，则该线性方程决定的平面通过原点且与w垂直。,3.4 模式空间和权空间,模式空间 若x是二维的增广向量，此时x3=1，则在非增广的模式空间中即为x1, x2 二维坐标，判别函数是下列联立方程的解 w1x1+w2x2+w3=0 x3=1 即为这两个平面相交的直线AB 此时，w =(w1 w2)T为非增广的权向量，它与直线AB垂直；AB将平面分为正、负两侧，w离开直线的一侧为正， w射向直线的一侧

10、为负。,3.4 模式空间和权空间,模式空间 增广向量决定的平面 非增广向量决定的直线,3.4 模式空间和权空间,权空间 若将方程x1w1+x2w2+w3=0绘在权向量w=(w1 w2 w3)T的三维空间中，则x=(x1 x2 1)T为方程的系数。 若以x向量作为法线向量，则该线性方程所决定的平面为通过原点且与法线向量垂直的平面，它同样将权空间划分为正、负两边。 在系数x不变的条件下，若w值落在法线向量离开平面的一边，则wTx0，若w值落在法线向量射向平面的一边，则wTx 0。,3.4 模式空间和权空间,权空间中判别界面的平面示意图,3.5 Fisher线性判别,出发点 应用统计方法解决模式识别

11、问题时，一再碰到的问题之一就是维数问题。 在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。 因此，降低维数有时就会成为处理实际问题的关键。,3.5 Fisher线性判别,问题描述 考虑把d维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维。 然而，即使样本在d维空间里形成若干紧凑的互相分得开的集群，当把它们投影到一条直线上时，也可能会是几类样本混在一起而变得无法识别。 但是，在一般情况下，总可以找到某个方向，使在这个方向的直线上，样本的投影能分得开。,3.5 Fisher线性判别,问题描述 问题：如何根据实际情况找到一条最好的、最易于分类的投影线，这就是Fisher

12、判别方法所要解决的基本问题。,3.5 Fisher线性判别,从d维空间到一维空间的一般数学变换方法 假设有一集合包含N个d维样本x1, x2, , xN，其中N1个属于1类的样本记为子集1， N2个属于2类的样本记为子集2 。若对xn的分量做线性组合可得标量： yn = wTxn, n=1,2,N 这样便得到N个一维样本yn组成的集合，并可分为两个子集1和2 。,3.5 Fisher线性判别,从d维空间到一维空间的一般数学变换方法 实际上，w的值是无关紧要的，它仅是yn乘上一个比例因子，重要的是选择w的方向。w的方向不同，将使样本投影后的可分离程度不同，从而直接影响的分类效果。 因此，上述寻找

13、最佳投影方向的问题，在数学上就是寻找最好的变换向量w*的问题。,3.5 Fisher线性判别,Fisher准则函数的定义 几个必要的基本参量 我们希望投影后，在一维Y空间中各类样本尽可能分得开些，即希望两类均值之差越大越好，同时希望各类样本内部尽量密集，即希望类内离散度越小越好。 Fisher准则函数定义 最佳变换向量w*的求取,3.5 Fisher线性判别,基于最佳变换向量w*的投影 w*是使Fisher准则函数JF(w)取极大值时的解，也就是d维X空间到一维Y空间的最佳投影方向。有了w*，就可以把d维样本x投影到一维，这实际上是多维空间到一维空间的一种映射，这个一维空间的方向w*相对于Fi

14、sher准则函数JF(w)是最好的。 利用Fisher准则，就可以将d维分类问题转化为一维分类问题，然后，只要确定一个阈值T，将投影点yn与T相比较，即可进行分类判别。,3.6 感知器算法,出发点 一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。 在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到。 感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。,3.6 感知器算法,基本思想 采用感知器算法(Perception Approach)能通过对训练模式样本集的“学习”得到判别函数的系数。 说明 这

15、里采用的算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法。,3.6 感知器算法,背景 “感知器”一词出自于20世纪50年代中期到60年代中期人们对一种分类学习机模型的称呼，它是属于有关动物和机器学习的仿生学领域中的问题。 当时的一些研究者认为感知器是一种学习机的强有力模型，后来发现估计过高了，但发展感知器的一些相关概念仍然沿用下来。,3.6 感知器算法,感知器的训练算法 感知器算法实质上是一种赏罚过程 对正确分类的模式则“赏”，实际上是“不罚”，即权向量不变。 对错误分类的模式则“罚”，使w(k)加上一个正比于xk的分量。 当用全部模式样本训练过一轮以后，只要有一个模式是判别

16、错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。 如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。,3.6 感知器算法,例子 感知器算法的收敛性 只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。（证明作为练习）,作业及编程,用感知器算法求下列模式分类的解向量w: 1: (0 0 0)T, (1 0 0)T, (1 0 1)T, (1 1 0)T 2: (0 0 1)T, (0 1 1)T, (0 1 0)T, (1 1 1)T 编写求解上述问题的感知器算法程序。,3.7 采用感知器算法的多类模式的分类,采用3.1的多类情况3，将感知器算法推广到多类模式。 感知器算法判别函数的推导 例子,3.7 采用感知器算法的多类模式的分类,讨论 这里的分类算法都是通过模式样本来确定判别函数的系数，但一个分类器的判断性能最终要受并未用于训练的那些未知样本来检验。 要使一个分类器设计完善，必须采用有代表性的训练数据，它能够合理反映模式数据的整体。,3.7 采用感知器算法的多类模式的分类,讨论 要获得一个判别性能好的线性分类器，究竟需要多少训练样本？ 直