Regroupez des individus avec k-means et la CAH

Des photos prises le long des quais de la Vilaine, à Rennes, forment-elles un seul ensemble ou plusieurs groupes autour de lieux précis ? Des clients d’une banque se répartissent-ils en quelques profils ? Dans les deux cas, personne ne vous donne les groupes : il faut les découvrir. C’est le partitionnement (clustering), aussi appelé classification non supervisée.

Ce chapitre ouvre la partie consacrée à la fouille de données. Vous verrez d’abord ce qu’est une « bonne » partition, puis deux algorithmes classiques : k-means, qui cherche un nombre fixé de groupes, et la classification ascendante hiérarchique (CAH), qui construit toute une hiérarchie de groupes. Notre fil rouge : six photos repérées par leur position le long d’un quai, en centaines de mètres depuis un pont, aux positions 1, 2, 4, 7, 8 et 10. C’est assez petit pour tout calculer à la main.

Qu’est-ce qu’une bonne partition ?

Intuitivement, un bon partitionnement rassemble des individus semblables à l’intérieur de chaque groupe et différents d’un groupe à l’autre. L’inertie, rencontrée avec l’ACP, permet de le mesurer.

• L’inertie totale mesure la dispersion de tous les points autour du centre de gravité général $g$.
• L’inertie intra-classe mesure la dispersion de chaque groupe autour de son propre centre $g_c$ ; on la veut petite (groupes compacts).
• L’inertie inter-classe mesure la dispersion des centres des groupes autour de $g$, chacun pondéré par son effectif $n_c$ ; on la veut grande (groupes éloignés).

Le théorème de Huygens relie les trois :

$$\underbrace{\sum_{i} d^2(x_i, g)}_{\text{totale}} \;=\; \underbrace{\sum_{c}\sum_{i \in c} d^2(x_i, g_c)}_{\text{intra}} \;+\; \underbrace{\sum_{c} n_c\, d^2(g_c, g)}_{\text{inter}}$$

(on divise souvent les trois termes par le nombre total d’individus $n$, ce qui ne change rien au raisonnement). Comme l’inertie totale ne dépend pas de la partition, minimiser l’inertie intra-classe revient exactement à maximiser l’inertie inter-classe. On n’a donc qu’un seul critère à optimiser.

Exemple

Nos six photos ont pour centre de gravité $g = 32/6 \approx 5{,}33$. L’inertie totale (somme des carrés des écarts) vaut $63{,}33$.

Coupons en deux groupes : $\lbrace 1, 2, 4 \rbrace$ de centre $2{,}33$ et $\lbrace 7, 8, 10 \rbrace$ de centre $8{,}33$. L’inertie intra vaut $4{,}67 + 4{,}67 = 9{,}33$, et l’inertie inter vaut $3 \times (2{,}33 - 5{,}33)^2 + 3 \times (8{,}33 - 5{,}33)^2 = 27 + 27 = 54$. On vérifie Huygens : $9{,}33 + 54 = 63{,}33$. Cette partition « explique » $54 / 63{,}33 \approx 85\,\%$ de l’inertie.

L'inertie intra mesure les écarts des points à leur centre (9,33 au total) ; l'inertie inter, les écarts des centres au centre général, pondérés par les effectifs (54). Leur somme redonne l'inertie totale, 63,33.

L’algorithme k-means

L’algorithme k-means (k-moyennes) cherche $k$ groupes, chacun résumé par son centre (la moyenne de ses points). Il alterne deux étapes jusqu’à ce que plus rien ne bouge :

1. choisir $k$ centres initiaux ;
2. affecter chaque point au centre le plus proche ;
3. recalculer chaque centre comme la moyenne des points qui lui sont affectés ;
4. recommencer les étapes 2 et 3 jusqu’à ce que les affectations ne changent plus.

Chaque étape fait baisser (ou laisse stable) l’inertie intra-classe, qui ne peut pas descendre indéfiniment : l’algorithme converge toujours, et vite.

Exemple

Lançons k-means avec $k = 2$ sur nos photos, en partant (maladroitement) des centres 1 et 2.

