Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== 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.

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

<code python>
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
</code>

===Recherche des k plus proches voisins et prédiction de la catégorie===
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.

<code python>
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
</code>