KD Tree: signification du paramètre `leafsize`

Question

Je regarde l' implémentation de KD Tree de SciPy . Je suis confus par le leafsizeparamètre, qui est dit

Le nombre de points auxquels l'algorithme passe en force brute. Par défaut: 16.

Est-ce le nombre de feuilles dans le BST? Si tel est le cas, cela signifie que par défaut, l'arborescence KD ne contiendra pas plus de 32 points. Cela semble déraisonnablement petit, en particulier pour mon cas d'utilisation de k = 2. Est-ce que j'interprète le paramètre de manière incorrecte?

Answer 1

Le paramètre leafsizene contrôle pas le nombre maximum de feuilles dans l'arbre (qui n'est pas limité), mais plutôt le nombre de points d'entrée associés à une seule feuille de l'arbre. Considérez que 64 points sont ajoutés à un arbre. Si chaque point est associé à une seule feuille, vous obtiendrez un arbre complet de sept niveaux de profondeur et tout traitement nécessitant un point descendra ces sept niveaux pour le trouver. Sinon, si la taille de la feuille est 16, vous obtiendrez un arbre qui n'a que 3 niveaux de profondeur et chaque feuille de l'arbre est associée à 16 points. Le traitement d'un point implique de descendre trois niveaux de l'arbre, puis de tester chacun des 16 points de la feuille (puisqu'ils ne sont pas ordonnés). Cette valeur peut être ajustée pour les performances, et empiriquement, la meilleure valeur dépend de la façon exacte dont l'arbre est utilisé.

Conceptuellement, voici un exemple d'arbres qui seraient construits pour différentes leafsizevaleurs.

Vous pouvez voir comment le leafsizeparamètre court-circuite le processus de construction de l'arborescence dans le code source scipy . Cela laissera entre leafsize/2et leafsizepoints non ordonnés dans les feuilles de l'arbre.