observacion_a <- c(4, 4.5, 4, 7.5, 7, 6, 5, 5.5, 5, 6)
observacion_b <- c(4, 4.5, 4, 7.5, 7, 6, 5, 5.5, 5, 6) + 4
datos <- data.frame(observacion = rep(c("a", "b"), each = 10),
valor = c(observacion_a, observacion_b),
predictor = 1:10)
library(ggplot2)
ggplot(data = datos, aes(x = as.factor(predictor), y = valor,
colour = observacion)) +
geom_path(aes(group = observacion)) +
geom_point() +
geom_line(aes(group = predictor), colour = "firebrick", linetype = "dashed") +
labs(x = "predictor") +
theme_bw() +
theme(legend.position = "none")Inteligencia Analítica de Datos con R
Clustering: aprendizaje no supervisado
Msc. Roberto Trespalacios
Universidad Tecnológica de Bolivar
6/8/23
Clustering: aprendizaje no supervisado
Introducción
El término clustering hace referencia a un amplio abanico de técnicas no supervisadas cuya finalidad es encontrar patrones o grupos (clusters) dentro de un conjunto de observaciones.
- Las particiones se establecen de forma que, las observaciones que están dentro de un mismo grupo, son similares entre ellas y distintas a las observaciones de otros grupos.
- Se trata de un método no supervisado, ya que el proceso ignora la variable respuesta que indica a que grupo pertenece realmente cada observación (si es que existe tal variable).
- Esta característica diferencia al clustering de las técnicas supervisadas, que emplean un set de entrenamiento en el que se conoce la verdadera clasificación.
Clustering y sus usos
Dada la utilidad del clustering en disciplinas muy distintas (genómica, marketing, geo-estadística, …), se han desarrollado multitud de variantes y adaptaciones de sus métodos y algoritmos. Pueden diferenciarse tres grupos principales:
Partitioning Clustering: Este tipo de algoritmos requieren que el usuario especifique de antemano el número de clusters que se van a crear (K-means, K-medoids, CLARA).
Hierarchical Clustering: Este tipo de algoritmos no requieren que el usuario especifique de antemano el número de clusters. (agglomerative clustering, divisive clusterig).
Métodos que combinan o modifican los anteriores (hierarchical K-means, fuzzy clustering, model based clustering y density based clustering).
Paquetes o librerías usadas en clustering.
En el entorno de programación R existen múltiples paquetes que implementan algoritmos de clustering y funciones para visualizar sus resultados. En este documento se emplean los siguientes:
stats: contiene las funcionesdist()para calcular matrices de distancias,kmeans(),hclust(),cuttree()para crear los clusters yplot.hclust()para visualizar los resultados.cluster,mclust: contienen múltiples algoritmos de clustering y métricas para evaluarlos.factoextra: extensión basada enggplot2para crear visualizaciones de los resultados de clustering y su evaluación.dendextend: extensión para la customización de dendrogramas.
Medidas de distancia
Todos los métodos de clustering tienen una cosa en común, para poder llevar a cabo las agrupaciones necesitan definir y cuantificar la similitud entre las observaciones.
- El término distancia se emplea dentro del contexto del clustering como cuantificación de la similitud o diferencia entre observaciones.
- Si se representan las observaciones en un espacio p dimensional, siendo p el número de variables asociadas a cada observación, cuando más se asemejen dos observaciones más próximas estarán, de ahí que se emplee el término distancia.
- La característica que hace del clustering un método adaptable a escenarios muy diversos es que puede emplear cualquier tipo de distancia, lo que permite al investigador escoger la más adecuada para el estudio en cuestión. A continuación, se describen algunas de las más utilizadas.
Distancia euclídea
La distancia euclídea entre dos puntos \(p\) y \(q\) se define como la longitud del segmento que une ambos puntos. En coordenadas cartesianas, la distancia euclídea se calcula empleando el teorema de Pitágoras. Por ejemplo, en un espacio de dos dimensiones en el que cada punto está definido por las coordenadas \((x,y)\) , la distancia euclídea entre p y q viene dada por la ecuación:
\[d_{euc}(p,q) = \sqrt{(x_p - x_q)^2 + (y_p - y_q)^2}\]
Esta ecuación puede generalizarse para un espacio euclídeo n-dimensional donde cada punto está definido por un vector de n coordenadas: \(p=(p_1,p_2,p_3,...,p_n)\) y \(q=(q_1,q_2,q_3,...,q_n)\).
\[d_{euc}(p,q) = \sqrt{(p_1 - q_1)^2 + (p_2 - q_2)^2 +...+(p_n - q_n)^2} = \sqrt{ \sum_{i=1}^n (p_i - q_i)^2}\]
- Una forma de dar mayor peso a aquellas observaciones que están más alejadas es emplear la distancia euclídea al cuadrado.
- En el caso del clustering, donde se busca agrupar observaciones que minimicen la distancia, esto se traduce en una mayor influencia de aquellas observaciones que están más distantes.
Ejemplo de Distancia euclídea
La siguiente imagen muestra el perfil de dos observaciones definidas por 10 variables (espacio con 10 dimensiones).
- La distancia euclídea entre las dos observaciones equivale a la raíz cuadrada de la suma de las longitudes de los segmentos rojos que unen cada par de puntos.
- Tiene en cuenta por lo tanto el desplazamiento individual de cada una de las variables.
Distancia de Manhattan
- La distancia de Manhattan, también conocida como taxicab metric, rectilinear distance o L1 distance, define la distancia entre dos puntos p y q como el sumatorio de las diferencias absolutas entre cada dimensión.
- Esta medida se ve menos afectada por outliers (es más robusta) que la distancia euclídea debido a que no eleva al cuadrado las diferencias.
\[d_{man}(p,q) = \sum_{i=1}^n |(p_i - q_i)|\]
- La siguiente imagen muestra una comparación entre la distancia euclídea (segmento azul) y la distancia de manhattan (segmento rojo y verde) en un espacio bidimensional.
- Existen múltiples caminos para unir dos puntos con el mismo valor de distancia de manhattan, ya que su valor es igual al desplazamiento total en cada una de las dimensiones.
Ejemplo Distancia de Manhattan
A continuación se presenta un ejemplo de la distancia Manhattan
datos <- data.frame(observacion = c("a", "b"), x = c(2,7), y = c(2,7))
manhattan <- data.frame(
x = rep(2:6, each = 2),
y = rep(2:6, each = 2) + rep(c(0,1), 5),
xend = rep(2:6, each = 2) + rep(c(0,1), 5),
yend = rep(3:7, each = 2))
manhattan_2 <- data.frame(
x = c(2, 5, 5, 7),
y = c(2, 2, 4, 4),
xend = c(5, 5, 7, 7),
yend = c(2, 4, 4, 7))Veamos el gráfico de las diferentes distancias.
ggplot(data = datos, aes(x = x, y = y)) +
geom_segment(aes(x = 2, y = 2, xend = 7, yend = 7), color = "blue", size = 1.2) +
geom_segment(data = manhattan, aes(x = x, y = y, xend = xend, yend = yend),
color = "red", size = 1.2) +
geom_segment(data = manhattan_2, aes(x = x, y = y, xend = xend, yend = yend),
color = "green3", size = 1.2) +
geom_point(size = 3) +
theme(panel.grid.minor = element_blank(),
panel.grid.major = element_line(size = 2),
panel.background = element_rect(fill = "gray",
colour = "white",
size = 0.5, linetype = "solid"))Correlación
La correlación es una medida de distancia muy útil cuando la definición de similitud se hace en términos de patrón o forma y no de desplazamiento o magnitud.
- ¿Qué quiere decir esto? En la imagen del apartado de la distancia euclídea, las dos observaciones tienen exactamente el mismo patrón, la única diferencia es que una de ellas está desplazada 4 unidades por encima de la otra.
- Si se emplea como medida de similitud 1 menos el valor de la correlación, ambas observaciones se consideran idénticas (su distancia es 0).
\[d_{cor}(p,q) = 1 - \text{correlacion}(p,q)\]
donde la correlación puede ser de distintos tipos (Pearson, Spearman, Kendall…) Correlación lineal.
En la siguiente imagen se muestra el perfil de 3 observaciones. Acorde a la distancia euclídea, las observaciones b y c son las más similares, mientras que acorde a la correlación de Pearson, las observaciones más similares son a y b.
Ejemplo de la correlación como distancia
A continuación se presenta un ejemplo de la correlación como distancia.
# datos
observacion_a <- c(4, 4.5, 4, 7.5, 7, 6, 5, 5.5, 5, 6)
observacion_b <- c(4, 4.5, 4, 7.5, 7, 6, 5, 5.5, 5, 6) + 4
observacion_c <- c(5, 5.5, 4.8, 5.4, 4.7, 5.6, 5.3, 5.5, 5.2, 4.8)
datos <- data.frame(observacion = rep(c("a", "b", "c"), each = 10),
valor = c(observacion_a, observacion_b, observacion_c),
predictor = 1:10)Veamos la distancia de euclidea
Ahora, 1 menos la distancia de la correlación
Este ejemplo pone de manifiesto que no existe una única medida de distancia que sea mejor que las demás, sino que, dependiendo del contexto, una será más adecuada que otra.
Jackknife correlation
- El coeficiente de correlación de Pearson resulta efectivo en ámbitos muy diversos.
- Sin embargo, tiene la desventaja de no ser robusto frente a outliers a pesar de que se cumpla la condición de normalidad.
- Si dos variables tienen un pico o un valle común en una única observación, por ejemplo, por un error de lectura, la correlación va a estar dominada por este registro a pesar de que entre las dos variables no haya correlación real alguna.
- Lo mismo puede ocurrir en la dirección opuesta.
- Si dos variables están altamente correlacionadas excepto para una observación, en la que los valores son muy dispares, entonces la correlación existente quedará enmascarada.
- Una forma de evitarlo es recurrir a la Jackknife correlation, que consiste en calcular todos los posibles coeficientes de correlación entre dos variables si se excluye cada vez una de las observaciones.
- El promedio de todas las Jackknife correlations calculadas atenua en cierta medida el efecto del outlier.
\[\bar{\theta}_{(A,B)} = \text{Promedio Jackknife correlation (A,B)} = \frac{1}{n} \sum_{i=1}^n \hat r_i\]
donde \(n\) es el número de observaciones y \(r^i\) es el coeficiente de correlación entre las variables \(A\) y \(B\), habiendo excluido la observación \(i\).
Intervalo de confianza para la correlation Jackknife
- Además del promedio, se puede estimar su error estándar (SE) y así obtener intervalos de confianza para la Jackknife correlation y su correspondiente p-value.
\[SE = \sqrt{\frac{n-1}{n} \sum_{i=1}^n (\hat r_i - \bar{\theta})^2}\]
\(\text{Promedio Jackknife correlation (A,B)} \pm \ 1.96 *SE\)
\[\bar{\theta} - 1.96 \sqrt{\frac{n-1}{n} \sum_{i=1}^n (\hat r_i - \bar{\theta})^2} \ , \ \ \bar{\theta}+ 1.96 \sqrt{\frac{n-1}{n} \sum_{i=1}^n (\hat r_i - \bar{\theta})^2}\]
Simple matching coefficient
Cuando las variables con las que se pretende determinar la similitud entre observaciones son de tipo binario, a pesar de que es posible codificarlas de forma numérica como 1 o 0, no tiene sentido aplicar operaciones aritméticas sobre ellas (media, suma…).
- Por ejemplo, si la variable sexo se codifica como 1 para mujer y 0 para hombre, carece de significado decir que la media de la variable sexo en un determinado set de datos es 0.5
- En situaciones como esta, no se pueden emplear medidas de similitud basadas en distancia euclídea, manhattan o correlació. En este sentido, se uan forma de hacer las comparaciones es la siguiente:
Dado dos objetos A y B, cada uno con \(n\) atributos binarios, el simple matching coefficient (SMC) define la similitud entre ellos como:
\[SMC= \frac{\text{número coincidencias}}{\text{número total de atributos}} = \frac{M_{00} + M{11}}{M_{00} + M_{01}+ M_{10}+M_{11}}\]
donde \(M_{00}\) y \(M_{11}\) son el número de variables para las que ambas observaciones tienen el mismo valor (ambas 0 o ambas 1), y \(M_{01}\) y \(M_{10}\) el número de variables que no coinciden. El valor de distancia simple matching distance (SMD) se corresponde con \(1−SMC\)
Índice Jaccard
- El índice Jaccard o coeficiente de correlación Jaccard es similar al simple matching coefficient (SMC).
- La diferencia radica en que el SMC tiene el término \(M_{00}\) en el numerador y denominador, mientras que el índice de Jaccard no.
- Esto significa que SMC considera como coincidencias tanto si el atributo está presente en ambos sets como si el atributo no está en ninguno de los sets, mientras que Jaccard solo cuenta como coincidencias cuando el atributo está presente en ambos sets.
\[J= \frac{M_{11}}{M_{01}+ M_{10}+M_{11}}\]
o en términos matemáticos de sets:
\[J(A,B) = \frac{A \cap B}{A \cup B}\]
- La distancia de Jaccard (1−J) supera a la simple matching distance en aquellas situaciones en las que la coincidencia de ausencia no aporta información.
- Para ilustrar este hecho, supóngase que se quiere cuantificar la similitud entre dos clientes de un supermercado en base a los artículos comprados.
- Es de esperar que cada cliente solo adquiera unos pocos artículos de los muchos disponibles, por lo que el número de artículos no comprados por ninguno (\(M_{00}\)) será muy alto.
- Como la distancia de Jaccard ignora las coincidencias de tipo \(M_{00}\), el grado de similitud dependerá únicamente de las coincidencias entre los artículos comprados.
Distancia coseno
El coseno del ángulo que forman dos vectores puede interpretarse como una medida de similitud de sus orientaciones, independientemente de sus magnitudes.
- Si dos vectores tienen exactamente la misma orientación (el ángulo que forman es 0º) su coseno toma el valor de 1, si son perpendiculares (forman un ángulo de 90º) su coseno es 0 y si tienen orientaciones opuestas (ángulo de 180º) su coseno es de -1.
\[\text{cos}(\alpha) = \frac{\textbf{x} \cdot \textbf{y}}{||\textbf{x}|| \ ||\textbf{y}||}\]
Si los vectores se normalizan restándoles la media (\(X−\bar{X}\)), la medida recibe el nombre de coseno centrado y es equivalente a la correlación de Pearson.
Correlación de Pearson
Coseno del ángulo que forman los vectores a y b
Coseno del ángulo que forman los vectores a y b, tras centrar los vectores
Escala de las variables
Al igual que en otros métodos estadísticos (PCA, ridge regression, lasso…), la escala en la que se miden las variables y la magnitud de su varianza pueden afectar en gran medida a los resultados obtenidos por clustering.
- Si una variable tiene una escala mucho mayor que el resto, determinará en gran medida el valor de distancia/similitud obtenido al comparar las observaciones, dirigiendo así la agrupación final.
- Escalar y centrar las variables de forma que todas ellas tengan media 0 y desviación estándar 1 antes de calcular la matriz de distancias asegura que todas las variables tengan el mismo peso cuando se realice el clustering. A continuación, se presenta un análisis de los distintos tipos de escalado y normalización.
\[\frac{x_i−mean(x)}{sd(x)}\]
Para ilustrar este hecho, supóngase que una tienda online quiere clasificar a los compradores en función de los artículos que adquieren, por ejemplo, calcetines y ordenadores.
La siguiente imagen muestra el número de artículos comprados por 8 clientes a lo largo de un año, junto con el gasto total de cada uno.
Escala de las variables
- Si se intenta agrupar a los clientes por el número de artículos comprados, dado que los calcetines se compran con mucha más frecuencia que los ordenadores, van a tener más peso al crear los clusters.
- Por el contrario, si la agrupación se hace en base al gasto total de los clientes, como los ordenadores son mucho más caros, van a determinar en gran medida la clasificación.
- Escalando y centrando las variables se consigue igualar la influencia de calcetines y ordenadores.
- Cabe destacar que, si se aplica la estandarización descrita, existe una relación entre la distancia euclídea y la correlación de Pearson que hace que los resultados obtenidos por clustering en ambos casos sean equivalentes.
\[d_{euc}(p,q\ estandarizados) = \sqrt{2n(1-cor(p,q ))}\]
Ejemplo de distancias
El conjunto de datos USArrests contiene información sobre el número de delitos (asaltos, asesinatos y secuestros) junto con el porcentaje de población urbana para cada uno de los 50 estados de USA. Empleando estas variables se pretende calcular una matriz de distancias que permita identificar los estados más similares.
- Dos de las funciones en R que permiten calcular matrices de distancia empleando variables numéricas son dist() y get_dist(). Esta última incluye más tipos de distancias.
Escalando las variables y encontrando las distancias
Distancia basada en la correlación de pearson
Equivalencia 1 - cor_pearson
K-means clustering
Idea intuitiva
El método K-means clustering (MacQueen, 1967) agrupa las observaciones en K clusters distintos, donde el número K lo determina el analista antes de ejecutar del algoritmo.
K-means clustering encuentra los K mejores clusters, entendiendo como mejor cluster aquel cuya varianza interna (intra-cluster variation) sea lo más pequeña posible.
Se trata por lo tanto de un problema de optimización, en el que se reparten las observaciones en K clusters de forma que la suma de las varianzas internas de todos ellos sea lo menor posible.
Para poder solucionar este problema es necesario definir un modo de cuantificar la varianza interna.
Considérense \(C_1, \dots, C_K\) como los sets formados por los índices de las observaciones de cada uno de los clusters.
Por ejemplo, el conjunto \(C_1\) contiene los índices de las observaciones agrupadas en el cluster 1. La nomenclatura empleada para indicar que la observación i pertenece al cluster k es: \(i\in C_k\). Todos los conjuntos satisfacen dos propiedades:
- \(C_1 ∪ C_2 \cup ...\cup C_k= {1,...,n}\). Significa que toda observación pertenece al menos a uno de los K clusters.
- \(C_k \cap C_{k'} = \emptyset\) para todo \(k\neq k'\). Implica que los clusters no solapan, ninguna observación pertenece a más de un cluster a la vez.
Algoritmo K-means clustering
Algoritmo
Otra forma de implementar el algoritmo de K-means clustering es la siguiente:
Especificar el número K de clusters que se quieren crear.
Seleccionar de forma aleatoria k observaciones del set de datos como centroides iniciales.
Asignar cada una de las observaciones al centroide más cercano.
Para cada uno de los K clusters recalcular su centroide.
Repetir los pasos 3 y 4 hasta que las asignaciones no cambien o se alcance el número máximo de iteraciones establecido.
Observaciones
- Debido a que el algoritmo de K-means no evalúa todas las posibles distribuciones de las observaciones sino solo parte de ellas, los resultados obtenidos dependen de la asignación aleatoria inicial (paso 1).
- Por esta razón, es importante ejecutar el algoritmo varias veces (25-50), cada una con una asignación aleatoria inicial distinta, y seleccionar aquella que haya conseguido un menor valor de varianza total.
Ventajas y desventajas de K-means clustering
K-means es uno de los métodos de clustering más utilizados. Destaca por la sencillez y velocidad de su algoritmo, sin embargo, presenta una serie de limitaciones que se deben tener en cuenta.
- Requiere que se indique de antemano el número de clusters que se van a crear.
- Esto puede ser complicado si no se dispone de información adicional sobre los datos con los que se trabaja.
- Se han desarrollado varias estrategias para ayudar a identificar potenciales valores óptimos de K (ver más adelante), aunque todas ellas son orientativas.
- Las agrupaciones resultantes pueden variar dependiendo de la asignación aleatoria inicial de los centroides.
- Para minimizar este problema se recomienda repetir el proceso de clustering entre 25-50 veces y seleccionar como resultado definitivo el que tenga menor suma total de varianza interna.
- Aun así, solo se puede garantizar la reproducibilidad de los resultados si se emplean semillas.
- Presenta problemas de robustez frente a outliers.
- La única solución es excluirlos o recurrir a otros métodos de clustering más robustos como K-medoids (PAM).
Ejemplo 1
Los siguientes datos simulados contienen observaciones que pertenecen a cuatro grupos distintos. Se pretende aplicar K-means-clustering con el fin de identificarlos.
library(tidyverse)
library(ggpubr)
set.seed(101)
# Se simulan datos aleatorios con dos dimensiones
datos <- matrix(rnorm(n = 100*2), nrow = 100, ncol = 2,
dimnames = list(NULL,c("x", "y")))
datos <- as.data.frame(datos)
# Se determina la media que va a tener cada grupo en cada una de las dos
# dimensiones. En total 2*4 medias. Este valor se utiliza para separar
# cada grupo de los demás.
media_grupos <- matrix(rnorm(n = 8, mean = 0, sd = 4), nrow = 4, ncol = 2,
dimnames = list(NULL, c("media_x", "media_y")))
media_grupos <- as.data.frame(media_grupos)
media_grupos <- media_grupos %>% mutate(grupo = c("a","b","c","d"))
# Se genera un vector que asigne aleatoriamente cada observación a uno de
# los 4 grupos
datos <- datos %>% mutate(grupo = sample(x = c("a","b","c","d"),
size = 100,
replace = TRUE))
# Se incrementa el valor de cada observación con la media correspondiente al
# grupo asignado.
datos <- left_join(datos, media_grupos, by = "grupo")
datos <- datos %>% mutate(x = x + media_x,
y = y + media_y)
ggplot(data = datos, aes(x = x, y = y, color = grupo)) +
geom_point(size = 2.5) +
theme_bw()Haciendo los cluster
- La función kmeans() del paquete stats realiza K-mean-clustering. Entre sus argumentos destacan: centers, que determina el número K de clusters que se van a generar y nstart, que determina el número de veces que se va a repetir el proceso, cada vez con una asignación aleatoria inicial distinta.
- Es recomendable que este último valor sea alto, entre 25-50, para no obtener resultados malos debido a una iniciación poco afortunada del proceso.
Como los datos se han simulado considerando que todas las dimensiones tienen aproximadamente la misma magnitud, no es necesario escalarlos ni centrarlos. De no ser así, sí que habría que hacerlo.
Analizando los cluster
- El objeto devuelto por la función kmeans() contiene entre otros datos:
- la media de cada una de las variables para cada cluster (centers),
- un vector indicando a que cluster se ha asignado cada observación (cluster),
- la suma de cuadrados interna de cada cluster (withinss)
- la suma total de cuadrados internos de todos los clusters (tot.withinss).
- Al imprimir el resultado, también se muestra:
- el ratio de la suma de cuadrados entre-clusters
- la suma de cuadrados totales. Este ratio es equivalente al \(R^2\) de los modelos de regresión, indica el porcentaje de varianza explicada por el modelo respecto al total de varianza observada.
- Puede utilizarse para evaluar el clustering obtenido pero, al igual que ocurre con \(R^2\) al incrementar el número de predictores, el ratio between_SS/total_SS aumenta con el número de clusters creados.
- Esto último se debe de tener en cuenta para evitar problemas de overfitting.
Al tratarse de una simulación, se conoce el número real de grupos (4) y a cuál de ellos pertenece cada observación. Esto no sucede en la mayoría de casos prácticos, pero es útil para evaluar cómo de bueno es el método de K-means-clustering clasificando las observaciones.
Gráfico de los clusters
Se representa el número de cluster al que se ha asignado cada observación y se muestra con un código de color el grupo real al que pertenece.
# Se representa el número de cluster al que se ha asignado cada observación y
# se muestra con un código de color el grupo real al que pertenece.
datos <- datos %>% mutate(cluster = km_clusters$cluster)
datos <- datos %>% mutate(cluster = as.factor(cluster),
grupo = as.factor(grupo))
ggplot(data = datos, aes(x = x, y = y, color = grupo)) +
geom_text(aes(label = cluster), size = 5) +
theme_bw() +
theme(legend.position = "none")- El gráfico muestra que solo dos observaciones se han agrupado incorrectamente.
- tipo de visualización es muy útil e informativa, sin embargo, solo es posible cuando se trabaja con dos dimensiones y se conocen los verdaderos grupos a los que pertenecen las observaciones.
Si los datos contienen más de dos variables (dimensiones), una posible solución es utilizar las dos primeras componentes principales obtenidas en un PCA previo.
El número de aciertos y errores puede representarse también en modo de matriz de confusión.
A la hora de interpretar estas matrices, es importante recordar que el clustering asigna las observaciones a clusters cuyo identificador no tiene que por qué coincidir con la nomenclatura empleada para los grupos reales.
Por ejemplo, el grupo b podría haberse llamado en su lugar grupo 2 y haberse asignado al cluster 1.
Así pues, por cada fila de la matriz cabe esperar un valor alto (coincidencias) para una de las posiciones y valores bajos en las otras (errores de clasificación), pero no tienen por qué coincidir los nombres.
Análisis de los clusters
En este análisis, solo 2 de las 100 observaciones se han agrupado erróneamente.
De nuevo repetir que, en la realidad, no se suelen conocer los verdaderos grupos en los que se dividen las observaciones, de lo contrario no se necesitaría aplicar clustering.
Supóngase ahora que se trata de un caso real, en el que se desconoce el número de grupos en los que se subdividen las observaciones.
El investigador tendría que probar con diferentes valores de K y decidir cuál parece más razonable (en los siguientes apartados se describen métodos más sofisticados).
A continuación, se muestran los resultados para K=2 y K=6.
# Resultados para K = 2
datos <- datos %>% select(x, y)
set.seed(101)
km_clusters_2 <- kmeans(x = datos, centers = 2, nstart = 50)
datos <- datos %>% mutate(cluster = km_clusters_2$cluster)
p1 <- ggplot(data = datos, aes(x = x, y = y, color = as.factor(cluster))) +
geom_point(size = 3) +
labs(title = "Kmenas con k=2") +
theme_bw() +
theme(legend.position = "none")
# Resultados para K = 6
datos <- datos %>% select(x, y)
set.seed(101)
km_clusters_6 <- kmeans(x = datos, centers = 6, nstart = 50)
datos <- datos %>% mutate(cluster = km_clusters_6$cluster)
p2 <- ggplot(data = datos, aes(x = x, y = y, color = as.factor(cluster))) +
geom_point(size = 3) +
labs(title = "Kmenas con k=6") +
theme_bw() +
theme(legend.position = "none")
ggarrange(p1, p2)Ejemplo 2
El set de datos USArrests contiene información sobre el número de delitos (asaltos, asesinatos y secuestros) junto con el porcentaje de población urbana para cada uno de los 50 estados de USA. Se pretende estudiar si existe una agrupación subyacente de los estados empleando K-means-clustering.
El paquete factoextra creado por Alboukadel Kassambara contiene funciones que facilitan en gran medida la visualización y evaluación de los resultados de clustering.
Si se emplea K-means-clustering con distancia euclídea hay que asegurarse de que las variables empleadas son de tipo continuo, ya que trabaja con la media de cada una de ellas.
Observemos las clases de las variables
Como la magnitud de los valores difiere notablemente entre variables, se procede a escalarlas antes de aplicar el clustering.
- Una forma de estimar K óptimo si no se dispone de información adicional, es aplicar el algoritmo de K-means para un rango de valores de K e identificar aquel valor a partir del cual la reducción en la suma total de varianza intra-cluster deja de ser sustancial.
- La función fviz_nbclust() automatiza este proceso y genera una representación de los resultados.
Ejemplo 2
Este mismo análisis también puede realizarse sin recurrir a la función fviz_nbclust().
calcular_totwithinss <- function(n_clusters, datos, iter.max=1000, nstart=50){
# Esta función aplica el algoritmo kmeans y devuelve la suma total de
# cuadrados internos.
cluster_kmeans <- kmeans(centers = n_clusters, x = datos, iter.max = iter.max,
nstart = nstart)
return(cluster_kmeans$tot.withinss)
}
# Se aplica esta función con para diferentes valores de k
total_withinss <- map_dbl(.x = 1:15,
.f = calcular_totwithinss,
datos = datos)
total_withinssVeamos el gráfico de la reducción en la suma total de cuadrados.
En este análisis, a partir de 4 clusters la reducción en la suma total de cuadrados internos parece estabilizarse, indicando que K = 4 es una buena opción.
K-medoids clustering (PAM)
Idea intuitiva
- K-medoids es un método de clustering muy similar a K-means en cuanto a que ambos agrupan las observaciones en K clusters, donde K es un valor preestablecido por el analista.
- La diferencia es que, en K-medoids, cada cluster está representado por una observación presente en el cluster (medoid), mientras que en K-means cada cluster está representado por su centroide, que se corresponde con el promedio de todas las observaciones del cluster pero con ninguna en particular.
Medoid
Una definición más exacta del término medoid es: el elemento dentro de un cluster cuya distancia (diferencia) promedio entre él y todos los demás elementos del mismo cluster es lo menor posible.
- Se corresponde con el elemento más central del cluster y por lo tanto puede considerarse como el más representativo.
- El hecho de utilizar medoids en lugar de centroides hace de K-medoids un método más robusto que K-means, viéndose menos afectado por outliers o ruido.
- A modo de idea intuitiva puede considerarse como la analogía entre media y mediana.
Algoritmo k-medoid
El algoritmo más empleado para aplicar K-medoids se conoce como PAM (Partitioning Around Medoids) y sigue los siguientes pasos:
Seleccionar K observaciones aleatorias como medoids iniciales. También es posible identificarlas de forma específica.
Calcular la matriz de distancia entre todas las observaciones si esta no se ha calculado anteriormente.
Asignar cada observación a su medoid más cercano.
Para cada uno de los clusters creados, comprobar si seleccionando otra observación como medoid se consigue reducir la distancia promedio del cluster, si esto ocurre, seleccionar la observación que consigue una mayor reducción como nuevo medoid.
Si al menos un medoid ha cambiado en el paso 4, volver al paso 3, de lo contrario, se termina el proceso.
Observación
- Por lo general, el método de K-medoids se utiliza cuando se conoce o se sospecha de la presencia de outliers.
- Si esto ocurre, es recomendable utilizar como medida de similitud la distancia de Manhattan, ya que es menos sensible a outliers que la euclídea.
Ventajas y desventajas
K-medoids es un método de clustering más robusto que K-means, por lo es más adecuado cuando el set de datos contiene outliers o ruido.
Al igual que K-means, necesita que se especifique de antemano el número de clusters que se van a crear. Esto puede ser complicado de determinar si no se dispone de información adicional sobre los datos. Muchas de las estrategias empleadas en K-means para identificar el numero óptimo, puden aplicarse en K-medoids.
Para sets de datos grandes necesita muchos recursos computacionales. En tal situación se recomienda aplicar el método CLARA que veremos despues.
Ejemplo
El set de datos USArrests contiene información sobre el número de delitos (asaltos, asesinatos y secuestros) junto con el porcentaje de población urbana para cada uno de los 50 estados de USA. Se pretende estudiar si existe una agrupación subyacente de los estados mediante clustering. Dado que se sospecha de la presencia de outliers se recurre a K-medoids.
- El proceso a seguir en R para aplicar el método de K-medoids es igual al seguido en K-means (ejemplo 2), pero en este caso empleando la función pam() del paquete cluster.
Como la magnitud de los valores difiere notablemente entre variables, se procede a escalarlas antes de aplicar el clustering.
- Se evalúa la reducción de varianza total intra-cluster para un rango de valores K con el objetivo de identificar el número óptimo de clusters.
- En este caso, dado que se sospecha de la presencia de outliers, se emplea la distancia de Manhattan como medida de similitud.
Al igual que ocurría al aplicar K-means a estos datos, a partir de 4 clusters la reducción en la suma total de diferencias internas parece estabilizarse, indicando que K = 4 es una buena opción.
Usando K-medoids: PAM (Partitioning Around Medoids)
la funcion pam(), nos construye los clusters
- El objeto devuelto por pam() contiene entre otra información:
- las observaciones que finalmente se han seleccionado como medoids ($medoids)
- el cluster al que se ha asignado cada observación ($clustering).
Observación
Como en k-medoids no hay centroides, no se muestran en la representación ni tampoco las distancias desde este al resto de observaciones.
Hierarchical clustering (Clustering jerárquico)
Hierarchical clustering es una alternativa a los métodos de partitioning clustering que no requiere que se pre-especifique el número de clusters.
Los métodos que engloba el hierarchical clustering se subdividen en dos tipos dependiendo de la estrategia seguida para crear los grupos:
- Agglomerative clustering (bottom-up): el agrupamiento se inicia en la base del árbol, donde cada observación forma un cluster individual. Los clusters se van combinado a medida que la estructura crece hasta converger en una única “rama” central.
- Divisive clustering (top-down): es la estrategia opuesta al agglomerative clustering, se inicia con todas las observaciones contenidas en un mismo cluster y se suceden divisiones hasta que cada observación forma un cluster individual.
En ambos casos, los resultados pueden representarse de forma muy intuitiva en una estructura de árbol llamada dendrograma.
Clustering Aglomerativo
La estructura resultante de un agglomerative hierarchical clustering se obtiene mediante un algoritmo sencillo.
- El proceso se inicia considerando cada una de las observaciones como un cluster individual, formando así la base del dendrograma (hojas).
- Se inicia un proceso iterativo hasta que todas las observaciones pertenecen a un único cluster:
- 2.1. Se calcula la distancia entre cada posible par de los n clusters. El investigador debe determinar el tipo de medida emplea para cuantificar la similitud entre observaciones o grupos (distancia y linkage).
- 2.2. Los dos clusters más similares se fusionan, de forma que quedan n-1 clusters.
- Determinar dónde cortar la estructura de árbol generada (dendrograma).
Clustering Aglomerativo y linkage
Para que el proceso de agrupamiento funcione, es necesario definir cómo se cuantifica la similitud entre dos clusters.
- Es decir, se tiene que extender el concepto de distancia entre pares de observaciones para que sea aplicable a pares de grupos, cada uno formado por varias observaciones.
- A este proceso se le conoce como linkage.
A continuación, se describen los 5 tipos de linkage más empleados y sus definiciones.
Complete or Maximum: Se calcula la distancia entre todos los posibles pares formados por una observación del cluster A y una del cluster B. La mayor de todas ellas se selecciona como la distancia entre los dos clusters. Se trata de la medida más conservadora (maximal intercluster dissimilarity).
Single or Minimum: Se calcula la distancia entre todos los posibles pares formados por una observación del cluster A y una del cluster B. La menor de todas ellas se selecciona como la distancia entre los dos clusters. Se trata de la medida menos conservadora (minimal intercluster dissimilarity).
Average: Se calcula la distancia entre todos los posibles pares formados por una observación del cluster A y una del cluster B. El valor promedio de todas ellas se selecciona como la distancia entre los dos clusters (mean intercluster dissimilarity).
Clustering Aglomerativo y linkage
Centroid: Se calcula el centroide de cada uno de los clusters y se selecciona la distancia entre ellos como la distancia entre los dos clusters.
Ward: Se trata de un método general. La selección del par de clusters que se combinan en cada paso del agglomerative hierarchical clustering se basa en el valor óptimo de una función objetivo, pudiendo ser esta última cualquier función definida por el analista.
- El conocido método Ward’s minimum variance es un caso particular en el que el objetivo es minimizar la suma total de varianza intra-cluster.
- En cada paso, se identifican aquellos 2 clusters cuya fusión conlleva menor incremento de la varianza total intra-cluster.
- Si se emplea la función
- hclust() se tiene que especificar method = “ward.D2”
- agnes() es method = ward”
Observación
- Los métodos de linkage complete, average y Ward’s minimum variance suelen ser los preferidos por los analistas debido a que generan dendrogramas más compensados.
- Sin embargo, no se puede determinar que uno sea mejor que otro, ya que depende del caso de estudio en cuestión.
- Por ejemplo, en genómica, se emplea con frecuencia el método de centroides.
- Junto con los resultados de un proceso de hierarchical clustering siempre hay que indicar qué distancia se ha empleado, así como el tipo de linkage, ya que, dependiendo de estos, los resultados pueden variar en gran medida.
Ejemplo gráfico ilustrativo
Clustering Divisivo
El algoritmo más conocido de divisive hierarchical clustering es DIANA (DIvisive ANAlysis Clustering).
- Este algoritmo se inicia con un único cluster que contiene todas las observaciones, a continuación, se van sucediendo divisiones hasta que cada observación forma un cluster independiente.
- En cada iteración, se selecciona el cluster con mayor diametro, entendiendo por diámetro de un cluster la mayor de las diferencias entre dos de sus observaciones.
- Una vez seleccionado el cluster, se identifica la observación más dispar, que es aquella con mayor distancia promedio respecto al resto de observaciones que forman el cluster, esta observación inicia el nuevo cluster.
- Se reasignan las observaciones en función de si están más próximas al nuevo cluster o al resto de la partición, dividiendo así el cluster seleccionado en dos nuevos clusters.
Algoritmo Clustering Divisivo
- Todas las n observaciones forman un único cluster.
- Repetir hasta que hayan n clusters:
- 2.1 Calcular para cada cluster la mayor de las distancias entre pares de observaciones (diámetro del cluster).
- 2.2 Seleccionar el cluster con mayor diámetro.
- 2.3 Calcular la distancia media de cada observación respecto a las demas.
- 2.4 La observación más distante inicia un nuevo cluster
- 2.5 Se reasignan las observaciones restantes al nuevo cluster o al viejo dependiendo de cual está más próximo.
Observación
A diferencia del clustering aglomerativo, en el que hay que elegir un tipo de distancia y un método de linkage, en el clustering divisivo solo hay que elegir la distancia, no hay linkage.
Dendrograma
Para ilustrar cómo se interpreta un dendograma, se simula un set de datos y se somete a un proceso de hierarchical clustering.
- Supóngase que se dispone de 45 observaciones en un espacio de dos dimensiones, que pertenecen a 3 grupos.
- Aunque se ha coloreado de forma distinta cada uno de los grupos para facilitar la comprensión de la idea, se va a suponer que se desconoce esta información y que se desea aplicar el método de hierarchical clustering para intentar reconocer los grupos.
- Al aplicar hierarchical clustering, empleando como medida de similitud la distancia euclídea y linkage complete, se obtiene el siguiente dendrograma.
- Como los datos se han simulado en aproximamdamente la misma escala, no es necesario estandarizarlos, de no ser así, sí se tendrían que estandarizar.
Observaciones del Dendograma
- En la base del dendrograma, cada observación forma una terminación individual conocida como hoja o leaf del árbol.
- A medida que se asciende por la estructura, pares de hojas se fusionan formando las primeras ramas.
- Estas uniones (nodos) se corresponden con los pares de observaciones más similares. También ocurre que ramas se fusionan con otras ramas o con hojas.
- Cuanto más temprana (más próxima a la base del dendrograma) ocurre una fusión, mayor es la similitud.
- Esto significa que, para cualquier par de observaciones, se puede identificar el punto del árbol en el que las ramas que contienen dichas observaciones se fusionan.
Verificar el árbol resultante
Una vez creado el dendrograma, hay que evaluar hasta qué punto su estructura refleja las distancias originales entre observaciones.
- Una forma de hacerlo es empleando el coeficiente de correlación entre las distancias cophenetic del dendrograma (altura de los nodos) y la matriz de distancias original.
- Cuanto más cercano es el valor a 1, mejor refleja el dendrograma la verdadera similitud entre las observaciones.
- Valores superiores a 0.75 suelen considerarse como buenos.
- Esta medida puede emplearse como criterio de ayuda para escoger entre los distintos métodos de linkage.
- En R, la función cophenetic() calcula las distancias cophenetic de un hierarchical clustering.
Ejemplo de Dendograma
A continuación usaremos los datos USArrests para realizar un dendograma.
Primero las distancias euclideas
Ahora veamos los dendogramas con linkage complete y average
Finalmente, vemos la correlación con cada linkage
Correlación con linkage: complete
Correlación con linkage: average
Para estos datos, el método de linkage average consigue representar ligeramente mejor la similitud entre observaciones.
¿Dónde cortar el árbol para generar los clusters?
Además de representar en un dendrograma la similitud entre observaciones, se tiene que poder identificar el número de clusters creados y qué observaciones forman parte de cada uno.
- Si se realiza un corte horizontal a una determinada altura del dendrograma, el número de ramas que sobrepasan (en sentido ascendente) dicho corte se corresponde con el número de clusters.
- A continuación vemos el código para mostrar dos veces el mismo dendrograma.
Primero generamos el dendograma con la función hclust()
A continuación el gráfico del dendograma usando la función fviz_dend() y el linkage completo y K = 2.
Ahora tenemos el gráfico del dendograma con linkage completo y con K = 4.
Observaciones
- Si se realiza el corte a la altura de 5, se obtienen dos clusters, mientras que si se hace a la de 3.5 se obtienen 4.
- La altura de corte tiene por lo tanto la misma función que el valor K en K-means-clustering: controla el número de clusters obtenidos.
Observaciones adicionales del dendograma
Dos propiedades adicionales se derivan de la forma en que se generan los clusters en el método de hierarchical clustering:
- Dada la longitud variable de las ramas, siempre existe un intervalo de altura para el que cualquier corte da lugar al mismo número de clusters.
- En el ejemplo anterior, todos los cortes entre las alturas 5 y 6 tienen como resultado los mismos 2 clusters.
- Con un solo dendrograma se dispone de la flexibilidad para generar cualquier número de clusters desde 1 a n.
- Una forma menos frecuente de representar los resultados de un hierarchical clustering es combinándolos con una reducción de dimensionalidad por PCA.
- Primero, se calculan las componentes principales y se representan las observaciones en un scatterplot empleando las dos primeras componentes, finalmente se colorean los clusters mediante elipses.
Veamos un ejemplo:
fviz_cluster(object = list(data=datos, cluster=cutree(hc_euclidea_completo, k=4)),
ellipse.type = "convex", repel = TRUE, show.clust.cent = FALSE,
labelsize = 8) +
labs(title = "Hierarchical clustering + Proyección PCA",
subtitle = "Distancia euclídea, Lincage complete, K=4") +
theme_bw() +
theme(legend.position = "bottom")Ejemplo
Los siguientes datos simulados contienen observaciones que pertenecen a cuatro grupos distintos. Se pretende aplicar hierarchical clustering aglomerativo con el fin de identificarlos.
Creamos los datos aleatorios
library(tidyr)
library(dplyr)
set.seed(101)
# Se simulan datos aleatorios con dos dimensiones
datos <- matrix(rnorm(n = 100*2), nrow = 100, ncol = 2,
dimnames = list(NULL,c("x", "y")))
datos <- as.data.frame(datos)
# Se determina la media que va a tener cada grupo en cada una de las dos
# dimensiones. En total 2*4 medias. Este valor se utiliza para separar
# cada grupo de los demás.
media_grupos <- matrix(rnorm(n = 8, mean = 0, sd = 4), nrow = 4, ncol = 2,
dimnames = list(NULL, c("media_x", "media_y")))
media_grupos <- as.data.frame(media_grupos)
media_grupos <- media_grupos %>% mutate(grupo = c("a","b","c","d"))
# Se genera un vector que asigne aleatoriamente cada observación a uno de
# los 4 grupos
datos <- datos %>% mutate(grupo = sample(x = c("a","b","c","d"),
size = 100,
replace = TRUE))
# Se incrementa el valor de cada observación con la media correspondiente al
# grupo asignado.
datos <- left_join(datos, media_grupos, by = "grupo")
datos <- datos %>% mutate(x = x + media_x,
y = y + media_y)
datos <- datos %>% select(grupo, x, y)Veamos el gráfico de los datos
Apliquemos clustering aglomerativo
- Al aplicar un hierarchical clustering aglomerativo se tiene que escoger una medida de distancia (1-similitud) y un tipo de linkage.
- En este caso, se emplea la función hclust(), a la que se pasa como argumento una matriz de distancia euclidea y el tipo de linkages.
- Se comparan los resultados con los linkages complete, single y average.
Nota
Dado que los datos se han simulado considerando que las dos dimensiones tienen aproximadamente la misma magnitud, no es necesario escalarlos ni centrarlos.
Ejemplo continuación
# Se calculan las distancias
matriz_distancias <- dist(x = datos[, c("x", "y")], method = "euclidean")
set.seed(567)
hc_euclidea_completo <- hclust(d = matriz_distancias, method = "complete")
hc_euclidea_single <- hclust(d = matriz_distancias, method = "single")
hc_euclidea_average <- hclust(d = matriz_distancias, method = "average")Los objetos devueltos por hclust() pueden representarse en forma de dendrograma con la función plot() o con la función fviz_dend() del paquete factoextra.
Distancia euclídea, Linkage complete
Distancia euclídea, Linkage single
Distancia euclídea, Linkage average
El conocer que existen 4 grupos en la población permite evaluar qué linkage consigue los mejores resultados.
- En este caso, los tres tipos identifican claramente 4 clusters, si bien esto no significa que en los 3 dendrogramas los clusters estén formados por exactamente las mismas observaciones.
¿A qué altura se corta el árbol?
- Una vez creado el dendrograma, se tiene que decidir a qué altura se corta para generar los clusters.
- La función cutree() recibe como input un dendrograma y devuelve el cluster al que se ha asignado cada observación dependiendo del número de clusters especificado (argumento k) o la altura de corte indicada (argumento h).
Cortando en k = 4
Cortando en k = 4
Observación
- Una forma visual de comprobar los errores en las asignaciones es indicando en el argumento labels el grupo real al que pertenece cada observación.
- Si la agrupación resultante coincide con los grupos reales, entonces, dentro de cada clusters las labels serán las mismas.
Veamos la matríz de confusión
Hierarchical K-means clustering
- K-means es uno de los métodos de clustering más utilizados y cuyos resultados son satisfactorios en muchos escenarios, sin embargo, como se ha explicado en apartados anteriores, sufre las limitaciones de necesitar que se especifique el número de clusters de antemano y de que sus resultados puedan variar en función de la iniciación aleatoria.
- Una forma de contrarrestar estos dos problemas es combinando el K-means con el hierarchical clustering. Los pasos a seguir son los siguientes:
Aplicar hierarchical clustering a los datos y cortar el árbol en k clusters. El número óptimo puede elegirse de forma visual o con cualquiera de los métodos explicados en la sección Número óptimo de clusters.
Calcular el centro (por ejemplo, la media) de cada cluster.
Aplicar k-means clustering empleando como centroides iniciales los centros calculados en el paso
El algoritmo de K-means tratará de mejorar la agrupación hecha por el hierarchical clustering en el paso 1, de ahí que las agrupaciones finales puedan variar respecto a las iniciales.
Ejemplo de Hierarchical K-means clustering
El set de datos USArrests contiene información sobre el número de delitos (asaltos, asesinatos y secuestros) junto con el porcentaje de población urbana para cada uno de los 50 estados de USA. Se pretende estudiar si existe una agrupación subyacente de los estados empleando Hierarchical K-means clustering.
Como la magnitud de los valores difiere notablemente entre variables, se procede a escalarlas antes de aplicar el clustering.
La función hkmeans() del paquete factoextra permite aplicar el método hierarchical K-means clustering de forma muy similar a la función estándar kmeans().
Veamos el dendograma
Empleando la representación del dendrograma se considera que existen 4 grupos.
Finalmente veamos los clusters junto con los mejores predictores (componentes principales)
Fuzzy clustering
Idea intuitiva
Los métodos de clustering descritos hasta ahora (K-means, hierarchical, K-medoids, CLARA,…) asignan cada observación únicamente a un cluster, de ahí que también se conozcan como hard clustering. Los métodos de fuzzy clustering o soft clustering se caracterizan porque, cada observación, puede pertenecer potencialmente a varios clusters, en concreto, cada observación tiene asignado un grado de pertenencia a cada uno de los cluster.
- Fuzzy c-means (FCM) es uno de los algoritmos más empleado para generar fuzzy clustering.
- Se asemeja en gran medida al algoritmo de k-means pero con dos diferencias:
- El cálculo de los centroides de los clusters. La definición de centroide empleada por c-means es: la media de todas las observaciones del set de datos ponderada por la probabilidad de pertenecer a al cluster.
- Devuelve para cada observación la probabilidad de pertenecer a cada cluster.
Ejemplo Fuzzy clustering
El set de datos USArrests contiene información sobre el número de delitos (asaltos, asesinatos y secuestros) junto con el porcentaje de población urbana para cada uno de los 50 estados de USA. Se pretende estudiar si existe una agrupación subyacente de los estados empleando fuzzy clustering.
Como la magnitud de los valores difiere notablemente entre variables, se procede a escalarlas antes de aplicar el clustering.
La función fanny() (fuzzy analysis) del paquete cluster permite aplicar el algoritmo c-means clustering.
El objeto devuelto fanny() incluye entre sus elementos: una matriz con el grado de pertenencia de cada observación a cada cluster (las columnas son los clusters y las filas las observaciones).
Ejemplo Fuzzy clustering - continuación
El coeficiente de partición Dunn normalizado y sin normalizar. Valores normalizados próximos a 0 indican que la estructura tiene un alto nivel fuzzy y valores próximos a 1 lo contrario.
El cluster al que se ha asignado mayoritariamente cada observación.
Para obtener una representación gráfica del clustering se puede emplear la función fviz_cluster().
Density based clustering (DBSCAN) (Clustering basado en densidad)
Idea intuitiva
El nombre del método: Density-based spatial clustering of applications with noise (DBSCAN) fue presentado en 1996 por Ester et al. como una forma de identificar clusters siguiendo el modo intuitivo en el que lo hace el cerebro humano, identificando regiones con alta densidad de observaciones separadas por regiones de baja densidad.
Véase la siguiente representación bidimensional de los datos multishape del paquete factoextra.
DBSCAN - Ejemplo usando kmeans
# lebreria y lectura de datos
library(factoextra)
data("multishapes")
datos <- multishapes[, 1:2]
# clusterig con kmeans
set.seed(321)
km_clusters <- kmeans(x = datos, centers = 5, nstart = 50)
# grafico
fviz_cluster(object = km_clusters, data = datos, geom = "point", ellipse = FALSE,
show.clust.cent = FALSE, pallete = "jco") +
theme_bw() +
theme(legend.position = "none")El cerebro humano identifica fácilmente 5 agrupaciones y algunas observaciones aisladas (ruido). Véanse ahora los clusters que se obtienen si se aplica, por ejemplo, K-means clustering.
DBSCAN - Ejemplo usando kmeans
Observaciones
- Los clusters generados distan mucho de representar las verdaderas agrupaciones.
- Esto es así porque los métodos de partitioining clustering como k-means, hierarchical, k-medoids, c-means… son buenos encontrando agrupaciones con forma esférica o convexa que no contengan un exceso de outliers o ruido, pero fallan al tratar de identificar formas arbitrarias.
- De ahí que el único cluster que se corresponde con un grupo real sea el amarillo.
- DBSCAN evita este problema siguiendo la idea de que, para que una observación forme parte de un cluster, tiene que haber un mínimo de observaciones vecinas dentro de un radio de proximidad y de que los clusters están separados por regiones vacías o con pocas observaciones.
Definiciones, parámetros y categorías de cada observación en DBSCAN
El algoritmo DBSCAN necesita dos parámetros:
- Epsilon (\(\epsilon\)): radio que define la región vecina a una observación, también llamada \(\epsilon\)-neighborhood (\(\epsilon\)-vecindad).
- Minimum points (minPts): número mínimo de observaciones dentro de la región epsilon.
Empleando estos dos parámetros, cada observación se puede clasificar en una categoría:
- Core point: observación que tiene en su \(\epsilon\)-neighborhood un número de observaciones vecinas igual o mayor a minPts.
- Border point: observación no satisface el mínimo de observaciones vecinas para ser core point pero que pertenece al \(\epsilon\)-neighborhood de otra observación que sí es core point.
- Noise u outlier (ruido): observación que no es core point ni border point.
Por último, empleando las tres categorías anteriores se pueden definir tres niveles de conectividad entre observaciones:
- Directamente alcanzable (direct density reachable): una observación A es directamente alcanzable desde otra observación B si A forma parte del \(\epsilon\)-neighborhood de B y B es un core point.
- Por definición, las observaciones solo pueden ser directamente alcanzables desde un core point.
- Alcanzable (density reachable): una observación A es alcanzable desde otra observación B si existe una secuencia de core points que van desde B a A.
- Densamente conectadas (density conected): dos observaciones A y B están densamente conectadas si existe una observación core point C tal que A y B son alcanzables desde C.
Idea gráfica de DBSCAN
La siguiente imagen muestra las conexiones existentes entre un conjunto de observaciones si se emplea minPts=4.
- La observación A y el resto de observaciones marcadas en rojo son core points, ya que todas ellas contienen al menos 4 observaciones vecinas (incluyéndose a ellas mismas) en su \(\epsilon\)-neighborhood.
- Como todas son alcanzables entre ellas, forman un cluster.
- Las observaciones B y C no son core points pero son alcanzables desde A a través de otros core points, por lo tanto, pertenecen al mismo cluster que A.
- La observación N no es ni un core point ni es directamente alcanzable, por lo que se considera como ruido.
Algoritmo DBSCAN
Para cada observación \(x_i\) calcular la distancia entre ella y el resto de observaciones.
- Si en su \(\epsilon\)-neighborhood hay un número de observaciones \(\leqslant\) minPts marcar la observación como core point, de lo contrario marcarla como visitada.
Para cada observación \(x_i\), marcada como core point, si todavía no ha sido asignada a ningún cluster, crear uno nuevo y asignarla a él.
- Encontrar recursivamente todas las observaciones densamente conectadas a ella y asignarlas al mismo cluster.
Iterar el mismo proceso para todas las observaciones que no hayan sido visitadas.
Aquellas observaciones que tras haber sido visitadas no pertenecen a ningún cluster se marcan como outliers.
Observación
Como resultado, todo cluster encontrado por DBSCAN, cumple dos propiedades:
- Todos los puntos que forman parte de un mismo cluster están densamente conectados entre ellos.
- Si una observación A es densamente alcanzable desde cualquier otra observación de un cluster, entonces A también pertenece al cluster.
Selección de parámetros
Como ocurre en muchas otras técnicas estadísticas, en DBSCAN no existe una forma única y exacta de encontrar el valor adecuado de epsilon (\(\epsilon\)) y minPts. A modo orientativo se pueden seguir las siguientes premisas:
- minPts: cuanto mayor sea el tamaño del set de datos, mayor debe ser el valor mínimo de observaciones vecinas.
- En el libro Practical Guide to Cluster Analysis in R recomiendan no bajar nunca de 3.
- Si los datos contienen niveles altos de ruido, aumentar minPts favorecerá la creación de clusters significativos menos influenciados por outliers.
- epsilon: una buena forma de escoger el valor de \(\epsilon\) es estudiar las distancias promedio entre las k=minPts observaciones más próximas.
- Al representar estas distancias en función de \(\epsilon\), el punto de inflexión de la curva suele ser un valor óptimo.
- Si el valor de \(\epsilon\) escogido es muy pequeño, una proporción alta de las observaciones no se asignarán a ningún cluster, por el contrario, si el valor es demasiado grande, la mayoría de observaciones se agruparán en un único cluster.
Ventajas y desventajas de DBSCAN
Ventajas de DBSCAN
No requiere que el usuario especifique el número de clusters.
Es independiente de la forma que tengan los clusters, no tienen por qué ser circulares.
Puede identificar outliers, por lo que los clusters generados no se influenciados por ellos.
Desventajas de DBSCAN
No es un método totalmente determinístico: los border points que son alcanzables desde más de un cluster pueden asignarse a uno u otro dependiendo del orden en el que se procesen los datos.
No genera buenos resultados cuando la densidad de los grupos es muy distinta, ya que no es posible encontrar los parámetros ϵ y minPts que sirvan para todos a la vez.
Ejemplo clusterig con DBSCAN
El conjunto de datos multishape del paquete factoextra contiene observaciones que pertenecen a 5 grupos distintos junto con cierto ruido (outliers). Como se espera que la distribución espacial de los grupos no sea esférica, se aplica el método de clustering DBSCAN.
En R existen dos paquetes con funciones que permiten aplicar el algoritmo DBSCAN como: fpc y dbscan.
Notas:
- dbscan: contiene una modificación del algoritmo original que lo hace más rápido.
- La función kNNdistplot del paquete dbscan calcula y representa las k-distancias para ayudar a identificar el valor óptimo de epsilon.
Ejemplo clusterig con DBSCAN
Iniciemos el ejemplo encontrando el \(\epsilon\) óptimo; para esto, usemos la función kNNdistplot.
Vemos que la curva tiene el punto de inflexión en torno a 0.15, por lo que se escoge este valor como epsilon para DBSCAN.
Veamos como quedan gráficamente los clusters con DBSCAN.
Ejercicio
Acerca del conjunto de datos
Necesidad de eficiencia en la agricultura:
En la publicación Agriculture to Agritech: Trends, Challenges, and the Path Forward with Digital Technology and Software Solutions, se proyecta que la industria agrícola alimentaría a una población mundial estimada de 9.7 mil millones para 2050. Solo en 2020, un Se requiere un aumento del 60% para alimentar a la población. Hablamos sobre la macroeconomía, las preferencias cambiantes de los consumidores, las tecnologías emergentes y la transformación de las cadenas de suministro como impulsores clave para la transformación digital en la agricultura y cómo los desafíos que enfrenta la industria agrícola en todo el mundo podrían abordarse de manera efectiva siguiendo el enfoque correcto y aprovechando la tecnología para satisfacer la creciente demanda. por comida.
Hasta ahora, factores como el cambio climático, el crecimiento de la población y la seguridad alimentaria han impulsado a la industria a buscar enfoques más innovadores para mejorar el rendimiento de los cultivos. Pero la crisis actual de COVID-19 ha expuesto aún más la vulnerabilidad del paisaje agrícola y ha planteado dudas sobre cómo satisfacer la demanda mundial de alimentos de manera sostenible, con factores adversos en juego. Una vez más, la respuesta está en lograr la eficiencia: producir más con menos, ahora más que nunca.
La industria será transformada por la ciencia de datos y la inteligencia artificial. Los agricultores tendrán las herramientas para aprovechar al máximo cada hectárea.
Ejercicio 1
Usar los datos Crop_recommendation, para realizar una clasificación de los datos usando los diferentes métodos vistos en clase. Haga un análisis de los resultados y concluya que clasificadores son mejores y que tipo de etiquetas piensa que están resultando de la clasificación; es decir, a qué grupos y que carácteristicas tienen esos grupos.
Acerca de los datos.
- N = Nitrógeno
- P = fósforo
- K = potasio
- Temperatura = Las temperaturas promedio del suelo para la bioactividad varían de 50 a 75F.
- Ph = Una escala utilizada para identificar la naturaleza de acidez o basicidad; (Naturaleza Ácida- Ph<7; Neutra- Ph=7; Naturaleza Base-P>7)
- label = Tipos de Cultivo (Arroz, Maíz, Garbanzo; Frijoles; gandules; polilla; frijol mungo; garbanzo negro; lentejas; granada; plátano; mango; uvas; sandía; melón; manzana; naranja; papaya; coco; algodón; yute; café )
Ejercicio 2
Ir a la página <www.kaggle.com/datasets> y descargar los datos AI Global Index; luego, realizar una análisis usando los clasificadores que vimos en clase.
Ejercicio 3
Descripción del conjunto de datos Mall_Customers: es un dato básico sobre los clientes que van al centro comercial del supermercado. Esto se puede utilizar para la segmentación de clientes. Hay 200 observaciones (clientes) y no faltan datos.
Se compone de cuatro columnas, es decir, las variables medidas:
- CustomerID: es el número de identificación del cliente.
- El género: es femenino y masculino.
- La edad: es la edad de los clientes.
- Ingreso Anual (k): es el ingreso anual de los clientes en miles de dólares.
- Spending Score (1-100): es el puntaje de gasto asignado por el centro comercial de acuerdo con el comportamiento de compra del cliente
Usar DBSCAN para realizar una clasificación de los datos.
plano cartesiano
