线性判别分析非参数判别分类方法第四次课详解演示文稿

线性判别分析非参数判别分类方法第四次课详解演示文稿当前第1页\共有58页\编于星期四\6点（优选）线性判别分析非参数判别分类方法第四次课当前第2页\共有58页\编于星期四\6点3.2.2Fisher线性判决Fisher线性判决的基本思想是寻找一个最好的投影方向,当特征向量x从d维空间映射到这个方向上时,两类能最好地分开。这个方法实际上涉及特征维数的压缩问题。3.2线性分类器当前第3页\共有58页\编于星期四\6点分析w1方向之所以比w2方向优越,可以归纳出这样一个准则：即向量w的方向选择应能使两类样本投影的均值之差尽可能大些,而使类内样本的离散程度尽可能小。这就是Fisher准则函数的基本思路。当前第4页\共有58页\编于星期四\6点第一步：计算参量。(1)各类样本的均值向量μi:(2)样本类内离散度矩阵Si：总类内离散度矩阵Sw:第二步：计算最优投影方向，并将样本往该方向上投影。第三步：决策。在投影空间内的决策准则为:若y>y0,则x∈ω1,否则x∈ω2。Fisher线性判决步骤当前第5页\共有58页\编于星期四\6点采用类似于人认知错误、纠正错误、通过自学习改善自己认识事物本领的过程，随意确定判别函数初始值，该值在对样本分类训练过程中逐步修正直至最终确定。基本思想：寻找一个权向量，使规范化增广样本向量集的错分类样本数最少。

3.2.3感知准则函数

当前第6页\共有58页\编于星期四\6点一、基本概念1.线性可分性已知来自ω1和ω2两类的样本集{x1,x2,…,xN},两类的线性判决函数为yi为增广样本向量,v为增广权向量。线性可分：如果存在一个线性分类器能把每个样本正确分类,即若存在一个权向量v,使得对于任何yi∈ω1,都有vTyi>0,而对于任何yi∈ω2,都有vTyi<0,则称这组样本集线性可分;否则称为线性不可分。反过来,若样本集是线性可分的,则必然存在一个权向量v,能将每个样本正确地分类。

当前第7页\共有58页\编于星期四\6点

2.样本的规范化如果样本集{y1,y2,…,yN}线性可分,则一定存在某个或某些权向量v,使如果令，则vTzi>0。规范化增广样本向量经过这样的变换后,我们可以不考虑样本原来的类别标志,只要找到一个对全部样本zi都满足vTzi>0(i=1,2,…,N)的权向量即可。样本的规范化当前第8页\共有58页\编于星期四\6点

3.解向量和解区

满足vTzi>0(i=1,2,…,N)的权向量称为解向量。若把v看成是权向量空间中的一点,对于任一zi,vTzi=0在权向量空间确定了一个超平面,这个超平面把权空间分为两个半空间,该超平面的法向量为zi,超平面正侧的向量满足vTzi>0。当前第9页\共有58页\编于星期四\6点相应地,N个样本确定了N个超平面,每个超平面把权空间分为两个半空间。所以,满足vTzi>0(i=1,2,…,N)的权向量必在这N个超平面正侧的交叠区,称这一交叠区为解区,解区中的任意向量都是解向量v*。当前第10页\共有58页\编于星期四\6点二、感知准则函数感知准则函数方法利用错分类对现决策权向量进行修正直至收敛。这种方法只对线性可分情况适用，并且只适用于两类判决。感知准则函数方法的思路是：先随意找一个初始向量v，写作v(0)，然后用训练样本集中的每个样本来计算。一旦发现有的zi，使vTzi<0，则说明当前的广义权向量v(0)不适合还需要进一步修正。

当前第11页\共有58页\编于星期四\6点设Z={z1,z2,…,zN}是经过规范化的一组样本集,定义感知准则函数:其中,Zk是被权向量v错分类的样本集合,当z∈Zk时,有显然,Jp(v)≥0。梯度下降算法求Jp(v)准则函数的极小值。迭代公式为其中即Zk为第k步被错分的样本集。ρk为正，是步长系数。当前第12页\共有58页\编于星期四\6点两点说明：感知准则函数方法只是对线性可分样本集有效，而对线性不可分的样本集，该算法不能收敛。这一节对感知准则函数的讨论，只是很初步的。但这种利用错误提供的信息，进行自修正的思想意义是十分深远的。这种只解决线性分类的感知器称为单层感知器，在此基础上发展起来的多层感知器在原理上能解决非线性分类、多类划分，以及非线性拟和非线性映射等多种问题。当前第13页\共有58页\编于星期四\6点3.2.4最小平方误差准则函数

