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.
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 à , l’élément à classer, le label de l’élément le plus proche dans l’ensemble . Ceci mène à l’algorithme de classification suivant :
Algorithme A1 : 1-PPV ou plus proche voisin
Soit un ensemble d’éléments d’un espace métrique quelconque, soit les classes associées à chacun des éléments de . On note la distance définie sur l’espace métrique . Soit un élément à classer, on cherche à déterminer la classe associée à . On définit comme étant :
Alors .
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 à la classe la plus représentée parmi ses plus proches voisins.
Algorithme A2 : k-PPV ou k-plus proches voisins
Soit un ensemble d’éléments d’un espace métrique quelconque, soit les classes associées à chacun des éléments de . On note la distance définie sur l’espace métrique . est une fonction strictement positive mesurant la ressemblance entre et . Soit un élément à classer, on cherche à déterminer la classe associée à . On définit l’ensemble incluant les -plus proches voisins de , cet ensemble vérifie :
On calcule les occurrences de chaque classe dans l’ensemble :
(1)#
On assigne alors à la classe :math:`c(x)$ choisie dans l’ensemble :
Dans sa version la plus simple, la fonction utilisée lors du calcul de la contribution (1) est constante. Mais il est possible de lui affecter une valeur tenant compte de la proximité entre et . La table suivante donne quelques exemples de contributions possibles.
Exemple de contribution pour l’algorithme des k-ppv. Ces fonctions sont toutes décroissantes (strictement ou non) par rapport à la distance . L’inconvénient majeur de la méthode des plus proches voisins est sa longueur puisqu’elle implique le calcul des distances entre et chacun des éléments de l’ensemble . 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 appartiennent à un espace vectoriel et ont donc des coordonnées. Les suivant traitent le cas où les points 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 fils.
Définition D1 : B+ tree
Soit un B+ tree, soit un noeud de , il contient un vecteur avec et . Ce noeud contient aussi exactement noeuds fils notés . On désigne par l’ensemble des descendants du noeud et . Le noeud vérifie :
Cet arbre permet de trier une liste de nombres, c’est une généralisation du tri quicksort pour lequel . 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 éléments), le coût de l’algorithme est en .
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 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 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 . On désigne par l’ensemble des boîtes d’un espace vectoriel quelconque et désigne son volume. Pour un noeud non feuille, désigne l’ensemble des descendants de ce noeud. est défini par :
La recherche dans un R-tree consiste à trouver tous les objets ayant une intersection avec une autre boîte ou fenêtre , soit l’ensemble :
Cet ensemble est construit grâce à l’algorithme suivant :
Algorithme A3 : recherche dans un R-tree
Les notations sont celles utilisées dans ce paragraphe. On désigne par le noeud racine d’un R-tree. Soit un noeud, on désigne par l’ensemble des fils de ce noeud.
initialisation
itération
while
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 désigné par son noeud feuille . On suppose que l’arbre contient au moins un noeud, sa racine . On désigne également par le père du noeud . Chaque noeud ne peut contenir plus de fils. On désigne par .
sélection du noeud d’insertion
ajout du noeud
Si a moins de fils, alors le noeud devient le fils de et 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 en deux grâce à l’étape suivante.
découpage des noeuds
L’objectif est de diviser le groupe composé de noeuds en deux groupes et . Tout d’abord, on cherche le couple qui minimise le critère alors : , et
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 et un sous-ensemble inclus dans 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 un ensemble de points, on cherche à déterminer un sous-ensemble de pivots .
initialisation
calcul de la fonction
mise à jour de
L’algorithme LAESA utilise les pivots pour diminuer le nombre de calculs en utilisant l’inégalité triangulaire. Par exemple, soit un élément à classer, un pivot, un point du nuage. On suppose qu’on connaît , et la distance du point à un autre point du nuage. L’inégalité triangulaire permet d’affirmer que si : , alors il n’est pas nécessaire de calculer la distance pour affirmer que . L’élément ne peut être l’élément le plus proche.
Algorithme A6 : LAESA
Soit un ensemble de points, un ensemble de pivots inclus dans . On cherche à déterminer le voisinage de inclus dans vérifiant :
On suppose que la matrice a été calculée préalablement comme suit :
initialisation
recherche du plus proche élément
Résultats théoriques#
L’article [Farago1993] démontre également qu’il existe une majoration du nombre moyen de calcul de distances pour peu que la mesure de l’espace contenant l’ensemble et l’élément soit connue et que l’ensemble des pivots vérifie :
L’algorithme développé dans [Farago1993] permet de trouver le point de plus proche d’un élément dans un ensemble :math:`E = ensemble{x_1}{x_N}`selon l’algorithme suivant :
Algorithme A7 : plus proche voisin d’après [Farago1993]_
Soit et . Soit , un élément quelconque. On suppose que les valeurs ont été préalablement calculées.
initialisation
On calcule préalablement les coefficients :
élaguage
On définit . Puis on construit l’ensemble .
plus proche voisin
Le plus proche voisin est défini par : .
Et un petit théorème.
Théorème T1 : [Farago1993]_ 1
Les notations sont celles de l’algorithme précédent. Il retourne le plus proche voisin de inclus dans . Autrement dit, .
Théorème T2 : [Farago1993]_ 2
Les notations sont celles du même algorithme. On définit une mesure sur l’ensemble , désigne la boule de centre et de rayon , une variable aléatoire, de plus :
On suppose qu’il existe et une fonction tels que :
La convergence doit être uniforme et presque sûre. On note également le nombre de calculs de dissimilarité effectués par l’algorithme où est le nombre d’élément de , désigne toujours le nombre de pivots, alors :
Implémentation#
La classe NuagePoints
implémente
les nuages de points sans optimisation. Il utilise la même interface que
sklearn.neighbors.NearestNeighbors. La second classe
NuagePointsLeasa
.
<<<
import numpy
from mlstatpy.ml.kppv_laesa import NuagePointsLaesa
X = numpy.array([[0, 0], [3, 3], [1, 1]])
nuage = NuagePointsLaesa(2)
nuage.fit(X)
dist, indices = nuage.kneighbors(X)
print("distance", dist)
print("indices", indices)
>>>
distance [0. 0. 0.]
indices [0 1 2]
Bilbiographie#
The R$^*$-tree: an efficient and robust access method for points and rectangles, N. Beckmann, H. P. Kriegel, P. Schneider, B. Seeger, Proceedings of SIGMOD conference, Atlantic City, pages 322-331
The X-Tree: An index structure for high dimension data, S. Berchtold, D. A. Keim, H. P. Kriegel, Proceedings of the 22nd Internation Conference on Very Large Databases, Bombay, India
Fast Nearest-Neighbor Search in Dissimilarity Spaces, A. Farago, T. Linder, G. Lugosi, IEEE Transactions on Pattern Analysis and Machine Intelligence, volume 15(9), pages 957-962
R-Trees: A Dynamic Index Structure for Spatial Searching, A. Guttman, Proceedings ACM SIGMOD, pages 47-57
A modification of the LAESA algorithm for approximated k-NN classification, Francisco Moreno-Seco, Luisa Mico, Jose Oncina, Pattern Recognition Letters, volumne 24, pages 47-53
Comparison of AESA and LAESA search algorithms using string and tree-edit-distances, J. R. Rico-Juan, L. Mico, Pattern Recognition Letters, volume 24, pages 1417-1426
The R+tree - a Dynamic Index for Multi-Dimensional Objects, T. Sellis, N. Roussopoulos, C. Faloutos, Proceedings of the 13th VLDB conference, pages 507-518