标签: nearest-neighbor

所以我有大约16,000个75维数据点,并且对于每个点我想找到它的k个最近邻居(使用欧氏距离,如果这使得它更容易,则当前k = 2)

我的第一个想法是为此使用kd树,但事实证明,随着维数的增长,它们变得相当低效.在我的示例实现中,它仅比详尽的搜索稍快.

我的下一个想法是使用PCA(主成分分析)来减少维数,但我想知道:是否有一些聪明的算法或数据结构可以在合理的时间内完全解决这个问题？

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

更新:太空是欧几里得,对不起.并感谢所有的答案.顺便说一句,这不是功课.

我有一个大约100,000(X,Y)对的数据集,代表2D空间中的点.对于每一点,我想找到它的k-最近邻居.

所以,我的问题是 - 假设我想绝对最小化整体运行时间,那么什么数据结构/算法将是一个合适的选择？

我不是在寻找代码 - 只是指向合适方法的指针.我有点害怕看似相关的选择 - 四棵树,R树,kd树等.

我认为最好的方法是构建一个数据结构,然后为每个点运行某种k-Nearest Neighbor搜索.但是,由于(a)我事先知道了这些要点,并且(b)我知道我必须对每个点进行一次搜索,或许有更好的方法？

一些额外的细节:

• 由于我想最小化整个运行时间,我不在乎大部分时间花在结构与搜索上.
• (X,Y)对分布相当均匀,因此我们可以假设几乎均匀分布.

我有一个像这样的numpy数组:

x = np.array([[1,2,3],[4,5,6],[7,8,9]])

我需要创建一个函数让我们用以下输入参数称它为"邻居":

• x:一个numpy 2d数组
• (i,j):2d数组中元素的索引
• d:邻域半径

作为输出,我想获得i,j具有给定距离的单元的邻居d.所以,如果我跑

neighbors(im, i, j, d=1) with i = 1 and j = 1 (element value = 5) 

我应该得到以下值的索引:[1,2,3,4,6,7,8,9].我希望我说清楚.是否有像scipy这样的库来解决这个问题？

我做了一些工作,但这是一个粗略的解决方案.

def pixel_neighbours(self, p):

    rows, cols = self.im.shape

    i, j = p[0], p[1]

    rmin = i - 1 if i - 1 >= 0 else 0
    rmax = i + 1 if i + 1 < rows else i

    cmin = j - 1 if j - …

我有一个大的x和y坐标列表,存储在一个numpy数组中.

Coordinates = [[ 60037633 289492298]
 [ 60782468 289401668]
 [ 60057234 289419794]]
...
...

我想要的是找到特定距离内的所有最近邻居(比如3米)并存储结果,以便我以后可以对结果进行进一步的分析.

对于大多数包裹,我发现有必要确定应该找到多少个NN,但我只想在设定的距离内完成所有NN.

我怎样才能实现这样的目标？什么是实现大型数据集(百万点)的最快和最好的方法？

我有一个我需要使用的自定义距离指标KNN,K Nearest Neighbors.

我试着遵循这个,但我不能因为某些原因让它工作.

我假设距离度量应该采用两个相同长度的向量/数组,如下所述:

import sklearn 
from sklearn.neighbors import NearestNeighbors
import numpy as np
import pandas as pd

def d(a,b,L):
    # Inputs: a and b are rows from a data matrix   
    return a+b+2+L

knn=NearestNeighbors(n_neighbors=1,
                 algorithm='auto',
                 metric='pyfunc',
                 func=lambda a,b: d(a,b,L)
                 )


X=pd.DataFrame({'b':[0,3,2],'c':[1.0,4.3,2.2]})
knn.fit(X)

但是,当我调用:时knn.kneighbors(),它似乎不喜欢自定义函数.这是错误堆栈的底部:

ValueError: Unknown metric pyfunc. Valid metrics are ['euclidean', 'l2', 'l1', 'manhattan', 'cityblock', 'braycurtis', 'canberra', 'chebyshev', 'correlation', 'cosine', 'dice', 'hamming', 'jaccard', 'kulsinski', 'mahalanobis', 'matching', 'minkowski', 'rogerstanimoto', 'russellrao', 'seuclidean', 'sokalmichener', …

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

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

问题来自Cormen的算法导论,问题9.3-7

我的普通代码没有插值:

im1 = imread('lena.jpg');imshow(im1);    
[m,n,p]=size(im1);
thet = rand(1);
m1=m*cos(thet)+n*sin(thet);
n1=m*sin(thet)+n*cos(thet);    

for i=1:m
    for j=1:n
       t = uint16((i-m/2)*cos(thet)-(j-n/2)*sin(thet)+m1/2);
       s = uint16((i-m/2)*sin(thet)+(j-n/2)*cos(thet)+n1/2);
       if t~=0 && s~=0           
        im2(t,s,:)=im1(i,j,:);
       end
    end
end
figure;
imshow(im2);

这段代码会产生黑点,问题是如何进行插值？谢谢大家的任何照明.PS不要求内置函数:imrotate(im1,1/thet,'nearest');

我目前正在尝试找到平衡KD树的所有节点的K最近邻(K = 2).

我的实现是来自维基百科文章的代码的变体,并且找到任何节点O(log N)的 KNN都非常快.

问题在于我需要找到每个节点的 KNN . 如果我遍历每个节点并执行搜索,则计算大约O(N log N).

有没有更有效的方法来做到这一点？

我在PostGIS中使用以下最近邻查询:

SELECT g1.gid g2.gid FROM points as g1, polygons g2   
WHERE g1.gid <> g2.gid
ORDER BY g1.gid, ST_Distance(g1.the_geom,g2.the_geom)
LIMIT k;

现在,我已经在两个表上的the_geom和gid列上创建了索引,这个查询所花费的时间比涉及空间连接的其他空间查询要多两个表.

有没有更好的方法找到K-最近邻居？我正在使用PostGIS.

而且,尽管在几何列上创建了索引,但另一个查询占用了异常长的时间:

select g1.gid , g2.gid from polygons as g1 , polygons as g2
where st_area(g1.the_geom) > st_area(g2.the_geom) ;

我相信,这些查询并没有受到主要指标的影响,但为什么呢？

鉴于此查询:

select a.polyid , sum(length(b.the_geom)) from polygon as a , roads as b  
where st_intersects(a.the_geom , b.the_geom);

尽管涉及比"多边形"或"点"表大得多的"道路"表并且还涉及更复杂的空间算子,但是在一段时间之后返回结果.