Clustering

Les choses se rassemblent naturellement par affinités ; la tâche du savant est de découvrir l’ordre caché sous l’apparent désordre.

Carl von Linné

Le clustering (ou partitionnement, regroupement) est la tâche fondamentale de l’apprentissage non supervisé : étant donné un ensemble d’observations sans étiquettes, il s’agit de les répartir en groupes homogènes (appelés clusters) de sorte que les observations d’un même groupe soient similaires entre elles et dissemblables de celles des autres groupes. Contrairement à la classification supervisée, aucune information sur la structure attendue n’est fournie à l’algorithme — celui-ci doit la découvrir seul à partir des données.

Les applications du clustering sont omniprésentes : segmentation de clientèle en marketing, compression d’images par quantification vectorielle, regroupement de gènes en bioinformatique, détection de communautés dans les réseaux sociaux, organisation automatique de documents, ou encore détection d’anomalies. Ce chapitre présente les méthodes principales — des plus classiques (K-Means, clustering hiérarchique) aux approches par densité (DBSCAN, OPTICS) et probabilistes (modèles de mélange gaussien) — ainsi que les outils d’évaluation qui permettent de juger la qualité d’un partitionnement.

Show code cell source

Hide code cell source

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from matplotlib.colors import ListedColormap
from sklearn.datasets import make_blobs, make_moons, make_circles
from sklearn.cluster import (
    KMeans, MiniBatchKMeans, AgglomerativeClustering, DBSCAN, OPTICS
)
from sklearn.mixture import GaussianMixture
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import (
    silhouette_score, silhouette_samples,
    adjusted_rand_score, normalized_mutual_info_score,
    homogeneity_score, completeness_score, v_measure_score,
    calinski_harabasz_score, davies_bouldin_score
)
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from scipy.spatial.distance import pdist
import time
import warnings
warnings.filterwarnings("ignore")

sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1)
np.random.seed(42)

Taxonomie des méthodes de clustering

Avant de détailler chaque algorithme, il est utile de dresser une carte des grandes familles de méthodes :

• Méthodes par partitionnement : elles cherchent à diviser les données en \(k\) groupes non chevauchants en optimisant un critère global (K-Means, K-Medoids).

• Méthodes hiérarchiques : elles construisent une hiérarchie emboîtée de clusters, soit par agglomération (bottom-up), soit par division (top-down).

• Méthodes par densité : elles définissent les clusters comme des régions de haute densité séparées par des régions de basse densité (DBSCAN, OPTICS).

• Méthodes basées sur des modèles : elles supposent que les données sont générées par un mélange de distributions et estiment les paramètres de ce mélange (Gaussian Mixture Models).

Chaque famille possède ses hypothèses, ses forces et ses limites. Le choix de la méthode dépend fondamentalement de la géométrie attendue des clusters, de la taille du jeu de données et de la présence éventuelle de bruit.

K-Means

L’algorithme K-Means est sans doute la méthode de clustering la plus connue et la plus utilisée. Il cherche à partitionner \(n\) observations en \(k\) clusters en minimisant la somme des distances au carré entre chaque observation et le centroïde de son cluster.

Définition 148 (Problème K-Means)

Soit \(\mathcal{X} = \{\mathbf{x}_1, \ldots, \mathbf{x}_n\} \subset \mathbb{R}^d\) un ensemble de \(n\) observations. Le problème K-Means consiste à trouver une partition \(\{C_1, \ldots, C_k\}\) de \(\mathcal{X}\) et des centroïdes \(\{\boldsymbol{\mu}_1, \ldots, \boldsymbol{\mu}_k\} \subset \mathbb{R}^d\) qui minimisent l”inertie (ou within-cluster sum of squares, WCSS) :

\[J = \sum_{j=1}^{k} \sum_{\mathbf{x}_i \in C_j} \|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2\]

où \(\boldsymbol{\mu}_j = \frac{1}{|C_j|} \sum_{\mathbf{x}_i \in C_j} \mathbf{x}_i\) est le centroïde du cluster \(C_j\).

Ce problème d’optimisation est NP-difficile dans le cas général, mais l’algorithme de Lloyd fournit une heuristique efficace qui converge vers un minimum local.

Algorithme de Lloyd

Définition 149 (Algorithme de Lloyd (K-Means))

L’algorithme de Lloyd procède par itérations alternées de deux étapes :

1. Étape d’affectation : chaque observation est assignée au cluster dont le centroïde est le plus proche :

\[C_j^{(t)} = \left\{\mathbf{x}_i : \|\mathbf{x}_i - \boldsymbol{\mu}_j^{(t)}\|^2 \leq \|\mathbf{x}_i - \boldsymbol{\mu}_l^{(t)}\|^2 \;\; \forall\, l \neq j\right\}\]

2. Étape de mise à jour : chaque centroïde est recalculé comme la moyenne des observations de son cluster :

\[\boldsymbol{\mu}_j^{(t+1)} = \frac{1}{|C_j^{(t)}|} \sum_{\mathbf{x}_i \in C_j^{(t)}} \mathbf{x}_i\]

L’algorithme s’arrête lorsque les affectations ne changent plus (ou que la variation de \(J\) est inférieure à un seuil \(\varepsilon\)).

Proposition 41 (Convergence de K-Means)

L’algorithme de Lloyd fait décroître (au sens large) l’inertie \(J\) à chaque itération. Puisque le nombre de partitions possibles est fini, l’algorithme converge en un nombre fini d’itérations vers un minimum local de \(J\). Cependant, ce minimum local peut être très éloigné du minimum global.

Proof. À l’étape d’affectation, chaque point est assigné au centroïde le plus proche, ce qui ne peut que diminuer (ou laisser inchangée) la somme \(J\). À l’étape de mise à jour, le nouveau centroïde est la moyenne des points du cluster, qui minimise la somme des distances au carré dans ce cluster (par propriété du barycentre). Ainsi, \(J^{(t+1)} \leq J^{(t)}\) à chaque itération. Comme \(J \geq 0\) et que la suite est décroissante et bornée inférieurement, elle converge. Le nombre fini de partitions possibles garantit la terminaison en un nombre fini d’étapes.

Initialisation K-Means++

La qualité du résultat dépend fortement de l’initialisation. L’initialisation aléatoire peut conduire à des résultats médiocres. L’algorithme K-Means++ propose une initialisation intelligente.

Définition 150 (Initialisation K-Means++)

L’initialisation K-Means++ choisit les centroïdes initiaux de manière séquentielle :

1. Choisir \(\boldsymbol{\mu}_1\) uniformément au hasard parmi les observations.

