线性判别分析非参数判别分类方法.pptx

《线性判别分析非参数判别分类方法.pptx》由会员分享，可在线阅读，更多相关《线性判别分析非参数判别分类方法.pptx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、线性判决u Fisher线性判决的基本思想是寻找一个最好的投影方向,当特征向量x从d维空间映射到这个方向上时,两类能最好地分开。u 这个方法实际上涉及特征维数的压缩问题。3.2线 性 分 类 器第1页/共59页分析w1方向之所以比w2方向优越,可以归纳出这样一个准则：即向量w的方向选择应能使两类样本投影的均值之差尽可能大些,而使类内样本的离散程度尽可能小。这就是Fisher准则函数的基本思路。第2页/共59页第一步：计算参量。(1)各类样本的均值向量i:(2)样本类内离散度矩阵Si：总类内离散度矩阵Sw:第二步：计算最优投影方向，并将样本往该方向上投影。第三步：决策。在投影空间内的决策准则为:

2、若yy0,则x 1,否则x 2。Fisher线性判决步骤第3页/共59页n采用类似于人认知错误、纠正错误、通过自学习改善自己认识事物本领的过程，随意确定判别函数初始值，该值在对样本分类训练过程中逐步修正直至最终确定。n 基本思想：寻找一个权向量，使规范化增广样本向量集的错分类样本数最少。感知准则函数 第4页/共59页一、基本概念1.1.线性可分性线性可分性 已知来自1和2两类的样本集x1,x2,xN,两类的线性判决函数为yi为增广样本向量,v为增广权向量。线性可分：如果存在一个线性分类器能把每个样本正确分类,即若存在一个权向量v,使得对于任何yi 1,都有vTyi0,而对于任何yi 2,都有v

3、Tyi0。规范化增广样本向量 经过这样的变换后,我们可以不考虑样本原来的类别标志,只要找到一个对全部样本zi都满足vTzi0(i=1,2,N)的权向量即可。样本的规范化第6页/共59页3.解向量和解区满足vTzi0(i=1,2,N)的权向量称为解向量。若把v看成是权向量空间中的一点,对于任一zi,vTzi=0在权向量空间确定了一个超平面,这个超平面把权空间分为两个半空间,该超平面的法向量为zi,超平面正侧的向量满足vTzi0。第7页/共59页 相应地,N个样本确定了N个超平面,每个超平面把权空间分为两个半空间。所以,满足vTzi0(i=1,2,N)的权向量必在这N个超平面正侧的交叠区,称这一交

4、叠区为解区,解区中的任意向量都是解向量v*。第8页/共59页二、感知准则函数感知准则函数方法利用错分类对现决策权向量进行修正直至收敛。这种方法只对线性可分情况适用，并且只适用于两类判决。感知准则函数方法的思路是：先随意找一个初始向量v，写作v(0)，然后用训练样本集中的每个样本来计算。一旦发现有的zi，使vTzi0,则引入余量后的解区在原解区之内。将上式写成矩阵形式即为 第12页/共59页定义误差向量:定义平方误差准则函数:Js(v)是一个非负函数,当 有解时,Js(v)达到最小值0,此时的矢量v*满足:v*能将所有样本正确分类。若v*不能使某个样本zj正确分类,即(v*)Tzjbj,则e2j

5、=(vTzjbj)2。错分样本的结果是使Js(v)增大,因此,Js(v)越小越好,其最小值0为理想分类结果,实现所有样本的正确分类。求使Js(v)最小的v*有两种方法:梯度下降法和解析法。第13页/共59页1.1.梯度下降法对Js(v)求梯度(3-(3-78)78)相应地,梯度下降算法为 其中，k为学习速率;初值v(0)(0)可任意选取。第14页/共59页2.解析法解析法得到的是伪逆解。令Js(v)=0得(3-79)其中(3-80)ZTZ为(d+1)(d+1)方阵,一般是满秩的,因此有唯一解:(3-81)是Z的左逆矩阵,Z的右逆矩阵定义为(3-82)b的典型值为 第15页/共59页3.3 分段

