Classification à l’aide des plus proches voisins#

La figure suivante représente un problème de classification classique. On dispose d’un nuage de points réparti en deux classes. Un nouveau point semblable aux précédents se présente, sa classe est inconnue. L’objectif est de lui attribuer une classe en utilisant le fait qu’on connaît la classe d’appartenance des autres points.

../_images/classif.png

A partir d’un nuage de points pour lesquels la classe d’appartenance est connue, comment classer un nouveau point pour lequel cette classe est inconnue ? Une méthode simple consiste à attribuer à ce nouveau point la même classe que le plus proche des points appartenant au nuage initial. C’est la méthode des plus proches voisins (ou nearest neighbours) Elle est facile à implémenter mais peu utilisée car souvent très gourmande en temps de calcul lorsque le nuage de points est conséquent. Le premier paragraphe décrit cette méthode, les suivants cherchent à accélérer l’algorithme selon que le nuage de points appartient à un espace vectoriel ou non. La dernière partie présente l’algorithme LAESA pour le cas où le nuage de points appartient à un espace métrique quelconque.

Principe#

Cette méthode est la plus simple puisqu’elle consiste à associer à x, l’élément à classer, le label c\pa{x_{i^*}} de l’élément le plus proche x_{i^*} dans l’ensemble \vecteur{x_1}{x_N}. Ceci mène à l’algorithme de classification suivant :

Algorithme A1 : 1-PPV ou plus proche voisin

Soit X = \vecteur{x_1}{x_N} \subset E un ensemble d’éléments d’un espace métrique quelconque, soit \vecteur{c\pa{x_1}}{c\pa{x_N}} les classes associées à chacun des éléments de X. On note d la distance définie sur l’espace métrique E. Soit x un élément à classer, on cherche à déterminer la classe \hat{c}(x) associée à x. On définit x_{i^*} comme étant :

x_{i^*} = \underset{i \in \intervalle{1}{N}}{\arg \min} \; d\pa{x_i,x}

Alors \hat{c}(x) = c\pa{x_i^*}.

Cet algorithme est souvent appelé 1-PPV (ou 1-NN pour Nearest Neighbors). Il existe une version améliorée k-PPV qui consiste à attribuer à x la classe la plus représentée parmi ses k plus proches voisins.

Algorithme A2 : k-PPV ou k-plus proches voisins

Soit X = \vecteur{x_1}{x_N} \subset E un ensemble d’éléments d’un espace métrique quelconque, soit \vecteur{c\pa{x_1}}{c\pa{x_N}} les classes associées à chacun des éléments de X. On note d la distance définie sur l’espace métrique E. \omega\pa{x,y} est une fonction strictement positive mesurant la ressemblance entre x et y. Soit x un élément à classer, on cherche à déterminer la classe c(x) associée à x. On définit l’ensemble S^*_k incluant les k-plus proches voisins de x, cet ensemble vérifie :

card{S^*_k} = 0 \text{ et } \underset{y \in S^*_k}{\max} \; d\pa{y,x}
\infegal \underset{y \in X - S^*_k}{\min} \; d\pa{y,x}

On calcule les occurrences f(i) de chaque classe i dans l’ensemble S^*_k :

(1)#f(i) = \sum_{y \in S^*_k} \, \omega\pa{x,y} \, \indicatrice{c(y) = i}