2. Pour \(j = 2, \ldots, k\) : choisir \(\boldsymbol{\mu}_j = \mathbf{x}_i\) avec une probabilité proportionnelle à

\[D(\mathbf{x}_i)^2 = \min_{l < j} \|\mathbf{x}_i - \boldsymbol{\mu}_l\|^2\]

Autrement dit, les points éloignés des centroïdes déjà choisis ont une plus grande probabilité d’être sélectionnés.

Proposition 42 (Garantie K-Means++)

L’initialisation K-Means++ garantit en espérance que l’inertie initiale vérifie

\[\mathbb{E}[J] \leq 8(\ln k + 2) \cdot J^*\]

où \(J^*\) est la valeur optimale de l’inertie. Cette garantie est \(O(\log k)\)-compétitive.

La complexité de l’algorithme K-Means est \(O(n \cdot k \cdot d \cdot T)\) où \(T\) est le nombre d’itérations, ce qui le rend très efficace pour de grands jeux de données.

Show code cell source

Hide code cell source

# Démonstration de K-Means sur des données synthétiques
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.8, random_state=42)

fig, axes = plt.subplots(3, 1, figsize=(9, 14))

# Données originales
axes[0].scatter(X[:, 0], X[:, 1], c='gray', alpha=0.6, edgecolors='k', linewidths=0.3, s=40)
axes[0].set_title("Données sans étiquettes")
axes[0].set_xlabel("$x_1$")
axes[0].set_ylabel("$x_2$")

# K-Means avec k=4
kmeans = KMeans(n_clusters=4, init='k-means++', n_init=10, random_state=42)
y_km = kmeans.fit_predict(X)

axes[1].scatter(X[:, 0], X[:, 1], c=y_km, cmap='viridis', alpha=0.6,
                edgecolors='k', linewidths=0.3, s=40)
axes[1].scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1],
                c='red', marker='X', s=200, edgecolors='k', linewidths=1.5,
                label='Centroïdes', zorder=5)
axes[1].set_title(f"K-Means ($k=4$, inertie = {kmeans.inertia_:.1f})")
axes[1].set_xlabel("$x_1$")
axes[1].set_ylabel("$x_2$")
axes[1].legend()

# Mauvaise initialisation : k=4 avec init aléatoire unique
kmeans_bad = KMeans(n_clusters=4, init='random', n_init=1, random_state=3)
y_km_bad = kmeans_bad.fit_predict(X)

axes[2].scatter(X[:, 0], X[:, 1], c=y_km_bad, cmap='viridis', alpha=0.6,
                edgecolors='k', linewidths=0.3, s=40)
axes[2].scatter(kmeans_bad.cluster_centers_[:, 0], kmeans_bad.cluster_centers_[:, 1],
                c='red', marker='X', s=200, edgecolors='k', linewidths=1.5,
                label='Centroïdes', zorder=5)
axes[2].set_title(f"Init. aléatoire unique (inertie = {kmeans_bad.inertia_:.1f})")
axes[2].set_xlabel("$x_1$")
axes[2].set_ylabel("$x_2$")
axes[2].legend()

plt.tight_layout()
plt.show()

Remarque 141

K-Means suppose implicitement que les clusters sont sphériques (isotropes) et de tailles comparables. Lorsque les clusters ont des formes allongées, des densités inégales ou des tailles très différentes, K-Means peut produire des partitions sous-optimales.

Choix du nombre de clusters

Le paramètre \(k\) doit être fixé à l’avance dans K-Means. Plusieurs heuristiques permettent de guider ce choix.

Méthode du coude (Elbow Method)

La méthode du coude consiste à tracer l’inertie \(J(k)\) en fonction de \(k\) et à repérer le point d’inflexion — le « coude » — au-delà duquel l’ajout d’un cluster supplémentaire n’apporte qu’une réduction marginale de l’inertie.

Score de silhouette

Définition 151 (Score de silhouette)

Pour une observation \(\mathbf{x}_i\) appartenant au cluster \(C_j\), on définit :

• \(a(\mathbf{x}_i) = \frac{1}{|C_j| - 1} \sum_{\mathbf{x}_l \in C_j,\, l \neq i} \|\mathbf{x}_i - \mathbf{x}_l\|\) : la distance intra-cluster moyenne.

• \(b(\mathbf{x}_i) = \min_{m \neq j} \frac{1}{|C_m|} \sum_{\mathbf{x}_l \in C_m} \|\mathbf{x}_i - \mathbf{x}_l\|\) : la distance moyenne au cluster le plus proche.

Le coefficient de silhouette de \(\mathbf{x}_i\) est :

\[s(\mathbf{x}_i) = \frac{b(\mathbf{x}_i) - a(\mathbf{x}_i)}{\max\{a(\mathbf{x}_i),\, b(\mathbf{x}_i)\}}\]

Il vérifie \(s(\mathbf{x}_i) \in [-1, 1]\). Une valeur proche de \(1\) indique que l’observation est bien assignée ; une valeur proche de \(-1\) indique une mauvaise assignation.

Indices Calinski-Harabasz et Davies-Bouldin

Définition 152 (Indice de Calinski-Harabasz)

L’indice de Calinski-Harabasz (ou Variance Ratio Criterion) est défini par :

\[\text{CH}(k) = \frac{\text{SS}_B / (k - 1)}{\text{SS}_W / (n - k)}\]

où \(\text{SS}_B = \sum_{j=1}^k |C_j| \|\boldsymbol{\mu}_j - \boldsymbol{\mu}\|^2\) est la dispersion inter-clusters et \(\text{SS}_W = \sum_{j=1}^k \sum_{\mathbf{x}_i \in C_j} \|\mathbf{x}_i - \boldsymbol{\mu}_j\|^2\) est la dispersion intra-clusters. Un indice élevé indique des clusters denses et bien séparés.

Définition 153 (Indice de Davies-Bouldin)

L’indice de Davies-Bouldin mesure la similarité moyenne entre chaque cluster et celui qui lui ressemble le plus :

\[\text{DB} = \frac{1}{k} \sum_{j=1}^k \max_{m \neq j} \frac{s_j + s_m}{d(\boldsymbol{\mu}_j, \boldsymbol{\mu}_m)}\]

où \(s_j = \frac{1}{|C_j|} \sum_{\mathbf{x}_i \in C_j} \|\mathbf{x}_i - \boldsymbol{\mu}_j\|\) est la dispersion moyenne du cluster \(C_j\). Un indice faible indique un meilleur partitionnement.

Show code cell source

Hide code cell source

