#knn — Apprentissage supervisé

Les k plus proches voisins : classer par ressemblance, choisir k, changer de distance — et voir la frontière se lisser ou se déchirer.

Ce que tu vas manipuler

Bienvenue dans #knn. Au sol, deux nuages de points déjà étiquetés : bleus et roses. La sphère jaune est un point nouveau, sans étiquette, posé entre les deux. Les k plus proches voisins ne « s'entraînent » pas : pour classer ce point, ils regardent ses k voisins les plus proches et font voter. Ici k = 1 : un seul segment jaune, la classe du point le plus proche, rien d'autre. Un seul point rose égaré suffit à faire pencher le verdict… c'est exactement le problème qu'on va corriger.
Que dirait ce classifieur en chaque point du plan ? Affiche la carte de décision : /frontiere. Chaque carré prend la couleur de la classe que k-NN prédirait à cet endroit.
Demande l'avis de sept voisins au lieu d'un : /k 7. Regarde la carte, les segments, et l'étiquette au-dessus de la sphère jaune.
Déplace la requête vers la zone où les deux nuages se mêlent : /requete 0.2 -0.4. Les sept segments se réorientent, et le cercle jaune au sol est la « boule » de voisinage : son rayon est la distance au septième voisin.
Changeons la définition même de « proche » : /distance manhattan. La distance de Manhattan additionne les écarts en x et en y au lieu de les combiner au carré, comme un taxi qui ne coupe pas à travers les immeubles.
Poussons k très haut : /k 25. Vingt-cinq voisins, c'est un cinquième du jeu de données.
Un compromis : garder beaucoup de voisins, mais donner plus de poids aux plus proches. Tape /pondere — chaque voisin vote avec un poids 1/d.
À toi de jouer. /dataset lunes puis /k 1 pour voir k-NN épouser une frontière courbe sans jamais l'apprendre (la carte reste affichée ; /frontiere la masque) ; /dataset chevauchement pour un cas où aucun k ne fera de miracle (regarde le leave-one-out) ; /classes 3 sur /dataset blobs pour un vote à trois ; /distance chebyshev pour la boule carrée ; /bruit 0.9 et /graine 42 pour d'autres tirages ; /reinit pour repartir. Prochaine étape : #svm-marges, où la frontière est apprise plutôt que déduite des voisins, et #metriques-classification pour juger ces prédictions au-delà de l'exactitude.

Commandes du canal

/k <1..25> — Nombre de voisins consultés pour le vote.
/requete <x=-2..2> <y=-2..2> — Déplace la sphère jaune à classer.
/distance <euclidienne|manhattan|chebyshev> — Change la façon de mesurer « proche ».
/frontiere — Affiche ou masque la carte de décision (grille 40 × 40).
/pondere — Bascule entre vote majoritaire et vote pondéré par 1/d.
/dataset <blobs|lunes|chevauchement> — Change le jeu de points.
/classes <2|3> — Deux ou trois nuages gaussiens (jeu blobs seulement).
/bruit <0..1> — Dispersion des nuages : 0 = nets, 1 = tout se mélange.
/graine <1..99> — Autre tirage aléatoire des points, mêmes réglages.
/reinit — Revient à blobs, k = 1, distance euclidienne, requête (−0,4 ; 0).

Glossaire

k plus proches voisins (k-NN): Méthode de classification qui attribue à un point la classe la plus fréquente parmi ses k voisins les plus proches dans le jeu d'apprentissage. Aucun modèle n'est ajusté : les données sont le modèle. Fonctionne bien en petite dimension ; en grande dimension toutes les distances se ressemblent (malédiction de la dimension) et la notion de voisin perd son sens.
Distance euclidienne: La distance « à vol d'oiseau » : √(Δx² + Δy²). Les points à distance r d'un centre forment un cercle. Sensible à l'échelle des variables : on normalise les données avant de l'utiliser.
Distance de Manhattan: Somme des écarts absolus : |Δx| + |Δy|, comme un taxi qui suit le quadrillage des rues. Les points à distance r forment un losange. Moins sensible aux grandes déviations sur une seule variable que l'euclidienne.
Distance de Tchebychev: Le plus grand des écarts absolus : max(|Δx|, |Δy|), le nombre de coups d'un roi aux échecs. Les points à distance r forment un carré. Seule la coordonnée la plus éloignée compte.
Vote majoritaire: Règle de décision de k-NN : chaque voisin apporte une voix à sa classe, la classe qui en réunit le plus l'emporte. Un k impair évite les égalités à deux classes ; sinon on départage, par exemple par le voisin le plus proche.
Vote pondéré: Variante où chaque voisin vote avec un poids décroissant avec sa distance, souvent 1/d. Les voisins tout proches pèsent plus que les lointains : on peut prendre un grand k sans que la classe majoritaire globale écrase la structure locale.
Frontière de décision: Ligne (ou surface) du plan où la classe prédite change. Pour k-NN elle n'est jamais calculée explicitement : on la révèle en classant chaque point d'une grille. Déchiquetée pour k = 1, de plus en plus lisse quand k grandit.
Hyperparamètre k: Le nombre de voisins consultés, fixé avant l'apprentissage et non appris. Petit k : faible biais, forte variance (la carte colle au bruit). Grand k : frontière lisse, mais biais élevé (sous-apprentissage). On le choisit par validation, par exemple en leave-one-out.
Leave-one-out: Validation croisée extrême : chaque point est classé par le modèle construit sur tous les autres, puis on compte les bonnes réponses. Pour k-NN elle est gratuite (il suffit d'exclure le point de ses propres voisins) et sert à choisir k.
Apprentissage paresseux: Famille de méthodes, dont k-NN, qui ne construisent aucun modèle à l'entraînement : elles stockent les exemples et repoussent tout le calcul au moment de la prédiction. Entraînement instantané, prédiction coûteuse (une distance par exemple stocké).

Autres canaux du thème Apprentissage supervisé

#entrainement-live — Six algorithmes qui apprennent sous tes yeux, comme une vidéo : REC, timecode, sous-titres, métriques en direct. Regarder est gratuit ; toucher au modèle est Premium.
#regression-lineaire — Ajuster une droite : moindres carrés, résidus, MSE, R² et descente de gradient — la première brique de tout apprentissage supervisé.
#regression-logistique — Classer en deux catégories : sigmoïde, frontière de décision, seuil et log-loss — et pourquoi une droite ne suffit pas toujours.
#arbres-de-decision — Un arbre qui découpe le plan en rectangles : Gini, entropie, profondeur, élagage — et le sur-apprentissage qu'on voit à l'œil nu.
#knn — Les k plus proches voisins : classer par ressemblance, choisir k, changer de distance — et voir la frontière se lisser ou se déchirer.
#svm-marges — Machines à vecteurs de support : la plus large marge possible, le paramètre C, et le noyau RBF qui courbe la frontière.
#metriques-classification — Précision, rappel, F1, matrice de confusion, ROC et AUC : lire honnêtement un classifieur, surtout quand les classes sont déséquilibrées.