Algorithmique¶

Algorithme des k plus proches voisins¶

Capacités attendues :

Écrire un algorithme qui prédit la classe d’un élément en fonction de la classe majoritaire de ses k plus proches voisins.

Commentaires :

Il s’agit d’un exemple d’algorithme d’apprentissage.

No description has been provided for this image

L'idée principale derrière l'algorithme k-NN (k Nearest Neighbors) est qu'un élément peut être classifié en fonction des éléments qui lui sont le plus proches dans l'espace des caractéristiques. Ainsi, pour prédire la classe d'un élément donné, on regarde les k éléments les plus proches de cet élément (où "k" est un nombre entier positif), et on attribue à cet élément la classe majoritaire parmi ces voisins.

Étapes :

  • Choisissez la valeur de k (nombre de voisins à considérer). Pour un élément donné que vous souhaitez classer :
  • Calculez la distance entre cet élément et tous les autres éléments de l'ensemble d'apprentissage.
  • Sélectionnez les k éléments ayant la plus faible distance par rapport à l'élément donné.
  • Comptez le nombre d'occurrences de chaque classe parmi ces k voisins.
  • Attribuez à l'élément la classe qui est la plus fréquente parmi ces k voisins.

Distances couramment utilisées :

  • Distance euclidienne
  • Distance de Manhattan
  • Distance de Minkowski
  • Et d'autres...

Inconvénients :

  • Coûteux en temps de calcul, surtout lorsque la taille de l'ensemble de données est grande.
  • Sensible aux variables non pertinentes.
  • La performance peut être affectée par la valeur de k choisie.

Exemple : Classification de fruits en fonction de leur poids et de leur texture¶

Contexte : Supposons que nous ayons un ensemble de données de fruits, principalement des pommes et des oranges. Nous voulons classer un fruit inconnu en fonction de son poids (en grammes) et de sa texture (mesurée sur une échelle de 1 à 10, où 1 est très rugueux et 10 est très lisse).

Ensemble d'apprentissage :

  • Pomme : 150g, texture 4
  • Pomme : 170g, texture 5
  • Orange : 160g, texture 7
  • Orange : 140g, texture 8
  • Pomme : 130g, texture 3
  • Orange : 155g, texture 9

Fruit à classifier : ? : 145g, texture 6

Résultats :

  • Distance entre le fruit inconnu et la 1ère pomme = $\sqrt{(150-145)^2+(4-6)^2} = \sqrt{29} \approx 5.39$
  • Distance entre le fruit inconnu et la 2ème pomme $\approx$ 25.02
  • Distance entre le fruit inconnu et la 1ère orange $\approx$ 15.03
  • Distance entre le fruit inconnu et la 2ème orange $\approx$ 5.39
  • Distance entre le fruit inconnu et la 3ème pomme $\approx$ 15.3
  • Distance entre le fruit inconnu et la 2ème orange $\approx$ 10.44

Les 3 plus proches voisins sont donc la 2ème orange, la 1ère orange et la 2ème pomme. Parmi eux, nous avons 2 oranges et 1 pomme.

Conclusion : La classe majoritaire parmi les 3 plus proches voisins est "Orange". Par conséquent, nous classifions le fruit inconnu comme une "Orange".

Exercice de Classification : Détection du Diabète¶

Contexte : Le diabète est une maladie caractérisée par une augmentation chronique du taux de glucose dans le sang. Un test courant pour diagnostiquer le diabète est le test de glycémie à jeun. Un résultat supérieur à 126 mg/dL est généralement considéré comme indicatif du diabète.

Données : Vous disposez des résultats de glycémie à jeun pour un groupe de patients :

Patient A: 130 mg/dL
Patient B: 110 mg/dL
Patient C: 140 mg/dL
Patient D: 125 mg/dL
Patient E: 135 mg/dL

Questions :

  1. En utilisant la valeur seuil de 126 mg/dL, classez chaque patient comme "Diabétique" ou "Non diabétique".

  2. Si vous deviez utiliser l'algorithme des k plus proches voisins (k-NN) avec k=3 pour déterminer la classification d'un nouveau patient avec une glycémie de 128 mg/dL, comment le classeriez-vous ? (Considérez que la distance est simplement la différence absolue entre les valeurs de glycémie.)

  3. Quels sont les avantages et les inconvénients de l'utilisation d'une valeur seuil fixe par rapport à l'utilisation de l'algorithme k-NN pour ce type de classification ?

