第四章近邻法则和聚类课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章 近邻法则和聚类,近邻法则,最近邻法则,k-近邻法,则,近邻法错误率分析,快速搜索近邻法,第四章 近邻法则和聚类近邻法则,1,近邻法则是一种根据样本提供的信息，绕开概率的估计而直接决策的技术，所以它也属于非参数判别方法的一种。,4.1近邻法,近邻法则是一种根据样本提供的信息，绕开概率的,2,模式识别的基本方法有两大类，一类是将特征空间划分成决策域，这就要确定判别函数和分界面方程。而另一种方法则称为模板匹配，即将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。上面我们讨论的方法可以说都是将特征空间划分为决策域，并用判别函数或决策面方程表示决策域的方法。而近邻法则在原理上属于模板匹配。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻),就按最近似的模板的类别作为自己的类别。,模式识别的基本方法有两大类，一类是将特征空间,3,譬如A类有10个训练样本，因此有10个模板，B类有8个训练样本，就有8个模板。任何一个待测试样本在分类时与这18个模板都算一算相似度，如最相似的那个近邻是B类中的一个，就确定待测试样本为B类，否则为A类。因此原理上说近邻法是最简单的。,但是近邻法有一个明显的缺点就是计算量大，存储量大，要存储的模板很多，每个测试样本要对每个模板计算一次相似度，因此在模板数量很大时，计算量也很大的。那么有一个如此明显缺点的方法还有没有存在的必要性呢？这就要看其是否有优点，所以对近邻法的优点也要弄清楚。结论是:在模板数量很大时其错误率指标还是相当不错的。这就是说近邻法有存在的必要。,譬如A类有10个训练样本，因此有10个模板，,4,4.1.1最近邻法则,将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。对一个C类别问题，每类有N,i,个样本，i1，C，则第i类,i,的判别函数,其中X,i,k,表示是,i,类的第k个样本。,决策规则为：如果,则决策Xj。,最近邻法在原理上最直观，方法上也十分简单，只要对所有样本(共NN,i,)进行N次距离运算，然后以最小距离者的类别作决策。,4.1.1最近邻法则 将与测试样本最近邻样本的,5,公式中用表示距离，其实这是一个象征性的表示，你可以采用任何一种相似性的度量，一般采用欧氏距离为相似性度量的较多。但由于特征向量各个分量之间对应的物理意义很可能不一致，因此究竟采用何种相似性度量要看问题而定。,最近邻规则是次优的方法，通常的错误率比最小可能错误率（即最小贝叶斯法则的错误率）要大。但在无限训练样本的情况下，这个错误率不会超过贝叶斯错误率的一倍。,公式中用表示距离，其实这是一个象征性的表示，你可以采用,6,设X的最近邻点X的类别,为一随机变量，,i,的概率就是后验概率,P(,i,|,X,)。当样本数目越来越多时，可以认为,X距离X 足够近，从而近似认为,P(,i,|,X,),P(,i,|,X,)。近邻法则可以看成是一个随机化的决策：按照概率P(,i,|,X,)来决定X的类别。,按贝叶斯决策法则：以概率1决策为,m,按最近邻法则：以概率,P(,m,|,X,),决策为,m,设,设X的最近邻点X的类别为一随机变量，,7,当,P(,m,|,X,)接近于1，即当最小错误概率非常小时，近邻法则的结果和最小错误率的Bayes法则的结果几乎相同，而其错误率也比较小，这说明两种方法同样“好”。,而当各类的后验概率接近于 时，两种决策规则的分类结果就相差比较大了，但两者的错误率都接近 ，说明两种方法同样“坏”。,虽然需要更详细的理论分析，但粗略的感觉是：最近邻法则有比较好的结果并不是偶然的。,当P(m|X)接近于1，即当最小错误概率非常小时，近邻法,8,最近邻法可以扩展成找测试样本的k个最近样本作决策依据的方法。其基本规则是，在所有N个样本中找到与测试样本的k个最近邻者，其中第个个类别所占个数为g,i,(X),i1，c，决策规则：,如果则决策X,j,。,4.1.2 K-近邻法则,k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。,最近邻法可以扩展成找测试样本的k个最近样本作决策依据的,9,K近邻算法从测试样本点开始生长，不断扩大区域，直到包含进k各训练样本点为止，并且把X归为这最近的k个训练样本点中出现频率最大的类别中。,如图为k=5的情况。,K近邻算法从测试样本点开始生长，不断扩大区域，直到包含进k各,10,4.1.3 近邻法则的错误率,其实近邻法的错误率是比较难算的，因为训练样本集的数量总是有限的，有时多一个少一个训练样本对测试样本分类的结果影响很大。譬如图中：,红点表示A类训练样本，蓝点表示B类训练样本，而绿点O表示待测样本。假设以欧氏距离来衡量，O的最近邻是A,3,，其次是B,1,，因此O应该属于A类，但若A,3,被拿开，O就会被判为B类。这说明计算最近邻法的错误率会有偶然性，也就是指与具体的训练样本集有关。,4.1.3 近邻法则的错误率其实近邻法的错误率是比较难算的，,11,同时还可看到，计算错误率的偶然性会因训练样本数量的增大而减小。因此人们就利用训练样本数量增至极大，来对其性能进行评价。这要使用渐近概念，以下都是在渐近概念下来分析错误率的。,当最近邻法所使用的训练样本数量N不是很大时，其错误率是带有偶然性的。图中所示一维特征空间中两类别情况。X表示一特测试样本，而X是所用训练样本集中X的最邻近者，则错误是由X与X分属不同的类别所引起的。由于X与所用训练样本集有关，因此错误率有较大偶然性。,同时还可看到，计算错误率的偶然性会因训练样本数量的增大而减小,12,但是如果所用训练样本集的样本数量N极大，即N时，可以想像X将趋向于X，或者说处于以X为中心的极小邻域内，此时分析错误率问题就简化为在X样本条件下X与一个X(X的极限条件)分属不同类别的问题。如果样本X的第i类后验概率为P(,i,|X),那么对X值，在N条件下，发生错误决策的概率为：,当训练样本数量无限增多时，一个测试样本X的最近邻在极限意义上讲就是X本身。那么当前测试样本与它的最近邻都属于同一类才能分类正确，故正确分类率为。,但是如果所用训练样本集的样本数量N极大，即N时，可以想像,13,而在这条件下的平均错误率,P称为渐近平均错误率，是P,N,(e)在N的极限。为了与基于最小错误率的贝叶斯决策方法对比（基于最小错误率贝叶斯决策的错误率是出错最低限，因此要与它作比较），下面写出贝叶斯错误率的计算式：,其中 ，而,而在这条件下的平均错误率,14,最近邻法的错误率要高于贝叶斯错误率，可以证明以下关系式成立：,最近邻法的渐近平均错误率的下、上界分别为贝叶斯错误率 及,。,由于一般情况下 很小，因此上式又可粗略表示成 因此可以说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。从这点说最近邻法是优良的，因此它是模式识别重要方法之一。,最近邻法的错误率要高于贝叶斯错误率，可以证明以下关系式成立：,15,两类别模式下，什么情况下P(,1,|X)1或P(,2,|X)=1?P(,1,|X)=P(,2,|X)会出现什么什么情况？一般来说，在某一类样本分布密集区，某一类的后验概率接近或等于1。此时，基于最小错误率贝叶斯决策基本没错，而近邻法出错可能也很小。而后验概率近似相等一般出现在两类分布的交界处，此时分类没有依据，因此基于最小错误率的贝叶斯决策也无能为力了，近邻法也就与贝叶斯决策平起平坐了。从以上讨论可以看出，当N时，最近邻法的渐近平均错误率的下界是贝叶斯错误率，这发生在样本对某类别后验概率处处为1的情况或各类后验概率相等的情况。,两类别模式下，什么情况下P(1|X)1或P(2|X)=,16,在N的条件下，k-近邻法的错误率要低于最近邻法。从图中也可看出，无论是最近邻法，还是k-近邻法，其错误率的上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。,不同k值时的错误率情况,K-近邻法则的错误率：,在N的条件下，k-近邻法的错误率要低于最近邻法。从图中,17,最近邻法和K近邻法的共同优点是简单，而且结果比较好，但仍存在不少缺点：,(1)要求的计算机存储容量和计算量相当大。,(2)没有考虑到决策风险。,(3)以上的分析是建立在无穷多样本的基础上的，对于有限样本的情况，缺乏理论上的分析。,最近邻法和K近邻法的共同优点是简单，而且结果比较好，但仍存在,18,4.1.4 快速近邻算法,从上述讨论中可以看出，尽管近邻法有其优良品质，但是它的一个严重弱点与问题是需要存储全部训练样本，以及繁重的距离计算量。但以简单的方式降低样本数量，只能使其性能降低，这也是不希望的。为此要研究既能减少近邻法计算量与存储量，同时又不明显降低其性能的一些改进算法。总的说来，改进的方法大致分为两种原理。一种是对样本集进行组织与整理，分群分层，尽可能将计算压缩到在接近测试样本邻域的小范围内，避免盲目地与训练样本集中每个样本进行距离计算。另一种原理则是在原有样本集中挑选出对分类计算有效的样本，使样本总数合理地减少，以同时达到既减少计算量，又减少存储量的双重效果。下面仅就第一种情况进行讨论。,4.1.4 快速近邻算法从上述讨论中可以看出，尽管近邻法有其,19,1.分量邻域法,输入：n维训练样本集，待分类样本X；,输出：X的最近邻,步骤：,（1）以X为中心，构造一个小的2d为边长的邻域C。,（2）在C中找出落入的训练集 的样本，如果C空，增加2d一个级差 转1。,（3）扩大邻域2d到 ，找出全部落入这个邻域中的训练集的样本，即 的一个子集 。,（4）对全部 计算距离 ，距离最小者即为X的最邻。,简单、快速，但特征向量维数较高时，效率较差。,1.分量邻域法简单、快速，但特征向量维数较高时，效率较差。,20,2.列表法,分为预处理阶段和搜索阶段,（1）预处理：在模式空间中任意指定三个点A，B，C。分别计算这三个点到训练样本集中全部成员的距离，并按由近及远的顺序排列，构成三个表A，B，C。,（2）搜索阶段：计算待分类模式X到A，B，C的距离,在三个表中分别按 将X嵌入相应的位置上。,在表A，B，C中取X的近邻形成三个子集 。若,非空，则交集中可能包含X的最近邻。若,为空则要扩大X的邻域范围，直至非空为止，从而找到X的最近邻。,2.列表法,21,预处理阶段需要花费许多计算时间和空间，但分类的时间不包含这个时间，从而搜索阶段的处理是很快的。,预处理阶段需要花费许多计算时间和空间，但分类的时间不包含这个,22,