Aller au contenu

Exercices#

Les k plus proches voisins

Mode d’emploi

  • Niveau : ★ échauffement, ★★ classique (niveau bac), ★★★ défi ; les coups de pouce et les corrigés se déplient sous chaque exercice.

  • ▶ À programmer et tester en Python. Rappel : pour comparer des distances, on peut garder la somme des carrés (sans racine).

  • Usage de l’IA, indiqué sur chaque exercice : aucune ; en appui (déboguer, reformuler, vérifier ; la réponse finale est écrite et comprise par vous) ; l’exercice s’appuie sur une réponse d’IA. Voir la charte d’usage de l’IA.

Classification et distance#

★ Exercice 1 — Le vocabulaire #

Répondre par une phrase.

  1. Qu’est-ce qu’une classification supervisée ?

  2. Dans le \(k\)-NN, que représentent les descripteurs d’un individu ? son étiquette ?

  3. Résumer la méthode des \(k\) plus proches voisins en une phrase.0

    Coup de pouce

    « Supervisée » : la machine apprend à partir d’exemples dont on connaît déjà la bonne réponse. Pour c), trois verbes suffisent : mesurer, garder, voter.

Corrigé

Remarque

On donne une version simple ; d’autres écritures sont possibles.

a) Apprendre à prédire une étiquette à partir d’exemples déjà étiquetés. b) Les descripteurs sont les mesures (les coordonnées) de l’individu ; l’étiquette est sa classe. c) On calcule la distance de l’individu à tous les exemples, on garde les \(k\) plus proches, on prend leur classe majoritaire.

★ Exercice 2 — Calculer des distances #

• essentiel

  1. Distance euclidienne entre \(A=(3 ; 4)\) et \(B=(0 ; 0)\).

  2. Distance entre \(A=(1 ; 2 ; 2)\) et \(B=(4 ; 2 ; 6)\) (trois descripteurs).

  3. Entre \(A=(4.7 ; 1.4)\) et \(B=(4.5 ; 1.5)\), donner la distance au carré, puis la distance.0

    Coup de pouce

    Pour chaque descripteur, calculer l’écart, puis son carré ; additionner ces carrés : c’est la distance au carré. La distance est sa racine carrée.

Corrigé

On élève au carré l’écart sur chaque descripteur, on additionne (c’est \(d^2\)), puis on prend la racine. a) \(\sqrt{3^2+4^2}=\sqrt{25}=\textbf{5}\). b) \(\sqrt{3^2+0^2+4^2}=\sqrt{25}=\textbf{5}\). c) \(d^2=0.2^2+0.1^2=0.04+0.01=\textbf{0.05}\) ; \(d=\sqrt{0.05}\approx\textbf{0.22}\).

▷ Erreur fréquente. additionner les écarts avant de les élever au carré : \((3 + 4)^2 = 49\), et non \(3^2 + 4^2 = 25\).

★ Exercice 3 — Qui gagne le vote ? #

• essentiel

On a déjà calculé la distance au carré entre un fruit inconnu \(x\) et six fruits étiquetés.

fruit 1 2 3 4 5 6
\(d^2\) à \(x\) 2 9 1 5 3 12
étiquette pomme poire poire pomme pomme poire

  1. Ranger les six fruits du plus proche au plus lointain de \(x\).

  2. Quelle étiquette prédit le \(1\)-NN ? le \(3\)-NN ? le \(5\)-NN ?0

    Coup de pouce

    Il suffit de comparer les \(d^2\) : ranger les fruits par \(d^2\) croissant, puis, pour chaque valeur de \(k\), compter les étiquettes parmi les \(k\) premiers seulement.

Corrigé

a) Fruit 3 (\(d^2=1\), poire), 1 (2, pomme), 5 (3, pomme), 4 (5, pomme), 2 (9, poire), 6 (12, poire). b) \(1\)-NN : poire. \(3\)-NN : poire, pomme, pomme \(\to\) pomme. \(5\)-NN : 3 pommes contre 2 poires \(\to\) pomme. La prédiction peut changer avec \(k\).

▷ Erreur fréquente. voter avec les \(k\) premiers fruits du tableau (fruits 1, 2, 3 pour \(k = 3\)) : il faut d’abord ranger par distance, puis garder les \(k\) plus proches.

★★ Exercice 4 — Dérouler le \(k\)-NN à la main (iris) #

• essentiel

On dispose des exemples suivants (longueur ; largeur de pétale \(\to\) espèce) :

