Exercices corrigés de NSI Première : l'algorithme des k plus proches voisins

a) On calcule les écarts de coordonnées, puis on applique la formule. Pour A : écarts $6$ et $0$, donc $\sqrt{36+0}=6$. Pour B : écarts $-3$ et $4$, donc $\sqrt{9+16}=\sqrt{25}=5$. Pour C : $-6$ et $8$, donc $\sqrt{36+64}=10$. Pour D : $12$ et $-5$, donc $\sqrt{144+25}=\sqrt{169}=13$. Pour E : $0$ et $-8$, donc $8$. Le signe d'un écart ne compte pas, puisqu'on l'élève au carré ; en revanche il ne faut surtout pas additionner les écarts AVANT de les élever au carré : $(-3+4)^{2}=1$ n'a rien à voir avec $9+16=25$. Écrire le détail des écarts sur la copie est ce qui rend l'erreur visible au correcteur, et à vous.

b) La distance de Manhattan additionne les valeurs absolues des écarts : A $6+0=6$, B $3+4=7$, C $6+8=14$, D $12+5=17$, E $0+8=8$. Le nom vient des rues à angle droit d'une ville quadrillée : pour aller d'un carrefour à un autre, on ne traverse pas les pâtés de maisons en diagonale, on suit les rues. La valeur absolue est indispensable ; sans elle, les écarts de B, $-3$ et $+4$, se compenseraient et donneraient $1$, une distance absurdement petite. Ce piège revient en Python à l'exercice 2.

c) Avec la distance euclidienne, le plus proche est B, à $5$ : l'algorithme prédit une POIRE. Avec la distance de Manhattan, le plus proche est A, à $6$, devant B à $7$ : il prédit une POMME. Même table, même fruit, même $k$, et deux réponses opposées. C'est le fil de toute la série : le vote ne décide rien, c'est la distance qui choisit les votants. B est proche en diagonale, A est proche en ligne droite le long d'un axe, et les deux distances ne récompensent pas la même chose. Le choix de la distance fait donc partie de l'algorithme, au même titre que $k$, et un énoncé qui ne la précise pas est incomplet.

d) Euclidienne, par distances croissantes : B $5$, A $6$, E $8$, C $10$, D $13$. Les trois premiers sont B, A, E : deux pommes contre une poire, prédiction pomme. Manhattan : A $6$, B $7$, E $8$, C $14$, D $17$ ; les trois premiers sont A, B, E, et la prédiction est encore pomme. Avec trois votants, le désaccord de $k=1$ disparaît : un seul voisin ne pèse plus tout le vote. Enfin, pour deux écarts $a$ et $b$, $(|a|+|b|)^{2}=a^{2}+b^{2}+2|a||b|\ge a^{2}+b^{2}$, et les deux membres étant positifs, $|a|+|b|\ge\sqrt{a^{2}+b^{2}}$. Géométriquement, l'escalier qui suit le quadrillage est plus long que la diagonale, sauf quand l'un des écarts est nul, comme pour A et E où les deux distances coïncident.

a) Les écarts sont $1-3=-2$, $5-1=4$ et $2-6=-4$. Au premier tour, s passe de $0$ à $(-2)^{2}=4$ ; au deuxième, à $4+16=20$ ; au troisième, à $20+16=36$. La fonction renvoie $\sqrt{36}=6$, écrit 6.0 par Python puisque sqrt renvoie toujours un flottant. La boucle parcourt les INDICES, et non les valeurs, parce qu'il faut lire la même coordonnée dans p et dans q au même tour. C'est aussi ce qui rend la fonction valable en dimension quelconque : deux, trois ou vingt attributs, le code ne change pas. En évaluation, une trace à trois lignes, une par tour, est la réponse attendue à « que renvoie cette fonction ».

