Chapitre 12

Clustering

Comment étudier des données non étiquetées ? La dimension de réduction nous permet de les visuali-
ser ; mais les méthodes dites de partitionnement de données, ou clustering, nous permettent d’aller beaucoup
plus loin. Il s’agit de séparer les données en sous-groupes homogènes, appelés clusters, qui partagent des
caractéristiques communes. Dans ce chapitre, nous détaillerons l’intérêt de ces techniques et verrons trois
types d’approches de clustering : le clustering hiérarchique, le clustering par centroïdes, et le clustering
par densité.

Objectifs
— Expliquer l’intérêt d’un algorithme de clustering
— Évaluer le résultat d’un algorithme de clustering
— Implémenter un clustering hiérarchique, un clustering par la méthode des k moyennes, et un clus-
tering par densité.

12.1 Pourquoi partitionner ses données

Les algorithmes de partitionnement de données permettent d’effectuer une analyse exploratoire sur
des données non étiquetées. Ils permettent par exemple d’identifier des utilisateurs qui ont des comporte-
ments similaires (ce que l’on appelle la segmentation de marché), des communautés sur un réseau social, des
motifs récurrents dans des transactions financières, des pixels d’un même objet dans une image (segmen-
tation d’image) ou des patients dont la maladie s’explique par un même profil génétique.
Ils permettent aussi de visualiser les données, en se contentant de regarder un exemple représentatif
par cluster.
Enfin, les algorithmes de clustering permettent de transférer à toutes les observations du même cluster
les propriétés que l’on sait vraies de l’un des éléments de ce cluster. Cela est particulièrement utile dans le
cas où l’étiquetage des données est difficile ou coûteux.

148
12.2. Évaluer la qualité d’un algorithme de clustering 149

Exemple
Prenons l’exemple de l’annotation d’un corpus de documents texte. Annoter manuellement chacun de
ces documents par le ou les sujets qu’il couvre est un travail fastidieux. Les personnes qui l’effectuent sont
d’ailleurs susceptibles de commettre involontairement des erreurs d’inattention. Il est ainsi moins coûteux,
voire plus efficace, d’utiliser un algorithme de clustering pour regrouper automatiquement ces documents
par sujet. Il suffira alors d’avoir recours à un intervenant humain pour assigner un sujet à chaque cluster
en lisant uniquement un ou deux des documents qu’il contient.

12.2 Évaluer la qualité d’un algorithme de clustering

Le clustering n’étant pas supervisé, il nous faut mettre au point des critères d’évaluation qui ne dé-
pendent pas d’une vérité terrain (c’est-à-dire d’étiquettes connues). La tâche est plus délicate que dans
le cadre de l’apprentissage supervisé, dans lequel le but à atteindre est beaucoup plus clair. Cependant,
elle n’est pas impossible, et il existe un large éventail de mesures de la performance d’un algorithme de
partitionnement des données.
Par la suite, nous supposons avoir partitionné un jeu de données non étiqueté D = {~x 1 , ~x 2 , . . . , ~x n }
de n points d’un espace X en K clusters C1 , C2 , . . . , CK . d est une distance sur X et k(~x) est l’indice du
cluster auquel ~x a été assigné.

12.2.1 La forme des clusters

Pour évaluer la qualité des clusters obtenus par un algorithme de partitionnement, il est possible de
s’appuyer sur le souhait formulé de regrouper entre elles les observations similaires. Ainsi, les observations
appartenant à un même cluster doivent être proches, tandis que les observations dissimilaires doivent ap-
partenir à des clusters différents.
Pour quantifier ces notions, nous allons avoir besoin de celle de centroïde, qui est le barycentre d’un
cluster.
Définition 12.1 (Centroïde et médoïde) On appelle centroïde du cluster C le point défini par
1 X
µ
~C = ~x.
|C|
x∈C
~

Le médoïde est le point du cluster le plus proche du centroïde (il peut ne pas être unique, auquel cas il
sera choisi arbitrairement). Il sert de représentant du cluster :

