标签: nearest-neighbor

我有一个数据库,我希望使用单个查询找出按ID排序的上一个和下一个记录.我试图做一个联盟,但这不起作用.:(

SELECT * FROM table WHERE `id` > 1556 LIMIT 1
UNION 
SELECT * FROM table WHERE `id` <1556 ORDER BY `product_id` LIMIT 1

有任何想法吗？非常感谢.

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

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

UPDATE

我想过它是如何工作的.看看这个图:

每个矩形有8个点(或者更确切地说是4个点和4个线),这些点是重要的.只有x值对于水平点(红点)才有意义,只有y值对于垂直点(绿点)才有意义.x和y都是角落的重要部分.

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

因此......对于任何给定的橙色十字,循环遍历每个矩形的8个点中的每一个,以找到每个矩形最接近橙色十字的最近边或角.具有最低值的矩形是最近的矩形.

我可以概念化和可视化它,但不能把它放入代码中.救命!

假设我们有两组点A,B,并且我们想要找到集合A中每个点,它们是集合B中的最近邻居.

有很多好的算法可以找到一个点的最近邻居.有没有办法使用我们为a_1获得的信息,更有效地搜索a_2的最近邻居或集合中的其他点？

我想的是:使用三角不等式来获得B中每个点与新点a_2之间可能距离的间隔,并对间隔的最大值和最小值进行排序,然后我只能搜索B中落入的点.第一个间隔.

在哪里可以找到k-最近邻算法的串行C/C++实现？
你知道有这个库吗？
我找到了openCV,但实现已经并行了.
我想从串行实现开始,并使用pthreads openMP和MPI并行化.

谢谢,
亚历克斯

是否有一个数据库支持高维向量空间中的快速近似最近邻查询？

我正在寻找一个适合以下用例的数据库:

• 适用于数百万点
• 适用于数十万个维度
• 可能使用覆盖树或局部敏感散列来进行索引

是否存在强有力的实现？

如果我在2D空间中有一组N个点,由它们位置的向量X和Y定义.什么是有效的算法

1. 选择要删除的固定数量(M)点,以便最大化剩余点之间的最短最近邻距离.
2. 移除最小数量的点,以使剩余点之间的最短最近邻距离大于固定距离(D).

按点按最短的最近邻距离进行排序并删除具有最小值的点不会给出正确的答案,因为您删除了两个紧密对的点,而您可能只需要删除这些对中的一个点.

对于我的情况,我通常处理1,000-10,000点,我可以删除50-90%的积分.

这是一个与https://stats.stackexchange.com/questions/21572/how-to-plot-decision-boundary-of-ak-nearest-neighbor-classifier-from-elements-o相关的问题

为了完整起见,这是该链接的原始示例:

library(ElemStatLearn)
require(class)
x <- mixture.example$x
g <- mixture.example$y
xnew <- mixture.example$xnew
mod15 <- knn(x, xnew, g, k=15, prob=TRUE)
prob <- attr(mod15, "prob")
prob <- ifelse(mod15=="1", prob, 1-prob)
px1 <- mixture.example$px1
px2 <- mixture.example$px2
prob15 <- matrix(prob, length(px1), length(px2))
par(mar=rep(2,4))
contour(px1, px2, prob15, levels=0.5, labels="", xlab="", ylab="", main=
        "15-nearest neighbour", axes=FALSE)
points(x, col=ifelse(g==1, "coral", "cornflowerblue"))
gd <- expand.grid(x=px1, y=px2)
points(gd, pch=".", cex=1.2, col=ifelse(prob15>0.5, "coral", "cornflowerblue"))
box()

我一直在玩这个例子,并希望尝试使用三个类.我可以用类似的东西改变g的某些值

g[8:16] <- 2

只是假装有一些来自第三类的样本.但是,我不能让情节有效.我想我需要改变处理获胜类别投票比例的线:

prob <- attr(mod15, "prob")
prob <- …

我想检索另一组点的给定范围内的所有点.比方说,找到距离任何地铁站500米范围内的所有商店.

我写了这个查询,这很慢,并且想要优化它:

SELECT DISCTINCT ON(locations.id) locations.id FROM locations, pois
WHERE pois.poi_kind = 'subway'
AND ST_DWithin(locations.coordinates, pois.coordinates, 500, false);

我正在使用最新版本的Postgres和PostGis(Postgres 9.5,PostGis 2.2.1)

这是表元数据:

                                         Table "public.locations"
       Column       |            Type             |                       Modifiers
--------------------+-----------------------------+--------------------------------------------------------
 id                 | integer                     | not null default nextval('locations_id_seq'::regclass)
 coordinates        | geometry                    |
Indexes:
    "locations_coordinates_index" gist (coordinates)


                                      Table "public.pois"
   Column    |            Type             |                     Modifiers
-------------+-----------------------------+---------------------------------------------------
 id          | integer                     | not null default nextval('pois_id_seq'::regclass)
 coordinates | geometry                    |
 poi_kind_id | integer                     |
Indexes:
    "pois_pkey" PRIMARY KEY, btree (id)
    "pois_coordinates_index" gist (coordinates)
    "pois_poi_kind_id_index" …

我想使用Postgres对地址进行一些基本的地理编码.我有一个地址表,有大约100万个原始地址字符串:

=> \d addresses
  Table "public.addresses"
 Column  | Type | Modifiers
---------+------+-----------
 address | text |

我还有一张位置数据表:

=> \d locations
   Table "public.locations"
   Column   | Type | Modifiers
------------+------+-----------
 id         | text |
 country    | text |
 postalcode | text |
 latitude   | text |
 longitude  | text |

大多数地址字符串包含邮政编码,所以我的第一次尝试是做类似和横向连接:

EXPLAIN SELECT * FROM addresses a
JOIN LATERAL (
    SELECT * FROM locations
    WHERE address ilike '%' || postalcode || '%'
    ORDER BY LENGTH(postalcode) DESC
    LIMIT 1
) AS l ON …

我在获取pandas数据框中某些行的最近值并用这些行中的值填充另一列时遇到问题。

我有数据样本：

id   su_id  r_value  match_v

A      A1      0        1
A      A2      0        1
A      A3      70       2
A      A4      120      100
A      A5      250      3
A      A6      250      100
B      B1      0        1
B      B2      30       2

关键是，无论哪里match_v等于100，我都需要将其替换为最接近原始行（其中等于）100的行中的值，而只是将组（按id分组）r_valuer_valuematch_v100

预期产量

id   su_id  r_value  match_v

A      A1      0        1
A      A2      0        1
A      A3      70       2
A      A4      120      2
A      A5      250      3
A      A6      250      3
B      B1 …