L'algorithme des k plus proches voisins (k-Nearest Neighbors ou KNN) est un algorithme d'apprentissage automatique supervisé utilisé pour la classification.
Le choix de la valeur $k$ est crucial : elle doit être assez grande pour éviter de suivre le bruit, mais pas trop pour ne pas lisser les frontières entre les classes. On choisit souvent un nombre impair pour éviter les égalités.
Pour mesurer la proximité, on utilise généralement la distance euclidienne entre deux points $A(x_A, y_A)$ et $B(x_B, y_B)$ :
$d(A, B) = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$
Imaginons que nous voulions classer un fruit Inconnu ($160\text{g}$, $7\text{cm}$ de largeur) parmi des Pommes et des Oranges déjà répertoriées.
| Voisin | Masse (g) | Largeur (cm) | Label | Distance à l'Inconnu |
|---|---|---|---|---|
| n°1 | 150 | 7.2 | Pomme | 10.00 |
| n°2 | 170 | 7.1 | Orange | 10.01 |
| n°3 | 158 | 6.8 | Pomme | 2.01 |
| n°4 | 165 | 7.5 | Orange | 5.02 |
| n°5 | 162 | 7.0 | Pomme | 2.00 |
Complétez le code Python pour implémenter l'algorithme KNN.
On veut calculer la distance entre deux points ayant un nombre quelconque de caractéristiques. Pour cela, nous utiliserons la fonction sqrt() du module math.
On veut créer une liste de couples (distance, label) pour un point inconnu cible.
On trie les distances et on garde les $k$ plus petites.
On compte quelle classe apparaît le plus souvent parmi les voisins.