long. larg. espèce
1.4 0.2 setosa
1.5 0.2 setosa
4.5 1.5 versicolor
4.9 1.5 versicolor
5.5 2.1 virginica
5.8 2.2 virginica

On veut classer la fleur \(x = (4.7 ; 1.4)\).

  1. Calculer la distance au carré de \(x\) à chacun des 6 exemples.

  2. Quelle espèce prédit le \(1\)-NN (le plus proche voisin) ?

  3. Quelle espèce prédit le \(3\)-NN (vote des 3 plus proches) ?

    Coup de pouce

    Pour chaque exemple : carré de l’écart des longueurs, plus carré de l’écart des largeurs. Ranger ensuite les six résultats dans l’ordre croissant avant de voter.

Corrigé

a) Distances au carré de \(x=(4.7;1.4)\) :

exemple espèce \(d^2\)
(1.4;0.2) setosa 12.33
(1.5;0.2) setosa 11.68
(4.5;1.5) versicolor 0.05
(4.9;1.5) versicolor 0.05
(5.5;2.1) virginica 1.13
(5.8;2.2) virginica 1.85

b) \(1\)-NN : le plus proche est une versicolor \(\to\) versicolor. c) \(3\)-NN : deux versicolor (0.05 ; 0.05) et une virginica (1.13) \(\to\) versicolor.

▷ Erreur fréquente. calculer les racines carrées pour comparer : c’est inutile, les distances au carré sont rangées dans le même ordre que les distances.

Programmer le \(k\)-NN#

★★ Exercice 5 — ▶ Les briques de base #

Écrire (ou compléter) les fonctions Python :

  1. distance2(a, b) : la somme des carrés des écarts entre deux listes de même longueur, c’est-à-dire la distance au carré \(d^2\) du cours (sans racine : pour comparer des distances, elle suffit) ;

  2. vote(etiquettes) : l’étiquette la plus fréquente d’une liste (avec un dictionnaire d’occurrences).

    Coup de pouce

    distance2 : un accumulateur et une boucle sur les indices. vote : compter d’abord chaque étiquette dans un dictionnaire, puis chercher l’étiquette de compte maximal (invariant du champion).

Corrigé

distance2 : un accumulateur et une boucle sur les indices des descripteurs. vote : un dictionnaire d’occurrences, puis une recherche du champion (l’étiquette de plus grand compte).

def distance2(a, b):
    s = 0
    for i in range(len(a)):
        s = s + (a[i] - b[i]) ** 2
    return s            # distance au carre (racine inutile pour comparer)

def vote(etiquettes):
    compte = {}
    for e in etiquettes:
        if e in compte:
            compte[e] += 1
        else:
            compte[e] = 1
    meilleure = None
    for e in compte:
        if meilleure is None or compte[e] > compte[meilleure]:
            meilleure = e
    return meilleure

★ Exercice 6 — ▶ Le plus proche voisin, à trous #

La fonction suivante renvoie l’étiquette de l’exemple le plus proche de x (c’est le \(1\)-NN). Elle utilise la fonction distance2 de l’exercice précédent.

def plus_proche(exemples, x):
    dists = []
    for descripteurs, etiquette in exemples:
        dists.append((.................... , etiquette))
    dists.sort(key=lambda couple: ..........)
    return dists[.....][1]

  1. Compléter les trois trous.

  2. Que contient la liste dists après le tri ? Que désigne dists[0][1] ?

  3. Tester avec les six iris de l’exercice 4 et x = [4.7, 1.4] : on doit obtenir ’versicolor’.0

    Coup de pouce

    Chaque couple rangé dans dists est (distance, etiquette). Sur quel élément du couple faut-il trier ? Après le tri, où se trouve le plus proche ?

Corrigé

a)

def plus_proche(exemples, x):
    dists = []
    for descripteurs, etiquette in exemples:
        dists.append((distance2(x, descripteurs), etiquette))
    dists.sort(key=lambda couple: couple[0])
    return dists[0][1]

b) Après le tri, dists contient les couples (distance au carré, etiquette) rangés par distance croissante. dists[0] est le couple le plus proche ; dists[0][1] est donc l’étiquette du plus proche voisin. c) plus_proche(iris, [4.7, 1.4]) renvoie ’versicolor’ (distance au carré \(0.05\)).

▷ Erreur fréquente. renvoyer dists[0][0] : c’est la distance du plus proche voisin, pas son étiquette, qui est le second élément du couple.