# Méthode du coude et score de silhouette
K_range = range(2, 10)
inertias = []
sil_scores = []
ch_scores = []
db_scores = []

for k in K_range:
    km = KMeans(n_clusters=k, init='k-means++', n_init=10, random_state=42)
    labels = km.fit_predict(X)
    inertias.append(km.inertia_)
    sil_scores.append(silhouette_score(X, labels))
    ch_scores.append(calinski_harabasz_score(X, labels))
    db_scores.append(davies_bouldin_score(X, labels))

fig, axes = plt.subplots(2, 2, figsize=(13, 10))

axes[0, 0].plot(list(K_range), inertias, 'o-', color='steelblue', linewidth=2)
axes[0, 0].set_xlabel("Nombre de clusters $k$")
axes[0, 0].set_ylabel("Inertie $J$")
axes[0, 0].set_title("Méthode du coude")
axes[0, 0].axvline(x=4, color='coral', linestyle='--', alpha=0.7, label='$k=4$')
axes[0, 0].legend()

axes[0, 1].plot(list(K_range), sil_scores, 's-', color='seagreen', linewidth=2)
axes[0, 1].set_xlabel("Nombre de clusters $k$")
axes[0, 1].set_ylabel("Score de silhouette moyen")
axes[0, 1].set_title("Score de silhouette")
axes[0, 1].axvline(x=4, color='coral', linestyle='--', alpha=0.7, label='$k=4$')
axes[0, 1].legend()

axes[1, 0].plot(list(K_range), ch_scores, 'D-', color='darkorange', linewidth=2)
axes[1, 0].set_xlabel("Nombre de clusters $k$")
axes[1, 0].set_ylabel("Calinski-Harabasz")
axes[1, 0].set_title("Indice de Calinski-Harabasz")
axes[1, 0].axvline(x=4, color='coral', linestyle='--', alpha=0.7, label='$k=4$')
axes[1, 0].legend()

axes[1, 1].plot(list(K_range), db_scores, '^-', color='mediumpurple', linewidth=2)
axes[1, 1].set_xlabel("Nombre de clusters $k$")
axes[1, 1].set_ylabel("Davies-Bouldin")
axes[1, 1].set_title("Indice de Davies-Bouldin (plus bas = mieux)")
axes[1, 1].axvline(x=4, color='coral', linestyle='--', alpha=0.7, label='$k=4$')
axes[1, 1].legend()

plt.tight_layout()
plt.show()

Les quatre critères convergent vers \(k = 4\) : le coude dans la courbe d’inertie, le maximum du score de silhouette, le maximum de l’indice de Calinski-Harabasz et le minimum de l’indice de Davies-Bouldin.

Mini-Batch K-Means

Lorsque le jeu de données est très volumineux, l’algorithme K-Means standard peut être coûteux. Le Mini-Batch K-Means propose une approximation stochastique qui traite à chaque itération un sous-échantillon aléatoire (mini-batch) au lieu de l’ensemble des données.

Définition 154 (Mini-Batch K-Means)

À chaque itération \(t\) :

1. Tirer un mini-batch \(\mathcal{B}^{(t)} \subset \mathcal{X}\) de taille \(b \ll n\).

2. Affecter chaque \(\mathbf{x}_i \in \mathcal{B}^{(t)}\) au centroïde le plus proche.

3. Mettre à jour les centroïdes par une moyenne mobile pondérée : pour chaque centroïde \(\boldsymbol{\mu}_j\) ayant reçu des points du mini-batch,

\[\boldsymbol{\mu}_j \leftarrow \boldsymbol{\mu}_j + \frac{1}{n_j} \sum_{\mathbf{x}_i \in \mathcal{B}^{(t)} \cap C_j} (\mathbf{x}_i - \boldsymbol{\mu}_j)\]

où \(n_j\) est le nombre cumulé de points assignés à \(C_j\) depuis le début.

Remarque 142

Le Mini-Batch K-Means produit des résultats légèrement moins bons que K-Means en termes d’inertie, mais il est considérablement plus rapide pour de grands jeux de données, avec une complexité par itération de \(O(b \cdot k \cdot d)\) au lieu de \(O(n \cdot k \cdot d)\).

Show code cell source

Hide code cell source

# Comparaison de vitesse : K-Means vs Mini-Batch K-Means
X_large, _ = make_blobs(n_samples=50000, centers=8, cluster_std=1.0, random_state=42)

results = {}
for name, model in [("K-Means", KMeans(n_clusters=8, init='k-means++', n_init=5, random_state=42)),
                     ("Mini-Batch K-Means", MiniBatchKMeans(n_clusters=8, batch_size=1024,
                                                            n_init=5, random_state=42))]:
    t0 = time.time()
    labels = model.fit_predict(X_large)
    elapsed = time.time() - t0
    results[name] = {
        "temps": elapsed,
        "inertie": model.inertia_,
        "silhouette": silhouette_score(X_large, labels, sample_size=5000, random_state=42)
    }

print(f"{'Méthode':<25} {'Temps (s)':>10} {'Inertie':>15} {'Silhouette':>12}")
print("-" * 65)
for name, r in results.items():
    print(f"{name:<25} {r['temps']:>10.3f} {r['inertie']:>15.0f} {r['silhouette']:>12.3f}")

Méthode                    Temps (s)         Inertie   Silhouette
-----------------------------------------------------------------
K-Means                        0.705           87433        0.499
Mini-Batch K-Means             0.021           92518        0.577

Clustering hiérarchique

Le clustering hiérarchique construit une hiérarchie emboîtée de clusters, représentée sous forme d’un arbre binaire appelé dendrogramme. L’approche agglomérative (la plus courante) procède de manière ascendante : chaque observation commence comme son propre cluster, puis les clusters les plus proches sont fusionnés itérativement.

Définition 155 (Clustering agglomératif)

L’algorithme de clustering agglomératif procède comme suit :

1. Initialiser \(n\) clusters singletons : \(C_i = \{\mathbf{x}_i\}\) pour \(i = 1, \ldots, n\).

2. Tant qu’il reste plus d’un cluster :

   • Trouver la paire \((C_a, C_b)\) qui minimise la distance inter-clusters \(d(C_a, C_b)\).

   • Fusionner \(C_a\) et \(C_b\) en un nouveau cluster \(C_a \cup C_b\).

   • Mettre à jour la matrice de distances.

3. Le dendrogramme enregistre l’ordre des fusions et les distances correspondantes.

Le choix du critère de liaison (linkage) détermine la façon dont la distance entre deux clusters est calculée.

Définition 156 (Critères de liaison)

Soient \(C_a\) et \(C_b\) deux clusters. Les critères de liaison classiques sont :