b) La ligne manquante est s = s + abs(p[i] - q[i]), et la version correcte renvoie $2+4+4=10$. Sans abs, les écarts s'ajoutent avec leur signe : $-2+4-4=-2$. La fonction renvoie alors une « distance » NÉGATIVE, et surtout, elle peut déclarer très proches deux points très éloignés dont les écarts se compensent : $(0, 0)$ et $(5, -5)$ seraient à distance $0$. Aucune erreur n'est levée, le programme tourne et prédit n'importe quoi. Le contrôle qui attrape ce défaut tient en une ligne : une distance est toujours positive ou nulle, et elle est nulle seulement entre deux points identiques. Un seul résultat négatif dans une trace suffit à condamner la fonction.

c) Les voisins ne changent pas. La racine carrée est une fonction STRICTEMENT CROISSANTE sur les nombres positifs : si $a<b$ alors $\sqrt{a}<\sqrt{b}$, et réciproquement. Classer les éléments par carré de distance ou par distance donne donc exactement le même ordre : v ($25$, distance $5$), puis u ($36$, distance $6$), puis w ($49$, distance $7$). Le plus proche est v. Supprimer la racine est une optimisation courante et légitime, qui économise un calcul par élément de la table. Elle devient fausse dès qu'on utilise la VALEUR de la distance et plus seulement son rang, par exemple pour ne garder que les voisins à moins de $6$ : il faudrait alors comparer le carré à $36$, pas à $6$.

d) Le premier appel renvoie $5{,}0$. La boucle tourne sur range(len(p)), donc sur deux indices seulement : $3^{2}+4^{2}=25$, et la troisième coordonnée de q, $12$, est ignorée sans un mot. Le second appel fait trois tours, et au troisième il lit q[2], qui n'existe pas : IndexError. Le même oubli donne donc, selon l'ordre des arguments, une erreur ou un résultat faux, et le résultat faux est le plus dangereux des deux, puisqu'on ne le voit pas. La distance n'a de sens qu'entre deux p-uplets de même longueur : c'est une PRÉCONDITION, qui s'écrit assert len(p) == len(q) en première ligne. Dans une table chargée depuis un fichier, une ligne à qui il manque une colonne produit exactement ce défaut.

def distance_manhattan(p, q):
    assert len(p) == len(q), 'p et q doivent avoir la même longueur'
    s = 0
    for i in range(len(p)):
        s = s + abs(p[i] - q[i])
    return s

assert distance_manhattan((1, 5, 2), (3, 1, 6)) == 10
assert distance_manhattan((0, 0), (5, -5)) == 10

a) Écarts à $(10{,}5\,;7{,}5)$ : G1 $(1\,;0{,}5)$, d2 $=1+0{,}25=1{,}25$ ; G2 $(-1\,;0)$, d2 $=1$ ; G3 $(0{,}5\,;-0{,}5)$, d2 $=0{,}25+0{,}25=0{,}5$ ; G4 $(-1{,}5\,;0{,}5)$, d2 $=2{,}25+0{,}25=2{,}5$ ; G5 $(-1\,;-1)$, d2 $=2$ ; G6 $(1{,}5\,;1)$, d2 $=2{,}25+1=3{,}25$. Aucune racine à calculer : l'exercice 2 a montré que le carré suffit pour CLASSER. Piège de calcul fréquent : $0{,}5^{2}=0{,}25$ et non $0{,}5$, un carré de nombre inférieur à $1$ est plus petit que lui.

b) L'instruction (2) trie grains SUR PLACE, et la méthode sort renvoie None : voisins vaut donc None, et la ligne suivante, voisins[0], lève une erreur. L'instruction (3) appelle d2 tout de suite, avec la liste entière comme argument ; g['longueur'] sur une liste lève une TypeError, les indices d'une liste étant des entiers. Le paramètre key attend une FONCTION, que sorted appellera elle-même sur chaque élément : on écrit key=d2, le nom seul, sans parenthèses. On garde donc l'instruction (1). Retenez la paire : liste.sort() modifie la liste et ne renvoie rien ; sorted(liste) ne modifie rien et renvoie une nouvelle liste.

