机器学习非参数方法要点技能课件

《机器学习非参数方法要点技能课件》由会员分享，可在线阅读，更多相关《机器学习非参数方法要点技能课件（72页珍藏版）》请在金锄头文库上搜索。

1、非参数方法,单击此处添加标题,前面的章节中，我们介绍了参数和半参数方法，这两种方法在实际训练前都需要对数据遵从的模型进行一个假定，这个假定可以是一个已知的概率分布或混合分布。参数方法的优点是把估计概率密度、判别式或回归函数问题归结为估计少量参数值，缺点则是模型假定并非总成立，当不成立时就会出现很大的误差。 这时我们就需要使用非参数方法，其中我们只需要假定一个事实：即相似的输入具有相似的输出。因为我们一般都认为世界的变化时平稳、量变到质变的，因此无论是密度、判别式还是回归函数都应当缓慢地变化。在这样的非参数估计（nonparamitric estimation）中，局部实例对于密度的影响就显得颇

2、为重要，而较远的实例影响则较小。 本节要点如下： k-近邻估计 Pazen 窗,K近邻,最简单的分段线性分类器：把各类划分为若干子类，以子类中心作为类别代表点，考查新样本到各代表点的距离并将它分到最近的代表点所代表的类。 极端情况，将所有样本都作为代表点 近邻法,问题描述:,特征向量 类别 X=(0.1,0.1) ?,最小距离分类器：将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。 最近邻法的基本思想：以全部训练样本作为

3、“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。 近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。,在二维情况下，最近邻规则算法使得二维空间被分割成了许多Voronoi网格，每一个网格代表的类别就是它所包含的训练样本点所属的类别。,最近邻法的错误率是比较难计算的，这是因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。,红点表示A类训练样本，蓝点表示B类训练样本，而绿点O表示待测样本。 假设以欧氏距离来衡量，O的最近邻是A3，其次是B1，因此O应该属于A类；

4、 但若A3被拿开，O就会被判为B类。,这说明计算最近邻法的错误率会有偶然性，也就是指与具体的训练样本集有关。 同时还可看到，计算错误率的偶然性会因训练样本数量的增大而减小。 因此我们就利用训练样本数量增至极大，来对其性能进行评价。这要使用渐近概念，以下都是在渐近概念下来分析错误率的。,当最近邻法所使用的训练样本数量N不是很大时，其错误率是带有偶然性的。,下图所示为一个在一维特征空间的两类别情况：,X表示一待测试样本，而X是所用训练样本集中X的最邻近者，则错误是由X与X分属不同的类别所引起的。,由于X与所用训练样本集有关，因此错误率有较大偶然性。 但是如果所用训练样本集的样本数量N极大，即N时，

5、可以想像X将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X的极限条件)分属不同类别的问题。 如果样本X的两类别后验概率分别为P(1|X)与P(2|X)，那么对X值，在N条件下，发生错误决策的概率为：,而在这条件下的平均错误率 P称为渐近平均错误率，是PN(e)在N的极限。 为了与基于最小错误率的贝叶斯决策方法对比，下面写出贝 叶斯错误率的计算式： 其中,若是两类问题，则 贝叶斯错误率： 最近邻法错误率： 可见在一般情况下P是大于零的值，只要P(1|X)P(2|X)0。,有以下两种例外情况P0： P(1|X)1 P(1|X)P(2|X)1/2。

6、,请想一下，什么情况下P(1|X)1或P(2|X)=1? P(1|X)= P(2|X)会出现什么什么情况？,一般来说，在某一类样本分布密集区，某一类的后验概率接近或等于1。此时，基于最小错误率贝叶斯决策基本没错，而近邻法出错可能也很小。 而后验概率近似相等一般出现在两类分布的交界处，此时分类没有依据，因此基于最小错误率的贝叶斯决策也无能为力了，近邻法也就与贝叶斯决策平起平坐了。,从以上讨论可以看出，当N时，最近邻法的渐近平均错误率的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况。,最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立：,由于一般情况下

7、P*很小，因此又可粗略表示成：,可粗略说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。,小结,模式识别（机器自动分类）的基本方法有两大类： 一类是将特征空间划分成决策域，这就要确定判别函数或确定分界面方程。 另一种方法则称为模板匹配，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。,前面讨论的方法可以说都是将特征空间划分为决策域，并用判别函数或决策面方程表示决策域的方法。,近邻法则在原理上属于模板匹配。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，就按最近似的模板的类别作为自己的类别。,6,k-近邻法

8、: 最近邻法的扩展，其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数表示成ki, i1，c。 定义判别函数为： gi(x)=ki, i=1, 2,c。,决策规则为：,k-近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。,从样本点x开始生长，不断扩大区域，直到包含进k个训练样本点为止，并且把测试样本点x的类别归为这最近的k个训练样本点中出现频率最大的类别。,对于两类问题， 有以下两种例外情况P0： PN(e|x,x)P(1|x) P(2|x) + P(2|x) P(1|x) 当N-时， P(i|x) 近似等于P(i|x) PN- (e|x,x)P

