識別具有最小歐幾里德距離的點

我有一個n維點的集合，我想找到哪個2最接近。我能想出的2個維的最好的是：識別具有最小歐幾里德距離的點

from numpy import * 
myArr = array([[1, 2], 
       [3, 4], 
       [5, 6], 
       [7, 8]]) 

n = myArr.shape[0] 
cross = [[sum((myArr[i] - myArr[j]) ** 2), i, j] 
     for i in xrange(n) 
     for j in xrange(n) 
     if i != j 
     ] 

print min(cross)

這給

[8, 0, 1]

但是，這是大型陣列太慢。我可以對其應用哪種優化？

來源

2011-02-25 Ηλίας

@Ηλίας很好地擴展：大約多少分你有嗎？請注意，可能有一組超過2點（甚至所有點）具有相同的距離（但不準確的計算可能不會反映這一點，所以最終您需要能夠設置閾值trh，其中trh以下的距離差爲視爲平等）。你沒有興趣找出最接近指定的點？ – eat 2011-02-25 20:31:43

@eat它是我正在構建的層次結構集羣，我需要找到兩個最接近的質心。通常不到一千分，但我需要看看它可以擴展多少。舍入錯誤對我來說不會那麼重要。 – 2011-02-25 20:57:38

嘗試scipy.spatial.distance.pdist(myArr)。這會給你一個壓縮的距離矩陣。您可以使用argmin並找到最小值的索引。這可以轉換成配對信息。

來源

2011-02-25 16:38:20 tkerwin

從這個單一的整數獲得這些座標最簡單的方法是什麼？ – 2011-02-25 18:58:26

@Ηίας如果*距離*包含上面* pdist *調用的結果，您可以使用'np.unravel_index（np.argmin（距離），距離。形狀）'。 – sffc 2015-06-19 00:53:47

它給了我一種肚子痛，使用這種方法在O（N^2）時間內找到最接近的對，因爲分而治之O（N log N）解決方案實際上是我在學校算法課中學到的第一個算法。但是這實現起來更容易，並且對於足夠小的設置來說它工作得很好。 – sffc 2015-06-19 00:56:33

有對剛纔這個問題整個維基百科頁面，請參閱：http://en.wikipedia.org/wiki/Closest_pair_of_points

內容提要：可以實現爲O（n log n）的一個遞歸除法和征服算法（在上面的Wiki頁面上概述）。

來源

2011-02-25 16:20:06 payne

整潔！我很高興在寫之前刷新：「顯然複雜度是O（n^2）」; o） – 2011-02-25 16:27:11

太好了。如果要連續添加點，並且要更新最小距離對，則保持Delaunay三角測量結構是有效的。 – 2011-02-25 16:28:17

它只是做一個嵌套的循環和跟蹤最短的對比較有多快？我認爲創建一個巨大的十字排列可能會傷害你。即使O（n^2）仍然非常快，如果你只做2維點。

來源

2011-02-25 16:24:21

它有幫助，但很快退化爲大型矩陣 – 2011-02-25 16:43:21

有一個SciPy的功能pdist，將讓你點之間的成對距離在一個陣列中的相當有效的方式：

http://docs.scipy.org/doc/scipy/reference/spatial.distance.html

輸出所述N *（N-1）/ 2的獨特對（因爲r_ij == r_ji）。然後您可以搜索最小值並避免代碼中的整個循環混亂。

來源

2011-02-25 16:37:34 JoshAdel

也許你可以沿着這些路線進行：

In []: from scipy.spatial.distance import pdist as pd, squareform as sf 
In []: m= 1234 
In []: n= 123 
In []: p= randn(m, n) 
In []: d= sf(pd(p)) 
In []: a= arange(m) 
In []: d[a, a]= d.max() 
In []: where(d< d.min()+ 1e-9) 
Out[]: (array([701, 730]), array([730, 701]))

與你需要能夠以某種方式利用自己的集羣的層次結構，大體上分以上。

來源

2011-02-25 21:09:18 eat

您可以利用最新版本的SciPy（v0.9）Delaunay三角測量工具。你可以確定最接近的兩個點將是三角形中單形的邊，這是一個小得多的子集，而不是每個組合。

這裏的（更新的一般ND）代碼：

import numpy 
from scipy import spatial 

def closest_pts(pts): 
    # set up the triangluataion 
    # let Delaunay do the heavy lifting 
    mesh = spatial.Delaunay(pts) 

    # TODO: eliminate reduncant edges (numpy.unique?) 
    edges = numpy.vstack((mesh.vertices[:,:dim], mesh.vertices[:,-dim:])) 

    # the rest is easy 
    x = mesh.points[edges[:,0]] 
    y = mesh.points[edges[:,1]] 

    dists = numpy.sum((x-y)**2, 1) 
    idx = numpy.argmin(dists) 

    return edges[idx] 
    #print 'distance: ', dists[idx] 
    #print 'coords:\n', pts[closest_verts] 

dim = 3 
N = 1000*dim 
pts = numpy.random.random(N).reshape(N/dim, dim)

密切似乎爲O（n）：

enter image description here

來源

2011-02-25 21:23:44 Paul

可能實際上在2D中工作。你有沒有做任何時機？然而這種方法在較暗的模糊中失敗了。謝謝 – eat 2011-02-25 21:31:09

@eat：你爲什麼說它「失敗慘痛」？ 3D比2D中的相同N慢4-5倍。但任何方法（除了天真的蠻力方法）都會看到D變慢。 – Paul 2011-02-25 21:56:37

那麼，嘗試在123D中做Delaunay三角測量是沒有意義的！所以這不會解決OP的問題（除非他的nD是2或3）。不要誤解我的意思，我真的很高興scipy能夠快速執行Delaunay三角測量。請使用'pdist'爲n = 2 ... 123進行一些計時，您會看到。謝謝 – eat 2011-02-25 22:16:06

接受的答案是小型數據集行，但它的執行時間規模爲n**2。但是，正如@payne指出的那樣，最佳解決方案可以實現計算時間縮放。

該操作解決方案可以使用sklearn.neighbors.BallTree獲得，如下所示。

import matplotlib.pyplot as plt 
import numpy as np 
from sklearn.neighbors import BallTree as tree 

n = 10 
dim = 2 
xy = np.random.uniform(size=[n, dim]) 

# This solution is optimal when xy is very large 
res = tree(xy) 
dist, ids = res.query(xy, 2) 
mindist = dist[:, 1] # second nearest neighbour 
minid = np.argmin(mindist) 

plt.plot(*xy.T, 'o') 
plt.plot(*xy[ids[minid]].T, '-o')

此過程很好地擴展爲非常大的集xy值，甚至可用於大尺寸dim（altough該示例示出的情況下dim=2）。所得到的輸出是這樣的

可使用scipy.spatial.cKDTree獲得的相同的溶液中，通過與以下SciPy的一個替換sklearn導入。但是請注意，cKDTree，不像BallTree，不會爲高維

from scipy.spatial import cKDTree as tree

來源

2017-09-07 14:56:00 divenex

識別具有最小歐幾里德距離的點

回答

相關問題