CHAPTER 5: K-MEDOIDS
Mariana Montoya
2023-05-12
CHAPTER 5 K-MEDOIDS
El algoritmo k-medoids es una técnica de agrupamiento que se utiliza para dividir un conjunto de datos en k grupos. A diferencia del algoritmo k-means, en k-medoids cada clúster está representado por un punto de datos llamado medoide, que es el objeto más central en el clúster. El método PAM (Partitioning Around Medoids) es uno de los enfoques más comunes para realizar el agrupamiento k-medoids. En este artículo se describe el algoritmo PAM y se proporcionan ejemplos prácticos utilizando el software R. También se menciona una variante de PAM llamada CLARA, que se utiliza para analizar grandes volúmenes de datos.
5.1 PAM CONCEPT
El uso de promedios implica que el agrupamiento k-means es altamente sensible a los valores atípicos, lo que puede afectar severamente la asignación de observaciones a clústeres. Un algoritmo más robusto es proporcionado por el algoritmo PAM.
5.2 PAM ALGORITHM
El algoritmo PAM es un enfoque utilizado para el agrupamiento de datos. Consiste en encontrar objetos representativos, llamados medoides, entre las observaciones del conjunto de datos. Se forman clústeres asignando cada observación al medoide más cercano. Luego, el algoritmo realiza un paso de intercambio para mejorar la calidad del agrupamiento mediante el intercambio de medoides seleccionados con objetos no seleccionados. Este proceso continúa hasta que la función objetivo, que mide las disimilitudes de los objetos con respecto a sus medoides más cercanos, ya no pueda disminuir. El objetivo es encontrar k objetos representativos que minimicen la suma de disimilitudes con sus medoides más cercanos. El algortimo PAM procede en dos fases como se muestra a continuación:
El algoritmo PAM consta de los siguientes pasos:
-Seleccionar k objetos para que se conviertan en los medoides, o utilizar los objetos proporcionados como medoides. -Calcular la matriz de disimilitud si no se proporcionó previamente. -Asignar cada objeto a su medoide más cercano. -Para cada clúster, buscar si alguno de los objetos del clúster reduce el coeficiente de disimilitud promedio. Si es así, seleccionar la entidad que reduzca este coeficiente en mayor medida como el medoide para ese clúster.
Si al menos un medoide ha cambiado, regresar al paso 3; de lo contrario, finalizar el algoritmo.
El algoritmo PAM trabaja con una matriz de disimilitud y puede utilizar dos métricas para calcularla: -Distancias euclidianas, que son la raíz cuadrada de la suma de los cuadrados de las diferencias. -Distancia de Manhattan, que es la suma de las diferencias absolutas. -Es importante tener en cuenta que, en la práctica, tanto la distancia euclidiana como la distancia de Manhattan suelen proporcionar resultados similares. Sin embargo, si tus datos contienen valores atípicos, la distancia de Manhattan tiende a ser más robusta, mientras que la distancia euclidiana puede verse afectada por estos valores inusuales.
5.3 COMPUTING PAM IN R
5.3.1 DATA
Se usará el demo “USArrests”, en donde usaremos la función scale().
#cargar el dataframe
data("USArrests")
#escalar el dataframe
df <- scale(USArrests)
#observar las 3 primeras filas de nuestro dataframe
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.0428783885.3.2 REQUIRED R PACKAGES AND FUNCTIONS
Las funciones pam() y pamk() son utilizadas para calcular el algoritmo PAM en R. La función pamk() no requiere que el usuario especifique 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, donde cada fila corresponde a una observación y cada columna corresponde a 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” (euclidiana) 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.
Luego de instalar los paquetes necesarios, los cargamos:
library("cluster")## Warning: package 'cluster' was built under R version 4.2.3library("factoextra")## Warning: package 'factoextra' was built under R version 4.2.3## Loading required package: ggplot2## Welcome! Want to learn more? See two factoextra-related books at https://goo.gl/ve3WBa5.3.3 ESTIMATING THE OPTIMAL NUMBER OF CLUSTERS
Para estimar el número óptimo de clústeres, se utiliza el método del promedio de la silueta. El objetivo es calcular el algoritmo PAM con diferentes valores de clústeres k y trazar el promedio de la silueta de los clústeres en función del número de clústeres. La silueta promedio mide la calidad del agrupamiento, y se busca el número óptimo de clústeres k que maximice la silueta promedio. La función fuiz_nbclust() del paquete factoextra en R proporciona una solución conveniente para estimar el número óptimo de clústeres.
fviz_nbclust(df,pam,method = "silhouette") + theme_classic()
De la gráfica el número de grupos sigerido es 2. En la siguiente
sección, clasificaremos las obervaciones en 2 grupos.
5.3.4 COMPUTING PAM CLUSTERING
El código de R a continuación 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 muestran: -Los grupos medoides: una matrix, cuyas filas son los medoides y las columnas las variables. -Los vectores agrupados: Un vector de enteros: un vector de números enteros (de 1:k) indicando el grupo al que 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 15.3.5 ACCESSING TO THE RESULTS OF THE PAM() FUNCTION
La función pam() devuelve un objeto de clase pam, cuyos componentes incluyen: - medoides: objetos que representan grupos - agrupamientos: un vector que contiene el grupo del número de cada objeto.
Se puede acceder a los componentes de la siguiente manera:
#cluster medoides: new Mexico, Nebraska
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#numero de grupos
head(pam.res$clustering)## Alabama Alaska Arizona Arkansas California Colorado
## 1 1 1 2 1 15.3.6 VISUALIZING PAM CLUSTERS
Para visualizar el fraccionamiento de los resultados, usaremos la función fviz_cluster() del paquete factoextra. Como vemos, se dibuja la gráfica con los datos de los grupos. Si los datos constan con más de dos variables, el algoritmo del PCA se usa para reducir la dimensionalidad de los datos. Como podemos observar, en este caso, las dos primeras dimensiones on usadas para graficar los datos.
fviz_cluster(pam.res, palette = c("#00AFBB", "#FC4E07"), ellipse.type = "t", repel = TRUE, ggtheme = theme_classic())
5.4 Summary
El algoritmo K-medoids, PAM, es una alternativa robusta al k-means para la partición de conjuntos de datos en clústeres. En PAM, cada clúster está representado por un objeto seleccionado llamado medoide, que es el punto más central del clúster. Se utiliza la función pam() en R para calcular PAM, donde se especifica el número de clústeres a generar. Los resultados de PAM pueden visualizarse utilizando la función fviz_cluster() del paquete factoextra. Para conjuntos de datos grandes, se recomienda utilizar la función clam() en lugar de pam().