《模式识别》课件 第三章 线性和非线性判别分析

第三章线性和非线性判别分析第三章线性和非线性判别分析3.1Fisher线性判别3.2感知准则函数3.3广义线性判别分析3.4k近邻3.5决策树第三章线性和非线性判别分析3.1Fisher线性判别3.2感知准则函数3.3广义线性判别分析3.4k近邻3.5决策树4贝叶斯估计：先验概率和类条件概率密度已知，通过贝叶斯公式，来求解后验概率的问题。实际问题中，类条件概率密度可能并不知道，这种情况下，可以采用非参数估计——当样本比较充足的时候，估计类条件概率密度的方法。但实际中，有时候并没有充分的样本，同时存在样本维数比较高，这种情况下，可能会使类条件概率密度估计不准确，我们就采用另一种方法。线性判别函数：我们直接假设判别函数，我们用样本估计判别函数的参数，这样就省去了估计类条件概率。在这一章之后，都采用这种方式。我们直接估计决策面或判别函数。这种情况下，最简单的是假设判别函数是线性函数。决策面是超平面。3.1Fisher线性判别5假设判别函数是线性的时候，利用样本用什么准则来求解这个判别函数的参数？当判别函数的参数有了，这个判别函数就确定了，这样决策面也就确定了。如果假设判别函数为线性函数，包含参数w和w0。当准则函数不同，求解出的参数就存在不同。贝叶斯决策中，最小错误率和最小风险就是准则函数，不同的准则最终判别函数存在不同。贝叶斯分类器，它使得错误率或风险达到最小，是所有分类器中的最优分类器。而其他准则函数下得到的分类器称为次优分类器。后续章节中介绍的准则函数，求出的是给定准则下的最优解。求得的最优解并不是这个问题的最优解。既然是次优解，为什么去研究？因为在样本有限情况下，简单容易实现，计算代价，存储量，求解速度快。所以，线性判别函数方法广泛使用。3.1Fisher线性判别63.1Fisher线性判别7方程g(x)=0定义了一个决策面，把归于不同类的点分割开来，当g(x)为线性函数时，这个决策面便是超平面。3.1Fisher线性判别8设计线性分类器的步骤3.1Fisher线性判别9Fisher线性判别出发点：—应用统计方法解决模式识别问题时，一再碰到的问题之一就是维数问题。—在低维空间里解析上或计算上行得通的方法，在高维空间里往往行不通。—降低维数有时就会成为处理实际问题的关键。问题描述：对两分类问题，考虑把d维空间的样本投影到一条直线上，形成一维空间，即把维数压缩到一维，同时保持较好的分类性能。3.1Fisher线性判别引言10如何根据实际数据找到一条最好的、最易于分类的投影方向，这就是Fisher判别方法所要解决的基本问题。（1）降低维数，降低计算复杂度；（2）易于分类的；3.1Fisher线性判别11假设有一集合D包含m个n维样本{x1,x2,…,xm}

第一类样本集合记为D1，规模为N1第二类样本集合记为D2，规模为N2若对xi的分量做线性组合可得标量：yi

=wTxi,i=1,2,…,m这样便得到m个一维样本yi组成的集合，并可分为两个子集D'1和D'2。从d维空间到一维空间的一般数学变换方法—w的值是无关紧要的，它仅使x乘上一个比例因子，重要的是选择w的方向。它将影响样本投影后的可分离程度。—上述寻找最佳投影方向的问题，在数学上就是寻找最好的变换向量w*的问题。3.1Fisher线性判别Fisher准则函数基本思想12最佳投影方向的评价依据：

使两类样本在该轴上投影之间的距离尽可能远，而每一类样本的投影尽可能紧凑。如何度量？评价标准—类内离散度矩阵，类间离散度矩阵x1x2w1H:g=0w23.1Fisher线性判别13

