Un cap pour ce chapitre
Ce que vous saurez faire
- Calculer et comparer des distances.
- Déterminer une classe par vote des
kvoisins. - Expliquer le rôle de
k, des exemples et de l’échelle des données.
Des exemples étiquetés, puis une prédiction
Chaque exemple connu possède des caractéristiques numériques et une classe. Pour reconnaître deux types de graines, on pourrait utiliser longueur et largeur avec des étiquettes A et B. Un nouvel objet possède les caractéristiques mesurées, mais pas encore d’étiquette. La prédiction consiste à utiliser les k exemples les plus proches puis à choisir leur classe majoritaire.
Le résultat est une estimation fondée sur les données disponibles. Ce n’est pas une démonstration de l’appartenance réelle de l’objet. Si les exemples sont mal étiquetés ou peu représentatifs, une exécution parfaitement correcte de l’algorithme peut tout de même produire une mauvaise prédiction.
Définir ce que signifie proche
Dans un plan, la distance euclidienne entre (x, y) et (a, b) vaut la racine carrée de (x - a)² + (y - b)². Pour comparer des distances non négatives, on peut comparer directement leurs carrés : la racine carrée conserve l’ordre. Cela simplifie les calculs à la main et évite des arrondis inutiles.
Une distance dépend des caractéristiques choisies et de leur échelle. Combiner une taille exprimée en millimètres avec une masse exprimée en kilogrammes peut donner une influence très différente aux deux coordonnées. Il faut réfléchir à la représentation avant de croire que la proximité numérique correspond automatiquement à une ressemblance pertinente.
Comparer les carrés convient seulement parce que les distances sont non négatives et que la racine carrée est croissante sur ce domaine. Ce raccourci ne remplace pas une définition de distance : on calcule toujours les mêmes différences de coordonnées. Avec M(2,1) et P(4,3), on obtient 2²+2²=8, qui est un carré de distance, pas une distance égale à 8.
Sélectionner k voisins et compter leurs votes
On calcule la distance du nouveau point à chaque exemple, on ordonne les exemples selon ces distances et on conserve les k premiers. Chaque voisin vote ensuite pour sa classe. Avec les étiquettes [A, B, A] des trois voisins retenus, la prédiction est A : deux votes contre un.
k doit être compris entre 1 et le nombre d’exemples. Une égalité de distances à la frontière du voisinage nécessite une convention. Notre atelier conserve alors l’ordre des exemples numérotés. Une égalité de votes produit explicitement « indécis ». Choisir k impair évite une égalité de vote entre deux classes, mais ne résout pas tous les problèmes de distances égales.
Séparez l’identité d’un point et sa classe. Plusieurs points différents peuvent avoir l’étiquette A, mais chacun apporte un vote. Trier les étiquettes alphabétiquement avant de choisir les voisins détruirait la règle de proximité. On trie les exemples avec leurs caractéristiques et leur distance, puis on compte les classes des seuls exemples retenus.
Comprendre l’effet de k
Avec k = 1, la prédiction dépend entièrement de l’exemple le plus proche. Une étiquette incorrecte ou un point isolé peut donc avoir un effet fort. Un k plus grand rassemble davantage d’informations, mais peut effacer des groupes locaux distincts. Si l’on utilise tous les exemples, la classe majoritaire globale finit par dominer presque partout.
On peut comparer des choix de k sur des exemples dont la classe est connue et qui ne sont pas utilisés comme voisins de référence. Ce principe de validation permet d’évaluer une méthode. En Première, l’objectif central reste de construire la prédiction, de la dérouler et d’expliquer ses limites, sans transformer un vote en certitude.
Exemple complet avec un changement de k
On classe M(0,0) à partir de P(1,0,B), Q(0,2,A), R(2,1,A), S(3,0,B). Les carrés des distances sont respectivement 1, 4, 5 et 9. L’ordre des voisins est donc P, Q, R, S. Avec un voisin, la classe prédite est B. Avec trois voisins, A l’emporte par deux voix contre une. Avec quatre, il y a deux voix pour chaque classe.
Ce changement ne provient pas d’une erreur de calcul : le voisinage utilisé change. La distance choisit les votants, puis les votes choisissent la classe. Dans la version majoritaire du cours, un point deux fois plus proche n’obtient pas deux voix. Une pondération par distance constituerait un autre algorithme et devrait être annoncée. Avant de conclure, contrôlez donc les distances, la sélection des k points et le décompte, dans cet ordre.
Tester la prédiction et examiner l’échelle
Supposons une caractéristique exprimée en mètres dont les écarts valent 1 ou 2, et une autre exprimée en millimètres dont les écarts valent 100 ou 200. Dans la somme des carrés, la seconde peut dominer uniquement à cause de son unité. Convertir une grandeur change ses nombres, pas le phénomène réel. Le choix d’échelle fait donc partie de la représentation du problème.
Pour évaluer une méthode, réservez des exemples connus qui ne servent pas de voisins de référence. Calculez les prédictions puis comparez aux étiquettes attendues. Quatre réussites sur cinq décrivent ces cinq essais ; elles ne certifient pas toutes les futures graines. Examinez les erreurs : voisin isolé, groupe peu représenté, étiquetage incorrect ou unité inadéquate. L’algorithme peut être correctement exécuté alors que les données ne représentent pas assez bien les objets à classer.
À vous de faire varier les choses
Déplacez l’inconnu dans le nuage
Choisissez les coordonnées du point et k. Le tableau indique les distances carrées ; les voisins retenus sont reliés au point M.
Lire le résultat de l’expérience initiale
Prédiction : A
Les distances égales sont départagées par le numéro du point. Une égalité de votes reste indécise.
| Point | Classe | Distance carrée | Retenu | Écart x au carré | Écart y au carré |
|---|---|---|---|---|---|
| 2 | A | 1 | oui | 1 | 0 |
| 6 | B | 2 | oui | 1 | 1 |
| 1 | A | 5 | oui | 4 | 1 |
| 4 | B | 5 | non | 4 | 1 |
| 3 | A | 8 | non | 4 | 4 |
| 5 | B | 8 | non | 4 | 4 |
La prédiction change lorsque le point se déplace ou que le voisinage retenu s’élargit.
De la compréhension à l’autonomie
À vous de résoudre
Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.
Comparer sans racine carrée
Le point à classer est M(2, 1). Comparez ses distances à A(1, 1), B(4, 1) et C(2, 4).
Indice 1
Calculez les carrés des différences de coordonnées.
Indice 2
Les carrés des distances suffisent au classement.
Comprendre la correction
Les carrés des distances valent 1 pour A, 4 pour B et 9 pour C. L’ordre du plus proche au plus éloigné est donc A, B, C. Les distances elles-mêmes valent 1, 2 et 3 dans cet exemple ; calculer leurs racines n’était pas nécessaire pour les ordonner.
Le voisin unique n’a pas toujours le dernier mot
Les cinq exemples les plus proches portent, dans l’ordre, les étiquettes B, A, A, B, A. Comparez les prédictions pour k = 1, 3 et 5.
Indice 1
Ne prenez que les k premiers à chaque fois.
Indice 2
Comptez les étiquettes, pas les distances elles-mêmes.
Comprendre la correction
Pour k = 1, B est choisi. Pour k = 3, A gagne par deux voix contre une. Pour k = 5, A gagne par trois voix contre deux. La classe du point le plus proche ne suffit donc pas à prévoir le résultat lorsque k dépasse 1.
Des données qui se votent elles-mêmes
Pour mesurer la qualité de k = 1, on classe chaque exemple en l’incluant dans la liste de ses propres voisins. Pourquoi cette évaluation est-elle trompeuse ?
Indice 1
Un point est à distance zéro de lui-même.
Indice 2
L’objectif est de prédire une étiquette inconnue.
Comprendre la correction
Chaque exemple peut se retrouver lui-même comme voisin le plus proche et récupérer sa propre étiquette. Cette réussite ne mesure pas la capacité à classer de nouveaux objets. Il faut séparer les exemples évalués des voisins utilisés, ou au minimum exclure l’exemple courant selon un protocole précisé.
Une égalité à expliquer
Les quatre voisins retenus sont A, B, A, B. Un programme annonce A parce que cette classe apparaît la première. Est-ce une majorité ?
Indice 1
Comptez les deux classes.
Indice 2
Une convention de départage n’est pas un vote majoritaire.
Comprendre la correction
Il y a deux votes pour chaque classe : aucune majorité. Choisir A peut constituer une convention explicite de départage, mais il faut l’annoncer comme telle. Notre atelier conserve le résultat indécis pour montrer que les données et k ne suffisent pas ici à choisir une classe majoritaire.
Du calcul au vote
Classez M(0,0) avec P(1,0,B), Q(0,2,A), R(2,1,A), S(3,0,B). Donnez les carrés des distances dans cet ordre, puis la classe pour k=1, k=3 et k=4 avec résultat indécis en cas d’égalité.
Indice 1
Calculez la somme des carrés des coordonnées de chaque point.
Indice 2
Après le classement, chaque voisin retenu compte pour une voix.
Comprendre la correction
Les carrés sont 1,4,5,9. L’ordre annoncé des points est déjà celui des distances. Pour k=1, B gagne ; pour k=3, A gagne 2 contre 1 ; pour k=4, le résultat est indécis. Le dernier vote ajouté modifie la décision sans changer aucune distance.
Départager des distances égales
Le point M est à distance carrée 1 de P1(A), P2(B) et P3(B), et à distance carrée 4 de P4(A). Pour k=2, la règle retient les identifiants les plus petits en cas d’égalité. Donnez les voisins et la prédiction. Comparez à k=3.
Indice 1
L’égalité se traite au moment de sélectionner les voisins.
Indice 2
Une autre égalité peut ensuite apparaître dans le vote.
Comprendre la correction
Pour k=2, on retient P1 et P2, donc un vote A et un B : indécis. Pour k=3, P1, P2 et P3 donnent B avec deux voix contre une. Le départage des distances a rendu la sélection déterministe, mais n’a pas empêché l’égalité des votes dans le premier cas.
Une évaluation indépendante
Un modèle prédit A,B,A,A,B pour cinq objets de test dont les vraies classes sont A,A,A,B,B. Calculez le nombre de bonnes prédictions et le taux de réussite. Expliquez pourquoi il faut exclure ces objets de la base des voisins lors du test.
Indice 1
Comparez les étiquettes position par position.
Indice 2
Avec k=1, un objet pourrait se reconnaître lui-même à distance nulle.
Comprendre la correction
Les objets 1,3,5 sont correctement classés : trois sur cinq, soit 60 %. Les objets testés doivent rester indépendants des voisins de référence pour éviter la réussite artificielle obtenue par auto-reconnaissance. Ce résultat mesure seulement la performance sur l’échantillon annoncé, pas une certitude sur tous les futurs objets.
Les erreurs qui méritent un détour
- Voter avec tous les exemples après avoir choisi
k. - Seuls les
kvoisins sélectionnés participent au vote. Les autres exemples servent à définir le classement des distances. - Confondre prédiction et certitude.
- La règle dépend des exemples, de la distance et de
k. Une évaluation sur d’autres données reste nécessaire.
La fiche à garder
L’essentiel à retenir
- Calculer les distances, sélectionner les voisins, puis compter les votes.
ket l’échelle des caractéristiques influencent la prédiction.- Les égalités exigent une convention explicite.
Cette notion au bac
Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.
Le prochain pas
Retrouver le catalogue de Première
Ce chapitre s’appuie sur le programme officiel de Première (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.