• Itération 1 : le point 1 va au centre 1 ; tous les autres sont plus proches de 2. Groupes $\lbrace 1 \rbrace$ et $\lbrace 2, 4, 7, 8, 10 \rbrace$, nouveaux centres 1 et 6,2.
• Itération 2 : le point 2 est maintenant plus proche de 1 (distance 1) que de 6,2 (distance 4,2). Groupes $\lbrace 1, 2 \rbrace$ et $\lbrace 4, 7, 8, 10 \rbrace$, centres 1,5 et 7,25.
• Itération 3 : le point 4 est à 2,5 de 1,5 et à 3,25 de 7,25 ; il change de groupe. Groupes $\lbrace 1, 2, 4 \rbrace$ et $\lbrace 7, 8, 10 \rbrace$, centres 2,33 et 8,33.
• Itération 4 : plus aucun point ne change de groupe. L’algorithme s’arrête, avec l’inertie intra de 9,33 calculée plus haut.

À chaque itération, on affecte les points au centre le plus proche (×), puis on recalcule les centres (◆). Le point 2, puis le point 4, basculent à gauche ; à l'itération 4, plus rien ne bouge.

Malgré un départ maladroit, on a trouvé la meilleure partition en deux groupes. Ce n’est pas toujours le cas : k-means converge vers un minimum local, qui dépend des centres initiaux (l’exercice 3 en montre un exemple). En pratique, on relance l’algorithme plusieurs fois avec des initialisations différentes et l’on garde la meilleure inertie ; l’initialisation k-means++, qui écarte les centres initiaux les uns des autres, rend les mauvais départs rares.

import numpy as np
from sklearn.cluster import KMeans

X = np.array([1, 2, 4, 7, 8, 10], dtype=float).reshape(-1, 1)   # une colonne : la position
km = KMeans(n_clusters=2, init="k-means++", n_init=10, random_state=0).fit(X)
print(km.labels_)            # groupe de chaque photo
print(km.cluster_centers_)   # [[2.33], [8.33]] (l'ordre des groupes peut varier)
print(km.inertia_)           # 9.33 : l'inertie intra-classe

Piège

k-means repose sur des distances euclidiennes : une variable en euros écrasera une variable en années. Standardisez les variables avant (chapitre 3). Et gardez en tête ses hypothèses : il produit des groupes convexes, à peu près sphériques et de tailles comparables, et il affecte chaque point à un groupe, même un point isolé. Le chapitre suivant présente une méthode qui ne fait pas ces hypothèses.

Combien de groupes ?

k-means demande $k$ à l’avance. Comment le choisir ? Bonne question, car l’inertie intra-classe baisse toujours quand $k$ augmente : avec autant de groupes que de points, elle vaut 0. On ne peut donc pas simplement la minimiser.

La méthode du coude. On trace l’inertie intra en fonction de $k$ et l’on cherche le point où la baisse ralentit nettement. Pour nos photos, les meilleures partitions donnent 63,3 pour $k = 1$, puis 9,3, 5,2, 1,0 et 0,5 pour $k = 2$ à 5. La chute est spectaculaire de 1 à 2 groupes, bien plus modeste ensuite : le coude désigne $k = 2$.

L'inertie intra baisse toujours quand k augmente, mais la chute spectaculaire a lieu de 1 à 2 groupes : c'est le coude.

La silhouette. Pour chaque point $i$, on calcule $a(i)$, sa distance moyenne aux autres points de son groupe, et $b(i)$, sa distance moyenne aux points du groupe voisin le plus proche. Sa silhouette vaut

$$s(i) = \frac{b(i) - a(i)}{\max\big(a(i), b(i)\big)}$$

Elle est comprise entre −1 et 1 : proche de 1, le point est bien au cœur de son groupe ; proche de 0, il est à la frontière ; négative, il serait mieux dans le groupe voisin. On choisit le $k$ qui maximise la silhouette moyenne.

Exemple

Pour la photo en position 4, dans le groupe $\lbrace 1, 2, 4 \rbrace$ : $a = (3 + 2)/2 = 2{,}5$ et $b = (3 + 4 + 6)/3 \approx 4{,}33$, d’où $s = (4{,}33 - 2{,}5)/4{,}33 \approx 0{,}42$. C’est la photo la moins bien placée, ce qui est cohérent : c’est elle qui a changé de groupe en dernier. La silhouette moyenne des six photos vaut environ 0,65, ce qui indique une structure nette.

Toutes les silhouettes sont positives : chaque photo est dans le bon groupe. La photo en 4, la plus proche de l'autre groupe, a la plus faible (0,42).

