《第六章 近邻法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第六章 近邻法PPT讲稿.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章 近邻法第1页，共21页，编辑于2022年，星期三第六章 近邻法第2页，共21页，编辑于2022年，星期三6.1.1.问题描述 特征向量特征向量 类别类别X=(0.1,0.1)?6.1 近邻法原理及其决策规则特征向量特征向量类别类别(0.1,0.2)W1(0.2,0.1)W1(0.4,0.5)W2(0.5,0.4)W2第六章 近邻法第3页，共21页，编辑于2022年，星期三u最小距离分类器:它将各类训练样本划分成若干子类，并在每个子类中确定代表点。未知样本的类别则以其与这些代表点距离最近作决策。该方法的缺点是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。m1m2xg(x)
2、=0m1m2x最近邻分类器(nearest neighborhood classifier,nnc):最小距离分类器的一种极端的情况，以全部训练样本作为代表点，计算测试样本与所有样本的距离，并以最近邻者的类别作为决策。最初的近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。第4页，共21页，编辑于2022年，星期三6.1.2.6.1.2.最近邻法的决策规则最近邻法的决策规则将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。对一个C类别问题，每类有Ni个样本，i1，C，则第i类i的判别函数其中Xik表示是i类的第k个样本。以上式
3、为判别函数的决策规则为：最近邻法在原理上最直观，方法上也十分简单，只要对所有样本(共NNi)进行N次距离运算，然后以最小距离者的类别作决策。如果则决策6.1 近邻法原理及其决策规则第5页，共21页，编辑于2022年，星期三在二维情况下，最近邻规则算法使得二维空间被分割成了许多在二维情况下，最近邻规则算法使得二维空间被分割成了许多VoronoiVoronoi网格，每一个网格代表的类别就是它所包含的训练样本点所网格，每一个网格代表的类别就是它所包含的训练样本点所属的类别。属的类别。6.1 近邻法原理及其决策规则第6页，共21页，编辑于2022年，星期三最近邻法错误率最近邻法的错误率高于贝叶斯错误率
4、，可以证明以下关最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立：系式成立：由于一般情况下由于一般情况下P*很小，因很小，因此又可粗略表示成：此又可粗略表示成：可粗略说最近邻法的渐近平均错误可粗略说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。率在贝叶斯错误率的两倍之内。6.1.2 近邻法决策规则第7页，共21页，编辑于2022年，星期三k-近邻法近邻法:最近邻法的扩展，其基本规则是，在所有最近邻法的扩展，其基本规则是，在所有N个个样本中找到与测试样本的样本中找到与测试样本的k个最近邻者，其中各类别所占个最近邻者，其中各类别所占个数表示成个数表示成ki,i1，c。定义定义判别函数判
5、别函数为：为：gi(x)=ki,i=1,2,c。决策规则决策规则为：为：k-近邻一般采用近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等为奇数，跟投票表决一样，避免因两种票数相等而难以决策。而难以决策。6.1.3.k-近邻法决策规则 6.1 近邻法原理及其决策规则第8页，共21页，编辑于2022年，星期三从样本点从样本点x开始生长，不断扩大区域，直到包含进开始生长，不断扩大区域，直到包含进k个训练样本个训练样本点为止，并且把测试样本点点为止，并且把测试样本点x的类别归为这最近的的类别归为这最近的k个训练样本点个训练样本点中出现频率最大的类别。中出现频率最大的类别。6.1.3 K近邻法第
6、9页，共21页，编辑于2022年，星期三k-近邻法错误率最近邻法和最近邻法和k-近邻法的错误率上下界都是在一倍到两倍贝叶斯近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。决策方法的错误率范围内。在在k 的条件下，的条件下，k-近邻法的错误率要低于最近邻法。近邻法的错误率要低于最近邻法。在在k 的条件下，的条件下，k-近邻法的错误率等于贝叶斯误差率。近邻法的错误率等于贝叶斯误差率。6.1.3 K近邻法第10页，共21页，编辑于2022年，星期三最近邻与最近邻与k-近邻法分类效果近邻法分类效果3-近邻最近邻第11页，共21页，编辑于2022年，星期三6.1.4.近邻法中的几个问题
7、问题1：如何度量两个向量的相似性？各种距离度量6.1 近邻法原理及其决策规则 绝对值距离（城市距离、棋盘距离）s阶明考夫斯基距离 欧几里德距离已知两个样本 切比雪夫距离 s趋向无穷大时明氏距离的极限情况 马哈拉诺比斯距离 第12页，共21页，编辑于2022年，星期三问题2 几种距离度量之间的关系每一个彩色的平面由距离原点为每一个彩色的平面由距离原点为1的点所形成。的点所形成。6.1 近邻法原理及其决策规则第13页，共21页，编辑于2022年，星期三问题3 计算复杂性N个样本，每一个样本是d维，在对于一个未知样本判别时，需要的计算量为？当样本量N非常大时，如何实时（在线）完成识别任务？对于分类来
8、说，每一个样本都有价值吗？6.1 近邻法原理及其决策规则第14页，共21页，编辑于2022年，星期三6.1.5 近邻法的应用举例6.1 近邻法原理及其决策规则例1：人脸识别第一步：把人脸图像映射到一个低维的字空间中，成为空间中的一个向量；第二步：使用近邻法对于未知的人脸图像分类。例2：B3B4B1B2A3A1A2第15页，共21页，编辑于2022年，星期三B3B4B1B2A3A1A26.1.5 近邻法应用举例第16页，共21页，编辑于2022年，星期三小结 模式识别（机器自动分类）的基本方法有两大类：I.将特征空间划分成决策域，需要确定判别函数或确定分界面方程。II.模板匹配，即将待分类样本与
9、标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。前面讨论的方法可以说都是将特征空间划分为决策域，并用判别函数或决策面方程表示决策域的方法。近邻法则在原理上属于模板匹配。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻)，就按最近似的模板的类别作为自己的类别。6.1 近邻法原理及其决策规则缺点：要存储的模板很多，每个测试样本要对每个模板计算一次相似度，因此在模板数量很大时，距离计算量也很大的。优点：在模板数量很大时其错误率指标还是相当不错的。这就是说近邻法有存在的必要。趋利避害，保留其优点，克服或改进其缺点呢？剪辑近邻法与压缩近
10、邻法就是两种有代表性的改进方法。第17页，共21页，编辑于2022年，星期三6.2 6.2 改进的近邻法改进的近邻法改进的方法大致分为两种原理：一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种原理则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。第六章 近邻法第18页，共21页，编辑于2022年，星期三第六章 近邻法 6.2.1.快速搜索近邻法 这种方法着眼于减少计算量，但不能减少存储量。基本思想：将样本集按邻近关系分解成组，给出每组的质
11、心所在，以及组内样本至该质心的最大距离。这些组又可形成层次结构，即组又分子组。因而待识别样本可将搜索近邻的范围从某一大组，逐渐深入到其中的子组，直至树的叶结点所代表的组，确定其相邻关系。第19页，共21页，编辑于2022年，星期三 6.2.2.剪辑近邻法 基本思想是：当不同类别的样本在分布上有交迭部分的，分类的错误率主要来自处于交迭区中的样本。由于交迭区域中不同类别的样本彼此穿插，导致用近邻法分类出错。因此如果能将不同类别交界处的样本以适当方式筛选，可以实现既减少样本数又提高正确识别率的双重目的。为此可以利用现有样本集对其自身进行剪辑。最终目标：去掉两类边界附近的样本6.2 改进的近邻法第20页，共21页，编辑于2022年，星期三6.2.3压缩近邻法压缩近邻法 基本思想是：利用现有样本集，逐渐生成一个新的样本集，使该样本集在保留最少量样本的条件下，仍能对原有样本的全部用最近邻法正确分类，那末该样本集也就能对待识别样本进行分类，并保持正常识别率。最终目标：将靠近类别中心的对分类不起作用的样本去掉。6.2 改进的近邻法第21页，共21页，编辑于2022年，星期三