1Principe de l'algorithme

L'algorithme des k plus proches voisins (k-Nearest Neighbors ou KNN) est un algorithme d'apprentissage automatique supervisé utilisé pour la classification.

Le principe est simple :
  • Soit un point $X$ dont on ne connaît pas la classe.
  • On calcule la distance entre $X$ et tous les points dont on connaît déjà la classe (données d'entraînement).
  • On sélectionne les $k$ points les plus proches (les "voisins").
  • On regarde la classe majoritaire parmi ces $k$ voisins : c'est la classe prédite pour $X$.

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.

2Définition de la distance

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}$

def distance_euclidienne(p1, p2): """Calcule la distance entre deux points p1(x,y) et p2(x,y)""" return ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)**0.5 # Test de la distance assert distance_euclidienne((0,0), (3,4)) == 5.0 print("Calcul de distance OK !")

3Exemple détaillé : Classification avec $k=3$

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
Analyse pour $k=3$ :
  1. On trie par distance : n°5 (2.00), n°3 (2.01), n°4 (5.02).
  2. Les 3 plus proches sont : Pomme (n°5), Pomme (n°3) et Orange (n°4).
  3. Majorité : 2 Pommes contre 1 Orange.
  4. Conclusion : Le fruit est classé comme Pomme.

4Exercices interactifs

Complétez le code Python pour implémenter l'algorithme KNN.

Exercice 1 : Fonction de distance multi-dimensionnelle

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.

from math import def distance(a, b): # a et b sont des listes [x1, x2, x3, ...] somme = 0 for i in range(len(a)): somme += (a[i] - b[i])**2 return # Test d'assertion assert distance([1, 1], [4, 5]) == 5.0 assert distance([0, 0, 0], [1, 1, 1]) == sqrt()
Exercice 2 : Liste des distances avec labels

On veut créer une liste de couples (distance, label) pour un point inconnu cible.

def liste_distances(donnees, cible): # donnees = [([x1, x2], "classe"), ...] L = [] for caract, label in donnees: d = L.append() return L # Exemple dataset = [([1, 2], "A"), ([4, 6], "B")] res = liste_distances(dataset, [1, 2]) assert res[0][0] ==
Exercice 3 : Sélection des k voisins

On trie les distances et on garde les $k$ plus petites.

def extraire_k_voisins(distances_labellisees, k): # On trie la liste par distance (premier élément du tuple) triees = sorted(distances_labellisees, key=lambda x: ) # On retourne les k premiers labels resultat = [] for i in range(): resultat.append() return resultat # Test input_dist = [(0.5, "P"), (2.1, "O"), (1.2, "P")] assert extraire_k_voisins(input_dist, 2) ==
Exercice 4 : Détermination de la classe

On compte quelle classe apparaît le plus souvent parmi les voisins.

def vote_majoritaire(voisins): comptage = {} for v in voisins: if v in comptage: comptage[v] += 1 else: comptage[v] = # On cherche le label avec le max d'occurrences best_label = None max_votes = -1 for label, nb in : if nb > max_votes: max_votes = best_label = return best_label # Test assert vote_majoritaire(["A", "B", "A", "C"]) ==
Exercice 5 : La fonction KNN complète
def knn(donnees, cible, k): # 1. Calculer toutes les distances dists = # 2. Extraire les labels des k plus proches voisins_labels = # 3. Vote majoritaire return # Jeu de test final data = [([1, 1], "A"), ([2, 2], "A"), ([10, 10], "B")] assert knn(data, [3, 3], 1) == "A" assert knn(data, [9, 9], 1) ==