Questcequeleclustering?

l d l i
1
analysedeclustering
regroupementdesobjetsenclusters
uncluster:unecollectiondobjets
similairesauseindunmmecluster
dissimilairesauxobjetsappartenantdautresclusters
classification non supervise : pas de classes prdfinies classificationnonsupervise:pasdeclassesprdfinies
Applicationstypiques
afindemieuxcomprendrelesdonnes
commeprtraitementavantdautresanalyses
Questcequunbonclustering?

2
Unebonnemthodevaproduiredesclustersdont
les lments ont leslmentsont
unefortesimilaritintraclasse
unefaiblesimilaritinterclasse
L lit d l t i d d d l d Laqualitdunclusteringdpenddelamesurede
similarit
Laqualitdunemthodepeutaussitremesure
l l parsacapacittrouverquelquesoutousles
motifs intressants motifsintressants
Caractristiquesdesmthodesdeclustering
Mi l h ll
3
Miselchelle
Capacitgrerdiffrentstypesdattributs
Dcouvertedeclustersavecdesformesarbitraires
Besoin minimum de connaissances du domaine pour Besoinminimumdeconnaissancesdudomainepour
dterminerlesparamtres
l b l Capacitgrerlebruitetlesexceptions
Indiffrentlordredesdonnesenentre
Nombrededimensions
Incorporation de contraintes par lutilisateur Incorporationdecontraintesparl utilisateur
Interprtabilitetutilisabilit
Structurededonnes
4
Matrice de donnes Matricededonnes

... ... ... ... ...

... ... ... ... ...

np
x ...
nf
x ...
n1
x
... ... ... ... ...
Matricededistance
(ou dissimilarit)

