TNI+VO · Exercice de Programmation

EP07_01 — 🟢 Classifieur k-NN Pas à Pas

7.18.1 EP07_01 🟢 Classifieur k-NN Pas à Pas

Le KNeighborsClassifier de scikit-learn, utilisé tout au long du chapitre, dissimule derrière un simple appel (.fit / .predict) une règle de décision très simple : pour chaque nouvelle observation, calculer la distance à tous les exemples d’entraînement, sélectionner les \(k\) plus proches et voter pour la classe majoritaire parmi eux.

Avant de vous fier à la bibliothèque, vous êtes chargé d’implémenter cette règle de zéro, pour un espace de caractéristiques bidimensionnel, exactement comme le simulateur interactif de frontière de décision du chapitre le fait en interne à chaque clic de l’utilisateur.

7.18.1.1 📋 Directives d’implémentation

  1. Quantité et paramètre : Lire l’entier \(N\) (nombre d’exemples d’entraînement) et l’entier impair \(k\) (nombre de voisins).
  2. Exemples d’entraînement : Pour chacun des \(N\) exemples, lire trois valeurs : les coordonnées \(x\) et \(y\) (réelles) et l’étiquette \(r\) (entier, \(0\) ou \(1\)).
  3. Requêtes : Lire l’entier \(Q\) (nombre de points de requête) puis les coordonnées \(x_q\), \(y_q\) (réelles) de chaque requête.
  4. Distance : Pour chaque requête, calculer la distance euclidienne à tous les exemples d’entraînement : \[ d(x_q, x_i) = \sqrt{(x_q - x_i)^2 + (y_q - y_i)^2}. \]
  5. Sélection des voisins : Trier les exemples par distance croissante et sélectionner les \(k\) premiers. En cas d’égalité de distance à la frontière du k-ième voisin, départager par l’exemple lu en premier dans l’entrée (ordre de lecture stable).
  6. Vote majoritaire : Compter les votes de chaque classe parmi les \(k\) voisins sélectionnés. S’il y a égalité dans le vote (seulement possible lorsque \(k\) est pair, ce qui ne devrait pas se produire selon la directive du point 1, mais traitez-le défensivement), attribuez la classe du voisin le plus proche parmi les classes à égalité.
  7. Sortie : Pour chaque requête, dans l’ordre d’entrée, imprimer la classe prédite. À la fin, imprimer le total de requêtes classées comme classe 1.

7.18.1.2 📌 Contraintes computationnelles

  • Métrique fixe : utilisez exclusivement la distance euclidienne (pas la distance au carré) pour le tri, bien que le résultat de la comparaison soit le même.
  • k toujours impair : l’entrée garantit \(k\) impair et \(k \le N\) ; néanmoins, implémentez le départage du point 6 par robustesse.
  • Stabilité : lors du tri par distance, préservez l’ordre relatif des exemples ayant la même distance (tri stable).

7.18.1.3 🧠 Fondement théorique

Élément Rôle dans le k-NN
Espace de caractéristiques Ensemble de tous les vecteurs \((x, y)\) possibles
Distance euclidienne Mesure de similarité entre observations
\(k\) petit Frontière irrégulière, variance élevée
\(k\) grand Frontière lisse, biais élevé
Vote majoritaire Règle de décision \(\hat y = \operatorname{moda}\{y_i : x_i \in N_k(x)\}\)

7.18.1.4 📦 Spécification d’entrée et de sortie (VPL)

Entrée :

  • Ligne 1 : entiers \(N\) et \(k\), séparés par un espace.
  • Les \(N\) lignes suivantes : trois valeurs par ligne — \(x\), \(y\) (réelles) et \(r\) (entier \(\in \{0,1\}\)), séparées par un espace.
  • Ligne suivante : entier \(Q\).
  • Les \(Q\) lignes suivantes : deux valeurs par ligne — \(x_q\), \(y_q\) (réelles), séparées par un espace.

Sortie :

  • \(Q\) lignes, chacune avec la classe prédite (0 ou 1) pour la requête respective, dans l’ordre d’entrée.
  • Dernière ligne : Total classe 1 : X.

7.18.1.5 📌 Exemples

Entrée Sortie Observation
4 3
0 0 0
1 0 0
5 5 1
6 5 1
1
1 1		 0
Total classe 1 : 0		 Requête proche du groupe de classe 0.
4 1
0 0 0
1 0 0
5 5 1
6 5 1
2
0.9 0.1
5.5 5.1		 0
1
Total classe 1 : 1		 Avec \(k=1\), chaque requête hérite de la classe du voisin le plus proche.
🎮 Simulateur EP07_01 : Classificateur k-NN pas à pas Vote majoritaire
Ajustez k et voyez quels exemples d'entraînement (triés par distance) participent au vote pour la requête fixe (★ à x = 3, y = 3).
–
Figure 7.21: Simulateur EP07_01 : Classifieur k-NN Pas à Pas 
%%writefile EP07_01.py
# Code Python
Overwriting EP07_01.py
TestSuite("EP07_01.py").run()
✔️ EP07_01.cases existe déjà dans casos/
📋 5 cas chargé(s) depuis casos/EP07_01.cases

🔍 Test de Python : EP07_01.py
⚠️ EP07_01.py : fichier vide (moins de 3 lignes). Tests ignorés.