Un arbre de boules est une structure de données en arbre binaire utilisée pour partitionner des points dans un espace multidimensionnel en une hiérarchie d'hypersphères imbriquées, appelées boules. Chaque nœud de l'arbre représente une boule contenant un sous-ensemble des points de données, et le nœud racine contient tous les points. L'arbre est construit en divisant récursivement les points de données en deux groupes, chacun étant enfermé dans sa propre boule, jusqu'à ce qu'un critère d'arrêt soit atteint, tel qu'une taille maximale de feuille ou un rayon minimal de boule. Les arbres de boules sont principalement utilisés pour accélérer les requêtes de plus proches voisins, les recherches de similarité et l'estimation de densité par noyau, couramment dans des applications de apprentissage automatique telles que la augmentation de données et le clustering.
L'avantage principal d'un arbre de boules par rapport à d'autres structures d'indexation spatiale, comme les arbres k-d, est sa performance dans les espaces de haute dimension. Alors que les arbres k-d partitionnent l'espace à l'aide d'hyperplans alignés sur les axes, ce qui peut devenir inefficace à mesure que la dimensionnalité augmente en raison de la malédiction de la dimensionnalité, les arbres de boules partitionnent à l'aide de boules métriques qui s'adaptent à la distribution locale des données. Cette propriété permet aux arbres de boules d'élaguer plus efficacement de grandes portions de l'espace de recherche, en particulier lorsque les données présentent une structure groupée ou de faible dimension intrinsèque. En conséquence, les arbres de boules ont été adoptés dans divers contextes scientifiques et techniques, notamment la robotique, l'astronomie et le réglage d'hyperparamètres de réseaux de neurones.
Structure et Construction
Un arbre de boules est défini par un ensemble de boules imbriquées, chacune désignée par un centre et un rayon. Le centre est souvent choisi comme le centroïde des points contenus dans la boule, et le rayon est la distance maximale du centre à tout point de cette boule. L'arbre est construit à l'aide d'un algorithme récursif. À chaque étape, l'algorithme sélectionne un point le plus éloigné du centre actuel, puis sélectionne un second point le plus éloigné du premier point sélectionné. Ces deux points servent de pivots pour partitionner les points restants en deux clusters en fonction de leur proximité à chaque pivot. Ce processus est répété pour chaque cluster résultant jusqu'à ce qu'un nœud feuille contienne moins d'un nombre spécifié de points, généralement une petite constante.
Le temps de construction d'un arbre de boules est O(n log n) pour n points en basse dimension, mais il peut se dégrader en très haute dimension en raison du coût accru des calculs de distance. Plusieurs stratégies existent pour améliorer la construction, notamment l'utilisation de la sélection approximative du point le plus éloigné et l'équilibrage de l'arbre pour garantir une profondeur logarithmique. Le choix de la métrique affecte également la structure ; bien que la distance euclidienne soit courante, les arbres de boules peuvent être construits avec toute métrique satisfaisant l'inégalité triangulaire, comme les distances de Manhattan ou de Minkowski.
Recherche de Plus Proches Voisins
L'utilisation la plus courante d'un arbre de boules est la recherche des k plus proches voisins (k-NN), fondamentale dans les tâches de classification et de régression. L'algorithme de recherche parcourt l'arbre récursivement, en maintenant une file de priorité des meilleurs points candidats trouvés jusqu'à présent. À chaque nœud, l'algorithme calcule la distance du point de requête au centre de la boule du nœud. Si cette distance moins le rayon de la boule est supérieure à la distance actuelle du k-ième plus proche voisin, tout le sous-arbre peut être élagué, car aucun point dans cette boule ne peut être plus proche que le meilleur actuel. Cet élagage exploite l'inégalité triangulaire, qui garantit que tout point dans la boule est au moins à une certaine distance de la requête.
En pratique, les arbres de boules peuvent réduire la complexité computationnelle du k-NN de O(n) par requête (balayage naïf) à environ O(log n) en moyenne pour des données de faible dimension intrinsèque. Cependant, à mesure que la dimensionnalité augmente, l'efficacité de l'élagage diminue. Les chercheurs ont proposé des variantes, comme l'utilisation d'algorithmes à double arbre, où un arbre de requêtes et un arbre de données sont parcourus simultanément, pour améliorer davantage les performances en haute dimension. Ces techniques ont été intégrées dans des bibliothèques utilisées dans des cadres d'intelligence artificielle, comme scikit-learn et Amazon Web Services SageMaker.
Applications
Les arbres de boules sont largement utilisés dans les pipelines de apprentissage automatique. Dans l'estimation de densité par noyau, les arbres de boules accélèrent le calcul des estimations de densité locales en agrégeant les contributions de clusters de points plutôt que de points individuels. Ils apparaissent également dans les mécanismes de attention croisée et les architectures de attention multi-têtes dans les modèles de transformers, où la récupération efficace de clés pertinentes peut être bénéfique, bien que les implémentations traditionnelles utilisent une attention dense.
Au-delà de l'apprentissage automatique, les arbres de boules sont utilisés en robotique pour la planification de trajectoires et la détection de collisions, en infographie pour le lancer de rayons, et dans les systèmes d'information géographique pour les requêtes spatiales. Par exemple, Waymo et d'autres systèmes de véhicules autonomes utilisent des arbres de boules pour indexer les données des capteurs afin de récupérer rapidement les caractéristiques cartographiques les plus proches. En astronomie, les arbres de boules aident à cataloguer les étoiles grâce à des requêtes de proximité rapides. Leur polyvalence découle de la simplicité de la métrique sous-jacente et de la garantie de résultats de requête exacts, contrairement aux méthodes approximatives basées sur le hachage.
Comparaisons avec d'Autres Structures
Les arbres de boules sont souvent comparés aux arbres k-d, aux arbres R et au hachage sensible à la localité (LSH). Les arbres k-d partitionnent par division alignée sur les axes, ce qui est efficace en basse dimension (généralement moins de 20) mais souffre d'un retour arrière excessif en dimension supérieure. Les arbres de boules ne nécessitent pas de divisions alignées sur les axes et peuvent s'adapter à la forme des données. Les arbres R, utilisés principalement pour les rectangles englobants dans les bases de données, sont moins flexibles pour des métriques arbitraires. Le LSH fournit des résultats approximatifs et est plus rapide pour des dimensions extrêmement élevées, mais ne garantit pas les plus proches voisins exacts. Les arbres de boules offrent un compromis : des requêtes exactes avec de meilleures performances en haute dimension que les arbres k-d, bien qu'ils dépassent encore la recherche linéaire en très haute dimension.
Limitations et Extensions
Une limitation clé des arbres de boules est la malédiction de la dimensionnalité : à mesure que le nombre de dimensions augmente, le rapport des volumes des boules à l'espace environnant devient négligeable, rendant l'élagage inefficace. Dans de tels cas, des méthodes approximatives comme le LSH sont préférées. De plus, les arbres de boules sont des structures statiques ; l'insertion ou la suppression de points nécessite de reconstruire l'arbre, ce qui les rend inadaptés aux ensembles de données dynamiques, sauf si des variantes équilibrées sont utilisées.
Les extensions incluent l'hybride arbre k-d et boule, qui utilise des partitions de boules aux niveaux supérieurs et des divisions alignées sur les axes aux niveaux inférieurs, et l'arbre couvrant, qui garantit un temps de requête quasi logarithmique sous certaines hypothèses de données. La recherche se poursuit sur des métriques adaptatives et des index appris, où des modèles de apprentissage profond prédisent les frontières de partition, bien que ces approches restent de niche.
Voir Aussi
- Arbre k-d
- Recherche de plus proches voisins
- Arbre métrique
- réduction de dimensionnalité