Vecino más cercano Buscar en Python sin árbol k-d

Question

Estoy empezando a aprender Python proveniente de un fondo de C++. Lo que estoy buscando es una forma rápida y fácil de encontrar el punto más cercano (vecino más cercano) de un punto de consulta multidimensional en una matriz 2D (numpy) de puntos multidimensionales (también matrices numpy). Sé que Scipy tiene un árbol k-d, pero no creo que esto sea lo que quiero. En primer lugar, voy a cambiar los valores de los puntos multidimensionales en la matriz 2D. En segundo lugar, la posición (coordenadas) de cada punto en la matriz 2D importa ya que también cambiaré sus vecinos.

Podría escribir una función que atraviese la matriz 2D y mida la distancia entre el punto de consulta y los puntos en la matriz mientras sigo la pista del más pequeño (utilizando una función de distancia espacial scipy para medir la distancia). ¿Hay una función incorporada que hace esto? Estoy tratando de evitar iterar sobre las matrices en Python tanto como sea posible. También tendré numerosos puntos de consulta, por lo que habría al menos dos "bucles for": uno para recorrer los puntos de consulta y para cada consulta, un bucle para iterar a través de la matriz 2D y encontrar la distancia mínima.

Gracias por cualquier consejo.

Answer 1

Puede calcular todas las distancias scipy.spatial.distance.cdist(X, Y) o utilizar RTree para datos dinámicos: .

Answer 2

Si concisa es su meta, usted puede hacer esto de una sola línea:

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 

Si tiene varios puntos de consulta:

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

radiodifusión es muy útil para este tipo de cosas. No estoy seguro de si esto es lo que necesita, pero aquí uso la radiodifusión para encontrar el desplazamiento entre p (un punto en 3 espacios) y X (un conjunto de 10 puntos en 3 espacios).

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

Para la búsqueda más rápida y soporte para la inserción elemento dinámico, se puede utilizar un árbol binario para los elementos 2D en el que más y menos del operador se define por la distancia a un punto de referencia (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)