On assigne alors à x la classe :math:`c(x)$ choisie dans l’ensemble :

\hat{c}(x) \in \underset{i \in \N}{\arg \max} \; f(i)

Dans sa version la plus simple, la fonction \omega\pa{x,y} utilisée lors du calcul de la contribution f (1) est constante. Mais il est possible de lui affecter une valeur tenant compte de la proximité entre x et y. La table suivante donne quelques exemples de contributions possibles.

Exemple de contribution w\pa{x,y} pour l’algorithme des k-ppv. Ces fonctions sont toutes décroissantes (strictement ou non) par rapport à la distance d. L’inconvénient majeur de la méthode des plus proches voisins est sa longueur puisqu’elle implique le calcul des distances entre x et chacun des éléments de l’ensemble \vecteur{x_1}{x_N}. C’est pourquoi de nombreuses méthodes d’optimisation ont été développées afin d’accélérer ce processus. Les deux premiers paragraphes traitent le cas où les points x_i appartiennent à un espace vectoriel et ont donc des coordonnées. Les suivant traitent le cas où les points x_i n’ont pas de coordonnées et appartiennent à un espace métrique quelconque.

B+ tree#

Ce premier algorithme B+ tree s’applique dans le cas réel afin d’ordonner des nombres dans un arbre de sorte que chaque noeud ait un père et pas plus de n fils.

../_images/btree.png

Définition D1 : B+ tree

Soit B_n un B+ tree, soit N un noeud de B_n, il contient un vecteur V\pa{N} = \vecteur{x_1}{x_t} avec 0 \infegal t \infegal n et x_1 < ... < x_t. Ce noeud contient aussi exactement t-1 noeuds fils notés \vecteur{N_1}{N_{t-1}}. On désigne par D\pa{N_t} l’ensemble des descendants du noeud N_t et G\pa{N_t} = \acc{ V\pa{M} \sac M \in D\pa{N_t}}. Le noeud N vérifie :

\begin{eqnarray*}
&& \forall x \in G\pa{N_t}, \; x_{t} \infegal x < x_{t+1} \\
&& \text{avec par convention } x_0 = -\infty \text{ et } x_{t+1} = + \infty
\end{eqnarray*}

Cet arbre permet de trier une liste de nombres, c’est une généralisation du tri quicksort pour lequel n=2. Comme pour le tri quicksort, l’arbre est construit à partir d’une série d’insertions et de cet ordre dépend la rapidité du tri. L’espérance du coût (moyenne sur tous les permutations possibles de k éléments), le coût de l’algorithme est en O\pa{k \log_n k}.

R-tree ou Rectangular Tree#

L’arbre R-tree est l’adaptation du mécanisme du B+ tree au cas multidimensionnel (voir [Guttman1984]). La construction de cet arbre peut se faire de manière globale - construction de l’arbre sachant l’ensemble de points à classer - ou de manière progressive - insertion des points dans l’arbre les uns à la suite des autres -. Toutefois, ces méthodes sont resteintes à des espaces vectoriels.

Il n’existe pas une seule manière de construire un R-tree, les noeuds de ces arbres suivent toujours la contrainte des B+ tree qui est d’avoir un père et au plus n fils. Les R-tree ont la même structure que les B+ tree ôtée de leurs contraintes d’ordonnancement des fils. De plus, ces arbres organisent spatialement des rectangles ou boîtes en plusieurs dimensions comme le suggère la figure précédente. Les boîtes à organiser seront nommés les objets, ces objets sont ensuite regroupés dans des boîtes englobantes. Un noeud n d’un R-tree est donc soit une feuille, auquel cas la boîte qu’il désigne est un objet, dans ce cas, il n’a aucun fils, soit le noeud désigne une boîte englobante B\pa{n}. On désigne par \mathcal{B} l’ensemble des boîtes d’un espace vectoriel quelconque et v\pa{b} désigne son volume. Pour un noeud n non feuille, A\pa{n} désigne l’ensemble des descendants de ce noeud. B\pa{n} est défini par :

B\pa{n} = \arg \min \acc{ v\pa{b} \sac b \in \mathcal{B} \text{ et } \forall n' \in A\pa{n'}, \; B\pa{n'} \subset B\pa{n} }

La recherche dans un R-tree consiste à trouver tous les objets ayant une intersection avec une autre boîte ou fenêtre W, soit l’ensemble L :

L = \acc{ B\pa{n} \sac B\pa{n} \text{ est un objet et } B\pa{n} \cap W \neq \emptyset }

Cet ensemble est construit grâce à l’algorithme suivant :

Les notations sont celles utilisées dans ce paragraphe. On désigne par r le noeud racine d’un R-tree. Soit n un noeud, on désigne par F\pa{n} l’ensemble des fils de ce noeud.

initialisation

L \longleftarrow 0 | N \longleftarrow \acc{r}

itération

while N \neq \emptyset
for n in 1..N
if W \cap B\pa{n} \neq \emptyset
N \longleftarrow N \cup F\pa{n}
if B\pa{n} est un objet
L \longleftarrow B\pa{n}

L est l’ensemble cherché.

Il reste à construire le R-tree, opération effectuée par la répétition successive de l’algorithme suivant permettant d’insérer un objet dans un R-tree.

Algorithme A4 : insertion d’un objet dans un R-tree

Les notations utilisées sont les mêmes que celles de l’algorithme de recherche. On cherche à insérer l’object E désigné par son noeud feuille e. On suppose que l’arbre contient au moins un noeud, sa racine r. On désigne également par p\pa{n} le père du noeud n. Chaque noeud ne peut contenir plus de s fils. On désigne par v^*\pa{G} = \min \acc{ P \sac P \in \mathcal{B} \text{ et } \cup_{g \in G} B\pa{g}  \subset P }.

sélection du noeud d’insertion

n^* \longleftarrow r
tant que n^* n’est pas un noeud feuille
On choisit le fils f de n^*
qui minimise l’accroissement v_f - v\pa{B\pa{f}}
du volume avec v_f défini par :
v_f = \min \acc{ v\pa{P} \sac P \in \mathcal{B} \text{ et } B\pa{f} \cup B\pa{e}  \subset P }
n^* \longleftarrow f

ajout du noeud

Si p\pa{n^*} a moins de s fils, alors le noeud e devient le fils de p\pa{n^*} et B\pa{p\pa{n^*}} est mis à jour d’après l’étape précédente. L’insertion est terminée. Dans le cas contraire, on sépare découpe le noeud p\pa{n^*} en deux grâce à l’étape suivante.

découpage des noeuds

L’objectif est de diviser le groupe G composé de s+1 noeuds en deux groupes G_1 et G_1. Tout d’abord, on cherche le couple \pa{n_1,n_2} qui minimise le critère d = v^*\pa{\acc{n_1,n_2}} - v\pa{B\pa{n_1}} - v\pa{B\pa{n_2}} alors : G_1 \longleftarrow n_1, G_2 \longleftarrow n_2 et G \longleftarrow G - G_1 \cup G_2

tant que G \neq \emptyset
On choisit un noeud n \in G, on détermine i^*
tel que :math:`vpa{acc{n} cup G_i} - vpa{G_i}$ soit minimal.
G \longleftarrow G - \acc{n}
G_{i^*} \longleftarrow G_{i^*} \cup \acc{n}

