scipy.spatial.

KDTree

class scipy.spatial.KDTree(data, leafsize=10, compact_nodes=True, copy_data=False, balanced_tree=True, boxsize=None)

KD-Baum für schnelle Suche nach nächstgelegenen Nachbarn.

Diese Klasse bietet einen Index für eine Menge von k-dimensionalen Punkten, der verwendet werden kann, um schnell die nächstgelegenen Nachbarn jedes Punktes nachzuschlagen.

Parameter:

dataarray_like, shape (n,m)

Die n Datenpunkte der Dimension m, die indiziert werden sollen. Dieses Array wird nicht kopiert, es sei denn, dies ist notwendig, um ein zusammenhängendes Array von Doubles zu erzeugen. Modifikationen dieser Daten führen zu fehlerhaften Ergebnissen. Die Daten werden auch kopiert, wenn der KD-Baum mit copy_data=True erstellt wird.

leafsizepositive int, optional

Die Anzahl der Punkte, bei der der Algorithmus auf Brute-Force umschaltet. Standard: 10.

compact_nodesbool, optional

Wenn True, wird der KD-Baum so aufgebaut, dass die Hyperrechtecke auf den tatsächlichen Datenbereich geschrumpft werden. Dies führt normalerweise zu einem kompakteren Baum, der robust gegenüber degenerierten Eingabedaten ist und schnellere Abfragen liefert, allerdings auf Kosten einer längeren Aufbauzeit. Standard: True.

copy_databool, optional

Wenn True, werden die Daten immer kopiert, um den KD-Baum vor Datenbeschädigung zu schützen. Standard: False.

balanced_treebool, optional

Wenn True, wird der Median verwendet, um die Hyperrechtecke zu teilen, anstatt den Mittelpunkt. Dies führt normalerweise zu einem kompakteren Baum und schnelleren Abfragen, allerdings auf Kosten einer längeren Aufbauzeit. Standard: True.

boxsizearray_like oder Skalar, optional

Wendet eine m-dimensionale toroidale Topologie auf den KD-Baum an. Die Topologie wird durch \(x_i + n_i L_i\) erzeugt, wobei \(n_i\) ganze Zahlen sind und \(L_i\) die Boxgröße entlang der i-ten Dimension ist. Die Eingabedaten müssen in \([0, L_i)\) eingekapselt werden. Es wird ein ValueError ausgelöst, wenn Daten außerhalb dieser Grenzen liegen.

Attribute:

datandarray, shape (n,m)

Die n Datenpunkte der Dimension m, die indiziert werden sollen. Dieses Array wird nicht kopiert, es sei denn, dies ist notwendig, um ein zusammenhängendes Array von Doubles zu erzeugen. Die Daten werden auch kopiert, wenn der KD-Baum mit copy_data=True erstellt wird.

leafsizepositive int

Die Anzahl der Punkte, bei der der Algorithmus auf Brute-Force umschaltet.

mint

Die Dimension eines einzelnen Datenpunktes.

nint

Die Anzahl der Datenpunkte.

maxesndarray, shape (m,)

Der Maximalwert in jeder Dimension der n Datenpunkte.

minsndarray, shape (m,)

Der Minimalwert in jeder Dimension der n Datenpunkte.

sizeint

Die Anzahl der Knoten im Baum.

Methoden

count_neighbors(other, r[, p, weights, ...])	Zählt, wie viele nahegelegene Paare gebildet werden können.
query(x[, k, eps, p, distance_upper_bound, ...])	Abfrage des KD-Baums nach nächstgelegenen Nachbarn.
query_ball_point(x, r[, p, eps, workers, ...])	Finde alle Punkte innerhalb der Distanz r von Punkt(en) x.
query_ball_tree(other, r[, p, eps])	Finde alle Punktepaare zwischen self und other, deren Abstand höchstens r beträgt.
query_pairs(r[, p, eps, output_type])	Finde alle Punktepaare in self, deren Abstand höchstens r beträgt.
sparse_distance_matrix(other, max_distance)	Berechne eine dünnbesetzte Distanzmatrix.

innernode
leafnode
node

Hinweise

Der verwendete Algorithmus ist in Maneewongvatana und Mount 1999 beschrieben. Die allgemeine Idee ist, dass der KD-Baum ein Binärbaum ist, dessen jeder Knoten ein achsenparalleles Hyperrechteck darstellt. Jeder Knoten gibt eine Achse an und teilt die Punktmenge basierend darauf, ob ihre Koordinate entlang dieser Achse größer oder kleiner als ein bestimmter Wert ist.

Während der Konstruktion werden die Achse und der Teilungspunkt mit der "gleitenden Mittelpunkt"-Regel gewählt, die sicherstellt, dass die Zellen nicht alle lang und dünn werden.

Der Baum kann nach den r nächstgelegenen Nachbarn eines beliebigen gegebenen Punktes abgefragt werden (optional werden nur diejenigen zurückgegeben, die sich innerhalb eines bestimmten maximalen Abstands zum Punkt befinden). Er kann auch mit erheblichem Effizienzgewinn nach den r ungefähr nächstgelegenen Nachbarn abgefragt werden.

Für hohe Dimensionen (20 ist bereits hoch) ist nicht zu erwarten, dass dies signifikant schneller als Brute-Force läuft. Die Suche nach nächstgelegenen Nachbarn in hochdimensionalen Räumen ist ein bedeutendes offenes Problem in der Informatik.