Clase 13 - segmentación
Andrés Acero
8/9/2021
Clustering basado en la media
Clustering de K-Medias
Al igual que la agrupación jerárquica, k-means es un enfoque muy popular. 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.
El agrupamiento de K-medias intenta encontrar grupos que sean más compactos, en términos de la desviación media de la suma de cuadrados de cada observación desde el centro multivariado (centroide) de su grupo asignado. 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.
Minimizar la suma total de varianza interna de forma exacta (encontrar el mínimo global) es un proceso muy complejo debido a la inmensa cantidad de formas en las que n observaciones se pueden dividir en K grupos. Sin embargo, es posible obtener una solución que, aun no siendo la mejor de entre todas las posibles, es muy buena (óptimo local). El algoritmo empleado para ello es:
Asignar aleatoriamente un número entre 1 y K a cada observación. Esto sirve como asignación inicial aleatoria de las observaciones a los clusters.
los siguientes pasos hasta que la asignación de las observaciones a los clusters no cambie o se alcance un número máximo de iteraciones establecido por el usuario.
Para cada uno de los clusters calcular su centroide. Entendiendo por centroide la posición definida por la media de cada una de las dimensiones (variables) de las observaciones que forman el cluster. Aunque no es siempre equivalente, puede entenderse como el centro de gravedad.
Asignar cada observación al cluster cuyo centroide está más próximo.
Este algoritmo garantiza que, en cada paso, se reduzca la intra-varianza total de los clusters hasta alcanzar un óptimo local. La siguiente imagen muestra cómo van cambiando las asignaciones de las observaciones a medida que se ejecuta cada paso del algoritmo.
Figura 1: agrupamiento de K-medias
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.
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. Debido a que calcula explícitamente una desviación media, la agrupación de k medias se basa en la distancia euclidiana u otras de las medidas vistas en la última clase. Por lo tanto, solo es apropiado para datos numéricos o datos que se pueden convertir razonablemente en numéricos.
Cargue de datos
El día de hoy trabajaremos con una base de datos de clientes de banco nuevamente:
data1 <- read.csv("Clase 12.csv")
data1 <- na.omit(data1)
str(data1)## 'data.frame': 8636 obs. of 18 variables:
## $ CUST_ID : chr "C10001" "C10002" "C10003" "C10005" ...
## $ BALANCE : num 40.9 3202.5 2495.1 817.7 1809.8 ...
## $ BALANCE_FREQUENCY : num 0.818 0.909 1 1 1 ...
## $ PURCHASES : num 95.4 0 773.2 16 1333.3 ...
## $ ONEOFF_PURCHASES : num 0 0 773 16 0 ...
## $ INSTALLMENTS_PURCHASES : num 95.4 0 0 0 1333.3 ...
## $ CASH_ADVANCE : num 0 6443 0 0 0 ...
## $ PURCHASES_FREQUENCY : num 0.1667 0 1 0.0833 0.6667 ...
## $ ONEOFF_PURCHASES_FREQUENCY : num 0 0 1 0.0833 0 ...
## $ PURCHASES_INSTALLMENTS_FREQUENCY: num 0.0833 0 0 0 0.5833 ...
## $ CASH_ADVANCE_FREQUENCY : num 0 0.25 0 0 0 0 0 0 0 0 ...
## $ CASH_ADVANCE_TRX : int 0 4 0 0 0 0 0 0 0 0 ...
## $ PURCHASES_TRX : int 2 0 12 1 8 64 12 5 3 12 ...
## $ CREDIT_LIMIT : num 1000 7000 7500 1200 1800 13500 2300 7000 11000 1200 ...
## $ PAYMENTS : num 202 4103 622 678 1400 ...
## $ MINIMUM_PAYMENTS : num 140 1072 627 245 2407 ...
## $ PRC_FULL_PAYMENT : num 0 0.222 0 0 0 ...
## $ TENURE : int 12 12 12 12 12 12 12 12 12 12 ...
## - attr(*, "na.action")= 'omit' Named int [1:314] 4 46 48 55 56 57 64 94 95 98 ...
## ..- attr(*, "names")= chr [1:314] "4" "46" "48" "55" ...Como podrán ver, tenemos una base de datos con las diferentes características de un cliente de un banco. Estas características incluyen frecuencia de compras, pagos, avances de tarjetas, entre otros. La base de datos la podrán encontrar en el siguiente enlace: https://www.dropbox.com/s/eic7jp5hb799cpt/Clase%2012.csv?dl=0.
Al igual que vimos ayer, el escalamiento de las variables es importante para evitar sobre-dimensionamiento. Como la magnitud de los valores difiere notablemente entre las variables, se procede a escalarlas antes de aplicar el clustering:
data2 <- as.data.frame(scale(data1[1:150,2:18], center = TRUE))Ahora que tenemos los datos procederemos a correr los métodos.
Clustering K-medias
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.
set.seed(96743)
km1 <- kmeans(data2, centers = 4, nstart = 50)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) y la suma total de cuadrados internos de todos los clusters (tot.withinss). Al imprimir el resultado también se muestra y el ratio de la suma de cuadrados entre-clusters y la suma de cuadrados totales. Este ratio es equivalente al R2 de los modelos de regresión, indica el porcentaje de varianza explicada por el modelo respecto al total de varianza observada. Ahora veamos que tenemos en el modelo usando la función clusplot() del paquete cluster. Este gráfico ubica las observaciones en un plano cuyos ejes son los primeros componentes principales:
library(cluster)
clusplot(data2, km1$cluster, color = T, shade = T)
Parece ser que nuestro modelo inicial no es muy bueno, por lo que probaremos con 5 centroides:
set.seed(96743)
km1 <- kmeans(data2, centers = 5, nstart = 50)
clusplot(data2, km1$cluster, color = T, shade = T)
Todavía parece ser que podríamos crear más centroides, así que usaremos un nuevo modelo:
set.seed(96743)
km1 <- kmeans(data2, centers = 3, nstart = 50)
clusplot(data2, km1$cluster, color = T, shade = T)
¿Cuál es el consejo? Escoger el que mejor represente los datos. Más que una técnica exacta, esto es un arte. Ahora revisemos los resultados de nuestros grupos usando unas gráficas:
data2$grupo <- as.factor(km1$cluster)
library(ggplot2)
ggplot(data2, aes(BALANCE, grupo)) + geom_boxplot() + theme_classic()
ggplot(data2, aes(MINIMUM_PAYMENTS, grupo)) + geom_boxplot() + theme_classic()
Ventajas y desventajas
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). Así que aprenderemos ahora este método.
Clustering por K-mediodes
El algoritmo k-mediodes es una aproximación al clustering con k-means que se usa para particionar y agrupar datos en una cantidad k de clústeres. En este algoritmo cada clúster es representado por uno de sus puntos (k-medioide). El termino medioide se refiere a un objeto en el clúster para el que la distancia (Euclidiana o de Manhattan) entre él y todos los demás puntos del clúster es mínima. Corresponde al punto ubicado de forma más central en el clúster y pueden ser considerados como ejemplos representativos de los miembros del clúster en situaciones particulares.
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.
Una definición más exacta del término medoid es: 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.
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.
El algoritmo k-medioids es mucho más robusto que el de k-means debido a su propia construcción que es relativamente menos sensible a los cambios realizados en el clúster. Para ser llevado a cabo, se deben establecer la cantidad k de clústeres lo que genera una gran diferencia en los resultados de acuerdo con dicho valor. Pero entonces ¿Cómo sabemos que valor de k es apropiado?
Implementación de k-mediodes: PAM
El algoritmo PAM (Partitioning Around Medoids) en R se basa en la búsqueda de los k valores representativos dentro del set de observaciones. Después de halla un set de k-medioides, se construyen los clústeres asignando cada punto observado al medioide más cercano y a continuación se computa la función objetivo, función que corresponde a la suma de las distancias de todos los objetos con respecto a su k-medioide asignado. Internamente esto se realiza cambiando el k-medioide y evaluando la función objetivo a un valor mínimo. PAM incluye 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
Para hacer uso del algoritmo PAM debemos usar los paquetes Factoextra y Fpc. Podemos usar las funciones pam() del paquete clúster o pamk del paquete fpc. En el caso de pamk no es necesario que el usuario determine el número de clústeres, sin embargo, para pam() la sintaxis necesaria es:
pam(x, k, metric = "euclidean", stand = FALSE)
Donde: * x: representa los valores posibles, incluyendo dataframes, matrices de distancias o matrices numéricas donde cada columna corresponde a una variable y cada fila a una observación. NOTA: En el caso de las matrices de distancia se suelen usar los resultados de la función daisy() o dist().
K: El número de clústeres.
Metric: el tipo de distancia a usar (Eucludiana o Manhattan).
*Stand: valor lógico que indica si deben estandarizarse los valores de x antes de calcular las distancias, se ignora si x es una matriz de distancias.
Como podemos observar, el valor k (número de clústeres) es necesario para usar PAM, sin embargo, no existe un método directo que nos permita encontrarlo por lo que se hace uso de funciones como Silhouette o gap_stat. El procedimiento consiste en hacer uso de PAM con diferente número de clústeres, a continuación, se usa una función para generar un gráfico de valores promedio. Estos gráficos “miden” la calidad de un clustering. El número óptimo de clústeres estará dado según la función:
Para Silhouette será aquel valor que maximice el valor de la silueta (distancia entre clústeres) dentro del rango de valores k analizados.
Para gap_stat será aquel valor donde el valor de la brecha o distancia empiece a estabilizarse.
La función fviz_nbclust nos facilita este procedimiento, su estructura es:
data2 <- as.data.frame(scale(data1[1:150,2:18], center = TRUE))
library(factoextra)## Warning: package 'factoextra' was built under R version 4.1.1## Welcome! Want to learn more? See two factoextra-related books at https://goo.gl/ve3WBafviz_nbclust(x=data2, FUNcluster= pam, method = "silhouette")
Al igual que ocurría al aplicar K-means a estos datos, a partir de 6 clusters la reducción en la suma total de diferencias internas parece estabilizarse, indicando que K = 6 es una buena opción. Por tanto, ahora vamos a usar el método pam():
pam1 <- pam(data2, 6, metric = "manhattan", stand = FALSE)Para visualizar los resultados podemos usar fviz_cluster() que recibirá como argumento nuestros resultados de PAM, el dataframe y el tipo de distancias usadas para la elipse a formar:
fviz_cluster(pam1, data2, ellipse.type = "euclid", show.clust.cent= T)
Al final, como siempre hacemos, vamos a revisar nuestros grupos creados:
data2$grupo <- as.factor(pam1$clustering)
ggplot(data2, aes(BALANCE, grupo)) + geom_boxplot() + theme_classic()
ggplot(data2, aes(PURCHASES, grupo)) + geom_boxplot() + theme_classic()
Validación de los clusters
El coeficiente Silhouette mide que tan similar es un objeto a otros en su mismo cluster vs que tan similar es a los objetos en un cluster vecino. Valores cercanos a 1 indican que el objeto fue bien agrupado. Valores sobre 0.6 son aceptables y valores inferiores nos indican problemas con el objeto. Podemos apreciar el grafico de siluetas haciendo uso de fviz_silhouette() que recibe como parámetros nuestros resultados de pam(), la paleta de colores y el tema de ggplot.
fviz_silhouette(pam1, palette = "jco", ggtheme = theme_classic())## cluster size ave.sil.width
## 1 1 38 0.42
## 2 2 18 0.03
## 3 3 36 0.02
## 4 4 34 0.25
## 5 5 15 0.03
## 6 6 9 0.06
CLARA
Una de las limitaciones del método K-medoids-clustering es que su algoritmo requiere mucha memoria RAM, lo que impide que se pueda aplicar cuando el set de datos contiene varios miles de observaciones. CLARA (Clustering Large Applications) es un método que combina la idea de K-medoids con el resampling para que pueda aplicarse a grandes volúmenes de datos.
En lugar de intentar encontrar los medoids empleando todos los datos a la vez, CLARA selecciona una muestra aleatoria de un tamaño determinado y le aplica el algoritmo de PAM (K-medoids) para encontrar los clusters óptimos acorde a esa muestra. Utilizando esos medoids se agrupan las observaciones de todo el set de datos. La calidad de los medoids resultantes se cuantifica con la suma total de las distancias entre cada observación del set de datos y su correspondiente medoid (suma total de distancias intra-clusters). CLARA repite este proceso un número predeterminado de veces con el objetivo de reducir el bias de muestreo. Por último, se seleccionan como clusters finales los obtenidos con aquellos medoids que han conseguido menor suma total de distancias. A continuación, se describen los pasos del algoritmo CLARA.
- Se divide aleatoriamente el set de datos en n partes de igual tamaño, donde n es un valor que determina el analista.
Para cada una de las n partes:
Aplicar el algoritmo PAM e identificar cuáles son los k medoids.
Utilizando los medoids del paso anterior agrupar todas las observaciones del set de datos.
Calcular la suma total de las distancias entre cada observación del set de datos y su correspondiente medoid (suma total de distancias intra-clusters).
Seleccionar como clustering final aquel que ha conseguido menor suma total de distancias intra-clusters en el paso 3.
La función clara() del paquete cluster permite aplicar el algoritmo CLARA. Entre sus argumentos destaca: una matriz numérica x donde cada fila es una observación, el número de clusters k, la medida de distancia empleada metric (euclídea o manhattan), si los datos se tienen que estandarizar stand, el número de partes samples en las que se divide el set de datos (recomendable 50) y si se utiliza el algoritmo PAM pamLike.
data2 <- as.data.frame(scale(data1[1:150,2:18], center = TRUE))
cl1 <- clara(x = data2, k = 6, metric = "manhattan", stand = TRUE, samples = 50, pamLike = TRUE)Al igual que hicimos con PAM, vamos a verificar los resultados con fviz_cluster:
fviz_cluster(cl1,data2, show.clust.cent= T )
Con esto, por tanto, concluimos con nuestros métodos de clustering o agrupamiento.