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 siguiente |