★★ Exercice 7 — ▶ Classer #

On représente les exemples par une liste de couples (descripteurs, etiquette). Écrire :

  1. k_plus_proches(exemples, x, k) : la liste des étiquettes des \(k\) exemples les plus proches de x (trier selon distance2) ;

  2. classer(exemples, x, k) qui renvoie l’étiquette prédite pour x.

Tester sur la table des iris de l’exercice 4 avec x = [4.7, 1.4] et \(k=3\).

Coup de pouce

Ranger dans une liste des couples (distance2(x, descripteurs), etiquette), puis trier cette liste en disant à sort sur quoi comparer : avec key=lambda couple: couple[0], on trie selon le premier élément de chaque couple, la distance.

Coup de pouce 2 (début de solution)

def k_plus_proches(exemples, x, k):
dists = []
for descripteurs, etiquette in exemples:
…

Corrigé

On range les couples (distance, etiquette), on les trie par distance, on garde les étiquettes des \(k\) premiers, puis on vote avec la fonction vote.

def k_plus_proches(exemples, x, k):
    dists = []
    for descripteurs, classe in exemples:
        dists.append((distance2(x, descripteurs), classe))
    dists.sort(key=lambda couple: couple[0])
    return [classe for (d, classe) in dists[:k]]

def classer(exemples, x, k):
    return vote(k_plus_proches(exemples, x, k))

Sur les iris avec x=[4.7,1.4] et \(k=3\) : ’versicolor’.

Autre méthode : la liste dists se construit aussi par compréhension, en une ligne : dists = [(distance2(x, d), classe) for (d, classe) in exemples].

Choisir \(k\), comprendre les limites#

★★ Exercice 8 — L’effet de \(k\) #

• essentiel

  1. Pourquoi \(k=1\) est-il très sensible à un exemple aberrant (mal étiqueté) ?

  2. Que prédit le \(k\)-NN si l’on prend \(k\) égal au nombre total d’exemples ? Le résultat dépend-il encore de \(x\) ?

  3. Pour un problème à deux classes, pourquoi préfère-t-on un \(k\) impair ?

    Coup de pouce

    Pour b), imaginer que tous les exemples votent : la position de x change-t-elle encore le résultat ? Pour c), essayer un vote à 4 voisins entre deux classes.

Corrigé

a) Avec \(k=1\), la prédiction copie le seul voisin le plus proche : si c’est un exemple mal étiqueté, la réponse est fausse. b) Si \(k=\) nombre total d’exemples, tous votent : on renvoie toujours la classe globalement majoritaire, sans plus dépendre de \(x\). c) Un \(k\) impair évite les égalités de vote entre les deux classes.

▷ Erreur fréquente. croire qu’un \(k\) impair évite toute égalité : avec trois classes ou plus, un vote à 3 voisins peut donner une voix à chacune.

★★★ Exercice 9 — ▶ Départager une égalité #

≈ 30 min

Le vote peut aboutir à une égalité. Une règle courante : en cas d’égalité, on retire le voisin le plus lointain et on revote, jusqu’à ce qu’une seule classe arrive en tête.

  1. Avec les six iris de l’exercice 4 et \(x = (4.7 ; 1.4)\), pour quelles valeurs de \(k\) le vote est-il à égalité ?

  2. Écrire vote_departage(voisins), où voisins est la liste des étiquettes des voisins, rangées du plus proche au plus lointain, qui applique cette règle.

  3. Tester : vote_departage(["A", "B", "B", "A", "C"]) doit renvoyer "B". Expliquer pourquoi ce n’est pas l’étiquette du voisin le plus proche.

Coup de pouce

Écrire d’abord une fonction qui compte les voix dans un dictionnaire. Ensuite, tant que plusieurs classes ont le nombre maximal de voix, recommencer sur la liste privée de son dernier élément.

Coup de pouce 2 (début de solution)

def vote_departage(voisins):
n = len(voisins)
while n > 0:
compte = compter(voisins[:n])
…

Corrigé

a) Voisins rangés : versicolor, versicolor, virginica, virginica, setosa, setosa. Égalité pour \(k = 4\) (2 contre 2), \(k = 5\) (2, 2 et 1) et \(k = 6\) (2, 2 et 2). b)

def compter(voisins):
    compte = {}
    for c in voisins:
        if c in compte:
            compte[c] += 1
        else:
            compte[c] = 1
    return compte