设由X={x1,x2,…,xN}得到的规范化增广向量集合为{z1,z2,…,zN},分类器设计的任务就在于寻找一个矢量v,满足:引入余量bi,用超平面:代替zTiv>0,则引入余量后的解区在原解区之内。将上式写成矩阵形式即为当前第14页\共有58页\编于星期四\6点定义误差向量:定义平方误差准则函数:Js(v)是一个非负函数,当有解时,Js(v)达到最小值0,此时的矢量v*满足:v*能将所有样本正确分类。若v*不能使某个样本zj正确分类,即(v*)Tzj≠bj,则e2j=(vTzj－bj)2。错分样本的结果是使Js(v)增大,因此,Js(v)越小越好,其最小值0为理想分类结果,实现所有样本的正确分类。

求使Js(v)最小的v*有两种方法:梯度下降法和解析法。当前第15页\共有58页\编于星期四\6点

1.梯度下降法对Js(v)求梯度(3-78)相应地,梯度下降算法为其中，ρk为学习速率;初值v(0)可任意选取。当前第16页\共有58页\编于星期四\6点

2.解析法解析法得到的是伪逆解。令Js(v)=0得(3-79)其中(3-80)ZTZ为(d+1)×(d+1)方阵,一般是满秩的,因此有唯一解:(3-81)是Z的左逆矩阵,Z的右逆矩阵定义为(3-82)b的典型值为当前第17页\共有58页\编于星期四\6点3.3分段线性分类器

线性分类器的分界面是一个超平面。当类与类之间不能用任何一个超平面实现划分时,类间的分界面应是一个超曲面。曲线可以由多个线段近似表达,曲面可以由多个平面逼近,因此,可以用多个超平面近似表达超曲面,分段线性分类器正是基于这种思路而设计的一种分类器。当前第18页\共有58页\编于星期四\6点线性判决函数只能解决线性可分问题。在线性不可分的情况下，可以采用分段线性判别或二次函数判别等方法。分段线性判决函数确定的决策面是由若干段超平面组成的。

3.3.1分段线性分类器的定义当前第19页\共有58页\编于星期四\6点与线性判别函数相比，分段线性判别函数设计中首先要解决的问题是分段线性判别函数的分段段数问题。分段段数过少，其分类效果必然要差；但段数又要尽可能少，以免分类判别函数过于复杂，增加分类决策的计算量。在有些实际的分类问题中，同一类样本可以用若干个子类来描述，这些子类的数目就可作为确定分段段数的依据。在有些情况下样本分布及合适子类划分并不知道，往往需要采用一种聚类的方法，设法将样本划分成相对密集的子类，然后用各种方法设计各段判别函数。当前第20页\共有58页\编于星期四\6点把属于类ωi的样本区域Ri分为li个两两不相交的子区,对每个子类定义一个线性判决函数:定义类ωi的判别函数:判决准则为若，则x∈ωj

称gi(x)(i=1,2,…,m)为分段线性判决函数,相应的分类器称为分段线性分类器。当前第21页\共有58页\编于星期四\6点当类由多个子类构成时,其决策面方程是由各子类的判决函数确定的,若第i类的第n个子类和第j类的第k个子类相邻,则该段决策面方程为其中,n∈{1,2,…,li},k∈{1,2,…,lj},li和lj分别表示第i类和第j类的子类数目。当前第22页\共有58页\编于星期四\6点3.3.2分段线性距离分类器正态分布条件下，两类别问题在各特征统计独立、同方差、且先验概率相等情况下，最小错误率决策可按最小距离决策，最小距离分类器的判决函数为

即这时类间的决策面为

它是两类均值点连线的垂直平分面。<><>当前第23页\共有58页\编于星期四\6点显然最小距离判别方法只有在各类别密集地分布在其均值附近时才有效。最小距离分类器两类物体在特征空间的分布对右图所示的情况按最小距离计算，就会将原来ω１类的x决策成ω2类，如不对ω１类进行子类划分，或采用别的决策就不会取得好的效果。当前第24页\共有58页\编于星期四\6点右图所示情况，若企图再用每类一个均值代表点产生最小距离分类器，就会产生很明显的错误率。在这种情况下，可以将各类别划分成相对密集的子类，每个子类以它们的均值作为代表点，然后按最小距离分类，可以有比较满意的效果。对样本进行子类的合适划分是分段线性距离分类器性能好坏的一个关键问题。分段线性距离分类器示意图当前第25页\共有58页\编于星期四\6点归纳起来，如果对于ωi有li个子类，则有li个代表点，或者说将类ωi的样本区域Ri分为li个子区:其中,。用mli表示Rli中的均值向量,并以此作为该子区的代表点,确定判别函数:则判决准则为若，则x∈ωj