• Liaison simple (single linkage) : \(d(C_a, C_b) = \min_{\mathbf{x} \in C_a,\, \mathbf{y} \in C_b} \|\mathbf{x} - \mathbf{y}\|\)

• Liaison complète (complete linkage) : \(d(C_a, C_b) = \max_{\mathbf{x} \in C_a,\, \mathbf{y} \in C_b} \|\mathbf{x} - \mathbf{y}\|\)

• Liaison moyenne (average linkage) : \(d(C_a, C_b) = \frac{1}{|C_a| |C_b|} \sum_{\mathbf{x} \in C_a} \sum_{\mathbf{y} \in C_b} \|\mathbf{x} - \mathbf{y}\|\)

• Liaison de Ward : minimise l’augmentation de la variance intra-cluster lors de la fusion :

\[d_{\text{Ward}}(C_a, C_b) = \frac{|C_a| |C_b|}{|C_a| + |C_b|} \|\boldsymbol{\mu}_a - \boldsymbol{\mu}_b\|^2\]

Remarque 143

La liaison simple a tendance à créer des clusters allongés (effet de chaîne). La liaison complète produit des clusters compacts mais est sensible aux outliers. La liaison de Ward tend à produire des clusters sphériques et de tailles équilibrées, similaires à ceux de K-Means.

Show code cell source

Hide code cell source

# Clustering hiérarchique et dendrogramme
X_hier, y_hier = make_blobs(n_samples=50, centers=3, cluster_std=0.8, random_state=42)

# Calcul du linkage
Z_ward = linkage(X_hier, method='ward')
Z_single = linkage(X_hier, method='single')
Z_complete = linkage(X_hier, method='complete')
Z_average = linkage(X_hier, method='average')

fig, axes = plt.subplots(2, 2, figsize=(15, 12))

for ax, Z, title in zip(axes.flat,
                         [Z_ward, Z_single, Z_complete, Z_average],
                         ['Ward', 'Single', 'Complete', 'Average']):
    dendrogram(Z, ax=ax, truncate_mode='level', p=5, leaf_rotation=90,
               leaf_font_size=8, color_threshold=0.7 * max(Z[:, 2]))
    ax.set_title(f"Dendrogramme — Liaison {title}")
    ax.set_xlabel("Observations")
    ax.set_ylabel("Distance")

plt.tight_layout()
plt.show()

Show code cell source

Hide code cell source

# Coupure du dendrogramme et AgglomerativeClustering
fig, axes = plt.subplots(3, 1, figsize=(9, 14))

for ax, method, title in zip(axes,
                              ['ward', 'single', 'complete'],
                              ['Ward', 'Simple', 'Complète']):
    agg = AgglomerativeClustering(n_clusters=3, linkage=method)
    labels = agg.fit_predict(X_hier)
    ax.scatter(X_hier[:, 0], X_hier[:, 1], c=labels, cmap='viridis',
               edgecolors='k', linewidths=0.3, s=60)
    ax.set_title(f"Liaison {title}")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")

plt.suptitle("Clustering agglomératif — 3 clusters", fontsize=14, y=1.02)
plt.tight_layout()
plt.show()

DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) est un algorithme de clustering fondé sur la notion de densité locale. Contrairement à K-Means, il ne requiert pas de spécifier le nombre de clusters à l’avance et peut détecter des clusters de forme arbitraire. De plus, il identifie naturellement les points aberrants (bruit).

Définition 157 (\(\varepsilon\)-voisinage et densité)

Soit \(\varepsilon > 0\). Le \(\varepsilon\)-voisinage d’un point \(\mathbf{x}_i\) est l’ensemble

\[N_\varepsilon(\mathbf{x}_i) = \{\mathbf{x}_j \in \mathcal{X} : \|\mathbf{x}_i - \mathbf{x}_j\| \leq \varepsilon\}\]

Définition 158 (Points noyau, frontière et bruit)

Soit \(\text{MinPts} \in \mathbb{N}^*\) un seuil de densité minimale.

• Un point \(\mathbf{x}_i\) est un point noyau (core point) si \(|N_\varepsilon(\mathbf{x}_i)| \geq \text{MinPts}\).

• Un point \(\mathbf{x}_i\) est un point frontière (border point) s’il n’est pas un point noyau mais appartient au \(\varepsilon\)-voisinage d’au moins un point noyau.

• Un point \(\mathbf{x}_i\) est un point de bruit (noise point) s’il n’est ni un point noyau ni un point frontière.

Définition 159 (Densité-connexité)

Deux points noyau \(\mathbf{x}_i\) et \(\mathbf{x}_j\) sont directement densité-accessibles si \(\mathbf{x}_j \in N_\varepsilon(\mathbf{x}_i)\). Deux points sont densité-connexes s’il existe une chaîne de points noyau directement densité-accessibles les reliant. Un cluster au sens de DBSCAN est un ensemble maximal de points densité-connexes.

Remarque 144

DBSCAN possède deux hyperparamètres : \(\varepsilon\) (rayon du voisinage) et \(\text{MinPts}\) (nombre minimal de voisins). Le choix de \(\varepsilon\) est souvent guidé par le graphe des \(k\)-distances : on trie les distances au \(k\)-ième plus proche voisin par ordre décroissant et on repère le « coude » de la courbe. Une règle empirique courante est \(\text{MinPts} = 2d\) où \(d\) est la dimension des données.

Show code cell source

Hide code cell source

# DBSCAN sur des données en forme de lunes
X_moons, y_moons = make_moons(n_samples=300, noise=0.07, random_state=42)

fig, axes = plt.subplots(3, 1, figsize=(9, 14))

# K-Means (échoue sur cette géométrie)
km_labels = KMeans(n_clusters=2, random_state=42).fit_predict(X_moons)
axes[0].scatter(X_moons[:, 0], X_moons[:, 1], c=km_labels, cmap='viridis',
                edgecolors='k', linewidths=0.3, s=40)
axes[0].set_title("K-Means ($k=2$)")
axes[0].set_xlabel("$x_1$")
axes[0].set_ylabel("$x_2$")

# DBSCAN
db = DBSCAN(eps=0.15, min_samples=5)
db_labels = db.fit_predict(X_moons)
n_clusters = len(set(db_labels)) - (1 if -1 in db_labels else 0)
n_noise = (db_labels == -1).sum()

colors = db_labels.copy().astype(float)
colors[db_labels == -1] = np.nan  # bruit en gris
axes[1].scatter(X_moons[:, 0], X_moons[:, 1], c=colors, cmap='viridis',
                edgecolors='k', linewidths=0.3, s=40)
