我需要在kd树中实现10维数据的k近邻搜索。
但问题是，我的算法对于k=1非常快，但是对于k>1（k=2,5,10,20,100）则慢了多达2000倍。
这种情况对于kd树来说正常吗？还是我做错了什么？
2个回答
8
好的，这主要取决于你特定的实现和数据集。
一棵平衡不良的树意味着你要搜索比你需要的数据更多。确保你的树构造是合理的。
这也可能取决于你如何找到k个邻居。如果你的算法搜索最近的邻居并存储它，然后搜索第二个最近的邻居并存储等等，那么你的搜索效率不高。相反，保持一个k个最近邻居的运行列表，并在遍历树时找到更近的点将其移出列表。这样你只需搜索一次，而不是k次。
无论哪种方式，听起来你正在为课程做这个。试着和你的教授、助教或同学交流，看看你的结果是否典型。
- Andrew
1
平衡不良的树是问题所在。我已经检查了我的树构建方法，发现选择了错误的分割维度。感谢提示 :) - Andraz
6
我知道这个问题已经有答案了，但是如果想要更详细地了解使用k-d树进行KNN搜索的内容，请参考Bentley（1975:514）的文章，《ACM通讯》18（9），九月。
- fluffels
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接