在n维X空间(1)各类样本的均值向量：(2)样本类内离散度矩阵Si和总样本类内离散度矩阵SwFisher准则函数中的基本参量其中Sw是对称半正定矩阵，而且当m>n时通常是非奇异的。(3)样本类间离散度矩阵Sb其中Sb是对称半正定矩阵。3.1Fisher线性判别14

在一维Y空间(1)各类样本的均值:

(2)样本类内离散度

和总样本类内离散度Fisher准则函数中的基本参量(3)样本类间离散度3.1Fisher线性判别15

目标：投影后，在一维Y空间中各类样本尽可能分得开些，即使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求.Fisher准则函数3.1Fisher线性判别16

目标：投影后，在一维Y空间中各类样本尽可能分得开些，即使原样本向量在该方向上的投影能兼顾类间分布尽可能分开，类内样本投影尽可能密集的要求.Fisher准则函数：Fisher最佳投影方向的求解:不同类的投影点尽量分开同一类的投影点尽量靠近Fisher准则函数3.1Fisher线性判别17Fisher准则函数由各类样本均值可推出：投影样本均值之差可以展开为：将J(w)变成w的显函数3.1Fisher线性判别18由类内散布矩阵可推出：于是有：Fisher准则函数准则函数可以写为：3.1Fisher线性判别19要求使J(w)最大的w，可以采用Lagrange乘子法求解。假设分母等于非零常数，即：定义Lagrange函数为：最佳变换向量w*的求取

矩阵/向量求导法则3.1Fisher线性判别20要求使J(w)最大的w，可以采用Lagrange乘子法求解。假设分母等于非零常数，即：定义Lagrange函数为：对w求偏导数，令偏导数为0：即：标量R最佳变换向量w*的求取

3.1Fisher线性判别21由于w的模对问题本身无关紧要，因此降维：对样本集合作线性变换w*Tx，得到n个样本投影后

的样本值y1，y2，……，ynFisher线性判别分析3.1Fisher线性判别22一维空间的分类面是一个点将两类分开即是确定一个阈值分类规则:Fisher线性分类3.1Fisher线性判别23例：两组训练数据D1和D2D1=[-0.4,0.58,0.089;-0.31,0.27,-0.04;-0.38,0.055,-0.035;-0.15,0.53,0.011;-0.35,0.47,0.034;0.17,0.69,0.1;-0.011,0.55,-0.18;-0.27,0.61,0.12;-0.065,0.49,0.0012;-0.12,0.054,-0.063]D2=[0.83,1.6,-0.014;1.1,1.6,0.48;-0.44,-0.41,0.32;0.047,-0.45,1.4;0.28,0.35,3.1;-0.39,-0.48,0.11;0.34,-0.079,0.14;-0.3,-0.22,2.2;1.1,1.2,-0.46;0.18,-0.11,-0.49]例题3.1Fisher线性判别（1）求取两组训练数据D1和D2的均值向量

和由公式：得:例题3.1Fisher线性判别（2）然后求取两组训练数据D1和D2的类内散度矩阵Si和总样本类内离散度矩阵Sw。由公式：得:例题3.1Fisher线性判别（3）求取最佳变换向量w*

由公式：得投影方向（4）求阈值由公式：得例题3.1Fisher线性判别（5）将两组训练数据D1和D2作线性变换，得到20个样本投影后的样本值两组数据投影后的样本值分别为：例题3.1Fisher线性判别28训练效果图：例题3.1Fisher线性判别测试数据和

