L'apprentissage par la similarité : k plus proches voisins

L'apprentissage par la similarité (similarity-based learning) repose sur une idée d'une simplicité désarmante : pour prédire ce qui va arriver dans une situation présente, le mieux est de fouiller sa mémoire à la recherche de situations passées qui lui ressemblent, puis de parier que ce qui était vrai dans le cas le plus proche le sera encore. C'est exactement le raisonnement de ce lieutenant-colonel qui, en 1798, se voit décrire par l'un de ses hommes — un marin revenu d'une expédition au bord d'une rivière australienne — un animal aux pattes palmées et au bec de canard : sans l'avoir vu lui-même, il compare ces traits aux animaux qu'il connaît, conclut qu'il s'agit d'un canard inoffensif et envoie ses hommes en expédition. La méthode est intuitive — et, comme on le verra dans l'épilogue, faillible. Ce chapitre montre comment transformer ce mode de pensée très humain en algorithme : l'espace de features (feature space) comme représentation des données, les métriques de distance (distance metrics) comme mesures de ressemblance, l'algorithme du plus proche voisin (nearest neighbor) puis ses extensions — les k plus proches voisins (k-nearest neighbors, k-NN), la pondération, l'indexation, la normalisation et la lutte contre la malédiction de la dimension.

La grande idée : ce qui se ressemble s'assemble

Le biais inductif (inductive bias) qui sous-tend toute la famille des modèles par similarité tient en une phrase : des instances dont les caractéristiques descriptives se ressemblent partagent aussi la même valeur de cible. Classer l'animal inconnu en comptant combien de traits il a en commun avec chaque animal connu, puis en retenant le plus ressemblant — un canard —, c'est appliquer ce principe à la main. La force de cette approche est qu'elle imite un raisonnement naturel, ce qui rend les modèles faciles à interpréter et à comprendre. Dans un contexte métier où des décideurs s'appuient sur un modèle, pouvoir expliquer comment il fonctionne nourrit la confiance — un avantage à ne pas sous-estimer.

Les fondamentaux : espace de features et distances

L'espace de features

Pour calculer une distance entre instances, encore faut-il une notion d'espace. L'idée est de faire de chaque feature descriptive un axe d'un système de coordonnées, puis de placer chaque instance comme un point dont les coordonnées sont les valeurs de ses features. Prenons un jeu de données classique du livre : la vitesse (SPEED) et l'agilité (AGILITY) de vingt athlètes universitaires, notées sur 10, et une cible binaire indiquant s'ils ont été recrutés (DRAFT) par une équipe professionnelle.

ID	SPEED	AGILITY	DRAFT	ID	SPEED	AGILITY	DRAFT
1	2.50	6.00	non	11	2.00	2.00	non
2	3.75	8.00	non	12	5.00	2.50	non
3	2.25	5.50	non	13	8.25	8.50	non
4	3.25	8.25	non	14	5.75	8.75	oui
5	2.75	7.50	non	15	4.75	6.25	oui
6	4.50	5.00	non	16	5.50	6.75	oui
7	3.50	5.25	non	17	5.25	9.50	oui
8	3.00	3.25	non	18	7.00	4.25	oui
9	4.00	4.00	non	19	7.50	8.00	oui
10	4.25	3.75	non	20	7.25	5.75	oui

Deux features, donc un espace à deux dimensions facile à tracer. Mais rien n'empêche d'en avoir des milliers — en classification de documents, on a couramment un axe par mot du vocabulaire. On définit alors formellement un espace de features comme un espace abstrait à m dimensions, obtenu en faisant de chaque feature descriptive un axe et en projetant chaque instance sur un point. La propriété précieuse pour l'apprentissage par similarité est la suivante : deux instances aux features identiques tombent sur le même point, et plus leurs features diffèrent, plus la distance entre leurs points grandit. La distance dans l'espace de features est donc une mesure de la similarité des descriptions.