from sklearn.metrics import silhouette_score

for k in range(2, 5):
    labels = KMeans(n_clusters=k, n_init=10, random_state=0).fit_predict(X)
    print(k, round(silhouette_score(X, labels), 3))

La classification ascendante hiérarchique

La CAH ne fixe pas le nombre de groupes à l’avance. Elle part de la situation où chaque individu est un groupe, puis fusionne à chaque étape les deux groupes les plus proches, jusqu’à n’en avoir plus qu’un. L’historique des fusions forme un arbre, le dendrogramme.

Tout dépend de ce qu’on appelle « les deux groupes les plus proches ». Le critère le plus utilisé en analyse de données est celui de Ward : on fusionne les deux groupes dont l’union augmente le moins l’inertie intra-classe. Cette augmentation vaut

$$\Delta(A, B) = \frac{n_A\, n_B}{n_A + n_B}\, d^2(g_A, g_B)$$

où $n_A$ et $n_B$ sont les effectifs des groupes $A$ et $B$, et $g_A$, $g_B$ leurs centres. Le facteur $\frac{n_A n_B}{n_A + n_B}$ pénalise la fusion de deux gros groupes : Ward produit des groupes compacts et de tailles équilibrées, dans le même esprit que k-means.

Exemple

Appliquons Ward à nos six photos.

1. Au départ, pour deux points isolés, $\Delta = \tfrac{1}{2} d^2$. Les paires les plus proches sont $(1, 2)$ et $(7, 8)$, à distance 1 : $\Delta = 0{,}5$ chacune. On fusionne $\lbrace 1, 2 \rbrace$, puis $\lbrace 7, 8 \rbrace$.
2. Il reste $\lbrace 1, 2 \rbrace$ (centre 1,5), $\lbrace 4 \rbrace$, $\lbrace 7, 8 \rbrace$ (centre 7,5) et $\lbrace 10 \rbrace$. Pour fusionner 4 avec $\lbrace 1, 2 \rbrace$ : $\Delta = \tfrac{1 \times 2}{3} \times 2{,}5^2 \approx 4{,}17$. Même valeur pour 10 avec $\lbrace 7, 8 \rbrace$. Ce sont les deux fusions suivantes.
3. Dernière fusion : $\lbrace 1, 2, 4 \rbrace$ avec $\lbrace 7, 8, 10 \rbrace$, $\Delta = \tfrac{3 \times 3}{6} \times 6^2 = 54$.

La somme des augmentations, $0{,}5 + 0{,}5 + 4{,}17 + 4{,}17 + 54 = 63{,}33$, redonne l’inertie totale : chaque fusion transforme un peu d’inertie inter en inertie intra. Et la dernière fusion coûte exactement l’inertie inter de la partition en deux groupes.

Le dendrogramme se lit de bas en haut ; ses hauteurs sont ici les augmentations d’inertie (le schéma n’est pas à l’échelle). Attention, les logiciels n’utilisent pas tous cette échelle : scipy (méthode ward) affiche $\sqrt{2\Delta}$ plutôt que $\Delta$. L’ordre des fusions et la lecture des sauts restent les mêmes. Pour obtenir une partition, on le coupe horizontalement, de préférence juste en dessous d’un grand saut de hauteur. Ici, le saut de 4,17 à 54 est énorme : on coupe en deux classes, $\lbrace 1, 2, 4 \rbrace$ et $\lbrace 7, 8, 10 \rbrace$, la même partition que k-means.

D’autres critères de fusion existent : le lien simple (distance entre les deux points les plus proches, qui crée des chaînes), le lien complet (entre les deux points les plus éloignés) et le lien moyen. Ward reste le choix naturel quand on raisonne en inertie.

from scipy.cluster.hierarchy import dendrogram, fcluster, linkage

Z = linkage(X, method="ward")                  # historique des fusions
classes = fcluster(Z, t=2, criterion="maxclust")   # coupe en 2 classes
dendrogram(Z, labels=[1, 2, 4, 7, 8, 10])      # trace l'arbre (avec matplotlib)

Combiner ACP et classification

L’ACP et la CAH se complètent très bien. On fait d’abord une ACP, puis on classe les individus sur leurs premières composantes seulement. Les derniers axes, de faible inertie, contiennent surtout du bruit : les écarter stabilise la classification. Si le dendrogramme ne change pas quand on retire encore un axe, c’est que les axes restants suffisent.

