问题标签 [nearest-neighbor]

在这里需要一些帮助。我是一名 UI 设计师，不擅长进行实验性 Web 表单设计的数字，我需要知道哪个输入元素最接近网页上的点击点。我知道如何用点做最近邻，但输入元素是矩形而不是点，所以我被卡住了。

我正在使用 jQuery。我只需要这个小算法的帮助。一旦我完成了我的实验，我会告诉你们我在做什么。

更新

我想过它是如何工作的。看这张图：

每个矩形有 8 个点（或者更确切地说是 4 个点和 4 条线），这些点很重要。只有 x 值对水平点（红点）有意义，只有 y 值对垂直点（绿点）有意义。x 和 y 对于角点都很重要。

橙色十字是要测量的点——在我的用例中是鼠标点击。浅紫色线是橙色十字和它可能最近的点之间的距离。

所以……对于任何给定的橙色十字架，遍历每个矩形的 8 个点中的每一个，以找到每个矩形最接近橙色十字架的边或角。具有最低值的矩形是最近的矩形。

我可以将其概念化和可视化，但无法将其放入代码中。帮助！

我正在寻找另一种算法：到最近邻问题的平均距离的免费 C/C++ 实现。

所以基本上我有一个 3D 点云，我想要所有点与其各自最近邻点之间距离的平均值。所以最简单的方法是为每个点找到最近的邻居，计算该邻居到该点的距离，然后将这些距离的总和除以点的数量。但是，还有更好的算法，因为它有很多冗余并且近似值运行得更快。我正在寻找那些更好算法的免费 C/C++ 实现。

一个 ε-Approximate 如果没问题。

我正在为非常稀疏的数据实现 K 最近邻算法。我想计算一个测试实例和训练集中每个样本之间的距离，但我很困惑。

因为训练样本中的大部分特征在测试实例中都不存在，反之亦然（缺失特征）。

在这种情况下如何计算距离？

我有一些低细节的图像要渲染到屏幕上。我使用位图作为缓冲区。有没有办法在.net 中重新调整位图的大小（使用“最近邻”）？

我使用的是 VB.net，所以所有 .net 解决方案都是可以接受的。

我有两组整数A和B（大小A小于或等于B），我想回答这个问题，“离 有多近A？B”。我想回答这个问题的方法是衡量你必须从一个给定a的 in走多远A才能找到一个bin B。

我想产生的具体措施如下：对于每个a，找到最接近b的，唯一的问题是一旦我将 ab与 an匹配a，我就不能再用它b来匹配任何其他a的了。（编辑：我试图实现的算法总是更喜欢较短的匹配。因此，如果b最近的邻居不止一个a，请选择a最接近的b。如果不止一个a具有相同的距离，我不确定该怎么办to b, 现在我正在选择a前面的b，但这是非常随意的，不一定是最佳的。）我将用于制作这些集合（最终产品）的度量是一个直方图，显示垂直轴上的对数和 x 轴上对的距离。

因此，如果A = {1, 3, 4}和B = {1, 5, 6, 7}，我将得到以下a,b对：1,1, 4,5, 3,6. 对于这些数据，直方图应显示距离为零的一对、距离为 1 的一对和距离为 3 的一对。

（这些集合的实际大小有大约 100,000 个元素的上限，我从已经从低到高排序的磁盘中读取它们。整数范围从 1 到 ~20,000,000。编辑：另外， 和 的元素A是B唯一的，即没有重复元素。）

我想出的解决方案感觉有点笨拙。我正在使用 Perl，但问题或多或少与语言无关。

1. 首先我做一个散列，对于出现在 和 的联合中的每个数字都有一个键，A并且B值指示每个数字是否出现在A、B或两者中，例如，$hash{5} = {a=>1, b=>1}如果数字 5 出现在两个数据集中。（如果它只出现在 中A，你就会有$hash{5} = {a=>1}。）

2. 接下来，我迭代A查找出现在Aand中的所有哈希元素，B在度量中标记它们，然后将它们从哈希中删除。

3. 然后，我对所有散列键进行排序，并使散列的每个元素指向其最近的邻居，就像一个链表，其中给定的散列元素现在看起来像$hash{6} = {b=>1, previous=>4, next=>8}. 链表不知道下一个和上一个元素是否在A或中B。

4. 然后我循环从 开始的对距离d=1，并找到所有具有距离的对d，标记它们，将它们从散列中删除，直到没有更多的元素A匹配。

循环如下所示：

这个循环显然更喜欢匹配b's 出现晚于a's; 的对。我不知道是否有一种明智的方法来决定以后是否比以前更好（在获得更接近的配对方面更好）。我感兴趣的主要优化是处理时间。

我正在寻找尽可能相似的动画系列照片。在研究时，我遇到了两种方法：

1. 生成图像的 pHash 并使用哈希的汉明距离做最近邻。
2. 创建颜色直方图并使用欧几里得距离做一个 n 维最近邻。

许多一直在评论https://stackoverflow.com/questions/6971966/how-to-measure-percentage-similarity-between-two-images问题的人声称这两个过程本质上是相同的。我正在寻找对此的更多见解。它们看起来像是不同的过程。

想法？

我知道从 Voronoi 镶嵌计算 k 最近邻的集合相对容易。反过来的问题呢？我已经有了一组 k 最近邻（3D），我想计算 Voronoi 单元的体积和中心。直观地说，应该有一个 O(n) 算法可以做到这一点，对吧？

有没有人在某处看到过这样的事情？

提前致谢

PS：我假设没有 Voronoi 单元的边数超过 k （这种关于点位置的先验知识可能使计算 O(n) 中的图表成为可能，与维度无关）。

PPS：我进一步假设对于给定的点，Voronoi 单元的顶点属于 kNN 的集合（见下面的评论）。

我有两个集合，A 和 B。这些集合由 N 个维度点组成并有序（N<10）。我需要找到 B 到 A 的最近部分。假设最近的部分是 B1。B1 中的点数应与 A 相同，且 B1 中所有点到 A 的距离之和应最小。

我检查了kd树。它只有助于在集合中找到最近的点。那么有没有一种算法可以快速找到最近的范围？

谢谢。

我对 k 最近邻分类器算法完全陌生。有人可以给我一个链接到一个很好的教程/讲座，它提供了一个数据集，以便我可以将 k-最近邻应用于它。

我真的真的需要学习这一点，但由于缺乏示例，这使得这项任务变得非常困难。

我已经成功编写了一个函数，该函数遍历 Kd-Tree 以获得点的最近单个邻居。

但是，我正在尝试切换此功能，以便它找到 K 近邻，而不仅仅是单个。事实证明，这比我最初想象的要艰巨得多，而且我发现自己需要一些帮助……

关于 kD-trees 的维基百科文章说：

该算法可以通过简单的修改以多种方式扩展。它可以通过保持 k 个当前最佳值而不是仅仅一个来为一个点提供 k 个最近邻。只有当它们的点不能比任何 k 当前最佳值更接近时，分支才会被消除。

...但它没有说明如何获得最初的当前最佳值。找到第一个“最佳”很简单，但我不知道如何在不删除以前的最佳并重新搜索的情况下找到其余的 k-current 最佳……这基本上违背了拥有一个快速算法，因为我必须做 k（在我的情况下，17）次。

如果我有一个包含 17 个初始“最佳”的填充列表，我相信我的算法会找到正确的点。

如果这含糊不清，我深表歉意。如果需要任何代码示例，我很乐意提供。虽然如果对这个问题有一个简单的解释，可能没有必要发布它，所以我一开始不会。

提前致谢！