machine-learning - 对于大 k (k = n)，如何在 kd 树中找到 k 最近邻？

Question

我目前正在python中从头开始实现一个kd树，并将knn算法应用于它。我已经构建了这棵树并拥有找到 1-nn 的算法，但我不确定如何使用它来获取 k 最近邻。我通过将每个节点与正确的属性进行比较来找到最近的邻居，然后向下移动节点的适当子/侧。完成该节点后，我进行了修剪技术并确定是否值得查看节点的另一个子节点，看看我是否获得了更好的距离（更近的邻居）。我在网上读到，我可以将 k 最佳距离保存到最大堆中，然后这会给我 k 最近的邻居。我已经实现了这个，但我发现它有缺陷，也许我没有正确地做到这一点。这让我想到了我的问题。

假设我的 k 很大，k = n，其中 n 是树中项目或节点的数量。如果我将树遍历到最近的邻居，并且沿途保存所有最佳距离，我的算法将不会遍历树中的所有节点。它将选择到达最近节点的最佳路径，并且通过修剪它会忽略节点，因此如果 k = n，它将无法访问 k 个节点。因此，我的最大堆将只有我遍历的节点数的最佳距离，并且我将无法遍历 k 个节点，因此它不会有 k 近邻。我该如何解决这个问题？还是有其他方法，我做错了什么？

** 我知道使用带有 kd 树的大 k 不是最佳实践，但我的任务是提供从 k=1 到 k=n 的所有 k 的准确性。

标签： machine-learningknnnearest-neighborkdtree