KD 树上的 KNN 算法

kd树knn算法

给定kd树,求距离p点最近的k个样本。
零、L为有k个空位的列表
(一)、根据p的坐标值和每个节点的切分向下搜索。
(二)、到达一个底部节点时,标记。如果L不足k,当前节点加入L;如果L有值,且当前节点与p的距离小于L里最长的距离,用点前点替换L中离p最远的点。
(三)、如果当前节点不是最顶点,执行(a);否则,输出L,完成。
(a)向上爬一个节点。如果爬过的节点未被标记,则标记,然后执行(1)和(2);如果已被标记,再执行(a)。
(1)如果L不足k,将此节点加入L;如果L已满,且当前节点与p的距离小于L里最长距离,则替换之。
(2)计算p与当前节点切分线距离。如果该距离大于等于L中距离p最远的距离且L中已满,执行(三);如果该距离小于L中最远距离或L未满,从当前节点另一枝从(一)开始。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 练习材料 L39-1: Nothing to worry about The rough across the p...
    喵小园upup阅读 1,045评论 0 0
  • Linux目录特点 特点:一起从根开的 linux下面的目录结构 是一个有层次的倒挂树形 linux下面的目录与次...
    begyou阅读 1,738评论 0 0
  • 今天下午保养马六 拆机滤的时候上面没胶圈 渗油 装的时候 新机滤里有个胶圈 就装上了 后来看不漏 就装好了 ...
    不够穷没有野心阅读 1,103评论 0 0
  • 喈喈切切,有鸟寻苦乐,天上追雪。一捧飞花,装满年华,松风抖落残屑。飞鸿一去无留迹,但听得、琼枝吹...
    桂做翔阅读 4,895评论 16 64
  • 遇到現在的丈夫對於丫頭來說純屬偶然!一場已經推掉的聚餐又鬼使神差地去參加了,在座十五六個人對於丫頭來說沒什麼印象,...
    寧寧阅读 1,558评论 0 0

友情链接更多精彩内容