问题标签 [nearest-neighbor]

我的任务是找到包含某个数据集的最多点的 N 个集群，因为这些集群受到一定大小的限制。目前，我正试图通过将我的数据插入到 kd 树中，迭代数据并找到其最近的邻居，然后在它们创建的集群不超过限制时合并这些点。我不确定这种方法会给我一个全球性的解决方案，所以我正在寻找调整它的方法。如果你能告诉我这会遇到什么类型的问题，那就太好了。

我有一个在 100 维空间中有 500,000 个点的数据库，我想找到最接近的 2 个点。我该怎么做？

更新：空间是欧几里得，对不起。并感谢所有的答案。顺便说一句，这不是家庭作业。

我有一个大约 100,000 个（X，Y）对的数据集，表示 2D 空间中的点。对于每个点，我想找到它的 k 最近邻。

所以，我的问题是——假设我想绝对最小化整体运行时间，什么样的数据结构/算法是合适的选择？

我不是在寻找代码 - 只是指向合适方法的指针。我对似乎相关的选择范围感到有点害怕——四叉树、R-树、kd-树等。

我认为最好的方法是构建一个数据结构，然后对每个点运行某种 k-最近邻搜索。但是，由于（a）我事先知道这些点，并且（b）我知道我必须对每个点只运行一次搜索，也许有更好的方法？

一些额外的细节：

• 因为我想最小化整个运行时间，所以我不在乎大部分时间是花在结构还是搜索上。
• (X, Y) 对分布得相当好，所以我们可以假设一个几乎均匀的分布。

所以我有大约 16,000 个 75 维数据点，对于每个点，我想找到它的 k 个最近邻居（使用欧几里德距离，如果这样更容易，目前 k=2）

我的第一个想法是为此使用 kd-tree，但事实证明，随着维度数量的增加，它们变得相当低效。在我的示例实现中，它只比穷举搜索稍微快一点。

我的下一个想法是使用 PCA（主成分分析）来减少维数，但我想知道：是否有一些聪明的算法或数据结构可以在合理的时间内准确地解决这个问题？

所以，我正在实施一个KD-Tree来进行最近邻搜索。我已经让构建树部分工作，但我认为我不完全理解搜索部分。

关于遍历树搜索邻居，维基百科文章说如下：

“大于或小于 spit 维度中的当前节点是什么意思？我们是根据与查询的距离比较点还是通过拆分维度比较点？

另外，有人可以解释一下关于超空间和超平面的部分吗？我觉得我理解它，但由于我不确定我是否需要更多解释。

谢谢！

我需要为数据集的每个点找到它所有最近的邻居。数据集包含大约。1000 万个二维点。数据接近网格，但没有形成精确的网格……

此选项排除（在我看来）使用 KD 树，其中基本假设是没有点具有相同的 x 坐标和 y 坐标。

我需要一个快速算法 O(n) 或更好的算法（但实现起来不太难:-)））来解决这个问题......由于 boost 没有标准化，我不想使用它......

感谢您的回答或代码示例...

我正在尝试构建 KD 树（静态案例）。我们假设点在 x 和 y 坐标上都排序。

对于均匀的递归深度，该集合被分成两个子集，垂直线穿过中值 x 坐标。

对于奇数递归深度，该集合被分成两个子集，水平线穿过中值 y 坐标。

中位数可以根据 x / y 坐标从排序集中确定。我在每次拆分集合之前执行此步骤。而且我认为它会导致树的构建缓慢。

1. 请你能帮我检查一下并优化代码吗？
2. 我找不到第 k 个最近的邻居，有人可以帮我写代码吗？

非常感谢您的帮助和耐心...

请看示例代码：

我有一个数据集，我需要为它找到 K 个最近的邻居，或者距离 d 内的所有邻居。数据集定义了自定义距离，但它不是欧几里得距离。

我以前使用过度量树，主要是覆盖树。但是，在这种情况下，我的数据集将大于可用内存。那么，是否有任何数据结构可用于磁盘存储数据集上的最近邻？此操作的良好数据库索引也将很有用。

在模拟粒子相互作用时，我偶然发现了莫顿顺序（Z 顺序）（维基百科链接）的网格索引，它被认为可以提供有效的最近邻单元搜索。我读过的主要原因是内存中空间接近的单元的几乎顺序排序。

在第一次实现的过程中，我无法思考如何有效地实现最近邻居的算法，尤其是与基本的统一网格相比。

1. 给定一个单元格 (x,y)，获取 8 个相邻单元格索引并计算相应的 z 索引是很简单的。尽管这提供了对元素的恒定访问时间，但必须计算或在预定义的表中查找 z-index（每个轴和 OR'ing 分开）。这怎么可能更有效率？是否真的，按 A[0] -> A 1 -> A[3] -> A[4] -> ...的顺序访问数组 A 中的元素比按 A[1023 的顺序访问更有效] -> A[12] -> A[456] -> A[56] -> ...？

2. 我期望存在一种更简单的算法来以 z 顺序查找最近的邻居。类似的东西：找到邻居的第一个单元格，迭代。但这不可能是真的，因为这只能在 2^4 大小的块内很好地工作。但是有两个问题：当单元格不在边界上时，可以很容易地确定块的第一个单元格并遍历块中的单元格，但必须检查该单元格是否是最近邻。更糟糕的是，当单元格位于边界上时，必须考虑 2^5 个单元格。我在这里想念什么？是否有一种相对简单有效的算法可以满足我的需求？

第 1 点中的问题很容易测试，但我对所描述的访问模式生成的底层指令不是很熟悉，并且真的很想了解幕后发生的事情。

在此先感谢您的任何帮助、参考等...

关于第 2 点：我应该补充一点，我了解如何为 R^d 中的点云构建莫顿有序数组，其中索引 i = f(x1, x2, ..., xd) 是从逐位隔行扫描等获得的。我试图理解的是是否有比以下天真 ansatz 更好的方法来获取最近的邻居（这里在 d=2 中，“伪代码”）：

有人知道用 Python 实现的最近邻算法可以增量更新吗？我发现的所有这些，比如这个，似乎都是批处理。是否可以实现增量NN算法？