Nächste Nachbar Suche in Python ohne Kd Baum

Ich beginne zu lernen, Python aus einem C ++ – Hintergrund zu kommen. Was ich suche, ist eine schnelle und einfache Möglichkeit, den nächstgelegenen (nächsten Nachbarn) eines multidimensionalen Abfragepunktes in einem 2D (numpy) Array von multidimensionalen Punkten (auch numpy Arrays) zu finden. Ich weiß, dass scipy hat einen kd Baum, aber ich glaube nicht, das ist, was ich will. Zuerst werde ich die Werte der multidimensionalen Punkte im 2D-Array ändern. Zweitens ist die Position (Koordinaten) jedes Punktes im 2D-Array wichtig, da ich auch ihre Nachbarn ändern werde.

Ich könnte eine Funktion schreiben, die durch das 2D-Array geht und den Abstand zwischen dem Abfragepunkt und den Punkten im Array misst, während er die kleinste Spur hinterlässt (mit einer scipy räumlichen Distanzfunktion, um den Abstand zu messen). Gibt es eine eingebaute Funktion, die das tut? Ich versuche zu vermeiden, über Arrays in Python so viel wie möglich zu vermeiden. Ich werde auch viele Abfragepunkte haben, also würde es mindestens zwei "für Loops" geben – eine, um durch die Abfragepunkte zu iterieren und für jede Abfrage eine Schleife, um durch das 2D-Array zu iterieren und den minimalen Abstand zu finden.

Vielen Dank für jeden Rat.

4 Solutions collect form web for “Nächste Nachbar Suche in Python ohne Kd Baum”

Wenn Sie gerade sind, können Sie dieses Ein-Liner machen:

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(qx,qx) for x in X]) Out[17]: 4 

Wenn Sie mehrere Abfragepunkte haben:

 In [18]: Q = scipy.array([[0.91, -0.43], [-0.14, -0.96]]) In [19]: [scipy.argmin([scipy.inner(qx,qx) for x in X]) for q in Q] Out[19]: [4, 9] 

Der Rundfunk ist für diese Art von Dingen sehr nützlich. Ich bin mir nicht sicher, ob dies das ist, was Sie brauchen, aber hier verwende ich den Rundfunk, um die Verschiebung zwischen p (ein Punkt in 3 Raum) und X (ein Satz von 10 Punkten im 3-Raum) zu finden.

 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 

Sie können alle Distanzen scipy.spatial.distance.cdist( X, Y ) berechnen oder RTree für dynamische Daten verwenden: http://gispython.org/rtree/docs/class.html .

Für eine schnellere Suche und Unterstützung für die dynamische Elementeinfügung können Sie einen Binärbaum für 2D-Elemente verwenden, bei denen größer und kleiner als der Bediener durch Abstand zu einem Referenzpunkt (0,0) definiert ist.

 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) 
  • Lesen Sie Nist Wav Datei in TIMIT Datenbank in Python numpy Array
  • Wie installiere ich numpy und scipy auf OS X?
  • Python-Konstruktion von Gitter, das Moleküle fängt - funktioniert nicht richtig
  • MemoryError in Toarray bei der Verwendung von DictVectorizer von Scikit Learn
  • Python: undefined symbol: PyUnicodeUCS2_DecodeUTF8
  • CSR, Inkonsistenz zwischen Indizes und Indptr
  • Vereinfachung der schlundartigen Operationen
  • Pandas spärliche DatenFrame zur spärlichen Matrix, ohne eine dichte Matrix im Speicher zu erzeugen
  • Multiplizieren von Spaltenelementen mit spärlicher Matrix
  • Verständnis scipy deconvolve
  • Prüfen Sie, ob zwei scipy.sparse.csr_matrix gleich sind
  • Python ist die beste Programmiersprache der Welt.