AGILITY
 10 |            x d17
    |     x d14
  8 |  o d2  o d4         x d19
    |  o d5     x d16
  6 |  o d1 o d3   x d15
    |  o d6        x d20
    |  o d7
  4 |     o d9              x d18
    |  o d8  o d10
  2 |  o d11    o d12          ? (requête)
    +-------------------------------------- SPEED
       2     4      6      8

       o = non (non recruté)   x = oui (recruté)

Mesurer la similarité avec des distances

La façon la plus simple de mesurer la ressemblance entre deux instances a et b est de mesurer leur distance dans l'espace. Une métrique (metric) metric(a, b) retourne cette distance et doit, mathématiquement, respecter quatre critères :

1. Non-négativité : metric(a, b) ≥ 0
2. Identité : metric(a, b) = 0 si et seulement si a = b
3. Symétrie : metric(a, b) = metric(b, a)
4. Inégalité triangulaire : metric(a, b) ≤ metric(a, c) + metric(b, c)

La plus connue est la distance euclidienne (Euclidean distance), longueur de la ligne droite entre deux points :

Euclidean(a, b) = √( Σ_(i=1..m) (a[i] − b[i])² )

Entre l'instance d12 (SPEED = 5.00, AGILITY = 2.50) et d5 (SPEED = 2.75, AGILITY = 7.50), cela donne √((5.00 − 2.75)² + (2.50 − 7.50)²) = √(5.0625 + 25) ≈ 5.48. Moins connue, la distance de Manhattan (Manhattan distance), ou distance du taxi, somme les écarts en valeur absolue — c'est le trajet d'un taxi sur un quadrillage de rues :

Manhattan(a, b) = Σ_(i=1..m) abs(a[i] − b[i])

Entre les mêmes d12 et d5, on obtient abs(5.00 − 2.75) + abs(2.50 − 7.50) = 2.25 + 5.00 = 7.25. Ces deux formules sont des cas particuliers de la distance de Minkowski (Minkowski distance), une famille paramétrée par p :

Minkowski(a, b) = ( Σ_(i=1..m) abs(a[i] − b[i])^p )^(1/p)

Avec p = 1 on retrouve Manhattan, avec p = 2 Euclidean. On peut ainsi définir une infinité de métriques — et ce n'est pas une coquetterie académique : les prédictions changent selon le p retenu. Plus p est grand, plus la métrique met l'accent sur les grosses différences sur une seule feature, car tous les écarts sont élevés à la puissance p. La distance euclidienne est donc plus sensible qu'une distance de Manhattan à un seul écart important.

Métrique	Paramètre	Formule (cœur)	Tempérament
Manhattan	p = 1	somme des abs(écarts)	influencée par beaucoup de petits écarts ; calcul léger
Euclidienne	p = 2	racine de la somme des carrés	dominée par un gros écart unique ; choix par défaut
Minkowski	p quelconque	(Σ abs(écart)^p)^(1/p)	famille générale paramétrable
Chebyshev	p → ∞	écart maximal sur une feature	distance « du roi » aux échecs

On le voit en comparant deux paires d'instances. La distance de Manhattan entre d12 et d5 vaut 7.25, et celle entre d12 et d17 (SPEED = 5.25, AGILITY = 9.50) vaut elle aussi 7.25 — identiques. Pourtant, l'euclidienne entre d12 et d17 monte à 8.25, contre seulement 5.48 entre d12 et d5. La raison : l'écart maximal sur une feature unique est de 7 unités entre d12 et d17 (sur AGILITY), contre 5 entre d12 et d5 ; comme ces écarts sont mis au carré, le plus gros pèse davantage. Côté calcul, Manhattan a un léger avantage — pas de carré ni de racine —, ce qui compte sur de très gros jeux ; mais l'euclidienne reste le choix par défaut.

L'approche standard : l'algorithme du plus proche voisin

Avec ces deux briques — l'espace de features et une métrique —, l'algorithme du plus proche voisin tient en deux lignes pour la prédiction.