Si la recherche est identique quel que soit l’arbre construit, chaque variante de la construction de l’arbre tente de minimiser les intersections des boîtes et leur couverture. Plus précisément, l’étape qui permet de découper les noeuds est conçue de manière à obtenir des boîtes englobantes de volume minimale et/ou d’intersection minimale avec d’autres boîtes englobantes. L’algorithme R+~Tree (voir [Sellis1987]) essaye de minimiser les intersections entre boîtes et les objets à organiser sont supposés n’avoir aucune intersection commune. La variante R* tree (voir [Beckmann1990]) effectue un compromis entre l’intersection et la couverture des boîtes englobantes. L’algorithme X-tree (voir [Berchtold1996]) conserve l’historique de la construction de l’arbre ce qui lui permet de mieux éviter les intersections communes entre boîtes. Ces techniques appartiennent à une classe plus larges d’algorithmes de type Branch and Bound.

LAESA#

Cet algorithme permet de chercher les plus proches voisins dans un ensemble inclus dans un espace métrique quelconque. Il s’appuie sur l’inégalité triangulaire. L’algorithme LAESA ou Linear Approximating Eliminating Search Algorithm, (voir [Rico-Juan2003]) consiste à éviter un trop grand nombre de calculs de distances en se servant de distances déjà calculées entre les éléments de E et un sous-ensemble B inclus dans E contenant des pivots. La sélection des pivots peut être aléatoire ou plus élaborée comme celle effectuée par l’algorithme qui suit, décrit dans l’article [Moreno2003].

Algorithme A5 : LAESA : sélection des pivots

Soit E = \ensemble{y_1}{y_N} un ensemble de points, on cherche à déterminer un sous-ensemble de pivots B = \ensemble{p_1}{p_P} \subset E.

initialisation