Plus proches voisins

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• énoncer la règle des $k$ plus proches voisins en classification et en régression, avec ses conventions d'égalité, et l'appliquer à la main comme en Python;
• choisir une distance (euclidienne, de Manhattan), expliquer pourquoi un simple changement d'unité peut changer les voisins, et standardiser les caractéristiques sans fuite de données;
• décrire les frontières de décision de la règle, des cellules de Voronoi pour $k=1$ jusqu'aux régions lissées des grands $k$, et démontrer que l'erreur d'entraînement du plus proche voisin est nulle;
• relier le choix de $k$ au compromis biais–variance, le démontrer pour la régression, et choisir $k$ par validation croisée par exclusion;
• pondérer les votes par la distance et dire ce que cette pondération change, à l'entraînement comme au test;
• quantifier la malédiction de la dimension par un calcul exact et par une expérience, et estimer le coût d'une requête, avec et sans arbre $k$-d.

Du plus proche voisin aux $k$ plus proches voisins

Le chapitre 1 a présenté la règle du plus proche voisin (définition 1.9): pour prédire l'étiquette d'un nouveau point, on cherche l'exemple le plus proche dans le jeu de données et l'on recopie son étiquette. Sur le jeu B — les seize courriels, des données fictives, construites pour le cours —, l'exemple 1.3 a classé le nouveau courriel $\mathbf{x}=(2,5;2)$ comme pourriel, parce que son plus proche voisin est E15, un pourriel. Et il a aussitôt noté le problème: E15 est précisément l'exemple «du mauvais côté», un pourriel isolé parmi les courriels légitimes. La règle a suivi une exception.

L'idée de ce chapitre tient en une phrase: au lieu de demander l'avis d'un seul voisin, on en consulte plusieurs et on les fait voter. Un voisin isolé et atypique est alors mis en minorité par ceux qui l'entourent. Cette idée simple pose aussitôt des questions qui occupent tout le chapitre. Combien de voisins? Que veut dire «proche» quand les caractéristiques n'ont pas la même unité? À quoi ressemble la règle de décision dans le plan? Et pourquoi une méthode aussi intuitive se dérègle-t-elle quand la dimension augmente?

Pour $k=1$, la définition redonne exactement la règle 1-PPV du chapitre 1, avec la même convention: à distance égale, le premier exemple du jeu de données l'emporte. Notre convention pour les voix est dans le même esprit — on remonte la liste rangée et le premier gagne —, et elle a une conséquence simple: une égalité des voix est tranchée par le plus proche des voisins concernés. D'autres conventions existent (tirer au sort, retirer le voisin le plus lointain et recompter, choisir la plus petite étiquette), et les bibliothèques ne choisissent pas toutes la même; un résultat qui dépend de la convention est un résultat fragile, et il vaut la peine de le savoir. En classification binaire, on évite la question en prenant $k$ impair: deux classes ne peuvent pas se partager un nombre impair de voix à égalité.

Comme pour le plus proche voisin, il n'y a rien à entraîner: le «modèle» est le jeu de données lui-même, conservé tel quel, et tout le calcul a lieu au moment de la prédiction. On parle d'apprentissage paresseux (lazy learning), par opposition à la régression linéaire ou logistique, qui résument les données en quelques paramètres une fois pour toutes et oublient ensuite les exemples. Le nombre $k$ n'est pas appris: c'est un hyperparamètre, au sens du chapitre 1, et il faudra le choisir sans tricher. Dans ce cours, la lettre $k$ désigne toujours un nombre de voisins; le nombre de groupes du partitionnement (chapitre 12) s'écrit $K$, et ce n'est pas la même chose.

La figure 7.1 rend le vote visible. Le petit disque ne contient que E15; le disque de rayon $1,5$ attrape E2 et E6, et touche E6 sur son bord — c'est le troisième voisin qui fixe le rayon; le grand disque englobe deux légitimes de plus. Ce qui compte n'est pas le rayon, mais le nombre de points qu'il faut englober: le $k$-PPV adapte la taille de son voisinage à la densité locale des données. Là où les exemples sont serrés, il regarde près; là où ils sont rares, il va chercher loin, et l'on verra dans la section sur la malédiction de la dimension que «loin» peut devenir très loin.