m
~ C = arg min d(~x, µ
~ C ).
x∈C
~

Que des observations proches appartiennent au même cluster peut se traduire par la notion d’homo-
généité, illustrée sur la figure 12.1 :
Définition 12.2 (Homogénéité) On appelle homogénéité du cluster Ck , ou tightness en anglais, la moyenne
des distances des observations de ce cluster à son centroïde :
1 X
Tk = d(~x, µ
~ k ).
|Ck |
x∈Ck
~
150 Chapitre 12. Clustering

~ k est le centroïde de Ck .
Ici µ
L’homogénéité globale d’un clustering de D se calcule comme la moyenne des homogénéités des clusters :

K
1 X
T = Tk .
K
k=1

Figure 12.1 – Les deux clusters représentés sur le panneau de gauche sont homogènes, resserrés sur eux-
mêmes : ils sont composés de points proches les uns des autres. À l’inverse, les deux clusters représentés
sur le panneau de droite sont moins homogènes.

Pour quantifier à quel point les clusters sont distants les uns des autres, nous pouvons utiliser le critère
de séparabilité, illustré sur la figure 12.2.
Définition 12.3 (Séparabilité) On appelle séparabilité des clusters Ck et Cl la distance entre leurs cen-
troïdes :
Skl = d(~µk , µ
~ l ).
La séparabilité globale d’un clustering de D se calcule comme la moyenne des séparabilités des clusters
deux à deux :
K X K
2 X
S= Skl .
K(K − 1)
k=1 k=k+1

Plutôt que de considérer les deux critères de séparabilité (que l’on souhaite élevée) et d’homogénéité
(que l’on souhaite faible) séparément, il est possible de les comparer l’un à l’autre grâce à l’indice de Davies-
Bouldin.
Définition 12.4 (Indice de Davies-Bouldin) On appelle indice de Davies-Bouldin du cluster Ck la valeur

Tk + Tl
Dk = max .
l6=k Skl
12.2. Évaluer la qualité d’un algorithme de clustering 151

Figure 12.2 – Les trois clusters représentés sur le panneau de gauche sont bien séparés, contrairement à
ceux représentés sur le panneau de droite qui sont proches les uns des autres.

L’indice de Davies-Bouldin global d’un clustering de D se calcule comme la moyenne des indices de Davies-
Bouldin des clusters :
K
1 X
D= Dk .
C
k=1

Une autre façon de prendre en compte séparabilité et homogénéité est de calculer le coefficient de sil-
houette, qui permet de quantifier pour chacune des observations si elle appartient ou non au bon cluster.

Définition 12.5 (Coefficient de silhouette) On appelle coefficient de silhouette de l’observation ~x ∈ D

la valeur
b(~x) − a(~x)
s(~x) =
max(a(~x), b(~x))
où a(~x) est la distance moyenne de ~x à tous les autres éléments du cluster auquel il appartient et b(~x) est
la plus petite valeur que pourrait prendre a(~x), si a appartenait à un autre cluster :