6、线性分类器 线性分类器的分界面是一个超平面。当类与类之间不能用任何一个超平面实现划分时,类间的分界面应是一个超曲面。曲线可以由多个线段近似表达,曲面可以由多个平面逼近,因此,可以用多个超平面近似表达超曲面,分段线性分类器正是基于这种思路而设计的一种分类器。第16页/共59页u线性判决函数只能解决线性可分问题。u在线性不可分的情况下，可以采用分段线性判别或二次函数判别等方法。u分段线性判决函数确定的决策面是由若干段超平面组成的。分段线性分类器的定义第17页/共59页 与线性判别函数相比，分段线性判别函数设计中首先要解决的问题是分段线性判别函数的分段段数问题。u分段段数过少，其分类效果必然要差；但

7、段数又要尽可能少，以免分类判别函数过于复杂，增加分类决策的计算量。u在有些实际的分类问题中，同一类样本可以用若干个子类来描述，这些子类的数目就可作为确定分段段数的依据。u在有些情况下样本分布及合适子类划分并不知道，往往需要采用一种聚类的方法，设法将样本划分成相对密集的子类，然后用各种方法设计各段判别函数。第18页/共59页把属于类i的样本区域Ri分为li个两两不相交的子区,对每个子类定义一个线性判决函数:定义类i的判别函数:判决准则为 若 ，则x j 称gi(x)(i=1,2,m)为分段线性判决函数,相应的分类器称为分段线性分类器。第19页/共59页当类由多个子类构成时,其决策面方程是由各子类

8、的判决函数确定的,若第i类的第n个子类和第j类的第k个子类相邻,则该段决策面方程为 其中,n 1,2,li,k 1,2,lj,li和lj分别表示第i类和第j类的子类数目。第20页/共59页分段线性距离分类器 正态分布条件下，两类别问题在各特征统计独立、同方差、且先验概率相等情况下，最小错误率决策可按最小距离决策，最小距离分类器的判决函数为即这时类间的决策面为 它是两类均值点连线的垂直平分面。第21页/共59页显然最小距离判别方法只有在各类别密集地分布在其均值附近时才有效。最小距离分类器两类物体在特征空间的分布n 对右图所示的情况按最小距离计算，就会将原来类的x决策成2类，如不对类进行子类划分，

9、或采用别的决策就不会取得好的效果。第22页/共59页u右图所示情况，若企图再用每类一个均值代表点产生最小距离分类器，就会产生很明显的错误率。u在这种情况下，可以将各类别划分成相对密集的子类，每个子类以它们的均值作为代表点，然后按最小距离分类，可以有比较满意的效果。u 对样本进行子类的合适划分是分段线性距离分类器性能好坏的一个关键问题。分段线性距离分类器示意图第23页/共59页归纳起来，如果对于i有li个子类，则有li个代表点，或者说将类i的样本区域Ri分为li个子区:其中,。用mli表示Rli中的均值向量,并以此作为该子区的代表点,确定判别函数:则判决准则为 若，则x j 称这种分类器为分段线

10、性距离分类器。第24页/共59页注意：线性距离分类器使用的是马氏距离,分段线性距离分类器使用的则是欧几里德距离,由最小距离分类器的导出过程可知,仅当所有子区的协方差阵相同且等于2I时,才具有较好的分类效果。第25页/共59页设计分段线性分类器的前提条件是有一组已知类别的样本集,其关键在于解决以下两个问题:(1)根据样本集确定子类数目及各子类的划分;(2)利用样本集计算各子类判别函数的权向量和阈值权。根据已知条件的不同,可以分别采取不同的方法。分段线性分类器设计的一般考虑(1)子类数目及各子类划分已知；(2)子类数目已知,各子类划分不知；(3)子类数目未知。第26页/共59页u最初的近邻法是由C

11、over和Hart于1968年提出的，是非参数法中最重要的方法之一。u最小距离分类器将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的均值或邻近均值的某一样本为代表点。实质就是将样本判属于与代表点距离最近的类。u该法的缺点是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。3.4 近邻分类器第27页/共59页最近邻法一、最近邻法的原理及判决准则u近邻法的基本思想：以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。u其主要特点就是将样本判属它的最近邻（和它距离最近的代表点）所在的类。第28页/共59页 假定有m