c) Rangés par d2 croissant : G3 $0{,}5$, G2 $1$, G1 $1{,}25$, G5 $2$, G4 $2{,}5$, G6 $3{,}25$. Pour $k=3$, les votants sont G3 arabica, G2 robusta, G1 arabica : deux voix contre une, prédiction arabica. Pour $k=5$, G5 et G4, deux robusta, rejoignent le vote : trois robusta contre deux arabica, prédiction robusta. La prédiction bascule entre $k=3$ et $k=5$ sans que la table ni le grain aient changé. Les voisins s'obtiennent par une tranche, voisins[:k], et la tranche garde l'ordre du tri : c'est pourquoi on trie D'ABORD et on coupe ENSUITE.

d) Le premier élément de grains est toujours G1, l'ordre de la table n'a pas bougé. C'est préférable parce que la table sert à TOUTES les prédictions : la suivante trie par rapport à une autre cible, et un tri sur place laisserait la table dans l'ordre d'une cible passée, ce qui ne fausse pas le résultat mais rend illisible tout affichage fondé sur la position, « le troisième grain de la table ». La fonction qui prédit ne doit pas modifier les données qu'on lui confie : c'est un effet de bord. Le prix de sorted est une copie de la liste des références, négligeable ici.

a) La boucle lit les sept étiquettes dans l'ordre. Charbonnière apparaît aux rangs $1$, $4$ et $6$, bleue aux rangs $2$ et $5$, nonnette aux rangs $3$ et $7$. D'où compteurs = {'charbonnière': 3, 'bleue': 2, 'nonnette': 2}. Vérification immédiate : la somme des compteurs vaut $7$, le nombre de votants. Le dictionnaire garde l'ORDRE D'INSERTION des clés, celui de leur première apparition : charbonnière, puis bleue, puis nonnette. Ce détail décide de la question d).

b) La condition est compteurs[e] > compteurs[gagnante] : on garde e si elle a strictement plus de voix que la meilleure vue jusqu'ici. C'est le schéma du maximum, appliqué aux VALEURS du dictionnaire, en retenant la CLÉ qui les porte. Le test gagnante is None traite le premier tour, où il n'existe encore aucune gagnante à battre. La fonction renvoie 'charbonnière', avec $3$ voix sur $7$, soit $\frac{3}{7}\approx 0{,}43$. Ce n'est PAS une majorité absolue : avec trois classes, la classe gagnante peut rassembler moins de la moitié des voix. « Classe majoritaire » veut dire ici la plus représentée, la majorité relative, et un énoncé qui demande « plus de la moitié des voisins » pose une autre question.

c) max(compteurs) parcourt le dictionnaire, donc ses CLÉS, et renvoie la plus grande dans l'ordre alphabétique : 'bleue' < 'charbonnière' < 'nonnette', d'où 'nonnette', une espèce qui n'a que deux voix. Le code tourne, renvoie une espèce plausible, et se trompe sans aucun message. Si l'on tient à une fonction toute faite, c'est max(compteurs, key=compteurs.get) : la clé de comparaison devient le compteur. Mais la boucle écrite en b) a l'avantage de rendre visible la règle appliquée en cas d'égalité, qui est l'objet de la question suivante.

d) Les cinq premiers voisins donnent charbonnière $2$, bleue $2$, nonnette $1$ : il y a égalité. Avec >, la boucle retient charbonnière au premier tour, puis bleue ne la bat pas, $2>2$ étant faux : la fonction renvoie 'charbonnière'. Avec >=, bleue remplace charbonnière à égalité, et nonnette ne l'égale pas : la fonction renvoie 'bleue'. Le choix n'est pas anodin. Comme la liste est rangée par distance croissante, l'ordre d'insertion est celui de la proximité : avec >, l'égalité est tranchée en faveur de l'espèce dont le représentant est le PLUS PROCHE, ce qui est une règle défendable. Avec >=, elle l'est en faveur de la plus lointaine. Une égalité se prévoit : on la tranche par une règle écrite, ou on l'évite en choisissant $k$, comme le montre l'exercice 5.

