En küçük Euclidean mesafesi olan noktaları belirleme

Question

N boyutlu noktalar koleksiyonuna sahibim ve en çok hangi 2'yi bulmak istiyorum. Ben 2 boyutları için gelebilir en iyisi:

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] 

veren Ama bu büyük diziler için çok yavaş. Ne tür bir optimizasyon uygulayabilirim?

İLGİLİ: Bir özyinelemeli ile size O elde edebilirsiniz (n log): http://en.wikipedia.org/wiki/Closest_pair_of_points

Yönetici özeti:

---

Euclidean distance between points in two different Numpy arrays, not within

Answer 1

scipy.spatial.distance.pdist(myArr)'u deneyin. Bu size yoğun bir mesafe matrisi verecektir. Üzerinde argmin kullanabilir ve en küçük değerin indeksini bulabilirsiniz. Bu, çift bilgisine dönüştürülebilir.

Answer 2

, bkz sadece bu sorun üzerinde bir bütün Vikipedi sayfası var bölün ve algoritmayı fethet (yukarıda Wiki sayfasında özetlenen).

Answer 3

Sadece yuvalanmış bir döngü yapmak ve en kısa çifti takip etmekle karşılaştırıldığında ne kadar hızlı? Büyük bir çapraz dizi yaratmanın seni incitebileceğini düşünüyorum. Sadece 2 boyutlu puan yapıyorsanız bile O (n^2) hala oldukça hızlıdır.

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

K * (N-1)/2 benzersiz verir:

Answer 4

oldukça verimli bir şekilde bir dizi içinde noktalar arasındaki ikili mesafeler alacak scipy fonksiyonu pdist yoktur çiftleri (r_ij == r_ji'den beri). Daha sonra minimum değeri arayabilir ve kodunuzdaki tüm döngü karmaşasından kaçabilirsiniz.

Answer 5

Belki bu satırlar boyunca devam olabilir:

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])) 

nasılsa senin kümeleme hiyerarşik yapısını kullanmak gerekiyor ölçüde daha fazla puan ile.

Answer 6

SciPy'nin (v0.9) Delaunay üçgenleme araçlarının en son sürümlerinden yararlanabilirsiniz. En yakın iki noktanın, her kombinasyonun yapılmasından çok daha küçük bir çift alt kümesi olan üçgenlemede bir simpleksin kenarı olacağından emin olabilirsiniz.

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) 

(n) yakından O görünüyor:

Answer 7

kabul cevap, küçük veri setleri için sorun yok ama onun yürütme zamanı İşte

(genel ND güncellenir) kod n**2 olarak ölçeklendirir. Ancak, @payne tarafından işaret edildiği gibi, optimal bir çözüm, n*log(n) hesaplama zaman ölçeklendirmesi elde edebilir.

Bu optik çözüm, sklearn.neighbors.BallTree kullanılarak aşağıdaki gibi elde edilebilir.

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') 

Bu prosedür de xy değerleri çok büyük kümeler ve hatta (örneğin durum dim=2 göstermektedir halde) büyük boyutlu dim için ölçekler. Elde edilen çıkış aşağıdaki scipy bir ile sklearn içe değiştirerek, özdeş bir çözelti scipy.spatial.cKDTree kullanılarak elde edilebilir, bu

gibi görünüyor. cKDTree, BallTree aksine

Ηλίας @

from scipy.spatial import cKDTree as tree