Retour

Algorithme des k plus proches voisins

Principe

Pour prédire la classe d’un nouvel élément, il faut des données :

• Un échantillon de données ;
• Un nouvel élément dont on connaît les caractéristiques et dont on veut prédire le type ;
• La valeur de k, le nombre de voisins étudiés.

Une fois ces données modélisées, nous pouvons formaliser l'algorithme de la façon suivante :

1. Trouver, dans l’échantillon, les k plus proches voisins de l'élément à déterminer.
2. Parmi ces proches_voisins, trouver la classification majoritaire.
3. Renvoyer la classification_majoritaire comme type cherché de l'élément.

Algorithme

· Données :

• Une table de données de taille n ;
• Une donnée cible ;
• Un entier k plus petit que n ;
• Une règle permettant de calculer la distance entre deux données.

· Algorithme :

• Trier les données de la table selon la distance croissante avec la donnée cible.
• Créer la liste des k premières données de la table triée.
• Renvoyer cette liste.

Implémentation en Python

🐍 Script Python

def k_plus_proches_voisins(table, cible, k) :
  """Renvoie la liste des k plus proches voisins de la cible"""
  def distance_cible(donnee) :
    """ renvoie la distance entre la donnée et la cible"""
    distance = abs(donnee[1]-cible[0])+abs(donnee[2]-cible[1])
    return distance

  table_triee = sorted(table, key = distance_cible) # La fonction distance_cible est appliquée sur chaque élément de table avant de trier
  proches_voisins = [] # Liste contenant les k plus proches voisins

  for i in range(k) :
    proches_voisins.append(table_triee[i])

  return proches_voisins