Un algorithme de machine learning (apprentissage automatique) est une recette précise qui transforme un tableau d'exemples en décisions. Les $k$ plus proches voisins font voter les exemples connus les plus ressemblants, l'arbre de décision pose des questions en cascade, les $k$-moyennes forment des groupes sans connaître aucune réponse. Exemple : pour prévoir si un abonné de salle de sport va résilier, la méthode des 3 plus proches voisins suit la majorité des trois anciens abonnés qui lui ressemblent le plus. Chaque recette est déroulée ici à la main, puis dans trois exercices corrigés.
Les $k$ plus proches voisins
Rappel : un apprentissage est supervisé quand chaque exemple connu porte sa réponse, son étiquette. Pour classer un nouvel exemple, les $k$ plus proches voisins mesurent sa distance à tous les exemples connus, gardent les $k$ plus proches et suivent la majorité de leurs étiquettes. La distance usuelle est euclidienne : pour deux exemples $u$ et $v$ décrits par $p$ variables, $d(u, v) = \sqrt{\sum_{j=1}^{p} (u_j - v_j)^2}$.
Voici six anciens abonnés d'une salle de sport (données fictives), avec leurs séances de septembre et d'octobre. L'abonné N en a fait 4 puis 3 : va-t-il résilier ? Pour ranger les distances, comparer leurs carrés $d^2$ suffit.
| Abonné | Septembre | Octobre | Résiliation | $d^2$ jusqu'à $N(4\,;3)$ |
|---|---|---|---|---|
| A | 1 | 1 | oui | 13 |
| B | 2 | 3 | oui | 4 |
| C | 3 | 1 | oui | 5 |
| D | 4 | 4 | non | 1 |
| E | 6 | 5 | non | 8 |
| F | 7 | 7 | non | 25 |
Pour A : $(4-1)^2 + (3-1)^2 = 13$. Avec $k = 1$, seul D compte : N resterait. Avec $k = 3$, D, B et C votent, deux résiliations contre un maintien : N résilierait.
Rien n'est réglé à l'entraînement : l'algorithme garde les exemples et calcule tout au moment de prédire. Un grand $k$ atténue le bruit, ces variations dues au hasard, mais brouille la frontière entre classes (documentation de scikit-learn). Avec deux classes, prends $k$ impair pour éviter les égalités. Dans scikit-learn, $k$ s'appelle n_neighbors et vaut 5 par défaut.
Piège classique : la distance ignore les unités. Avec la dépense au bar en euros à côté des séances, 10 € d'écart pèsent autant que 10 séances : la variable aux plus grands nombres choisit seule les voisins. Standardise d'abord chaque variable (moyenne 0, écart type 1).
L'arbre de décision
Un arbre de décision pose des questions fermées, chacune sur une seule variable ; au bout de chaque branche, une feuille donne la réponse. Pour choisir la meilleure question, l'algorithme mesure le mélange des étiquettes.
Définition : si la classe $c$ forme une part $p_c$ d'un groupe, l'impureté de Gini du groupe vaut $G = 1 - \sum_c p_c^2$. C'est la probabilité que deux exemples tirés au hasard, avec remise, aient des étiquettes différentes.
Elle vaut 0 pour un groupe pur, et 0,5 au plus avec deux classes. Une question coupe $n$ exemples en deux groupes de $n_g$ et $n_d$ exemples, et reçoit le score $\dfrac{n_g}{n}G_g + \dfrac{n_d}{n}G_d$. L'algorithme teste toutes les variables et tous les seuils, garde le plus petit score et recommence dans chaque branche : c'est la méthode CART, qu'utilise scikit-learn.
Huit anciens abonnés (données fictives) :
| Abonné | Engagement | Séances par mois | Résiliation |
|---|---|---|---|
| 1 | non | 1 | oui |
| 2 | non | 2 | oui |
| 3 | non | 3 | oui |
| 4 | non | 5 | oui |
| 5 | non | 6 | non |
| 6 | oui | 2 | non |
| 7 | oui | 3 | non |
| 8 | oui | 10 | non |
Au départ, 4 résiliations sur 8 : $G = 0{,}5$. Question « engagé ? » : les 3 engagés sont tous restés, $G = 0$ ; parmi les 5 autres, 4 ont résilié, $G = 1 - (0{,}8^2 + 0{,}2^2) = 0{,}32$. Score : $\dfrac{3}{8} \times 0 + \dfrac{5}{8} \times 0{,}32 = 0{,}2$.
Le meilleur seuil sur les séances, au plus 5 par mois, laisse d'un côté 6 abonnés dont 4 résiliés ($G = \dfrac{4}{9}$), de l'autre 2 restés : score $\dfrac{6}{8} \times \dfrac{4}{9} = \dfrac{1}{3}$. L'arbre commence donc par l'engagement, puis ce seuil tranche la branche sans engagement : on y résilie à 5 séances ou moins. Comme chaque question porte sur une seule variable, changer d'unité ne déplace que le seuil.
Par défaut, scikit-learn coupe jusqu'à des feuilles pures : ici, une feuille repose sur le seul abonné 5. Une règle tirée d'un seul cas, c'est du surapprentissage : elle colle aux exemples sans valoir pour les suivants. On freine l'arbre avec max_depth (profondeur maximale) ou min_samples_leaf (exemples minimum par feuille).
Les $k$-moyennes
Sans étiquette, l'apprentissage est non supervisé : la salle cherche cette fois des profils d'abonnés. Les $k$-moyennes (k-means) forment $k$ groupes autour de $k$ centres.
Étape 1 : placer $k$ centres de départ, par exemple sur $k$ exemples.
Étape 2 : affecter chaque exemple au centre le plus proche.
Étape 3 : remplacer chaque centre par la moyenne de son groupe, puis reprendre l'étape 2 jusqu'à ce que plus rien ne bouge.
Six abonnés (données fictives) sont notés par leurs séances du mois en semaine, puis le week-end : P1 $(1\,;2)$, P2 $(2\,;1)$, P3 $(2\,;3)$, P4 $(6\,;5)$, P5 $(7\,;7)$ et P6 $(8\,;6)$. On prend $k = 2$, en partant de P1 et P3.
| Tour | Centres | Groupe 1 | Groupe 2 |
|---|---|---|---|
| 1 | $(1\,;2)$ et $(2\,;3)$ | P1, P2 | P3, P4, P5, P6 |
| 2 | $(1{,}5\,;1{,}5)$ et $(5{,}75\,;5{,}25)$ | P1, P2, P3 | P4, P5, P6 |
| 3 | $\left(\tfrac{5}{3}\,;2\right)$ et $(7\,;6)$ | P1, P2, P3 | P4, P5, P6 |
Au tour 2, P3 change de groupe : $d^2 = 0{,}5^2 + 1{,}5^2 = 2{,}5$ jusqu'au centre 1, contre $19{,}1$ environ jusqu'au centre 2. Au tour 3, rien ne bouge : deux profils, peu et très assidus.
Pourquoi ça s'arrête : chaque étape fait baisser l'inertie, somme des carrés des distances de chaque exemple à son centre, ou la laisse égale ; la moyenne est justement le point qui minimise cette somme pour un groupe. Les répartitions étant en nombre fini, l'algorithme se fige, ici à une inertie de $\dfrac{20}{3} \approx 6{,}67$.
Le résultat dépend aussi du départ : scikit-learn place les centres initiaux loin les uns des autres (k-means++, par défaut) et peut relancer plusieurs départs pour garder le meilleur (n_init).
Piège classique : choisir $k$ à l'inertie la plus basse. Elle ne remonte jamais quand $k$ augmente et tombe à 0 quand chaque exemple forme son propre groupe. Cherche plutôt le coude, au-delà duquel un groupe de plus ne la fait presque plus baisser.
Choisir entre les trois
| Méthode | Apprentissage | Ce qu'elle garde | Échelle des variables |
|---|---|---|---|
| $k$ plus proches voisins | supervisé | tous les exemples | à standardiser |
| Arbre de décision | supervisé | ses questions | sans effet |
| $k$-moyennes | non supervisé | les $k$ centres | à standardiser |
Dans le programme national du BUT Science des données, R4.03 « Classification automatique » (semestre 4) traite du regroupement non supervisé, et R5.02 « Data mining » (semestre 5) cite les arbres CART et les $k$ plus proches voisins.
Piège classique : dans ce programme, « classification automatique » veut dire regroupement sans étiquette (mot clé de R4.03 : « clustering »), et R5.02, supervisée, parle de « classement ». En anglais, donc dans scikit-learn, « classification » désigne la prédiction d'une étiquette, d'où KNeighborsClassifier.
Exercices corrigés
Exercice 1 : Pour classer l'abonné M (8 séances par mois, 40 € dépensés au bar) avec $k = 1$, seuls deux anciens abonnés sont en lice (données fictives) : X (8 séances, 50 €), resté, et Y (2 séances, 42 €), résilié. Trouve le plus proche voisin avec les valeurs brutes, puis après avoir divisé les séances par leur écart type, 3, et la dépense par le sien, 20 €.
Correction :
Valeurs brutes : $d^2(M, X) = 0^2 + 10^2 = 100$ et $d^2(M, Y) = 6^2 + 2^2 = 40$. Y l'emporte : M résilierait, alors qu'il fait autant de séances que X.
Après division : $d^2(M, X) = 0^2 + 0{,}5^2 = 0{,}25$ et $d^2(M, Y) = 2^2 + 0{,}1^2 = 4{,}01$. X l'emporte : M resterait. Sans mise à l'échelle, l'écart de 10 € décidait seul. Soustraire en plus la moyenne, comme le fait la standardisation, ne changerait aucun écart.
Exercice 2 : Un service client veut prédire si une réclamation sera traitée en plus de 48 heures (données fictives). Question A, « arrivée par courrier ? » : oui pour 4 réclamations dont 3 en retard, non pour 6 dont 1 en retard. Question B, « montant supérieur à 100 € ? » : oui pour 5 dont 3 en retard, non pour 5 dont 1 en retard. Laquelle l'arbre place-t-il à la racine ?
Correction :
Question A : $G_{\text{oui}} = 1 - \left(\left(\tfrac{3}{4}\right)^2 + \left(\tfrac{1}{4}\right)^2\right) = 0{,}375$ et $G_{\text{non}} = 1 - \left(\left(\tfrac{1}{6}\right)^2 + \left(\tfrac{5}{6}\right)^2\right) = \tfrac{5}{18}$. Score : $0{,}4 \times 0{,}375 + 0{,}6 \times \tfrac{5}{18} \approx 0{,}317$.
Question B : $G_{\text{oui}} = 1 - (0{,}6^2 + 0{,}4^2) = 0{,}48$ et $G_{\text{non}} = 1 - (0{,}2^2 + 0{,}8^2) = 0{,}32$. Score : $0{,}5 \times 0{,}48 + 0{,}5 \times 0{,}32 = 0{,}4$.
L'arbre place A à la racine, au score le plus bas.
Exercice 3 : Une boutique en ligne veut deux groupes de clients d'après leur panier moyen, en euros : 10, 20, 40, 90, 100 et 120 (données fictives). Applique les $k$-moyennes en partant des centres 10 € et 20 €.
Correction :
Tour 1 : seul 10 va au centre 10, les autres sont plus près de 20. Nouveaux centres : 10 € et $\dfrac{20 + 40 + 90 + 100 + 120}{5} = 74$ €.
Tour 2 : 20 et 40 passent au premier centre, 40 de justesse (30 € d'écart contre 34 €). Nouveaux centres : $\dfrac{70}{3} \approx 23{,}33$ € et $\dfrac{310}{3} \approx 103{,}33$ €.
Tour 3 : rien ne bouge. Petits paniers $\{10\,;20\,;40\}$, gros paniers $\{90\,;100\,;120\}$.
À retenir
À retenir :
- $k$ plus proches voisins : vote des $k$ exemples les plus proches, sur des variables standardisées.
- Arbre de décision : à chaque étape, la question qui minimise l'impureté de Gini pondérée, avec $G = 1 - \sum_c p_c^2$ ; sans frein, il surapprend.
- $k$-moyennes : affecter au centre le plus proche, recalculer les moyennes, recommencer ; $k$ se choisit au coude de l'inertie.
Sources
- Programme national 2022 du BUT Science des données, mis à jour en 2023, ministère de l'Enseignement supérieur, ressources R4.03 et R5.02 : texte en PDF.
- Documentation de scikit-learn : plus proches voisins, arbres de décision, k-moyennes.