问题标签 [nearest-neighbor]

我是 Postgres 和 SQL 的新手。我创建了以下脚本，该脚本从一个点到最近线上的投影点绘制一条线。它适用于具有相同行数的 5 到 10 个点的小型数据集；但是，在 2,000 行的 60 个点上进行查询，大约需要 12 个小时。它基于粘贴在下面的最近邻函数以及来自http://www.bostongis.com/downloads/pgis_nn.txt

http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_nearest_neighbor_generic上提供了关于 pgis_fn_nn 的EDIT文档

缓慢的部分是 pgis_fn_nn(...)

1. 我究竟做错了什么？
2. 有什么技巧可以让这更快吗？
3. 有没有办法可以改进这两个脚本？
4. 如果我想将两个查询合并为一个，您会推荐什么？

my_script.sql

pgis_fn_nn来自http://www.bostongis.com/downloads/pgis_nn.txt

我正在尝试编写自己的函数来使用最近邻插值算法来放大输入图像。不好的部分是我能够看到它是如何工作的，但找不到算法本身。我将不胜感激任何帮助。

这是我尝试将输入图像放大 2 倍的方法：

这是Mark建议后的输出

我可以使用中位数选择算法的中位数来找到 O(n) 中的中位数。另外，我知道算法完成后，中位数左侧的所有元素都小于中位数，右侧的所有元素都大于中位数。但是如何在 O(n) 时间内找到离中位数最近的 k 个邻居？

如果中位数为n，则左边的数字小于n，右边的数字大于n。但是，数组不是在左侧或右侧排序的。这些数字是用户给出的任何一组不同的数字。

问题来自 Cormen 的算法介绍，问题 9.3-7

在 kd 树的wikipedia 条目中，提出了一种算法，用于在 kd 树上进行最近邻搜索。我不明白的是步骤3.2的解释。仅仅因为搜索点的分裂坐标与当前节点的差值大于搜索点的分裂坐标与当前最佳点的差值，你怎么知道没有更近的点呢？

最近邻搜索 使用二维 KD 树进行 NN 搜索的动画

最近邻（NN）算法旨在找到树中最接近给定输入点的点。这种搜索可以通过使用树属性快速消除大部分搜索空间来有效地完成。在 kd-tree 中搜索最近邻的过程如下：

1. 从根节点开始，算法递归地向下移动树，与插入搜索点的方式相同（即它向右或向左移动取决于该点是否大于或小于当前节点。分割维度）。
2. 一旦算法到达叶节点，它将该节点点保存为“当前最佳”
3. 该算法展开树的递归，在每个节点执行以下步骤： 1. 如果当前节点比当前最佳节点更接近，则它成为当前最佳节点。2. 算法检查分割平面的另一侧是否有任何点比当前最佳点更靠近搜索点。从概念上讲，这是通过将分割超平面与搜索点周围的超球面相交来完成的，该超球面的半径等于当前最近的距离。由于超平面都是轴对齐的，因此这是一个简单的比较，以查看搜索点和当前节点的分割坐标之间的差异是否小于搜索点到当前最佳点的距离（整体坐标）。1. 如果超球面穿过平面，则平面的另一侧可能有更近的点，因此算法必须从当前节点向下移动树的另一个分支以寻找更近的点，遵循与整个搜索相同的递归过程. 2. 如果超球面不与分裂平面相交，则算法继续向上走，并且该节点另一侧的整个分支被消除。
4. 当算法完成对根节点的这个过程时，搜索就完成了。

通常，该算法使用平方距离进行比较以避免计算平方根。此外，它可以通过将平方当前最佳距离保存在变量中进行比较来节省计算量。

我一直在考虑构建一个“喜欢 x 的人，也喜欢 y”类型的推荐系统，并且正在考虑使用 Vogoo，但是在查看了他们的代码之后，似乎有很多基于评级的最近邻。

在过去的几周里，我看到一些文章说大多数人要么根本不评分，要么评分 5 http://youtube-global.blogspot.com/2009/09/five-stars-dominate-评级.html

我目前没有实施评级系统，如果所有适用的评级都没有波动，我真的不认为有必要实施它。

这是否意味着 KNN 并不真正有价值？

