Supposons que ces listes contiennent les statistiques d'atta

Implémentation de l'algorithme des K plus proches voisins.

On pourrait essayer de penser à un algorithme simple pour pouvoir implémenter l'algorithme knn en python:

Il nous faut une liste d'échantillons de taille n
La donnée que l'on veut classer, appellons là mystere
Un entier k plus petit que n
La règle de calcul des distances

Il nous faudra donc répéter ces trois étapes suivantes pour faire fonctionner l'algorithme:

Trier les échantillons selon une distance croissante avec mystere
Un tableau contenant les k premiers voisins de la liste triée
Renvoyer ce tableau.

Et en langage Python ?

Nous allons utiliser la bibliothèque Matplotlib

Pourquoi utiliser`matplotlib` ?

Visualiser les données : Avant de plonger dans des algorithmes complexes, il est essentiel de comprendre les données avec lesquelles on travaille. Un bon graphique peut révéler des tendances, des anomalies, des clusters ou des relations entre les variables bien mieux qu'une simple inspection des chiffres.
Communiquer des résultats : Les graphiques aident à communiquer les résultats d'une analyse de manière efficace et intuitive, que ce soit entre scientifiques ou pour présenter à un public non spécialiste.

Premiers Pas avec `matplotlib`

Pour commencer, il faut installer matplotlib si ce n'est pas déjà fait. Cela se fait généralement via pip :

pip install --upgrade --proxy=172.16.0.253:3128 matplotlib

Ensuite, pour utiliser matplotlib, on commence par importer le module pyplot, souvent sous l'alias plt :

import matplotlib.pyplot as plt

Exemple de Base

Imaginons que l'on souhaite représenter les statistiques d'attaque et de défense de quelques Pokémon.

import matplotlib.pyplot as plt

# Supposons que ces listes contiennent les statistiques d'attaque et de défense de quelques Pokémon
attaques = [55, 75, 150, 45]
defenses = [45, 60, 50, 65]
noms = ['Pikachu', 'Bulbizarre', 'Salameche', 'Carapuce']

plt.figure(figsize=(10, 5)) # Définit la taille de la figure
plt.scatter(attaques, defenses, color='red') # Crée un nuage de points avec les statistiques d'attaque et de défense

# Ajoute des titres et des étiquettes
plt.title('Attaque vs Défense des Pokémon')
plt.xlabel('Attaque')
plt.ylabel('Défense')

# Ajoute des annotations pour chaque point
for i, nom in enumerate(noms):
    plt.annotate(nom, (attaques[i], defenses[i]))

plt.grid(True) # Ajoute une grille pour une meilleure lisibilité
plt.show() # Affiche le graphique

Ce code génère un graphique en nuage de points où chaque point représente un Pokémon, avec son niveau d'attaque sur l'axe des x et son niveau de défense sur l'axe des y. Les annotations permettent d'identifier chaque Pokémon sur le graphique.

Implémentation de l'algorithme KNN

Maintenant que nous savons visualiser nos données, passons à l'implémentation de l'algorithme.

Étape 1 : Calculer la distance entre deux points

import math

def calculer_distance(point1, point2):
    """
    Calcule la distance euclidienne entre deux points.
    point1 et point2 sont des listes de coordonnées [x, y]
    """
    somme = 0
    for i in range(len(point1)):
        somme += (point1[i] - point2[i]) ** 2
    return math.sqrt(somme)

# Test
print(calculer_distance([0, 0], [3, 4]))  # Affiche 5.0

Étape 2 : Trouver les k plus proches voisins

def trouver_voisins(echantillons, mystere, k):
    """
    Trouve les k plus proches voisins de mystere dans echantillons.

    Paramètres:
        echantillons : liste de dictionnaires {'coords': [x, y], 'classe': 'Type'}
        mystere : liste [x, y] du point à classifier
        k : nombre de voisins à retourner

    Retourne:
        Liste des k plus proches voisins
    """
    # Calculer la distance pour chaque échantillon
    distances = []
    for echantillon in echantillons:
        dist = calculer_distance(echantillon['coords'], mystere)
        distances.append({'echantillon': echantillon, 'distance': dist})

    # Trier par distance croissante
    distances_triees = sorted(distances, key=lambda x: x['distance'])

    # Retourner les k premiers
    return [d['echantillon'] for d in distances_triees[:k]]

Étape 3 : Déterminer la classe majoritaire

def classe_majoritaire(voisins):
    """
    Détermine la classe la plus représentée parmi les voisins.

    Paramètres:
        voisins : liste de dictionnaires avec une clé 'classe'

    Retourne:
        La classe majoritaire (str)
    """
    compteur = {}
    for voisin in voisins:
        classe = voisin['classe']
        if classe in compteur:
            compteur[classe] += 1
        else:
            compteur[classe] = 1

    # Trouver la classe avec le plus grand nombre
    classe_max = None
    max_count = 0
    for classe, count in compteur.items():
        if count > max_count:
            max_count = count
            classe_max = classe

    return classe_max

Étape 4 : L'algorithme KNN complet

def knn(echantillons, mystere, k):
    """
    Algorithme des k plus proches voisins.

    Paramètres:
        echantillons : liste de dictionnaires {'coords': [x, y], 'classe': 'Type'}
        mystere : liste [x, y] du point à classifier
        k : nombre de voisins à considérer

    Retourne:
        La classe prédite pour mystere
    """
    voisins = trouver_voisins(echantillons, mystere, k)
    return classe_majoritaire(voisins)

Exemple complet

# Échantillon de Pokémon
pokemons = [
    {'coords': [49, 49], 'classe': 'Eau'},    # Ecayon
    {'coords': [50, 95], 'classe': 'Psy'},    # Deoxys
    {'coords': [80, 45], 'classe': 'Psy'},    # Eoko
    {'coords': [90, 75], 'classe': 'Psy'},    # Groret
    {'coords': [90, 75], 'classe': 'Eau'},    # Tarpaud
]

# Pokémon mystère à classifier
pokemon_mystere = [65, 40]

# Prédiction avec k=3
prediction = knn(pokemons, pokemon_mystere, k=3)
print("Le Pokémon mystère est probablement de type :", prediction)

Auteur : Florian Mathieu

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.