Entrées : un ensemble d'instances d'entraînement, une requête q
1. Parcourir les instances en mémoire pour trouver le plus proche
   voisin : celle dont la distance à q dans l'espace est la plus courte.
2. Prédire pour q la valeur de la cible de ce plus proche voisin.

Un exemple chiffré

Supposons une requête avec SPEED = 6.75 et AGILITY = 3.00 ; faut-il prédire « recruté » ou non ? L'algorithme calcule la distance euclidienne entre la requête et chacune des vingt instances, puis les classe de la plus proche à la plus lointaine. Voici le haut du classement :

Rang	Instance	SPEED	AGILITY	Distance	DRAFT
1	d18	7.00	4.25	1.2749	oui
2	d12	5.00	2.50	1.8200	non
3	d20	7.25	5.75	2.7959	oui
4	d16	5.50	6.75	3.9528	oui

Le plus proche voisin est d18, à 1.2749, dont la cible est « oui » : le modèle prédit donc que l'athlète sera recruté. En cherchant le plus proche voisin avec la distance euclidienne, l'algorithme partitionne en réalité l'espace en une mosaïque de Voronoï (Voronoi tessellation) : à chaque instance d'entraînement correspond une région contenant tous les points qui lui sont plus proches qu'à toute autre. Prédire pour une requête, c'est décider dans quelle région de Voronoï elle tombe.

Modèles locaux (Voronoï)  ->  modèle global implicite

   région d'une instance "oui"
   .-----.-----.
   |     |  x  |   <- chaque cellule = un voisin
   .--?--.-----.      ? tombe dans une cellule "oui"
   |     |     |
   '-----'-----'

Frontière de décision = on agrège les cellules voisines
qui prédisent la MÊME cible.

En agrégeant les cellules voisines qui prédisent la même cible, on fait apparaître la frontière de décision (decision boundary) : la limite entre les zones de l'espace où l'on prédit « oui » et celles où l'on prédit « non ». C'est ainsi que l'algorithme, à partir d'une foule de modèles locaux (un par instance), construit un modèle global implicite reliant les features à la cible. Avantage notable : mettre le modèle à jour est trivial — il suffit d'ajouter la nouvelle instance étiquetée au jeu de données, ce qui redécoupe localement la mosaïque et déplace la frontière.

Extensions et variations

L'algorithme standard fonctionne bien sur des données propres, de taille raisonnable, aux features continues. Le réel est rarement aussi clément : données bruitées, volumineuses, hétérogènes. D'où une série d'extensions.

Gérer le bruit : des k voisins plutôt qu'un seul

Dans notre exemple, le coin supérieur droit de l'espace formait une petite région « non » isolée, due à une instance « non » entourée de « oui ». Soit elle est mal étiquetée, soit l'une de ses features est erronée : c'est du bruit (noise). Comme chaque modèle local repose sur une seule instance, l'algorithme y est très sensible. La parade la plus directe est de diluer cette dépendance : on retourne la cible majoritaire parmi les k plus proches voisins (k-NN).

M_k(q) = argmax_(l ∈ levels(t))  Σ_(i=1..k) δ(t_i, l)

où δ(t_i, l) = 1 si t_i = l, et 0 sinon (delta de Kronecker)
les i parcourent les k voisins par distance croissante à q.

Avec k = 3, la région « non » parasite du coin disparaît : la frontière est régularisée. Mais k = 3 n'est pas universel. Le réglage de k est un arbitrage permanent :

Valeur de k	Risque	Conséquence sur la frontière
k trop petit	sur-apprentissage (overfitting)	sensible au bruit, frontière dentelée
k bien réglé	équilibre	frontière qui suit le vrai motif
k trop grand	sous-apprentissage (underfitting)	le vrai motif se perd, la cible majoritaire domine

Le k-NN pondéré par la distance

Le problème d'un k élevé vient de ce qu'on accorde le même poids à des voisins lointains qu'à des voisins proches. Le k-NN pondéré (weighted k-NN) corrige cela : la contribution de chaque voisin devient une fonction de l'inverse de sa distance. Le poids habituel est l'inverse du carré de la distance entre le voisin d et la requête q :