def vote(etiquettes):
    compteurs = {}
    for e in etiquettes:
        compteurs[e] = compteurs.get(e, 0) + 1
    gagnante = None
    for e in compteurs:
        if gagnante is None or compteurs[e] > compteurs[gagnante]:
            gagnante = e
    return gagnante

assert vote(voisins) == 'charbonnière'
assert vote(voisins[:5]) == 'charbonnière'   # égalité : la plus proche

a) Carrés des distances à X $(2\,;10)$ : abeille $(3\,;10)$ : $1+0=1$ ; syrphes $(1\,;9)$ et $(1\,;11)$ : $1+1=2$ chacune ; syrphe $(2\,;12)$ : $0+4=4$ ; syrphe $(3\,;8)$ : $1+4=5$ ; abeille $(4\,;12)$ : $4+4=8$ ; syrphe $(2\,;7)$ : $0+9=9$. Les suivants sont des abeilles, $(5\,;11)$ à $10$, $(6\,;10)$ à $16$, puis $(5\,;13)$ à $18$, $(4\,;14)$ et $(6\,;12)$ à $20$. L'égalité entre les deux syrphes de carré $2$ est sans conséquence : elles sont de la même classe et entrent ensemble dans le vote dès $k=3$. Une égalité de distance ne compte que si elle tombe sur la FRONTIÈRE du $k$-ième voisin avec deux classes différentes.

b) $k=1$ : le seul votant est l'abeille atypique, prédiction abeille. $k=3$ : abeille, syrphe, syrphe, prédiction syrphe. $k=5$ : une abeille et quatre syrphes, syrphe. $k=7$ : l'abeille $(4\,;12)$ entre au sixième rang et la syrphe $(2\,;7)$ au septième, soit deux abeilles contre cinq syrphes, syrphe. Sur la figure, X est entouré de syrphes, et la seule abeille proche est un individu qui ne ressemble pas aux autres. Avec $k=1$, cet individu décide seul, et l'algorithme reproduit une particularité de la table au lieu de la tendance qu'elle décrit.

c) Pour $k=2$, les deux votants sont l'abeille à $1$ et une syrphe à $2$ : une voix chacune, égalité, et l'algorithme ne sait pas conclure. Encore faut-il choisir laquelle des deux syrphes à $2$ entre dans le vote, ce qui ajoute une seconde ambiguïté. Avec DEUX classes, un $k$ impair rend l'égalité impossible, puisqu'un nombre impair de voix ne se partage pas en deux moitiés égales. Avec trois classes ou plus, l'imparité ne suffit plus, comme l'exercice 4 l'a montré avec $2$, $2$ et $1$ voix pour $k=5$ : il faut alors une règle de départage écrite.

d) Pour $k=12$, tous les insectes de la table votent, quel que soit X : $7$ abeilles contre $5$ syrphes, prédiction abeille. La distance ne sert plus à rien, l'algorithme répond toujours la classe la plus nombreuse de la table : c'est le défaut inverse, le sous-ajustement, où la prédiction ignore l'élément à classer. Le choix $k=1$ est le SUR-AJUSTÉ : il suit chaque individu de la table, y compris les atypiques et les erreurs d'étiquetage. On retient donc un $k$ impair intermédiaire, ici $3$ ou $5$, assez grand pour qu'un individu isolé ne décide pas seul, assez petit pour que le vote reste local. L'exercice 9 montre comment choisir $k$ sur des données, plutôt qu'au jugé.