Une fois les classes obtenues, il faut les décrire : pour chaque classe, on compare la moyenne de chaque variable à la moyenne générale. Un indicateur standard, la valeur-test, mesure cet écart en nombre d’écarts-types ; une valeur-test supérieure à 2 en valeur absolue signale une variable caractéristique de la classe. Enfin, on peut projeter les classes sur la carte de l’ACP, comme une variable illustrative qualitative, pour visualiser leur séparation.

À retenir

Un bon partitionnement minimise l’inertie intra-classe, ce qui revient (Huygens) à maximiser l’inertie inter-classe. k-means cherche $k$ groupes par affectations et recalculs successifs, et converge vers un minimum local ; on choisit $k$ par le coude ou la silhouette. La CAH de Ward fusionne à chaque étape les deux groupes qui augmentent le moins l’inertie intra, et l’on coupe le dendrogramme sous le plus grand saut.

En entretien

« k-means est rapide et marche bien pour des groupes compacts dont on connaît à peu près le nombre ; je standardise avant, je relance plusieurs initialisations et je choisis k avec la silhouette. La CAH de Ward ne demande pas k à l’avance : le dendrogramme montre à quel niveau couper. »

En résumé

• Le partitionnement découvre des groupes sans étiquette ; un bon partitionnement a une faible inertie intra-classe et une forte inertie inter-classe, deux objectifs équivalents par le théorème de Huygens.
• k-means alterne affectation au centre le plus proche et recalcul des centres ; il converge toujours, mais vers un minimum local : on relance avec plusieurs initialisations (k-means++).
• k-means suppose des groupes convexes et affecte chaque point ; il faut standardiser les variables.
• On choisit $k$ avec la méthode du coude ou la silhouette $s(i) = (b - a)/\max(a, b)$.
• La CAH fusionne pas à pas les groupes les plus proches ; le critère de Ward $\Delta = \frac{n_A n_B}{n_A + n_B} d^2(g_A, g_B)$ minimise la hausse d’inertie intra.
• On coupe le dendrogramme sous le plus grand saut ; classer sur les premières composantes d’une ACP enlève du bruit.

Exercices

Exercice · Faire tourner k-means en deux dimensions

facile

Quatre points : $P_1 = (1, 1)$, $P_2 = (2, 1)$, $P_3 = (4, 3)$ et $P_4 = (5, 4)$. On lance k-means avec $k = 2$ et les centres initiaux $c_1 = (1, 1)$ et $c_2 = (2, 1)$. Déroulez l’algorithme jusqu’à convergence.

Voir la solution

Itération 1. $P_1$ est confondu avec $c_1$ et $P_2$ avec $c_2$. $P_3$ et $P_4$ sont plus proches de $c_2$ (par exemple $d(P_3, c_2) = \sqrt{4 + 4} \approx 2{,}83$ contre $d(P_3, c_1) = \sqrt{9 + 4} \approx 3{,}61$). Groupes $\lbrace P_1 \rbrace$ et $\lbrace P_2, P_3, P_4 \rbrace$. Nouveaux centres : $c_1 = (1, 1)$ et $c_2 = \big(\tfrac{2 + 4 + 5}{3}, \tfrac{1 + 3 + 4}{3}\big) \approx (3{,}67 ;\, 2{,}67)$.

Itération 2. $P_2$ est à distance 1 de $c_1$ et à $\sqrt{1{,}67^2 + 1{,}67^2} \approx 2{,}36$ de $c_2$ : il rejoint $c_1$. $P_3$ et $P_4$ restent avec $c_2$. Groupes $\lbrace P_1, P_2 \rbrace$ et $\lbrace P_3, P_4 \rbrace$, centres $(1{,}5 ;\, 1)$ et $(4{,}5 ;\, 3{,}5)$.

Itération 3. Chaque point est plus proche du centre de son groupe : rien ne change, l’algorithme s’arrête.

En code

Python

import numpy as np
from sklearn.cluster import KMeans

P = np.array([[1, 1], [2, 1], [4, 3], [5, 4]], dtype=float)
centres = np.array([[1, 1], [2, 1]], dtype=float)     # centres initiaux imposés

