Neighbor Search più vicino in Python senza k-d tree

Question

Sto iniziando a imparare Python proveniente da uno sfondo C++. Quello che sto cercando è un modo facile e veloce per trovare il più vicino (il vicino più vicino) di qualche punto di query multidimensionale in una matrice 2D (numerica) di punti multidimensionali (anche array numpy). So che Scipy ha un albero k-d, ma non penso che questo sia ciò che voglio. Prima di tutto, cambierò i valori dei punti multidimensionali nell'array 2D. In secondo luogo, la posizione (coordinate) di ciascun punto nell'array 2D è importante, poiché cambierò anche i loro vicini.

Potrei scrivere una funzione che attraversa l'array 2D e misura la distanza tra il punto di query e i punti nell'array tenendo traccia di quella più piccola (utilizzando una funzione di distanza spaziale scipy per misurare la distanza). C'è una funzione integrata che fa questo? Sto cercando di evitare il più possibile l'iterazione su array in python. Avrò anche numerosi punti di interrogazione, quindi ci saranno almeno due "per loops": uno per scorrere i punti di query e per ogni query, un ciclo per scorrere l'array 2D e trovare la distanza minima.

Grazie per qualsiasi consiglio.

Answer 1

È possibile calcolare tutte le distanze scipy.spatial.distance.cdist(X, Y) o utilizzare RTree per dati dinamici: .

Answer 2

Se concisa è il vostro obiettivo, si può fare questo one-liner:

In [14]: X = scipy.randn(10,2) 

In [15]: X 
Out[15]: 
array([[ 0.85831163, 1.45039761], 
     [ 0.91590236, -0.64937523], 
     [-1.19610431, -1.07731673], 
     [-0.48454195, 1.64276509], 
     [ 0.90944798, -0.42998205], 
     [-1.17765553, 0.20858178], 
     [-0.29433563, -0.8737285 ], 
     [ 0.5115424 , -0.50863231], 
     [-0.73882547, -0.52016481], 
     [-0.14366935, -0.96248649]]) 

In [16]: q = scipy.array([0.91, -0.43]) 

In [17]: scipy.argmin([scipy.inner(q-x,q-x) for x in X]) 
Out[17]: 4 

Se si dispone di diversi punti di query:

In [18]: Q = scipy.array([[0.91, -0.43], [-0.14, -0.96]]) 

In [19]: [scipy.argmin([scipy.inner(q-x,q-x) for x in X]) for q in Q] 
Out[19]: [4, 9] 

Answer 3

Broadcasting è molto utile per questo genere di cose. Non sono sicuro se questo è ciò di cui hai bisogno, ma qui uso la trasmissione per trovare lo spostamento tra p (un punto nello spazio 3) e X (un set di 10 punti nel 3-spazio).

import numpy as np 

def closest(X, p): 
    disp = X - p 
    return np.argmin((disp*disp).sum(1)) 

X = np.random.random((10, 3)) 
p = np.random.random(3) 

print X 
#array([[ 0.68395953, 0.97882991, 0.68826511], 
#  [ 0.57938059, 0.24713904, 0.32822283], 
#  [ 0.06070267, 0.06561339, 0.62241713], 
#  [ 0.93734468, 0.73026772, 0.33755815], 
#  [ 0.29370809, 0.76298588, 0.68728743], 
#  [ 0.66248449, 0.6023311 , 0.76704199], 
#  [ 0.53490144, 0.96555923, 0.43994738], 
#  [ 0.23780428, 0.75525843, 0.46067472], 
#  [ 0.84240565, 0.82573202, 0.56029917], 
#  [ 0.66751884, 0.31561133, 0.19244683]]) 
print p 
#array([ 0.587416 , 0.4181857, 0.2539029]) 
print closest(X, p) 
#9 

Answer 4

Per una ricerca più veloce e il supporto per l'inserimento elemento dinamico, è possibile utilizzare un albero binario per gli elementi 2D in cui maggiore e minore di operatore è definito dalla distanza ad un punto di riferimento (0,0).

def dist(x1,x2): 
    return np.sqrt((float(x1[0])-float(x2[0]))**2 +(float(x1[1])-float(x2[1]))**2) 

class Node(object): 

    def __init__(self, item=None,): 
     self.item = item 
     self.left = None 
     self.right = None 

    def __repr__(self): 
     return '{}'.format(self.item) 

    def _add(self, value, center): 
     new_node = Node(value) 
     if not self.item: 
      self.item = new_node   
     else: 
     vdist = dist(value,center) 
     idist = dist(self.item,center) 
      if vdist > idist: 
       self.right = self.right and self.right._add(value, center) or new_node 
      elif vdist < idist: 
       self.left = self.left and self.left._add(value, center) or new_node 
      else: 
       print("BSTs do not support repeated items.") 

     return self # this is necessary!!! 

    def _isLeaf(self): 
     return not self.right and not self.left 

class BSTC(object): 

    def __init__(self, center=[0.0,0.0]): 
     self.root = None 
    self.count = 0 
    self.center = center 

    def add(self, value): 
     if not self.root: 
      self.root = Node(value) 
     else: 
      self.root._add(value,self.center) 
    self.count += 1 

    def __len__(self): return self.count 

    def closest(self, target): 
      gap = float("inf") 
      closest = float("inf") 
      curr = self.root 
      while curr: 
       if dist(curr.item,target) < gap: 
        gap = dist(curr.item, target) 
        closest = curr 
       if target == curr.item: 
        break 
       elif dist(target,self.center) < dist(curr.item,self.center): 
        curr = curr.left 
       else: 
        curr = curr.right 
      return closest.item, gap 


import util 

bst = util.BSTC() 
print len(bst) 

arr = [(23.2323,34.34535),(23.23,36.34535),(53.23,34.34535),(66.6666,11.11111)] 
for i in range(len(arr)): bst.add(arr[i]) 

f = (11.111,22.2222) 
print bst.closest(f) 
print map(lambda x: util.dist(f,x), arr)