9、(1|x) P(2|x) + P(2|x) P(1|x) 对于K近邻法,对所有的x，有： PN- (e|x) CkP*(e|x) 根据Jensen不等式, P=EPNk(e|x) ECkP*(e|x) CkE P*(e|x) = Ck( P*) 不等式关系 P* P Ck( P*) Ck-1( P*) C1( P*) 2 P* (1- P* ),最近邻法和k-近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。 在k 的条件下，k-近邻法的错误率要低于最近邻法。 在k 的条件下，k-近邻法的错误率等于贝叶斯误差率。,6.3 改进的近邻法,尽管近邻法有其优良品质，但是它的一个严重弱

10、点与问题是需要存储全部训练样本，以及繁重的距离计算量。,但以简单的方式降低样本数量，只能使其性能降低，这也是不希望的。 为此要研究既能减少近邻法计算量与存储量，同时又不明显降低其性能的一些改进算法。,改进的方法大致分为两种原理。一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。,另一种原理则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。,快速搜索近邻法,这种方法着眼于只解决减少计算量，但没有达到减少存储量的要求。,基本思想： 将样本集按邻近关系

11、分解成组，给出每组的质心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组。 因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。,（1）样本集的分级分解 首先将整个样本分成l个子集，每个子集又分为它的l个子集，如此进行若干次就能建立起一个样本集的树形结构。分成子集的原则是该子集内的样本尽可能聚成堆，这可用聚类方法实现。 结点参数： 树形结构，每个结点表示一样本子集，描述该子集的参数是：,用树结构表示样本分级: p: 树中的一个结点，对应一个样本子集Kp Np : Kp中的样本数 Mp : Kp中的样本均值 rp

12、: 从Kp中任一样本到Mp的最大距离,（2）快速搜索算法 要实现快速搜索近邻，需要有方法快速判断某个样本子集是否是该待识样本的可能近邻样本集，从而可将无关的样本子集尽快排除。另一方面在某样本子集内寻找哪个样本是近邻时，需快速排除不可能为近邻的样本。 这两个快速判别算法可用以下两个规则表示。,规则1： 如果存在 则 不可能是X的近邻。其中B是待识别样本在搜索近邻过程中的当前近邻距离，B在搜索过程中不断改变与缩小。算法开始可将B设为无穷大。 表示待识样本X到结点 的均值点距离。,规则2：如果 其中Xi ，则Xi不可能是X的近邻。 由此可见，只要将每个样本子集 中的每个样本Xi到其均值Mp的距离D(

13、Xi,Mp)存入存储器中，就可利用上式将许多不可能成为测试样本近邻的训练样本排除。,（3）搜索算法 搜索算法的大体过程是这样的： 当搜索树形样本集结构由高层次向低层次深入时，对同一层次的所有结点，可以利用规则1排除掉一些不可能包含待识别样本的近邻的结点(样本子集)。但是这往往不能做到只留下唯一的待搜索结点，因此必须选择其中某一结点先深入搜索，以类似于深度优先的方法确定搜索路径直至叶结点。然而在该叶结点中找到的近邻并不能保证确实是全样本集中的最近邻者，所找到的该近邻样本需要在那些有可能包含最近邻的样本子集中核对与修正，直至找到真正的最近邻样本为止。,置B=，L=0，p=0 将当前结点的所有直接后

14、继结点放入一个目录表中，并对这些结点计算D(x,Mp) 根据规则1从目录表中去掉step2中的某些结点 如果目录表已无结点则置L=L-1，如果L=0则停止，否则转Step3。如果目录表有一个以上的结点，则转step5 在目录表中选出最近结点p为当前执行结点。如果当前的水平L是最终水平，则转Step6，否则置L=L+1，转Step2 对当前执行结点p中的每个xi，根据规则2决定是否计算D(x, xi)。若D(x, xi)B，则置NN=i和B= D(x, xi)，处理完当前执行结点中的每个xi后转Step3 当算法结束时，输出x的最近邻xNN和x与xNN的距离B,剪辑近邻法,目的：去掉靠近两类中心

15、的样本？ 基本思想：当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本。当我们得到一个作为识别用的参考样本集时，由于不同类别交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。,剪辑的过程是：将样本集KN分成两个互相独立的子集：考试（test）集KT和参考（reference）集KR。首先对KT中每一个Xi在参考集KR中找到其最近邻的样本Yi(Xi) 。如果Yi与Xi不属于同一类别，则将Xi从考试集KT中删除，最后得到一个剪辑的样

16、本集KTE（剪辑样本集），以取代原样本集，对待识别样本进行分类。 剪辑的结果是去掉两类边界附近的样本。,压缩近邻法：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。,定义两个存储器，一个用来存放即将生成的样本集，称为Store；另一存储器则存放原样本集，称为Grabbag。其算法是： 初始化。Store是空集，原样本集存入Grabbag；从Grabbag中任意选择一样本放入Store中作为新样本集的第一个样本。 样本集生成。在Grabbag中取出第i个样本用Store中的当前样本集按最近邻法分类。若分类错误，则将该样本从Grabbag转入Store中，若