k-Nearest Neighbours

k-Nearest Neighbours (k-NN voire KNN ou méthode des k plus proches voisins) : k-NN est un algorithme standard de classification qui repose exclusivement sur le choix de la métrique de classification. Il est « non paramétrique » (seul k doit être fixé) et se base uniquement sur les données d’entraînement.

L’idée est la suivante : à partir d’une base de données étiquetées, on peut estimer la classe d’une nouvelle donnée en regardant quelle est la classe majoritaire des k données voisines les plus proches (d’où le nom de l’algorithme). Le seul paramètre à fixer est k, le nombre de voisins à considérer (voir figure).

Les métriques les plus souvent choisies sont la distance usuelle dite euclidienne (comme dans la figure) et la distance de Mahalanobis (qui tient compte de la variance – du point de vue statistique – et de la corrélation entre les données). Bien que l’algorithme puisse fonctionner avec ces métriques par défaut, il est généralement bien meilleur quand il est utilisé avec une métrique adaptée aux données, métrique qui peut être calculée à partir d’heuristiques connues liées au problème (par exemple la distance euclidienne pondérée).

Les points faibles de cet algorithme sont : d’une part, son coût en puissance de calcul (pour prédire l’image d’un nouveau point, on doit calculer sa distance à tous les autres), d’autre part le fait de devoir conserver toutes les données d’entraînement en mémoire (k-NN  convient donc plutôt aux problèmes d’assez petite taille).Il est également important de noter que cet algorithme est vulnérable à la « curse of dimensionality » : le nombre de données nécessaires pour avoir un bon estimateur croît potentiellement de manière exponentielle avec la dimension, autrement dit avec la complexité de la représentation des données. Pour ces raisons, k-NN est assez peu utilisé dans sa forme première mais plutôt avec des versions améliorées qui limitent partiellement ces défauts (comme dans l’exemple [1]).

A remarquer que l’algorithme peut aussi être adapté pour la régression.

[1] Wu, Y., Ianakiev, K., & Govindaraju, V. (2002). Improved k-nearest neighbor classification. Pattern recognition, 35(10), 2311-2318.

Quelle est la classe du point vert ? Celle des triangles rouges (délimitée par le cercle continu) ou celle des carrés bleus (cercle tracé en pointillés) ? Si le nombre de plus proches voisins, k, est fixé à 3,  la classe du point vert est celle des triangles rouges, car ces derniers sont au nombre de 2 contre un seul carré bleu. Si k vaut 5, la classe du point vert est celle des carrés bleus, au nombre de 3 contre 2 triangles rouges. (Source de l’image : Wikipédia CC BY-SA 3.0)