1
Qu’est‐ce que le clustering ?
• analyse
l de
d clustering
l i
regroupement des objets en clusters
• un cluster : une collection d’objets
similaires au sein d’un même cluster
dissimilaires aux objets appartenant à d’autres clusters
• classification non supervisée : pas de classes prédéfinies
• Applications typiques
afin de mieux comprendre les données
comme prétraitement avant d’autres analyses
2
Qu’est‐ce qu’un bon clustering ?
• Une bonne méthode
é va produire des clusters dont
les éléments ont
une forte similarité intra‐classe
une faible similarité inter‐classe
• La
L qualité
lité d’un
d’ clustering
l t i dépend
dé d de
d la
l mesure de
d
similarité
• La qualité d’une méthode peut aussi être mesurée
par sa capacitéé à trouver quelques
l ou tous les
l
motifs intéressants
3
Caractéristiques des méthodes de clustering
• Mise à l’échelle
Mi l’é h ll
• Capacité à gérer différents types d’attributs
• Découverte de clusters avec des formes arbitraires
• Besoin minimum de connaissances du domaine pour
déterminer les paramètres
• Capacitéé à gérer
é le l bruit
b et les
l exceptions
• Indifférent à l’ordre des données en entrée
• Nombre de dimensions
• Incorporation de contraintes par ll’utilisateur
utilisateur
• Interprétabilité et utilisabilité
4
Structure de données
• Matrice de données ⎡ x 11 ... x 1f ... x 1p ⎤
⎢ ⎥
⎢ ... ... ... ... ... ⎥
⎢x ... x if ... x ip ⎥
⎢ i1 ⎥
⎢ ... ... ... ... ... ⎥
⎢x ... x nf ... x np ⎥⎥
⎢⎣ n1 ⎦
• M
Matrice
t i ded distance
di t
⎡ 0 ⎤
(ou dissimilarité) ⎢ d(2,1) 0 ⎥
⎢ ⎥
⎢ d(3,1 ) d ( 3,2 ) 0 ⎥
⎢ ⎥
⎢ : : : ⎥
⎣⎢ d ( n ,1) d ( n ,2 ) ... ... 0 ⎥⎦
5
Similarité et dissimilarité
• Mé
Métrique
i d
de similarité/dissimilarité
i il i é/di i il i é : exprimée
i é en termes
d’une fonction de distance, typiquement d(i,j)
• Fonction de distance dépend du type des données : binaires,
nominales, ordinales ou continues
• Pondération des dimensions selon l’application et la
sémantique des données
• Difficulté de définir « suffisamment similaires »
la réponse est très subjective
6
Types de données
• continue sur un intervalle
ex : poids,
poids taille
• binaire
• nominale
ex : couleur
• ordinale
• à échelle variable
ex : croissance optimale des bactéries, durée de
la radioactivité
• Mixte
7
Valeurs continues sur un intervalle, normalisation
• N
Normaliser
li les
l données
d é : s’affranchir
’ ff hi ddes unités
ié d de mesures
• écart absolu à la moyenne
s f = 1n (| x1 f − m f | + | x2 f − m f | +...+ | xnf − m f |)
• Calculer la mesure normalisée (z‐score)
xif − m f
zif = sf
• L’utilisation de l’écart absolu est plus robuste que celle de
ll’écart
écart type
8
Valeurs continues sur un intervalle, Fonction de distance
• Di t
Distance d
de Mi
Minkowski
k ki :
d (i, j) = q (| x − x |q + | x − x |q +...+ | x − x |q )
i1 j1 i2 j2 ip jp
avec i = (xi1, xi2, …, xip) et j = (xj1, xj2, …, xjp) deux objets à p dimensions, et q un
entier positif
• si q = 1 : distance de Manhattan
d(i, j) =| x − x | +| x − x | +...+| x − x |
i1 j1 i2 j2 ip jp
• si q = 2 :distance euclidienne
d (i, j) = (| x − x |2 + | x − x |2 +...+ | x − x |2 )
i1 j1 i2 j2 ip jp
• Propriétés
d(i,i)) = 0
d(
d(i,j) ≥ 0 (positive)
d(i,j) = d(j,i) (symétrique)
d(i,j) ≤ d(i,k) + d(k,j) (inégalité triangulaire)
9
Valeurs binaires
• table de contingence
Objet j
1 0
1 a b
Objet i
0 c d
• coefficient simple d’appariement (invariant, si la
variable est symétrique) b+c
d (i, j ) =
a+b+c+d
• coefficient de Jaccard (non invariant, si la variable
estt asymétrique)
ét i )
d (i, j ) = b+c
a+b+c
10
Dissimilarité de valeurs binaires
• Exemple
E l
N
Nom S
Sexe Fiè
Fièvre T
Tousse T t 1
Test-1 T t 2
Test-2 T t 3
Test-3 T t 4
Test-4
Jacques M O N P N N N
Marie F O N P N P N
Jean M O P N N N N
• sexe est symétrique
• les autres sont asymétriques
• soit O et P = 1, et N = 0
0 +1
d ( jacques , marie ) = = 0 . 33
2 + 0 +1
1+1
d ( jacques , jean ) = = 0 . 67
1+1+1
1+ 2
d ( jean , marie ) = = 0 . 75
1+1+ 2
11
Variables nominales
• généralisation
é é li ti d des valeurs
l bi
binaires
i : plus
l ded 2 états
ét t
• méthode 1 : appariement simple
m : nombre d’appariements, p : nombre total de
variables
i bl
d ( i , j ) = p −p m
• méthode 2 : utiliser un grand nombre de variables
binaires
création d’une variable binaire pour chacun des
ét t d’une
états d’ variable
i bl nominale
i l
12
Variable ordinale
• l’l’ordre
d estt iimportant
t t : rang
• peut être traitée comme une variable continue sur
un intervalle
remplace
l xif par son rang rif ∈ {1,..., M f }
transforme chaqueq variable sur [0,1]
[ , ] en
remplaçant le i‐ième objet de la f‐ième variable
r if − 1
z =
if M f − 1
calcule la dissimilarité en utilisant les méthodes
d valeurs
de l continues
ti sur un intervalle
i t ll
13
à échelle variable
• mesure positive
i i sur une ééchelle
h ll non linéaire,
li é i échelle
é h ll
exponentielle qui suit approximativement AeBT ou Ae‐BT
• Méthodes
les traiter comme des variables continues sur un intervalles : mauvais
choix
appliquer une transformation logarithmique puis les traiter comme
des variables continues sur un intervalle
yiff = log(xiff)
les traiter comme des variables ordinales en traitant leur rangg
14
Variables de type mixte
• Les objets peuvent être
ê décrits
é avec tous les types
de données
binaire symétrique, binaire asymétrique,
nominale, ordinale, …
• Utilisation d’une formule p
pondérée pour
p combiner
leurs effets
Σ p
δ ( f )
d ( f )
d (i, j ) = f = 1 ij ij
Σ p
f = 1
δ ( f )
ij
15
Principales approches
• partitionnement
ii
partitionne les objets et évalue les partitions
• hiérarchique
décomposition hiérarchique d’ensembles
d objets
d’objets
• densité
basée sur une fonction de densité ou de
connectivité
• grille
basée sur une structure de granularité à
plusieurs
l i niveaux
i
16
Partitionnement
• C
Construire
t i une partition
titi de
d la
l base
b de
d données
d é D contenant
t tn
objets en un ensemble de k clusters
• Etant
E donné
d é k,
k trouvéé une partition
i i en k clusters
l quii
optimisent le critère de partitionnement
Optimum
O i global
l b l : traiter
i toutes lesl partitions
ii exhaustivement
h i
Heuristique : k‐means ou k‐médoïdes
k‐means
k : chaque
h cluster
l t estt représenté
é té par son centre
t
k‐médoïdes ou PAM (partition around medoids) : chaque cluster est
représenté par un des objets du cluster
17
k‐means
• 4 étapes
é
1 Partitionne les objets en k ensembles non
1.
vides
2. Calcule le centroïde de chaque
partition/cluster
3. Assigne
g à chaqueq objet j le cluster dont le
centroïde est le plus proche
4. boucle
b l en 2, jusqu’à ’à ce les
l clusters
l soient
stables.
18
k‐means, exemple
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
0 0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
0 0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
19
k‐means. Remarques
• Avantages
Relativement efficace : O(tkn), avec n le nombre d’objets, t le nombre
d’itérations et en ggénéral t et k << n
Termine souvent sur un optimum local. L’optimum global peut être
atteint en utilisant des techniques telles que les algorithmes
génétiques
• Faiblesses
Utilisable seulement lorsque la moyenne est définie.
définie Que faire dans le
cas de données nominales ?
Besoin de spécifier k à l’avance
Ne gère pas le bruit et les exceptions
Ne trouve que des clusters de forme convexe
20
k‐médoïdes
• Trouve des représentants
représentants, appelés médoïdes,
médoïdes dans les
clusters
• PAM
médoïde : l’objet d’un cluster pour lequel la distance moyenne à tous
les autres objets du cluster est minimale
k
critère d’erreur :
E= ∑∑ d ( p, m ) 2
i
• Algorithme i =1 p∈Ci
1. Sélectionner k objets arbitrairement
2. Assigner le reste des objets au médoïde le plus proche
3. Sél ti
Sélectionner un objet
bj t non médoïde
éd ïd ett échanger
é h sii le
l critère
itè d’d’erreur
peut être réduit
4. Répéter
p 2 et 3 jusqu’à
j q ne plusp pouvoir
p réduire le critère d’erreur
21
PAM. Exemple
E’-E<0
E’-E>0
E’-E<0
22
Clustering hiérarchique
• Utilisation d’une matrice de distance : ne nécessite
é
pas de spécifier le nombre de clusters
Step 0 Step 1 Step 2 Step 3 Step 4
agglomerative
((AGNES))
a ab
b abcde
c
cde
d
de
e
sépatative
Step 4 Step 3 Step 2 Step 1 Step 0 (DIANA)
23
AGNES (Agglomerative Nesting)
• Utilise une matrice de dissimilaritéé
• Fusionne les nœuds les moins dissimilaires
10 10 10
9 9 9
8 8 8
7 7 7
6 6 6
5 5 5
4 4 4
3 3 3
2 2 2
1 1 1
0 0 0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
24
Un dendrogramme illustre comment les clusters sont fusionnés hiérarchiquement
• Décompose
é les données
é en plusieurs niveaux
imbriqués de partitionnement
• Un clustering est obtenu en coupant le
dendogramme au niveau choisi
25
Mesures de similarité entre 2 clusters
• complete linkage
plus petite similarité/plus grande distance entre
toutes les paires de gènes entre 2 clusters
• average linkage
similarité
i il ité moyenne entre t les
l paires
i ded gènes
è
• single linkage
plus grande similarité/plus petite distance entre
2 gènes
è de
d 2 clusters
l t
26
Méthodes basées sur la densité
• Principales caractéristiques
Cluster de forme arbitraire
Gestion du bruit
B i d’un
Besoin d’ paramètre
è de d densité
d i é comme critère
iè
d’arrêt p
• 2 paramètres
Eps : rayon maximal de voisinage
q
MinPts : nombre minimal de points dans le voisinage
défini par Eps
• NEps(p) : { q ∈ D | dist(p,q) ≤ Eps} p
• un point p est directement atteignable d
d’un
un point q si
p appartient à NEps(q) p1
|NEps(q)| ≥ MinEps
q
• un point
i p est atteignable
i bl d’un
d’ point
i q sii
il existe une chaîne de points p1, …, pn telle que p1=q et
pn=p et que les pi+1 sont directement atteignables des pi
• un point p est connecté à un point q si p q
il existe un point o tel que p et q sont atteignables
depuis o
o
27
Méthodes basées sur une grille
• U
Utilisation
ili i d’une
d’ grille
ill à des
d résolutions
é l i multiples
l i l comme
structure de données
• L’espace est divisé en cellules rectangulaires
28
Méthodes basées sur une grille
• Chaque cellule de niveau i est divisée en un certain
nombre de cellules plus petites au niveau i+1
• Informations statistiques calculées et stockées à chaque
niveau
• Approche descendante
• Suppression des cellules non pertinentes pour les
ité ti
itérations suivantes
i t
• Répéter le processus jusqu’à atteindre le niveau le plus
bas
• Avantages
parallélisable, mise à jour incrémentale
O(k), où k est le nombre de cellule au p
plus bas niveau
• Faiblesse
les bords des clusters sont soit horizontaux soit
verticaux, pas de diagonale !
Salaary
(10,000)
τ=3
0 1 2 3 4 5 6 7
20
30
40
50
Vacatio
on
60
age
30
Vacaation
(weeek)
50
0 1 2 3 4 5 6 7
20
30
40
age
50
60
age
29
