Vantage point tree

Un arbre à points de vue (ou vp-tree, abréviation de l'appellation anglaise vantage point tree) est un arbre métrique permettant de partitionner n'importe quel espace de données pourvu d'une métrique, c'est-à-dire d'une mesure de distance entre les nœuds ou points représentant les données. Le processus de construction de l'arbre consiste à sélectionner un point privilégié (ledit point de vue ou point d'observation / de référence, vantage point en anglais), puis à diviser l'espace en deux sous-espaces : un sous-espace gauche (ou intérieur) contenant l'ensemble des points à une distance du point privilégié inférieure à un certain seuil, et un sous-espace droit (ou extérieur) contenant l'ensemble des points ne remplissant pas cette condition. Le processus est appliqué de manière récursive, produisant des sous-espaces de plus en plus petits. Le vp-tree résultant est une structure de données arborescente telle qu'une proximité dans l'arbre est représentative de la proximité dans l'espace de données ainsi partitionné.

Ce processus de partitionnement itératif est similaire à celui d'un k-d tree, mais utilise des partitions circulaires (ou sphériques, hypersphériques, etc. selon la dimension de l'espace) plutôt que rectilignes. Dans un espace euclidien bidimensionnel, il produit un découpage en régions dont la forme ressemble à des coquilles sphériques.

Histoire

La première mention de cette méthode remonte à 1991 : elle est présentée sous le nom d'arbre métrique dans un article publié par Jeffrey Uhlmann. Toutefois, on doit l'appellation vantage point tree à Peter Yianilos, qui affirme dans un papier datant de 1993 avoir formalisé cette méthode indépendamment des recherches de J. K. Uhlmann. Dans cette publication, il introduit trois versions du vp-tree (vp-tree, vp^s-tree, vp^sb-tree).

En 1999, T. Bozkaya et M. Ozsoyoglu proposent les arbres à points de vue multiples (ou mvp-tree, abréviation de l'appellation anglaise multivantage point tree). Les mvp-trees sont une généralisation des vp-trees. Cette approche a été développée afin d'améliorer les propriétés des vp-trees lors de requêtes de recherche de similarité sur de grands espaces métriques. La différence majeure est l'utilisation de plus d'un point de référence pour partitionner l'espace à chaque niveau.

En 2009, Nielsen et des collabrateurs créent les bvp-trees (ou Bregman ventage point trees) et étendent ainsi les vp-trees à des espaces non métriques en utilisant les divergences de Bregman.

Construction

La construction la plus simple d'un vp-tree consiste à partitionner l'espace à l'aide de coupes sphériques, au sens de la distance choisie, c'est-à-dire qu'on s'intéresse aux points à une certaine distance d'un point privilégié, donc dans une sphère centrée en ce point.

On sélectionne d'abord un point pivot $v$ (vantage point) correspondant à un nœud de l'arbre.

On calcule ensuite les distances de tous les autres points (c.-à-d. les points qui seront indexés sous ce nœud) au point pivot.

La valeur médiane $dist_{m}$ de ces distances est utilisée comme distance-seuil, de sorte que la moitié des points se trouve à l'intérieur de la boule de centre $v$ et de rayon $dist_{m}$, et l'autre moitié à l'extérieur.

On associe les points qui se trouvent à l'intérieur de la boule au sous-arbre de gauche, et ceux se trouvant à l'extérieur au sous-arbre de droite.

On construit ensuite de manière récursive les branches de niveau inférieur.

Le vp-tree est une structure de données intéressante car elle ne nécessite aucune connaissance des points autre que l'évaluation de la fonction de distance. Cette méthode d'indexation basée uniquement sur la distance peut donc aussi être utilisée dans des espaces métriques non standards (en particulier non euclidiens). Elle n'exige aucune hypothèse sur la géométrie de l'espace de données.

Recherche du plus proche voisin

Un vp-tree peut être utilisé pour trouver le plus proche voisin ${x}_{best}$ d'un point $x_{1}$. Cette recherche peut être couplée à une condition sur la distance maximale $\tau$ entre deux points pour qu'ils soient considérés comme suffisamment proches.

L'algorithme de recherche est récursif. Une implémentation possible est la suivante :

À chaque nœud, de point pivot $v$ (vantage point) et de distance-seuil $t$ (la lettre $t$ étant choisie à cause de l'anglais threshold, seuil), on calcule la distance $dist(x_{1},v)$ de $x_{1}$ à $v$ ;

Si $dist(x_{1},v)\leq \tau$, on stocke les nouvelles valeurs : ${x}_{best}=v$, $\tau =dist(x_{1},{x}_{best})$.

Si $dist(x_{1},v)+t\leq \tau$, alors tous les points du sous-arbre de gauche sont à une distance inférieure ou égale à $\tau$ de $x_{1}$. On continue la recherche de manière récursive dans le sous-arbre de gauche (intérieur de la boule).

Si $dist(x_{1},v)\leq t+\tau$, on cherche de manière récursive dans le sous-arbre de gauche (intérieur de la boule) ; si $dist(x_{1},v)\geq t-\tau$, on cherche de manière récursive dans le sous-arbre de droite (extérieur de la boule).

Le pire des cas se produit lorsque $t-\tau \leq dist(x_{1},v)\leq t+\tau$, c'est-à-dire lorsque l'ensemble des points qui pourraient satisfaire la requête intersecte à la fois la boule associée au sous-arbre gauche et la boule associée au sous-arbre droit. Dans ce cas, il faut chercher de manière récursive dans les deux sous-arbres : aucun élagage de l'arbre n'est possible.

Complexité

La méthode de construction la plus simple a une complexité de $O(n\log n)$. Pour chaque élément, $\log n$ niveaux sont parcourus pour trouver son emplacement.

La temps d'exécution de la recherche d'un plus proche voisin unique est d'environ $O(\log n)$.

Le temps nécessaire au parcours d'un vp-tree pour un ensemble de données peut varier considérablement en fonction des spécificités de l'algorithme utilisé et du choix des paramètres. S. Brin a détaillé les performances de plusieurs variantes algorithmiques du vp-tree, pour plusieurs valeurs de paramètres, afin d'étudier le coût de chacune d'entre elles . Le coût est mesuré en nombre de calculs de distance.

Le coût en termes d'espace de stockage pour un vp-tree est linéaire (environ $n$). Chaque point de données est stocké et chaque élément de chaque nœud interne (c'est-à-dire qui n'est pas une feuille) nécessite un pointeur vers ses nœuds descendants.

Certains outils d'espace métrique nécessitent le calcul d'une matrice de distances par paires, de coût $O(n^{2})$. Ce n'est pas nécessaire avec les vp-trees.

Voir aussi

Articles connexes

• Recherche des plus proches voisins
• Méthode itérative

Liens externes

• "VP trees: A data structure for finding stuff fast" - Steve Hanov's Blog