CLUSTERING

Bases de Datos Masivas

2020

​

1

Temas

• ¿Qué es clustering?
• K-Means Clustering
• Hierarchical Clustering

2

​

​

¿QUÉ ES CLUSTERING?

3

Aprendizaje Supervisado vs. No Supervisado

• Aprendizaje Supervisado: tanto X como Y son conocidos
• Aprendizaje No Supervisado solo conozco X

​

4

Supervised Learning

Unsupervised Learning

Problema del agrupamiento

Dada una nube de puntos en un espacio, queremos entender cuál es la estructura de esa nube.

Problema del agrupamiento

Dado un conjunto de puntos, con una noción de distancia entre ellos, se realiza un agrupamiento de los puntos en una N cantidad de subconjuntos, de modo que:

​

• Los miembros de un grupo están cerca (similares entre sí).
• Los miembros de los otros grupos son bien diferentes.

Generalmente:

• Los puntos están en un espacio de dimensión alta.
• La similitud se define utilizando una medida de distancia.

Euclidiana, coseno, Jaccard, distancia de edición, ...

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

Clustering: Problema Hard ¿Por qué?

• El agrupamiento en dos dimensiones parece fácil
• El agrupamiento de pequeñas cantidades de datos parece fácil
• Y en la mayoría de los casos, las apariencias no engañan

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

Pero la mayoría de los problemas no tienen 2 dimensiones, sino que pueden tener 10, 100 o miles de dimensiones

En espacios de alta dimensionalidad todo se ve diferente:

• La Maldición de la Dimensionalidad:
• Una manifestación de la "maldición" es que en dimensiones altas, casi todos los pares de puntos están igualmente alejados unos de otros.

Problemas de Clustering: Galaxias

8

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

• Datos: Un catálogo de 2 mil millones de "cuerpos celestes" representados por su radiación en 7 dimensiones (bandas de frecuencia)

• Problema: Cluster en objetos similares, por ejemplo: galaxias, las estrellas cercanas, cuásares, etc.

Proyecto:

Sloan Digital Sky Survey

Problemas de Clustering: CDs de música

9

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

• Intuitivamente: La música se divide en categorías, los clientes prefieren unas pocas categorías.
• ¿Pero qué son realmente las categorías?
• Representar un CD por el conjunto de clientes que lo compraron:
• CDs similares tienen un conjunto de clientes similares y viceversa.

Problemas de Clustering: CDs de música

10

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

Espacio de todos los CDs:

• Piense en un espacio con una dimensión para cada cliente.
• Los valores en una dimensión pueden ser 0 o 1 solamente.
• Un CD es un punto en este espacio (x₁, x₂, ..., x_k), donde x_i = 1 si y sólo si el i-ésimo cliente compró el CD

Para Amazon, la dimensión es de decenas de millones

Tarea: Buscar clusters de CDs similares

Clustering

• Clustering hace referencia al conjunto de técnicas para buscar subgrupos (o clusters) en un conjunto de datos.
• Un buen clustering permite que las observaciones dentro de un grupo sean similares pero entre los grupos sean bien diferentes.
• El clustering también es llamado segmentación de datos en algunas aplicaciones.
• Se realizan particiones de grandes conjuntos de datos, en clusters de acuerdo a su similitud.

​

​

11

Clustering

(Larose, 2014)

Métodos de Clustering

• Existen muchos tipos de métodos de agrupamiento diferentes.

​

• Dos de los más utilizados son:
• K-Means Clustering
• Hierarchical Clustering

13

Métodos de Clustering

Jerárquico:

• Aglomerativo (de abajo hacia arriba):
• Inicialmente, cada punto es un cluster
• Combina repetidamente los dos grupos "más cercanos" en uno.
• Divisivo (de arriba abajo):
• Comienza con un cluster y de forma recursiva lo va dividiendo.

Asignación de puntos (k-means):

• Se mantiene un conjunto de clusters
• Cada punto pertenece al grupo de "más cercano"

14

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

K-MEANS CLUSTERING

15

K-Means Clustering

• Para realizar un agrupamiento por K-Means, debemos especificar en primer lugar la cantidad de clusters (K) deseados.
• Entonces el algoritmo de K-means asignará cada una de las observaciones exactamente a uno solo de los K clusters

16

¿Cómo funciona K-medias?

• Nos gustaría particionar ese conjunto de datos en K grupos

C₁...C_k