for iteration in range(1, 10):
    distances = np.linalg.norm(P[:, None, :] - centres[None, :, :], axis=2)
    groupes = distances.argmin(axis=1)                 # affectation au centre le plus proche
    nouveaux = np.array([P[groupes == g].mean(axis=0) for g in range(2)])
    print(iteration, groupes, nouveaux.round(2).tolist())
    if np.allclose(nouveaux, centres):
        break
    centres = nouveaux
# 1 [0 1 1 1] [[1.0, 1.0], [3.67, 2.67]]
# 2 [0 0 1 1] [[1.5, 1.0], [4.5, 3.5]]
# 3 [0 0 1 1] [[1.5, 1.0], [4.5, 3.5]] : plus rien ne bouge

km = KMeans(n_clusters=2, init=np.array([[1, 1], [2, 1]]), n_init=1).fit(P)
print(km.labels_, km.cluster_centers_.tolist())        # [0 0 1 1] [[1.5, 1.0], [4.5, 3.5]]

R

P <- matrix(c(1, 1,  2, 1,  4, 3,  5, 4), ncol = 2, byrow = TRUE)
depart <- matrix(c(1, 1,  2, 1), ncol = 2, byrow = TRUE)   # centres initiaux imposés

# Algorithme de Lloyd : exactement les étapes du cours
km <- kmeans(P, centers = depart, algorithm = "Lloyd")
km$cluster    # 1 1 2 2
km$centers    # (1.5, 1) et (4.5, 3.5)
km$iter       # 3 itérations, comme à la main

Exercice · Choisir une fusion avec Ward

moyen

Sur une droite, trois groupes ont été formés : $A = \lbrace 1, 3 \rbrace$, $B = \lbrace 6 \rbrace$ et $C = \lbrace 10, 12 \rbrace$. Calculez l’augmentation d’inertie de Ward pour chacune des trois fusions possibles, et dites laquelle la CAH effectue.

Voir la solution

Les centres sont $g_A = 2$, $g_B = 6$ et $g_C = 11$.

• $\Delta(A, B) = \frac{2 \times 1}{3} \times (6 - 2)^2 = \frac{2}{3} \times 16 \approx 10{,}67$.
• $\Delta(B, C) = \frac{1 \times 2}{3} \times (11 - 6)^2 = \frac{2}{3} \times 25 \approx 16{,}67$.
• $\Delta(A, C) = \frac{2 \times 2}{4} \times (11 - 2)^2 = 1 \times 81 = 81$.

La CAH fusionne A et B, l’union qui augmente le moins l’inertie intra-classe. Remarquez que 6 est à distance 4 de $g_A$ et 5 de $g_C$ : ici, le plus proche centre et le critère de Ward désignent la même fusion, mais ce n’est pas toujours le cas, car Ward tient aussi compte des effectifs.

En code

Python

from itertools import combinations
import numpy as np

groupes = {"A": [1, 3], "B": [6], "C": [10, 12]}

def ward(g, h):
    """Hausse de l'inertie intra-classe si l'on fusionne g et h."""
    na, nb = len(g), len(h)
    return na * nb / (na + nb) * (np.mean(g) - np.mean(h)) ** 2

for a, b in combinations(groupes, 2):
    print(a, b, round(ward(groupes[a], groupes[b]), 2))
# A B 10.67 ; A C 81.0 ; B C 16.67 : la CAH fusionne A et B

# Vérification directe : inertie intra avant et après la fusion de A et B
intra = lambda g: ((np.array(g) - np.mean(g)) ** 2).sum()
print(round(intra([1, 3, 6]) - intra([1, 3]) - intra([6]), 2))   # 10.67

R

groupes <- list(A = c(1, 3), B = 6, C = c(10, 12))

# Hausse de l'inertie intra-classe si l'on fusionne g et h
ward <- function(g, h) {
  na <- length(g); nb <- length(h)
  na * nb / (na + nb) * (mean(g) - mean(h))^2
}
paires <- combn(names(groupes), 2)
hausses <- apply(paires, 2, function(p) ward(groupes[[p[1]]], groupes[[p[2]]]))
names(hausses) <- apply(paires, 2, paste, collapse = "-")
round(hausses, 2)   # A-B 10.67  A-C 81  B-C 16.67 : la CAH fusionne A et B

# Vérification directe : inertie intra avant et après la fusion de A et B
intra <- function(g) sum((g - mean(g))^2)
intra(c(1, 3, 6)) - intra(c(1, 3)) - intra(6)   # 10.67