poids(q, d) = 1 / dist(q, d)²

M_k(q) = argmax_(l ∈ levels(t))  Σ_(i=1..k) ( 1 / dist(q, d_i)² ) × δ(t_i, l)

La prédiction est la cible dont la somme des poids est la plus forte. Avantage spectaculaire : on peut alors poser k égal à la taille du jeu entier — toutes les instances votent, mais les plus lointaines pèsent presque rien, donc le risque de perdre le motif s'estompe. Sur le jeu des athlètes avec k = 21, la frontière devient nettement plus lisse, ce qui suggère une meilleure modélisation de la transition entre cibles.

Recherche efficace en mémoire : les arbres k-d

Stocker tout le jeu en mémoire pèse sur la complexité en temps : retrouver les k voisins exige, en version naïve, de calculer la distance à toutes les instances. Si le jeu est stable, on peut amortir ce coût par un index construit une fois pour toutes : le arbre k-d (k-d tree, pour k-dimensional tree). C'est un arbre binaire équilibré où chaque nœud indexe une instance, construit de sorte que des nœuds voisins dans l'arbre indexent des instances voisines dans l'espace.

Construction : on choisit une feature, on coupe les données en deux selon sa valeur médiane (la médiane résiste mieux aux valeurs aberrantes que la moyenne et garde l'arbre équilibré), puis on recommence récursivement sur chaque moitié jusqu'à ce qu'il reste moins de deux instances. On choisit la feature de découpe en cyclant sur un ordre fixé d'avance (par exemple SPEED, puis AGILITY, puis on revient à SPEED). Chaque nœud non-feuille définit ainsi un hyperplan (hyperplane) qui partage l'espace : la branche gauche tient les instances sous la médiane, la droite celles au-dessus.

Pour retrouver le plus proche voisin d'une requête, on descend l'arbre depuis la racine en suivant à chaque nœud la branche correspondant à la valeur de la requête, jusqu'à une feuille — qui fournit un premier candidat best et une best-distance. Rien ne garantit qu'il s'agisse du vrai plus proche voisin ; on remonte donc l'arbre en appliquant la clé de l'algorithme : à chaque nœud, on teste si la distance de la requête à l'hyperplan du nœud est inférieure à best-distance.

Entrées : requête q, arbre kdtree
1: best = null ; best-distance = ∞
2: node = descenteVersFeuille(kdtree, q)
3: tant que node ≠ NULL faire
4:   si distance(q, node) < best-distance alors
5:     best = node ; best-distance = distance(q, node)
6:   si boundaryDist(q, node) < best-distance alors
7:     node = descenteVersFeuille(autre branche, q)   # on explore
8:   sinon
9:     node = parent(node)                            # on élague
10: retourner best

Si l'hyperplan coupe l'hypersphère cible (target hypersphere) — la boule de rayon best-distance centrée sur la requête —, c'est qu'un voisin plus proche pourrait se cacher de l'autre côté : on descend explorer cette branche. Sinon, on élague (prune) tout le sous-arbre sans le visiter, et on remonte. La recherche s'arrête à la racine. Sur l'exemple du livre (requête SPEED = 6.00, AGILITY = 3.50), cette procédure trouve d21 comme plus proche voisin en économisant le calcul de distance à quatorze des instances.

La normalisation : un impératif, pas une option

Un institut financier veut prédire, avec un modèle du plus proche voisin et une distance euclidienne, quels clients souscriront un produit d'épargne, à partir de leur salaire annuel (SALARY) et de leur âge (AGE).

ID	SALARY	AGE	PURCH	ID	SALARY	AGE	PURCH
1	53 700	41	non	6	55 900	57	oui
2	65 300	37	non	7	48 600	26	non
3	48 900	45	oui	8	72 800	60	oui
4	64 800	49	oui	9	45 300	34	non
5	44 200	30	non	10	73 200	52	oui

Pour une requête SALARY = 56 000, AGE = 35, l'inspection visuelle suggère que d1 (cible « non ») est le voisin le plus proche. Pourtant le modèle prédit « oui », en désignant d6 comme plus proche voisin. Pourquoi ? Parce que les salaires (dizaines de milliers) écrasent les âges (dizaines) : les distances calculées avec SALARY seul sont quasi identiques à celles calculées avec SALARY et AGE — la feature AGE est tout simplement ignorée. Ce serait absurde de biaiser un modèle vers une feature au seul prétexte que ses valeurs sont grandes : une longueur en millimètres pèserait alors plus qu'une longueur en mètres.

La solution est la normalisation (normalization), par exemple la normalisation par plage (range normalization) ramenant chaque feature dans [0, 1] :

valeur_normalisée = (valeur − min) / (max − min)

On normalise le jeu et toute requête avec les mêmes paramètres. Une fois les deux axes ramenés à [0, 1], les rangs changent radicalement : d1 devient le plus proche voisin, et le modèle prédit « non » — l'inverse exact de la prédiction précédente, et conforme à l'intuition géométrique.

Prédire une cible continue

Adapter le k-NN à une cible numérique est immédiat : on retourne la moyenne des cibles des k voisins plutôt que la cible majoritaire.

M_k(q) = ( 1 / k ) × Σ_(i=1..k) t_i

Pour un marchand de whiskies rares qui veut fixer un prix de réserve aux enchères, on décrit chaque bouteille par son âge (AGE) et sa note (RATING, de 1 à 5), avec le prix atteint (PRICE). Après normalisation, une requête « 2 ans, note 5 » (soit AGE = 0.0667, RATING = 1.00) avec k = 3 a pour voisins d12, d16 et d3, de prix 200, 250 et 55 : la prédiction est (200 + 250 + 55) / 3 = 168.33. La version pondérée par l'inverse du carré de la distance donne une moyenne pondérée :

M_k(q) = Σ_(i=1..k) ( t_i / dist(q, d_i)² )  ÷  Σ_(i=1..k) ( 1 / dist(q, d_i)² )

Sur tout le jeu (k = 20), elle prédit 163.71 — très proche du 168.33 du k = 3 simple. En général, modèle simple et modèle pondéré convergent quand l'espace est bien peuplé ; sur un espace clairsemé, le pondéré est plus juste car il tient compte du fait que certains « voisins » sont en réalité lointains.

D'autres mesures de similarité

La Minkowski n'est pas toujours appropriée. On distingue les métriques (qui respectent les quatre critères) des index (qui n'en respectent pas tous, mais restent utiles). Rappel de vocabulaire : avec une distance, plus petit = plus proche ; avec une similarité, plus grand = plus proche.