Programmer la règle demande deux fonctions: l'une range les exemples et garde les $k$ premiers, l'autre compte les voix. Le rangement le plus simple est un tri de couples (distance, indice): Python compare les couples composante par composante, si bien qu'à distance égale l'indice le plus petit passe devant — c'est exactement la convention de la définition 7.1, sans une ligne de plus.

La régression par les $k$ plus proches voisins

Rien dans l'idée du vote n'est propre à la classification. Si l'étiquette est un nombre, les voisins ne votent pas: on fait la moyenne de leurs étiquettes.

La moyenne n'est pas un choix arbitraire: le théorème 1.2 dit qu'elle est la constante qui minimise la perte carrée sur les étiquettes des voisins. La règle $k$-PPV en régression revient donc à ajuster, autour de chaque point $\mathbf{x}$, un prédicteur constant sur les seuls exemples proches. Avec la perte absolue, on prendrait la médiane des voisins, pour la même raison (théorème 1.3).

Distances et mise à l'échelle

La règle des $k$ plus proches voisins ne connaît des données que leurs distances. Tout ce que l'on sait du problème — quelles caractéristiques comptent, dans quelle unité, avec quel poids — doit donc passer par le choix de la distance. C'est la décision la plus importante, et la plus souvent prise sans y penser.

La distance de Manhattan doit son nom aux rues à angle droit: c'est la longueur d'un trajet qui ne peut se déplacer que parallèlement aux axes. Ses «boules» sont des losanges, celles de la distance euclidienne des disques. Elle est moins sensible qu'une distance euclidienne à un grand écart sur une seule coordonnée, qui n'y est pas élevé au carré.

Sur le jeu B, avec la distance de Manhattan, les voisins de $\mathbf{x}=(2,5;2)$ sont E15 (distance $0,5$), puis E2 et E6, tous deux à distance $1,5$ — E2 à $0,5+1$, E6 à $1,5+0$ —, puis E3, E4 et E5, tous trois à $2,5$. Les égalités se multiplient, parce que les coordonnées sont entières et que la distance ne fait qu'additionner: la convention de la définition 7.1 range E2 avant E6, et E3 avant E4 avant E5. Les verdicts, eux, ne changent pas: pourriel pour , légitime pour et . Sur des données aussi simples, la distance compte moins que l'échelle des caractéristiques, à laquelle nous venons.

Pourquoi l'échelle compte

Les deux caractéristiques du jeu B ont des unités arbitraires: $x_1$ est un taux de mots suspects pour mille, $x_2$ une part de majuscules en pour cent. Rien n'obligeait à ces choix. Un autre ingénieur aurait pu mesurer $x_1$ pour dix mille mots, et multiplier ainsi toutes ses valeurs par 10 sans rien changer aux courriels.

