K-Nearest Neighbors (KNN)

Débutant 30 min 13 sections

Aucun entraînement : la classe se décide au vote des k voisins, à condition d'avoir normalisé les échelles.

Télécharger le CSV Télécharger le script Python

Objectifs d'apprentissage

Comprendre le principe de classification par voisinage
Choisir le bon nombre k de voisins
Connaître l'importance de la normalisation
Implémenter KNN avec scikit-learn

Prérequis

Notions de base en Python

Théorie

Qu'est-ce que KNN?

K-Nearest Neighbors (KNN) est un algorithme de classification base sur une idée simple:

"Dis-moi qui sont tes voisins, je te dirai qui tu es"

Fonctionnement:

Pour un nouveau point, trouver les k points les plus proches
Regarder les classes de ces k voisins
Prédire la classe majoritaire

Exemple: Si k=5 et les 5 voisins sont [A, A, B, A, B], on prédit A (3 contre 2).

Avantages:

Très intuitif et facile à comprendre
Pas d'entraînement (lazy learning)
Fonctionne pour classification et régression
Pas d'hypothèse sur la distribution des données

Inconvénients:

Lent en prédiction (doit calculer toutes les distances)
Sensible à l'échelle des features
Sensible au "fléau de la dimension"
Le choix de k est important

Théorie

Schéma: Comment KNN décide

Classification d'un nouveau point:

flowchart TD NEW["Nouveau Point
(à classifier)"] subgraph Voisins ["Recherche des k=5 voisins"] V1["Voisin 1: Setosa
Distance: 0.2"] V2["Voisin 2: Setosa
Distance: 0.3"] V3["Voisin 3: Versicolor
Distance: 0.5"] V4["Voisin 4: Setosa
Distance: 0.6"] V5["Voisin 5: Versicolor
Distance: 0.7"] end NEW --> Voisins VOTE["Vote Majoritaire
Setosa: 3 | Versicolor: 2"] Voisins --> VOTE PRED["Prédiction: SETOSA"] VOTE --> PRED class PRED ml-node-accent

Impact du choix de k:

flowchart LR subgraph K1 ["k=1"] R1["Très sensible
au bruit"] end subgraph K5 ["k=5"] R5["Equilibre
(souvent optimal)"] end subgraph K50 ["k=50"] R50["Trop lisse
(sous-apprentissage)"] end class R5 ml-node-accent

Conseil: Choisir k impair pour éviter les égalités!

Exemple concret - Classification d'une fleur (k=3):

Nouvelle fleur: $\textcolor{#3498db}{petal\_length = 3.5}$ cm, $\textcolor{#e67e22}{petal\_width = 1.2}$ cm

Étape 1 - Calcul des distances (Euclidienne):

$$d = \sqrt{(\textcolor{#3498db}{x_1} - \textcolor{#3498db}{x_1'})^2 + (\textcolor{#e67e22}{x_2} - \textcolor{#e67e22}{x_2'})^2}$$

Voisin	Espèce	Distance
$\textcolor{#9B7AC4}{V_1}$	Versicolor	$\textcolor{#9B7AC4}{0.3}$
$\textcolor{#F7E64D}{V_2}$	Versicolor	$\textcolor{#F7E64D}{0.5}$
$\textcolor{#e74c3c}{V_3}$	Virginica	$\textcolor{#e74c3c}{0.8}$

Étape 2 - Vote majoritaire:

Versicolor: $\textcolor{#9B7AC4}{1}$ + $\textcolor{#F7E64D}{1}$ = 2 votes
Virginica: $\textcolor{#e74c3c}{1}$ = 1 vote

Résultat: $\textcolor{#27ae60}{\mathbf{VERSICOLOR}}$ (2 > 1)

Légende des couleurs:

$\textcolor{#3498db}{Bleu}$ : longueur du pétale ($\textcolor{#3498db}{3.5}$ cm)
$\textcolor{#e67e22}{Orange}$ : largeur du pétale ($\textcolor{#e67e22}{1.2}$ cm)
$\textcolor{#9B7AC4}{Violet}$ : voisin 1 (le plus proche)
$\textcolor{#F7E64D}{Jaune}$ : voisin 2
$\textcolor{#e74c3c}{Rouge}$ : voisin 3 (le plus éloigné)
$\textcolor{#27ae60}{Vert}$ : prédiction finale

Avancé Exercice manuel: À vous de calculer!

Objectif: Appliquer K-Nearest Neighbors à la main.

CONTEXTE

Classification de fruits (Pomme/Orange) basée sur 2 features : poids et couleur (score).

Points d'entraînement :

Fruit	Poids (g)	Couleur	Classe
A	150	0.8	Pomme
B	170	0.9	Pomme
C	140	0.3	Orange
D	160	0.4	Orange
E	180	0.7	Pomme

Nouveau fruit à classifier : Poids = 155g, Couleur = 0.5

Distance euclidienne : $d = \sqrt{(x_1-y_1)^2 + (x_2-y_2)^2}$

Note: Normalisez le poids en divisant par 100.

PARTIE 1 : Calcul des distances

1.1) Calculez la distance du nouveau fruit à chaque point d'entraînement 1.2) Classez les points par distance croissante

PARTIE 2 : Classification avec K=3

2.1) Quels sont les 3 plus proches voisins ? 2.2) Quelle est la prédiction (vote majoritaire) ?

PARTIE 3 : Impact de K

3.1) Quelle serait la prédiction avec K=1 ? 3.2) Et avec K=5 ?

Avancé Solution de l'exercice manuel

SOLUTION DÉTAILLÉE

Nouveau point : (1.55, 0.5) après normalisation

PARTIE 1 : Calcul des distances

1.1) Distances (poids normalise par 100) :

$d(A) = \sqrt{(1.55-1.5)^2 + (0.5-0.8)^2} = \sqrt{0.0025 + 0.09} = \textcolor{#3498db}{0.304}$
$d(B) = \sqrt{(1.55-1.7)^2 + (0.5-0.9)^2} = \sqrt{0.0225 + 0.16} = \textcolor{#3498db}{0.427}$
$d(C) = \sqrt{(1.55-1.4)^2 + (0.5-0.3)^2} = \sqrt{0.0225 + 0.04} = \textcolor{#e67e22}{0.250}$
$d(D) = \sqrt{(1.55-1.6)^2 + (0.5-0.4)^2} = \sqrt{0.0025 + 0.01} = \textcolor{#e67e22}{0.112}$
$d(E) = \sqrt{(1.55-1.8)^2 + (0.5-0.7)^2} = \sqrt{0.0625 + 0.04} = \textcolor{#3498db}{0.320}$

1.2) Tri par distance :

D (0.112) - Orange
C (0.250) - Orange
A (0.304) - Pomme
E (0.320) - Pomme
B (0.427) - Pomme

PARTIE 2 : Classification avec K=3

2.1) 3 plus proches : $\textcolor{#F7E64D}{D, C, A}$

2.2) Vote :

Orange : 2 (D, C)
Pomme : 1 (A)

$\boxed{\text{Prédiction : Orange}}$

PARTIE 3 : Impact de K

3.1) K=1 : Plus proche = D (Orange) → $\textcolor{#e67e22}{\text{Orange}}$

3.2) K=5 : Tous les points

Orange : 2 (D, C)
Pomme : 3 (A, E, B)

→ $\textcolor{#3498db}{\text{Pomme}}$

$\boxed{\text{K influence la décision!}}$

Légende : $\textcolor{#3498db}{Bleu}$: Pomme, $\textcolor{#e67e22}{Orange}$: Orange, $\textcolor{#F7E64D}{Jaune}$: K plus proches

Code

Explorer le dataset Iris

Ctrl+Entrée

Cliquez sur "Exécuter" pour voir le résultat