Mesure	Type	Pour quel cas	Idée
Russel-Rao	index	features binaires	ratio des co-présences sur le total des features
Sokal-Michener	index	features binaires	ratio (co-présences + co-absences) sur le total
Jaccard	index	binaire clairsemé (sparse)	co-présences sur le total, en ignorant les co-absences
Cosinus (cosine)	index	continu, corrélé ou clairsemé	cosinus de l'angle entre les vecteurs (ignore l'amplitude)
Mahalanobis	métrique	continu covariant	distance recalée par la covariance du jeu

Pour des features binaires (un client a-t-il rempli son profil ? lu la FAQ ? aimé la page ?), on raisonne en termes de co-présence et de co-absence. Russel-Rao ne compte que les co-présences ; Sokal-Michener ajoute les co-absences (utile en médecine, où l'absence partagée d'un symptôme compte) ; Jaccard ignore les co-absences — idéal pour les données clairsemées (sparse data), où la plupart des features valent zéro (un catalogue où chacun n'a vu qu'une infime fraction des articles). Sur un même exemple, ces trois index donnent des verdicts opposés sur qui est le voisin le plus proche : choisir le bon index est décisif, et l'expérimentation tranche.

La similarité cosinus mesure le cosinus de l'angle entre les vecteurs allant de l'origine à chaque instance. Elle s'intéresse au mélange des features, pas à leur amplitude : deux clients téléphonie qui envoient quatre fois plus de SMS que d'appels vocaux sont jugés identiques même si leurs volumes diffèrent, car chaque instance est normalisée sur l'hypersphère unité. Comme le produit scalaire annule les co-absences (0 × 0 = 0), le cosinus convient aussi aux données clairsemées non binaires.

