Comprendre `leafsize` dans scipy.spatial.KDTree
Énoncé du problème:
J'ai 150k points dans un espace 3D avec leurs coordonnées stockées dans une matrice de dimension [150k, 3] en mm.
Je veux trouver tous les voisins d'un point donné p
qui sont dans un rayon r
. Et je veux faire cela de la manière la plus précise.
Comment choisir mon leafsize
paramètre?
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
Réponses
La fonction query_ball_point
renverra l'ensemble de points correct pour n'importe quelle version de l'arborescence de recherche. Le leafsize
paramètre n'a pas d'impact sur les résultats de la requête, uniquement sur les performances des résultats.
Imaginez deux arbres illustrés ci-dessous pour les mêmes données (mais des paramètres de taille de feuille différents) et une requête recherchant tous les points à l'intérieur du cercle rouge.

Dans les deux cas, le code ne retournera que les deux points situés à l'intérieur du cercle rouge. Cela se fait en cochant tous les points de toutes les cases de l'arbre qui coupent le cercle. Cela conduit à une quantité de travail différente (c'est-à-dire à des performances différentes) dans chaque cas. Pour l'arbre de gauche (correspondant à une plus grande taille de feuille), l'algorithme doit vérifier si 13 points sont à l'intérieur du cercle (6 dans la case d'intersection supérieure et 7 dans la case d'intersection inférieure). Dans l'arbre de droite (qui a une taille de feuille plus petite), seuls trois points sont traités (un dans la boîte d'intersection supérieure et deux dans la boîte d'intersection inférieure).
En suivant cette logique, vous pouvez penser qu'il est logique de toujours utiliser une petite taille de feuille: cela minimisera le nombre de comparaisons réelles à la fin de l'algorithme (décidez si les points se trouvent réellement dans la région de requête). Mais ce n'est pas si simple: la taille plus petite des feuilles générera un arbre plus profond, ajoutant un coût au temps de construction et au temps de traversée de l'arbre. Obtenir le bon équilibre entre les performances de traversée de l'arborescence avec les comparaisons au niveau feuille dépend vraiment du type de données entrant dans l'arborescence et des comparaisons spécifiques au niveau feuille que vous effectuez. C'est pourquoi scipy fournit le paramètre leafsize comme argument afin que vous puissiez régler les choses pour qu'elles fonctionnent le mieux sur un algorithme particulier.