axes[1].scatter(X_moons[db_labels == -1, 0], X_moons[db_labels == -1, 1],
                c='gray', marker='x', s=30, label=f'Bruit ({n_noise} pts)')
axes[1].set_title(f"DBSCAN ({n_clusters} clusters)")
axes[1].set_xlabel("$x_1$")
axes[1].set_ylabel("$x_2$")
axes[1].legend(fontsize=9)

# Graphe des k-distances pour le choix de eps
from sklearn.neighbors import NearestNeighbors
nn = NearestNeighbors(n_neighbors=5)
nn.fit(X_moons)
distances, _ = nn.kneighbors(X_moons)
k_dist = np.sort(distances[:, -1])[::-1]

axes[2].plot(k_dist, color='steelblue', linewidth=1.5)
axes[2].axhline(y=0.15, color='coral', linestyle='--', alpha=0.7, label=r'$\varepsilon = 0.15$')
axes[2].set_xlabel("Points (triés)")
axes[2].set_ylabel("Distance au 5e voisin")
axes[2].set_title("Graphe des $k$-distances")
axes[2].legend()

plt.tight_layout()
plt.show()

OPTICS

OPTICS (Ordering Points To Identify the Clustering Structure) est une extension de DBSCAN qui élimine le besoin de fixer un paramètre \(\varepsilon\) global. L’algorithme produit un diagramme d’atteignabilité (reachability plot) qui révèle la structure multi-échelle des clusters.

Définition 160 (Distance d’atteignabilité)

La distance noyau (core distance) d’un point \(\mathbf{x}_i\) est la distance minimale \(\varepsilon'\) telle que \(|N_{\varepsilon'}(\mathbf{x}_i)| \geq \text{MinPts}\) :

\[\text{core-dist}(\mathbf{x}_i) = d(\mathbf{x}_i, N_{\text{MinPts}}(\mathbf{x}_i))\]

La distance d’atteignabilité de \(\mathbf{x}_j\) par rapport à \(\mathbf{x}_i\) est :

\[\text{reach-dist}(\mathbf{x}_j, \mathbf{x}_i) = \max\{\text{core-dist}(\mathbf{x}_i),\; d(\mathbf{x}_i, \mathbf{x}_j)\}\]

Remarque 145

Dans le diagramme d’atteignabilité, les clusters apparaissent comme des vallées : une zone de faibles distances d’atteignabilité entourée de pics. La profondeur et la largeur des vallées renseignent respectivement sur la densité et la taille des clusters.

Show code cell source

Hide code cell source

# OPTICS et diagramme d'atteignabilité
X_optics, y_optics = make_blobs(n_samples=400, centers=[[-3, -3], [0, 0], [3, 3], [6, 0]],
                                 cluster_std=[0.4, 0.8, 0.4, 1.2], random_state=42)

optics = OPTICS(min_samples=10, xi=0.05, min_cluster_size=0.05)
optics.fit(X_optics)
labels_optics = optics.labels_

fig, axes = plt.subplots(2, 1, figsize=(9, 9))

# Diagramme d'atteignabilité
reachability = optics.reachability_[optics.ordering_]
axes[0].bar(range(len(reachability)), reachability, color='steelblue', width=1.0, alpha=0.7)
axes[0].set_xlabel("Ordre OPTICS")
axes[0].set_ylabel("Distance d'atteignabilité")
axes[0].set_title("Diagramme d'atteignabilité")
axes[0].set_ylim(0, np.percentile(reachability[reachability < np.inf], 99) * 1.2)

# Clustering résultant
n_clusters_optics = len(set(labels_optics)) - (1 if -1 in labels_optics else 0)
scatter = axes[1].scatter(X_optics[:, 0], X_optics[:, 1], c=labels_optics, cmap='viridis',
                           edgecolors='k', linewidths=0.3, s=40, alpha=0.7)
axes[1].scatter(X_optics[labels_optics == -1, 0], X_optics[labels_optics == -1, 1],
                c='gray', marker='x', s=30, label='Bruit')
axes[1].set_title(f"OPTICS ({n_clusters_optics} clusters détectés)")
axes[1].set_xlabel("$x_1$")
axes[1].set_ylabel("$x_2$")
axes[1].legend(fontsize=9)

plt.tight_layout()
plt.show()

Modèles de mélange gaussien (GMM)

Les modèles de mélange gaussien (Gaussian Mixture Models, GMM) adoptent une approche probabiliste du clustering. On suppose que les données sont générées par un mélange de \(k\) distributions gaussiennes, chacune caractérisée par sa moyenne, sa matrice de covariance et son poids dans le mélange.

Définition 161 (Modèle de mélange gaussien)

Un mélange de \(k\) gaussiennes est défini par la densité :

\[p(\mathbf{x}) = \sum_{j=1}^{k} \pi_j \,\mathcal{N}(\mathbf{x} \mid \boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j)\]

où :

• \(\pi_j \geq 0\) avec \(\sum_{j=1}^k \pi_j = 1\) sont les poids du mélange (probabilités a priori).

• \(\boldsymbol{\mu}_j \in \mathbb{R}^d\) est la moyenne de la \(j\)-ème composante.

• \(\boldsymbol{\Sigma}_j \in \mathbb{R}^{d \times d}\) est la matrice de covariance (symétrique définie positive) de la \(j\)-ème composante.

• \(\mathcal{N}(\mathbf{x} \mid \boldsymbol{\mu}, \boldsymbol{\Sigma}) = \frac{1}{(2\pi)^{d/2} |\boldsymbol{\Sigma}|^{1/2}} \exp\!\left(-\frac{1}{2}(\mathbf{x} - \boldsymbol{\mu})^\top \boldsymbol{\Sigma}^{-1} (\mathbf{x} - \boldsymbol{\mu})\right)\)

Algorithme EM (Expectation-Maximization)

L’estimation des paramètres \(\boldsymbol{\theta} = \{(\pi_j, \boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j)\}_{j=1}^k\) par maximum de vraisemblance se fait via l’algorithme EM.

Définition 162 (Algorithme EM pour les GMM)

L’algorithme EM alterne deux étapes :

E-step (Espérance) : calculer les responsabilités — la probabilité a posteriori que l’observation \(\mathbf{x}_i\) appartienne au cluster \(j\) :

\[\gamma_{ij} = \frac{\pi_j \,\mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_j, \boldsymbol{\Sigma}_j)}{\sum_{l=1}^k \pi_l \,\mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_l, \boldsymbol{\Sigma}_l)}\]

M-step (Maximisation) : mettre à jour les paramètres en utilisant les responsabilités :