：计算投影变换和：由：得：判别准则：例题3.1Fisher线性判别301.Fisher辨别分析要求：在UCI数据集上的Iris和sonar数据上验证算法的有效性；Iris数据3类，4维，150个数据；Sonar数据2类，60维，208个样本；训练和测试样本有三种方式进行划分：（三选一）1）将数据随机分训练和测试，多次平均求结果2）k折交叉验证3）留1法仿真结果+报告。第一次大作业3.1Fisher线性判别第三章线性和非线性判别分析3.1Fisher线性判别3.2感知准则函数3.3广义线性判别分析3.4k近邻3.5决策树几个基本概念线性可分样本的规范化解向量和解区对解区的限制3.2感知准则函数线性可分性假设样本集，为样本个数m，为n维向量，其中包含两类和。如果存在一个向量，满足如下条件，则称样本集是线性可分的，反之是线性不可分的。33几个基本概念3.2感知准则函数样本的规范化对于线性可分的样本集，若令则样本集线性可分的条件可改写为。上述过程就被称为样本的规范化。被称为规范化增广样本向量，后续介绍中，我们简化记为。34几个基本概念3.2感知准则函数解向量和解区对于线性可分的一组样本(规范化增广样本向量)，若存在一个权向量满足则称为一个解向量，在权值空间中所有解向量组成的区域称作为解区。35几个基本概念3.2感知准则函数对解区的限制由于解向量不唯一，我们可以通过加入额外的限制得到更好的选择。一般认为，越靠近解区中间的解向量，似乎越能对新的样本正确分类。因此，我们可以选找一个单位长度的解向量使之最大化样本到分界面的距离，也可以引用一个余量

