Apprentissage automatique : k plus proches voisins et k-moyennes, cours et exercices corrigés de prépa

• MP
• PC
• PSI
• PT
• TSI 2
• TPC 2
• Offert à l'essai

Apprentissage supervisé et non supervisé, données d'apprentissage et de test, distance, algorithme des k plus proches voisins et vote majoritaire, matrice de confusion, choix de k, algorithme des k-moyennes, centres, partition, inertie, initialisation et arrêt, complexités.

• 17méthodes
• 36exercices corrigés
• 6problèmes
• 18pièges
• 45figures

Les nombres sont ceux du chapitre complet ; chaque filière voit la partie qui correspond à son programme.

L'apprentissage supervisé prédit la classe d'une donnée nouvelle à partir de données déjà étiquetées ; l'apprentissage non supervisé regroupe des données sans étiquette. Le chapitre traite les deux algorithmes du programme d'informatique de deuxième année, en MP, PSI et TSI au Maroc et en MP, PC, PSI, PT, TSI et TPC en France. Il écrit en Python l'algorithme des k plus proches voisins avec distance euclidienne : calcul des distances, sélection des k plus petites sans trier, vote par une liste de compteurs, en $O(nd + kn + c)$ par prédiction. Il montre pourquoi normaliser les attributs, construit et lit la matrice de confusion et choisit k sur des données de test. Il écrit ensuite l'algorithme des k-moyennes : affectation au centre le plus proche, recalcul des centres, arrêt, groupe vide, inertie, et observe la convergence vers un minimum local. Les problèmes reprennent des sujets d'informatique du CNC 2024, 2025 et 2026 (pluie du lendemain, code postal, fleurs d'iris, segmentation d'une image) et du CCINP 2026 (spectres de galaxies et d'étoiles).

Ce que tu sauras faire

Au coin des pesées de la coopérative, deux trieurs ne classent pas les dattes de la même façon. On voudrait qu'une machine propose la variété d'une datte d'après ses mesures, en la comparant aux dattes déjà classées par le connaisseur. Puis, pour les lots du jour, qui n'ont pas d'étiquette, on voudrait former d'elle-même des calibres. Ce chapitre présente les deux algorithmes du programme qui répondent à ces deux questions : les k plus proches voisins et les k-moyennes.

• distinguer apprentissage supervisé et non supervisé, classification et segmentation ;
• représenter des données par des listes d'attributs et des classes numérotées ;
• écrire une distance et normaliser des attributs quand l'énoncé le demande ;
• dérouler à la main et écrire l'algorithme des k plus proches voisins ;
• construire et lire une matrice de confusion, et s'en servir pour choisir k ;
• dérouler à la main et écrire l'algorithme des k-moyennes, calculer une inertie ;
• observer la convergence vers un minimum local ;
• justifier les complexités.

def plus_proches(D, k):
    n = len(D)
    pris = [False] * n
    vois = []
    for t in range(k):
        m = -1
        for i in range(n):
            if not pris[i] and (m == -1 or D[i] < D[m]):
                m = i
        pris[m] = True
        vois.append(m)
    return vois

def vote(Y, vois, c):
    cpt = [0] * c
    for i in vois:
        cpt[Y[i]] = cpt[Y[i]] + 1
    gagnante = 0
    for j in range(1, c):
        if cpt[j] > cpt[gagnante]:
            gagnante = j
    return gagnante

def knn(X, Y, x, k, c):
    D = distances(X, x)
    vois = plus_proches(D, k)
    return vote(Y, vois, c)

for k in [1, 3, 5]:
    print(k, knn(PLATEAUX, ETAT, INCONNU, k, 2))

1 0
3 0
5 1

Un exercice corrigé Extrait gratuit

Exercice Voisins à la main ★☆☆

Huit points du plan sont déjà classés en deux classes, 0 et 1. On veut classer le point $x = (3, 3)$.

X3 = [[1, 3], [5, 4], [3, 4], [0, 0],
      [2, 2], [4, 6], [6, 6], [1, 0]]
Y3 = [0, 1, 1, 0, 0, 1, 1, 0]

