Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Principal axis tree

Introduction

L'arbre d'axes principaux, aussi appelé Principal Axis Tree ou encore PAT, permet de diviser un espace de points de manière efficiente en vue de solutionner rapidement le problème des plus proches voisins. Cette méthode de recherche des plus proches voisins a été développée par James McNames (J. McNames, « A Fast Nearest Neighbor Algorithm Based on a Principal Axis Tree, » IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 23, No. 9, pp. 964-976, September 2001.)

L'algorithme obtenu permet d'effectuer des recherches de voisinage d'un point donnée en un temps et ce même dans des dimensions élevées. Cet algorithme de recherche se base sur un élagage très rapide de l'arbre, grâce à la puissance de son critère d'élimination, tout en limitant l'espace de stockage nécessaire en mémoire. Enfin, à l'intérieur d'une feuille donnée, l'algorithme utilise la recherche de distance partielle pour encore accélérer les calculs. L'algorithme présente les caractéristiques suivantes, N étant le nombre de points présents dans l'espace:

• Temps de calcul préparatoire (prétraitement) de ;
• Espace de stockage de ;
• Temps de recherche moyen de

Construction de l'arbre

Schématiquement, la construction de l'arbre d'axe principal se déroule 6 étapes:

1. Soient N points à classer dans un nœud, considéré comme nœud racine, et le nombre de fils maximum que peut avoir un nœud;
2. attribuer les N points au nœud racine. Le nœud racine deviens le nœud en cours;
3. si le nombre de points assigné au nœud en cours est inférieur à , le nœud est terminal et son traitement est terminé;
4. sinon, construire l'axe principal pour les points en cours et projeter orthogonalement ces points sur cet axe;
5. partitioner l'ensemble des points projetés sur l'axe en régions distinctes et manière à ce que chaque région contienne le même nombre de points, à une unité prêt;
6. Attribuer chaque région ainsi créée à un des nœuds fils distinct et recommencer en 3 pour chacun de ces nœuds.

On obtient ainsi un arbre pour lequel l'ensemble des points est attribué à la racine. Ces points sont ensuite séparés en différentes régions, chacune correspondant à un fils de la racine. On peut, via l'axe principal qui a été sauvé à chaque étape, déterminer dans quelle région doit se situer un point de coordonnée donnée et donc savoir à quel nœud fils il est associé. À partir de là, on peut déterminer dans quelle sous-région il se trouve et ainsi de suite jusqu'à atteindre une région terminale. Cette région terminale est caractérisée par la présence de peu de points (moins de qui est généralement de l'ordre de 2 à une dizaine). À noter que cet arbre présente au premier abord 2 avantages:

1. Aucune région de l'arbre n'est vide, même partiellement;
2. l'axe principal sert à tout moment et est une droite, les problèmes sont donc réduit à des problèmes en dimension un.

Recherche dans l'arbre

1. L'arbre est analysé depuis sa racine pour déterminer dans quelle région (et donc dans quel nœud fils) se trouve le point dont on cherche le voisinage. Cette analyse est aisément effectuée en projetant ledit point sur l'axe principal associé au nœud racine et enffectuant un recherche dichotomique parmi les limites des régions. Ce processus est répété sur le nœud correspondant à la région en question et ainsi de suite jusqu'à atteindre une feuille que nous appellerons nœud terminal;
2. un algorithme de recherche de distance partielle est appliqué sur l'ensemble des points appartenant à ce nœud terminal. Rappelons qu'il y a, par construction, moins de points dans ce nœud;
3. l'algorithme remonte au nœud parent et tente d'éliminer les nœuds frères via le critère délimination.

1. Si le critère est satisfait, les nœuds frères sont éliminé et l'analyse remonte au nœud parent;
2. si le critère n'est pas satisfait, l'algorithme descend dans le nœud frere le plus proche pour une analyse plus approfondie.

1. Lorsque le nœud racine est complètement analysé (avec un émlange d'exploration et d'élimination), le voisinage est considéré comme construit.

En résumé, on part de la racine, on descend vers le nœud terminal correspondant au point dont on cherche le voisinage et on tente d'éliminer des sections entières de l'arbre via le critère délimination.

Critère d'élimination

La puissance du critère d'élimination régit la puissance de tout algorithme de recherche. L'algorithme utilisé dans l'arbre des axes principaux tire sa puissance de deux points:

1. Un minima de la distance entre un point situé dans une région et l'ensemble des points situé dans une autre région de l'espace se fait en utilisant uniquement des addition et des multiplications et sans connaître les coordonées des points situés dans la deuxième région;
2. Par construction de l'arbre, pour chaque séparation entre 2 régions à l'intérieur d'un nœud, un point doit se situer à la frontière, impliquant une réduction considérable des risque de sous évaluation dus à la présence d'espaces vides.

Pour comprendre le fonctionnement du critère d'élimination, le lecteur est invité à se référer à la figure ci-contre. Chaque nœud de l'arbre correspond à une région de l'espace. À partir d'informations fournies lors de la construction de l'arbre, le critère d'élimination est capable d'évaluer une distance minimum au-delà de laquelle se trouve n'importe quel point de la région. Si cette distance minimale est trop grande par rapport au proches voisins déjà trouvé, la région entière peut être éliminée. Les nœuds voisins sont encore plus loin, par construction de l'arbre, et sont eux aussi éliminés.

Dans la figure, la distance entre le point q, point situé dans la région 1 dont on cherche le voisinage, et x un point quelconque situé dans la région 2 est supérieure à la distance entre le point q et l'hyperplan séparant la région 1 de la région 2. Cet hyperplan étant, par construction, perpendiculaire à l'axe principal, la distance peut être calculée rapidement le long de cet axe, soit en dimension 1. La distance est donc le minimum entre le point q et tout point de la région grisée. Si ce minima est supérieur à l'ensemble des point voisin de q déjà trouvée, la région grisée ainsi que la région 5 et au-delà peuvent être éliminés sans avoir à regarder les points présents dans ces régions.

Si le test échoue, il faut regarder de plus prêt ce qui se passe dans la région grisée (c'est-à-dire descendre dans le nœud correspondant). Soit le triangle formé par (). Nous savons que l'angle est compris entre 90 et 180. Son cosinus est donc négatif et un minima de peut être calculé par pythagore généralisé:

Le même raisonnement appliqué à une autre sous région donne

Les points frontières b et les minimums des distances sont ainsi calculés récursivement par l'algorithme de recherche. Ces calculs de distances de points frontière se font extrèmement rapidement car ils peuvent être fait directement a partir de projections sur l'axe principal, et donc en dimension 1!