La standardisation est invariante par changement d'unité: si $x_j$ devient $c{x}_j$ avec $c>0$, alors ${\bar{x}}_j$ devient , devient , et le quotient (7.4) ne change pas. C'est exactement la propriété qui manquait à la distance brute. La standardisation ne dit pas pour autant que toutes les caractéristiques compter autant: elle remplace un choix accidentel (l'unité) par un choix explicite (le même poids pour un écart type de chaque caractéristique). Si l'on sait qu'une caractéristique compte davantage, on peut ensuite la multiplier par un poids — c'est alors une décision, plus un accident.

Le chapitre 3 a rencontré la standardisation pour une autre raison: elle améliore le conditionnement de la descente de gradient sur le jeu A. Ici, elle ne rend pas un calcul plus rapide; elle change le modèle lui-même, puisque les voisins dépendent de l'échelle. La mise à l'échelle min–max a la même invariance, mais elle dépend de deux valeurs seulement, les extrêmes: un seul courriel aberrant avec $x_1=90$ écraserait tous les autres dans le premier dixième de l'intervalle. La standardisation, qui s'appuie sur toutes les valeurs, y est moins sensible, sans être robuste pour autant (la moyenne et l'écart type suivent les valeurs aberrantes, comme l'a montré l'exemple 1.2).

Une dernière remarque sur les distances, qui annonce la fin du chapitre: la standardisation égalise les échelles, elle ne trie pas les caractéristiques. Ajoutez au jeu B une troisième caractéristique sans aucun rapport avec les pourriels — l'heure d'envoi à la seconde près, par exemple —, standardisez-la comme les autres: elle pèsera autant que $x_1$ et $x_2$ dans la distance, et les voisins seront en partie choisis au hasard. Le $k$-PPV n'a aucun moyen de savoir qu'une caractéristique est inutile. Une régression linéaire lui donnerait un coefficient proche de zéro; un arbre de décision (chapitre 8) la choisirait rarement près de la racine, même si un arbre profond finit par s'en servir pour ajuster le bruit de ses dernières coupures. Chaque caractéristique inutile ajoutée à la distance dégrade les voisins, et la section sur la malédiction de la dimension montre jusqu'où.

Frontières de décision

Avec deux caractéristiques, on peut voir une règle de classification tout entière: il suffit de colorier chaque point du plan selon la classe qu'elle prédit. Les régions de décision ainsi obtenues sont séparées par la frontière de décision. Pour la régression logistique du chapitre 4, la frontière est une droite. Pour le plus proche voisin, elle a une structure géométrique classique.

Chaque condition $\Vert \mathbf{x}-{\mathbf{x}}_i\Vert \le \Vert \mathbf{x}-{\mathbf{x}}_j\Vert$ définit un demi-plan (un demi-espace en dimension $d$), limité par la médiatrice du segment $[{\mathbf{x}}_i,{\mathbf{x}}_j]$: il suffit d'élever au carré et de développer, les termes en s'en vont et il reste une inégalité linéaire en (exercice 7.5). Une cellule est donc une intersection de demi-plans: un polygone convexe, éventuellement non borné. À l'intérieur de , le plus proche voisin est , et la règle 1-PPV prédit . Les régions de décision de la règle 1-PPV sont donc des : la région «pourriel» réunit les cellules des huit pourriels, la région «légitime» celles des huit courriels légitimes. La frontière de décision est faite des morceaux de médiatrices qui séparent deux exemples de classes différentes; les médiatrices entre exemples de même classe sont intérieures à une région et ne servent à rien.

La figure 7.2 montre ce que signifie «suivre les exceptions». La cellule de E15 découpe un îlot de pourriels au milieu de la région légitime, et le nouveau courriel tombe dedans: c'est la géométrie du verdict de l'exemple 1.3. Symétriquement, E8 a son îlot légitime au milieu des pourriels. La frontière épaisse fait de nombreux détours pour les entourer: elle épouse chaque exemple. Sa forme dépend de chaque point du jeu de données: déplacez E15 d'une unité, et l'îlot se déplace avec lui. C'est la marque d'un modèle à forte variance, au sens du chapitre 6.

Cette fidélité aux exemples a une conséquence que le chapitre 1 a déjà observée et que l'on peut maintenant énoncer proprement.

Démonstration. Fixons $j$ et rangeons les exemples par distance à ${\mathbf{x}}_j$. L'exemple $j$ lui-même est à distance $\Vert {\mathbf{x}}_j-{\mathbf{x}}_j\Vert =0$. Pour , les points étant distincts, , et une norme ne s'annule qu'en : . L'exemple est donc l' exemple de distance minimale; il est rangé premier sans qu'aucune convention d'égalité n'intervienne, et la règle prédit . La perte est nulle pour chaque , donc leur moyenne aussi. Rien dans l'argument n'utilise les étiquettes.

L'hypothèse «points distincts» n'est pas décorative. Si deux courriels avaient exactement les mêmes caractéristiques avec des étiquettes différentes, la convention ferait gagner le premier, et le second serait mal classé: l'erreur d'entraînement ne serait plus nulle, et aucun modèle ne pourrait faire mieux sur ces deux points. Le théorème dit aussi ce qu'il ne faut pas conclure: sur des étiquettes tirées à pile ou face, la règle 1-PPV a encore une erreur d'entraînement nulle, et une erreur de test de 50 %.

Pour $k>1$, l'exemple ${\mathbf{x}}_j$ vote encore pour lui-même — il est son propre premier voisin —, mais ses $k-1$ voisins suivants peuvent le mettre en minorité. Sur le jeu B, l'erreur d'entraînement vaut 1 sur 16 pour $k=3$ (E15, dont les deux voisins suivants, E6 et E2, sont légitimes) et 3 sur 16 pour $k=5$ (E7, E8 et E15). Elle reste optimiste: chaque exemple dispose d'une voix acquise d'avance, la sienne. L'explorateur suivant affiche côte à côte cette erreur d'entraînement et l'erreur honnête de la section suivante.

L'explorateur part de $k=3$. L'îlot de E15 a disparu: E15 est mis en minorité par E6 et E2. E8, lui, reste légitime, au bout d'une avancée de la région légitime: ses voisins sont E8 lui-même, le pourriel E16, puis trois exemples à égalité de distance $\sqrt{5}$ — E6, E9 et E11 —, et la convention retient E6, légitime, qui donne la majorité à E8. À $k=5$, E9 et E11 entrent à leur tour, E8 passe du côté des pourriels, et la frontière devient plus simple. Les cercles de l'explorateur entourent les $k$ voisins du nouveau courriel. En montant jusqu'à ou , elle se rapproche d'une ligne qui sépare grossièrement le bas à gauche du haut à droite, ce que fait la régression logistique avec une vraie droite. En passant à , vous verrez les régions se découper en bandes verticales: la distance ne voit plus que , et la part de majuscules ne sert presque plus à rien. Les points n'ont pas bougé; seule la notion de «proche» a changé.

Choisir $k$

Le nombre de voisins règle la flexibilité du modèle, de la plus grande ($k=1$, qui épouse chaque exemple) à la plus petite ($k=n$, le prédicteur constant). C'est exactement la situation que le chapitre 6 analyse avec le degré d'un polynôme, et la même décomposition s'applique. On la démontre ici dans le cas le plus simple, la régression.

Démonstration. Les voisins de $\mathbf{x}$ ne dépendent que des positions ${\mathbf{x}}_i$, qui sont fixées, et pas des étiquettes: l'ensemble $V_k(\mathbf{x})$ n'est pas aléatoire. Posons $b=f(\mathbf{x})-\frac{1}{k}{\sum }_{i\in V_k(\mathbf{x})}f({\mathbf{x}}_i)$, un nombre fixé, et . En remplaçant et chaque par leur expression,

Développons le carré et prenons l'espérance. Les trois carrés donnent $\mathbb{E}[{\epsilon }_0^2]={\sigma }^2$, $b^2$, et $\mathbb{E}[{\bar{\epsilon }}^2]=\mathrm{Var}[\bar{\epsilon }]=\frac{1}{k^2}\cdot k{\sigma }^2={\sigma }^2/k$, par indépendance des bruits (Probabilités et statistique, chapitre 7). Les doubles produits sont nuls: , de même , et puisque est indépendant des . Il reste (7.6).

La variance ${\sigma }^2/k$ décroît avec $k$: moyenner $k$ étiquettes bruitées divise la variance du bruit par $k$. Le biais, lui, compare $f(\mathbf{x})$ à la moyenne de $f$ sur les voisins; il est petit si les voisins sont proches et que $f$ varie peu, et il grandit en général avec $k$, puisque les voisins supplémentaires sont plus loin. Mais «en général» n'est pas «toujours», comme le montre le calcul suivant.

Le théorème et l'exemple disent la même chose que le chapitre 6, avec un vocabulaire différent: un petit $k$ donne un faible biais et une forte variance, un grand $k$ l'inverse. Une manière de le retenir: la règle à $k$ voisins sur $n$ exemples se comporte un peu comme un modèle à environ $n/k$ paramètres, puisqu'elle découpe l'espace en régions qui contiennent chacune de l'ordre de $k$ exemples. Pour $k=1$, autant de «paramètres» que d'exemples, et l'erreur d'entraînement est nulle; pour $k=n$, un seul, la moyenne.

Mais aucune de ces deux grandeurs ne se calcule sur de vraies données: il faudrait connaître $f$. Pour choisir $k$, on mesure donc directement l'erreur sur des exemples qui n'ont pas servi à prédire. Le chapitre 1 a fait tourner l'ensemble de test par quarts (exemple 1.4); le chapitre 5 formalise cette validation croisée en plusieurs plis — un nombre de plis qui n'a rien à voir avec le nombre $k$ de voisins. Avec seize exemples, on peut pousser l'idée jusqu'au bout.

Pour la règle des $k$ plus proches voisins, la validation croisée par exclusion est particulièrement bon marché: il n'y a rien à réentraîner, il suffit d'exclure l'exemple $j$ de ses propres voisins. Sur le jeu B, avec la distance euclidienne et les unités d'origine, voici le nombre d'erreurs pour les valeurs impaires de $k$:

Plusieurs choses se lisent sur ce tableau.

• L'erreur d'entraînement ment le plus pour $k=1$, où elle vaut 0 alors que l'erreur LOO vaut $5/16=31,25$ %. Les cinq erreurs sont E6, E7, E8, E15 et E16: les deux exceptions; E6 et E16, dont le plus proche voisin est une exception (E15 et E8); et E7, plus proche du pourriel E12 que de tout courriel légitime.
• Le minimum, 2 erreurs sur 16, est atteint pour $k=7$, $9$ et $11$, et ces deux erreurs sont toujours E8 et E15. C'est le mieux que l'on puisse espérer d'une règle qui suit la tendance: les deux exceptions sont mal classées, tous les autres bien. Le choix naturel est le plus petit de ces $k$, soit $k=7$, ou celui du milieu si l'on veut s'éloigner des deux bords du plateau.

Il faut lire ces chiffres avec la prudence de l'exemple 1.4. Un écart de deux erreurs sur seize exemples n'est pas significatif; le chapitre 1 a d'ailleurs obtenu $3/16$ pour la règle 1-PPV avec quatre plis de quatre, contre $5/16$ ici avec seize plis d'un: ce sont deux estimations bruitées d'une même erreur. Et un détail de convention compte: pour $k=3$, l'exemple E12 $(4,5)$ a pour voisins E10, puis E7, puis — à égalité, à distance $\sqrt{8}=2,828$ — E8 et E14. La convention retient E8, légitime, et E12 est mal classé; l'autre choix l'aurait bien classé. Une erreur sur seize dépend ici de l'ordre dans lequel les courriels ont été numérotés.

Votes pondérés

Dans le vote de la définition 7.1, le premier voisin et le $k$-ième pèsent autant, même si l'un est tout près et l'autre très loin. Pour le nouveau courriel, avec $k=5$, E15 à distance $0,5$ et E4 à distance $2,062$ ont chacun une voix. Il est naturel de donner plus de poids aux voisins plus proches.

Au nouveau courriel, avec $k=3$, le pourriel E15 reçoit le poids $1/0,5=2$, et les deux légitimes E2 et E6 reçoivent $1/1,118=0,894$ et $1/1,5=0,667$, soit $1,561$ ensemble. Le pourriel l'emporte, 2 contre 1,561: le vote pondéré à trois voisins rend le verdict du plus proche voisin. Avec $k=5$, E5 et E4 ajoutent et aux légitimes, qui totalisent et l'emportent. La pondération rapproche donc la règle du plus proche voisin: un voisin très proche pèse plusieurs voix, et il faut davantage de voisins pour le mettre en minorité. En régression, l'appartement de 80 m² de l'exemple 7.2 reçoit, avec et des poids , et , la prédiction CHF 2 168,18, plus proche du loyer de son plus proche voisin (CHF 2 350) que la moyenne simple (CHF 2 116,67).

Le vote pondéré par $1/\mathrm{dist}$ a une propriété qu'il faut connaître: son erreur d'entraînement est nulle pour tout $k$. Un exemple d'entraînement est à distance nulle de lui-même, son poids est infini, et il décide seul — c'est le théorème 7.1, qui vaut désormais quel que soit le nombre de voisins. L'erreur d'entraînement ne dit donc rien du tout pour ce modèle, et seule la validation croisée le juge. Sur le jeu B, la validation par exclusion du vote pondéré donne 5, 5, 4, 2, 2, 2, 2 et 4 erreurs pour $k=1,3,5,\dots ,15$: le minimum est le même que pour le vote simple, mais le désastre de $k=15$ disparaît, parce que les voisins proches gardent l'avantage même quand tout le monde vote.

D'autres poids sont possibles. Le plus courant après $1/\mathrm{dist}$ est le poids gaussien $w_i=\exp (-\mathrm{dist}(\mathbf{x},{\mathbf{x}}_i{)}^2/(2h^2))$, qui ne devient jamais infini et dont la joue le rôle de : petite, seuls les voisins très proches comptent; grande, tous comptent presque autant. Avec ce poids, on peut même laisser voter les exemples, les lointains ayant un poids négligeable. On obtient alors une méthode à noyau, et le noyau gaussien reviendra au chapitre 9, dans les machines à vecteurs de support et la régression ridge à noyau.

La malédiction de la dimension

Tout ce qui précède repose sur une intuition: les plus proches voisins d'un point sont proches, donc semblables. En dimension 2, avec des données raisonnablement denses, c'est vrai. Mais les problèmes réels ont souvent des dizaines, des centaines ou des milliers de caractéristiques, et l'intuition s'y effondre. Le phénomène a reçu un nom dramatique, la malédiction de la dimension (curse of dimensionality), et il se démontre en quelques lignes.

Démonstration. Un point $\mathbf{u}\in [0,1{]}^d$ est à distance au moins $\epsilon$ de la frontière si et seulement si chacune de ses coordonnées vérifie $\epsilon \le u_j\le 1-\epsilon$: la frontière est faite des faces $u_j=0$ et , et la distance de à la face est , à la face est . Ces points forment le cube intérieur , de côté et donc de volume . La coquille est le complémentaire, de volume , puisque le cube unité a un volume 1. Comme , la puissance tend vers 0 et la fraction tend vers 1. L'inégalité vient de pour tout réel (la fonction est convexe et est sa tangente en 0, Analyse I), appliquée à puis élevée à la puissance , les deux membres étant positifs. Enfin, pour un point uniforme, la probabilité d'être dans la coquille est son volume; la proportion de points dans la coquille est une moyenne de indicatrices d'espérance , d'où la dernière affirmation par linéarité.

Prenons une coquille fine, $\epsilon =0,05$, soit 5 % du côté de chaque bord. En dimension 2, elle contient $1-0,9^2=19$ % du carré. En dimension 10, déjà $65,1$ %. En dimension 20, $87,8$ %. En dimension 100, $99,997$ %, et la minoration (7.8) garantit à elle seule plus de $1-{\mathrm{e}}^{-10}=99,995$ %. Un point tiré au hasard en dimension 100 est presque sûrement — sur au moins une de ses cent coordonnées, il est dans les 5 % extrêmes. Dans un tel espace, l'idée d'un point «typique, au milieu des autres» n'a plus de sens.

Le même calcul dit autre chose sur les voisinages. Pour capturer une fraction $r$ des points uniformes du cube avec un sous-cube, il faut un sous-cube de volume $r$, donc de côté $r^{1/d}$. Pour en capturer 1 %, il faut un côté de $0,1$ en dimension 2, mais de $0,631$ en dimension 10 et de $0,955$ en dimension 100: le «voisinage» qui contient 1 % des données couvre 95,5 % de l'étendue de chaque caractéristique. Ces voisins ne sont plus voisins de rien.

Le théorème 7.3 parle de volumes. Le $k$-PPV, lui, compare des distances, et l'expérience suivante mesure directement ce qui lui arrive: on tire 500 points et 20 requêtes uniformes dans $[0,1{]}^d$, et pour chaque requête on divise la distance au plus proche des 500 points par la distance au plus lointain.

import math
import random

random.seed(0)


def rapport_moyen(d, n=500, requetes=20):
    """Moyenne, sur des requetes uniformes, de (plus proche) / (plus lointain)."""
    total = 0.0
    for _ in range(requetes):
        x = [random.random() for _ in range(d)]
        distances = []
        for _ in range

d =   1: 0.001
d =   2: 0.023
d =   5: 0.132
d =  10: 0.305
d =  20: 0.455
d =  50: 0.614
d = 100: 0.713
d = 500: 0.861

En dimension 2, le plus proche des 500 points est à environ 2 % de la distance du plus lointain: les voisins sont vraiment proches, et le contraste entre «proche» et «loin» est énorme. En dimension 100, le plus proche est à 71 % de la distance du plus lointain; en dimension 500, à 86 %. Toutes les distances se ressemblent. Ranger les points par distance ne sépare plus grand-chose, et une petite perturbation des données — un peu de bruit sur chaque coordonnée — suffit à changer l'ordre des voisins. On peut montrer que, pour des coordonnées indépendantes, ce rapport tend vers 1 quand $d$ croît, la dispersion relative des distances diminuant comme $1/\sqrt{d}$; nous l'admettons ici, l'expérience suffisant à fixer les idées.

Faut-il en conclure que le $k$-PPV est inutilisable dès que $d$ dépasse 10? Non, et c'est la nuance qui sauve la méthode. Le théorème et l'expérience portent sur des points uniformes dans un cube, dont chaque coordonnée est indépendante des autres. Les données réelles sont rarement ainsi: des images de chiffres manuscrits ont des centaines de pixels, mais les images plausibles n'occupent qu'une toute petite partie de l'espace de tous les tableaux de pixels possibles, une «surface» de faible dimension intrinsèque repliée dans un grand espace. Sur une telle surface, les voisins redeviennent significatifs. Deux remèdes en découlent: retirer les caractéristiques inutiles, qui ajoutent des dimensions sans ajouter d'information (la fin de la section sur l'échelle), et réduire la dimension avant de chercher des voisins, ce que fait l'analyse en composantes principales du chapitre 13.

Le coût d'une requête

La règle des $k$ plus proches voisins n'a pas de phase d'entraînement, ou presque: il suffit de ranger les données en mémoire, $n\times d$ nombres. Tout le coût est reporté sur la prédiction. Pour un point $\mathbf{x}$, l'algorithme naïf calcule les $n$ distances, chacune en $O(d)$ opérations, puis sélectionne les $k$ plus petites. Un tri complet coûte $O(n\log n)$ comparaisons; un tas de taille $k$ ou une sélection partielle font mieux, en ou . Le terme dominant reste le calcul des distances:

Avec un million d'exemples à 100 caractéristiques, chaque prédiction demande $10^6\times 100=10^8$ soustractions, multiplications et additions. Un ordinateur portable en fait de l'ordre de quelques centaines de millions à quelques milliards par seconde dans un langage compilé, bien moins en Python pur: une prédiction prend une fraction de seconde, ce qui est acceptable pour une requête, et rédhibitoire pour en classer des millions. C'est exactement le contraire d'un modèle paramétrique: la régression logistique coûte cher à entraîner et $O(d)$ par prédiction, quel que soit $n$.

Pour accélérer la recherche, on organise les données à l'avance dans une structure qui permet d'écarter des régions entières sans calculer les distances de leurs points. La plus classique est l'arbre $k$-d (k-d tree, pour k-dimensional tree; ici, par tradition, $k$ désigne la dimension, pas le nombre de voisins).

La recherche du plus proche voisin descend d'abord dans l'arbre comme si l'on y insérait $\mathbf{x}$, jusqu'à une feuille, en calculant au passage la distance à chaque nœud visité et en retenant la meilleure, $d^{\ast }$. Puis elle remonte, et à chaque nœud elle se demande s'il faut explorer l'autre sous-arbre: c'est inutile si la distance de $\mathbf{x}$ à l'hyperplan de coupure dépasse $d^{\ast }$, car tous les points de l'autre côté sont alors plus loin que $d^{\ast }$.

Construisons-le sur le jeu B. Rangés selon $x_1$, avec la convention habituelle à égalité, les seize courriels ont pour neuvième élément — le médian de rang $\lfloor 16/2\rfloor +1$ — E12 $(4,5)$: c'est la racine, et elle coupe selon $x_1=4$. Le sous-arbre gauche reçoit les huit courriels qui précèdent E12 dans ce rangement (E1 à E7 et E15, tous avec $x_1\le 4$), le sous-arbre droit les sept qui le suivent (E8, E9, E10, E11, E13, E14 et E16, tous avec ). Cherchons le plus proche voisin du nouveau courriel . La descente part à gauche, puisque , et après exploration du sous-arbre gauche la meilleure distance est (E15). En remontant à la racine, la distance du nouveau courriel au plan de coupure vaut : aucun courriel du sous-arbre droit ne peut battre E15, et les sept sont écartés sans calcul. La recherche a calculé — la racine et les huit courriels du sous-arbre gauche.

Sur seize points, le gain est modeste. Sur un million de points en dimension 2 ou 3, il est spectaculaire: la recherche ne visite en général qu'un nombre de nœuds de l'ordre de $\log n$, et les arbres $k$-d sont l'outil standard des systèmes d'information géographique ou des simulations physiques. Mais la malédiction de la dimension les rattrape: en grande dimension, la distance au plus proche voisin est comparable à celle de tous les autres (figure 7.3), elle dépasse donc la distance à presque tous les hyperplans de coupure, et l'élagage ne se déclenche plus. Au-delà de quelques dizaines de dimensions, un arbre $k$-d visite la plupart des nœuds et ne fait guère mieux que la recherche exhaustive. On recourt alors à des méthodes de recherche approchée (approximate nearest neighbours), qui acceptent de manquer parfois le vrai plus proche voisin en échange d'une recherche beaucoup plus rapide: hachage sensible à la localité (locality-sensitive hashing), graphes de proximité. Elles sont au cœur des moteurs de recherche par similarité d'images ou de textes, où les objets sont représentés par des vecteurs de plusieurs centaines de dimensions (chapitre 13).

Synthèse

• La règle des $k$ plus proches voisins prédit par un vote majoritaire des $k$ exemples les plus proches (classification) ou par la moyenne de leurs étiquettes (régression). Elle n'a pas de paramètre appris: le jeu de données est le modèle, et tout le travail se fait à la prédiction. Les égalités de distance se tranchent en faveur du premier exemple du jeu, les égalités de voix en faveur du voisin le mieux classé; avec deux classes, un $k$ impair les évite. Au nouveau courriel $(2,5;2)$, $k=1$ prédit pourriel (E15), $k=3$ et $k=5$ prédisent légitime.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Hastie, T., Tibshirani, R. et Friedman, J., The Elements of Statistical Learning, Springer, 2ᵉ éd., 2009, chap. 2 (plus proches voisins et malédiction de la dimension) et chap. 13 (méthodes à prototypes et plus proches voisins).
• James, G., Witten, D., Hastie, T. et Tibshirani, R., An Introduction to Statistical Learning, Springer, 2ᵉ éd., 2021, chap. 2 et 3 (classifieur des $k$ plus proches voisins, comparaison avec la régression linéaire).
• Shalev-Shwartz, S. et Ben-David, S., Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, 2014, chap. 19 (plus proches voisins, analyse et malédiction de la dimension).
• Azencott, C.-A., Introduction au Machine Learning, Dunod, 2ᵉ éd., 2022 (méthodes des plus proches voisins, en français).
• Cover, T. M. et Hart, P. E., «Nearest neighbor pattern classification», IEEE Transactions on Information Theory, 1967.
• Bentley, J. L., «Multidimensional binary search trees used for associative searching», Communications of the ACM, 1975.