def vote_departage(voisins):
    n = len(voisins)
    while n > 0:
        compte = compter(voisins[:n])
        maxi = 0
        for c in compte:
            if compte[c] > maxi:
                maxi = compte[c]
        gagnants = [c for c in compte if compte[c] == maxi]
        if len(gagnants) == 1:
            return gagnants[0]
        n = n - 1          # egalite : on retire le voisin le plus lointain

La boucle s’arrête : avec un seul voisin, il ne peut pas y avoir d’égalité. c) Avec 5 voisins : A 2, B 2, C 1 (égalité) ; avec 4 : A 2, B 2 (égalité) ; avec 3 : A 1, B 2 \(\to\) "B". Le plus proche voisin est un A, mais une fois les voisins lointains retirés, B reste majoritaire : la règle départage par le vote, pas par le premier voisin. Sur les iris, avec \(k = 4\), 5 ou 6, on obtient ’versicolor’.

★★ Exercice 10 — Le piège de l’échelle #

On classe des personnes par leur âge (de 0 à 100) et leur revenu mensuel (de 0 à 5000). On utilise la distance euclidienne brute.

  1. Entre deux personnes, quel descripteur domine la distance ? Pourquoi ?

  2. Que faut-il faire avant d’appliquer le \(k\)-NN pour que les deux descripteurs comptent équitablement ?

    Coup de pouce

    Comparer un écart typique de 10 ans et un écart typique de 200 € : que valent leurs carrés ?

Corrigé

a) Le revenu domine : un écart de 200 € pèse \(200^2=40\,000\), alors qu’un écart de 10 ans ne pèse que \(10^2=100\). L’âge devient négligeable. b) Il faut normaliser : ramener chaque descripteur à la même échelle (par exemple entre 0 et 1) pour qu’ils comptent équitablement.

★ Exercice 11 — Le coût #

Une base contient \(10\,000\) exemples, chacun décrit par \(196\) pixels.

  1. Pour classer une image, à combien d’exemples doit-on calculer la distance ?

  2. Pourquoi dit-on que le \(k\)-NN est un algorithme « paresseux » ? Quel est le coût par prédiction (linéaire, quadratique…) en le nombre d’exemples ?0

    Coup de pouce

    Relire l’algorithme : avant de pouvoir voter, de quels exemples faut-il connaître la distance ? Le \(k\)-NN prépare-t-il quelque chose avant qu’on lui demande de classer ?

Corrigé

a) À 10 000 exemples (tous). b) « Paresseux » car il ne construit aucun modèle au préalable : il garde tout et compare à la demande. Coût linéaire en le nombre d’exemples, à chaque prédiction.

Applications#

★★ Exercice 12 — Recommander un poste (football) #

On décrit des joueurs par leur taille (cm) et leur poids (kg), avec leur poste :

taille poids poste
180 75 milieu
178 72 milieu
192 88 défenseur
195 90 défenseur
170 65 attaquant
173 68 attaquant

Un nouveau joueur mesure \(176\) cm pour \(70\) kg.

  1. Calculer la distance au carré aux 6 joueurs.

  2. Quel poste recommande le \(1\)-NN ? le \(3\)-NN ?

  3. Ici taille et poids ont des ordres de grandeur proches : faut-il normaliser ? (Contraster avec l’exercice « Le piège de l’échelle » : âge et revenu.)

    Coup de pouce

    Même méthode que pour les iris : un tableau des six distances au carré, rangées dans l’ordre croissant.

Corrigé

a) Distances au carré de \((176;70)\) :

joueur poste \(d^2\)
(180;75) milieu 41
(178;72) milieu 8
(192;88) défenseur 580
(195;90) défenseur 761
(170;65) attaquant 61
(173;68) attaquant 13

b) \(1\)-NN : le plus proche (8) est un milieu. \(3\)-NN : les trois plus proches sont 8 (milieu), 13 (attaquant), 41 (milieu) \(\to\) 2 milieux contre 1 \(\to\) milieu. c) Ici taille (\(\sim\)170–195) et poids (\(\sim\)65–90) sont du même ordre : la normalisation n’est pas indispensable. Au contraire, âge (0–100) et revenu (0–5000) diffèrent d’un facteur \(\sim\)50, d’où l’obligation de normaliser dans l’exercice « Le piège de l’échelle ».

★★ Exercice 13 — Reconnaître une image \(3\times3\) (sans machine) #