\[N_j = \sum_{i=1}^n \gamma_{ij}, \qquad \boldsymbol{\mu}_j = \frac{1}{N_j} \sum_{i=1}^n \gamma_{ij}\, \mathbf{x}_i\]

\[\boldsymbol{\Sigma}_j = \frac{1}{N_j} \sum_{i=1}^n \gamma_{ij}\, (\mathbf{x}_i - \boldsymbol{\mu}_j)(\mathbf{x}_i - \boldsymbol{\mu}_j)^\top, \qquad \pi_j = \frac{N_j}{n}\]

Proposition 43 (Convergence de l’algorithme EM)

L’algorithme EM fait croître (au sens large) la log-vraisemblance à chaque itération :

\[\ell(\boldsymbol{\theta}^{(t+1)}) \geq \ell(\boldsymbol{\theta}^{(t)}) \quad \text{où} \quad \ell(\boldsymbol{\theta}) = \sum_{i=1}^n \log p(\mathbf{x}_i \mid \boldsymbol{\theta})\]

L’algorithme converge vers un point stationnaire de la vraisemblance (maximum local ou point selle).

Choix du nombre de composantes : BIC et AIC

Définition 163 (BIC et AIC)

Le critère d’information bayésien (BIC) et le critère d’information d’Akaike (AIC) pénalisent la vraisemblance par la complexité du modèle :

\[\text{BIC} = -2\,\ell(\hat{\boldsymbol{\theta}}) + p \ln n, \qquad \text{AIC} = -2\,\ell(\hat{\boldsymbol{\theta}}) + 2p\]

où \(p\) est le nombre de paramètres libres du modèle et \(n\) le nombre d’observations. On choisit le modèle qui minimise le BIC (ou l’AIC).

Remarque 146

Les GMM fournissent un clustering souple (soft clustering) : chaque observation est associée à un vecteur de probabilités d’appartenance \((\gamma_{i1}, \ldots, \gamma_{ik})\), contrairement au clustering dur de K-Means. Pour obtenir un clustering dur, on assigne chaque point au cluster de responsabilité maximale : \(\hat{y}_i = \arg\max_j \gamma_{ij}\).

Show code cell source

Hide code cell source

# GMM : clustering souple et choix du nombre de composantes
X_gmm, y_gmm = make_blobs(n_samples=400, centers=4, cluster_std=[0.8, 1.2, 0.6, 1.0],
                            random_state=42)

fig, axes = plt.subplots(3, 1, figsize=(9, 14))

# GMM avec k=4
gmm = GaussianMixture(n_components=4, covariance_type='full', random_state=42)
gmm.fit(X_gmm)
labels_gmm = gmm.predict(X_gmm)
probs = gmm.predict_proba(X_gmm)

axes[0].scatter(X_gmm[:, 0], X_gmm[:, 1], c=labels_gmm, cmap='viridis',
                edgecolors='k', linewidths=0.3, s=40, alpha=0.7)
# Tracer les ellipses de covariance
from matplotlib.patches import Ellipse
for j in range(4):
    mean = gmm.means_[j]
    cov = gmm.covariances_[j]
    eigenvalues, eigenvectors = np.linalg.eigh(cov)
    angle = np.degrees(np.arctan2(eigenvectors[1, 0], eigenvectors[0, 0]))
    for n_std in [1, 2]:
        ell = Ellipse(xy=mean, width=2*n_std*np.sqrt(eigenvalues[0]),
                      height=2*n_std*np.sqrt(eigenvalues[1]), angle=angle,
                      facecolor='none', edgecolor='coral', linewidth=1.5,
                      linestyle='--' if n_std == 2 else '-')
        axes[0].add_patch(ell)
axes[0].set_title("GMM — Clustering et ellipses de covariance")
axes[0].set_xlabel("$x_1$")
axes[0].set_ylabel("$x_2$")

# Incertitude (entropie de la responsabilité)
entropy = -np.sum(probs * np.log(probs + 1e-10), axis=1)
sc = axes[1].scatter(X_gmm[:, 0], X_gmm[:, 1], c=entropy, cmap='YlOrRd',
                      edgecolors='k', linewidths=0.3, s=40, alpha=0.8)
plt.colorbar(sc, ax=axes[1], label="Entropie")
axes[1].set_title("Incertitude du clustering souple")
axes[1].set_xlabel("$x_1$")
axes[1].set_ylabel("$x_2$")

# BIC / AIC pour le choix de k
K_range_gmm = range(1, 9)
bics = []
aics = []
for k in K_range_gmm:
    gm = GaussianMixture(n_components=k, covariance_type='full', random_state=42)
    gm.fit(X_gmm)
    bics.append(gm.bic(X_gmm))
    aics.append(gm.aic(X_gmm))

axes[2].plot(list(K_range_gmm), bics, 'o-', color='steelblue', linewidth=2, label='BIC')
axes[2].plot(list(K_range_gmm), aics, 's--', color='seagreen', linewidth=2, label='AIC')
axes[2].axvline(x=4, color='coral', linestyle=':', alpha=0.7, label='$k=4$')
axes[2].set_xlabel("Nombre de composantes $k$")
axes[2].set_ylabel("Critère d'information")
axes[2].set_title("BIC et AIC pour le choix de $k$")
axes[2].legend()

plt.tight_layout()
plt.show()

Comparaison pratique

Chaque algorithme de clustering possède ses propres hypothèses sur la forme des clusters, sa propre scalabilité et ses propres sensibilités. Le tableau ci-dessous résume les caractéristiques principales.

Méthode	Forme des clusters	Scalabilité	Paramètres	Bruit
K-Means	Sphérique	\(O(nkdT)\)	\(k\)	Sensible
Mini-Batch K-Means	Sphérique	\(O(bkdT)\)	\(k\), batch	Sensible
Hiérarchique (Ward)	Sphérique	\(O(n^2 \log n)\)	\(k\) ou seuil	Sensible
Hiérarchique (single)	Arbitraire (chaîne)	\(O(n^2)\)	\(k\) ou seuil	Très sensible
DBSCAN	Arbitraire	\(O(n \log n)\)*	\(\varepsilon\), MinPts	Robuste
OPTICS	Arbitraire	\(O(n \log n)\)*	MinPts, \(\xi\)	Robuste
GMM	Ellipsoïdale	\(O(nk d^2 T)\)	\(k\), type cov.	Modéré

* avec un index spatial (KD-tree, ball tree).

Illustrons cette comparaison sur trois jeux de données synthétiques aux géométries variées.

Show code cell source

Hide code cell source

