关于knn算法中kd树的问题

  统计/机器学习 监督式学习    浏览次数：564        分享
二维码
手机扫描二维码
  面试中常见简答题？
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


  相关主题

剪枝是什么意思   1回答

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

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

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

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

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

如果采用非等权重的方法集成一个随机森林，会表现得更好嘛？   1回答

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

Extra Tree算法   1回答

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

Gradient tree boosting和random forest (随机森林) 有什么区别和联系   1回答

随机森林如何调参？   3回答

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

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

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

我们谢绝答非所问。

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

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