Méthode des k plus proches voisins

Adrien Guille, Université Lyon 2

Partie théorique

Partie pratique

Formulation du modèle

Soit le jeu de données composé de paires , avec la description d'un individu selon descripteurs, sous la forme d'un vecteur réel de taille , et la classe d'appartenance de cet individu parmi classes possibles :

L'espace de représentation des observations doit être muni d'une distance, nécessaire à la construction du voisinage d’une nouvelle observation. La distance est une fonction, , respectant les 3 propriétés suivantes :

Typiquement, lorsque l’espace de représentation des observations est , on utilise la distance euclidienne :

La classe d'une nouvelle observation est déterminée d'après la distribution des classes des plus proches voisins dans , c’est-à-dire les observations minimisant la distance avec . Il s'agit simplement du mode de cette distribution, autrement dit la classe la plus fréquente parmi ses voisins. Cette méthode repose donc sur la règle de décision suivante :

désigne les plus proches voisins de dans au sens de la distance choisie, et où est le delta de Kronecker, défini ainsi :

Mise en œuvre

Les figures 1 et 2 illustrent comment la méthode des k plus proches voisins résoud une tâche de classification supervisée binaire () dans , selon la distance euclidienne et pour . La figure 1 montre comment (en 3 étapes, de gauche à droite) une nouvelle observation est attribuée à la classe 2, son voisinnage étant composé de 3 observations appartenant à la classe 2. La figure 2 montre comment une nouvelle observation est attribuée à la classe 2, son voisinnage étant composé de 2 observations appartenant à la classe 2 et d'une observation appartenant à la classe 1.

Figure 1 : Classification d'une nouvelle observation : les 3 plus proches voisins appartiennent à la classe 2.

Figure 2 : Classification d'une nouvelle observation : 2 des 3 plus proches voisins appartiennent à la classe 2.

K plus proches voisins avec R et le paquet «caret»

Le code ci-dessous montre comment, à l'aide du paquet «caret», construire un classifieur basé sur la méthode des k plus proches voisins. Les données décrivent 150 iris, selon 4 descripteurs :

La classe, Variété, a 3 modalités ('Iris-setosa' ou 'Iris-versicolor' ou 'Iris-virginica').