有没有人有任何建议开发一个系统来根据过去的观看历史（被动过滤）获得相似的推荐？

我正在使用的数据是基于事件的，所以如果你看过男子双打网球、蓝鸟棒球、大学女子篮球等。我会推荐目前在你所在地区的其他活动，其他人看过在整个系统的类似事件中也看过。

我主要使用 PHP，但已经开始学习 Python（如果有帮助，可能还需要学习 Java）。

为了找到最近的邻居，空间分区是算法之一。它是如何工作的？

假设我有一组 2D 点（x 和 y 坐标），并且给定一个点 (a,b)。这个算法如何找到最近的邻居？

我没有插值的纯代码：

这段代码产生了黑点，问题是如何进行插值？谢谢大家的任何启发。PS 不要求内置函数：imrotate(im1,1/thet,'nearest');

这是在 C 中。

我有两个二维数组 ArrayA 和 ArrayB，它们对相同的空间进行采样。B 对与 ArrayA 不同的属性进行采样的频率低于 ArrayA，因此它比 A 小。

只是想尝试定义一些变量： ArrayA：SizeAX 按 SizeAY，由 indexA 索引，用于位置 posAX，posAY ArrayB：SizeBX，按 SizeAY，由 indexB 索引，用于位置 posBX，posBY

ArrayA 和 ArrayB 是指向数组开头的指针，其中先存储 X 的行，然后递增 Y，然后存储下一行 X（Y=1）

所以我需要从给定的 indexA 设置 indexB，使其成为最近邻样本，以与 indexA 的值相关联。

这是我所在的位置（请更正任何错误！请注意，我从索引 0 开始）：如果 ArrayA 是 9x9 而 ArrayB 是 3x3： (posX,posY) posA 0,0; indexA = 0 posB 0,0; 指数B = 0

POSA 8,0; indexA = 8（第一行结束）posB 2,0；指数B = 2

位置 0,1; indexA = 9 posB 0,0; indexB = 0（仍然更接近底部点）

位置 0,3; indexA = 27 posB 0,1；指数B = 3

POSA 8,8; indexA = 80（最后一点）posB 2,2；指数B = 8

到目前为止我有： indexA = posAX + (posAY * SizeAX)

我尝试过的（当然失败了）： indexB = (int) (indexA * (SizeBX * SizeBY / (SizeAX * SizeAY)) + 0.5) // 似乎只适用于第一行和最后一个值.. 但是这显然是行不通的——但我很好奇它是如何将两者映射在一起的，但我会在修复它后研究它。

我无法访问 posAY 或 posAX，只能访问 indexA，但我应该能够使用 mod 和余数将其分解，对吧？还是有更有效更快的方法？一个

我也试过这个：

indexB = (posAY * SizeBY / SizeAY) * SizeBY + (posAX * SizeBX / SizeAX)

我认为问题是我需要将 X 和 Y 索引分开，然后再使用 SizeBX 和 SizeBY ？

一个额外的警告是 ArrayA 和 ArrayB 来自更大的数据集，它们都对更大的空间进行采样。由于矩形是任意的，因此 ArrayA 或 ArrayB 可能具有最接近矩形边界的点，从而导致其他问题，即最近邻居真正抓取的方式。我也不确定如何解决这个问题。

我必须在 kd-tree 中实现 k 个最近邻搜索 10 维数据。

但问题是我的算法对于 k=1 非常快，但对于 k>1 (k=2,5,10,20,100) 慢 2000 倍

这对 kd 树来说是正常的，还是我在做一些磨损的事情？

用例示例：客户 A 来请求销售信息，输入他们的邮政编码并被定向到代表 X。

由于实际上存在无限数量的邮政编码，因此不会为每个邮政编码分配一个代理，然后将其转移到县级，然后进入县级区域，最后在州级结束。

哪种类型的关系最适合对这种情况进行建模？

有没有办法消除需要专门定义邮政编码可以近似于分配代表的最近县的区域，如果是这样，只有通过完整的地理位置查找才能进行距离比较以找到最近的代表或也许邮政编码本身可以用来近似距离？

澄清： 这个问题的真正意图是如何解决区域近似而不需要维护县与区域的完美关联表，或者这个问题的解决方案是否如此复杂以至于手动维护关系的成本不那么令人望而却步？