【图文】K近邻算法PPT.doc

K近邻法的实现kd树 ? 2017/1/9 11 K近邻法的实现kd树 ? 搜索kd树 ? ? 利用kd树可以省去大部分数据点的搜索从而减少搜索的计算量 这里以最近邻为例同样的方法可以应用到K近邻 给定一个目标点搜索其最近邻首先找到包含目标点的叶结点 然后从该叶结点出发依次回退到父结点不断查找与目标点 最邻近的结点当确定不可能存在更近的结点时终止这样搜索 就被限制在空间的局部区域上效率大为提高