Méthode des k plus proches voisins

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

En intelligence artificielle, la méthode des k plus proches voisins est une méthode d’apprentissage supervisé. En abrégé k-NN ou KNN, de l'anglais k-nearest neighbor.

Dans ce cadre, on dispose d’une base de données d'apprentissage constituée de N couples « entrée-sortie ». Pour estimer la sortie associée à une nouvelle entrée x, la méthode des k plus proches voisins consiste à prendre en compte (de façon identique) les k échantillons d'apprentissage dont l’entrée est la plus proche de la nouvelle entrée x, selon une distance à définir.

Par exemple, dans un problème de classification, on retiendra la classe la plus représentée parmi les k sorties associées aux k entrées les plus proches de la nouvelle entrée x.

En reconnaissance de forme, l'algorithme des k plus proches voisins (k-NN) est une méthode non paramétrique utilisée pour la classification et la régression. Dans les deux cas, il s'agit de classer l'entrée dans la catégorie à laquelle appartient les k plus proches voisins dans l'espace des caractéristiques identifiées par apprentissage. Le résultat dépend si l'algorithme est utilisé à des fins de classification ou de régression :

  • en classification k-NN , le résultat est une classe d'appartenance. Un objet d'entrée est classifié selon le résultat majoritaire des statistiques de classes d'appartenance de ses k plus proches voisins, (k est un nombre entier positif généralement petit). Si k = 1, alors l'objet est assigné à la classe d'appartenance de son proche voisin.
  • en régressionk-NN, le résultat est la valeur pour cet objet. Cette valeur est la moyenne des valeurs des k plus proches voisins.

La méthode k-NN est basée sur l'apprentissage préalable, ou l'apprentissage faible, ou la fonction est évaluée localement, le calcul défintif étant effectué à l'issue de la classification. L'algorithme k-NN est parmi les plus simples des algorithmes de machines apprenantes.

Que ce soit pour la classification ou la régression, une technique efficace peut être utilisée pour pondérer l'influence contributive des voisinages, ainsi les plus proches voisins contribuent-ils plus à la moyenne que les voisins plus éloignés. Pour exemple, un schéma courant de pondération consiste à donner à chaque voisin une pondération de 1/d, ou d est la distance de l'élément, à classer ou à pondérer, de ce voisin.

Les voisins sont pris depuis un ensemble d'objets pour lesquels la classe (en classification k-NN) ou la valeur (pour une régression k-NN) est connue. Ceci peut être considéré comme l'ensemble d'entraînement pour l'algoritme, bien qu'un entraînement explicite ne soit pas particulièrement requis.

Une particularité des algorithmes k-NN est d'être particulièrement sensible à la structure locale des données.

Hypothèse statistique et choix de k[modifier | modifier le code]

Suppose que nous ayons des paires de données prenant leur valeur dans l'ensemble ,ou Y est la classe de labellisation de X, tel que for (et une loi de distribution de probabilités ). Étant donnée une norme quelconque sur et un point , soit , est un ré-arrangement des données d'apprentissage tel que les couples soient les plus proches voisins appartenant à une même classe respectant la métrique (classe de population proposant k éléments dans le voisinage). L'algorithme nécessite de connaître k, le nombre de voisins à considérer. Une méthode classique pour avoir cette valeur est la validation croisée (cross validation).

Algorithme[modifier | modifier le code]

Exemple de classification k-NN . L'échantillon de test (cercle vert) pourrait être classé soit dans la première classe de carré bleu ou la seconde classe de triangles rouges. Si k = 3 (cerle en ligne pleine) il est affecté à la seconde classe car il y a deux triangles et seulement un carré dans le cercle considéré. Si k = 5 (cercle en ligne pointillée) il est assigné à la première classe (3 carrés face à deux triangles dans le cercle externe).

Les exemples d'apprentissage sont des vecteurs dans un un espace multidimensionnel de caractéristiques, chacun avec un label de classe d'appartenance. La phase d'apprentissage de l'algorithme consiste seulement dans le stockage des vecteurs caractéristiques et des labels de classe des échantillons d'apprentissage.

Dans la phase de classification, k est une constante définie par l'utilisateur, et un vecteur non labellisé (une requête ou un point de test) est classé en lui affectant le label qui est le plus fréquent parmi les k échantillons d'entraînement les plus proches du point à classer.

La distance métrique commune pour des variables continues est la distance Euclidienne. Pour des variables discrètes, telles que dans de la classification de texte, une autre métrique peut être utilisée, telle que la métrique de recouvrement (ou la distance de Hamming). Dans le contexte de microtableau de données génétiques, par exemple, k-NN a aussi été employé avec des coefficients de corrélation de Pearson et Spearman[1]. Fréquemment, la précision de la classification k-NN peut être améliorée de manière significative si la métrique de distance est apprise avec des algorithmes spécialisés tels que Plus proche voisin à grande tolérance or Analyse des composantes de voisinage.

Une faiblesse de la classification basique par "vote majoritaire" apparaît quand la distribution de classe est assymétrique. C'est-à-dire, des exemples d'une classe plus fréquente tendent à dominer la prédiction de classification du nouvel entrant, car elle serait statistiquement plus fréquente parmi les k plus proches voisins par définition[2]. Un moyen de surmonter cette difficulté est de pondérer la classification, en prenant en compte la distance du nouvel entrant à chacun de ses k plus proches voisins. La classe (ou la valeur en cas de régression) de chacun de ces k plus proches voisins est multipliée par une pondération proportionnnelle à l'inverse de la distance de ce voisin au point à classer. Une autre façon de s'affranchir de cette assymétrie se fait par abstraction dans la représentation des données. Par exemple, dans une Carte auto adaptative (SOM), chaque nœud est représentatif du centre de gravité (barycentre) d'un amas de points similaire, indépendamment de leur densité dans les données originales d'apprentissage . K-NN peut être employé pour les SOM.

Notes et références[modifier | modifier le code]

  1. P. A. Jaskowiak et R. J. G. B. Campello, « Comparing Correlation Coefficients as Dissimilarity Measures for Cancer Classification in Gene Expression Data », sur http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.208.993, Brazilian Symposium on Bioinformatics (BSB 2011) (consulté le 16 octobre 2014), p. 1–8
  2. D. Coomans et D.L. Massart, « Alternative k-nearest neighbour rules in supervised pattern recognition : Part 1. k-Nearest neighbour classification by using alternative voting rules », Analytica Chimica Acta, vol. 136,‎ , p. 15–27 (DOI 10.1016/S0003-2670(01)95359-0)

Voir aussi[modifier | modifier le code]