Une image \(3\times3\) est une liste de 9 pixels (0 blanc, 1 encre), lus ligne par ligne. On a deux modèles étiquetés : $\(T=\begin{smallmatrix}1&1&1\\0&1&0\\0&1&0\end{smallmatrix}\quad(\text{« T »}) \qquad\qquad L=\begin{smallmatrix}1&0&0\\1&0&0\\1&1&1\end{smallmatrix}\quad(\text{« L »})\)$ On reçoit l’image inconnue \; \(N=\begin{smallmatrix}1&1&1\\0&1&0\\0&1&1\end{smallmatrix}\).

  1. Écrire \(T\), \(L\) et \(N\) comme des listes de 9 nombres.

  2. Avec des pixels 0/1, la distance au carré compte le nombre de pixels différents. Calculer \(d(N,T)\) et \(d(N,L)\).

  3. Que prédit le \(1\)-NN ? Cela vous semble-t-il correct visuellement ?

    Coup de pouce

    Comparer les deux listes case par case et compter les cases où elles diffèrent.

Corrigé

a) \(T=[1,1,1,0,1,0,0,1,0]\), \(L=[1,0,0,1,0,0,1,1,1]\), \(N=[1,1,1,0,1,0,0,1,1]\). b) \(N\) et \(T\) ne diffèrent que sur le dernier pixel \(\to d^2(N,T)=\textbf{1}\). \(N\) et \(L\) diffèrent sur 5 pixels \(\to d^2(N,L)=\textbf{5}\). c) Le \(1\)-NN prédit T (le plus proche). C’est cohérent : \(N\) est un « T » avec un pixel d’encre en plus.

Mini-problème de synthèse#

★★★ Exercice 14 — Évaluer la qualité #

≈ 20 min

On dispose d’exemples d’entraînement (étiquetés) et d’exemples de test (étiquetés eux aussi, mais on cache l’étiquette pour évaluer).

  1. ▶ Écrire taux_reussite(train, test, k) qui renvoie la proportion d’exemples de test correctement classés par le \(k\)-NN entraîné sur train.

  2. Pourquoi mesure-t-on la qualité sur des exemples de test et non sur ceux d’entraînement ?

  3. On teste \(k = 1, 3, 5, 7\) et on garde le meilleur taux. Comment s’appelle cette démarche de choix de \(k\) ?

    Coup de pouce

    Pour a), parcourir les couples de test, prédire l’étiquette de chacun avec classer(train, …, k), compter les bonnes réponses, puis diviser par le nombre d’exemples de test.

    Coup de pouce 2 (début de solution)

    def taux_reussite(train, test, k):
    bons = 0
    for descripteurs, etiquette in test:
    …

Corrigé

a)

def taux_reussite(train, test, k):
    bons = 0
    for descripteurs, vraie in test:
        if classer(train, descripteurs, k) == vraie:
            bons += 1
    return bons / len(test)

b) Sur les exemples d’entraînement, l’évaluation est trompeuse (avec \(k=1\), chaque exemple est son propre voisin \(\to\) 100 %). Seul un jeu de test (jamais vu) mesure la capacité à généraliser. c) Tester plusieurs \(k\) et garder le meilleur, c’est le réglage (ou choix) de \(k\).

★★ Exercice 15 — Un \(k\)-NN selon un assistant d’IA #

Un élève demande à un assistant d’IA : « Écris en Python une fonction classer(exemples, x, k) des \(k\) plus proches voisins, où exemples est une liste de couples (descripteurs, classe). » Voici la réponse obtenue (distance est la fonction du cours).

def classer(exemples, x, k):
    dists = []
    for descripteurs, classe in exemples:
        dists.append((classe, distance(x, descripteurs)))
    dists.sort()                  # du plus proche au plus lointain
    compte = {}
    for classe, d in dists[:k]:   # les k voisins
        if classe in compte:
            compte[classe] += 1
        else:
            compte[classe] = 1
    meilleure = None
    for c in compte:
        if meilleure is None or compte[c] > compte[meilleure]:
            meilleure = c
    return meilleure

« On calcule la distance de x à chaque exemple, on trie, on garde les \(k\) premiers et on renvoie leur classe majoritaire. »

  1. La réponse est-elle correcte ? ▶ Vérifier sur les six iris du cours avec \(x = (4.7\,;\,1.4)\) et \(k = 3\) (le cours donne versicolor).

  2. Localiser et corriger l’erreur.

  3. Quelle vérification simple, faite avant de faire confiance à la réponse, aurait suffi à détecter l’erreur ?

    Coup de pouce

    Dérouler le code sur les iris en écrivant le contenu de dists avant et après le tri.

