ALGORITHMES DE

CLUSTERING
Étude du fonctionnement concret

K-Means · GMM · DBSCAN · Hierarchical Clustering

Ce document présente une étude détaillée de quatre algorithmes de regroupement de

données (clustering). Pour chaque algorithme, vous trouverez le principe de fonctionnement,
les étapes pratiques, les paramètres clés, les avantages et inconvénients, ainsi que les cas
d'utilisation typiques.

Vue d'ensemble comparative

Algorithme Type Nb. clusters Forme des clusters Gère le bruit

K-Means Partitionnel Requis (k) Sphérique Non

GMM Probabiliste Requis (k) Elliptique Partiel

DBSCAN Densité Automatique Arbitraire Oui

Hiérarchique Hiérarchique Flexible Variable Non

Algorithmes de Clustering — Page 1

 1. K-Means

Principe
K-Means est un algorithme de clustering partitionnel. Il divise les données en k groupes (clusters) en
minimisant la variance intra-cluster. L'assignation de chaque point est dure : chaque point appartient à un
seul cluster.

Étapes pratiques

1 Choisir le nombre k de clusters.

2 Initialiser k centroïdes de façon aléatoire (ou avec k-means++).

3 Assignation : chaque point est assigné au centroïde le plus proche (distance euclidienne).

4 Mise à jour : recalculer chaque centroïde comme la moyenne des points de son cluster.

5 Répéter les étapes 3 et 4 jusqu'à convergence (centroïdes stables).

Paramètres importants
Paramètre Description

n_clusters Nombre k de clusters souhaités.

init Méthode d'initialisation. k-means++ est recommandé pour de meilleurs résultats.

n_init Nombre d'initialisations aléatoires pour éviter les mauvais minima locaux.

max_iter Nombre maximal d'itérations avant arrêt forcé de l'algorithme.

Avantages & Inconvénients

✔ Avantages ✘ Inconvénients

• Très rapide et simple à implémenter. • Sensible aux outliers et à l'initialisation.

• Bon sur des données bien séparées et sphériques. • Nécessite de connaître k à l'avance.

• Faible coût mémoire. • Fonctionne mal avec des clusters non sphériques.

Cas d'utilisation : Segmentation client · Compression d'images · Regroupement de documents

Algorithmes de Clustering — Page 2

 2. Gaussian Mixture Model (GMM)

Principe
GMM est un modèle probabiliste. Contrairement à K-Means (assignation dure), GMM suppose que
chaque cluster suit une distribution gaussienne (normale). Chaque point appartient à tous les clusters
avec une certaine probabilité. L'apprentissage est réalisé via l'algorithme EM (Expectation-Maximization).

Étapes pratiques (algorithme EM)

1 Initialiser les paramètres : moyennes, covariances et poids des gaussiennes.

2 E-step (Expectation) : calculer la probabilité d'appartenance de chaque point à chaque cluster.

3 M-step (Maximization) : mettre à jour les paramètres pour maximiser la vraisemblance.

4 Répéter jusqu'à convergence.

Paramètres importants
Paramètre Description

n_components Nombre de composantes gaussiennes (équivalent de k).

covariance_type full : matrice complète | tied : partagée | diag : diagonale | spherical : scalaire.

n_init Nombre d'initialisations pour améliorer la robustesse.

max_iter Nombre maximal d'itérations EM.

Avantages & Inconvénients

✔ Avantages ✘ Inconvénients

• Gère bien les clusters de formes et tailles différentes. • Plus lent que K-Means.

• Fournit des probabilités d'appartenance (utile pour • Sensible aux données de grande dimension
l'incertitude). (malédiction de la dimension).

• Très flexible grâce aux différents types de covariance. • Peut diverger si les gaussiennes se chevauchent
fortement.

Cas d'utilisation : Détection d'anomalies · Segmentation d'images · Modélisation de données

biologiques

Algorithmes de Clustering — Page 3

 3. DBSCAN — Density-Based Spatial Clustering

Principe
DBSCAN est un algorithme basé sur la densité. Il regroupe les points densément connectés et marque
comme bruit les points isolés. Il ne nécessite pas de spécifier le nombre de clusters à l'avance et gère
nativement les formes arbitraires.

Concepts clés
Concept Définition

Point central A au moins min_samples voisins dans un rayon eps.