12、个类别1,2,m的模式识别问题,每类有Ni(i=1,2,m)个样本,规定类i的判别函数为其中,表示第i类的第k个元素。判决准则:若，则x j 第29页/共59页第30页/共59页二、错误率分析u最近邻法的错误概率比最小错误概率判决准则的错误概率要大，但是当样本数目无限时，它的错误概率不会超过后者的错误概率的一倍。u假设近邻分类器的渐近平均错误概率为P,最小错误概率判决准则的错误概率为P*e,那么它们之间存在如下关系:其中m为类别数,PN(e)是当样本数为N 时近邻分类器的平均错误概率。第31页/共59页图中曲线与直线分别是近邻法分类器当N时渐近平均错误概率的上、下界,具体的P落在图中阴影区内。

13、P的上、下界 第32页/共59页k近邻法一、k近邻法的原理及判决准则u最近邻分类器的判决思想是将样本判属与它距离最小的样本所属的类。u这种方法的特点是概念容易理解，最近邻样本和待分类样本在距离意义下是最相似的。u其缺点在于受随机噪声影响较大，尤其是在两类的交叠区内。第33页/共59页u例如下图有两类样本点。图中有两个待识别样本，其中点1落在第一类较密集的区域内，它属于第一类的可能性较大，但点1的最近邻为第二类的样本，而该样本对于第二类的区域而言属于因较大的随机误差引起的样本；点2落在第二类较密集的区域内，属于第二类的可能性较大，但点2的最近邻为第一类的样本，而该样本对于第一类的区域而言属于因较

14、大的随机误差引起的样本。随机噪声对最近邻分类结果的影响第34页/共59页对于待分类样本x,在N个样本集中找出它的k个近邻,设k个样本中属于第i类的为ki个(i=1,2,m),即定义判别函数:判决准则为 若，则 x j称这种方法为k近邻法,相应的分类器称为k近邻分类器。第35页/共59页8近邻示意图 对于下图中的样本点,若按8近邻方法判决,则点1的8近邻中,k1=6,k2=2,所以应判属第一类；点2的8近邻中,k1=2,k2=6,所以应判属第二类。第36页/共59页二、错误率分析二、错误率分析 k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。k近邻分类器的渐近平均错误概率也

15、满足:其中,P*e为最小错误概率的贝叶斯分类器的错误概率。第37页/共59页近邻法优点：在模板数量很大时其错误率指标还是相当不错的。缺点：需要存储全部训练样本，另外有繁重的距离计算量，即计算量大，存储量大。剪辑近邻法与压缩近邻法就是两种有代表性的改进方法。近邻法的改进方法第38页/共59页剪辑近邻法，其基本原理是在原有样本集中挑选出对分类计算有效的样本，将不同类别交界处的样本以适当方式进行筛选，把处于交界处的训练样本给剪辑掉，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。压缩近邻法，其基本原理是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范

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

17、59页 用近邻法容易出错的区域是在两类的交界处，这时某个训练样本存在与否就会影响到某些测试分类的结果。因此剪辑的效果往往把这些处于交界的训练样本给剪辑掉了。第41页/共59页二、压缩近邻法剪辑近邻法所得到的剪辑样本集在样本数量的压缩方面并不十分明显，它的作用在于将原样本集中处于边界处的样本删除掉，但靠近两类中心的大部分样本仍被保留下来。然而按近邻规则来看，这些样本中的大多数对分类决策没什么用处，如能在剪辑的基础上再去掉一部分这样的样本，将有助于进一步缩短计算时间与压缩存储量。其实处于同一类样本密集区的测试样本并不一定要全部保留，几乎绝大部分都可去掉，只要保留若干个训练样本即可。问题是保留哪些好

18、。压缩近邻法采用了用测试集测试的办法，采用只要分类有错，在出错处添加一个训练样本的做法。第42页/共59页压缩近邻法压缩样本的思想很简单，它利用现有样本集，逐渐生成一个新的样本集。使该样本集在保留最少量样本的条件下,仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类,并保持正常识别率。该算法的作法也十分简单，它定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。第43页/共59页 1.初始化Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。2

19、.样本集生成在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若分类正确，则将该样本放回Grabbag中，对Grabbag中所有样本重复上述过程。3.结束过程若Grabbag中所有样本在执行第二步时没有发生转入Store的现象，或Grabbag已成空集，则算法终止，否则转入第二步。在算法终止后，Store中的样本集作为压缩样本集，可用来对待识别样本按最近邻法分类。压缩近邻法算法步骤：第44页/共59页本章小结 u参数判别分类方法与非参数判别分类方法u线性判别函数和决策面方程uFisher线性判决准则u感知准则函数u

