Arbre d'axes principaux

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

• Soient N points à classer dans un nœud, considéré comme nœud racine, et ${\displaystyle n_{c}}$ le nombre maximum de fils que peut avoir un nœud ;
• Attribuer les N points au nœud racine. Le nœud racine devient le nœud en cours ;
  • Si le nombre de points assigné au nœud en cours est inférieur à ${\displaystyle n_{c}}$, le nœud est terminal et son traitement est terminé ;
  • Sinon, construire l'axe principal pour les points en cours et projeter orthogonalement ces points sur cet axe ;
• Partitioner l'ensemble des points projetés sur l'axe en ${\displaystyle n_{c}}$ régions distinctes et manière à ce que chaque région contienne le même nombre de points, à une unité prêt ;
• Attribuer chaque région ainsi créée à un des ${\displaystyle n_{c}}$ 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ées données 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 ${\displaystyle n_{c}}$ qui est généralement de l'ordre de 2 à une dizaine).

À noter que cet arbre présente au premier abord 2 avantages :

• Aucune région de l'arbre n'est vide, même partiellement ;
• L'axe principal sert à tout moment et est une droite, les problèmes sont donc linéaires.

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 en effectuant une recherche dichotomique parmi les limites des ${\displaystyle n_{c}}$ 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. Un algorithme de recherche de distance partielle est alors appliqué sur l'ensemble des points appartenant à ce nœud terminal[2].

L'algorithme remonte ensuite au nœud parent et tente d'éliminer les nœuds frères via le critère d'élimination :

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

Lorsque le nœud racine est complètement analysé (avec un mélange 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 de l'algorithme, basé sur des projections orthogonales.

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

• Un minimum 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 additions et des multiplications, sans connaître les coordonnées des points situés dans la deuxième région ;
• Par construction de l'arbre, pour chaque séparation entre deux régions à l'intérieur d'un nœud, un point doit se situer à la frontière, impliquant une réduction considérable des risques 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 aux proches voisins déjà trouvés, 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 ${\displaystyle d_{q2}}$ 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 points voisins de q déjà trouvée, la région grisée ainsi que la région 5 et au-delà peuvent être éliminées sans avoir à regarder les points présents dans ces régions.

Si le test échoue, il faut regarder de plus près ce qui se passe dans la région grisée (c'est-à-dire descendre dans le nœud correspondant). Soit le triangle formé par (${\displaystyle qb_{2}x}$). Nous savons que l'angle ${\displaystyle {\widehat {qb_{2}x}}}$ est compris entre 90° et 180°. Son cosinus est donc négatif et un minima de ${\displaystyle d_{qx}^{2}}$ peut être calculé par le théorème d'Al-Kashi :

${\displaystyle d_{qx}^{2}}$	${\displaystyle =}$	${\displaystyle d_{q2}^{2}+d_{2x}^{2}-2d_{q2}d_{2x}^{2}\cos \left({\widehat {qb_{2}x}}\right)}$
${\displaystyle d_{qx}^{2}}$	${\displaystyle \geq }$	${\displaystyle d_{q2}^{2}+d_{2x}^{2}}$	${\displaystyle \forall x\in {\textrm {region}}\;{\textrm {grise}}}$
${\displaystyle d_{2x}^{2}}$	${\displaystyle \geq }$	${\displaystyle d_{23}^{2}}$	${\displaystyle \forall x\in {\textrm {region}}\;3}$
${\displaystyle d_{qx}^{2}}$	${\displaystyle \geq }$	${\displaystyle d_{q2}^{2}+d_{23}^{2}}$	${\displaystyle \forall x\in {\textrm {region}}\;3}$

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

${\displaystyle d_{qx}^{2}}$

${\displaystyle \geq }$

${\displaystyle d_{q2}^{2}+d_{23}^{2}+d_{34}^{2}}$

${\displaystyle \forall x\in {\textrm {region}}\;4}$

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 faits directement à partir de projections sur l'axe principal, et donc en dimension 1.

• Portail de l'informatique théorique