cosinus(a, b) = ( Σ a[i] × b[i] )  ÷  ( |a| × |b| )

où |a| = √( Σ a[i]² ) est la longueur du vecteur a.
Résultat dans [0, 1] (1 = identiques, 0 = orthogonaux).

Enfin, la distance de Mahalanobis tient compte de l'étalement du jeu via sa covariance : elle réduit les distances dans les directions où les données sont étalées et les amplifie là où elles sont resserrées. Deux requêtes B et C équidistantes de A au sens euclidien peuvent ne pas l'être au sens de Mahalanobis, selon que la covariance est positive ou négative. Quand il n'y a aucune covariance, la matrice de covariance inverse est l'identité et Mahalanobis se réduit à l'euclidienne.

Mahalanobis(a, b) = √( [a − b] × Σ⁻¹ × [a − b]ᵀ )

Σ⁻¹ = matrice de covariance inverse du jeu de données.
Effet : variances ramenées à 1, covariances annulées.

La malédiction de la dimension et la sélection de features

L'intuition voudrait que plus on ajoute de features, plus le modèle s'améliore. Faux. Au-delà d'un certain point, ajouter des features dégrade le pouvoir prédictif. La raison tient à la densité d'échantillonnage (sampling density) : prédire suppose soit de partitionner l'espace par grappes d'instances, soit d'interpoler à partir d'instances proches — deux stratégies qui exigent une densité raisonnable. Or, à nombre d'instances constant, chaque dimension ajoutée fait fuir les points les uns des autres.

1D : 29 instances sur [0,3]      cube unité [0,1] -> 10 instances
2D : mêmes 29 instances          cube unité       ->  4 instances
3D : mêmes 29 instances          cube unité       ->  1 instance (l'espace se vide)

Pour MAINTENIR la densité :
2D -> il faudrait 29 × 29   =    841 instances
3D -> il faudrait 29 × 29 × 29 = 24 389 instances  (croissance exponentielle !)

C'est la malédiction de la dimension (curse of dimensionality) : pour garder la densité, il faut un nombre d'instances qui croît exponentiellement avec les dimensions. Dans un espace de haute dimension presque vide, la plupart des requêtes n'ont aucun voisin proche, et le modèle se réduit à deviner. Deux propriétés des données réelles atténuent le mal : elles forment des grappes (dimensionnalité effective plus basse que l'espace), et elles varient en douceur localement (petits changements de features = petits changements de cible), ce qui rend l'interpolation possible. Le plus proche voisin, qui utilise toutes les features, y est particulièrement vulnérable — là où les arbres de décision, qui sélectionnent des sous-ensembles, résistent mieux.

Comme on ne peut généralement pas acquérir plus d'instances, le remède est la sélection de features (feature selection) : réduire le jeu au plus petit sous-ensemble utile. On distingue quatre types de features — prédictive (informative sur la cible), interagissante (inutile seule, informative combinée à d'autres), redondante (fortement corrélée à une autre), non pertinente (sans information). L'objectif idéal : garder les prédictives et les interagissantes, écarter les redondantes et les non pertinentes.

