关于knn算法中kd树的问题

  统计/机器学习 监督式学习    浏览次数： 426
  面试中常见简答题？
0

kd树可以用来来找样本点的最近邻的点，但是k近邻算法需要找到这个样本点最近的前k个点，那么kd树和knn是如何一起使用的？

难道每次找到一个最近点后，删掉这个点再重新建一个kd树，接着再找一个最近点，直到找到k个点吗？

谢谢！

 

PyGeek   2018-08-29 21:35


   1个回答 
4

只需要建立一个kd tree。kd tree不会直接给出相邻点，只能减小相邻点的查找范围，减小两点间距离的计算量。如果是kNN，需要记录k个当前最相邻点，在遍历kd tree时把每个可能的点和这k个当前最相邻点比较并更新，直到达到root。

SofaSofa数据科学社区 DS面经 问答 实战

Zealing   2018-11-08 01:15

明白了，谢谢回复 - PyGeek   2018-11-30 16:14


  相关主题

Extra Tree算法   1回答

决策树怎么做增量学习或者online学习？   1回答

决策树可以做多元分类吗？   1回答

决策树的熵是什么？怎么用熵来选分叉？   1回答

随机森林是如何计算测试样本的概率的？   1回答

剪枝是什么意思   1回答

决策树的深度和数据特征个数的关系   1回答

决策树算法ID3，C4.5和CART的特点、异同？   3回答

随机森林中增加树的数量对于偏差和方差的影响   2回答

决策树是如何得到量化的概率，不只是0或1的标签？   2回答

决策树剪枝有什么策略或者注意事项？   2回答

Adaboost里的树有没有可能权重是负数？   1回答

回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单，你自己想”、“书上有的，你认真看”这类的回答；如果你认为对方的提问方式或者内容不妥，你可以直接忽略该问题，不用进行任何作答，甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出！