K-Medoids

El algoritmo k-medoids es un enfoque de agrupamiento similar al k-means para dividir un conjunto de datos en k grupos o clusters. En k-medoids, cada cluster se representa por un punto del conjunto de datos, llamado medoid. Un medoid es un objeto dentro del cluster cuya disimilitud promedio con todos los demás miembros es mínima, siendo el punto más central del cluster. Esto lo hace un representante útil del cluster en ciertas situaciones. A diferencia de k-means, que utiliza la media de los puntos para determinar el centro del cluster, k-medoids es menos sensible al ruido y a los valores atípicos, ya que usa medoids como centros de los clusters. El usuario debe especificar k, el número de clusters a generar. Un método útil para determinar el número óptimo de clusters es el método del silhouette. El método más común de k-medoids es el algoritmo PAM (Partitioning Around Medoids).

Concepto de PAM

El uso de medias en k-means hace que sea muy sensible a los valores atípicos, lo cual puede afectar gravemente la asignación de observaciones a los clusters. El algoritmo PAM ofrece una alternativa más robusta.

Algoritmo PAM

El algoritmo PAM busca k objetos representativos o medoids entre las observaciones del conjunto de datos. Una vez encontrados los k medoids, se construyen los clusters asignando cada observación al medoid más cercano. Luego, se intercambian cada medoid seleccionado y cada punto de datos que no es medoid, y se calcula la función objetivo, que es la suma de las disimilitudes de todos los objetos con su medoid más cercano. El paso de INTERCAMBIO intenta mejorar la calidad del agrupamiento al cambiar objetos seleccionados (medoids) y no seleccionados. Si la función objetivo se reduce al intercambiar un objeto seleccionado con uno no seleccionado, se realiza el intercambio. Esto continúa hasta que la función objetivo ya no pueda disminuir. El objetivo es encontrar k objetos representativos que minimicen la suma de las disimilitudes de las observaciones a su objeto representativo más cercano. En resumen, el algoritmo PAM se desarrolla en dos fases:

Pasos del Algoritmo PAM

  1. Seleccionar k objetos para que se conviertan en los medoids o, si estos objetos fueron proporcionados, utilizarlos como medoids.
  2. Calcular la matriz de disimilitud si no fue proporcionada.
  3. Asignar cada objeto a su medoid más cercano.
  4. Para cada cluster, buscar si algún objeto del cluster reduce el coeficiente de disimilitud promedio; si lo hace, seleccionar la entidad que más reduce este coeficiente como el medoid del cluster.
  5. Si al menos un medoid ha cambiado, volver al paso 3; de lo contrario, finalizar el algoritmo.

Como se mencionó anteriormente, el algoritmo PAM trabaja con una matriz de disimilitud, y para calcular esta matriz, el algoritmo puede usar dos métricas:

  1. Las distancias euclidianas, que son la raíz de la suma de los cuadrados de las diferencias.

  2. La distancia de Manhattan, que es la suma de las distancias absolutas.

Cálculo de PAM en R

Datos

Utilizaremos los conjuntos de datos de demostración "USArrests", los cuales comenzaremos escalando (Capítulo 2) utilizando la función scale() de R de la siguiente manera:

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

Paquetes y Funciones de R Requeridos

Las funciones pam() [paquete cluster] y pamk() [paquete fpc] pueden ser utilizadas para calcular PAM. La función pamk() no requiere que el usuario decida el número de clusters K. En los siguientes ejemplos, describiremos únicamente la función pam(), cuyo formato simplificado es:

pam(x, k, metric = "euclidean", stand = FALSE)

  • x: Los valores posibles incluyen: - Matriz de datos numéricos o marco de datos numéricos: cada fila corresponde a una observación y cada columna corresponde a una variable. - Matriz de disimilitud: en este caso, x es típicamente el resultado de daisy() o dist().

  • k: El número de clusters.

  • metric: La métrica de distancia a utilizar. Las opciones disponibles son “euclidiana” y “manhattan”.

  • stand: Valor lógico; si es verdadero, las variables (columnas) en x se estandarizan antes de calcular las disimilitudes. Se ignora cuando x es una matriz de disimilitud.

Para crear un gráfico atractivo de los clusters generados con la función pam(), utilizaremos el paquete factoextra.

  1. Instalando los paquetes requeridos:}

    options(repos = c(CRAN = "https://cran.r-project.org"))
    install.packages(c("cluster", "factoextra"))
    ## Installing packages into 'C:/Users/Lehna Rincon/AppData/Local/R/win-library/4.3'
## (as 'lib' is unspecified)
    ## package 'cluster' successfully unpacked and MD5 sums checked
## package 'factoextra' successfully unpacked and MD5 sums checked
## 
## The downloaded binary packages are in
##  C:\Users\Lehna Rincon\AppData\Local\Temp\RtmpGYqbD1\downloaded_packages

  2. Cargando los paquetes:

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

Estimación del número óptimo de clusters

Para estimar el número óptimo de clusters, utilizaremos el método del silhouette promedio. La idea es calcular el algoritmo PAM utilizando diferentes valores de clusters k. A continuación, se traza el silhouette promedio de los clusters en función del número de clusters. El silhouette promedio mide la calidad de un agrupamiento. Un ancho de silhouette promedio alto indica un buen agrupamiento. El número óptimo de clusters k es aquel que maximiza el silhouette promedio sobre un rango de valores posibles para k (Kaufman y Rousseeuw [1990]). La función R fviz_nbclust() [paquete factoextra] proporciona una solución conveniente para estimar el número óptimo de clusters.

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

Cálculo de Agrupamiento PAM

El código R a continuación calcula 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"

Si deseas agregar las clasificaciones de los puntos a los datos originales, utilice esto:

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

Acceder a los resultados de la función pam()

La función pam() devuelve un objeto de clase pam cuyos componentes incluyen:

  • Medoids: Objetos que representan los clusters

  • Clustering: un vector que contiene el número de cluster de cada objeto

Estos componentes pueden ser accedidos de la siguiente manera:

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

Visualización de Clusters PAM

Para visualizar los resultados de la partición, utilizaremos la función fviz_cluster() [paquete factoextra]. Esta función dibuja un gráfico de dispersión de los puntos de datos coloreados por los números de cluster. Si los datos contienen más de 2 variables, se utiliza el algoritmo de Análisis de Componentes Principales (PCA) para reducir la dimensionalidad de los datos. En este caso, se utilizan las dos primeras dimensiones principales para trazar los datos.

fviz_cluster(pam.res,
             palette = c("#00AFBB", "#FC4E07"),
             ellipse.type = "t", 
             repel = TRUE, 
             ggtheme = theme_classic()
)

Resumen

El algoritmo k-medoids, PAM, es una alternativa robusta a k-means para dividir un conjunto de datos en clusters de observaciones. En el método k-medoids, cada cluster está representado por un objeto seleccionado dentro del cluster. Estos objetos seleccionados se llaman medoids y corresponden a los puntos más centralmente ubicados dentro del cluster. El algoritmo PAM requiere que el usuario conozca los datos e indique el número apropiado de clusters a producir. Esto puede ser estimado utilizando la función fviz_nbclust [en el paquete R factoextra]. La función R pam() [paquete cluster] puede ser utilizada para calcular el algoritmo PAM. El formato simplificado es pam(x, k), donde “x” son los datos y k es el número de clusters a generar. Después de realizar el agrupamiento PAM, la función R fviz_cluster() [paquete factoextra] puede ser utilizada para visualizar los resultados. El formato es fviz_cluster(pam.res), donde pam.res son los resultados de PAM.