L'approche la plus simple est le classement-élagage (rank and prune) à l'aide d'un filtre (filter) — une heuristique évaluant la prédictivité d'une feature à partir des seules propriétés intrinsèques des données (par exemple le gain d'information), indépendamment de l'algorithme d'apprentissage. Rapide, mais évaluant chaque feature isolément, il tend à exclure les interagissantes et à conserver les redondantes. Tester tous les sous-ensembles est exclu : pour d features, il y a 2^d possibilités (2^20 dépasse le million). On reformule donc en recherche locale gloutonne (greedy local search) :

• Sélection séquentielle avant (forward sequential selection) : on part du sous-ensemble vide et on ajoute une feature à la fois. Bon choix s'il y a beaucoup de features non pertinentes (coût moindre, sous-ensembles plus petits), au risque de rater les features interagissantes.
• Sélection séquentielle arrière (backward sequential selection) : on part de toutes les features et on en retire une à la fois. Plus coûteux, mais capable de conserver des ensembles de features interagissantes. À préférer si la performance prime sur le coût de calcul.

Au lieu d'un filtre, on peut utiliser un wrapper, qui évalue un sous-ensemble par la performance réelle d'un modèle entraîné dessus : plus coûteux (un modèle par sous-ensemble candidat), mais il intègre le biais inductif de l'algorithme cible.

Forces, faiblesses et dérive de concept

Une finesse pour conclure. Étant un apprenant paresseux, le plus proche voisin est lent à prédire sur de très gros jeux (il compare la requête à toutes les instances) — un k-d tree atténue ce coût au prix d'un prétraitement. En revanche, sa paresse le rend robuste à la dérive de concept (concept drift), ce phénomène où la relation entre features et cible évolue dans le temps (le spam de 2014 ne ressemble pas à celui de 1994). Là où un apprenant empressé verrait son abstraction se périmer et devrait être réentraîné, le plus proche voisin se met à jour en ajoutant simplement les nouvelles instances vérifiées.

L'épilogue du livre éclaire une limite plus profonde. Le lendemain, le lieutenant-colonel découvre que l'animal n'était pas un canard : c'était un ornithorynque, inconnu des Européens. L'apprentissage supervisé repose sur l'hypothèse de stationnarité (stationarity assumption) — les données ne changent pas, et aucune cible inédite n'apparaît — et classe toujours une requête parmi les cibles vues à l'entraînement. Un modèle entraîné à distinguer lions, grenouilles et canards classera tout, y compris un ornithorynque, comme l'un des trois. Détecter qu'une requête est trop différente pour appartenir à une classe connue relève d'autres champs (détection d'anomalies, classification à une classe).

À retenir

• Le biais inductif de l'apprentissage par similarité : des instances aux features semblables ont des cibles semblables. On représente les données dans un espace de features et on mesure la ressemblance par une distance.
• La famille Minkowski unifie Manhattan (p = 1, sensible à beaucoup de petits écarts) et Euclidienne (p = 2, dominée par un gros écart, choix par défaut) ; le plus proche voisin construit un modèle global implicite (mosaïque de Voronoï) à partir de modèles locaux.
• Contre le bruit, on passe à k-NN (vote majoritaire) : k trop petit = sur-apprentissage, trop grand = sous-apprentissage et domination de la majorité sur jeu déséquilibré ; le k-NN pondéré par l'inverse du carré de la distance lisse la frontière.
• La normalisation (par plage, dans [0, 1]) est quasi obligatoire : sans elle, une feature à grandes valeurs (le salaire) écrase les autres (l'âge) et fausse les prédictions.
• Les arbres k-d accélèrent la recherche des voisins par élagage (efficaces si ≈ 2^m instances pour m features) ; d'autres mesures — Jaccard (binaire clairsemé), cosinus (mélange plutôt qu'amplitude), Mahalanobis (données covariantes) — remplacent l'euclidienne selon le profil des données.
• La malédiction de la dimension : à nombre d'instances constant, chaque dimension vide l'espace ; le remède est la sélection de features (filtre rapide, ou wrapper plus précis ; recherche séquentielle avant ou arrière) pour garder le plus petit sous-ensemble utile.
• Le plus proche voisin est un apprenant paresseux : facile à interpréter et robuste à la dérive de concept, mais lent à prédire, sensible à la dimension et aux valeurs manquantes — et incapable, par construction, de reconnaître un ornithorynque qu'il n'a jamais vu.