0
(oudissimilarit)

) 2 , 3 ( ) 0 d d(3,1
0 d(2,1)

0 ... ) 2 , ( ) 1 , (
: : :
... n d n d
Similaritetdissimilarit
M i d i il i /di i il i i
5
Mtriquedesimilarit/dissimilarit:exprimeentermes
dunefonctiondedistance,typiquementd(i,j)
Fonctiondedistancedpenddutypedesdonnes:binaires,
nominales,ordinalesoucontinues
Pondrationdesdimensionsselonlapplicationetla
smantique des donnes smantiquedesdonnes
Difficultdedfinir suffisammentsimilaires
larponseesttrssubjective
Typesdedonnes
6
continuesurunintervalle
ex : poids taille ex:poids,taille
binaire
nominale
ex:couleur
ordinale ordinale
chellevariable
ex:croissanceoptimaledesbactries,durede
laradioactivit
Mixte Mixte
Valeurscontinuessurunintervalle,normalisation
N li l d ff hi d i d
7
Normaliserlesdonnes:saffranchirdesunitsdemesures
cartabsolulamoyenne
|) | ... | | | (|
1
2 1 f nf f f f f f
m x m x m x
n
s + + + =
Calculerlamesurenormalise(zscore)
f
f if
if
s
m x
z

=
Lutilisationdelcartabsoluestplusrobustequecellede
lcart type l carttype
Valeurscontinuessurunintervalle,Fonctiondedistance
Di t d Mi k ki
8
DistancedeMinkowski:
q
q
p p
q q
j
x
i
x
j
x
i
x
j
x
i
x j i d ) | | ... | | | (| ) , (
2 2 1 1
+ + + =
aveci =(x
i1
,x
i2
,,x
ip
)etj =(x
j1
,x
j2
,,x
jp
)deuxobjetsp dimensions,etq un
entier positif
p p j i j i j i 2 2 1 1
entierpositif
siq =1:distancedeManhattan
| | ... | | | | ) , (
2 2 1 1 p p j
x
i
x
j
x
i
x
j
x
i
x j i d + + + =
siq =2:distanceeuclidienne
2 2 1 1 p p j i j i j i
) | | | | | (| ) (
2 2 2
x x x x x x j i d + + + =
Proprits
d( )
) | | ... | | | (| ) , (
2 2 1 1 p p j
x
i
x
j
x
i
x
j
x
i
x j i d + + + =
d(i,i) =0
d(i,j) 0(positive)
d(i,j) =d(j,i) (symtrique)
d(i,j) d(i,k) +d(k,j) (ingalittriangulaire)
Valeursbinaires
9
tabledecontingence
Objet j
b a 1
0 1
Objet i
d c 0
Objet i
coefficientsimpledappariement(invariant,sila
variable est symtrique) variableestsymtrique)
d c b a
c b
j i d
+ + +
+
= ) , (
coefficientdeJaccard(noninvariant,silavariable
t t i ) estasymtrique)
c b a
c b
j i d
+ +
+
= ) , (
Dissimilaritdevaleursbinaires
E l
10
Exemple
N S Fi T T t 1 T t 2 T t 3 T t 4 Nom Sexe Fivre Tousse Test-1 Test-2 Test-3 Test-4
Jacques M O N P N N N
Marie F O N P N P N Marie F O N P N P N
Jean M O P N N N N


sexeestsymtrique
lesautressontasymtriques

soitOetP=1,etN=0
1 1
) (
33 . 0
1 0 2
1 0
) , (
+
=
+ +
+
=
d
marie jacques d
75 . 0
2 1 1
2 1
) , (
67 . 0
1 1 1
1 1
) , (
=
+
=
=
+ +
+
=
marie jean d
jean jacques d
2 1 1 + +
Variablesnominales
li ti d l bi i l d 2 t t
11
gnralisationdesvaleursbinaires:plusde2tats
mthode 1 : appariement simple mthode1:appariementsimple
m:nombredappariements,p:nombretotalde
i bl variables
p
m p
j i d

= ) , (
p
mthode2:utiliserungrandnombredevariables
binaires
crationdunevariablebinairepourchacundes
t t d i bl i l tatsdunevariablenominale
Variableordinale
l d t i t t
12
lordreestimportant:rang
peut tre traite comme une variable continue sur peuttretraitecommeunevariablecontinuesur
unintervalle
l
} 1 { M
remplacex
if
parsonrang
transformechaquevariablesur[0,1]en
} ,..., 1 {
f if
M r
q [ , ]
remplaantleiime objetdelafime variable
1
1

=
f
if
if
M
r
z
calculeladissimilaritenutilisantlesmthodes
d l ti i t ll
f
devaleurscontinuessurunintervalle
chellevariable
i i h ll li i h ll
13
mesurepositivesurunechellenonlinaire,chelle
exponentiellequisuitapproximativementAe
BT
ouAe
BT
Mthodes
lestraitercommedesvariablescontinuessurunintervalles:mauvais
choix
appliquerunetransformationlogarithmiquepuislestraitercomme
desvariablescontinuessurunintervalle
y
if
= log(x
if
)
f f
lestraitercommedesvariablesordinalesentraitantleurrangg
Variablesdetypemixte

14
Lesobjetspeuventtredcritsavectouslestypes
de donnes dedonnes
binairesymtrique,binaireasymtrique,
nominale,ordinale,
Utilisationduneformulepondrepourcombiner p p
leurseffets
) ( ) (
1
) (
f
ij
f
ij
p
f
d
j i d

) (
1
1
) , (
f
ij
p
f
ij ij f
j i d

=
=

=
Principalesapproches
i i
15
partitionnement
partitionne les objets et value les partitions partitionnelesobjetsetvaluelespartitions
hirarchique
dcompositionhirarchiquedensembles
dobjets d objets
densit
basesurunefonctiondedensitoude
connectivit connectivit
grille grille
basesurunestructuredegranularit
l i i plusieursniveaux
Partitionnement
C t i titi d l b d d D t t
16
ConstruireunepartitiondelabasededonnesD contenantn
objetsenunensembledek clusters
E d k i i k l i Etantdonnk,trouvunepartitionenk clustersqui
optimisentlecritredepartitionnement
O i l b l i l i i h i Optimumglobal:traitertouteslespartitionsexhaustivement
Heuristique:kmeans oukmdodes
k h l t t t t kmeans :chaqueclusterestreprsentparsoncentre
kmdodes ouPAM(partitionaroundmedoids):chaqueclusterest
reprsent par un des objets du cluster reprsentparundesobjetsducluster
kmeans

17
4tapes
1 Partitionne les objets en k ensembles non 1. Partitionnelesobjetsenk ensemblesnon
vides
2. Calculelecentrodedechaque
partition/cluster partition/cluster
3. Assignechaqueobjetleclusterdontle g q j
centrodeestleplusproche
b l l l 4. boucleen2,jusqucelesclusterssoient
stables. stables.
kmeans,exemple
18
7
8
9
10
7
8
9
10
3
4
5
6
3
4
5
6
0
1
2
0 1 2 3 4 5 6 7 8 9 10
0
1
2
0 1 2 3 4 5 6 7 8 9 10
9
10
9
10
5
6
7
8
9
5
6
7
8
9
1
2
3
4
1
2
3
4
0
0 1 2 3 4 5 6 7 8 9 10
0
0 1 2 3 4 5 6 7 8 9 10
kmeans. Remarques
Avantages
19
Avantages
Relativementefficace:O(tkn),avecnlenombredobjets,tlenombre
ditrationsetengnraltetk<<n g
[Link]
atteintenutilisantdestechniquestellesquelesalgorithmes
gntiques gntiques
Faiblesses
Utilisable seulement lorsque la moyenne est dfinie Que faire dans le [Link]
casdedonnesnominales?
Besoindespcifierklavance
Negrepaslebruitetlesexceptions
Netrouvequedesclustersdeformeconvexe
kmdodes
Trouve des reprsentants appels mdodes dans les
20
Trouvedesreprsentants,appelsmdodes,dansles
clusters
PAM PAM
mdode :lobjetdunclusterpourlequelladistancemoyennetous
lesautresobjetsduclusterestminimale
critrederreur:
Algorithme

=
=
k
i C p
i
i
m p d E
1
2
) , (
1. Slectionnerk objetsarbitrairement
2. Assignerlerestedesobjetsaumdode leplusproche
Sl ti bj t d d t h i l it d 3. Slectionnerunobjetnonmdode etchangersilecritrederreur
peuttrerduit
4. Rpter2et3jusqunepluspouvoirrduirelecritrederreur p j q p p
[Link]
21
E-E<0
E-E>0
E-E<0
Clusteringhirarchique

22
Utilisationdunematricededistance:nencessite
pas de spcifier le nombre de clusters pasdespcifierlenombredeclusters
Step 0
Step 1 Step 2 Step 3 Step 4
agglomerative
(AGNES)
b
a
a b
abcde
( )
d
c
c d e
a b c d e
d
e
d e
spatative
Step 4
Step 3 Step 2 Step 1 Step 0
spatative
(DIANA)
AGNES(AgglomerativeNesting)

23
Utiliseunematricededissimilarit
Fusionne les nuds les moins dissimilaires Fusionnelesnudslesmoinsdissimilaires
10 10 10
5
6
7
8
9
5
6
7
8
9
5
6
7
8
9
0
1
2
3
4
0
1
2
3
4
0
1
2
3
4
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
Undendrogrammeillustrecommentlesclusterssontfusionnshirarchiquement

24
Dcomposelesdonnesenplusieursniveaux
imbriqus de partitionnement imbriqusdepartitionnement
Unclusteringestobtenuencoupantle
dendogrammeauniveauchoisi
Mesuresdesimilaritentre2clusters
25
complete linkage
plus petite similarit/plus grande distance entre pluspetitesimilarit/plusgrandedistanceentre
touteslespairesdegnesentre2clusters
average linkage
i il it t l i d similaritmoyenneentrelespairesdegnes
singlelinkage
plusgrandesimilarit/pluspetitedistanceentre
2 d 2 l t 2gnesde2clusters
Mthodesbasessurladensit
Principales caractristiques
26
Principalescaractristiques
Clusterdeformearbitraire
Gestiondubruit
B i d d d i i Besoindunparamtrededensitcommecritre
darrt
2paramtres
p
q
Eps :rayonmaximaldevoisinage
MinPts :nombreminimaldepointsdanslevoisinage
dfiniparEps
q
N
Eps
(p):{q D|dist(p,q)Eps}
un point p est directement atteignable dun point q si
p
unpointp estdirectementatteignable d unpointq si
p appartientN
Eps
(q)
|N
Eps
(q)|MinEps
i i bl d i i
q
p
1
unpointp estatteignable dunpointq si
ilexisteunechanedepointsp
1
,,p
n
tellequep
1
=q et
p
n
=p etquelesp
i+1
sontdirectementatteignablesdesp
i
p q
unpointp estconnect unpointq si
ilexisteunpointo telquep etq sontatteignables
depuiso
p q
oo
Mthodesbasessurunegrille
U ili i d ill d l i l i l
27
Utilisationdunegrilledesrsolutionsmultiplescomme
structurededonnes
Lespaceestdivisencellulesrectangulaires
Mthodesbasessurunegrille
Chaque cellule de niveau i est divise en un certain
28
Chaquecelluledeniveauiestdiviseenuncertain
nombredecellulespluspetitesauniveaui+1
Informations statistiques calcules et stockes chaque Informationsstatistiquescalculesetstockeschaque
niveau
Approche descendante Approchedescendante
Suppressiondescellulesnonpertinentespourles
it ti i t itrationssuivantes
Rpterleprocessusjusquatteindreleniveauleplus
bbas
Avantages
paralllisable,misejourincrmentale
O(k),ok estlenombredecelluleauplusbasniveau p
Faiblesse
les bords des clusters sont soit horizontaux soit lesbordsdesclusterssontsoithorizontauxsoit
verticaux,pasdediagonale!
a
r
y

0
0
0
)
77
a
t
i
o
n
e
k
)
29
S
a
l
a
(
1
0
,
5
6
7
5
6
7
V
a
c
a
(
w
e
e
4
3
2
4
3
2
20 30 40 50 60
age
1
2
0
20 30 40 50 60
age
1
2
0
20 30 40 50 60 20 30 40 50 60
o
n
=3
V
a
c
a
t
i
o
= 3
30 50
age