称这种分类器为分段线性距离分类器。当前第26页\共有58页\编于星期四\6点

注意：

线性距离分类器使用的是马氏距离,分段线性距离分类器使用的则是欧几里德距离,由最小距离分类器的导出过程可知,仅当所有子区的协方差阵相同且等于σ2I时,才具有较好的分类效果。当前第27页\共有58页\编于星期四\6点设计分段线性分类器的前提条件是有一组已知类别的样本集,其关键在于解决以下两个问题:(1)根据样本集确定子类数目及各子类的划分;(2)利用样本集计算各子类判别函数的权向量和阈值权。根据已知条件的不同,可以分别采取不同的方法。3.3.3分段线性分类器设计的一般考虑

(1)子类数目及各子类划分已知；(2)子类数目已知,各子类划分不知；(3)子类数目未知。当前第28页\共有58页\编于星期四\6点最初的近邻法是由Cover和Hart于1968年提出的，是非参数法中最重要的方法之一。最小距离分类器将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的均值或邻近均值的某一样本为代表点。实质就是将样本判属于与代表点距离最近的类。该法的缺点是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。3.4近邻分类器当前第29页\共有58页\编于星期四\6点3.5.1最近邻法一、最近邻法的原理及判决准则

近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。其主要特点就是将样本判属它的最近邻（和它距离最近的代表点）所在的类。当前第30页\共有58页\编于星期四\6点假定有m个类别ω1,ω2,…,ωm的模式识别问题,每类有Ni(i=1,2,…,m)个样本,规定类ωi的判别函数为其中,表示第i类的第k个元素。判决准则:

若，则x∈ωj

当前第31页\共有58页\编于星期四\6点当前第32页\共有58页\编于星期四\6点二、错误率分析最近邻法的错误概率比最小错误概率判决准则的错误概率要大，但是当样本数目无限时，它的错误概率不会超过后者的错误概率的一倍。假设近邻分类器的渐近平均错误概率为P∞,最小错误概率判决准则的错误概率为P*e,那么它们之间存在如下关系:其中m为类别数,PN(e)是当样本数为N时近邻分类器的平均错误概率。当前第33页\共有58页\编于星期四\6点图中曲线与直线分别是近邻法分类器当N→∞时渐近平均错误概率的上、下界,具体的P∞落在图中阴影区内。P∞的上、下界当前第34页\共有58页\编于星期四\6点3.5.2k近邻法一、k近邻法的原理及判决准则最近邻分类器的判决思想是将样本判属与它距离最小的样本所属的类。这种方法的特点是概念容易理解，最近邻样本和待分类样本在距离意义下是最相似的。其缺点在于受随机噪声影响较大，尤其是在两类的交叠区内。当前第35页\共有58页\编于星期四\6点例如下图有两类样本点。图中有两个待识别样本，其中点1落在第一类较密集的区域内，它属于第一类的可能性较大，但点1的最近邻为第二类的样本，而该样本对于第二类的区域而言属于因较大的随机误差引起的样本；点2落在第二类较密集的区域内，属于第二类的可能性较大，但点2的最近邻为第一类的样本，而该样本对于第一类的区域而言属于因较大的随机误差引起的样本。随机噪声对最近邻分类结果的影响当前第36页\共有58页\编于星期四\6点对于待分类样本x,在N个样本集中找出它的k个近邻,设k个样本中属于第i类的为ki个(i=1,2,…,m),即定义判别函数:

判决准则为若，则x∈ωj称这种方法为k近邻法,相应的分类器称为k近邻分类器。

当前第37页\共有58页\编于星期四\6点8近邻示意图对于下图中的样本点,若按8近邻方法判决,则点1的8近邻中,k1=6,k2=2,所以应判属第一类；点2的8近邻中,k1=2,k2=6,所以应判属第二类。当前第38页\共有58页\编于星期四\6点二、错误率分析

