13
Métricas de distancia
Distancia de Minkowski
Distancia de Manhattan = 12
Distancia Euclídea ? 8.5
Distancia de Chebyshev = 6
Medidas de similitud
14
Métricas de distancia
Distancia de Minkowski d(i,j) ? 0
Propiedad reflexiva d(i,i) = 0
Propiedad simétrica d(i,j) = d(j,i)
Desigualdad triangular d(i,j) ? d(i,k)+d(k,j)
Medidas de similitud
15
Métricas de distancia
Distancia de Chebyshev
También conocidacomo distancia detablero de ajedrez(chessboard distance):Número demovimientosque el rey ha de hacerpara llegar de unacasilla a otra en untablero de ajedrez.
Medidas de similitud
16
Métricas de distancia
Distancia de Mahalanobis
Considera lascorrelacionesentre variables.
No depende de laescala de medida.
Medidas de similitud
17
Métricas de distancia
Distancia de Bhattacharyya
Medidas de similitud
18
Métricas de distancia
Distancia de edición = Distancia de Levenshtein
Número de operaciones necesariopara transformar una cadena en otra.
d(“data mining”, “data minino”) = 1
d(“efecto”, “defecto”) = 1
d(“poda”, “boda”) = 1
d(“night”,”natch”) = d(“natch”,”noche”) = 3
Aplicaciones: Correctores ortográficos, reconocimiento de voz, detección de plagios, análisis de ADN…
Para datos binarios: Distancia de Hamming
Medidas de similitud
19
Métricas de distancia
Vecinos compartidos
“Mutual Neighbor Distance”
donde NN(xi,xj) es el número de vecinode xj con respecto a xi
Medidas de similitud
(Gp:) i
(Gp:) j
(Gp:) i
(Gp:) j
(Gp:) 4
20
Medidas de correlación
Producto escalar
“Cosine similarity”
Coeficiente de Tanimoto
Medidas de similitud
21
Medidas de correlación
Índice de correlación
Medidas de similitud
22
Modelos basados en Teoría de Conjuntos
Modelo de Tversky
Modelo de Restle
Intersección
Medidas de similitud
23
Modelos basados en Teoría de Conjuntos
Modelo proporcional
Modelo de Gregson = Coeficiente de Jaccard
Distancia de Tanimoto
Medidas de similitud
24
Medidas de similitud
25
Métodos de agrupamiento
Requisitos del algoritmo “perfecto”
Escalabilidad
Manejo de distintos tipos de datos
Identificación de clusters con formas arbitrarias
Número mínimo de parámetros
Tolerancia frente a ruido y outliers
Independencia con respecto al orden de presentación de los patrones de entrenamiento
Posibilidad de trabajar en espacios con muchas dimensiones diferentes
Capacidad de incorporar restricciones especificadas por el usuario (“domain knowledge”)
Interpretabilidad / Usabilidad
26
Métodos de agrupamiento
Tipos de algoritmos de clustering
Agrupamiento por particiones
k-Means, CLARANS
Clustering jerárquico
BIRCH, ROCK, CHAMELEON
Métodos basados en densidad
DBSCAN
…
27
(Gp:) Datos agrupados
Métodos de agrupamiento
Clustering por particiones
Datos originales
28
Métodos de agrupamiento
Clustering jerárquico
Tradicional
No tradicional
DENDOGRAMA
29
Métodos de agrupamiento
Métodos basados en densidad
Un cluster en una región densa de puntos, separada por regiones poco densas de otras regiones densas.
Útiles cuando los clusters tienen formas irregulares, están entrelazados o hay ruido/outliers en los datos.
30
k-Means
Algoritmo de agrupamiento por particiones(MacQueen, 1967)
Número de clusters conocido (k)
Cada cluster tiene asociado un centroide (centro geométrico del cluster).
Los puntos se asignan al cluster cuyo centroide esté más cerca (utilizando cualquier métrica de distancia).
Iterativamente, se van actualizando los centroides en función de las asignaciones de puntos a clusters, hasta que los centroides dejen de cambiar.
Complejidad O(n*k*I*d)donde n es el número de datos, k el número de clusters,I el número de iteraciones y d el número de atributos
31
k-Means
32
k-Means
33
k-Means
34
k-Means
35
k-Means
(Gp:) Óptimo local
(Gp:) Solución óptima
Puntos originales
36
k-Means
Ejercicio
Agrupar los 8 puntos de lafigura en 3 clusters usandoel algoritmo de las K medias.
Centroides iniciales:A1, A7 y A8
Métricas de distancia:
Distancia euclídea
Distancia de Manhattan
Distancia de Chebyshev
37
k-Means
Ejercicio resuelto
Distancia euclídea
38
k-Means
Ejercicio resuelto
Distancia euclídea
Primera iteración Segunda iteración
39
k-Means
Ejercicio resuelto
Distancia euclídea
Tercera iteración Configuración final
40
k-Means
DEMO: K-Means
http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/AppletKM.html
41
k-Means
Ventaja
Eficiencia O(n·k·I·d) vs. PAM O(I·k(n-k)2)
CLARA O(ks2+k(n-k))
Desventajas
Termina en un óptimo local: El resultado depende de la selección inicial de centroides.
Necesidad de conocer el número de agrupamientos k
Incapacidad para detectar ruido / identificar outliers.
No resulta adecuado para detectar clusters no convexos
Si tenemos datos de tipo categórico, ¿cómo calculamos la media?
42
k-Means
Clusters dedistinto tamaño
Clusters dedistinta densidad
Clustersno convexos
43
k-Means
Variantes
GRASP [Greedy Randomized Adaptive Search Procedure] para evitar óptimos locales.
k-Modes (Huang’1998) utiliza modas en vez de medias (para poder trabajar con atributos de tipo categórico).
k-Medoids utiliza medianas en vez de medias para limitar la influencia de los outliers
vg. PAM (Partitioning Around Medoids, 1987)
CLARA (Clustering LARge Applications, 1990)
CLARANS (CLARA + Randomized Search, 1994)
44
k-Means
DEMO: Fuzzy C-Means
http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/AppletFCM.html
45
Clustering jerárquico
DENDROGRAMA: La similitud entre dos objetos viene dada por la “altura” del nodo común más cercano.
46
Clustering jerárquico
El DENDROGRAMA nos puede ayudar a determinar el número adecuado de agrupamientos (aunque normalmente no será tan fácil).
47
Clustering jerárquico
El DENDROGRAMAtambién nos puede servir para detectar outliers.
Outlier
48
Clustering jerárquico
En lugar de establecer de antemano el número de clusters, tenemos que definir un criterio de parada
(Gp:) 0
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) b
(Gp:) d
(Gp:) c
(Gp:) e
(Gp:) a
(Gp:) a b
(Gp:) d e
(Gp:) c d e
(Gp:) a b c d e
(Gp:) 4
(Gp:) 3
(Gp:) 2
(Gp:) 1
(Gp:) 0
(Gp:) aglomerativo
(AGNES)AGglomerative NESting
(Gp:) divisivo
(DIANA)Divisive ANAlysis
49
Clustering jerárquico
¿Cómo medir la distancia entre clusters?
MINsingle-link
MAXcompletelinkage(diameter)
50
Clustering jerárquico
¿Cómo medir la distancia entre clusters?
Promedio
Centroidesp.ej. BIRCH
(Gp:) ?
(Gp:) ?
51
Clustering jerárquico
Ejercicio
Utilizar un algoritmo aglomerativo de clustering jerárquico para agrupar los datos descritos por la siguiente matriz de distancias:
Variantes:
Single-link (mínima distancia entre agrupamientos)
Complete-link (máxima distancia entre agrupamientos)
52
Clustering jerárquico
Ejercicio resuelto
Single-link
Complete-link
53
Clustering jerárquico
DEMO: Algoritmo aglomerativo
http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/AppletH.html
54
Clustering jerárquico
Datos sintéticos (4 clusters): Single-link
55
Clustering jerárquico
Datos sintéticos (4 clusters): Complete-link
56
Clustering jerárquico
Datos sintéticos (aleatorios): Single-link
57
Clustering jerárquico
Datos sintéticos (aleatorios): Complete-link
58
Clustering jerárquico
Principal inconveniente del clustering jerárquico:
Baja escalabilidad = O(n2)
Algoritmos “escalables”:
BIRCH: Balanced Iterative Reducing and Clustering using Hierarchies (Zhang, Ramakrishnan & Livny, SIGMOD’1996)
ROCK: RObust Clustering using linKs (Guha, Rastogi & Shim, ICDE’1999)
CURE: Clustering Using REpresentatives(Guha, Rastogi & Shim, SIGMOD’1998)
CHAMELEON: Hierarchical Clustering Using Dynamic Modeling (Karypis, Han & Kumar, 1999)
59
Clustering jerárquico
CURE
60
Clustering jerárquico
Agrupamientoscon distintasdensidades
CURE
61
Clustering jerárquico
CHAMELEON
Partición del grafo
Combinar particiones
Clusters finales
62
Clustering jerárquico
CHAMELEON
63
Density-based Clustering
Criterio de agrupamiento local:
Densidad de puntos
Región densas de puntos separadas de otras regiones densas por regiones poco densas
Características
Identifica clusters de formas arbitrarias.
Robusto ante la presencia de ruido
Escalable: Un único recorrido del conjunto de datos
64
Density-based Clustering
Algoritmos
DBSCAN: Density Based Spatial Clustering of Applications with Noise (Ester et al., KDD’1996)
OPTICS: Ordering Points To Identify the Clustering Structure (Ankerst et al. SIGMOD’1999)
DENCLUE: DENsity-based CLUstEring(Hinneburg & Keim, KDD’1998)
CLIQUE: Clustering in QUEst(Agrawal et al., SIGMOD’1998)
SNN (Shared Nearest Neighbor) density-based clustering(Ertöz, Steinbach & Kumar, SDM’2003)
65
Density-based Clustering
Ejercicio
Agrupar los 8 puntosde la figura utilizandoel algoritmo DBSCAN.
Número mínimo de puntosen el “vecindario”:
MinPts = 2
Radio del “vecindario”:
Epsilon ?
66
Density-based Clustering
Ejercicio resuelto
Distancia euclídea
67
Density-based Clustering
Ejercicio resuelto Epsilon =
A1, A2 y A7 no tienen vecinos en su vecindario,
por lo que se consideran “outliers” (no están en zonas densas):
68
Density-based Clustering
Ejercicio resuelto Epsilon =
Al aumentar el valor del parámetro Epsilon,
el vecindario de los puntos aumenta y todos quedan agrupados:
69
Density-based Clustering
DEMO: DBSCAN et al.
http://www.cs.ualberta.ca/~yaling/Cluster/Applet/Code/Cluster.html
70
Density-based Clustering
DBSCAN … cuando funciona bien
(Gp:) Clusters
71
Density-based Clustering
DBSCAN sensible al valor inicial de sus parámetros
72
Density-based Clustering
SNN density-based clustering… O(n2)
(Gp:) i
(Gp:) j
(Gp:) i
(Gp:) j
(Gp:) 4
73
Grids multiresolución
Otros métodos
74
Grids multiresolución
STING, a STatistical INformation Grid approach(Wang, Yang & Muntz, VLDB’1997)
WaveCluster, basado en wavelets(Sheikholeslami, Chatterjee & Zhang, VLDB’1998)
CLIQUE: CLustering In QUEst(Agrawal et al., SIGMOD’1998)
Otros métodos
75
Clustering basado en modelos
Ajustar los datos a un modelo matemático
Se supone que los datos provienen de la superposición de varias distribuciones de probabilidad.
Algoritmos
Estadística: EM [Expectation Maximization], AutoClass
Clustering conceptual (Machine Learning):COBWEB, CLASSIT
Redes neuronales:SOM [Self-Organizing Maps]
Otros métodos
76
Clustering con restricciones
p.ej. Clustering con obstáculos
Posibles aplicaciones:
Distribución de cajeros automáticos/supermercados…
Otros métodos
77
Subspace clustering
La dimensionalidad de los datos
¿Por qué es un problema?
Los datos en una dimensión están relativamente cerca
Al añadir una nueva dimensión, los datos se alejan.
Cuando tenemos muchas dimensiones, las medidas de distancia no son útiles (“equidistancia”).
78
Subspace clustering
La dimensionalidad de los datos
Transformación de características (PCA, SVD)útil sólo si existe correlación/redundancia
Selección de características (wrapper/filter)útil si se pueden encontrar clusters en subespacios
“Subspace clustering”Buscar clusters en todos los subespacios posibles.
vg. CLIQUE (Agrawal et al., SIGMOD’1998)
79
Subspace clustering
80
Subspace clustering
81
Subspace clustering
DEMO: CLIQUE et al.
http://www.cs.ualberta.ca/~yaling/Cluster/Applet/Code/Cluster.html
82
Validación
¿Cómo se puede evaluar la calidad de los clusters obtenidos?
Depende de lo que estemos buscando…
Hay situaciones en las que nos interesa:
Evitar descubrir clusters donde sólo hay ruido.
Comparar dos conjuntos de clusters alternativos.
Comparar dos técnicas de agrupamiento
83
Validación
Criterios externos (aportando información adicional)
p.ej. entropía/pureza (como en clasificación)
Criterios internos (a partir de los propios datos),
p.ej. SSE (“Sum of Squared Error”)
para comparar clusters
para estimar el número de clusters
Otras medidas:cohesión, separación, coeficientes de silueta…
84
Validación
¿Cuál es el número adecuado de agrupamientos?
p.ej. SSE (“Sum of Squared Error”)
k = 1 k = 2 k = 3
J = 873.0 J = 173.1 J = 133.6
85
Validación
¿Cuál es el número adecuado de agrupamientos?
p.ej. SSE (“Sum of Squared Error”)
El codo en k=2 sugiere que éste es el valor adecuado para el número de agrupamientos.
(Gp:) 0.00E+00
(Gp:) 1.00E+02
(Gp:) 2.00E+02
(Gp:) 3.00E+02
(Gp:) 4.00E+02
(Gp:) 5.00E+02
(Gp:) 6.00E+02
(Gp:) 7.00E+02
(Gp:) 8.00E+02
(Gp:) 9.00E+02
(Gp:) 1.00E+03
(Gp:) 1
(Gp:) 2
(Gp:) 3
(Gp:) 4
(Gp:) 5
(Gp:) 6
k
J
86
Validación
87
Validación
88
Validación
Matriz de similitud
Ordenamos los datos en la matriz de similitud con respecto a los clusters en los que quedan los datos e inspeccionamos visualmente…
89
Validación
Matriz de similitud
Clusters en datos aleatorios
(DBSCAN y k-Means)
90
Validación
Matriz de similitud
DBSCAN
91
Bibliografía
R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. Automatic subspace clustering of high dimensional data for data mining applications. SIGMOD'98
M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander. Optics: Ordering points to identify the clustering structure, SIGMOD’99.
L. Ertöz, M. Steinbach, and V. Kumar. Finding clusters of different sizes, shapes, and densities in noisy, high-dimensional data, SDM’2003
M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases. KDD'96.
D. Fisher. Knowledge acquisition via incremental conceptual clustering. Machine Learning, 2:139-172, 1987.
D. Gibson, J. Kleinberg, and P. Raghavan. Clustering categorical data: An approach based on dynamic systems. VLDB’98
S. Guha, R. Rastogi, and K. Shim. Cure: An efficient clustering algorithm for large databases. SIGMOD'98.
S. Guha, R. Rastogi, and K. Shim. ROCK: A robust clustering algorithm for categorical attributes. In ICDE'99, Sydney, Australia, March 1999.
92
Bibliografía
A. Hinneburg, D.l A. Keim: An Efficient Approach to Clustering in Large Multimedia Databases with Noise. KDD’98.
G. Karypis, E.-H. Han, and V. Kumar. CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling. COMPUTER, 32(8): 68-75, 1999.
L. Parsons, E. Haque and H. Liu, Subspace Clustering for High Dimensional Data: A Review , SIGKDD Explorations, 6(1), June 2004
G. Sheikholeslami, S. Chatterjee, and A. Zhang. WaveCluster: A multi-resolution clustering approach for very large spatial databases. VLDB’98.
A. K. H. Tung, J. Hou, and J. Han. Spatial Clustering in the Presence of Obstacles , ICDE'01
H. Wang, W. Wang, J. Yang, and P.S. Yu. Clustering by pattern similarity in large data sets, SIGMOD’ 02.
W. Wang, Yang, R. Muntz, STING: A Statistical Information grid Approach to Spatial Data Mining, VLDB’97.
T. Zhang, R. Ramakrishnan, and M. Livny. BIRCH : an efficient data clustering method for very large databases. SIGMOD'96.
93
Créditos
Jiawei Han (University of Illinois at Urbana-Champaign): “Data Mining: Concepts and Techniques”, capítulo 7, 2006
Pang-Ning Tan (Michigan State University), Michael Steinbach & Vipin Kumar (University of Minnesota): “Introduction to Data Mining”, capítulos 8 y 9, 2006
94
Apéndice: Notación O
El impacto de la eficiencia de un algoritmo…
n 10 100 1000 10000 100000
O(n) 10ms 0.1s 1s 10s 100s
O(n·log2 n) 33ms 0.7s 10s 2 min 28 min
O(n2) 100ms 10s 17 min 28 horas 115 días
O(n3) 1s 17min 12 días 31 años 32 milenios
 Página anterior | Volver al principio del trabajo | Página siguiente  |