Comment une machine peut-elle former des groupes dans des données sans qu'on lui dise lesquels ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Les plateformes de vidéo regroupent les spectateurs en « profils » sans qu'aucun humain ne les définisse. En NSI, j'ai découvert l'algorithme des k-moyennes, qui forme des groupes tout seul. J'ai été surpris de retrouver dans sa justification une propriété de la moyenne que j'avais étudiée en statistiques : elle minimise la somme des carrés des écarts.

L'enjeu et les notions du programme

Démontrer que la moyenne minimise une somme de carrés et en déduire qu'un algorithme itératif fait décroître une erreur.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   On dispose de données sans étiquettes, par exemple les durées de visionnage de spectateurs, et l'on veut les répartir en $k$k groupes homogènes. Problématique : comment former ces groupes automatiquement, et pourquoi l'algorithme s'arrête-t-il ?

2. 2. NSI : l'algorithme

   2,5 min

   On choisit $k$k centres de départ. Puis on répète deux étapes. Affectation : chaque point rejoint le groupe du centre le plus proche. Mise à jour : chaque centre est remplacé par la moyenne des points de son groupe. On s'arrête quand plus rien ne change.

   Exemple avec $k=2$k=2 sur 1, 2, 3, 10, 11, 12 et les centres de départ 1 et 2. Tour 1 : groupes {1} et {2, 3, 10, 11, 12}, nouveaux centres 1 et 7,6. Tour 2 : groupes {1, 2, 3} et {10, 11, 12}, centres 2 et 11. Tour 3 : rien ne change.

3. 3. Mathématiques : pourquoi l'erreur diminue

   4,5 min

   On mesure la qualité par l'inertie : la somme des carrés des distances de chaque point à son centre. Pour les groupes finaux : $(1-2{)}^2+0+(3-2{)}^2+(10-11{)}^2+0+(12-11{)}^2=4$(1-2)²+0+(3-2)²+(10-11)²+0+(12-11)²=4.

   Propriété : pour des nombres $x_1,\dots ,x_n$x₁,…,xₙ, la fonction $g(c)=\sum (x_i-c{)}^2$g(c)=Σ(xᵢ-c)² est minimale pour $c=\bar{x}$c=bar x. En effet, $g(c)=n{c}^2-2c\sum x_i+\sum x_i^2$g(c)=nc²-2cΣ xᵢ+Σ xᵢ² est un polynôme du second degré de coefficient $n>0$n>0, minimal au sommet $c=\frac{\sum x_i}{n}=\bar{x}$c=(Σ xᵢ)/n=bar x. Sa valeur minimale est $nV(x)$n V(x).

   Chaque étape fait donc diminuer l'inertie ou la laisse égale : l'affectation au centre le plus proche réduit chaque distance, et le remplacement par la moyenne minimise la somme dans chaque groupe. L'inertie forme une suite décroissante, et comme il n'y a qu'un nombre fini de façons de former des groupes, l'algorithme s'arrête.

   Mais il peut s'arrêter sur une solution qui n'est pas la meilleure : le résultat dépend des centres de départ.

4. 4. Conclusion

   1,5 min

   Les k-moyennes forment des groupes en alternant affectation et calcul de moyennes ; la moyenne minimisant la somme des carrés, l'erreur décroît à chaque tour et l'algorithme s'arrête. On le relance avec plusieurs départs pour éviter une mauvaise solution. J'ouvre sur le choix de $k$k, qui reste une décision humaine.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Croire que l'algorithme trouve toujours la meilleure répartition.
• Confondre k-moyennes et k plus proches voisins.
• Oublier que le nombre de groupes est choisi à l'avance.

Revoir les notions

• Second degré (Première spé maths) →
• Statistiques descriptives (Seconde) →

Autres questions : données et intelligence artificielle

• Comment une machine peut-elle classer une donnée nouvelle en regardant simplement ses voisines ?
• Pourquoi le résultat d'un algorithme d'intelligence artificielle peut-il changer si l'on mesure en millimètres plutôt qu'en centimètres ?
• Comment une machine trouve-t-elle la droite qui résume le mieux un nuage de points ?
• Comment une intelligence artificielle apprend-elle en corrigeant ses erreurs pas à pas ?

Toutes les questions maths-nsi →