• Cada una de las observaciones pertenecen al menos a uno de los K clusters
• Los clusters no están solapados (non-overlapping), es decir, no hay observaciones que pertenezcan a más de un cluster
• El objetivo es tener una mínima variación dentro del cluster, es decir, los elementos dentro de un cluster deberían ser tan similares como sea posible.
• Una forma de lograr esto es reducir al mínimo la suma de todas las distancias euclidianas por pares al cuadrado entre las observaciones en cada cluster.

17

Algoritmo K-Means

• Paso Inicial: De forma aleatoria asignar cada observación a uno de los K clusters

​

• Iterar hasta que la asignación de clusters deje de modificarse:

​

• Para cada uno de los K clusters, calcular el centroide. El centroide del k-ésimo cluster es la media de las observaciones etiquetadas como K.
• Asigna cada una de las observaciones al cluster cuyo centroide es más cercano (donde “cercano” se define utilizando la distancia Euclídea)

18

Ejemplo del algoritmo K-means

19

Calcula los centroides para los clusters actuales

Óptimos locales

• El algoritmo K-means puede atascarse en "óptimos locales" y no encontrar la mejor solución
• El resultado va a estar atado a la imputación inicial
• Para encontrar una buena solución tenemos que correr varias veces con distintas configuraciones iniciales.

​

20

Solución Mala

Solución Buena

Ejemplo: K-mean

Imagen con 10 canales

1000 puntos al azar

B1,B2,...,B10

p1 5,8,....,21

p2 15,3,....,3

p3 53,7,....,12

p4 4,2,....,21

.

.

p1000 31,34,....,2

k = 3

k = 4

k = 10

HIERARCHICAL CLUSTERING

22

Clustering Jerárquico

• K-Means requiere elegir un número de clusters

​

• El problema de seleccionar un K está lejos de ser un tema simple.

​

• Ahora, si no queremos pasar por el proceso de selección de K podemos utilizar Clustering Jerárquico

​

• Los clusters jerárquicos son construidos a partir de una representación gráfica basada en árboles llamada Dendrograma

23

Clustering Jerárquico

• Clustering aglomerativos (Bottom-Up).
• Comienzan el análisis con tantos clusters como observaciones se tienen.
• A partir de las unidades iniciales se forman grupos, de forma ascendente hasta que queda un solo cluster.
• Clustering disociativos (Top-Down).
• Comienzan con un único cluster que engloba a todas las observaciones.
• Y se realizan repetidas divisiones hasta llegar a tantas agrupaciones como casos tratados.

24

Dendrograma

• Juntamos los puntos más cercanos Ejemplo: 5 y 7
• La altura de fusión (en el eje vertical) indica cuán similares son los puntos
• Luego de ser fusionados, se los trata como una simple observación y el algoritmo continúa.

25

Métrica

Similitud/Disimilitud

Interpretación

• Cada una de las hojas del dendrograma representa una de las 45 observaciones.
• Cuando nos movemos hacia arriba las hojas se van fusionando.
• Esto corresponde a observaciones que son similares unas a otras.
• A medida que avanzamos más arriba en el árbol, un creciente número de observaciones han fusionado.
• Las dos observaciones que se unieron previamente (más abajo) son las más similares entre sí.
• Las observaciones que se fusionan al final, son muy diferentes de las primeras en fusionarse.

26

Tenemos 45

observaciones

Elegir los Clusters

• Para elegir los clusters podemos trazar una línea que cruce el dendrograma.
• Podemos obtener un número de clusters dependiendo de las intersecciones de la línea.

27

1 Cluster

2 Clusters

3 Clusters

Enfoque aglomerativo

• El dendrograma se genera de la siguiente manera:
• Comienza con cada uno de los puntos como un cluster separado (n clusters)
• Calcula una medida de disimilitud entre los puntos / clusters
• Fusiona dos clusters que son más similares de manera que ahora tenemos n – 1 clusters.
• A continuación fusiona los siguientes más similares entonces nos quedan ahora n – 2 clusters.
• Continúa hasta que nos queda un solo cluster.

28

Casos

Clusters

Un ejemplo

• Inicia con 9 clusters
• Une 5 y 7
• Une 6 y 1
• Une el cluster (5,7) con 8.
• Continua hasta que todas las observaciones están unidas.

29

¿Cómo definimos disimilitud?

• La implementación de clustering jerárquico implica resolver un problema obvio que es...

​

• ¿Cómo hacer para definir la disimilitud o amalgamiento (o linkage) entre un cluster cluster (5 , 7) y el punto 8?
• Hay 4 opciones:
• Complete Linkage
• Single Linkage
• Average Linkage
• Centroid Linkage