a) Distance brute = écart d'autonomie + écart de prix. P1 : $16+10=26$ ; P2 : $14+20=34$ ; P3 : $2+60=62$ ; P4 : $4+700=704$ ; P5 : $2+80=82$ ; P6 : $8+100=108$. Les trois plus proches sont P1, P2 et P3 : deux déconseillés contre un recommandé, prédiction déconseillé. Or P1 et P2 ont une autonomie de $10$ et $12$ heures, moins de la moitié de celle de X, et ce sont eux qui votent parce qu'ils coûtent à peu près le même prix. Le calcul additionne des heures et des dollars : le nombre obtenu n'a pas d'unité, et il n'a pas de sens.

b) Autonomie : de $10$ à $30$ h, étendue $20$. Prix : de $200$ à $1\,000$ dollars, étendue $800$, soit $40$ fois plus. Un écart de $20$ dollars, insignifiant pour un téléphone, pèse autant dans la distance que tout l'écart d'autonomie de la table, de $10$ à $30$ heures. Autrement dit, la distance brute ne regarde presque que le prix, et l'autonomie ne sert qu'à départager des téléphones de même prix. Ce n'est pas un choix, c'est un accident d'unités : exprimer le prix en milliers de dollars ferait au contraire disparaître le prix du calcul. Dès que les attributs n'ont ni la même unité ni la même étendue, les voisins dépendent des unités choisies, ce qui est absurde.

c) La normalisation min-max ramène chaque attribut entre $0$ et $1$ : $0$ pour la plus petite valeur de la table, $1$ pour la plus grande. Autonomie : $a'=\dfrac{a-10}{20}$ ; prix : $p'=\dfrac{p-200}{800}$. Pour X : $a'=\dfrac{16}{20}=0{,}8$ et $p'=\dfrac{100}{800}=0{,}125$. P3 $(28\,;360)$ devient $(0{,}9\,;0{,}2)$, distance $0{,}1+0{,}075=0{,}175$. P5 $(24\,;380)$ devient $(0{,}7\,;0{,}225)$, distance $0{,}1+0{,}1=0{,}2$. Après normalisation, un écart de $0{,}1$ représente un dixième de l'étendue, que ce soit en heures ou en dollars : les deux attributs pèsent enfin le même poids.

d) P1 $(0\,;0{,}1125)$ : $0{,}8+0{,}0125=0{,}8125$. P2 $(0{,}1\,;0{,}15)$ : $0{,}7+0{,}025=0{,}725$. P4 $(1\,;1)$ : $0{,}2+0{,}875=1{,}075$. P6 $(0{,}4\,;0)$ : $0{,}4+0{,}125=0{,}525$. Rangement : P3, P5, P6, P2, P1, P4. Les trois votants sont deux recommandés et un déconseillé : la prédiction devient recommandé. La même table, le même $k$ et la même distance donnent l'avis contraire : on a seulement changé les échelles, donc les votants. On ne recalcule PAS le minimum et le maximum avec X : la transformation est fixée une fois pour toutes sur la table, et chaque nouvel élément la subit telle quelle, sinon deux prédictions successives ne seraient pas faites dans le même repère. Un élément hors de l'étendue donne une coordonnée hors de $[0\,;1]$, ce qui ne pose aucun problème.

a) feuilles[0] est le dictionnaire {'longueur': '12.5', 'largeur': '10.0', 'arbre': 'érable'}. Les guillemets autour de 12.5 ne sont pas une coquetterie d'affichage : un fichier CSV est un fichier TEXTE, et le module csv ne devine aucun type. Toutes les valeurs lues sont des chaînes, de type str, y compris celles qui ressemblent à des nombres. La première ligne du fichier n'apparaît pas dans la liste : DictReader s'en sert pour nommer les clés, ce qui évite l'erreur classique de traiter l'en-tête comme une donnée.