Exercice · Piéger k-means dans un minimum local

difficile

Quatre points forment un rectangle allongé : $(0, 0)$, $(0, 1)$, $(4, 0)$ et $(4, 1)$. On lance k-means avec $k = 2$.

1. Quelle est la meilleure partition en deux groupes, et son inertie intra-classe ?
2. On part des centres $(2, 0)$ et $(2, 1)$. Montrez que l’algorithme s’arrête immédiatement, et calculez l’inertie obtenue.
3. Qu’en concluez-vous, et comment s’en protège-t-on ?

Voir la solution

1. La meilleure partition sépare la gauche et la droite : $\lbrace (0, 0), (0, 1) \rbrace$ de centre $(0 ;\, 0{,}5)$ et $\lbrace (4, 0), (4, 1) \rbrace$ de centre $(4 ;\, 0{,}5)$. Chaque point est à distance 0,5 de son centre : l’inertie intra vaut $4 \times 0{,}25 = 1$.
2. Avec les centres $(2, 0)$ et $(2, 1)$, les deux points du bas sont à distance 2 de $(2, 0)$ et à $\sqrt{5} \approx 2{,}24$ de $(2, 1)$ : ils vont au premier centre ; symétriquement, ceux du haut vont au second. Les groupes sont « bas » et « haut », et leurs moyennes sont exactement $(2, 0)$ et $(2, 1)$ : les centres ne bougent pas, l’algorithme s’arrête. Chaque point est à distance 2 de son centre : l’inertie vaut $4 \times 4 = 16$, seize fois plus que l’optimum.
3. k-means ne garantit qu’un minimum local, qui dépend de l’initialisation. On s’en protège en relançant l’algorithme avec plusieurs initialisations (n_init dans scikit-learn) et en gardant la plus faible inertie, et en utilisant k-means++, qui choisit les centres initiaux parmi les points en favorisant les points éloignés des centres déjà choisis. Ici, si le premier centre est $(0, 0)$, les carrés des distances aux autres points valent 1, 16 et 17 : le second centre tombe du côté droit avec une probabilité de $33/34$, soit environ 97 %, et l’on part alors vers la bonne partition.

En code

Python

import numpy as np
from sklearn.cluster import KMeans

X = np.array([[0, 0], [0, 1], [4, 0], [4, 1]], dtype=float)

# 1. Départ gauche / droite : l'optimum
bon = KMeans(n_clusters=2, init=np.array([[0, 0.5], [4, 0.5]]), n_init=1).fit(X)
# 2. Départ piège : centres (2, 0) et (2, 1)
piege = KMeans(n_clusters=2, init=np.array([[2, 0], [2, 1]]), n_init=1).fit(X)
print(bon.inertia_, piege.inertia_)            # 1.0  16.0
print(piege.cluster_centers_.tolist())         # [[2.0, 0.0], [2.0, 1.0]] : rien n'a bougé

# 3. k-means++ avec plusieurs départs retrouve l'optimum
print(KMeans(n_clusters=2, n_init=10, random_state=0).fit(X).inertia_)   # 1.0
d2 = ((X - X[0]) ** 2).sum(axis=1)             # carrés des distances à (0, 0)
print(d2, round((d2[2] + d2[3]) / d2.sum(), 2))   # [0 1 16 17]  0.97

R

X <- matrix(c(0, 0,  0, 1,  4, 0,  4, 1), ncol = 2, byrow = TRUE)

# 1. Départ gauche / droite : l'optimum
bon <- kmeans(X, centers = rbind(c(0, 0.5), c(4, 0.5)), algorithm = "Lloyd")
# 2. Départ piège : centres (2, 0) et (2, 1)
piege <- kmeans(X, centers = rbind(c(2, 0), c(2, 1)), algorithm = "Lloyd")
c(bon$tot.withinss, piege$tot.withinss)   # 1  16
piege$centers                             # (2, 0) et (2, 1) : rien n'a bougé

# 3. Plusieurs départs aléatoires (nstart) : on garde la meilleure inertie
set.seed(0)
kmeans(X, centers = 2, nstart = 10)$tot.withinss   # 1
d2 <- rowSums(sweep(X, 2, X[1, ])^2)               # carrés des distances à (0, 0)
d2; round(sum(d2[3:4]) / sum(d2), 2)               # 0 1 16 17 ; 0.97