Clustering

Aprendizaje no supervisado: agrupamiento de datos.

Clase 8 · Bases de Datos Masivas (11088) · UNLu

Temas

1. ¿Qué es clustering? · motivación, definición y aplicaciones
2. Medidas de distancia y similitud · numéricas, binarias y categóricas
3. K-Means · algoritmo, óptimos locales y ejemplo
4. Clustering jerárquico · dendrogramas y métodos de linkage
5. Evaluación y elección de K · SS, método del codo y silueta

​

​

1. ¿Qué es clustering?

Aprendizaje Supervisado vs. No Supervisado

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

​

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

(Larose, 2014)

¿Por qué el clustering es un problema difícil?

• 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

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

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

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

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

2. Medidas de distancia y similitud

Variables Numéricas

Distancia Euclídea

Distancia de Manhattan

Distancia Minkowski

​

Variables Binarias:

Coeficiente de Jaccard

​

Variables Categóricas

​

Medidas de distancia/similitud

Es necesario Normalizar/Estandarizar los datos:

• z-score
• min-max
• decimal scale

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.

Coeficiente de Jaccard

Distancia de dos variables binarias

Similitud

​

​

​

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

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

3. K-Means

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

¿Cómo funciona K-Means?

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

C₁...C_k

• Cada observación pertenece exactamente 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.

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 asignadas al cluster k.
• Asigna cada una de las observaciones al cluster cuyo centroide es más cercano (donde “cercano” se define utilizando la distancia Euclídea)

Ejemplo del algoritmo K-Means

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.

​

Solución Mala

Solución Buena

Ejemplo: K-Means

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

4. Clustering jerárquico

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

Aglomerativo vs. Divisivo

• 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 divisivos (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.

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.

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.

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.

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.

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.

¿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 el cluster (5, 7) y el punto 8?
• Hay 4 opciones:
• Complete Linkage
• Single Linkage
• Average Linkage
• Centroid Linkage

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.

Criterio de Distancia y Similitud

Distancia

​

​

​

​

​

​

Similitud

Ejemplo: Single Linkage

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

Dendrograma Resultante en K=6

​

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

Importancia del Linkage

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

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

5. Evaluación y elección de K

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 del codo (Elbow)

• Ejemplo para N=136

Método del codo (Elbow)

• El método de Elbow permite seleccionar un k

Método del codo (Elbow)

Método del codo (Elbow)

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 el menor promedio de distancias de i a las observaciones de otro cluster (el más cercano, distinto del suyo).

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

Coeficiente de Silueta: interpretación

• 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 clusters
• s(i) ≈ −1, la observación i está mal asignada a su cluster

Coeficiente de Silueta: gráfico

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

​

• Larose, D. T., & Larose, C. D. (2014). Discovering knowledge in data: an introduction to data mining (2nd ed.). Wiley.