Principal axis tree

Principal axis tree: Principal axis tree

L’arbre d'axes principaux (en anglais : Principal Axis Tree), souvent abrégé PAT est un algorithme permettant de diviser un espace de points de manière efficiente en vue de résoudre rapidement le problème des plus proches voisins. Elle fut développée par James McNames^[1] en 2001.

L'algorithme obtenu permet d'effectuer des recherches de voisinage d'un point donnée en un temps moyen $O \left ( \log{\left( N \right)}\right)$ . 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 informatique. 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) en $O\left( N \log{\left( N \right)} \right)$ ;

Espace de stockage en $O \left( N \right)$ ;

Temps de recherche moyen en $O \left( \log{\left( N \right)} \right)$ .

Sommaire

1 Construction de l'arbre

2 Recherche dans l'arbre

3 Critère d'élimination

4 Notes et références

Construction de l'arbre

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 $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 deviens le nœud en cours ;

Si le nombre de points assigné au nœud en cours est inférieur à $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 $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 $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 $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.

Recherche dans l'arbre

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 $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é 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

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 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 $d q 2$ 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è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 ( $q b 2 x$ ). Nous savons que l'angle $\widehat{qb_2x}$ est compris entre 90° et 180°. Son cosinus est donc négatif et un minima de $d^2_{qx}$ peut être calculé par le théorème d'Al-Kashi :

$d^2_{qx}$ $=$ $d_{q2}^{2}+d_{2x}^{2}-2d_{q2}d_{2x}^{2}\cos \left( \widehat{qb_{2}x}\right)$

$d_{qx}^{2}$ $\geq$ $d_{q2}^{2}+d_{2x}^{2}$ $\forall x\in \textrm{region}\;\textrm{grise}$

$d_{2x}^{2}$ $\geq$ $d_{23}^{2}$ $\forall x\in \textrm{region}\;3$

$d_{qx}^{2}$ $\geq$ $d_{q2}^{2}+d_{23}^{2}$ $\forall x\in \textrm{region}\;3$

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

$d_{qx}^{2}$ $\geq$ $d_{q2}^{2}+d_{23}^{2}+d_{34}^{2}$ $\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.

Notes et références

↑ (en) 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.

↑ Rappelons qu'il y a, par construction, moins de $n c$ points dans ce nœud.

Portail de l’informatique

Ce document provient de « Principal axis tree ».

Catégorie : Algorithmique

Contenu soumis à la licence CC-BY-SA. Source : Article Principal axis tree de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

Principal Axis Tree — L’arbre d axes principaux (en anglais : Principal Axis Tree), souvent abrégé PAT est un algorithme permettant de diviser un espace de points de manière efficiente en vue de résoudre rapidement le problème des plus proches voisins. Elle fut… … Wikipédia en Français
Tree — /tree/, n. Sir Herbert Beerbohm /bear bohm/, (Herbert Beerbohm), 1853 1917, English actor and theater manager; brother of Max Beerbohm. * * * I Woody perennial plant. Most trees have a single self supporting trunk containing woody tissues, and in … Universalium
tree — treelike, adj. /tree/, n., v., treed, treeing. n. 1. a plant having a permanently woody main stem or trunk, ordinarily growing to a considerable height, and usually developing branches at some distance from the ground. 2. any of various shrubs,… … Universalium
Arbre d'axes principaux — L’arbre d axes principaux (en anglais : Principal Axis Tree), souvent abrégé PAT est un algorithme permettant de diviser un espace de points de manière efficiente en vue de résoudre rapidement le problème des plus proches voisins. Elle fut… … Wikipédia en Français
List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… … Wikipedia
List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… … Wikipedia
craig flounder — Pole Pole, n. [As. p[=a]l, L. palus, akin to pangere to make fast. Cf. {Pale} a stake, {Pact}.] 1. A long, slender piece of wood; a tall, slender piece of timber; the stem of a small tree whose branches have been removed; as, specifically: (a) A… … The Collaborative International Dictionary of English
Glyptocephalus cynoglossus — Pole Pole, n. [As. p[=a]l, L. palus, akin to pangere to make fast. Cf. {Pale} a stake, {Pact}.] 1. A long, slender piece of wood; a tall, slender piece of timber; the stem of a small tree whose branches have been removed; as, specifically: (a) A… … The Collaborative International Dictionary of English
Pole — Pole, n. [As. p[=a]l, L. palus, akin to pangere to make fast. Cf. {Pale} a stake, {Pact}.] 1. A long, slender piece of wood; a tall, slender piece of timber; the stem of a small tree whose branches have been removed; as, specifically: (a) A… … The Collaborative International Dictionary of English
Pole bean — Pole Pole, n. [As. p[=a]l, L. palus, akin to pangere to make fast. Cf. {Pale} a stake, {Pact}.] 1. A long, slender piece of wood; a tall, slender piece of timber; the stem of a small tree whose branches have been removed; as, specifically: (a) A… … The Collaborative International Dictionary of English

Dictionnaires et Encyclopédies sur 'Academic'

Principal axis tree

Principal axis tree

Sommaire

Construction de l'arbre

Recherche dans l'arbre

Critère d'élimination

Notes et références

Regardez d'autres dictionnaires:

Share the article and excerpts

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

Dictionnaires et Encyclopédies sur 'Academic'

Wikipédia en Français

Principal axis tree

Principal axis tree

Sommaire

Construction de l'arbre

Recherche dans l'arbre

Critère d'élimination

Notes et références

Regardez d'autres dictionnaires:

Share the article and excerpts

Direct link