machine-learning - KD树搜索KNN什么时候不起作用？

Question

我一直在探索和学习 KNN 的 KD 树（K 最近邻问题），什么时候搜索不起作用？或者是否值得或不改进天真的搜索。这种方法有什么缺点吗？

score 3 · Accepted Answer

Kd 树在高维度（您必须访问大量树枝）中效果不佳。一条经验法则是，如果您的数据维度是，那么只有当您拥有的数据点k多于多个时，kd 树才会有任何好处。2^k

在高维度中，您通常希望切换到近似最近邻搜索。如果您还没有遇到过它，FLANN ( github ) 是一个非常有用的库（带有 C、C++、python 和 matlab API）；它具有很好的 kd 树、蛮力搜索和几种近似技术的实现，它可以帮助您自动调整它们的参数并轻松地在它们之间切换。

score 2 · Accepted Answer

这取决于您的距离函数。

您不能使用具有任意距离函数的 kd 树。闵可夫斯基规范应该没问题。但在很多应用程序中，您会希望使用更高级的距离函数。

另外，随着维数的增加，kd-trees 的工作效果会大大降低。

原因很简单：kd-trees 避免查看到边界的一维距离已经大于所需阈值的点，即欧几里得距离的位置（其中 z 是最近的边界，y 是最近的已知点）：

(x_j - z_j)      <=>   sqrt(sum_i((x_i - y_i)^2))
equivalently, but cheaper:
(x_j - z_j)^2    <=>   sum_i((x_i - y_i)^2)

你可以想象，这个修剪规则成立的机会随着维度的数量而急剧下降。如果您有 100 个维度，那么单个维度的平方差几乎不可能大于平方差的总和。

score 1 · Accepted Answer

knn 的时间复杂度：O(k * lg(n))

，其中 k 是 k-最近邻，lg(n) 是 kd-tree 高度

如果数据集的维度由于如此巨大的空间而很高，kd-trees 将无法正常工作。

让我们考虑你在原点周围有很多点，为简单起见考虑二维

如果你想找到任何点的 k 最近邻，那么你必须沿着 4 个轴搜索，因为所有点都彼此靠近，这会导致回溯到 kd-tree 中的其他轴，

所以对于一个 3 维空间，我们必须沿着 8 个方向搜索

概括为 n 维是 2^k

所以时间复杂度变成 O(2^k * lg(n))

3 回答 3