，寻找对所有样本满足的最小长度的向量。新的解区位于原解区之中，而且它的边界到原解区边界的距离为。实际上，只要解向量严格位于解区之中都能满足要求，这里引入余量主要是为了避免求解权向量的算法收敛到解区边界的某点上。36几个基本概念3.2感知准则函数37几个基本概念解向量和解区的两维示意图解区里面的向量叫解向量；让它线性可分的解不唯一；准则不同，落在这个解区中的解不同；但准则确定，解一般是唯一的。3.2感知准则函数感知准则出发点一旦判别函数的形式确定下来，不管它是线性的还是非线性的，剩下的问题就是如何确定它的系数。在模式识别中，系数确定的一个主要方法就是通过对已知样本的训练和学习来得到。感知器算法就是通过训练样本模式的迭代和学习，产生线性（或广义线性）可分的模式判别函数。感知准则函数，是人工神经网络的雏形，最早的人工神经网络就是感知器神经网络。感知器准则求解过程，线性判别函数形式一但确定，通过样本不断试错纠正迭代来求解更新参数w和w0的过程。给定一个w和w0的初始值，来一个样本，如果这个参数结果不好，就进行修正，如果结果好，就保留，不断这样迭代，等所有样本都可以正确划分，保留这时的参数，就是最终要求解的参数。3.2感知准则函数感知器算法基本思想采用感知器算法(PerceptionApproach)能通过对训练模式样本集的“学习”得到判别函数的系数说明这里采用的算法不需要对各类别中模式的统计性质做任何假设，因此称为确定性的方法。3.2感知准则函数对于权向量w，如果某个样本被错误分类，。我们可以用对所有错分样本的求和来表示对错分样本的惩罚，定义感知器准则函数：当且仅当函数取得最小值0时，求得最优的w。可以用梯度下降法进行求解。3.2感知准则函数样本线性可分满足：其中，梯度下降算法3.2感知准则函数梯度下降算法梯度是一个向量，它的最重要性质就是指出了函数f在其自变量y增加时最大增长率的方向。负梯度指出f的最陡下降方向利用这个性质，可以设计一个迭代方案来寻找函数的最小值3.2感知准则函数讨论若正确地选择了准则函数J(w,x)，则当权向量w是一个解时，J达到极小值（J的梯度为零）。为了使权向量能较快地收敛于一个使函数J极小的解，C值的选择是很重要的。若C值太小，则收敛太慢；若C值太大，则搜索可能过头，引起发散。梯度下降算法3.2感知准则函数3.2感知准则函数感知器算法3.2感知准则函数感知器算法感知器算法实质上是一种赏罚过程对正确分类的模式则“赏”，实际上是“不罚”，即权向量不变。对错误分类的模式则“罚”，使w(k)加上一个正比于Xk的分量。当用全部模式样本训练过一轮以后，只要有一个模式是判别错误的，则需要进行下一轮迭代，即用全部模式样本再训练一次。如此不断反复直到全部模式样本进行训练都能得到正确的分类结果为止。3.2感知准则函数感知器算法的收敛性只要模式类别是线性可分的，就可以在有限的迭代步数里求出权向量。如果有一个样本线性不可分，那么感知器算法就会一直迭代，无法收敛。这是它的局限性。3.2感知准则函数感知器算法采用感知器算法的多类模式的分类讨论这个分类算法都是通过训练样本来确定判别函数的系数，并没有考虑到测试样本，但一个分类器的性能最终用未知的测试样本来检验。要使一个分类器设计完善，必须采用有代表性的正确的训练数据，它能够合理反映模式数据的整体。如果训练样本中有噪声样本，就会影响分类的性能。局限性在于对噪声数据敏感，解不够鲁棒。3.2感知准则函数采用感知器算法的多类模式的分类讨论要获得一个判别性能好的线性分类器，究竟需要多少训练样本？直观上是越多越好，但实际上能收集到的样本数目会受到客观条件的限制；过多的训练样本在训练阶段会使计算机需要较长的运算时间；一般来说，合适的样本数目可如下估计： 若k是模式的维数，令C=2(k+1)，则通常选用的训练样本数目约为C的10~20倍。3.2感知准则函数50三种梯度下降优化框架批量梯度下降法（BatchGradientDescent,BGD）每次使用全部的训练样本来更新模型参数/学习；优点：每次更新都会朝着正确的方向进行，最后能够保证收敛于极值点；缺点：每次学习时间过长，并且如果训练集很大以至于需要消耗大量的内存，不能进行在线模型参数更新。3.2感知准则函数51随机梯度下降法（StochasticGradientDescent,SGD）随机梯度下降算法每次从训练集中随机选择一个样本来进行学习；优点：每次只随机选择一个样本来更新模型参数，因此每次的学习是非常快速的，并且可以进行在线更新；SGD波动带来的好处，在类似盆地区域，即很多局部极小值点，那么这个波动的特点可能会使得优化的方向从当前的局部极小值点调到另一个更好的局限极小值点，这样便可能对于非凹函数，最终收敛于一个较好的局部极值点，甚至全局极值点。缺点：每次更新可能并不会按照正确的方向进行，因此会带来优化波动，使得迭代次数增多，即收敛速度变慢。3.2感知准则函数52小批量梯度下降法（Mini-batchGradientDescent,SGD）小批量梯度下降综合了batch梯度下降与stochastic梯度下降，在每次更新速度与更新次数中间一个平衡，其每次更新从训练集中随机选择k(k<m)个样本进行学习；优点：相对于随机梯度下降，Mini-batch梯度下降降低了收敛波动性，即降低了参数更新的方差，使得更新更加稳定；相对于批量梯度下降，其提高了每次学习的速度；MBGD不用担心内存瓶颈从而可以利用矩阵运算进行高效计算；3.2感知准则函数第三章线性和非线性判别分析3.1Fisher线性判别3.2感知准则函数3.3广义线性判别分析3.4k近邻3.5决策树54对于非线性问题，线性判别函数难以正确分类，而且设计非线性判别函数比较复杂。此时，常用的方法是将原特征空间映射到一个高维空间，将低维空间中的非线性问题转化为高维空间中的线性问题，从而降低模式分类的难度。3.3广义线性判别分析例：如右图，55对于非线性问题，线性判别函数难以正确分类，而且设计非线性判别函数比较复杂。此时，常用的方法是将原特征空间映射到一个高维空间，将低维空间中的非线性问题转化为高维空间中的线性问题，从而降低模式分类的难度。3.3广义线性判别分析例：如右图，二次判别函数可以表达为563.3广义线性判别分析广义线性判别函数这样一个非线性判别函数通过映射，变换成线性判别函数。原始的特征空间是非线性，但通过某种映射，在新的空间能保证是线性函数，原始空间的判别函数为广义线性判别函数。判别函数的一般形式：3.3广义线性判别分析第三章线性和非线性判别分析3.1Fisher线性判别3.2感知准则函数3.3广义线性判别分析3.4k近邻3.5决策树近邻法

