如何在一组点中找到一个点的第k个最近邻？

Question

我有一组在2D平面上的点（x，y）。给定一个点（x0，y0）和数字k，如何在点集中找到（x0，x0）的第k个最近邻居。具体来说，点集由两个数组表示：x和y。点（x0，y0）由索引i0给出。它意味着x0 = x（i0）和y0 = y（i0）。

是否有Matlab中的任何函数或其他方法可以帮助我解决这个问题。如果Matlab没有这种函数，您能否建议其他有效的方法。

编辑：我必须为集合中的每个点（x0，y0）计算这种距离。集合的大小约为1000。 k的值应该约为sqrt（1500）。最糟糕的是，我要做很多次这样的计算。在每次迭代中，集合都会改变，我会再次计算距离。因此，运行时间是一个关键问题。

- opmfan

Answer 1

如果您需要对多个点进行此检查，您可能需要先构建一个点间距离表

squareform(pdist([x y]))

- zamazalotta

---

是的，我会为集合中的每个点执行此操作。因此，某种距离表可以帮助节省运行时间。我将找出如何在我的问题中使用squareform函数。非常感谢。 - opmfan

这个函数实际上是pdist，squareform只是将pdist的向量输出转换为一个方阵。 - zamazalotta

但前提是你必须拥有统计工具箱。 - Andrey Rubshtein

它对我有效。也许这不是最好的方法，但实现和使用起来很简单。老实说，我没有太多时间完成代码。非常感谢。 - opmfan

这是O(N²)，其中N是点的数量，每次查询的复杂度为O(N lg N)。下面提到的kd树，也被knnsearch在某些条件下使用，通常要快得多，构建花费O(N lg^2 N)，1个最近邻花费O(lg N)，并且我猜，在k较小且数据集有利的情况下，k个最近邻大约需要花费O(k(lg k)(lg N))（思考：通过二分查找）。 （这意味着，例如，如果您有10000个点，则应该快100到1000倍左右。）因此，更推荐使用knnsearch。 - Evgeni Sergeev

Answer 2

如果您安装了统计工具箱，您可以使用函数knnsearch来实现。

- 3lectrologos

---

knnsearch似乎是一个解决方案，但我不确定如何确切地应用knnsearch到我的问题上。我会找到方法的。无论如何，您能否给我更多有关使用knnsearch的详细信息。非常感谢。 - opmfan

你看过Matlab帮助文档了吗？（在我上面的回答中添加了链接） - 3lectrologos

我读了关于knnsearch的在线文档，但对我来说有点复杂，而且我真的没有太多时间去理解和使用它。我尝试了更简单的方法。虽然运行时间更长，但我会先尝试这种方法。谢谢你的帮助。 - opmfan

Answer 3

一种暴力算法可能是这样的：

array x[n] = ()
array y[n] = () 
array d[n] = ()

... populate x and y arrays with your n points ...

/* step over each point and calculate its distance from (x0, y0) */
for i = 1 to n
do
  d[i] = distance((x0, y0), (x[i], y[i])
end 

/* sort the distances in increasing order */
sort(d)

/* the k'th element of d, is the k'th nearest point to (x0, y0) */
return d[k]

- ardnew

Answer 4

暴力破解的方法大致如下：

%Create some points
n = 10;
x = randn(n,1);
y = randn(n,1);

%Choose x0
ix0 = randi(n);

%Get distances
d = sqrt(...
    (x - x(ix0) ).^2 + ...
    (y - y(ix0) ).^2 );

%Sort distances
[sorted_Dstances, ixSort] = sort(d);

%Get kth point
k = 3;
kth = [x(ixSort(k+1)); y(ixSort(k+1))]; %+1 since the first element will always be the x0 element.

- Pursuit

---

你不应该删除元素本身吗？考虑一下k=1的情况。 - Andrey Rubshtein

好的建议。我通常不喜欢像这样更改匹配向量的大小。也许在最终索引中添加“+1”。编辑：虽然如果有一个与初始点相同的点，那么这会留下一个空隙。如果您想确保答案是不同的点，即使某些点可能相等，则需要更多的工作。 - Pursuit

@Pursuit，删除相等的点也没有意义。如果您有5个与您正在搜索的点相等的点，则第三远的距离应为0。 - ardnew

非常感谢！但是我必须计算集合中每个点的这种距离。因此，这种方法似乎比我预期的要简单一些。很抱歉我之前没有澄清。 - opmfan

Answer 5

免费且开源的VLFeat工具包含有kd-tree实现，以及其他有用的功能。

- Maurits