# Comparaison des algorithmes sur trois géométries
datasets = {
    "make_blobs": make_blobs(n_samples=500, centers=3, cluster_std=0.8, random_state=42),
    "make_moons": make_moons(n_samples=500, noise=0.07, random_state=42),
    "make_circles": make_circles(n_samples=500, noise=0.05, factor=0.5, random_state=42),
}

algorithms = {
    "K-Means": lambda: KMeans(n_clusters=3, random_state=42),
    "Hiérar. (Ward)": lambda: AgglomerativeClustering(n_clusters=3, linkage='ward'),
    "DBSCAN": lambda: DBSCAN(eps=0.3, min_samples=5),
    "GMM": lambda: GaussianMixture(n_components=3, random_state=42),
}

# Adapter les paramètres selon le jeu de données
algo_params = {
    "make_blobs": {
        "K-Means": {"n_clusters": 3},
        "Hiérar. (Ward)": {"n_clusters": 3},
        "DBSCAN": {"eps": 1.0, "min_samples": 5},
        "GMM": {"n_components": 3},
    },
    "make_moons": {
        "K-Means": {"n_clusters": 2},
        "Hiérar. (Ward)": {"n_clusters": 2},
        "DBSCAN": {"eps": 0.15, "min_samples": 5},
        "GMM": {"n_components": 2},
    },
    "make_circles": {
        "K-Means": {"n_clusters": 2},
        "Hiérar. (Ward)": {"n_clusters": 2},
        "DBSCAN": {"eps": 0.15, "min_samples": 5},
        "GMM": {"n_components": 2},
    },
}

fig, axes = plt.subplots(3, 4, figsize=(18, 13))

for i, (ds_name, (X_ds, y_ds)) in enumerate(datasets.items()):
    X_ds = StandardScaler().fit_transform(X_ds)

    for j, (algo_name, algo_factory) in enumerate(algorithms.items()):
        ax = axes[i, j]
        params = algo_params[ds_name][algo_name]

        if algo_name == "K-Means":
            model = KMeans(**params, random_state=42)
            labels = model.fit_predict(X_ds)
        elif algo_name == "Hiérar. (Ward)":
            model = AgglomerativeClustering(**params, linkage='ward')
            labels = model.fit_predict(X_ds)
        elif algo_name == "DBSCAN":
            model = DBSCAN(**params)
            labels = model.fit_predict(X_ds)
        elif algo_name == "GMM":
            model = GaussianMixture(**params, random_state=42)
            model.fit(X_ds)
            labels = model.predict(X_ds)

        # Couleurs : bruit en gris
        unique_labels = set(labels)
        colors_arr = labels.astype(float)
        noise_mask = labels == -1

        ax.scatter(X_ds[~noise_mask, 0], X_ds[~noise_mask, 1],
                   c=labels[~noise_mask], cmap='viridis', edgecolors='k',
                   linewidths=0.2, s=25, alpha=0.7)
        if noise_mask.any():
            ax.scatter(X_ds[noise_mask, 0], X_ds[noise_mask, 1],
                       c='gray', marker='x', s=20, alpha=0.5)

        if i == 0:
            ax.set_title(algo_name, fontsize=12, fontweight='bold')
        if j == 0:
            ax.set_ylabel(ds_name, fontsize=11, fontweight='bold')

        ax.set_xticks([])
        ax.set_yticks([])

plt.suptitle("Comparaison des algorithmes de clustering", fontsize=14, y=1.01)
plt.tight_layout()
plt.show()

Remarque 147

Cette comparaison met en évidence les forces et faiblesses de chaque méthode. K-Means et le clustering hiérarchique de Ward excellent sur les blobs sphériques mais échouent sur les lunes et les cercles concentriques. DBSCAN identifie correctement ces structures non convexes, à condition que le paramètre \(\varepsilon\) soit bien choisi. Les GMM peuvent s’adapter à des clusters ellipsoïdaux mais restent limités face à des géométries fortement non convexes.

Métriques d’évaluation

L’évaluation d’un clustering est un problème délicat car, en l’absence d’étiquettes, il n’existe pas de notion objective de « bonne » partition. On distingue deux familles de métriques.

Métriques externes

Les métriques externes comparent le clustering obtenu à une partition de référence (vérité terrain). Elles ne sont utilisables que lorsqu’on dispose d’étiquettes, par exemple pour comparer des algorithmes sur des jeux de données de référence.

Définition 164 (Adjusted Rand Index (ARI))

Soit \(U = \{U_1, \ldots, U_R\}\) la partition obtenue et \(V = \{V_1, \ldots, V_C\}\) la partition de référence. L”indice de Rand ajusté est :

\[\text{ARI} = \frac{\text{RI} - \mathbb{E}[\text{RI}]}{\max(\text{RI}) - \mathbb{E}[\text{RI}]}\]

où \(\text{RI} = \frac{a + b}{\binom{n}{2}}\), avec \(a\) le nombre de paires d’observations qui sont dans le même cluster dans \(U\) et dans \(V\), et \(b\) le nombre de paires qui sont dans des clusters différents dans \(U\) et dans \(V\). L’ARI vaut \(1\) pour un accord parfait et \(0\) en espérance pour un clustering aléatoire.

Définition 165 (Normalized Mutual Information (NMI))

L”information mutuelle normalisée est définie par :

\[\text{NMI}(U, V) = \frac{2 \, I(U; V)}{H(U) + H(V)}\]

où \(I(U; V) = \sum_{i=1}^R \sum_{j=1}^C \frac{|U_i \cap V_j|}{n} \log \frac{n \, |U_i \cap V_j|}{|U_i| \, |V_j|}\) est l’information mutuelle et \(H(U)\), \(H(V)\) sont les entropies des partitions. La NMI est comprise dans \([0, 1]\).

Définition 166 (Homogénéité, complétude et V-mesure)

• Homogénéité : un clustering est homogène si chaque cluster ne contient que des éléments d’une seule classe.

• Complétude : un clustering est complet si tous les éléments d’une même classe sont regroupés dans un seul cluster.

• La V-mesure est la moyenne harmonique de l’homogénéité et de la complétude :

\[V = 2 \cdot \frac{h \cdot c}{h + c}\]

Métriques internes

Les métriques internes évaluent la qualité du clustering sans étiquettes de référence, en mesurant la cohésion intra-cluster et la séparation inter-clusters. Le score de silhouette, l’indice de Calinski-Harabasz et l’indice de Davies-Bouldin (déjà définis plus haut) en sont les exemples les plus courants.

Remarque 148

