问题标签 [nearest-neighbor]

我有一个表（DB2 数据库），其中包含城市信息和相应的纬度和经度以及与城市相关的许多其他信息。我的要求是：

我的应用程序的输入将是纬度和经度，它们可能或许多不是存储在数据库中的精确纬度和经度。我需要在输入纬度和经度的帮助下从表中找到最近的城市信息。非常感谢任何帮助。

java中是否有可用的最近邻实现或SQL来处理这个

如果想使用 K-nearest-neighbors 算法对图像进行分类，如何从图像中提取特征？什么是最简单、最有效的方法？

人们总是吹捧KD树非常适合最近邻搜索。但是，如果您的数据集都是离散值，没有真正的距离度量，它们仍然有效吗？

例如，如果您的属性类似于[black, blue, red], [bread, milk, cheese], [right, left, straight, curved]没有连续性，并且测量距离的唯一方法是汉明距离（我们检查有多少与测试示例等效）。KD树在这些情况下仍然有效吗？怎么来的？

我正在查看 KD 树的 Wikipedia 页面。例如，我在 python 中实现了用于构建列出的 kd 树的算法。

然而，使用 KD 树进行 KNN 搜索的算法会切换语言并且并不完全清楚。英文解释开始有意义，但其中的一部分（例如他们“展开递归”以检查其他叶节点的区域）对我来说并没有任何意义。

这是如何工作的，如何在 python 中使用 KD 树进行 KNN 搜索？这不是一个"send me the code!"类型问题，我不希望这样。请简单解释一下:)

我有一组格式如下的数据：

日期/时间 | 纬度 | 经度 | 身高 | 温度

用户可以根据不同空间和时间的大气温度测量值输入这些数据。空间由纬度、经度和高度表示。现在从这组数据中，我必须通过插值。我不确定在这种情况下我必须使用什么样的数据结构。我读过Kd-tree，这是一个选项吗？

我在二维平面上有一组具有给定位置和半径的圆。我想确定每个圆是否与任何其他圆相交以及将两者分开所需的距离。在我目前的实现中，我只是遍历所有可能的圆圈组合，然后进行计算。不幸的是，这个算法是 O(n^2)，速度很慢。

这些圆通常会成组聚集，并且它们将具有相似（但不同）的半径。圈数的近似最大值约为 200。该算法不必精确，但应该接近。

这是我目前在 JavaScript 中的一个（慢）实现：

另外，如果您用简单的英语解释一个好的算法（KD 树？），我将不胜感激：-/

给定一个四元数，我想在一组四元数中找到它最近的邻居。为此，我显然需要一种方法来比较两个四元数之间的“距离”。这种比较需要什么距离表示，它是如何计算的？

谢谢，

乔什

我需要在一组点中找到“近”邻居。

上图中有 10 个点。红线是Delaunay 三角剖分的边缘，黑色星星标记边缘的中线，蓝线是Voronoi 镶嵌。点 1 有 3 个“近”邻居，即 4、6 和 7，但不是 2 和 3，它们几乎与边缘 1-7 一致，但距离更远。

什么是识别近邻（或“好”边缘）的好方法？看这个图，在我看来，要么选择中点落在与 Voronoi 线相交的边缘，要么将那些与 Voronoi 细胞接触的边缘视为“近”邻居，这可能是一个很好的解决方案（3-5 的分类）可以去任何一种方式）。是否有一种在 Matlab 中实现任一解决方案的有效方法（我很高兴得到一个好的通用算法，然后我可以将其转换为 Matlab，顺便说一句）？

因此，我正在尝试查找有关 Michael Rabin 算法的详细信息，该算法在 O(n) 时间内给定一组 2D 点找到最近邻。出于某种原因，谷歌搜索完全让我失望。我找到的最好的（也是唯一的）描述在这里：http ://rjlipton.wordpress.com/2009/03/01/rabin-flips-a-coin/ 。

如果有人对此有所了解，或者知道在哪里可以找到有关该主题的书籍或论文（最好是在线的！），我非常感谢您参与进来。

我想我知道如何使用 Cover Trees 做 K-Nearest-Neighbors。（顺便说一句：有人可以指出我对此的运行时复杂性分析吗？），但我正在寻找全kNN（即：找到树中所有点的kNN）。