Activité : k plus proches voisins - Classification de fruits

Dans cet exercice, vous allez classifier un fruit inconnu à partir d'un ensemble d'apprentissage plus grand. Vous allez :

Calculer la distance euclidienne entre le fruit inconnu et chaque fruit de l'ensemble d'apprentissage.
Trier les distances à l'aide d'un tri par sélection.
Sélectionner les k plus proches voisins et effectuer un vote majoritaire pour déterminer la classe prédite.
Visualiser l'ensemble d'apprentissage sur un graphique.
Répondre à la question bonus : que faire si k est pair ?

Données

Nous disposons de l'ensemble d'apprentissage suivant (ensemble plus grand) :

ensemble_apprentissage = [
    {"fruit": "Pomme", "poids": 150, "texture": 4},
    {"fruit": "Pomme", "poids": 170, "texture": 5},
    {"fruit": "Pomme", "poids": 130, "texture": 3},
    {"fruit": "Pomme", "poids": 155, "texture": 4},
    {"fruit": "Pomme", "poids": 160, "texture": 6},
    {"fruit": "Orange", "poids": 160, "texture": 7},
    {"fruit": "Orange", "poids": 140, "texture": 8},
    {"fruit": "Orange", "poids": 155, "texture": 9},
    {"fruit": "Orange", "poids": 145, "texture": 7},
    {"fruit": "Orange", "poids": 150, "texture": 8},
    {"fruit": "Orange", "poids": 165, "texture": 7},
    {"fruit": "Pomme", "poids": 135, "texture": 4}
]

fruit_inconnu = {"poids": 148, "texture": 6}

ensemble = [
    {"fruit": "Pomme", "poids": 150, "texture": 4},
    {"fruit": "Pomme", "poids": 170, "texture": 5},
    {"fruit": "Pomme", "poids": 130, "texture": 3},
    {"fruit": "Pomme", "poids": 155, "texture": 4},
    {"fruit": "Pomme", "poids": 160, "texture": 6},
    {"fruit": "Orange", "poids": 160, "texture": 7},
    {"fruit": "Orange", "poids": 140, "texture": 8},
    {"fruit": "Orange", "poids": 155, "texture": 9},
    {"fruit": "Orange", "poids": 145, "texture": 7},
    {"fruit": "Orange", "poids": 150, "texture": 8},
    {"fruit": "Orange", "poids": 165, "texture": 7},
    {"fruit": "Pomme", "poids": 135, "texture": 4}
]

fruit_inconnu = {"poids": 148, "texture": 6}

import matplotlib.pyplot as plt

poids_pomme = [fruit["poids"] for fruit in ensemble if fruit["fruit"] == "Pomme"]
texture_pomme = [fruit["texture"] for fruit in ensemble if fruit["fruit"] == "Pomme"]
poids_orange = [fruit["poids"] for fruit in ensemble if fruit["fruit"] == "Orange"]
texture_orange = [fruit["texture"] for fruit in ensemble if fruit["fruit"] == "Orange"]
plt.scatter(fruit_inconnu["poids"], fruit_inconnu["texture"], c='blue', label='Fruit inconnu', marker='x', s=100)


plt.scatter(poids_pomme, texture_pomme, c='red', label='Pomme')
plt.scatter(poids_orange, texture_orange, c='orange', label='Orange')
plt.xlabel('Poids')
plt.ylabel('Texture')
plt.legend()
plt.show()

Question 1

Écrire une fonction distance_euclidienne qui calcule la distance euclidienne entre deux fruits en utilisant leurs attributs "poids" et "texture".

import math

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

Question 2

Implémentez une fonction selection_sort qui trie une liste de tuples de la forme (distance, fruit) par ordre croissant de distance.

def selection_sort(liste):
    n = len(liste)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if liste[j][0] < liste[min_index][0]:
                min_index = j
        liste[i], liste[min_index] = liste[min_index], liste[i]
    return liste

#test
def list_distance(liste, fruit_inconnu):
    distances = []
    for element in liste:
            d = distance_euclidienne(element, fruit_inconnu)
            distances.append((d, element["fruit"]))
    distances = selection_sort(distances)
    return distances

list_distance(ensemble, fruit_inconnu)

Question 3

Implémentez la fonction kNN qui :

Calcule la distance entre le fruit inconnu et chaque fruit de l'ensemble d'apprentissage.
Trie les distances à l'aide de selection_sort.
Sélectionne les k plus proches voisins.
Effectue un vote majoritaire pour déterminer la classe prédite (sans utiliser Counter).

def kNN(ensemble,fruit_inconnu, k):
    distances = list_distance(ensemble, fruit_inconnu)
    print(distances)
    
    k_voisins = [item[1] for item in distances[:k]]
    print(k_voisins)
    
    classes = {}
    for v in k_voisins:
        if v in classes:
            classes[v] += 1
        else:
            classes[v] = 1
    print(classes)
    
    classe_majoritaire = ""
    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, fruit_inconnu, k)
print("Le fruit inconnu est classé comme une", classe_predite)

[(2.8284271247461903, 'Pomme'), (2.8284271247461903, 'Orange'), (3.1622776601683795, 'Orange'), (7.280109889280518, 'Pomme'), (7.615773105863909, 'Orange'), (8.246211251235321, 'Orange'), (12.0, 'Pomme'), (12.041594578792296, 'Orange'), (13.152946437965905, 'Pomme'), (17.029386365926403, 'Orange'), (18.24828759089466, 'Pomme'), (22.02271554554524, 'Pomme')]
['Pomme', 'Orange', 'Orange']
{'Pomme': 1, 'Orange': 2}
Le fruit inconnu est classé comme une Orange

Question 6

Lorsque k est pair, il peut arriver qu'il y ait autant de voisins pour chaque classe, ce qui conduit à une égalité dans le vote majoritaire. Par exemple, avec k = 4, on obtient :

[(2.8284271247461903, 'Pomme'), (2.8284271247461903, 'Orange'), (3.1622776601683795, 'Orange'), (7.280109889280518, 'Pomme'), ...]
['Pomme', 'Orange', 'Orange', 'Pomme']
{'Pomme': 2, 'Orange': 2}

Dans notre implémentation, la classe retournée est "Pomme" car c'est la première rencontrée lors de l'itération sur le dictionnaire. Pour pallier ce problème, il est recommandé de choisir un k impair. Sinon, on peut ajouter une règle de départage.

Par exemple, en cas d'égalité, on peut retourner la classe du voisin le plus proche parmi. C'est à dire, on cherche parmi le fruit avec la distance minimale. Comment trouver ce fruit ?

print(list_distance(ensemble, fruit_inconnu)[0])