b) '12.5' - 11.0 lève une TypeError : Python refuse de soustraire un flottant à une chaîne. C'est l'erreur heureuse, car elle se voit dès le premier calcul de distance. L'expression min, elle, ne lève rien et renvoie '10.5'. Les chaînes se comparent caractère par caractère, dans l'ordre alphabétique : '10.5' commence par '1', qui précède '8' et '9', donc '10.5' est la plus « petite » chaîne alors que la plus petite longueur est $8{,}5$. De même, un tri de la colonne rangerait '14.0' avant '8.5'. Un algorithme des k plus proches voisins qui trierait des chaînes produirait des voisins faux sans aucun message : c'est l'erreur malheureuse.

c) Dans la boucle : ligne['longueur'] = float(ligne['longueur']), puis la même ligne pour largeur. On ne convertit pas la colonne arbre, qui est une étiquette et doit rester une chaîne. Après conversion, min renvoie $8{,}5$, un flottant, la vraie plus petite longueur. On appelle convertir UNE SEULE FOIS, juste après charger, et non dans la fonction de distance : une conversion placée dans la distance serait refaite à chaque comparaison, c'est-à-dire des milliers de fois par prédiction sur une grande table, pour un résultat toujours identique. Le fichier se nettoie au chargement ; l'algorithme travaille ensuite sur des nombres.

d) On numérote les feuilles F1 à F6 dans l'ordre du fichier. Écarts à $(11\,;7{,}5)$ et carrés : F1 $(1{,}5\,;2{,}5)$, $2{,}25+6{,}25=8{,}5$ ; F2 $(-2\,;-3)$, $4+9=13$ ; F3 $(-0{,}5\,;1)$, $0{,}25+1=1{,}25$ ; F4 $(3\,;-0{,}5)$, $9+0{,}25=9{,}25$ ; F5 $(-2{,}5\,;0)$, $6{,}25$ ; F6 $(0{,}5\,;-2)$, $0{,}25+4=4{,}25$. Les trois plus proches sont F3 érable, F6 chêne et F5 érable : deux voix contre une, prédiction érable. Les deux attributs sont ici dans la même unité et d'étendues voisines, $5{,}5$ et $5{,}5$ cm, donc la normalisation de l'exercice 6 n'est pas indispensable : elle se décide en regardant les étendues, pas par habitude.

def convertir(table):
    for ligne in table:
        ligne['longueur'] = float(ligne['longueur'])
        ligne['largeur'] = float(ligne['largeur'])

feuilles = charger('feuilles.csv')
convertir(feuilles)          # une seule fois, au chargement
assert min([f['longueur'] for f in feuilles]) == 8.5

a) Faux. Quand $k$ atteint le nombre $n$ d'exemples, toute la table vote, et la prédiction est la classe la plus nombreuse de la table, QUEL QUE SOIT l'élément à classer : à l'exercice 5, $k=12$ répond abeille même pour un insecte entouré de syrphes. La distance ne joue plus aucun rôle. Énoncé correct : un $k$ trop petit suit les individus atypiques, un $k$ trop grand efface la notion de voisinage ; on cherche une valeur intermédiaire, et on la choisit en mesurant les erreurs sur des exemples de test, comme à l'exercice 9.

b) Faux. La racine carrée est strictement croissante sur les nombres positifs : si $d_{1}^{2}<d_{2}^{2}$ alors $d_{1}<d_{2}$. Classer par carré de distance donne exactement le même rang à chaque élément, donc les mêmes $k$ voisins et la même prédiction ; aucun voisin ne change. C'est précisément ce qui a permis de travailler sans calculatrice aux exercices 3, 5 et 7. Énoncé correct : supprimer la racine ne change pas les voisins, mais change la VALEUR de la distance, ce qui compte dès qu'on la compare à un seuil fixé.

c) Faux. Pour un exemple de la table, le plus proche voisin est lui-même, à distance $0$, et il porte évidemment sa propre classe : le taux de réussite de $k=1$ sur la table vaut toujours $100\ \%$, même si le choix est mauvais. Mesurer ainsi, c'est corriger une copie en lui donnant son propre corrigé. À l'exercice 9, $k=1$ ne réussit que deux oiseaux test sur quatre. Énoncé correct : la qualité d'un choix de $k$ se mesure sur des éléments de classe connue qui ne sont PAS dans la table.

