K-Nearest Neighbors (KNN)

Debutant 30 min 13 sections

Decouvrez KNN, un algorithme intuitif qui classe les points selon leurs k plus proches voisins.

Telecharger CSV Telecharger Script Python

Objectifs d'apprentissage

Comprendre le principe de classification par voisinage
Choisir le bon nombre k de voisins
Connaitre l'importance de la normalisation
Implementer KNN avec scikit-learn

Prerequis

Notions de base en Python

Theorie

Qu'est-ce que KNN?

K-Nearest Neighbors (KNN) est un algorithme de classification base sur une idee 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
Predire la classe majoritaire

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

Avantages:

Tres intuitif et facile a comprendre
Pas d'entrainement (lazy learning)
Fonctionne pour classification et regression
Pas d'hypothese sur la distribution des donnees

Inconvenients:

Lent en prediction (doit calculer toutes les distances)
Sensible a l'echelle des features
Sensible au "fleau de la dimension"
Le choix de k est important

Theorie

Schema: Comment KNN decide

Classification d'un nouveau point:

flowchart TD NEW["Nouveau Point
(a 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["Prediction: SETOSA"] VOTE --> PRED style PRED fill:#F7E64D,color:#1A1A1A

Impact du choix de k:

flowchart LR subgraph K1 ["k=1"] R1["Tres sensible
au bruit"] end subgraph K5 ["k=5"] R5["Equilibre
(souvent optimal)"] end subgraph K50 ["k=50"] R50["Trop lisse
(sous-apprentissage)"] end style R5 fill:#F7E64D,color:#1A1A1A

Conseil: Choisir k impair pour eviter les egalites!

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

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

Etape 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	Espece	Distance
__MATH_11b0412a__	Versicolor	__MATH_72ca353d__
__MATH_2a8d0e0d__	Versicolor	__MATH_e5fa56fa__
__MATH_e0915755__	Virginica	__MATH_6834125e__

Etape 2 - Vote majoritaire:

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

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

Legende des couleurs:

$\textcolor{#3498db}{Bleu}$ : longueur du petale ($\textcolor{#3498db}{3.5}$ cm)
$\textcolor{#e67e22}{Orange}$ : largeur du petale ($\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 eloigne)
$\textcolor{#27ae60}{Vert}$ : prediction finale

Avance Exercice manuel: A vous de calculer!

Objectif: Appliquer K-Nearest Neighbors a la main.

CONTEXTE

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

Points d'entrainement :

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 a 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 a chaque point d'entrainement

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 prediction (vote majoritaire) ?

PARTIE 3 : Impact de K

3.1) Quelle serait la prediction avec K=1 ?

3.2) Et avec K=5 ?

Avance Solution de l'exercice manuel

SOLUTION DETAILLEE

Nouveau point : (1.55, 0.5) apres 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{Prediction : 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 decision!}}$

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

Code

Explorer le dataset Iris

Cliquez sur "Executer" pour voir le resultat