L'algorithme $k$-NN

L'algorithme $k$-NN (k-nearest neighbors) ou kppv (algorithme des k-plus proches voisins) est un algorithme (parmi les plus élémentaires) utilisé en intelligence artificielle.

Heuristique

L'algorithme $k$-NN est un algorithme de classification et d'apprentissage supervisé :

• Classification : les éléments de la population étudiée ont un attribut qualitatif dont la valeur permet de lesregrouper en classes « homogènes ».

• Apprentissage supervisé : le programmeur ne donne pas de « critère explicite » pour la classification mais des données de référence déjà réparties dans les classes. C'est par comparaison avec ces données que l'algorithme permettra de « prédire » la classe ce chacune de ces nouvelles données.

Principe

• On dispose d'une population statistique (données connues et représentatives) avec des mesures quantitatives (valeurs numériques) sur certains attributs des individus de cette population.
• Les individus se répartissent en plusieurs classes, plus ou moins bien caractérisées par les valeurs des attributs.
• Pour décider de la classe d'un nouvel individu, on compare les valeurs de ses attributs avec ceux des individus déjà classés les plus proches de lui.

Exemple

Une population d'éléphants est répartie en deux classes : les éléphants d'Afrique et les éléphants d'Asie. Les éléphants d'Afrique ont des oreilles plus imposantes que les éléphants d'Asie et ils sont plus grands.

Les attributs utilisés pour effectuer des comparaisons pourraient donc être :

• la hauteur de l'éléphant ;
• la taille de ses oreilles.

Arrive un nouvel éléphant. On ne sait pas a priori de quelle classe il relève. Pour le décider, on décide de comparer les valeurs de ses attributs (hauteur de l'éléphant, taille des oreilles) à ceux de la population déjà répartie en classe.

Problème

Parmi les éléphants d'Asie il y en a des plus gros (qui se rapprochent donc de l'éléphant d'Afrique) ou avec de plus grandes oreilles. De même les éléphants d'Afrique ne sont pas uniformes, il en existe des plus petits, etc...

Ainsi, les attributs choisis ne permettent pas nécessairement de conclure de façon évidente. Il faut donc comparer ce nouvel éléphant à chacun des individus présents et retenir ceux qui auront des attributs les « plus proches » de notre éléphant. Mais lesquels retenir ?

C'est là que l'entier $k$ entre compte. Par exemple, en définissant $k=3$, on retiendra les 3 individus aux attributs « les plus proches » de ceux du nouvel éléphant. On appelle ces individus des voisins.

En conclusion, si, parmi les $k$ individus les plus proches de notre nouvel éléphant, il y a plus d'éléphants d'Afrique que d'éléphants d'Asie, alors on décide qu'il s'agit d'un éléphant d'Afrique.

Bilan

La décision n'est évidemment pas absolument fiable (et il peut arriver qu'en changeant la valeur de $k$, on change de conclusion !). Toutefois, avec une population de départ suffisamment importante et quelques heuristiques pour le choix de $k$, le principe donne de bons résultats dans un certain nombre de contextes.