d) Faux sur les deux moitiés. Les k plus proches voisins n'ont aucune phase d'apprentissage : ils ne construisent aucun résumé de la table, ils la gardent entière en mémoire. Tout le travail se fait au moment de la prédiction : pour une table de $1\,000$ lignes, chaque prédiction calcule $1\,000$ distances puis trie ou sélectionne. Énoncé correct : l'algorithme ne coûte rien avant la première question, et coûte au moins un parcours complet de la table à chaque question. C'est l'objet de l'exercice 10.

e) Faux. Avec $k=4$ et deux classes, les voix peuvent se répartir $2$ contre $2$, et l'algorithme ne sait pas conclure ; à l'exercice 5, $k=2$ donnait déjà une voix chacune. Un nombre impair de voix, en revanche, ne se coupe jamais en deux moitiés égales. Énoncé correct : avec deux classes, un $k$ impair garantit une majorité ; avec trois classes ou plus, aucun $k$ ne la garantit, et il faut écrire une règle de départage, comme à l'exercice 4.

a) T1 $62{,}5$ : le plus proche est le véloce $63$, à $0{,}5$ ; prédiction véloce, FAUX. T2 $59{,}5$ : véloce $60$, à $0{,}5$ ; véloce, juste. T3 $61{,}5$ : fitis $61$, à $0{,}5$ ; fitis, FAUX. T4 $66{,}5$ : fitis $67$, à $0{,}5$ ; fitis, juste. Deux réussites sur quatre, soit $50\ \%$, autant qu'en tirant à pile ou face. La figure montre pourquoi : les deux espèces se CHEVAUCHENT entre $60$ et $63$ mm, avec un véloce à grande aile ($63$) et un fitis à petite aile ($61$). Avec un seul votant, chaque oiseau test proche de la zone de chevauchement est classé d'après l'individu le plus atypique de la table.

b) T1 $62{,}5$ : $63$ véloce à $0{,}5$, puis $61$ et $64$ fitis à $1{,}5$ ; deux fitis contre un véloce, fitis, juste. T2 $59{,}5$ : $60$ véloce à $0{,}5$, $61$ fitis et $58$ véloce à $1{,}5$ ; véloce, juste. T3 $61{,}5$ : $61$ fitis à $0{,}5$, $60$ et $63$ véloces à $1{,}5$ ; véloce, juste. T4 $66{,}5$ : $67$, $65$ et $68$, trois fitis ; fitis, juste. Quatre sur quatre, $100\ \%$. On vérifie à chaque fois que le quatrième voisin est strictement plus loin que le troisième, à $2{,}5$ : sinon le choix des trois votants serait ambigu. Avec trois votants, l'individu atypique est mis en minorité par ses deux voisins suivants.

c) Pour $k=11$, toute la table vote pour chaque oiseau test : $6$ fitis contre $5$ véloces, la prédiction est TOUJOURS fitis. T1 et T4 sont justes, T2 et T3 faux : $50\ \%$. Le taux est le même qu'avec $k=1$, pour la raison opposée : $k=1$ écoute un seul individu, $k=11$ n'écoute plus l'aile de l'oiseau du tout. Ce résultat dépend d'ailleurs uniquement de la composition de la table : il suffirait d'y ajouter deux véloces pour que $k=11$ réponde toujours véloce.

d) Sur les $11$ oiseaux de la table, $k=1$ réussit $11$ fois sur $11$, soit $100\ \%$ : chaque oiseau a pour plus proche voisin lui-même, à distance $0$, qui porte sa propre espèce. Ce nombre ne mesure que la mémoire de l'algorithme, pas sa capacité à classer un oiseau nouveau, qui est la seule chose qu'on lui demande. C'est pourquoi on garde des oiseaux TEST hors de la table. On retient $k=3$, le seul des trois essais qui réussit tous les tests. Prudence toutefois : quatre oiseaux test, c'est $25\ \%$ par oiseau, et un vrai choix de $k$ se ferait sur des dizaines d'oiseaux ; la méthode, elle, est exactement celle-ci.