20、最小平方误差准则函数u分段线性分类器u近邻分类器第45页/共59页参数判别分类方法与非参数判别分类方法参数判别方法：适用条件：前提是清楚特征空间中的各类样本的分布，一旦待分类样本的特征向量值x已知，就可以确定x对各类的后验概率，也就可按相应的准则计算与分类。参数分类判别方法一般只能用在有统计知识的场合，或能利用训练样本估计出参数的场合。判别函数类型如何确定？判别函数及决策面方程的类别确定是由样本分布规律决定的，例如，符合某种条件就可使用线性分类器，正态分布条件下一般适合用二次函数决策面。第46页/共59页参数判别分类方法与非参数判别分类方法非参数分类判别方法：直接利用训练样本集，省去参数估计这

21、一环节，根据一些准则(如Fisher准则、感知准则函数)来设计分类器。判别函数类型如何确定？在非参数判别方法的设计中，使用什么典型的分类决策方法预先由设计者确定，然后利用训练样本集提供的信息确定这些函数中的参数。这是参数与非参数判别方法的一个重要不同点。第47页/共59页非参数分类判别方法的基本做法：使用非参数分类判别方法进行分类器设计主要包含两个步骤：选择函数类型与确定参数。确定使用的判别函数类型或决策面方程类型，如线性分类器、非线性分类器、分段线性分类器或近邻法等。在选定的函数类型条件下，确定相应的参数，从而完成整个分类器设计。第48页/共59页其中wi是权向量,wi0是一个常数，称为阈值

22、权。设样本在d维特征空间中描述，两类问题线性判别函数的一般形式可表示成判决准则的可以表示为 线性判别函数和决策面方程第49页/共59页在线性判别函数条件下，它是d维空间的一个超平面。相应的决策面方程为其中,第50页/共59页n基本思想：寻找一个最好的投影方向，当特征向量从d 维空间映射到这个方向时，两类能最好地分开。nFisher准则函数的基本思路：向量w的方向选择应能使两类样本在该向量上投影的交迭部分最少,投影的均值之差尽可能大些，而使类内样本的离散程度尽可能小。Fisher线性判决准则 第51页/共59页第一步：计算参量。(1)各类样本的均值向量i:(2)样本类内离散度矩阵Si总类内离散度

23、矩阵Sw:第二步：计算最优投影方向，并 将样本往该方向上投影。第三步：决策。在投影空间内的决策准则为:若yy0,则x 1,否则x 2。步骤第52页/共59页感知准则函数n这种方法只对线性可分情况适用。适用于两类判决。n基本思想：寻找一个增广权向量v，使规范化增广样本向量集的错分类样本数最少。第53页/共59页感知准则函数方法的思路是：先随意找一个初始向量v，写作v(0)，然后用训练样本集中的每个样本来计算。一旦发现有的zi，使vTzi0，则说明当前的广义权向量v(0)不适合还需要进一步修正。感知准则函数n基本思想：寻找一个增广权向量v，使规范化增广样本向量集的错分类样本数最少。n这种方法只对线

24、性可分情况适用，并且适用于两类判决。第54页/共59页 设Z=z1,z2,zN是经过规范化的一组样本集,定义感知准则函数:其中,Zk是被权向量v错分类的样本集合,当z Zk时,有 显然,Jp(v)0。梯度下降算法求Jp(v)准则函数的极小值。迭代公式为 其中即Zk为第k步被错分的样本集。k为正，是步长系数。第55页/共59页最小平方误差准则函数 Js(v)越小越好,其最小值0为理想分类结果,实现所有样本的正确分类。n平方误差准则函数Js(v)为第56页/共59页分段线性距离分类器 正态分布条件下，两类别问题在各特征统计独立、同方差、且先验概率相等情况下，最小错误率决策可按最小距离决策，最小距离分类器的判决函数为即这时类间的决策面为 它是两类均值点连线的垂直平分面。第57页/共59页近邻法 基本特点：将样本集中的任何一个样本都作为代表点。实质：将样本判属于与代表点距离最近的类。第58页/共59页感谢您的观看！第59页/共59页