K-Means à la main

Fait partie de la section Apprentissage non supervisé du Journey Machine Learning de Coddy. Leçon 3 sur 51.

K-means répète un tour de deux étapes pour trouver k groupes. Affectation : chaque point rejoint le centre le plus proche. Déplacement : chaque centre se déplace vers la moyenne de ses points. Trois stands de glaces :

150 serviettes sur une plage réparties en trois groupes, à gauche, au milieu et à droite. Trois stands commencent rapprochés près du milieu ; des lignes noires tracent le parcours de chaque stand, tour après tour, jusqu’à une étoile au milieu de son propre groupe

Un tour dans NumPy, où dists est un tableau de distances avec une colonne par centre :

labels = dists.argmin(axis=1)  # attribuer
for c in range(k):
    centers[c] = X[labels == c].mean(axis=0)  # déplacer

argmin(axis=1) donne la colonne la plus petite de chaque ligne : son centre le plus proche. Tour après tour, les centres se stabilisent ; lorsqu’aucun ne bouge, l’algorithme k-means est terminé.

Défi

Facile

Un fabricant de T-shirts adapte ses tailles S, M et L à sa clientèle actuelle. Son ancien tableau des tailles fournit les centres de départ, distances(people, centers) donne le tableau des distances, et le programme lit le nombre de tours à effectuer.

À chaque tour : attribuez une taille à chaque personne, puis déplacez chaque centre.
Affichez le centre de chaque taille et le nombre de personnes qui lui ont été attribuées au dernier tour, comme ci-dessous.

Pour un autre fabricant :

Rounds run: 2
S: chest 87.3 cm, length 65.1 cm, 14 people
M: chest 95.0 cm, length 68.9 cm, 31 people
L: chest 104.8 cm, length 72.6 cm, 45 people

Essayez vous-même

import numpy as np

# Ne modifiez pas les lignes ci-dessous
rng = np.random.default_rng(12)
chest = np.concatenate([rng.normal(88, 3, 30), rng.normal(98, 3.5, 35), rng.normal(110, 4, 25)])
length = np.concatenate([rng.normal(66, 1.8, 30), rng.normal(70, 2, 35), rng.normal(75, 2.2, 25)])
# 90 clients, une ligne par client : tour de poitrine et longueur en cm
people = np.round(np.column_stack([chest, length]), 1)

# L'ancien tableau des tailles définit les centres initiaux : S, M, L
sizes = ["S", "M", "L"]
centers = np.array([[85.0, 64.0], [90.0, 67.0], [96.0, 69.0]])
rounds = int(input())


# Tableau des distances : une ligne par personne, une colonne par centre
def distances(X, centers):
    table = np.zeros((len(X), len(centers)))
    for c in range(len(centers)):
        table[:, c] = np.sqrt(((X - centers[c]) ** 2).sum(axis=1))
    return table


# Écrivez votre code ci-dessous