a) couples.sort() trie la liste sur place, et c'est ce qu'on veut puisque couples est une liste de travail créée pour cette prédiction. couples = couples.sort() remplace la liste par None, et la ligne suivante échoue ; sorted(couples) seul calcule une liste triée et la jette. Les couples sont des tuples, comparés d'abord sur la distance, puis, à distance égale, sur l'étiquette : 'L' avant 'M' avant 'S', un départage alphabétique arbitraire qu'il vaut mieux savoir. Enfin la tranche range(k) suppose k <= len(table), sinon couples[i] lève une IndexError : la précondition s'écrit assert 0 < k <= len(table).

b) Écarts au client $(175\,;72)$ : C2 $(-3\,;-2)$, $9+4=13$ ; C7 $(1\,;-4)$, $1+16=17$ ; C3 $(3\,;3)$, $9+9=18$. Les autres sont bien plus loin : C5 $25+64=89$, C6 $49+100=149$, C1 $100+144=244$, C4 $100+169=269$. Pour $k=3$ : C2 M, C7 M, C3 L, taille conseillée M. Pour $k=5$ : C5 L et C6 S s'ajoutent, et les voix se répartissent M $2$, L $2$, S $1$. C'est une égalité, que la règle de l'exercice 4, avec >, tranche en faveur de M, l'étiquette du plus proche client. Sans règle écrite, le conseil dépendrait d'un détail d'implémentation. Les centimètres et les kilogrammes ont ici des étendues comparables, $20$ et $25$ environ, ce qui rend la normalisation moins urgente qu'à l'exercice 6.

c) Chaque prédiction parcourt TOUTE la table et calcule $40\,000$ distances : c'est le prix de l'absence de phase d'apprentissage, l'algorithme ne résume rien et recommence tout à chaque question. Sur une journée, $500\times 40\,000=20\,000\,000$ distances. Le calcul des distances est LINÉAIRE en $n$ : doubler la table double le travail de chaque prédiction. C'est acceptable ici, quelques dixièmes de seconde par prédiction, mais le coût ne diminue jamais avec l'usage, contrairement à un modèle qu'on aurait calculé une fois pour toutes.

d) Le tri par insertion fait au pire $1+2+\cdots+(n-1)=\dfrac{n(n-1)}{2}$ comparaisons, soit $\dfrac{40\,000\times 39\,999}{2}=799\,980\,000$, près de huit cents millions pour UNE prédiction : le tri coûte alors bien plus que les distances. Or on n'a besoin que des cinq premiers. En gardant une liste triée d'au plus $5$ couples et en y insérant chaque nouveau couple à sa place, par le geste du tri par insertion, chaque client coûte de l'ordre de $k=5$ comparaisons : $40\,000\times 5=200\,000$ au total, environ $4\,000$ fois moins. Un couple plus éloigné que le cinquième de la liste est même écarté en une seule comparaison, ce qui arrive pour presque tous les clients. Trier toute la table pour n'en lire que le début est la dépense inutile type de cet algorithme.

def k_plus_proches(table, cible, k):
    assert 0 < k <= len(table)
    meilleurs = []                 # au plus k couples, triés
    for client in table:
        c = (distance(client, cible), client['vetement'])
        if len(meilleurs) < k or c < meilleurs[-1]:
            meilleurs.append(c)
            i = len(meilleurs) - 1
            while i > 0 and meilleurs[i - 1] > meilleurs[i]:
                meilleurs[i - 1], meilleurs[i] = meilleurs[i], meilleurs[i - 1]
                i = i - 1
            if len(meilleurs) > k:
                meilleurs.pop()
    return [c[1] for c in meilleurs]