L'algorithme kNN

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

Note

L'algorithme kNN est un algorithme de classification et d'apprentissage supervisé:

• Classification: on cherche à regrouper les individus de la population étudiée 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'ordinateur pourra classer les nouvelles données.

L'idée générale est la suivante:

• On dispose d'une population statistique avec des mesures 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 ses attributs avec ceux des individus déjà classés.

Prenons l'exemple d'une population d'éléphants répartis en deux classes: les éléphants d'Afrique et les éléphants d'Asie. Les éléphants d'Afrique ont des oreilles plus grandes que les éléphants d'Asie, l'éléphant d'Afrique est plus grand que l'éléphant d'Asie. Les attributs utilisés pourraient donc être: taille de l'éléphant, taille des oreilles.
Arrive un nouvel individu. 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.

Le problème est que, 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...

Bref, les attributs choisis ne permettent pas nécessairement de conclure de façon évidente. On va donc comparer notre nouvel individu à tous les individus présents. Et par exemple retenir les k=3 éléphants ayant des attributs les "plus proches" de notre individu (on a choisi k=3 mais on peut choisir k=4 ou une autre valeur de k).

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

La décision n'est évidemment pas absolument fiable (et il peut arriver qu'en changeant la valeur de k, on change de conclusion!) mais 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.