6.2k近邻法 6.2k近邻法 口k近邻法错误率分析 ■在N一∞的条件下，k-近邻法的错误率要低于最 近邻法。 ■最近邻法和k近邻法的错误率上下界都是在一倍 到两倍贝叶斯决策方法的错误率范围内。 k=1 特定点 k=2 k=3 k=99 贝叶斯误 6.3改进的近邻法 6.3.1快速搜索近邻法 口近邻法的一个严重不足与问题是需要存储全部训 口基本思想：将样本集按邻近关系分解成组，给出 练样本，以及繁重的距离计算量。 每组的质心所在，以及组内样本至该质心的最大 口两类改进的方法： 距离。这些组又可形成层次结构，即组又分子 组，因而待识别样本可将搜索近邻的范围从某一 ■一种是对样本集进行组织与整理，分群分层，尽 大组，逐渐深入到其中的子组，直至树的叶结点 可能将计算压编到在接近测试样本邻域的小范围 所代表的组，确定其相邻关系。这种方法着眼于 内，避免盲目地与训练样本集中每个样本进行距 离计算。 只解决减少计算量，但没有达到减少存储量的要 求 ■另一种则是在原有样本集中挑选出对分类计算有 效的样本，使样本总数合理地减少，以同时达到 口算法包括两个阶段： 既减少计算量，又减少存储量的双重效果。 ■训练样本集的分级分解； ■搜索； 6.3.1快速搜索近邻法 6.3.1快速搜索近邻法 阶段一：训练样本集的分级分解 =708 M-350 ■符号约定 口P树中的一个结点； 口K:p对应一个样本子集； cN2:K,中的样本数； =102 N:=292 口M。:K中的样本均值： 口rp从K,中任一样本到M的最大距离 T。=max D(x,Mn） 玉，CA。13 6.2 k-近邻法 14 6.2 k-近邻法  k-近邻法错误率分析  在 N→∞ 的条件下，k-近邻法的错误率要低于最 近邻法。  最近邻法和 k-近邻法的错误率上下界都是在一倍 到两倍贝叶斯决策方法的错误率范围内。 15 6.3 改进的近邻法  近邻法的一个严重不足与问题是需要存储全部训 练样本，以及繁重的距离计算量。  两类改进的方法：  一种是对样本集进行组织与整理，分群分层，尽 可能将计算压缩到在接近测试样本邻域的小范围 内，避免盲目地与训练样本集中每个样本进行距 离计算。  另一种则是在原有样本集中挑选出对分类计算有 效的样本，使样本总数合理地减少，以同时达到 既减少计算量，又减少存储量的双重效果。 16 6.3.1 快速搜索近邻法  基本思想：将样本集按邻近关系分解成组，给出 每组的质心所在，以及组内样本至该质心的最大 距离。这些组又可形成层次结构，即组又分子 组，因而待识别样本可将搜索近邻的范围从某一 大组，逐渐深入到其中的子组，直至树的叶结点 所代表的组，确定其相邻关系。这种方法着眼于 只解决减少计算量，但没有达到减少存储量的要 求。  算法包括两个阶段：  训练样本集的分级分解；  搜索； 17 6.3.1 快速搜索近邻法 阶段一：训练样本集的分级分解  符号约定  p:树中的一个结点；  Kp：p对应一个样本子集；  Np：Kp中的样本数；  Mp：Kp中的样本均值；  rp：从 Kp中任一样本到Mp的最大距离， max ( , ). i p p ip K r D   x x M 18 6.3.1 快速搜索近邻法