Fiche d'exercices : K plus proches voisins (k-NN)

📚 Partie 1 : Concepts fondamentaux du k-NN

Introduction 🦊

Exercice 1 - Principe de base

Expliquez le principe de l'algorithme k-NN :

1. Que signifie "k-NN" ?
2. Comment fonctionne la classification avec k-NN ?
3. Quelle est la différence entre k=1 et k=5 ?
4. Pourquoi utilise-t-on généralement un k impair ?
5. Quels sont les avantages et inconvénients de k-NN ?

Explications :
1. k-NN : k-Nearest Neighbors (k plus proches voisins)

2. Fonctionnement :
• Calculer la distance entre le point à classifier et tous les points d'entraînement
• Sélectionner les k points les plus proches
• Attribuer la classe majoritaire parmi ces k voisins

3. Différence k=1 vs k=5 :
• k=1 : Classification basée sur le voisin le plus proche uniquement
• k=5 : Classification basée sur le vote des 5 voisins les plus proches

4. k impair : Évite les égalités lors du vote (pas d'ex-aequo)

5. Avantages : Simple, pas d'hypothèse sur les données, efficace pour données non-linéaires
Inconvénients : Coûteux en calcul, sensible aux données aberrantes, nécessite beaucoup de mémoire

Introduction 🦊

Exercice 2 - Calcul de distance

Calculez la distance euclidienne entre ces points :

Point A : (2, 3)
Point B : (5, 7)
Point C : (1, 1)

Questions :
1. Distance entre A et B
2. Distance entre A et C
3. Distance entre B et C
4. Quel point est le plus proche de A ?

Calculs (formule : √[(x₂-x₁)² + (y₂-y₁)²]) :

1. Distance A-B :
√[(5-2)² + (7-3)²] = √[3² + 4²] = √[9 + 16] = √25 = 5

2. Distance A-C :
√[(1-2)² + (1-3)²] = √[(-1)² + (-2)²] = √[1 + 4] = √5 ≈ 2.24

3. Distance B-C :
√[(1-5)² + (1-7)²] = √[(-4)² + (-6)²] = √[16 + 36] = √52 ≈ 7.21

4. Plus proche de A : Point C (distance ≈ 2.24)

Moyen 🦊🦊

Exercice 3 - Classification simple

Données d'entraînement (Taille, Poids, Classe) :

Point	Taille (cm)	Poids (kg)	Classe
1	160	50	A
2	170	65	B
3	155	45	A
4	180	80	B
5	165	55	A

Nouveau point à classifier : (162, 52)
Utilisez k=3 pour classifier ce point.

Calcul des distances :

Point à classifier : (162, 52)

Point	Distance	Classe
1	√[(162-160)² + (52-50)²] = √8 ≈ 2.83	A
2	√[(162-170)² + (52-65)²] = √233 ≈ 15.26	B
3	√[(162-155)² + (52-45)²] = √98 ≈ 9.90	A
4	√[(162-180)² + (52-80)²] = √1108 ≈ 33.29	B
5	√[(162-165)² + (52-55)²] = √18 ≈ 4.24	A

3 plus proches voisins : Points 1, 5, 3
Classes : A, A, A
Classification : Classe A (vote unanime)

📚 Partie 2 : Implémentation en Python

Moyen 🦊🦊

Exercice 4 - Fonction de distance

Implémentez une fonction qui calcule la distance euclidienne :

def distance_euclidienne(point1, point2):
    """
    Calcule la distance euclidienne entre deux points
    point1 et point2 sont des listes [x, y]
    """
    # À compléter
    pass

Testez avec :
• distance_euclidienne([0, 0], [3, 4]) → doit retourner 5.0
• distance_euclidienne([1, 1], [4, 5]) → doit retourner 5.0

Implémentation :

import math

def distance_euclidienne(point1, point2):
    """
    Calcule la distance euclidienne entre deux points
    point1 et point2 sont des listes [x, y]
    """
    x1, y1 = point1
    x2, y2 = point2
    return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

# Tests
print(distance_euclidienne([0, 0], [3, 4]))  # 5.0
print(distance_euclidienne([1, 1], [4, 5]))  # 5.0

Moyen 🦊🦊

Exercice 5 - Trouver les k plus proches voisins

Implémentez une fonction qui trouve les k plus proches voisins :

def k_plus_proches_voisins(point_test, donnees_entrainement, k):
    """
    Trouve les k plus proches voisins d'un point
    point_test : [x, y]
    donnees_entrainement : liste de [x, y, classe]
    k : nombre de voisins à retourner
    """
    # À compléter
    pass

Implémentation :

def k_plus_proches_voisins(point_test, donnees_entrainement, k):
    """
    Trouve les k plus proches voisins d'un point
    point_test : [x, y]
    donnees_entrainement : liste de [x, y, classe]
    k : nombre de voisins à retourner
    """
    distances = []

    # Calculer la distance pour chaque point d'entraînement
    for donnee in donnees_entrainement:
        point_entrainement = [donnee[0], donnee[1]]
        classe = donnee[2]
        dist = distance_euclidienne(point_test, point_entrainement)
        distances.append((dist, classe, donnee))

    # Trier par distance croissante
    distances.sort(key=lambda x: x[0])

    # Retourner les k premiers
    return distances[:k]

# Exemple d'utilisation
donnees = [[160, 50, 'A'], [170, 65, 'B'], [155, 45, 'A']]
voisins = k_plus_proches_voisins([162, 52], donnees, 2)
print(voisins)

Difficile 🦊🦊🦊

Exercice 6 - Algorithme k-NN complet

Implémentez l'algorithme k-NN complet :

def classifier_knn(point_test, donnees_entrainement, k):
    """
    Classifie un point avec l'algorithme k-NN
    Retourne la classe prédite
    """
    # À compléter
    pass

def evaluer_knn(donnees_test, donnees_entrainement, k):
    """
    Évalue la précision de l'algorithme k-NN
    Retourne le pourcentage de bonnes classifications
    """
    # À compléter
    pass

Implémentation complète :

def classifier_knn(point_test, donnees_entrainement, k):
    """
    Classifie un point avec l'algorithme k-NN
    Retourne la classe prédite
    """
    # Trouver les k plus proches voisins
    voisins = k_plus_proches_voisins(point_test, donnees_entrainement, k)

    # Compter les votes pour chaque classe
    votes = {}
    for distance, classe, donnee in voisins:
        if classe in votes:
            votes[classe] += 1
        else:
            votes[classe] = 1

    # Retourner la classe avec le plus de votes
    classe_predite = max(votes, key=votes.get)
    return classe_predite

def evaluer_knn(donnees_test, donnees_entrainement, k):
    """
    Évalue la précision de l'algorithme k-NN
    Retourne le pourcentage de bonnes classifications
    """
    bonnes_predictions = 0
    total_predictions = len(donnees_test)

    for donnee_test in donnees_test:
        point_test = [donnee_test[0], donnee_test[1]]
        vraie_classe = donnee_test[2]

        classe_predite = classifier_knn(point_test, donnees_entrainement, k)

        if classe_predite == vraie_classe:
            bonnes_predictions += 1

    precision = (bonnes_predictions / total_predictions) * 100
    return precision

# Exemple d'utilisation
entrainement = [[160, 50, 'A'], [170, 65, 'B'], [155, 45, 'A'], 
                [180, 80, 'B'], [165, 55, 'A']]
test = [[162, 52, 'A'], [175, 70, 'B']]

print(f"Précision avec k=3: {evaluer_knn(test, entrainement, 3):.1f}%")

📚 Partie 3 : Applications pratiques

Moyen 🦊🦊

Exercice 7 - Choix de k optimal

Analysez l'impact de différentes valeurs de k :

Données : 100 points d'entraînement, 2 classes équilibrées

k	Précision (%)	Temps (ms)
1	85	10
3	92	12
5	94	15
10	91	25
20	88	45
50	82	95

Questions :
1. Quelle valeur de k choisiriez-vous ?
2. Pourquoi k=1 donne-t-il une précision plus faible ?
3. Pourquoi k=50 donne-t-il une précision plus faible ?

Analyse :

1. Choix optimal : k=5 (meilleure précision 94% avec temps raisonnable)

2. Problème k=1 :
• Très sensible au bruit et aux données aberrantes
• Pas de lissage, décisions trop locales
• Overfitting possible

3. Problème k=50 :
• k trop grand par rapport à la taille des données (50% des données)
• Perte de la structure locale des données
• Tendance vers la classe majoritaire globale
• Underfitting

Règle générale : k ≈ √n où n est le nombre de points d'entraînement

Difficile 🦊🦊🦊

Exercice 8 - Système de recommandation

Créez un système de recommandation de films avec k-NN :

Données utilisateurs (notes sur 5) :

Utilisateur	Action	Comédie	Drame	Sci-Fi
Alice	5	2	4	1
Bob	1	5	2	4
Charlie	4	3	5	2
Diana	2	4	1	5

Nouvel utilisateur : Eve (Action: 4, Comédie: 1, Drame: 5, Sci-Fi: ?)
Prédisez la note de Eve pour les films Sci-Fi avec k=2.

Solution :

1. Calcul des distances (sans Sci-Fi) :
Eve : [4, 1, 5]

• Alice [5, 2, 4] : √[(4-5)² + (1-2)² + (5-4)²] = √3 ≈ 1.73
• Bob [1, 5, 2] : √[(4-1)² + (1-5)² + (5-2)²] = √34 ≈ 5.83
• Charlie [4, 3, 5] : √[(4-4)² + (1-3)² + (5-5)²] = √4 = 2.00
• Diana [2, 4, 1] : √[(4-2)² + (1-4)² + (5-1)²] = √29 ≈ 5.39

2. Les 2 plus proches voisins :
• Alice (distance 1.73, Sci-Fi: 1)
• Charlie (distance 2.00, Sci-Fi: 2)

3. Prédiction :
Moyenne pondérée par l'inverse de la distance :
Poids Alice = 1/1.73 ≈ 0.58
Poids Charlie = 1/2.00 = 0.50

Note prédite = (1×0.58 + 2×0.50) / (0.58 + 0.50) ≈ 1.46

Prédiction pour Eve en Sci-Fi : ≈ 1.5/5

Difficile 🦊🦊🦊

Exercice 9 - Optimisations et variantes

Analysez ces améliorations de l'algorithme k-NN :

1. k-NN pondéré : Les voisins plus proches ont plus d'influence
2. Normalisation : Mettre toutes les features à la même échelle
3. Distance de Manhattan : |x₁-x₂| + |y₁-y₂|
4. Réduction de dimensionnalité : PCA avant k-NN

Questions :
• Quand utiliser chaque amélioration ?
• Implémentez la distance de Manhattan
• Pourquoi normaliser les données ?

Analyse des améliorations :

1. k-NN pondéré :
• Utilisation : Quand la proximité est très importante
• Poids = 1/distance ou exp(-distance)

2. Normalisation :
• Nécessaire quand les features ont des échelles différentes
• Exemple : âge (0-100) vs salaire (20000-100000)

def normaliser(donnees):
    # Min-Max normalization
    for i in range(len(donnees[0])-1):  # -1 pour exclure la classe
        valeurs = [point[i] for point in donnees]
        min_val, max_val = min(valeurs), max(valeurs)
        for point in donnees:
            point[i] = (point[i] - min_val) / (max_val - min_val)
    return donnees

3. Distance de Manhattan :

def distance_manhattan(point1, point2):
    return sum(abs(a - b) for a, b in zip(point1, point2))

• Utilisation : Données avec features indépendantes, moins sensible aux outliers

4. Réduction de dimensionnalité :
• Utilisation : Données haute dimension, réduction du bruit • Améliore les performances et réduit la malédiction de la dimensionnalité