K-Medoids

El algoritmo k-medoids es una técnica de agrupamiento relacionada con el clúster k-means (tema abordado en el capítulo 4), que permite dividir un conjunto de datos en grupos o clústeres k. En el caso del clúster k-medoids, cada clúster está representado por uno de los puntos de datos que lo conforman, conocidos como medoides de clúster.

El término “medoide” se refiere a un objeto dentro de un clúster cuya diferencia promedio con respecto a los demás miembros del clúster es mínima. Es como el punto más central del grupo. Estos objetos, uno por cada grupo, pueden considerarse ejemplos representativos de los miembros de ese grupo, lo cual resulta útil en ciertas situaciones. En contraste, en el clúster k-means, el centro de un clúster se calcula como el promedio de todos los puntos de datos que lo componen.

K-medoid representa una alternativa robusta al clúster k-means. Esto implica que el algoritmo es menos sensible al ruido y a los valores atípicos, ya que utiliza medoides como centros de clúster en lugar de medios, como lo hace k-means.

El algoritmo k-medoids requiere que el usuario especifique el valor de k, es decir, el número de clústeres que se desean generar (al igual que en el clúster k-means). Una forma útil de determinar el número óptimo de grupos es mediante el método de la silueta, el cual se describe en las secciones siguientes.

5.1 PAM concept

La utilización de “medios” implica que el clúster k-means es altamente sensible a los valores atípicos, lo cual puede tener un impacto significativo en la asignación de observaciones a los grupos. En contraste, el algoritmo PAM ofrece una solución más robusta.

5.2 PAM algorithm

El algoritmo PAM se fundamenta en la búsqueda de k objetos representativos o medoides dentro del conjunto de observaciones de los datos.

Una vez que se han encontrado k medoides, se procede a construir los clústeres asignando cada observación al medoide más cercano. Luego, se lleva a cabo un intercambio entre cada medoide m seleccionado y cada punto de datos no medoide, calculando la función objetivo. Esta función objetivo corresponde a la suma de las diferencias entre todos los objetos y su medoide más cercano.

El paso de intercambio (SWAP) tiene como objetivo mejorar la calidad del agrupamiento mediante el intercambio de objetos seleccionados (medoides) y objetos no seleccionados. Si al intercambiar un objeto seleccionado con un objeto no seleccionado la función objetivo se reduce, se realiza el intercambio. Este proceso continúa hasta que la función objetivo ya no pueda reducirse. El objetivo es encontrar k objetos representativos que minimicen la suma de las diferencias entre las observaciones y su objeto representativo más cercano.

En resumen, el algoritmo PAM se lleva a cabo en dos fases:

  1. Seleccionar k objetos para que actúen como medoides, o utilizar objetos proporcionados como medoides si están disponibles.

  2. Calcular la matriz de disimilitud en caso de que no se haya proporcionado previamente.

  3. Asignar cada objeto a su medoide más cercano.

  4. Para cada clúster, buscar si alguno de los objetos del clúster reduce el coeficiente medio de disimilitud. Si es así, seleccionar la entidad que más disminuye dicho coeficiente como medoide para ese clúster.

  5. Si al menos un medoide ha cambiado, volver al paso 3. Si no, finalizar el algoritmo.

Es importante tener en cuenta que el algoritmo PAM trabaja con una matriz de disimilitud, y para calcularla puede utilizar dos métricas:

  1. Distancias euclidianas, que consisten en la raíz cuadrada de la suma de los cuadrados de las diferencias.

  2. Distancia Manhattan, que es la suma de las diferencias absolutas.

Es válido destacar que, en la práctica, en la mayoría de los casos se obtendrán resultados similares utilizando tanto la distancia euclidiana como la distancia Manhattan. Sin embargo, si los datos contienen valores atípicos, la distancia Manhattan proporcionará resultados más robustos, mientras que la distancia euclidiana se verá influenciada por dichos valores inusuales.

library(cluster)
library(factoextra)
## Loading required package: ggplot2
## Welcome! Want to learn more? See two factoextra-related books at https://goo.gl/ve3WBa
library(ggplot2)
library(ggsignif)

5.3 Computing PAM in R

5.3.1 Data

Para éstos ejemplos se usará la base de datos de “USArrests”, la cual se usará con la función scale():

data("USArrests")
df <- scale (USArrests)
head(df, n = 3)
##             Murder   Assault   UrbanPop         Rape
## Alabama 1.24256408 0.7828393 -0.5209066 -0.003416473
## Alaska  0.50786248 1.1068225 -1.2117642  2.484202941
## Arizona 0.07163341 1.4788032  0.9989801  1.042878388

5.3.2 Required R packages and functions

Las funciones pam() y pamk() se utilizan en R para calcular el algoritmo PAM. La función pamk() no requiere que especifiques el número de clústeres, mientras que la función pam() sí lo requiere.

El formato simplificado de la función pam() es el siguiente:

pam(x, k, metric = “euclidean”, stand = FALSE)

  • x: Puede ser una matriz de datos numéricos o un marco de datos numéricos. Cada fila representa una observación y cada columna representa una variable. También puede ser una matriz de disimilitud, que es típicamente el resultado de las funciones daisy() o dist().

  • k: Especifica el número de clústeres.

  • metric: Indica la métrica de distancia a utilizar, que puede ser “euclidean” o “manhattan”.

  • stand: Un valor lógico que indica si se deben estandarizar las variables antes de calcular las disimilitudes. Este parámetro se ignora si x es una matriz de disimilitud. Para crear un gráfico de los clústeres generados con la función pam(), se recomienda utilizar el paquete factoextra.