Les métriques internes ont un biais en faveur de certaines géométries : le score de silhouette et l’indice de Calinski-Harabasz favorisent les clusters convexes et bien séparés. Ils peuvent donner des résultats trompeurs sur des clusters de forme complexe (lunes, cercles concentriques). Les métriques externes, lorsqu’elles sont disponibles, fournissent une évaluation plus fiable.

Show code cell source

Hide code cell source

# Évaluation complète des algorithmes sur make_blobs
X_eval, y_eval = make_blobs(n_samples=500, centers=4, cluster_std=0.8, random_state=42)
X_eval = StandardScaler().fit_transform(X_eval)

models = {
    "K-Means (k=4)": KMeans(n_clusters=4, random_state=42),
    "K-Means (k=3)": KMeans(n_clusters=3, random_state=42),
    "Hiérar. (Ward, k=4)": AgglomerativeClustering(n_clusters=4, linkage='ward'),
    "DBSCAN": DBSCAN(eps=0.5, min_samples=5),
    "GMM (k=4)": GaussianMixture(n_components=4, random_state=42),
}

print(f"{'Modèle':<24} {'ARI':>7} {'NMI':>7} {'Homog.':>7} {'Compl.':>7} "
      f"{'V-mes.':>7} {'Silh.':>7} {'CH':>10} {'DB':>7}")
print("-" * 95)

for name, model in models.items():
    if isinstance(model, GaussianMixture):
        model.fit(X_eval)
        labels = model.predict(X_eval)
    else:
        labels = model.fit_predict(X_eval)

    # Ignorer le bruit pour les métriques internes
    mask = labels != -1
    if mask.sum() < 2 or len(set(labels[mask])) < 2:
        continue

    ari = adjusted_rand_score(y_eval, labels)
    nmi = normalized_mutual_info_score(y_eval, labels)
    h = homogeneity_score(y_eval, labels)
    c = completeness_score(y_eval, labels)
    v = v_measure_score(y_eval, labels)
    sil = silhouette_score(X_eval[mask], labels[mask])
    ch = calinski_harabasz_score(X_eval[mask], labels[mask])
    db = davies_bouldin_score(X_eval[mask], labels[mask])

    print(f"{name:<24} {ari:>7.3f} {nmi:>7.3f} {h:>7.3f} {c:>7.3f} "
          f"{v:>7.3f} {sil:>7.3f} {ch:>10.1f} {db:>7.3f}")

Modèle                       ARI     NMI  Homog.  Compl.  V-mes.   Silh.         CH      DB
-----------------------------------------------------------------------------------------------
K-Means (k=4)              1.000   1.000   1.000   1.000   1.000   0.839     8696.8   0.225
K-Means (k=3)              0.713   0.857   0.750   1.000   0.857   0.767     2041.2   0.345
Hiérar. (Ward, k=4)        1.000   1.000   1.000   1.000   1.000   0.839     8696.8   0.225
DBSCAN                     1.000   1.000   1.000   1.000   1.000   0.839     8696.8   0.225
GMM (k=4)                  1.000   1.000   1.000   1.000   1.000   0.839     8696.8   0.225

Show code cell source

Hide code cell source

# Diagramme de silhouette détaillé pour K-Means
X_sil, y_sil = make_blobs(n_samples=400, centers=4, cluster_std=[0.6, 0.9, 0.7, 1.1],
                            random_state=42)
km_sil = KMeans(n_clusters=4, random_state=42)
labels_sil = km_sil.fit_predict(X_sil)
sil_vals = silhouette_samples(X_sil, labels_sil)
sil_avg = silhouette_score(X_sil, labels_sil)

fig, axes = plt.subplots(2, 1, figsize=(9, 11))

# Diagramme de silhouette
y_lower = 10
for j in range(4):
    cluster_sil = sil_vals[labels_sil == j]
    cluster_sil.sort()
    size_j = cluster_sil.shape[0]
    y_upper = y_lower + size_j

    color = plt.cm.viridis(j / 4)
    axes[0].fill_betweenx(np.arange(y_lower, y_upper), 0, cluster_sil,
                           facecolor=color, edgecolor=color, alpha=0.7)
    axes[0].text(-0.05, y_lower + 0.5 * size_j, str(j), fontsize=10, fontweight='bold')
    y_lower = y_upper + 10

axes[0].axvline(x=sil_avg, color='coral', linestyle='--', linewidth=2,
                label=f'Moyenne = {sil_avg:.3f}')
axes[0].set_xlabel("Coefficient de silhouette")
axes[0].set_ylabel("Cluster")
axes[0].set_title("Diagramme de silhouette")
axes[0].legend()
axes[0].set_yticks([])

# Clusters correspondants
axes[1].scatter(X_sil[:, 0], X_sil[:, 1], c=labels_sil, cmap='viridis',
                edgecolors='k', linewidths=0.3, s=40, alpha=0.7)
axes[1].scatter(km_sil.cluster_centers_[:, 0], km_sil.cluster_centers_[:, 1],
                c='red', marker='X', s=200, edgecolors='k', linewidths=1.5, zorder=5)
axes[1].set_title("Clusters K-Means correspondants")
axes[1].set_xlabel("$x_1$")
axes[1].set_ylabel("$x_2$")

plt.tight_layout()
plt.show()

Résumé

Ce chapitre a présenté les principales méthodes de clustering, chacune répondant à des hypothèses différentes sur la structure des données :

• K-Means est simple, rapide et efficace pour des clusters sphériques et équilibrés, mais nécessite de fixer \(k\) et est sensible à l’initialisation.

• Le Mini-Batch K-Means offre un compromis vitesse-précision pour de très grands jeux de données.

• Le clustering hiérarchique produit une hiérarchie riche (dendrogramme) et ne requiert pas de fixer \(k\) à l’avance, mais sa complexité quadratique limite son usage aux jeux de données de taille modérée.

• DBSCAN et OPTICS découvrent des clusters de forme arbitraire et identifient naturellement le bruit, mais sont sensibles au choix des paramètres de densité.

• Les GMM offrent un cadre probabiliste élégant avec clustering souple, mais supposent des clusters de forme ellipsoïdale.

Le choix de la méthode dépend de la géométrie attendue des clusters, de la taille du jeu de données, de la présence de bruit et du besoin (ou non) d’un clustering souple. Les métriques d’évaluation — internes (silhouette, Calinski-Harabasz, Davies-Bouldin) et externes (ARI, NMI, V-mesure) — fournissent des outils essentiels pour comparer et valider les partitions obtenues. En pratique, il est recommandé d’essayer plusieurs algorithmes et de confronter les résultats, car aucune méthode n’est universellement supérieure.