1. Calculer le carré de la distance de $x$ à chaque point.
2. Ranger les points du plus proche au plus lointain.
3. En déduire la classe prédite pour $k = 1$, $k = 3$ et $k = 5$.
4. Contrôler par programme.

Indications

• Méthode 7 : distances, sélection des k plus proches, vote.
• Les carrés suffisent pour ranger.

Analyse : comment trouver l’idée

On calcule les huit carrés, sans racine, puis on lit les plus petits dans l'ordre. Pour chaque valeur de $k$, on compte les classes des $k$ premiers points et l'on prend la plus représentée. Avec deux classes et $k$ impair, il n'y a jamais d'égalité de votes.

Correction détaillée

Question 1. Carrés des distances à $x = (3, 3)$, dans l'ordre des indices :

indice	0	1	2	3	4	5	6	7
point	$(1, 3)$	$(5, 4)$	$(3, 4)$	$(0, 0)$	$(2, 2)$	$(4, 6)$	$(6, 6)$	$(1, 0)$
classe	0	1	1	0	0	1	1	0
carré	4	5	1	18	2	10	18	13

Question 2. Du plus proche au plus lointain : 2 (1), 4 (2), 0 (4), 1 (5), 5 (10), 7 (13), puis 3 et 6 (18 tous les deux ; la règle du cours met 3 avant 6).

Question 3.

• $k = 1$ : le seul voisin est le point 2, de classe 1 : $x$ est classé 1.
• $k = 3$ : points 2, 4, 0, de classes 1, 0, 0 : deux voix pour 0, une pour 1 : classe 0.
• $k = 5$ : points 2, 4, 0, 1, 5, de classes 1, 0, 0, 1, 1 : trois voix pour 1 : classe 1.

La décision change deux fois avec $k$ : un point situé entre deux classes n'a pas de réponse évidente, et c'est le choix de $k$ qui tranche.

Question 4.

D3 = distances(X3, [3, 3])
print(plus_proches(D3, 5))
for k in [1, 3, 5]:
    print(k, knn(X3, Y3, [3, 3], k, 2))

Le programme affiche :

[2, 4, 0, 1, 5]
1 1
3 0
5 1

Méthodes à retenir

On range les données par distance croissante, puis on fait voter les $k$ premières. Le résultat dépend de $k$ : on le fixe par l'évaluation sur des données de test, jamais au hasard. Voir les méthodes 7, 5 et 6.

Plan du cours

• 1. Apprendre à partir d'exemples
  • 1.1 Au coin des pesées
  • 1.2 Intelligence artificielle et apprentissage automatique
  • 1.3 Supervisé, non supervisé
  • 1.4 Représenter les données
  • 1.5 Le Python employé
• 2. Distances
  • 2.1 La distance euclidienne
  • 2.2 Comparer sans racine
  • 2.3 La distance que donne l'énoncé
  • 2.4 L'échelle des attributs
• 3. L'algorithme des k plus proches voisins
  • 3.1 L'idée
  • 3.2 Étape 1 : les distances
  • 3.3 Étape 2 : les k plus proches, sans trier
  • 3.4 Étape 3 : le vote
  • 3.5 Le code complet
  • 3.6 Terminaison, correction, complexité
  • 3.7 Les égalités
• 4. Évaluer et choisir k
  • 4.1 Pourquoi des données de test
  • 4.2 La matrice de confusion
  • 4.3 Lire la matrice
  • 4.4 Choisir k
  • 4.5 Régression par les k plus proches voisins
• 5. Segmenter : l'algorithme des k-moyennes
  • 5.1 Partition, centre, inertie
  • 5.2 L'algorithme
  • 5.3 Une trace à la main
  • 5.4 Le code
  • 5.5 Le groupe vide
  • 5.6 Complexité
• 6. Convergence et minima locaux
  • 6.1 L'inertie ne croît pas
  • 6.2 Un minimum local
  • 6.3 Plusieurs départs
  • 6.4 Combien de groupes
  • 6.5 L'inertie des sujets