1 X 1 X
a(~x) = d(~u, ~x); b(~x) = min d(~u, ~x).
|Ck(~x) | − 1 x) |Cl |
l6=k(~
u∈Ck(~x) ,~
~ u6=~
x u∈Cl
~

Le coefficient de silhouette global du clustering est son coefficient de silhouette moyen :

n
1X
s= s(~x i ).
n
i=1

Le coefficient de silhouette de ~x est d’autant plus proche de 1 que son assignation au cluster Ck(~x) est
satisfaisante.
152 Chapitre 12. Clustering

12.2.2 La stabilité des clusters

Un autre critère important est celui de la stabilité des clusters. On s’attend en effet à obtenir les mêmes
clusters si on supprime ou perturbe quelques observations, ou en initialisant différemment l’algorithme
de partitionnement.
Ce critère peut être utilisé pour choisir les hyperparamètres de l’algorithme : si on obtient des clusters
très différents pour différentes initialisations de l’algorithme de partitionnement, cela peut indiquer que
les hyperparamètres sont mal choisis.

12.2.3 Les connaissances expert

Enfin, il arrive parfois que l’on dispose d’un jeu de données partiellement étiqueté par des classes que
nous aimerions retrouver par clustering. Cela peut être le cas d’un corpus de documents dont un sous-
ensemble est étiqueté par sujet, ou d’une base de données d’images dont un sous-ensemble est étiqueté en
fonction de ce qu’elles représentent.
On peut alors évaluer le résultat d’un algorithme de partitionnement comme on évaluerait celui d’un
algorithme de classification multi-classe. Attention, il y a cependant une différence : dans le cas du clus-
tering, peu importe que les objets de la classe k se retrouvent dans le premier, le deuxième ou le k-ème
cluster. Il faut donc évaluer la concordance de la partition des données par l’algorithme de clustering avec
celle induite par les étiquettes. C’est ce que permet de faire l’indice de Rand.
Nous supposons maintenant les observations ~x i étiquetées par y i ∈ {1, 2, . . . , C}.
Définition 12.6 (Indice de Rand) On appelle indice de Rand la proportion de paires d’observations qui
sont soit de même classe et dans le même cluster, soit de classe différente et dans deux clusters différents :
n X
n
2 X    
RI = δ k(~x i ) = k(~x l ) δ(y i = y l ) + δ k(~x i ) 6= k(~x l ) δ(y i 6= y l ).
n(n − 1)
i=1 l=i+1

En bioinformatique, où il est souvent délicat d’étiqueter les objets d’étude par manque de connais-
sances, il est fréquent d’évaluer un clustering en le comparant à une ontologie, c’est-à-dire une classifica-
tion d’objets (par exemple, des gènes) en catégories décrites par un vocabulaire commun et organisées de
manière hiérarchique. On peut évaluer la cohérence d’un clustering avec une ontologie par une analyse
d’enrichissement, qui consiste à évaluer s’il y a plus d’objets d’une catégorie de l’ontologie au sein d’un clus-
ter que ce à quoi on pourrait s’attendre par hasard. Si l’on suppose les données issues d’une distribution
hypergéométrique, il s’agit alors de calculer, pour un cluster Ck , une catégorie G, et un seuil t ∈ N,
|G| n−|G|



t
s |Ck |−s
X
P[|G ∩ Ck | ≥ t] = 1 − n

. (12.1)
s=1 |Ck |

En effet, le terme sous la somme est la probabilité que, lorsqu’on tire |Ck | éléments parmi n, s d’entre eux
appartiennent à G.
Muni de ces différentes façons d’évaluer un algorithme de partitionnement de données, nous pouvons
maintenant découvrir ces algorithmes eux-mêmes. Ces algorithmes cherchent à optimiser les critères d’ho-
mogénéité et de séparabilité que nous venons de définir. Comme il n’est pas possible de le faire de manière
exacte, il s’agit de le faire de manière approchée. Nous nous concentrerons dans ce chapitre sur les trois
principales familles d’algorithmes de clustering : clustering hiérarchique, clustering par centroïdes, et clus-
tering par densité.
12.3. Clustering hiérarchique 153

12.3 Clustering hiérarchique

Le clustering hiérarchique forme des clusters séparés par récurrence : il s’agit de partitionner les données
pour toutes les échelles possibles de taille de partition, dans une hiérarchie à plusieurs niveaux.

12.3.1 Dendrogramme

Le résultat d’un clustering hiérarchique peut se visualiser sous la forme d’un dendrogramme. Il s’agit d’un
arbre dont les n feuilles correspondent chacune à une observation. Chaque nœud de l’arbre correspond à
un cluster :
— la racine est un cluster contenant toutes les observations
— chaque feuille est un cluster contenant une observation
— les clusters ayant le même parent sont agglomérés en un seul cluster au niveau au-dessus
— un cluster est subdivisé en ses enfants au niveau au-dessous.
Ce sont donc les nœuds intermédiaires qui nous intéresseront le plus.
Enfin, la longueur d’une branche de l’arbre est proportionnelle à la distance entre les deux clusters
qu’elle connecte.
La figure 12.3 représente un exemple de dendrogramme. Dans le cas où n est trop grand pour repré-
senter l’intégralité de l’arbre, il est classique de le couper et de n’en représenter que la partie de la racine
à un niveau que l’on choisit.

Figure 12.3 – Un exemple de dendrogramme. En coupant au niveau de la ligne en pointillés, on obtient 3

clusters. Chaque feuille de l’arbre (sur l’axe des abscisses) correspond à une observation.

Cette facilité à représenter visuellement le résultat d’un algorithme de clustering hiérarchique fait qu’il
est très utilisé dans des domaines comme la bioinformatique.
154 Chapitre 12. Clustering

12.3.2 Construction agglomérative ou divisive

Un clustering hiérarchique peut se construire de manière agglomérative ou divisive.
Le clustering agglomératif, ou bottom-up clustering, commence par considérer les feuilles du dendrogramme :
initialement, chaque observation forme un cluster de taille 1. À chaque itération de l’algorithme, on trouve
les deux clusters les plus proches, et on les agglomère en un seul cluster, et ce jusqu’à ne plus avoir qu’un
unique cluster contenant les n observations.
Le clustering divisif, ou top-down clustering, est l’approche inverse. On l’initialise en considérant un seul
cluster, la racine du dendrogramme, contenant toutes les observations. À chaque itération, on sépare un
cluster en deux, jusqu’à ce que chaque cluster ne contienne plus qu’une seule observation.
Par la suite, nous nous concentrerons sur l’approche agglomérative.

12.3.3 Fonctions de lien

Déterminer les deux clusters les plus proches afin de les agglomérer requiert de définir une distance
entre clusters ; c’est ce qu’on appelle dans le cadre du clustering une fonction de lien, ou linkage en anglais.
Plusieurs approches sont possibles, qui reposent toutes sur une distance d sur X .
Tout d’abord, on peut choisir d’agglomérer deux clusters si deux de leurs éléments sont proches. On
utilise alors le lien simple.

Définition 12.7 (Lien simple) On appelle lien simple, ou single linkage, la distance entre deux clusters
définie par
dsimple (Ck , Cl ) = min d(~u, ~v ).
u,~v )∈Ck ×Cl
(~

On peut aussi choisir d’agglomérer deux clusters si tous leurs éléments sont proches. On utilise alors le
lien complet, qui est la distance maximale entre un élément du premier cluster et un élément du deuxième.

Définition 12.8 (Lien complet) On appelle lien complet, ou complete linkage, la distance entre deux
clusters définie par
dcomplet (Ck , Cl ) = max d(~u, ~v ).
u,~v )∈Ck ×Cl
(~

Une approche intermédiaire consiste à considérer la distance moyenne entre un élément du premier
cluster et un élément du deuxième. C’est le lien moyen.

Définition 12.9 (Lien moyen) On appelle lien moyen, ou average linkage, la distance entre deux clusters
définie par
1 1 X X
dmoyen (Ck , Cl ) = d(~u, ~v ).
|Ck | |Cl |
u∈Ck ~v ∈Cl
~

Cette distance est aussi parfois appelée UPGMA pour Unweighted Paired Group Method with Arithmetic mean. 

Une alternative au lien moyen est le lien centroïdal, qui considère la distance entre les centroïdes des
clusters.
12.3. Clustering hiérarchique 155

Définition 12.10 (Lien centroïdal) On appelle lien centroïdal, ou centroid linkage, la distance entre deux
clusters définie par
 
1 X 1 X
dcentroidal (Ck , Cl ) = d  ~u, ~v  = d(~
µk , µ
~ l ).
|Ck | |Cl |
u∈Ck
~ ~v ∈Cl

Cette distance est aussi parfois appelée UPGMC pour Unweighted Paired Group Method with Centroid. 

Les fonctions de lien ci-dessus s’attachent à garantir la séparabilité des clusters. À l’inverse, il est possible
1 P
de chercher à maximiser leur homogénéité : il s’agit de minimiser Tk = |Ck | ~x∈Ck d(~x, µ ~ k ). Dans le cas où d
1 P
est la distance euclidienne, alors Tk = |Ck | ~x∈Ck ||~x − µ ~ k ||2 . Le clustering de Ward utilise une formulation
similaire : il s’agit d’agglomérer deux clusters de sorte à minimiser la variance intra-cluster du résultat.

Définition 12.11 (Inertie) On appelle variance intra-cluster, ou inertie du cluster C la valeur

1 X
Varin (C) = ~ ||22 .
||~x − µ
|C|
x∈C
~

L’inertie globale d’un clustering de D est alors donnée par la somme des inerties des clusters :

K
X 1 X
V = ~ k ||22 .
||~x − µ
|Ck |
k=1 x∈Ck
~

12.3.4 Choix du nombre de clusters

Le clustering hiérarchique a l’avantage de ne pas requérir de définir à l’avance le nombre de clusters,
ce qui permet d’explorer toutes les possibilités le long du dendrogramme. Cependant, il faut généralement
prendre cette décision à un moment.
Il est possible pour cela d’utiliser un dendrogramme, pour y déceler un « niveau » auquel les clusters
sont clairement distants les uns des autres – on se rappellera que la longueur d’une branche est propor-
tionnelle à la distance entre les deux clusters qu’elle sépare.
Une solution alternative est d’évaluer les différentes partitions trouvées, c’est-à-dire les différents nœuds
du dendrogramme, à l’aide d’une mesure de performance telle que le coefficient de silhouette.

12.3.5 Complexité algorithmique

La complexité algorithmique du clustering hiérarchique est élevée : à chaque itération, pour décider
quels clusters regrouper, il nous faudra calculer les distances deux à deux entre toutes les paires d’obser-
vations du jeu de données, pour une complexité en O(pn2 ). Une alternative est de stocker ces distances en
mémoire pour pouvoir les réutiliser, ce qui a une complexité quadratique en le nombre d’observations.
Le clustering hiérarchique est donc plus adapté aux jeux de données contenant peu d’échantillons.
156 Chapitre 12. Clustering

12.4 Méthode des k-moyennes

Plutôt que d’explorer toutes les partitions possibles à différentes échelles, il peut être préférable de se
fixer un nombre K de clusters, ce qui permet de réduire les temps de calculs.
Nous avons vu ci-dessus que le clustering de Ward cherche à minimiser la variance intra-cluster afin
de créer des clusters homogènes. La méthode dite des k-moyennes, ou du k-means, proposée par Hugo Stein-
haus (1957), cherche à résoudre ce problème pour un nombre de clusters K fixé. Il s’agit alors de trouver
l’affectation des observations à K clusters qui minimise la variance intra-cluster globale :
K X
X
arg min ~ k ||22 .
||~x − µ (12.2)
C1 ,C2 ,...,CK k=1
x∈Ck
~

Cependant, résoudre ce problème de manière exacte n’est pas possible. On utilise donc une heuristique,
l’algorithme de Lloyd, proposé par Stuart Lloyd (1982).

12.4.1 Algorithme de Lloyd

Définition 12.12 (Algorithme de Lloyd) Étant données n observations dans Rp et un nombre K de
clusters, l’algorithme de Lloyd procède de la manière suivante :
1. Choisir K observations µ
~ 1, µ
~ 2, . . . , µ
~ K parmi les n observations, pour servir de centroïdes initiaux ;
2. Affecter chaque observation ~x i ∈ D au centroïde dont elle est le plus proche :

k(~x i ) = arg min ~x i − µ

~k 2
;
k=1,...,K

3. Recalculer les centroïdes de chaque cluster :

1 X i
µ
~k = ~x ;
|Ck | i
x ∈Ck
~

4. Répéter les opérations 2–3 jusqu’à convergence, c’est-à-dire jusqu’à ce que les affectations ne changent
plus.


L’algorithme de Lloyd implémente une stratégie gloutonne, et s’il converge en général très rapidement,
il peut tomber dans un minimum local. Il peut donc être pertinent de le faire tourner plusieurs fois, et de
garder la solution qui a la plus faible variance intra-cluster.
Si l’on doit itérer t fois l’algorithme de Lloyd, sachant que le coût de calculer Kn distances en p dimen-
sions est de l’ordre de O(npK), la complexité algorithmique de l’algorithme de Lloyd est en O(npKt). K
et t sont typiquement négligeables devant n, et cet algorithme est donc linéaire en le nombre d’observa-
tions, par opposition au clustering hiérarchique dont le coût est quadratique en n : nous avons remplacé le
calcul des distances d’une observation ~x i aux n − 1 autres points du jeu de données par un calcul de sa
distance à K centroïdes.

12.4.2 Forme des clusters

D’après la formulation de l’algorithme des k-moyennes (équation 12.2), chaque cluster Ck est constitué
des observations de D qui sont les plus proches du centroïde µ ~ k . Ils forment donc un diagramme de Voronoï
(cf. section 8.1.2). En particulier, cela signifie que les clusters trouvés par l’algorithme des k-moyennes sont
nécessairement convexes.
12.4. Méthode des k-moyennes 157

Données aberrantes
L’algorithme du k-means est sensible aux données aberrantes : elles vont en effet tirer un cluster à elle.
Si une observation ~x i est très éloignée des autres observations, alors elle se retrouvera dans son propre
cluster, tandis que le reste des données sera partitionné en K − 1 clusters.
Cette propriété est néanmoins intéressante, car elle permet d’utiliser l’algorithme des k-moyennes jus-
tement pour détecter les observations aberrantes : ce sont celles qui sont seules dans leur cluster.

12.4.3 Variantes
k-means++
L’algorithme du k-means est stochastique : on peut obtenir des résultats différents selon l’initialisation,
et certains de ces résultats peuvent avoir une inertie bien plus grande que la solution optimale.
Pour éviter ce problème, l’algorithme k-means++ commence par initialiser les centroïdes de manière à
les disperser au maximum parmi les données. Plus précisément, la procédure consiste à
1. Choisir un premier centroïde ~u 1 aléatoirement parmi les observations D
2. Pour k = 2, . . . , K :
Choisir le k-ème centroïde ~u k parmi D \ ~u k−1 , en suivant une loi proportionnelle au carré de la
distance à ~u k−1 , c’est-à-dire que ~u k aura de fortes chances d’être éloigné de ~u k−1 .
Cette approche ne rend pas le k-means déterministe, mais permet d’éviter les « pires » solutions.

Méthode des k-moyennes avec noyau

La méthode des k-moyennes requiert de décrire les données dans un espace euclidien, et ne peut for-
mer que des clusters convexes, ce qui peut être limitant. Cependant, l’astuce du noyau (cf. section 10.3.3)
s’applique à l’algorithme de Lloyd.
Démonstration. Soit κ : X × X 7→ R un noyau. Il existe un espace de Hilbert H et une application
φ : X → H telle que, pour tout ~x, ~x0 ∈ X × X , κ(~x, ~x0 ) = hφ(~x), φ(~x0 )iH .
Pour appliquer l’algorithme de Lloyd aux images {φ(~x 1 ), φ(~x 2 ), . . . , φ(~x n )} des éléments de D dans
H, nous avons besoin de calculer, à chaque itération, la distance de φ(~x i ) à chacun des K centroïdes
~h1 , ~h2 , . . . , ~hK .
La position d’un centroïde ~hk se calcule comme la moyenne des images des observations appartenant
à Ck :
~hk = 1
X
φ(~x i ).
|Ck | i
x ∈Ck
~

La distance de l’image d’une observation ~x i à un centroïde se calcule alors comme

2
2 1 X
φ(~x i ) − ~hk = φ(~x i ) − φ(~u)
2 |Ck |
u∈Ck
~ 2
* +
i 1 X
i 1 X
= φ(~x ) − φ(~u), φ(~x ) − φ(~u)
|Ck | |Ck |
u∈Ck
~ u∈Ck
~ H
2 X 1 X X
= κ(~x i , ~x i ) − κ(~u, ~x i ) + κ(~u, ~v ).
|Ck | |Ck |2
u∈Ck
~ u∈Ck ~v ∈Ck
~

On peut ainsi réécrire l’étape (2) de l’algorithme de Lloyd sans faire appel à l’application φ, et sans avoir
besoin de recalculer explicitement les centroïdes à l’étape (3). 
158 Chapitre 12. Clustering

Remarque
La version à noyau de la méthode des k-moyennes ne permet généralement pas de connaître les cen-
troïdes des clusters, puisqu’ils vivent dans l’espace de redescription H qui n’est pas accessible sans connaître
φ.

12.5 Clustering par densité

Une autre façon d’obtenir des clusters non convexes est le clustering par densité. Prenons l’exemple
présenté sur la figure 12.4 : il semblerait naturel de partitionner les données en 3 cercles concentriques, ce
que ni le clustering agglomératif ni la méthode des k-moyennes n’arrivent à faire, car ces clusters ne sont
pas convexes.

(a) Il nous semble naturel de par- (b) Partitionnement en 3 clusters (c) Partitionnement en 3 clusters
titionner ces données en 3 cercles par clustering agglomératif (lien par k-moyennes.
concentriques. moyen).

Figure 12.4 – Motivation du clustering par densité.

C’est le problème que le clustering par densité cherche à résoudre, en observant que les points les plus
proches d’un point donné sont sur le même cercle et non sur un autre cercle. Il s’agit de former des clusters
d’observations proches les unes des autres, au sens où si deux éléments ~x i et ~x l d’un même cluster Ck
peuvent être éloignés l’un de l’autre, il existe une séquence d’éléments ~u 1 , ~u 2 , . . . , ~u m ∈ Ck tels que ~u 1
est proche de ~x i , ~u m est proche de ~x l , et pour tout t ∈ {1, . . . , m}, ~u t est proche de ~u t−1 . Cette idée est
illustrée sur la figure 12.5
Pour formaliser cette idée, nous allons avoir besoin de quelques définitions.
Définition 12.13 (-voisinage) Soient D = {~x 1 , ~x 2 , . . . , ~x n } le jeu d’éléments de X à partitionner, d
une distance sur X , et  > 0. On appelle -voisinage d’un élément ~x ∈ X l’ensemble des observations de D
dont la distance à ~x est inférieure à  :

N (~x) = {~u ∈ D : d(~x, ~u) < }.

Définition 12.14 (Point intérieur) Étant donné nmin ∈ N, on dit de ~x ∈ X qu’il est un point intérieur,
ou core point en anglais, si son -voisinage contient au moins nmin éléments : |N (~x)| ≥ nmin . 
12.5. Clustering par densité 159

Figure 12.5 – Il existe un chemin entre voisins proches permettant de passer d’un point à un autre du même
cluster.

Définition 12.15 (Connexion par densité) On dit que ~x et ~v ∈ X sont connectés par densité si l’on
peut les « relier » par une suite d’-voisinages contenant chacun au moins nmin éléments. Formellement,
cela signifie qu’il existe m ∈ N, et une séquence ~u 1 , ~u 2 , . . . , ~u m d’éléments de D tels que ~u 1 est un point
intérieur de N (~x), ~u 2 est un point intérieur de N (~u 1 ), . . . , ~u m est un point intérieur de N (~u m−1 ), ~v
est un point intérieur de N (~u m ). 

L’algorithme DBSCAN, proposé en 1996 par Martin Ester, Hans-Peter Kriegel, Jörg Sander et Xiaowei
Xu (Ester et al., 1996), partitionne les données en créant des clusters de points atteignables par densité les
uns depuis les autres. C’est un algorithme de partitionnement populaire, qui a obtenu en 2014 une distinc-
tion de contribution scientifique ayant résisté à l’épreuve du temps, le test of time award de la prestigieuse
conférence KDD.
Définition 12.16 (DBSCAN) On appelle DBSCAN, pour Density-Based Spatial Clustering of Applications with
Noise, ou partitionnement dans l’espace par densité pour des applications bruitées, la procédure de parti-
tionnement suivante :
— Initialisation : Un ensemble d’éléments visités V = ∅, une liste de clusters K = ∅, une liste d’obser-
vations aberrantes A = ∅.
— Pour chaque élément ~x ∈ D \ V :
1. Construire N (~x)
2. Si |N (~x)| < nmin : considérer (temporairement) ~x comme une observation aberrante :

A ← A ∪ {~x}

Sinon :
— créer un cluster C ← {~x}
— augmenter ce cluster par la procédure grow_cluster(C, N (~x), , nmin )
3. Ajouter C à la liste des clusters : K ← K ∪ C
160 Chapitre 12. Clustering

4. Marquer tous les éléments de C comme visités : V ← V ∪ C.

La procédure grow_cluster(C, N , , nmin ) est définie comme suit :
Pour tout ~u ∈ N \ V :
— créer N 0 ← N (~u)
— si |N 0 | ≥ nmin : actualiser N de sorte à prendre les éléments de N 0 en considération : N ←
N ∪ N0
— si ~u n’appartient à aucun autre cluster, l’ajouter à C : C ← C ∪ {~u}
— si ~u était précédemment cataloguée comme aberrante, l’enlever de la liste des observations aber-
rantes : A = A \ {~u}.


Un des avantages de DBSCAN est sa robustesse aux données aberrantes, qui sont identifiées lors de la
formation des clusters.
Le fléau de la dimension (voir section 11.1.3) rend DBSCAN difficile à appliquer en très grande dimen-
sion : les -voisinages auront tendance à ne contenir que leur centre. De plus, la densité étant définie par les
paramètres  et nmin , DBSCAN ne pourra pas trouver de clusters de densité différente. Cependant, DBSCAN
ne requiert pas de prédéfinir le nombre de clusters, et est efficace en temps de calcul. Son application aux
données de la figure 12.4a est illustrée sur la figure 12.6.

Figure 12.6 – Partitionnement des données de la figure 12.4a par DBSCAN.

Points clefs
— Le clustering, ou partitionnement de données, cherche à identifier des classes sans utiliser d’éti-
quettes.
— En l’absence d’étiquette, la qualité d’une partition peut s’évaluer sur des critères de séparabilité et
d’homogénéité
 161

— Le clustering hiérarchique partitionne les données de manière itérative. Son résultat peut être vi-
sualisé sur un dendrogramme.
— Le clustering par la méthode des k-moyennes s’effectue grâce à l’algorithme de Lloyd ou une de ses
variantes. Il permet de trouver efficacement K clusters convexes.
— La version à noyau de la méthode des k-moyennes permet de l’appliquer pour découvrir des clusters
non convexes.
— Le clustering par densité permet d’identifier des régions denses du jeu de données, c’est-à-dire
des observations qui peuvent former un ensemble non convexe mais qui sont proches les unes des
autres.

Pour aller plus loin

• Les algorithmes de partitionnement que nous avons vus associent un seul et unique cluster à chaque
observation. Il existe des variantes, appelées partitionnement flou, ou fuzzy clustering en anglais, qui
associent à chaque observation et chaque cluster la probabilité que cette observation appartienne à
ce cluster.
• L’ouvrage de Jain et Dubes (1988) constitue une bonne introduction au clustering. On pourra aussi
se reporter à l’article de Xu et Wunsch II (2005)

Bibliographie

Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. (1996). A density-based algorithm for discovering clusters
in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge
Discovery and Data Mining, pages 226–231, Portland (OR). AAAI Press.

Jain, A. K. and Dubes, R. C. (1988). Algorithms for Clustering Data. Prentice Hall, New York.

Lloyd, S. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2) :129–137.

Steinhaus, H. (1957). Sur la division des corps matériels en parties. Bulletin de l’Académie polonaise des Sciences,
4(12) :801–804.

Xu, R. and Wunsch II, D. (2005). Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16 :645–
678.