Réponse :

  1. En utilisant la valeur seuil de 126 mg/dL, classez chaque patient comme "Diabétique" ou "Non diabétique".
  • Patient A: 130 mg/dL -> Diabétique
  • Patient B: 110 mg/dL -> Non diabétique
  • Patient C: 140 mg/dL -> Diabétique
  • Patient D: 125 mg/dL -> Non diabétique
  • Patient E: 135 mg/dL -> Diabétique
  1. Si vous deviez utiliser l'algorithme des k plus proches voisins (k-NN) avec k=3k=3 pour déterminer la classification d'un nouveau patient avec une glycémie de 128 mg/dL, comment le classeriez-vous ?

Pour cela, nous allons calculer la distance (différence absolue) entre le nouveau patient et chaque patient existant :

  • Distance avec A: |130 - 128| = 2
  • Distance avec B: |110 - 128| = 18
  • Distance avec C: |140 - 128| = 12
  • Distance avec D: |125 - 128| = 3
  • Distance avec E: |135 - 128| = 7

Les trois plus petites distances sont pour les patients A, D et E.

Parmi ces trois patients, deux sont diabétiques (A et E) et un est non diabétique (D). Ainsi, la majorité est "Diabétique".

donc Le nouveau patient serait classé comme "Diabétique" en utilisant k-NN avec k=3.

  1. Quels sont les avantages et les inconvénients de l'utilisation d'une valeur seuil fixe par rapport à l'utilisation de l'algorithme k-NN pour ce type de classification ?

Avantages de la valeur seuil :

Simple à comprendre et à implémenter.
Pas besoin de stocker tout l'ensemble de données pour les nouvelles classifications.
Rapide pour classer de nouvelles données.

Inconvénients de la valeur seuil :

Peut ne pas être précis si la limite n'est pas clairement définie.
Ne prend pas en compte la distribution globale des données.

Avantages de k-NN :

Prend en compte la distribution globale des données.
Flexible et peut être adapté en changeant la valeur de k.
Pas besoin d'un modèle formel, utilise directement les données pour la classification.

Inconvénients de k-NN :

Nécessite de stocker tout l'ensemble de données, ce qui peut être coûteux en termes de mémoire.
Plus lent pour classer de nouvelles données car il faut calculer la distance avec chaque point de l'ensemble de données.
In [9]:
import math

# Données d'entraînement
ensemble_apprentissage = [
    {"fruit": "Pomme", "poids": 150, "texture": 4},
    {"fruit": "Pomme", "poids": 170, "texture": 5},
    {"fruit": "Orange", "poids": 160, "texture": 7},
    {"fruit": "Orange", "poids": 140, "texture": 8},
    {"fruit": "Pomme", "poids": 130, "texture": 3},
    {"fruit": "Orange", "poids": 155, "texture": 9},
]

# Fruit à classer
fruit_inconnu = {"poids": 145, "texture": 6}

def distance_euclidienne(a, b):
    return math.sqrt((a["poids"] - b["poids"])**2 + (a["texture"] - b["texture"])**2)

def kNN(ensemble, point, k):
    distances = []
    for élément in ensemble:
        d = distance_euclidienne(élément, point)
        distances.append((d, élément["fruit"]))
    
    # Tri simplifié des distances
    distances.sort()
    print(distances)

    # Sélection des k plus proches voisins
    k_voisins = [item[1] for item in distances[:k]]
    print(k_voisins)

    # Détermination de la classe majoritaire sans Counter
    classes = {}
    for v in k_voisins:
        if v in classes:
            classes[v] += 1
        else:
            classes[v] = 1
    print(classes)

   # Détermination de la classe majoritaire
    classe_majoritaire = None
    max_count = 0
    for fruit, count in classes.items():
        if count > max_count:
            max_count = count
            classe_majoritaire = fruit
 
    return classe_majoritaire

# Test
k = 3
classe_predite = kNN(ensemble_apprentissage, fruit_inconnu, k)
print(f"Le fruit inconnu est classé comme une {classe_predite}.")

[(5.385164807134504, 'Orange'), (5.385164807134504, 'Pomme'), (10.44030650891055, 'Orange'), (15.033296378372908, 'Orange'), (15.297058540778355, 'Pomme'), (25.019992006393608, 'Pomme')]
['Orange', 'Pomme', 'Orange']
{'Orange': 2, 'Pomme': 1}
Le fruit inconnu est classé comme une Orange.