Classification non supervise
Data Mining
Principes
Mthodes par partitionnement
Mthodes hirarchiques
Master 2
UAG
Classification non supervise
Principes
Mthodes par partitionnement
Mthodes hirarchiques
Classification non supervise
Classification (non supervise) (en : clustering)
tche de description
recherche des groupes (clusters) dans un ensemble de donnes
avec la plus grande similarit possible intra-groupe
et la plus grande dissimilarit possible inter-groupes
Classement ou Classification supervise (en : classification)
tche de prdiction
prdit des variables catgorielles
construit un modle de classement (classifieur) des donnes
en se basant sur un ensemble appel
ensemble d'apprentissage (EA) (training set)
utilise le modle pour classer de nouvelles donnes
Classification non supervise :
Apprentissage non supervis
Classification non supervise
Exemples
recherche de classes d'objets dans un ensemble de
donnes
classe (cluster) : ensemble d'objets similaires entre
elles et dissimilaires des objets d'autres classes
doit permettre de dcouvrir des modles cachs
utilise en Machine learning, Data mining, Analyse de
donnes
en Data Mining : intervient comme pr-tape d'analyse
des donnes
Mthodes de classification
exclusives ou non exclusives
hirarchiques ou non
hirarchiques ascendantes ou descendantes
pour donnes numriques et symboliques
dterministes vs. probabilistes
Modles rsultants
Evaluation du rsultat
Qu'est-ce qu'un "bon clustering"?
Critres de qualit des clusters :
grande similarit intra cluster
faible similarit inter-clusters
1
a
0.4
b
0.1
c
0.3
d
0.1
e
0.4
f
0.1
g
0.7
h
0.5
0.1
0.8
0.3
0.1
0.2
0.4
0.2
0.4
0.5
0.1
0.4
0.8
0.4
0.5
0.1
0.1
Types de donnes classifier
numriques continues
catgorielles binaires
catgorielles nominales
qualit du rsultat dpendante de la mesure de
similarit
Variables continues
standardisation
Ecart moyen absolu
avec
catgorielles ordinales
mesure standardise
Variables continues
Variables continues
Distances entre objets i = (xi1, xi2, , xip) et j = (xj1, xj2, , xjp)
q = 2, d distance euclidienne
distance de Minkowski
proprits en gnral vrifies
d(i,j) 0
d(i,i) = 0
q = 1 distance de Manhattan
d(i,j) = d(j,i)
d(i,j) d(i,k) + d(k,j)
Variables binaires
Variables nominales
Object j
Table de contingence
Object i
valeurs discrtes, gnralisent le cas des variables
binaires
mesure de correspondance simple
variable symtrique : coeff de correspondance simple
p=nombre de variables
m=nombre de valeurs communes sur i et j
variable assymtrique :
coefficient de Jaccard
Variables ordinales
valeurs ordonnes
Donnes mixtes
Variables de types diffrents : Mesures pondres
toute valeur d'une variable x est remplace par son rang
dans la liste des valeurs
les valeurs obtenues sont normalises :
ij(x) =0 si valxi ou valxj est manquant, sinon ij(x) =1
x binaire ou nominale:
dij(x) = 0 if valxi = valxj , sinon dij(x) = 1
x continue : distance normalise
distance pour variables continues
x ordinale : calcul du rang et distance pour var.
continue
Clustering en Data mining
Types de mthodes
Doit permettre
par partitionnement
le passage l'chelle
construisent diffrentes partitions, puis les valuent selon
certains critres
de traiter diffrents types d'attributs
hirarchiques
d'tre robuste au bruit et aux dviations
construisent une organisation hirarchique des objets
bases sur la densit
de donner des rsultats interprtables
utilisent des fonctions de densit et de connectivit
bases sur un modle
le meilleur modle de structure est recherch pour chaque
cluster
Classification non supervise
Principes
Mthodes par partitionnement
Mthodes hirarchiques
Mthode des K-moyennes
(en : K-means)
Mthodes par partitionnement
Principe : construire une partition de l'ensemble des donnes
en k parties dont chacune reprsente une classe
Mthode :
pas initial : cration d'une partition initiale
puis
itration d'un processus de replacement qui optimise le
partitionnement en dplaant les objets d'une classe
l'autre
K-moyennes : exemples
slectionner alatoirement K objets pour
tre les centrodes des cluster initiaux
itrer
assigner chaque objet x au cluster dont
le centrode est le plus proche de x
pour chaque cluster C, recalculer son
centroide comme moyenne (arithmtique) des
objets de C
jusqu' ce que les clusters soient stables
10
10
0
0
10
0
0
10
K-moyennes : exemples (2)
K-moyennes : exemple (3)
dist(3,M2)<dist(3,M3)3 passe dans C2
C1={1}, M1=1, C2={2,3}, M2=2.5,C3={6,7,8,13,15,17} et M3=
66/6=11
A={1,2,3,6,7,8,13,15,17}.
K= 3
Centroides initiaux : 1, 2, 3
dist(6,M2)<dist(6,M3)6 passe dans C2
C1={1}, M1=1, C2={2,3,6}, M2=11/3=3.67, C3={7,8,13,15,17},
M3= 12
Clusters initiaux
C1={1}, M1=1,
C2={2}, M2=2
C3={3, 6,7,8,13,15,17}, M3=69/7=9.86
dist(2,M1)<dist(2,M2)2 passe en C1
dist(7,M2)<dist(7,M3) 7 passe en C2
C1={1,2}, M1=1.5, C2={3,6,7}, M2=5.34, C3= {8,13,15,17},
M3=13.25
dist(3,M1)<dist(3,M2)3 passe en 1
dist(8,M2)<dist(8,M3)8 passe en 2
C1={1,2,3}, M1=2, C2={6,7,8}, M2=7, C3={13,15,17}, M3=15
K-moyennes : fonction objectif
Dans l'exemple prcdent :
Fonction minimiser
K-moyennes : avantages/
inconvnients
+
assez rapide : en O(l*k*n) avec l nombre d'itrations
n nombre d'objets classer k nombre de clusters
Trouve des minima locaux
pour donnes numriques
sensible au bruit, adapt des clusters convexes
le nombre K doit tre spcifi
K-moyennes : Variantes
Minima locaux
Resultat trs dpendant du choix des premiers
paramtres
Pb des minima locaux
K-modes
K-mdoides : PAM
initial cluster
centers
selection automatique des K classes initiales
instances
EM (Expectation Maximization) : un objet est affect
une classe selon un poids qui reprsente sa probabilit
d'appartenance la classe
K-modes (Huang 98)
Le mode remplace la moyenne pour les attributs
catgoriels
Nouvelle fonction de similarit entre objets
K-medoides
K-medoides
Moyenne de 1, 3, 5, 7, 9 : 5
Moyenne de 1, 3, 5, 7, 1009 : 205
Mediane de 1, 3, 5, 7, 1009 is 5
Les valeurs extremes naffectent pas la mdiane
Mthode k-prototype pour la cas d'attributs
numriques et catgoriels
Partitioning around Medoids(PAM)
PAM ( Kaufman and Rousseeuw 1987)
Mdoide objet d'un cluster dont le dissimilarit avec les autres
objets du cluster est minimal
-un objet x est plac dans le cluster Ci s'il est plus prt de son
mdoide que de tout autre
-PAM minimise la fonctions objectif somme des dissimilarits de
tous les objets avec le mdoide le plus proche
K medoides, M = (m1, . . . ,mK)
PAM : Exemple
A={1,3,4,5,8,9}
k=2 1 et 8 mdoides initiaux
Clusters initiaux C1={1,3,4} et C2={5,8,9}
E{1,8}=dist(3,1)2+dist(4,1)2+dist(5,8)2+dist(9,8)2=15
Comparons 1 et 3, si 3 remplace 1 : C1={1,3,4,5} et C2={8,9}
E{3,8} =dist(1,3)2+dist(4,3)2+dist(5,3)2+dist(9,8)2=10
le remplacement est fait M={3,8}
Comparons 3 et 4, si 4 remplace 3 : C1={1,3,4,5} et C2={8,9}
E{4,8}=dist(1,4)2+dist(3,4)2+dist(5,4)2+dist(8,9)2= 12
3 nest pas remplac par 4
Comparons 3 et 5, si 5 remplace 1 : C1={1,3,4,5} et C2={8,9}
E{5,8}=dist(1,5)2+dist(3,5)2+dist(4,5)2+dist(8,9)2= 22
3 nest pas remplac par 5
Comparons 3 et 9, si 9 remplace 1 : C1={1,3,4,5,8} et C2={9}
E{9,8}=dist(1,8)2+dist(3,8)2+dist(4,8)2+dist(5,8)2>49
3 nest pas remplac par 9
slectionner K objets alatoirement comme mdoides
initiaux
itrer
affecter chaque objet restant au medoide le plus
proche
Choisir alatoirement un non-medoide Or
Pour chaque medoide Oj, Calculer le cot TC du
remplacement de Oj par Or
Si TC < 0 alors
Remplacer Oj par Or
Calculer les nouveaux clusters
jusqu' ce que les clusters soient stables
PAM : Exemple
Clusters C1={1,3,4,5} et C2={8,9}
E{3,8} =dist(1,3)2+dist(4,3)2+dist(5,3)2+dist(9,8)2=10
Comparons 8 et 1, si 1 remplace 8 : C1={1} et C2={8,9,3,4,5}
E{3,1} =dist(8,3)2+dist(9,3)2+dist(4,3)2+dist(5,3)2>25
8 nest pas remplac par 1
Comparons 8 et 4, si 4 remplace 8 : C1={1,3} et C2={8,9,4,5}
E{3,4}=dist(3,1)2+dist(4,8)2+dist(4,9)2+dist(4,5)2>25
8 nest pas remplac par 4
Comparons 8 et 5, si 5 remplace 8 : C1={1,3,4} et C2={5,8,9}
E{3,5}=dist(3,1)2+dist(3,4)2+dist(5,8)2+dist(5,9)2= 15
8 nest pas remplac par 5
Comparons 8 et 9, si 9 remplace 1 : C1={1,3,4,5} et C2={9,8}
E{3,9}=dist(1,3)2+dist(4,3)2+dist(5,3)2+dist(9,8)2=10
8 nest pas remplac
Clusters rsultats C1={1,3,4,5} et C2={8,9}
PAM Silhouette plot
Silhouette plots
reprsentation graphique
permette de slectionner le nombre de clusters
Silhouette de l'observation i
ai moyenne des distances entre i et les autres points de son
cluster
bi distance moyenne minimum entre i et les autres clusters
les objets large silhouette sont bien classs
Expectation-maximization (EM)
Classification non supervise
Au lieu d'affecter chaque objet un cluster en
maximisant les distances entre clusters, EM calcule
les probabilits d'appartenance aux clusters
Principes
Objectif : estimer moyenne et ecart-type pour chaque
cluster de manire maximiser la probabilit
globale d'appartenance des objets aux clusters
finaux
Mthodes hirarchiques
Mthodes par partitionnement
Dtermine automatiquement le nombre de clusters
Mthodes hirarchiques
par agglomration (ascendante)
pas initial : chaque lment forme une classe
puis, chaque itration, les objets les plus proches
sont groups dans la mme classe
jusqu' ce que toutes les classes soient regroupes
en une seule
par division (descendante)
pas initial : tous les lments sont dans la mme
classe
puis, chaque itration, les classes sont clates
jusqu' ce que chaque lment soit dans une classe
Mthodes hirarchiques
Deux types :
Agglomeratives bottom-up
Divisives top-down
Ne ncessitent pas de spcifier k
Produisent un arbre appel dendrogramme
les clusters sont obtenus en coupent l'arbre un niveau
donn
le dendrogramme montre la formation des clusters et sousclusters
Classification hierarchique
pas 0
a
b
pas 1
pas 2
pas 4
agglomeration
ab
abcde
cde
de
e
pas 4
pas 3
Classification hierarchique
division
pas 3
pas 2
pas 1
pas 0
Mthodes agglomeratives
Algorithme d'agglomration
Algorithme pour N objets classifier
Dmarre avec N clusters
chaque tape, fusionne deux clusters les plus proches
en utilisant une mesure de distance entre clusters
Jusqu' ce qu'il y ait un seul cluster
distances entre clusters
Single linkage
Complete linkage
Average linkage
Centroid linkage
Ward
distance
distance
distance
distance
distance
pour chaque instance x, Cx={x}
tant qu'il y a plus d'un cluster
minimum
maximum
moyenne
entre les centroides
euclidienne pondre entre
etant donns Cx et Cy des clusters
qui minimisent d(Ci,Cj)
Cx=Cx Cy
supprimer Cy
moyennes
Distance between clusters
Single Link: smallest distance between points
Complete Link: largest distance between points
Average Link: average distance between points
Centroid: distance between centroids
Classification hierarchique
conceptuelle COBWEB
Classification hierarchique
conceptuelle COBWEB
adaptee a des attributs categoriels
effectue une classification conceptuelle par arbre de
dcision
identifie des classes
et en donne une description (2 tapes)
dmarre la racine
insre les instances une une
met jour l'arbre chaque tape
chaque tape, 4 actions sont possibles :
fusionner deux noeuds, clater un noeud, crer un
noeud, crer un sous-noeud
optimiser l'indice Category utility
chaque nud
reprsente un concept et contient une description
probabiliste de celui-ci
la description caractrise les objets classs dans ce
nud : probabilit du concept et probabilits
conditionnelles sur les valeurs des attributs
les nuds frres dun niveau forment une partition
Clustering weather data
1
ID
Outlook
Temp.
Humidity
Windy
Sunny
Hot
High
False
Sunny
Hot
High
True
ID
Outlook
Temp.
Humidity
Windy
Sunny
Hot
High
False
Sunny
Hot
High
True
Overcast
Hot
High
False
Rainy
Mild
High
False
Rainy
Cool
Normal
False
Overcast
Hot
High
False
Rainy
Mild
High
False
Rainy
Cool
Normal
True
Rainy
Cool
Normal
False
Overcast
Cool
Normal
True
True
Sunny
Mild
High
False
Sunny
Cool
Normal
False
Rainy
Mild
Normal
False
Sunny
Mild
Normal
True
Overcast
Mild
High
True
Overcast
Hot
Normal
False
Rainy
Mild
High
True
Rainy
Cool
Normal
Overcast
Cool
Normal
True
Sunny
Mild
High
False
Sunny
Cool
Normal
False
Rainy
Mild
Normal
False
Sunny
Mild
Normal
True
Overcast
Mild
High
True
Overcast
Hot
Normal
False
Rainy
Mild
High
True
Autre exemple: IRIS data set
ID
Outlook
Temp.
Humidity
Windy
Sunny
Hot
High
False
Sunny
Hot
High
True
Overcast
Hot
High
False
Rainy
Mild
High
False
a et b sont trs
similaires
avec cutoff
10
