Algorithme des k plus proches voisins

L'algorithme des k plus proches voisins (k-NN, pour “k Nearest Neighbors”) est un algorithme de classification. Pour prédire la catégorie d'un nouvel élément, on calcule sa distance avec tous les éléments déjà connus (les données d'apprentissage), puis on regarde les k éléments les plus proches : la catégorie la plus représentée parmi ces k voisins est attribuée au nouvel élément.

On utilise généralement la distance euclidienne pour mesurer l'écart entre deux points.

from math import sqrt
 
def distance(point1, point2):
    """
    Objectif :
    Calcule la distance euclidienne entre deux points.
    Entrée :
    point1 : tuple : les coordonnées du premier point, ex : (x1, y1)
    point2 : tuple : les coordonnées du deuxième point, ex : (x2, y2)
    Sortie :
    resultat : float : la distance euclidienne entre les deux points
    """
    somme = 0
    for i in range(len(point1)):  #additionne le carré de l'écart pour chaque coordonnée
        somme = somme + (point1[i] - point2[i])**2
    resultat = sqrt(somme)
    return resultat

On calcule la distance entre le nouveau point et chaque point connu, on trie les résultats, on garde les k plus proches, puis on renvoie la catégorie la plus fréquente parmi eux.

donnees = [
    ((1, 1), "rouge"),
    ((2, 1), "rouge"),
    ((1, 2), "rouge"),
    ((6, 5), "bleu"),
    ((7, 5), "bleu"),
    ((6, 6), "bleu")
]
 
def k_plus_proches_voisins(nouveau_point, donnees, k):
    """
    Objectif :
    Prédit la catégorie d'un nouveau point grâce à l'algorithme des k plus proches voisins.
    Entrée :
    nouveau_point : tuple : les coordonnées du point à classer
    donnees       : list : liste de tuples (coordonnees, categorie) représentant les données connues
    k             : int : le nombre de voisins à prendre en compte
    Sortie :
    categorie_predite : str : la catégorie prédite pour le nouveau point
    """
    distances = []
    for coordonnees, categorie in donnees:  #calcule la distance entre le nouveau point et chaque point connu
        d = distance(nouveau_point, coordonnees)
        distances.append((d, categorie))
 
    distances_triees = sorted(distances)  #trie les distances de la plus petite à la plus grande
    k_voisins = distances_triees[:k]      #ne garde que les k plus proches voisins
 
    categories = []
    for d, categorie in k_voisins:  #récupère uniquement la catégorie de chaque voisin
        categories.append(categorie)
 
    categorie_predite = max(set(categories), key=categories.count)  #catégorie la plus fréquente parmi les voisins
    return categorie_predite
 
print(k_plus_proches_voisins((2, 2), donnees, 3))  #affiche rouge