k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。k近邻分类器的渐近平均错误概率也满足:其中,P*e为最小错误概率的贝叶斯分类器的错误概率。当前第39页\共有58页\编于星期四\6点近邻法优点：在模板数量很大时其错误率指标还是相当不错的。缺点：需要存储全部训练样本，另外有繁重的距离计算量，即计算量大，存储量大。剪辑近邻法与压缩近邻法就是两种有代表性的改进方法。

3.5.3近邻法的改进方法当前第40页\共有58页\编于星期四\6点剪辑近邻法，其基本原理是在原有样本集中挑选出对分类计算有效的样本，将不同类别交界处的样本以适当方式进行筛选，把处于交界处的训练样本给剪辑掉，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。压缩近邻法，其基本原理是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。当前第41页\共有58页\编于星期四\6点一、剪辑近邻法

剪辑近邻法着眼于如何减少模板样本数目，从而可同时减少分类时的计算量及模板样本的存储量，同时还能进一步改进分类器的性能，如降低错误率等要求。剪辑近邻法的基本思想是从这样一个现象出发的，即当不同类别的样本在分布上有交迭部分，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。

当前第42页\共有58页\编于星期四\6点用近邻法容易出错的区域是在两类的交界处，这时某个训练样本存在与否就会影响到某些测试分类的结果。因此剪辑的效果往往把这些处于交界的训练样本给剪辑掉了。当前第43页\共有58页\编于星期四\6点二、压缩近邻法

剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十分明显，它的作用在于将原样本集中处于边界处的样本删除掉，但靠近两类中心的大部分样本仍被保留下来。然而按近邻规则来看，这些样本中的大多数对分类决策没什么用处，如能在剪辑的基础上再去掉一部分这样的样本，将有助于进一步缩短计算时间与压缩存储量。其实处于同一类样本密集区的测试样本并不一定要全部保留，几乎绝大部分都可去掉，只要保留若干个训练样本即可。问题是保留哪些好。压缩近邻法采用了用测试集测试的办法，采用只要分类有错，在出错处添加一个训练样本的做法。当前第44页\共有58页\编于星期四\6点压缩近邻法压缩样本的思想很简单，它利用现有样本集，逐渐生成一个新的样本集。使该样本集在保留最少量样本的条件下,仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类,并保持正常识别率。该算法的作法也十分简单，它定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。当前第45页\共有58页\编于星期四\6点1.［初始化］Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。2.［样本集生成］在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中，对Grabbag中所有样本重复上述过程。3.［结束过程］若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。在算法终止后，Store中的样本集作为压缩样本集，可用来对待识别样本按最近邻法分类。压缩近邻法算法步骤：当前第46页\共有58页\编于星期四\6点本章小结参数判别分类方法与非参数判别分类方法线性判别函数和决策面方程Fisher线性判决准则感知准则函数最小平方误差准则函数分段线性分类器近邻分类器当前第47页\共有58页\编于星期四\6点参数判别分类方法与非参数判别分类方法参数判别方法：适用条件：前提是清楚特征空间中的各类样本的分布，一旦待分类样本的特征向量值x已知，就可以确定x对各类的后验概率，也就可按相应的准则计算与分类。参数分类判别方法一般只能用在有统计知识的场合，或能利用训练样本估计出参数的场合。

判别函数类型如何确定？判别函数及决策面方程的类别确定是由样本分布规律决定的，例如，符合某种条件就可使用线性分类器，正态分布条件下一般适合用二次函数决策面。当前第48页\共有58页\编于星期四\6点参数判别分类方法与非参数判别分类方法非参数分类判别方法：直接利用训练样本集，省去参数估计这一环节，根据一些准则(如Fisher准则、感知准则函数)来设计分类器。

判别函数类型如何确定？在非参数判别方法的设计中，使用什么典型的分类决策方法预先由设计者确定，然后利用训练样本集提供的信息确定这些函数中的参数。这是参数与非参数判别方法的一个重要不同点。当前第49页\共有58页\编于星期四\6点非参数分类判别方法的基本做法：

使用非参数分类判别方法进行分类器设计主要包含两个步骤：选择函数类型与确定参数。确定使用的判别函数类型或决策面方程类型，如线性分类器、非线性分类器、分段线性分类器或近邻法等。在选定的函数类型条件下，确定相应的参数，从而完成整个分类器设计。当前第50页\共有58页\编于星期四\6点其中wi是权向量,wi0是一个常数，称为阈值权。设样本在d维特征空间中描述，两类问题线性判别函数的一般形式可表示成判决准则的可以表示为

线性判别函数和决策面方程当前第51页\共有58页\编于星期四\6点在线性判别函数条件下，它是d维空间