30

Métodos de Linkage: Distancia entre Clusters

• Complete Linkage: Distancia máxima o similitud mínima entre observaciones
• Single Linkage: Distancia mínima o similitud máxima entre observaciones
• Average Linkage: Distancia promedio entre las observaciones
• Centroid: Distancias entre centroides de las observaciones.

31

Importancia del Linkage

• Aquí tenemos los tres resultados con los mismos datos.
• La diferencia en los dendrogramas se atribuye al Linkage utilizado.

32

• Linkage Complete y Average tienden a producir racimos de tamaño uniforme mientras que Single Linkage tiende a producir racimos extendidos para que las hojas individuales se fusionen una a una.

Criterio de Distancia y Similitud

33

Distancia

​

​

​

​

​

​

Similitud

Ejemplo: Single Linkage

34

Matriz Inicial de distancias

Nivel K=1

Nivel K=2

Nivel K=3

Nivel K=4

Nivel K=5

Nivel K=6

Ejemplo: Single Linkage

35

Dendrograma Resultante en K=6

​

En la etapa K-ésima quedan formados n – K clusters

Variables Numéricas

Distancia Euclídea

Distancia de Manhattan

Distancia Minkowski

​

Variables Binarias:

Coeficiente de Jaccard

​

Variables Categóricas

​

36

Medidas de distancia/similitud

Es necesario Normalizar/Estandarizar los datos:

• z-score
• min-max
• decimal scale

37

Variables Numéricas

Distancia Euclídea

Distancia de Manhattan

Distancia Minkowski

Los requisitos para una función de distancia son:

• Las distancias son siempre no negativas
• Sólo la distancia entre un punto y sí mismo es 0.
• La distancia es simétrica; no importa en qué orden se tiene en cuenta los puntos al calcular su distancia.
• Las medidas de distancia obedecen a la desigualdad triangular; la distancia de X a Y a Z nunca es menor que la distancia que va desde X a Z directamente.

38

Coeficiente de Jaccard

Distancia de dos variables binarias

Similitud

​

​

​

sim(i, j) es conocido como coeficiente de Jaccard

39

Variables Categóricas

Distancia de dos variables categóricas

​

donde:

p: es el total de variables

m: es el total de coincidencias

​

Ejemplo para test-I

MÉTRICAS DE EVALUACIÓN

40

Suma de Cuadrados

• Buscamos minimizar la Suma de Cuadrados (SS) dentro de los clusters.
• SS son las diferencias con respecto a los centros
• Cuando utilizamos k-means obtenemos:
• totss: Suma total de cuadrados
• withinss: Suma de cuadrados dentro de cada cluster.
• Es una por cluster.
• betweenss: es la diferencia entre totss – sum(withinss)
• betweenss/totss es la medida de referencia que indica cuán bueno es el agrupamiento.

Con k-means son las distancias a los centroides.

En jerárquicos… usamos la matriz de distancias

Método Elbow

• Ejemplo para N=136

Método Elbow

• El método de Elbow permite seleccionar un k

Método Elbow

Método Elbow

46

Coeficiente de Silueta

• El coeficiente de Silueta es una métrica para evaluar la calidad del agrupamiento obtenido con algoritmos de clustering.
• El objetivo de Silueta es identificar cuál es el número óptimo de agrupamientos.

​

Donde:

• a es el promedio de las disimilitudes (o distancias) de la observación i con las demás observaciones del cluster al que pertenece i
• b es la distancia mínima a otro cluster que no es el mismo en el que está la observación i.

Ese cluster es la segunda mejor opción para i y se lo denomina vecindad de i.

47

Evaluación: Coeficiente de Silueta

• El valor de s(i) puede ser obtenido combinando los valores de a y b como se muestra a continuación:

• El coeficiente de Silueta es un valor comprendido entre -1 y 1.

Resumiendo:

• s(i) ≈ 1, la observación i está bien asignada a su cluster

• s(i) ≈ 0, la observación i está entre dos cluster

• s(i) ≈ −1, la observación i está mal asignada a su cluster

48

Evaluación: Coeficiente de Silueta

Gráfico de ancho de Silueta

REFERENCIAS

• Basado principalmente en: Clustering Chapter 10. IOM 530: Intro. to Statistical Learning. (Traducción Libre)

​

• Han, J., Kamber, M., & Pei, J. (2011). Data mining: concepts and techniques: concepts and techniques. Elsevier.

​

• J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

49