近邻法则是一种根据样本提供的信息，绕开概率的估计而直接决策的技术，所以它也属于非参数判别方法的一种。（没有训练过程）模式识别的基本方法有两大类，一类是将特征空间划分成决策域，这就要确定判别函数和分界面方程（线性判别函数）。而另一种方法则称为模板匹配，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。近邻法

线性判别函数是将特征空间划分为决策域，并用判别函数或决策面方程表示决策域的方法。近邻法则在原理上属于模板匹配。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，就按最近似的模板的类别作为自己的类别。譬如A类有10个训练样本，因此有10个模板，B类有8个训练样本，就有8个模板。任何一个待测试样本在分类时与这18个模板都算一算相似度，如最相似的那个近邻是B类中的一个，就确定待测试样本为B类，否则为A类。因此原理上说近邻法是最简单的。近邻法

但是近邻法有一个明显的缺点:就是计算量大，存储量大，要存储的模板很多，每个测试样本要对每个模板计算一次相似度，因此在模板数量很大时，计算量也很大的。

思想简单，有一个如此明显缺点的方法还有没有存在的必要性呢？优点:在模板数量很大时其错误率指标还是相当不错的。该方法普适性比较好。常用来作为一个基准算法。

结论:这就是说近邻法有存在的必要。最近邻法则最近邻法:将与测试样本最近邻样本的类别作为决策的方法。对一个C类别问题，每类有Ni个样本，i＝1，…，C，则第i类ωi的判别函数

其中表示是ωi类的第k个样本。对于C类：决策规则为：如果则决策X∈ωj。

最近邻法则

最近邻法在原理上最直观，方法上也十分简单，只要对所有样本(共N＝∑Ni)进行N次距离运算，然后以最小距离者的类别作决策。

公式中用‖·‖表示距离，其实这是一个象征性的表示，可以采用任何一种相似性的度量，一般采用欧氏距离为相似性度量的较多。但由于特征向量各个分量之间对应的物理意义很可能不一致，因此究竟采用何种相似性度量要看问题而定。

近邻法则的错误率实际问题中，近邻法的错误率是比较难算的，因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。譬如图中:(A3)

红点表示A类训练样本，蓝点表示B类训练样本绿点O表示待测样本。假设以欧氏距离来衡量，O的最近邻是A3，其次是B1，因此O应该属于A类，但若A3被拿开，O就会被判为B类。这说明计算最近邻法的错误率会有偶然性，也就是指与具体的训练样本集有关。计算错误率的偶然性会因训练样本数量的增大而减小。随着训练样本的增加，准确率会有所提高。因此人们就利用训练样本数量增至极大，来对其性能进行评价。

近邻法则的错误率最近邻法则

最近邻规则是次优的方法，通常的错误率比最小可能错误率（即最小贝叶斯法则的错误率）要大。但在无限训练样本的情况下，这个错误率不会超过贝叶斯错误率的一倍。小于等于两倍，错误率有上限的。当训练样本足够多时：最近邻法的错误率要高于贝叶斯错误率，可以证明以下关系式成立：

最近邻法的渐近平均错误率的下、上界分别为贝叶斯错误率及

由于一般情况下

很小，因此上式又可粗略表示成

近邻法则的错误率

因此可以说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。从这点说最近邻法是优良的，因此它是模式识别重要方法之一。近邻法则的错误率

最近邻方法最近的样本可能受噪声影响。最近邻法可以扩展成找测试样本的k个最近样本作决策依据的方法。k近邻基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中第i个类别所占个数为gi(X),i＝1，…，c，决策规则：如果

则决策X∈ωj

。K-近邻法则k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。可以这样理解:K近邻算法从测试样本点开始生长，不断扩大区域，直到包含进k个训练样本点为止，并且把X归为这最近的k个训练样本点中出现频率最大的类别中。如图为k=5的情况。K-近邻法则