Después de instalar los paquetes necesarios, los cargamos:

library(cluster)
library(factoextra)
library(ggplot2)

5.3.3 Estimating the optimal number of clusters

En la búsqueda del número adecuado de grupos, se emplea el método de promedio de la silueta al trabajar con R Markdown. El propósito es calcular el algoritmo PAM utilizando distintos valores de grupos (k) y graficar el promedio de la silueta de los grupos en relación al número de grupos. La silueta promedio es una medida de calidad de la agrupación, y se pretende encontrar el número óptimo de grupos (k) que maximice dicho valor. Una forma conveniente de estimar el número óptimo de grupos se encuentra en la función “fuiz_nbclust()” del paquete factoextra en R.

library(cluster)
library(factoextra)
fviz_nbclust(df, pam, method = "silhouette")+
  theme_classic()

Según el gráfico, se sugiere que el número óptimo de grupos es 2. En la próxima sección, procederemos a categorizar las observaciones en 2 grupos.

5.3.4 Computing PAM clustering

El codigo de abajo computa el algoritmo PAM con k = 2:

pam.res <- pam(df, 2)
print(pam.res)
## Medoids:
##            ID     Murder    Assault   UrbanPop       Rape
## New Mexico 31  0.8292944  1.3708088  0.3081225  1.1603196
## Nebraska   27 -0.8008247 -0.8250772 -0.2445636 -0.5052109
## Clustering vector:
##        Alabama         Alaska        Arizona       Arkansas     California 
##              1              1              1              2              1 
##       Colorado    Connecticut       Delaware        Florida        Georgia 
##              1              2              2              1              1 
##         Hawaii          Idaho       Illinois        Indiana           Iowa 
##              2              2              1              2              2 
##         Kansas       Kentucky      Louisiana          Maine       Maryland 
##              2              2              1              2              1 
##  Massachusetts       Michigan      Minnesota    Mississippi       Missouri 
##              2              1              2              1              1 
##        Montana       Nebraska         Nevada  New Hampshire     New Jersey 
##              2              2              1              2              2 
##     New Mexico       New York North Carolina   North Dakota           Ohio 
##              1              1              1              2              2 
##       Oklahoma         Oregon   Pennsylvania   Rhode Island South Carolina 
##              2              2              2              2              1 
##   South Dakota      Tennessee          Texas           Utah        Vermont 
##              2              1              1              2              2 
##       Virginia     Washington  West Virginia      Wisconsin        Wyoming 
##              2              2              2              2              2 
## Objective function:
##    build     swap 
## 1.441358 1.368969 
## 
## Available components:
##  [1] "medoids"    "id.med"     "clustering" "objective"  "isolation" 
##  [6] "clusinfo"   "silinfo"    "diss"       "call"       "data"

Los resultados revelan lo siguiente:

  • Las medias representativas de los grupos: una matriz que contiene los medoides en sus filas y las variables en sus columnas.

  • Los vectores de agrupamiento: un vector de enteros que indica, mediante números del 1 al k, a qué grupo pertenece cada punto.

Si se quiere añadir puntos de clasificación a los datos originales, se usa:

dd <- cbind(USArrests, cluster = pam.res$cluster)
head(dd, n = 3)
##         Murder Assault UrbanPop Rape cluster
## Alabama   13.2     236       58 21.2       1
## Alaska    10.0     263       48 44.5       1
## Arizona    8.1     294       80 31.0       1

5.3.5 Accessing to the results of the pam() funtion

La función pam() genera un objeto de tipo pam que contiene diferentes componentes, como los medoides que representan los grupos, y los “agrupamientos” que son un vector que indica el número de grupo al que pertenece cada objeto.

Para acceder a estos componentes, se puede utilizar el siguiente enfoque:

pam.res$medoids
##                Murder    Assault   UrbanPop       Rape
## New Mexico  0.8292944  1.3708088  0.3081225  1.1603196
## Nebraska   -0.8008247 -0.8250772 -0.2445636 -0.5052109
head(pam.res$clustering)
##    Alabama     Alaska    Arizona   Arkansas California   Colorado 
##          1          1          1          2          1          1

5.3.6 Vizualizing PAM clusters

Para representar la segmentación de los resultados, haremos uso de la función fviz_cluster() perteneciente al paquete factoextra. Mediante esta función, se generará un gráfico que muestra los datos agrupados. En el caso de que los datos contengan más de dos variables, se empleará el algoritmo PCA para reducir la dimensionalidad de los datos. De esta forma, se utilizarán únicamente las dos primeras dimensiones para la visualización de los datos.

library(rstatix)
## 
## Attaching package: 'rstatix'
## The following object is masked from 'package:stats':
## 
##     filter
fviz_cluster(pam.res,
             palette = c("#FF0080", "#FFC0CB"),
             ellipse.type = "t",
             repel = TRUE,
             ggtheme = theme_classic()
             )

5.4 Summary

El algoritmo PAM (Partitioning Around Medoids), también conocido como K-medoids, se presenta como una opción sólida frente al k-means para dividir conjuntos de datos en clústeres. En este enfoque, cada clúster se representa por un objeto seleccionado denominado medoide, que corresponde al punto más central del grupo. En R, se puede utilizar la función pam() para calcular PAM, indicando el número de clústeres deseados. La visualización de los resultados obtenidos con PAM se puede realizar mediante la función fviz_cluster() del paquete factoextra.

Para conjuntos de datos de gran tamaño, se sugiere emplear la función clam() en lugar de pam() como una alternativa más eficiente.