Post on 02-Feb-2021
Mineria de Datos
Clustering IIClustering II
Dr. Edgar Acuna Departmento de Matematicasp
Universidad de Puerto Rico- Mayaguez
math.uprrm.edu/~edgar
PERU 2009 Mineria de Datos Edgar Acuna 1
Algoritmos jerárquicos
Estos algoritmos generan sucesiones anidadas de clusters que se pueden
i li d b l
En la figura se muestra el
visualizar con una estructura de arbol llamado Dendrograma,En la figura se muestra eldendrograma del conjunto Bupa
obtenido usando la función hclust para algoritmo p gjerarquico aglomerativo de la libreria stats.
> a=hclust(dist(bupa[,1:6]))> plot(a)
PERU 2009 Mineria de Datos Edgar Acuna 2
Dendrogramas
Los dendrogramas son fáciles de interpretar pero pueden conducir afalsas conclusiones por las siguientes razones:falsas conclusiones por las siguientes razones:
1) El dendrograma correspondiente a un conglomerado jerárquico no es único, puesto que por cada junte de clusters (merge) uno necesita
ifi b á b l l d h ál l i i despecificar que sub-árbol va a la derecha y cuál a la izquierda. Por default la función hclust de la librería stats ordena los arboles de tal manera que los conglomerados más concentrados van a la q gizquierda.
2) La estructura jerárquica del Dendrograma no representa con certezalas verdaderas distancias entre los objetos distintos del conjunto delas verdaderas distancias entre los objetos distintos del conjunto de datos.
PERU 2009 Mineria de Datos Edgar Acuna 3
Cluster Dendrogram00
040
0020
0030
ght
1000
Hei
g
8577 11
531
634
217
919
032
333
141 15
822
826
128
634
518
616
929
518
314
732
618
134
015
727
813
417
531
7 36 233
300
167
343
250
311
148 53 151
168
334
187
312 25 133
294
189
307
182
205 98 139
252 89 246 18 44 210
217
267 29 119
262
105
200
194
196
174 90 339
111
31 14 66 51 191 49 207
204
209
112 57 114 16 104
208
335
220
329 20 214
123
211
337 83 43 216
122
321
171
108
213
268
305 1
193
310
125
266 39 221 34 251
188
320
159
338 81 203
218
161
19 110
140
178
242
118
135
120
165
271 47 239
162 58 75 274
302
324 79 11 64 22 315
106
282 30 113
219 38 92 129
197
202 27 257
303
136
292
154
117
264 63 6 145
287 5
273 67 126
225
116
309
141
318 69 237
285
124
130
222 24 201 62 160
293
224
212
184
137
284 12 241
153
226
240 84 86 149
173
138
270
247
299
132
314
243 68 232
166
260
101
281 60 258
325
248 21 259
344
143
150
198
245
253 15 249
109
195 35 17 215 45 8 94 9 192 10 23 46 70 7 28 283 52 73 56 223 88 103
265
277
102
177
235
156
172
128
155
185
332
127
170
176
229
146
298 42 97 290
330
296 54 304
313
121 82 254
180 48 280 3 71 230 76 206
333 80 100
107 4
152
341
164
319
234 59 306 40 99 26 275
131
238 74 256 65 91 199 33 78 93 327
289
227
255 2 13 95 272 37 308
322
336 50 244 61 87 276
288 55 96 236
279
163
297 32 291
269 72 144
142
231
263
301
328
0
hclust (*, "ward")dist(bupa[, 1:6])
PERU 2009 Mineria de Datos Edgar Acuna 4
El coeficiente de correlación cofenético puede ser usado para medir cuan bien la estructura jerárquica del dendrograma representa a las verdaderas distancias Se define como larepresenta a las verdaderas distancias. Se define como la correlación entre las n(n - 1)/2 pares de dissimilaridades y sus distancias cofenéticas del dendograma. La función copheneticen la libreria mva calcula la distancia cofenéticasen la libreria mva calcula la distancia cofenéticas.
disbupa=dist(bupa[,1:6])hbupa=hclust(disbupa, method=”ave”)denbupa=cophenetic(hbupa)cor(disbupa denbupa)cor(disbupa,denbupa)La correlacion cofenética da 0.915849
PERU 2009 Mineria de Datos Edgar Acuna 5
Ejemplo de un dendrograma y sus cortes
treebupa=as.dendrogram(hbupa)bupita=cut(treebupa, h=100)> bupita$upper`dendrogram' with 2 branches and 4 members total, at height 176.9354 $lower$lower[[1]]`dendrogram' with 2 branches and 333 members total, at height 91.22225 $lower[[2]]`d d ' ith 2 b h d 3 b t t l t h i ht 64 38526`dendrogram' with 2 branches and 3 members total, at height 64.38526 $lower[[3]]`dendrogram' leaf '85', at height 0 $lower[[4]]$lower[[4]]`dendrogram' with 2 branches and 8 members total, at height 62.8725
PERU 2009 Mineria de Datos Edgar Acuna 6
Ejemplo de un dendrograma y sus cortes
treebupa=as.dendrogram(hbupa)bupita=cut(treebupa, h=100)> bupita$upper`dendrogram' with 2 branches and 4 members total, at height 176.9354 $lower$lower[[1]]`dendrogram' with 2 branches and 333 members total, at height 91.22225 $lower[[2]]`d d ' ith 2 b h d 3 b t t l t h i ht 64 38526`dendrogram' with 2 branches and 3 members total, at height 64.38526 $lower[[3]]`dendrogram' leaf '85', at height 0 $lower[[4]]$lower[[4]]`dendrogram' with 2 branches and 8 members total, at height 62.8725
PERU 2009 Mineria de Datos Edgar Acuna 7
Ejemplo de un dendrograma y sus cortes
> par(mfrow=c(2,3))> plot(treebupa)> plot(bupita$upper)> plot(bupita$lower[[1]])> plot(bupita$lower[[2]])> plot(bupita$lower[[3]])> plot(bupita$lower[[4]])>
PERU 2009 Mineria de Datos Edgar Acuna 8
150
150 80
5010
0
5010
0
anch
1
h 2
h 4 20
4060
0
20 214
123
211
337
335
220
329
290
330
296 54304
31342 9782 254
180 48 2803 71230
156
172
128
155
185
265
277
102
177
235
16119 11081 203
218
122
321
310
171
108
213
268 83159
338
305 1
193 93327
229
289
227
255 76206
33334 25139 221
125
266
341
164
319 4
152
127
170
176
146
298
332
188
320
111
224
198
245
204
20990 339
210
217
267 1844 104
196 89246 51191 49 20731 1466 57114
112
208 6916 141
318 29119
26243 216
174
194
105
20063 3892 129
154
145
287
117
264
303
257
136
292
325
24821 259
232
243
197
20258 6827 28230 113
219
212
131
238 4099 23459 30626 19933 7880 100
107 6574 25632 291
269 72144
328
301
231
263
28855 96 236
279
163
297
153
240
241
137
284
142
27584 86149
173
138
270
247
299
132
314
166
260
184
101
28160 91258
344
109
1955
273
116
30967 126
225
237
285 24201 62160
293
124
130
222
140
178
162 7911 64192
16575 27412 226
242
118
135
302
324 6
271
12047 23923 910 4535 17215 8 94103
143
150
25315 24988 4670 728 28352 7356 2232 1395 27237 308
322
33650 244 6187 276
106 22315
286
121
181
340
345
186
169
295 41158
228
261
157
278
183
147
326
167
343
250
311
14853 151
187
312
294 98139
25225 133
189
307
168
334
182
205
134
175
317 36233
30085 331 77115
323
316
342
179
190
0
Bra
Bran
cBr
anch
3 Bra
nch
0
20 214
123
211
337
335
220
329
290
330
29654 304
313 4297 82254
18048 2803 71 230
156
172
128
155
185
265
277
102
177
235
161 19110 81 203
218
122
321
310
171
108
213
26883 159
338
305 1
193 93327
229
289
227
255 76206
33334 251 39221
125
266
341
164
3194
152
127
170
176
146
298
332
188
320
111
224
198
245
204
209 90339
210
217
267 1844 104
196 89246 51191 49207 31 1466 57114
112
208 6916 141
318 29119
26243 216
174
194
105
200 6338 92129
154
145
287
117
264
303
257
136
292
325
248 21259
232
243
197
202 58 6827 28230 113
219
212
131
23840 99234 59 30626 19933 7880 100
107 6574 25632 291
26972 144
328
301
231
263
288 5596 236
279
163
297
153
240
241
137
284
142
275 8486 149
173
138
270
247
299
132
314
166
260
184
101
281 6091 258
344
109
1955
273
116
30967 126
225
237
285 24201 62 160
293
124
130
222
140
178
162 7911 64192
165 75274 12226
242
118
135
302
3246
271
120 47 23923 910 4535 17215 894 103
143
150
25315 24988 4670 728 28352 7356 223 213 95272 37308
322
336 50244 6187 276
10622 315
286
121
181
340
345
186
169
29541 158
228
261
157
278
183
147
326
167
343
250
311
148 53151
187
312
294 98139
25225 133
189
307
168
334
182
205
134
175
317
06
3050
020.
040.
0
3050
010
36 233
300 0
.00
0.0
85
010
331 77 115
323
316
342
179
190
Heatmaps.
Son gráficas que muestran simultaneamente lasi l d d l filagrupaciones en conglomerados de columna y filas.
La función heatmap de la libreria mva permite hacerheatmaps usando un gran número de tonalidades decolores.
PERU 2009 Mineria de Datos Edgar Acuna 10
Ejemplo de heatmaps para Iris
Notar que solo las variables 2 y 3 determinan claramente l 3 l
PERU 2009 Mineria de Datos Edgar Acuna 11
las 3 clases.
Algoritmo jerárquico aglomerativoSuponiendo que tenemos una matriz de datos m x n. Se empieza con m conglomerados si se desea formar gruposde muestras (filas) o con n clusters si se quieren formar gruposde muestras (filas) o con n clusters si se quieren formar gruposde variables (columnas). En cada paso se juntan los cluster mas cercanos usando una medida de distancia entre clusters (linkage)Entre estas distancias estánLinkage promedio: promedio de las distancias de lasLinkage promedio: promedio de las distancias de lasobservaciones en cada cluster.Linkage simple: la menor distancia entre las observacionesde cada clusterLinkage completo: la mayor distancia entre las observacionesde cada cluster.
PERU 2009 Mineria de Datos Edgar Acuna 12
de cada cluster.
Ejemplo de Jerarquico Aglomerativo
En este caso usaremos la funcion agnes de la libreria clusterbupagl table(cutree(bupagl,k=2))1 2
62 28362 283> table(cutree(bupagl,k=3))
1 2 3 283 53 9La función plot.agnes permite hacer un plot del dendrograma.
PERU 2009 Mineria de Datos Edgar Acuna 13
Pero no tiene la misma flexibilidad de las funciones en stats.
Métodos jerárquicos divisivos
Empieza con un solo cluster, que es aquel que contiene atodas las muestras. En cada paso se divide los clusters en dos subgrupos.Son más lentos de calcular que los jeráquicos aglomerativosA continuacion se muestra un ejemplo del métodojerarquico divisivo usando la función Diana de la libreriacluster.> bupadiv plot(bupadiv,which=2)> bupadiv
PERU 2009 Mineria de Datos Edgar Acuna 14
Ejemplo usando Diana
bupadiv=diana(bupa[,1:6],metric='euclidean')l (b di hi h )
300
Dendrogram of diana(x = bupa[, 1:6], metric = "euclidean")
plot(bupadiv,which=2)bupadivb=cutree(bupadiv,k=2) 200
250
table(b)1 2
33 312 85100
150
Hei
ght
table( b,bupa [,7])> table(cutree(bupadiv,k=3))1 2 3 1 9
111
3 9 9 032
6 22
42 82 6 5 44 8 2 2 224
43 9 8 5 7 50
8 47 61 7 8 1 8 5 5 0 5 41 8328
66 4
5 312
7 3 1 175
187
7 5 8 2 294
36 300
134
317
233
115
323
9 0 6 233
1
050
1 2 3 25 8 312
422
7 33 107 34 251
39 221
125
266 76 206 80 152
333
127
164
319
341
234
14 66 31
191 49 89 24
6 51 57 114 9
0 1911
219
419
6 100
198
204
209 16 69 18 44 104
210
217
267
119
262 222
208
124
141
318 10
520
017
433
920 21
4 123
211
337 329
2926
832
110
821
317
119
3 310
43 122 83 216 2 13 37 30
8 95 272
301
93 327 32 291
40 99 236
279
297 59 260
72 144
269
263 4
50 244 61 87 276 28
832
233
68
48 280
180 54
304
313 29
629
033
0 5 88 23 103 56 223
283 7 10 17 21
5 35 28
52 73 15 249
245
207 19
46 70 118
143
150 25
327
014
017
813
231
424
729
914
9 285 3 4 8 94 4
5 12 109
116
309
24 237 62
160
293
201
130
137
284
241
153
240
6712
622
527
321 25
924
832
5 328
26 78 306
65 74 256 91 258 21
260
101
281
84 86 138
173
142
231
131
238
275
163
166
184 23
2 26
47 239
120
165
135
242 11 64 79
162
75 274
226 9
192 92 6
327
130
232
414
528
730
315
427
136
292
257
197
202 55 96 68 58
117
264 38 129
3011
321
928
2 106
315 2 4 3
71 230
170
176 1
77 97
254
146
298
229 28
922
826
510
223
527
712
815
518
515
617
2 25
121
340
148
181 1 4 26 15 27 19 11
0 8120
321
8 161
188
320 33
215
825
515
933
8 305
22 334 18
169
295 18
6 325 13
3 167
343
53 151 31
1 7 2016
833
498 18
213
925
218
930
7 179
190
316
342
PERU 2009 Mineria de Datos Edgar Acuna 15
Divisive Coefficient = 0.96
Comparación de métodos de particionamiento con los métodos jerárquicos.
Los métodos de particionamiento tienen la ventaja de quesatisfacen un criterio de optimilidad aunque sea aproximadamente. D t j N it l i i i l d l ú dDesventajas: Necesitan un valor inicial del número declusters y toma mucho tiempo obtener los clusters.
Por otro lados los métodos jerárquicos tienen la ventaja que sonrápidos de calcular sobre todo el aglomerativorápidos de calcular sobre todo el aglomerativo. Desventaja: La rigidez que le da la estructura de árbol ( el llamadofactor de anidamiento). Es dificil corregir lo que se hizo antes. ) g q
PERU 2009 Mineria de Datos Edgar Acuna 16
Validacion clusters
Indices Internos. Estadisticas basados en las sumas de cuadradosentre clusters y dentro de clusters. El número de clusters K esyaquel que maximiza o minimiza uno de estos indices.(Milligan,
G.W.& Cooper, M.C.). Entre los principales estan el indice de Dunn el Indice de Davies BouldinDunn, el Indice de Davies-Bouldin.
Ancho de silueta promedio.Determinar el número de componentes de una mezcla de p
distribuciones es lo mismo que determinar el número de clusters. Asi, que se pueden usar los criterios de AIC ( Criterio de Información de Akaike) y BIC ( Criterio de Informaciónde Información de Akaike) y BIC ( Criterio de Información Bayesiano).
PERU 2009 Mineria de Datos Edgar Acuna 17
Indice de Dunn (1974). La idea es identificar los clusteres que estan bien compactos y bien separados de los demas. Dada una particion de clusters donde c representa el iDada una particion de clusters donde ci representa el i-esimo cluster de la particion, se define el indice de Dunn por
)(d}}
)('(max),(
{{minmin1
11knk
jinijni cd
ccdD
≤≤≤≠≤≤≤=
donde d(ci,cj) – es la distancia entre los clusters ci, y cj y d'(ck) representa la distancia intracluster del cluster ck.En numero optimo de clusters es aquel que maximiza D.
La libreria fpc tiene una funcion cluster.stats que calcula el indice de Dunn.
PERU 2009 Mineria de Datos Edgar Acuna 18
> disbupa=dist(bupa[,1:6])> cutree(bupadiv k=2)> cutree(bupadiv,k=2)> cluster.stats(disbupa,a,bupa[,7])$dunn[1] 0 06806368[1] 0.06806368
PERU 2009 Mineria de Datos Edgar Acuna 19
Silhouette plots
Los plots siluetas, (Rousseeuw 1987) pueden ser usados para:Seleccionar el número de clusters.Evaluar cuan bien han sido asignados las observaciones en los clusters.
El h d l il t ( ilh tt idth) d l i é iEl ancho de la silueta (silhouette width) de la i-ésimaobservación es definida por: sili = (bi - ai)/ max(ai, bi)Donde ai denota la distancia promedio entre la observación i yDonde, ai denota la distancia promedio entre la observación i ytodas las otras que están en el mismo cluster de i, y bi denota ladistancia promedio minima de i a las observaciones que están enotros clusters.El valor de la silhouette varia entre -1 y +1.
PERU 2009 Mineria de Datos Edgar Acuna 20
Características de los Silhouette plots
Las observaciones con ancho de silueta grande están bien agrupadas mientras aquellas con ancho de silueta baja tienden a estar ubicada en el medio de dos clusters.
Para un número de clusters dado K el ancho de silueta promedioPara un número de clusters dado K, el ancho de silueta promediode la configuracion de conglomerados será simplemente el promedio de sili sobre todas las observaciones. Es decir,
il∑
Kaufman y Rousseeuw (1990) sugirieron estimar el númeron
sils i
i∑=
Kaufman y Rousseeuw (1990) sugirieron estimar el número óptimo de cluster K para el cual el ancho de silueta promedio sea la mayor posible.
PERU 2009 Mineria de Datos Edgar Acuna 21
Ejemplo de los Silhouette plots
Ejemplo con el conjunto de datos Bupa y el metodo jerarquico aglomerativojerarquico aglomerativo
> agbupa=agnes(dist(bupa[,1:6]),method=“ward”)>a=silhouette(cutree(agbupa,k=2),daisy(bupa[,1:6]))a silhouette(cutree(agbupa,k 2),daisy(bupa[,1:6]))>b=silhouette(cutree(agbupa,k=3),daisy(bupa[,1:6]))>c=silhouette(cutree(agbupa,k=4),daisy(bupa[,1:6]))( ( g p , ), y( p [, ]))>par(mfrow=c(1,3))>plot(a,main=“”)>plot(b, main=“”)>plot(c,main=“”)
PERU 2009 Mineria de Datos Edgar Acuna 22
Mirando el plot k=2 clusters es lo recomendado.
PLOTS SILUETAS PARA CLUSTERING DE BUPA
n = 345 2 clusters Cjj : nj | avei∈Cj sin = 345 3 clusters Cjj : nj | avei∈Cj si
n = 345 4 clusters Cjj : nj | avei∈Cj sij j j j j j1 : 40 | 0.36
1 : 283 | 0.65 1 : 283 | 0.59
2 : 243 | 0.41
02 00 02 04 06 08 10
2 : 62 | 0.11
02 00 02 04 06 08 10
2 : 53 | 0.18
3 : 9 | 0.5
02 00 02 04 06 08 10
3 : 53 | 0.14
4 : 9 | 0.5
Silhouette width si
-0.2 0.0 0.2 0.4 0.6 0.8 1.0
Average silhouette width : 0.56
Silhouette width si
-0.2 0.0 0.2 0.4 0.6 0.8 1.0
Average silhouette width : 0.52
Silhouette width si
-0.2 0.0 0.2 0.4 0.6 0.8 1.0
Average silhouette width : 0.36
Ejemplo de los Silhouette plots
Ejemplo con el conjunto de datos Bupa y el metodo PAM plots de siluetas
silicom=rep(0,9)f (i i 1 9){
0.35
p
for(i in 1:9){ silicom[i]=pam(vehicle[,1:18],i+1,diss=F stand=T)$silinfo$avg width} .25
0.30
silic
om
diss F,stand T)$silinfo$avg.width}
plot(2:10,silicom) 0.2
00
plot(2:10,silicom,type="o",xla="clusters",main="plots de siluetas")
Aqui tambien salen 2 clusters
2 4 6 8 10
clusters
PERU 2009 Mineria de Datos Edgar Acuna 24
Aqui tambien salen 2 clusters.
. Indices externosSupongamos que tenemos dos particiones de n objetos x1, ..., xn: la partición en R clases U = {u1, ..., uR} y la partición en C-clases = V={v1, ...,vC}, por lo general una de ellas conocida de antemano.. Los { 1 C} p gindices externos de concordancia entre las particiones pueden ser expresados en término de una tabla de contingencia con entradas nij que representa el número de objetos que están en ambos clusters uique representa el número de objetos que están en ambos clusters uiand vj, i = 1,...,R, j = 1,...,C . Sean
yque denotan las sumas de filas y columnas de la tabla de contingencia Seacontingencia. Sea
PERU 2009 Mineria de Datos Edgar Acuna 25
Dada las dos particiones U y Va: numero de pares objetos que estan en el mismo cluster tanto en U
como en V. c: numero de pares de objetos que estan en el mismo cluster en V pero
no en U.b: numero de pares de objetos que estan en el mismo cluster en U pero
no en V.d: numero de pares de objetos que estan en diferentes clusters tantod: numero de pares de objetos que estan en diferentes clusters tanto
en U como en V. m1=a+b = numero de pares de objetos en el mismo cluster en U.∑
=⎟⎟⎠
⎞⎜⎜⎝
⎛R
i
in
1
.
2
m2=a+c= numero de pares de objetos en el mismo cluster en V. ∑=
⎟⎟⎠
⎞⎜⎜⎝
⎛C
j
jn
1
.
2
PERU 2009 Mineria de Datos Edgar Acuna 26
Ejemplo
a= 4, b =2, C=3, d=6, m1=6, m2=7, Z=14
1 23
4 5
61 2
3
4 5
63 6
P1 P2
3 6
Notar que M=a+b+c+d= ⎟⎠
⎞⎜⎝
⎛2n
PERU 2009 Mineria de Datos Edgar Acuna 27
Rand(1971)2 2. .
1 1( (1/ 2)( ))
1
R C
i ji j
z n na dRand
n n= =
− ++
= + =⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟
∑ ∑
Jaccard 2 2⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠
( )z n dJac −= =
Fowlkes and Mallows
2 2. .
1 1
R C
i ji j
Jacb c dn n Z n
= =
= =+ ++ − −∑ ∑
(1/ 2)( ) d. . 1/2 1 2
1 1
(1/ 2)( )
[ ]2 2
R Ci j
i j
z n dFMn n m m
= =
−= =
⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠
∑ ∑
Un valor de Rand, Jaccard y FM cercano a 1 indica un buen agrupamiento.
PERU 2009 Mineria de Datos Edgar Acuna 28
g p
La medida Γ de Hubert y Arabie (1985)Sean las variables aleatorias:X(i,j)=1 si los objetos i y j caen en el mismo cluster de la
particion U e igual a 0 en otro caso.Y(i j) 1 i l bj i j l i l d lY(i,j)=1 si los objetos i y j caen en el mismo cluster de la
particion V e igual a 0 en otro caso. Se define la medida Γ de Hubert como:Se define la medida Γ de Hubert como:
∑ ∑Γ )()(1 jiYjiX∑ ∑=Γ ),(),( jiYjiXM
PERU 2009 Mineria de Datos Edgar Acuna 29
Para obtener valores de Γ entre -1 y 1 se prefiere normalizarlo y se obtienenormalizarlo y se obtiene
YX SSYjiYXjiXM /)]),(()),(()/1[( −∑∑ −=Γ
Que es equivalente a:Que es equivalente a:
∑ ∑ −= YX SSYXMjiYjiXH /]/),(),([
PERU 2009 Mineria de Datos Edgar Acuna 30
Pero, usando el hecho que X y Y son binomiales, se tiene quese tiene que
niRi
)2
( .1
∑=
n
Y
JC
J)
2( .
1∑
=
MX
i 21==
MY =
Que son las probabilidades de que los objetos i y jQue son las probabilidades de que los objetos i y j caigan en los mismos clusters de las particiones U y V respectivamente p
PERU 2009 Mineria de Datos Edgar Acuna 31
Similarmente,⎞⎛⎞⎛
)21(2)1(1
.
1
.
M
n
M
n
XXS
R
i
iR
i
i
X
∑ ⎟⎠
⎞⎜⎝
⎛
−∑ ⎟
⎠
⎞⎜⎝
⎛
=−===
MM
)21(2)1(1
.
1
. nn
YYS
C
j
jC
j
j ∑ ⎟⎠
⎞⎜⎝
⎛
−∑ ⎟
⎠
⎞⎜⎝
⎛
=−===
)1()1(MM
YYSY
PERU 2009 Mineria de Datos Edgar Acuna 32
Finalmente,
nZnnn
jiYjiXR
i
C
jij
R
i
C
jij
R
i
C
j
ij
2),(),( 1 11 12
1 1 −∑ ∑∑ ∑ −∑ ∑ ⎟
⎠
⎞⎜⎝
⎛∑∑
= =
MnZ
MMMi ji ji j
222 1 11 11 1 ==⎠⎝= = == =
PERU 2009 Mineria de Datos Edgar Acuna 33
Sustituyendo, en la forma de Γ normalizada se tiene⎞⎛⎞⎛R C nn
)2
)(2
(22
22)(*5.
....
1 1
..
∑ ⎟⎠
⎞⎜⎝
⎛−∑ ⎟
⎠
⎞⎜⎝
⎛−∑ ∑ ⎟
⎠
⎞⎜⎝
⎛⎟⎠
⎞⎜⎝
⎛
∑ ∑ ⎟⎠
⎞⎜⎝
⎛⎟⎠
⎞⎜⎝
⎛−−
== =
C jR iR C ji
R
i
C
j
ji
nM
nM
nn
nnnzM
H)
2)(
2(
22 111 1∑
⎠⎝∑
⎠⎝∑ ∑
⎠⎝⎠⎝ === = jii j
Ahora usando las identidades ⎞⎛
∑ ⎟⎠
⎞⎜⎝
⎛=+
=
R
i
inba1
.
2∑ ⎟
⎠
⎞⎜⎝
⎛=+
=
C
j
jnca1
.
2⎠⎝ ⎠⎝y a= (z-n)/2, se tiene la siguiente formula simplificada de H
PERU 2009 Mineria de Datos Edgar Acuna 34
de H
))())(()()(())((
caMbaMcabacabaMaH
++++++−
=))())(()()(( caMbaMcaba +−+−++
PERU 2009 Mineria de Datos Edgar Acuna 35
>agbupa=agnes(dist(bupa[,1:6]),method="ward")>a=cutree(agbupa,k=2)> mexter(bupa[,7],a)$rand[1] 0.4990563
$jaccard[1] 0.4163361
$fandm[1] 0.5954606
$hubert[1] -0.01218121
PERU 2009 Mineria de Datos Edgar Acuna 36
> agbupa=agnes(dist(bupa[,1:6]),method="complete")> c=cutree(agbupa,k=2)> mexter(bupa[,7],c) mexter(bupa[,7],c)$rand[1] 0.5103809$jaccard$jaccard[1] 0.5091815$fandm[1] 0 7124241[1] 0.7124241$hubert[1] -0.01026507> table(c)c1 2
PERU 2009 Mineria de Datos Edgar Acuna 37
344 1
FOM=Figure of Merit (Yeung and R 2001)Ruzzo,2001)The Gap Statistics (Tibshirani,2000).p ( )Clest (Dudoit & Fridlyand, 2002)
PERU 2009 Mineria de Datos Edgar Acuna 38
Algoritmo Clest (Dudoit & Fridlyand, 2002).Estima el número de conglomerados basado en la precision de la
prediccion. Para cada número de clusters k, se divide al azar B veces el conjunto de
datos original en dos conjuntos que no se superponen. Uno de ellos Lb forma la muestra de entrenamiento y el otro,Uno de ellos Lb forma la muestra de entrenamiento y el otro, Tb forma la muestra de prueba , b = 1, . . . , B.-Aplicar el algoritmo de conglomerados (se recomienda el PAM) a lasobservaciones en el conjunto de entrenamiento Lb.– Construir un clasificador ( puede ser LDA, k-nn, CART, etc) usando
laslasetiquetas obtenidas del método de conglomerados.-Aplicar el clasificador al conjunto de prueba Tb.
PERU 2009 Mineria de Datos Edgar Acuna 39
p j p-Aplicar el algoritmo de conglomerados al conjunto de prueba Tb.
-Calcular un score sk,b comparando las etiquetas del conjunto de prueba obtenidas por conglomerados y por predicción p p g y p pdel clasificador. Estos scores se obtienen aplicando indices externos como RAND, Jaccard o Fowkles y Mallows (FM)(FM)
-El score de similaridad para los k clusters es la mediana de los B scores de similaridad tk = median(sk,1, · · · , sk,B).
-El número de clusters K es estimado comparando el b d tk l dscore observado tk con su valor esperado
asumiendo cierta distribución de Referencia.
PERU 2009 Mineria de Datos Edgar Acuna 40
El programa Machaon (2004)
Nadia.Bolshakova (CS Department, T i it C ll UK)Trinity College, UK)
Cluster Validty Tool for gene Expression y g pdata
PERU 2009 Mineria de Datos Edgar Acuna 41
Clustering basados en modelos Clustering basados en modelos ( Fraley y Raftery, JASA 2002)Analisis de conglomerados (cluster) es el agrupamiento de
objetos en grupos bien coherentes basado en caracteristicas medidas en los objetos. Fue introducido a los finales de 1950 por Sokal, Sneath y otros, y se ha desarrolado principalmente usando metodos heuristicos. p pRecientemente se ha encontrado que analisis de clusters basado en modelos probabilisticos tanto para entender los metodos actualres de hacer clustering como parlos metodos actualres de hacer clustering como par sugerir nuevos metodos. El suo de modelo tambien permite responder interrogantes tales como, cuantos clusters usar? que metodo de cluster es el masclusters usar?, que metodo de cluster es el mas conveniente? Como tratar la presencia de outliers?
PERU 2009 Mineria de Datos Edgar Acuna 42
Clustering basado en modelosDesde hace tiempo, investigadores, se han dado cuenta que analisis de conglomerados puede ser llevado a cabo usando modelos de probabildad. Con estos modelos se esta tratando de ver cuando es que un cierto metodo de clustering funciona bien. Se ha demostrado que algunos de los metodos heuristicos de hacer cpnglomerados son simplemente metodos de estimacion aproximados de modelos de probabilidad Por ejemplo elaproximados de modelos de probabilidad. Por ejemplo, el metodo de k-means y el metodo de Ward son equivalentes a conocidos metodos para maximizar aproximadamente la clasificacion usando una normal multivariada cuando la matrizclasificacion usando una normal multivariada cuando la matriz de covarianza es la misma para cada componente y proporcional a la matriz identidad.
PERU 2009 Mineria de Datos Edgar Acuna 43
Clustering basado en mezclas Clustering basado en mezclas finitas
Modelos de mezcla finitas han sido propuestos y estudiado a menudo en el contexto de clasificacion (Wolfe, 1963,menudo en el contexto de clasificacion (Wolfe, 1963, 185,1967,1970; Edwards y Cavalli-Sforza 1965; Day 1969; Scott y Symons 1971; Duda y Hart 1973; Binder 1978). In modelos de mezclas finita cada componente de la distribucion deIn modelos de mezclas finita cada componente de la distribucion de probabilidad corresponde a un cluster. El problema de determinar el numero de componentes puede ser reformulado como un problema de seleccion de modelosreformulado como un problema de seleccion de modelosLos outliers son tratados mediante la adicion de una o mas componente representando una distribucion distinta para los datos
lanomalos.
PERU 2009 Mineria de Datos Edgar Acuna 44
Clustering basado en Mezclas Clustering basado en Mezclas finitasLa funcion de likelihood de un modelo de mezcla con G componentes dado que se observo el la muestra aleatoria y1, y2,… yn de la varible aleatoria y esta definida poraleatoria y esta definida por
)/()/,....;,.....(1 1
11 kik
n
i
G
kkGG yfyL θτττθθ ∏ ∑=
1 1i k= =
Donde fk y θk son las funciones de densidad y los parametros de la k-esima componente de la muestra y τ es la probabilidad de que unaesima componente de la muestra y τk es la probabilidad de que una observacion pertenezca a la k-esima componente . Los τk son no negativos y su suma debe dar 1.Por lo general fk es una densidad normal multivariada φk parametrizadaPor lo general fk es una densidad normal multivariada φk parametrizada por su media y matriz de covarianza.
PERU 2009 Mineria de Datos Edgar Acuna 45
La distribucion Normal La distribucion Normal Multivariada
))()(1exp( 1 yy T Σ − μμ
)2det(
))()(2
exp(),/(
k
yyy
kikki
kkik Σ
−Σ−−≡Σ
π
μμμφ
PERU 2009 Mineria de Datos Edgar Acuna 46
Clustering basado en mezclas Clustering basado en mezclas Gaussianas
Las caracteristicas geometricas( forma, volumen, orientacion) de los clusters son determinados por las covarianzas Σk que a su vez puedenclusters son determinados por las covarianzas Σk, que a su vez pueden ser parametrizadas para imponer restricciones entre clusters. Asi, si se considera Σk=λI, entonces todos los clusters son esfericos y del mismo tamano, si Σk=Σ entonces todos los clusters tienen la misma geometria , k gpero no son necesariamente esfericos. En el primer caso se necesita solo un parametro y en el segundo d(d+1)/2 parametros.
PERU 2009 Mineria de Datos Edgar Acuna 47
El criterio BIC (Bayesian Information C iit i ) l i l j Criiterio) para seleecionar el mejor modelo
kkkkk BICnvMDpMDp =−≈ )log(),ˆ/(log2)/(log2 θ kkkkk pp )g(),(g)(g
donde νk es el numero de parametros independientes a ser estimado en el modelo M (Schwarz 1978)en el modelo MK (Schwarz 1978).El mejor modelo sera aquel tiene el BIC ma grande
PERU 2009 Mineria de Datos Edgar Acuna 48
Uso de MclustLos siguientes modelos son comparados en 'Mclust':
"EII": spherical, equal volume "VII": spherical unequal volumeVII : spherical, unequal volume "EEI": diagonal, equal volume, equal shape "VEI": diagonal, varying volume, equal shape"EVI": diagonal, equal volume, varying shape "VVI": diagonal, varying volume, varying shape
"EEE": ellipsoidal, equal volume, shape, and orientation p q pEEV": ellipsoidal, equal volume and equal shape"VEV": ellipsoidal, equal shape "VVV": ellipsoidal varying volume shape and orientationVVV : ellipsoidal, varying volume, shape, and orientation
El comportamiento de los modelos dependen de la descomposicion espectral de las matrices de covarianzas
PERU 2009 Mineria de Datos Edgar Acuna 49
> a=Mclust(bupa[,1:6],1:10)> abest model: diagonal varying volume and shape with 4best model: diagonal, varying volume and shape with 4
components> a$bic[1] 14867 11[1] -14867.11> table(a$class)
1 2 3 41 2 3 4 135 152 53 5 > a$parameters$pro[1] 0.40769889 0.41884788 0.15928831 0.01416492
PERU 2009 Mineria de Datos Edgar Acuna 50
> a$parameters$mean[,1] [,2] [,3] [,4]
V1 90 429894 89 313426 91 110518 96 69474V1 90.429894 89.313426 91.110518 96.69474V2 73.818404 64.056493 73.900558 82.77228V3 29.045119 20.299498 57.676037 61.74509V4 24.067698 19.222119 38.203606 49.03473V5 35.667890 16.089920 88.777391 202.03921V6 3.700042 2.163306 5.584584 10.65408
PERU 2009 Mineria de Datos Edgar Acuna 51
> a$BICEII VII EEI VEI EVI VVI EEE EEV VEV VVV
1 -18303.43 -18303.43 -15983.15 -15983.15 -15983.15 -15983.15 -15568.76 -15568.76 -15568.76 -15568.762 -17202 80 -16598 74 -15510 36 -15132 42 -15321 70 -15001 33 -15441 96 -15297 84 -14983 84 -14964 502 -17202.80 -16598.74 -15510.36 -15132.42 -15321.70 -15001.33 -15441.96 -15297.84 -14983.84 -14964.503 -16838.22 -16197.67 -15409.54 -14992.76 -15209.54 -15040.37 -15318.12 -15277.09 -15036.85 NA4 -16678.34 -16008.67 -15408.63 -14940.84 -15185.15 -14867.11 -15314.72 -15309.64 -15097.61 NA5 -16554.47 -15886.13 -15445.39 -14957.04 -15161.28 -14894.18 -15245.00 -15330.92 -15155.63 NA6 -16468.54 -15783.68 -15158.72 -14974.77 -15181.85 NA -15154.37 -15316.74 -15193.14 NA7 16466 85 15776 61 15194 85 14976 11 NA NA 15172 70 15406 73 15178 47 NA7 -16466.85 -15776.61 -15194.85 -14976.11 NA NA -15172.70 -15406.73 -15178.47 NA8 -16470.31 -15760.68 -15183.71 -15009.91 NA NA -15207.83 -15539.95 -15316.13 NA9 -16097.65 -15749.74 -15222.67 -15033.18 NA NA -15208.77 -15566.15 -15350.26 NA10 -16090.24 -15726.55 -15199.41 -15039.04 NA NA -15230.21 -15620.28 -15527.11 NA
plot(a,bupa[,1:6])
PERU 2009 Mineria de Datos Edgar Acuna 52
000
0-1
500
-160
00
BIC
-170
00
B
-180
00
EIIVIIEEIVEIEVI
VVEEEEVEVV
2 4 6 8 10
number of components
V1
20 60 100 20 60
90
V1
70
100
V2
2060
V2
V3 100
V3
050
60
V4
20
V4
250
V5
70 90 0 50 100 0 100 250
010
0V5