`Leafsize` in scipy.spatial.KDTree verstehen
Problemstellung:
Ich habe 150k Punkte in einem 3D-Raum, deren Koordinaten in einer Matrix mit der Dimension [150k, 3] in mm gespeichert sind.
Ich möchte alle Nachbarn eines bestimmten Punktes finden p
, die sich innerhalb eines Radius befinden r
. Und das möchte ich auf die genaueste Weise tun.
Wie soll ich meinen leafsize
Parameter wählen ?
from scipy.spatial import KDTree
import numpy as np
pts = np.random.rand(150000,3)
T1 = KDTree(pts, leafsize=20)
T2 = KDTree(pts, leafsize=1)
neighbors1= T1.query_ball_point((0.3,0.2,0.1), r=2.0)
neighbors2= T2.query_ball_point((0.3,0.2,0.1), r=2.0)
np.allclose(sorted(neighbors1), sorted(neighbors2))
True
Antworten
Die Funktion query_ball_point
gibt den richtigen Satz von Punkten für jede Version des Suchbaums zurück. Der leafsize
Parameter wirkt sich nicht auf die Ergebnisse der Abfrage aus, sondern nur auf die Leistung der Ergebnisse.
Stellen Sie sich zwei unten gezeigte Bäume für dieselben Daten (aber unterschiedliche Blattgrößenparameter) und eine Abfrage vor, die nach allen Punkten innerhalb des roten Kreises sucht.

In beiden Fällen gibt der Code nur die beiden Punkte zurück, die innerhalb des roten Kreises liegen. Dies erfolgt durch Aktivieren aller Punkte in allen Feldern des Baums, die den Kreis schneiden. Dies führt jeweils zu einem unterschiedlichen Arbeitsaufwand (dh einer unterschiedlichen Leistung). Für den linken Baum (entsprechend einer größeren Blattgröße) muss der Algorithmus prüfen, ob sich 13 Punkte innerhalb des Kreises befinden (6 im oberen Schnittfeld und 7 im unteren Schnittfeld). Im rechten Baum (der eine kleinere Blattgröße hat) werden nur drei Punkte verarbeitet (einer im oberen Schnittfeld und zwei im unteren Schnittfeld).
Wenn Sie dieser Logik folgen, denken Sie vielleicht, dass es nur sinnvoll ist, immer eine kleine Blattgröße zu verwenden: Dadurch wird die Anzahl der tatsächlichen Vergleiche am Ende des Algorithmus minimiert (entscheiden Sie, ob die Punkte tatsächlich im Abfragebereich liegen). Aber es ist nicht so einfach: Die kleinere Blattgröße erzeugt einen tieferen Baum, was die Bauzeit und die Baumdurchlaufzeit erhöht. Das richtige Gleichgewicht zwischen der Leistung beim Durchlaufen von Bäumen und den Vergleichen auf Blattebene hängt wirklich von der Art der Daten ab, die in den Baum eingehen, und von den spezifischen Vergleichen auf Blattebene, die Sie durchführen. Aus diesem Grund stellt scipy den Parameter leafsize als Argument zur Verfügung, damit Sie die Leistung eines bestimmten Algorithmus optimieren können.