Point de bordure Dans le voisinage d'un point central, mais pas central lui-même.

Point de bruit N'appartient à aucun cluster (outlier).

Étapes pratiques

1 Pour chaque point, examiner son voisinage dans un rayon eps.

2 Si un point a au moins min_samples voisins → il devient un point central.

3 Former des clusters en reliant les points centraux et leurs voisins (points de bordure).

4 Les points n'appartenant à aucun cluster sont marqués comme bruit (noise).

Paramètres importants
Paramètre Description

eps Rayon du voisinage. Un eps trop petit → trop de bruit ; trop grand → un seul cluster.

min_samples Nombre minimum de points dans le voisinage pour former un cluster dense.

metric Mesure de distance utilisée (euclidienne par défaut).

Avantages & Inconvénients

✔ Avantages ✘ Inconvénients

• Ne nécessite pas de fixer le nombre de clusters. • Très sensible au choix de eps et min_samples.

• Gère très bien les formes arbitraires et le bruit. • Moins efficace en grande dimension.

• Robuste aux outliers. • Difficile à appliquer sur des données de densités

variables.

Algorithmes de Clustering — Page 4

Cas d'utilisation : Détection de fraudes · Analyse géospatiale · Segmentation d'images avec bruit

Algorithmes de Clustering — Page 5

 4. Clustering Hiérarchique

Principe
Le clustering hiérarchique construit une hiérarchie de clusters représentée sous forme d'arbre
(dendrogramme). Il existe deux approches :

Approche Description

Agglomérative Commence avec chaque point comme cluster distinct et fusionne progressivement
(bottom-up) les plus proches.

Divisive (top-down) Commence avec un seul cluster global et le divise récursivement.

Étapes pratiques (version agglomérative)

1 Calculer la matrice de distances entre tous les points.

2 Choisir une méthode de linkage (ward, complete, average, single).

3 Fusionner les deux clusters les plus proches.

4 Mettre à jour la matrice de distances.

5 Répéter jusqu'à obtenir un seul cluster → on obtient un dendrogramme.

Méthodes de linkage
Méthode Description Usage

ward Minimise la variance totale intra-cluster. Recommandé en général

complete Distance entre les points les plus éloignés de deux clusters. Clusters compacts

average Distance moyenne entre tous les points des deux clusters. Compromis

single Distance entre les points les plus proches. Formes allongées

Paramètres importants
Paramètre Description

linkage Méthode de calcul de la distance entre clusters. ward souvent optimal.

metric Mesure de distance : euclidienne, cosinus, etc.

n_clusters Couper le dendrogramme à un niveau donné pour obtenir k clusters.

Avantages & Inconvénients

Algorithmes de Clustering — Page 6

 ✔ Avantages ✘ Inconvénients

• Pas besoin de fixer k à l'avance (choix après • Coûteux en mémoire et en temps pour de grands jeux
dendrogramme). de données.

• Très interprétable visuellement. • Sensible au bruit et aux outliers.

• Révèle la structure hiérarchique des données. • Fusions irréversibles (pas de correction possible).

Cas d'utilisation : Taxonomie · Analyse de données génétiques · Organisation de documents

Algorithmes de Clustering — Page 7

 Tableau de comparaison final

Critère K-Means GMM DBSCAN Hiérarchique

Type Partitionnel Probabiliste Densité Hiérarchique

Nb. clusters Requis (k) Requis (k) Automatique Flexible

Assignation Dure Douce (prob.) Dure Dure

Forme clusters Sphérique Elliptique Arbitraire Variable

Gère le bruit Non Partiel Oui ✓ Non

Vitesse Rapide ✓ Moyenne Moyenne Lente

Grande dim. Moyen Faible Faible Faible

Interprétabilité Haute Moyenne Moyenne Très haute ✓

Paramétrage Simple Modéré Sensible Modéré

Comment choisir ?

• K-Means : données volumineuses, clusters sphériques bien séparés, besoin de rapidité.

• GMM : clusters de formes variées, besoin de probabilités d'appartenance.
• DBSCAN : présence de bruit/outliers, clusters de formes complexes, nombre inconnu.
• Hiérarchique : petit jeu de données, besoin d'interprétation visuelle ou de taxonomie.

Algorithmes de Clustering — Page 8