Méthode des k plus proches voisins

On suppose des couples de données ${\displaystyle (X_{1},Y_{1}),(X_{2},Y_{2}),\dots ,(X_{n},Y_{n})}$ prenant leur valeur dans l'ensemble ${\displaystyle \mathbb {R} ^{d}\times \{1,2\}}$, où Y est la classe de labellisation de X, tel que ${\displaystyle X|Y=r\sim P_{r}}$ pour ${\displaystyle r=1,2}$ (et une loi de distribution de probabilités ${\displaystyle P_{r}}$). Étant donnée une norme quelconque ${\displaystyle \|\cdot \|}$ sur ${\displaystyle \mathbb {R} ^{d}}$ et un point ${\displaystyle x\in \mathbb {R} ^{d}}$, soit ${\displaystyle (X_{(1)},Y_{(1)}),(X_{(n)},Y_{(n)})}$, un ré-arrangement des données d'apprentissage tel que les couples ${\displaystyle \|X_{(1)}-x\|\leq \dots \leq \|X_{(k)}-x\|}$ 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).

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 (cercle 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 affecté à la première classe (3 carrés face à deux triangles dans le cercle externe).

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

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

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

Une faiblesse de la classification dans sa version de base par vote majoritaire apparaît quand la distribution de classe est asymé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[4]. 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 proportionnelle à l'inverse de la distance de ce voisin au point à classer. Une autre façon de s'affranchir de cette asymé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 barycentre d'un amas de points similaires, indépendamment de leur densité dans les données originales d'apprentissage. La méthode k-NN peut être employée pour les SOM.

• Recherche des plus proches voisins

• Portail de l'informatique théorique
• Portail des probabilités et de la statistique