• 7. Bilan
  • 7.1 Deux algorithmes à ne pas confondre
  • 7.2 Les complexités
  • 7.3 Vers le chapitre suivant

Les méthodes du chapitre

Chaque méthode est une fiche : quand l'utiliser, le rappel de cours, les étapes, la rédaction attendue sur la copie, un exemple traité, les erreurs à éviter.

1. Reconnaître le type de problème
2. Représenter les données et respecter la représentation imposée
3. Écrire une distance et comparer sans racine
4. Normaliser les attributs
5. Sélectionner les k plus proches sans trier
6. Faire voter les voisins et départager
7. Écrire knn et le dérouler à la main
8. Construire et lire une matrice de confusion
9. Choisir k sur les données de test
10. Dérouler les k-moyennes à la main
11. Affecter et recalculer les centres
12. Écrire les k-moyennes complètes
13. Calculer une inertie, comparer des partitions et répéter les départs
14. Montrer un minimum local et ne pas choisir k par l'inertie
15. Lire et critiquer un code donné
16. Prédire une valeur numérique par les k plus proches voisins
17. Choisir le nombre de groupes par la méthode du coude

Les exercices corrigés

Chaque exercice a ses indications, sa correction rédigée et ce qu'il faut en retenir.

Application directe (14)

• Supervisé ou non supervisé
• Distances à la main
• Voisins à la main
• Égalités
• Le vote par compteurs
• Lire une matrice de confusion
• Une classe contre les autres
• Normaliser à la main
• Un tour de k-moyennes
• Centre et inertie
• Le rectangle
• Trois questions de cours
• Lire un tableau de réussite
• Lire un coude

Entraînement (16)

• Les k plus petits sans trier
• Reconnaître des caractères
• Les olives de la coopérative voisine
• La matrice en code
• Choisir k
• Normaliser, mesurer, commenter
• Les sons sous-marins
• Affecter
• Recalculer, et le groupe vide
• Les k-moyennes avec un nombre maximal de tours
• Tirer les centres de départ
• Plusieurs départs
• Un code à corriger
• Deux représentations d'une partition
• Estimer un prix par les voisins
• Avec les facilités du langage

Approfondissement (6)

• Les points de collecte
• Frontières de décision
• Le hasard et le minimum local
• Choisir k sans tricher
• Manhattan et moyenne
• L'inertie ne croît pas

Les problèmes de concours

Des extraits de sujets réels, corrigés en entier, avec la durée conseillée et les méthodes mobilisées.

• Va-t-il pleuvoir demain ?
  CNC 2026, filières PSI et TSI, épreuve d'informatique, partie II « Va-t-il pleuvoir demain ? », questions 14 à 20 en PSI (15 à 21 en TSI), complétée
• Lire un code postal
  CNC 2025, filière MP, épreuve d'informatique, partie I « Apprentissage automatique supervisé », sections B « Algorithme KNN » et C « Reconnaissance automatique du code postal », questions 14, 15 et 17 à 21, complétée
• Regrouper des fleurs d'iris
  CNC 2024, filière PSI, épreuve d'informatique, partie II « Apprentissage automatique, partitionnement de données (Clustering) », questions 13 à 23, complétée
• Segmenter une image par couleurs
  CNC 2024, filière MP, épreuve d'informatique, partie II « Segmentation d'image », questions 16 à 24, complétée
• Classer des spectres de galaxies et d'étoiles
  CCINP 2026, filière PC, épreuve d'informatique mutualisée avec e3a-Polytech, parties II « Classification de spectres de galaxies » et III « Classification de spectres stellaires », questions 6, 12 à 16, 21 et 22, complétée
• Le prix d'un téléphone
  CNC 2025, filière PSI, épreuve d'informatique, partie II « Apprentissage automatique, prix des téléphones mobiles », questions 14 à 21, complétée

Comment y accéder

Ce chapitre fait partie des chapitres offerts : il s'ouvre en entier avec un compte d'essai gratuit pour les filières dont il est l'un des premiers chapitres. Créer un compte d'essai ou se connecter. Pour l'accès complet et les tarifs, vois les offres.