scipy.spatial.

cKDTree

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

kd-Baum für schnelle Suche nach nächsten Nachbarn

Diese Klasse bietet einen Index für eine Menge von k-dimensionalen Punkten, der verwendet werden kann, um schnell die nächsten Nachbarn eines beliebigen Punktes zu finden.

Hinweis

cKDTree ist funktional identisch mit KDTree. Vor SciPy v1.6.0 hatte cKDTree eine bessere Leistung und leicht abweichende Funktionalität, aber jetzt existieren die beiden Namen nur noch aus Gründen der Abwärtskompatibilität. Wenn die Kompatibilität mit SciPy < 1.6 keine Rolle spielt, bevorzugen Sie KDTree.

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. Das Modifizieren dieser Daten führt 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: 16.

compact_nodesbool, optional

Wenn True, wird der kd-Baum so erstellt, dass die Hyperrechtecke auf den tatsächlichen Datenbereich geschrumpft werden. Dies ergibt normalerweise einen kompakteren Baum, der gegen entartete Eingabedaten robust ist und schnellere Abfragen ermöglicht, auf Kosten einer längeren Erstellungszeit. 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 des Mittelpunkts. Dies ergibt normalerweise einen kompakteren Baum und schnellere Abfragen, auf Kosten einer längeren Erstellungszeit. Standard: True.

boxsizearray_like oder Skalar, optional

Wendet eine m-dimensionale toroidale Topologie auf den KDTree 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)\) eingepasst werden. Ein ValueError wird ausgelöst, wenn Daten außerhalb dieser Grenze 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 Datenpunkts.

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.

treeobject, class cKDTreeNode

Dieses Attribut stellt eine Python-Ansicht des Wurzelknotens im cKDTree-Objekt bereit. Eine vollständige Python-Ansicht des kd-Baums wird beim ersten Zugriff dynamisch erstellt. Dieses Attribut ermöglicht es Ihnen, eigene Abfragefunktionen in Python zu erstellen.

sizeint

Die Anzahl der Knoten im Baum.

Methoden

count_neighbors(self, other, r[, p, ...])	Zählt, wie viele nahegelegene Paare gebildet werden können.
query(self, x[, k, eps, p, ...])	Fragt den kd-Baum nach den nächsten Nachbarn ab
query_ball_point(self, x, r[, p, eps, ...])	Finde alle Punkte innerhalb der Distanz r von Punkt(en) x.
query_ball_tree(self, other, r[, p, eps])	Findet alle Punktpaare zwischen self und other, deren Abstand höchstens r beträgt
query_pairs(self, r[, p, eps, output_type])	Finde alle Punktepaare in self, deren Abstand höchstens r beträgt.
sparse_distance_matrix(self, other, max_distance)	Berechnet eine spärliche Distanzmatrix

Hinweise

Der verwendete Algorithmus wird 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 nach 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ächsten Nachbarn eines beliebigen gegebenen Punktes abgefragt werden (optional werden nur diejenigen innerhalb eines bestimmten maximalen Abstands zum Punkt zurückgegeben). Er kann auch, mit erheblicher Effizienzsteigerung, nach den r ungefähren nächsten Nachbarn abgefragt werden.

Für hohe Dimensionen (20 ist bereits hoch) erwarten Sie keine signifikant schnellere Leistung als bei Brute-Force. Nächste-Nachbar-Abfragen in hoher Dimension sind ein erhebliches offenes Problem in der Informatik.