Corrigé

a) Non. Sur les six iris du cours, classer(iris, [4.7, 1.4], 3) renvoie ’setosa’ (et de même avec \(k = 1\)), alors que les exemples les plus proches de \(x\) sont des versicolor (\(d^2 = 0.05\)). b) L’erreur est l’ordre dans les couples : (classe, distance). Le tri dists.sort() d’une liste de couples se fait sur le premier élément, donc ici par ordre alphabétique des classes (setosa avant versicolor), et non par distance croissante : les « \(k\) premiers » sont les \(k\) premiers dans l’alphabet. On met la distance en premier (ou on trie avec une clé, comme dans le cours) :

def classer(exemples, x, k):
    dists = []
    for descripteurs, classe in exemples:
        dists.append((distance(x, descripteurs), classe))
    dists.sort()                  # tri par distance croissante
    compte = {}
    for d, classe in dists[:k]:
        if classe in compte:
            compte[classe] += 1
        else:
            compte[classe] = 1
    meilleure = None
    for c in compte:
        if meilleure is None or compte[c] > compte[meilleure]:
            meilleure = c
    return meilleure

Avec cette correction, l’appel renvoie ’versicolor’. c) Afficher dists après le tri (les distances ne sont pas dans l’ordre croissant, cela saute aux yeux), ou tester sur l’exemple du cours dont on connaît la réponse.

Entraînement#

Exercices courts pour s’entraîner aux gestes de base, chacun avec plusieurs données. Ils font tous partie du parcours essentiel.

★ Exercice 16 — Distances au carré #

• essentiel

Calculer la distance au carré \(d^2\) entre \(A\) et \(B\), puis la distance \(d\) (valeur approchée si besoin) : a) \(A = (2 ; 5)\), \(B = (6 ; 2)\) ; b) \(A = (0 ; 3)\), \(B = (2 ; 0)\) ; c) \(A = (1 ; 2 ; 3)\), \(B = (3 ; 1 ; 0)\) ; d) \(A = (1.5 ; 0.4)\), \(B = (1.2 ; 0.2)\).

Coup de pouce

Un écart par descripteur, que l’on élève au carré ; on additionne. L’ordre ne compte pas : \((2 - 6)^2 = (6 - 2)^2\).

Corrigé

a) \(4^2 + 3^2 = 25\), \(d = 5\). b) \(2^2 + 3^2 = 13\), \(d = \sqrt{13} \approx 3{,}6\). c) \(2^2 + 1^2 + 3^2 = 14\), \(d = \sqrt{14} \approx 3{,}7\). d) \(0{,}3^2 + 0{,}2^2 = 0{,}09 + 0{,}04 = 0{,}13\), \(d \approx 0{,}36\).

★ Exercice 17 — Le vote des \(k\) plus proches voisins #

• essentiel

On donne la distance au carré entre un individu inconnu \(x\) et des exemples étiquetés. Pour chaque série, donner la prédiction du \(k\)-NN pour \(k = 1\), \(k = 3\) et \(k = 5\).

  1. \(d^2\) : 4 (rouge), 1 (bleu), 9 (rouge), 2 (rouge), 6 (bleu) ;

  2. \(d^2\) : 3 (chat), 7 (chien), 1 (chien), 5 (chat), 2 (chat), 8 (chien). Que se passe-t-il pour \(k = 6\) ?

Coup de pouce

Toujours commencer par ranger les exemples du plus proche au plus lointain. Le vote ne porte que sur les \(k\) premiers de ce classement.

Corrigé

a) Classement : 1 (bleu), 2 (rouge), 4 (rouge), 6 (bleu), 9 (rouge). \(k = 1\) : bleu ; \(k = 3\) : 2 rouges contre 1 bleu, rouge ; \(k = 5\) : 3 rouges contre 2 bleus, rouge. b) Classement : 1 (chien), 2 (chat), 3 (chat), 5 (chat), 7 (chien), 8 (chien). \(k = 1\) : chien ; \(k = 3\) : chat ; \(k = 5\) : 3 chats contre 2 chiens, chat ; \(k = 6\) : 3 contre 3, égalité : le vote ne permet pas de conclure sans règle pour départager (voir l’exercice « Départager une égalité »).

▷ Erreur fréquente. garder pour tout \(k\) la prédiction du plus proche voisin : en a) comme en b), la prédiction change entre \(k = 1\) et \(k = 3\).