Récapitulatif de l'algorithme des k plus proches voisins (k-NN)

Principes fondamentaux

• Type d'algorithme : Apprentissage supervisé (données étiquetées)
• Objectif : Classifier selon similarités
• Origine : Terme "machine learning" (1959), popularisé années 2000

Formule de calcul de distance

Distance euclidienne entre I = (xI, yI) et C = (xC, yC) :

IC = √[(xC - xI)² + (yC - yI)²]

    import math

    def distance(pok_inconnu, pok_de_la_base):
        d = math.sqrt((int(pok_inconnu[0]) - int(pok_de_la_base[1]))**2
        + (int(pok_inconnu[1]) - int(pok_de_la_base[2]))**2)
        return d
        

Fonctionnement de l'algorithme en pseudocode

    Algorithme k-NN (base apprentissage, k, inconnu)
    Pour chaque donnée dans la base d'apprentissage
      Calculer la distance entre l'inconnu et la donnée courante.
      Mémoriser cette distance et la donnée associée dans une liste de couple (distance, donnée).
      Triez la liste distance_Donnée par ordre croissant des distances.
      Choisissez les k premières entrées de cette liste.
      Obtenir les étiquettes des k données de la base d'apprentissage sélectionnée.
      Renvoyer l'étiquette majoritaire.
      

Implémentation complète en Python

1. Chargement des données

    ListeDesPok = []
    with open('pokemon.csv', 'r', newline="") as fichier:
        table = [ligne.rstrip().split(',') for ligne in fichier]
        for i in range(1, len(table)):
            pok = (table[i][0], table[i][1], table[i][2], table[i][3] == 'OUI')
            ListeDesPok.append(pok)
            

2. Visualisation des données

    import matplotlib.pyplot as plt

    x_True = [int(x[1]) for x in ListeDesPok if x[-1] == True]
    y_True = [int(x[2]) for x in ListeDesPok if x[-1] == True]
    x_False = [int(x[1]) for x in ListeDesPok if x[-1] == False]
    y_False = [int(x[2]) for x in ListeDesPok if x[-1] == False]

    plt.scatter(x_True, y_True, color='red', label='legendes')
    plt.scatter(x_False, y_False, color='blue')
    plt.xlabel('attack')
    plt.ylabel('defense')

    plt.show()
    

3. Calcul des distances

    def liste_distances(pok_inconnu, table_pokemon):
        """Description : retourne la liste des t-uples (Nom_pokemon, distance entre le pok_inconnu et pokemon, classe du pokemon)
        Entrée : deux listes pok_inconnu et table_pokemon de type list
        Sortie : liste de t-uples de type list"""
        
        l = []
        for pok in table_pokemon:
            dist = distance(pok_inconnu, pok)
            l.append((pok[0], dist, pok[3]))
        
        return l
        

4. Tri de la liste des distances

    def tri_insertion(liste):
        """Trie une liste de tuples par ordre croissant des distances (2ème élément du tuple)"""
        for i in range(1, len(liste)):
            element = liste[i]
            j = i - 1
            while j >= 0 and liste[j][1] > element[1]:
                liste[j+1] = liste[j]
                j -= 1
            liste[j+1] = element
        return liste
        

5. Détermination de la classe majoritaire

    def classe_majoritaire(liste_triee, k):
        """Détermine la classe majoritaire parmi les k premiers éléments
        Entrée : liste de tuples (Nom_Pokemon, distance, Booleen), entier k
        Sortie : valeur booléenne majoritaire"""
        
        # Extraction des k premiers éléments
        k_premiers = liste_triee[:k]
        
        # Comptage des True et False
        compte_true = sum(1 for _, _, classe in k_premiers if classe == True)
        compte_false = k - compte_true
        
        # Retourne la classe majoritaire
        return compte_true > compte_false
        

6. Implémentation complète de l'algorithme k-NN

    def knn_prediction(pok_inconnu, base_apprentissage, k):
        """Prédit la classe d'un pokemon inconnu en utilisant l'algorithme k-NN
        Entrée : pok_inconnu (liste), base_apprentissage (liste de pokemons), k (entier)
        Sortie : booléen (True si légendaire, False sinon)"""
        
        # Calcul des distances
        liste_dist = liste_distances(pok_inconnu, base_apprentissage)
        
        # Tri des distances
        liste_triee = tri_insertion(liste_dist)
        
        # Détermination de la classe majoritaire
        resultat = classe_majoritaire(liste_triee, k)
        
        return resultat
        

6. Utilisation pour prédire si Mega Heracross est légendaire

    # Caractéristiques de Mega Heracross
    mega_heracross = [80, 185]

    # Prédiction avec différentes valeurs de k
    resultat_k3 = knn_prediction(mega_heracross, ListeDesPok, 3)
    resultat_k5 = knn_prediction(mega_heracross, ListeDesPok, 5)
    resultat_k7 = knn_prediction(mega_heracross, ListeDesPok, 7)

    print(f"Avec k=3, Mega Heracross est légendaire : {resultat_k3}")
    print(f"Avec k=5, Mega Heracross est légendaire : {resultat_k5}")
    print(f"Avec k=7, Mega Heracross est légendaire : {resultat_k7}")
    

Avantages et limitations

• Avantages :
  • Simple à implémenter
  • Aucun entraînement requis
• Limitations :
  • Coûteux en mémoire
  • Sensible au choix de k

Applications

• Classification de textes
• Reconnaissance d'images
• Systèmes de recommandation