在N→∞的条件下，k-近邻法的错误率要低于最近邻法。从图中也可看出，无论是最近邻法，还是k-近邻法，其错误率的上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。不同k值时的错误率情况K-近邻法则的错误率：K-近邻法则最近邻法和K近邻法的共同优点是简单，而且结果比较好，但仍存在不少缺点：

(1)要求的计算机存储容量和计算量相当大。

(2)没有考虑到决策风险。

(3)以上的分析是建立在无穷多样本的基础上的，对于有限样本的情况，缺乏理论上的分析。K-近邻法则732.近邻法数据：1）USPS手写体2）UCI数据库中sonar数据源3）UCI数据库中Iris数据验证算法：不进行降维，1）K近邻方法分类；2）最近邻方法分类；对比算法：fisher+K近邻（最近邻）作业形式：程序+大报告+上机课演示第二次大作业第三章线性和非线性判别分析3.1Fisher线性判别3.2感知准则函数3.3广义线性判别分析3.4k近邻3.5决策树3.5.1决策树分类介绍3.5.2ID33.5.3C4.5决策树简介决策树：（适合离散属性的分类问题）一种多级分类器，它采用分级的形式，综合用多个决策规则，逐步把复杂的多类别分类问题转化为若干个简单的分类问题来解决n1n2n3n4n5t1t2t3t4t5t6t7多类

问题根节点：所有样本集合叶子节点：分完类的样本集合，每个集合属于同一类别二叉决策树二叉决策树：除叶节点外，决策树的每个节点ni都有且只有两个子节点nil和nir。二叉决策树把复杂的多类别分类问题转化为多级两类分类问题来解决。在每个节点ni，都把样本集分成两个子集。每个子集可能仍包含多类别的样本，继续分直至仅包含单类别样本的叶节点n1n2n3n4t1t2t5x2≤5x1≤2x3≤4x2≤2ω1ω2ω3ω2ω3t3t4多类

问题简介决策树方法的起源是概念学习系统，然后发展到ID3（处理离散属性）方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistant（处理缺失属性的数据，比如互联网数据）。是应用最广的归纳推理算法之一一种逼近离散值目标函数的方法对噪声数据有很好的健壮性且能学习析取表达式，之前的线性判别函数中的感知器函数对噪声特别敏感，决策树对噪声鲁棒性较好决策树举例决策树树的基础知识树的结构示意图决策树的表示法决策树通过把实例（样本）从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值（二叉决策树：是或否）例子类标示例天气温度湿度风力打网球1SunnyHotHighWeakNo2SunnyHotHighStrongNo3OvercastHotHighWeakYes4RainMildHighWeakYes5RainCoolNormalWeakYes6RainCoolNormalStrongNo7OvercastCoolNormalStrongYes8SunnyMildHighWeakNo9SunnyCoolNormalWeakYes10RainMildNormalWeakYes11SunnyMildNormalStrongYes12OvercastMildHighStrongYes13OvercastHotNormalWeakYes14RainMildHighStrongNo图离散属性：若干个确定的特征值14个训练样本，2分类问题，4个属性表达式决策树代表实例属性值约束的合取的析取式。属性之间的合取（且的关系），多种情况下的析取（或的关系）。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。（基于规则的分类）决策树学习的适用问题实例是由‘属性-值’对表示的:如实例是用一系列固定的属性（例如，Temperature）和它们的值（离散的值）（例如，Hot）来描述的目标函数具有离散的输出值:决策树给每个实例赋予一个布尔型的分类（例如，yes或no），如果是多分类，就是多个离散输出。决策树方法很容易扩展到学习有两个以上输出值的函数。一种更强有力的扩展算法允许学习具有实数值输出的函数，比如C4.5.可能需要析取的描述训练数据可以包含错误：决策树学习对错误有很好的鲁棒性，无论是训练样例所属的分类错误还是描述这些样例的属性值错误。单个样本存在错误，对整个决策树的构造影响并不明显。训练数据可以包含缺少属性值的实例:决策树学习甚至可以在有未知属性值的训练样例中使用（例如，仅有一部分训练样