k-medoides

El problema $de los k$ -medoides es un problema de agrupamiento similar al de $los k$ -medias . El nombre fue acuñado por Leonard Kaufman y Peter J. Rousseeuw con su algoritmo PAM (Partitioning Around Medoids). ^[1] Tanto el algoritmo de $los k$ -medias como el de $los k$ -medoides son particionarios (dividen el conjunto de datos en grupos) e intentan minimizar la distancia entre los puntos etiquetados para estar en un grupo y un punto designado como el centro de ese grupo. A diferencia del algoritmo de los $k$ -medias, $los k$ -medoides eligen puntos de datos reales como centros ( medoides o ejemplares), y por lo tanto permiten una mayor interpretabilidad de los centros de los grupos que en los $k$ -medias, donde el centro de un grupo no es necesariamente uno de los puntos de datos de entrada (es el promedio entre los puntos del grupo). Además, $los k$ -medoides se pueden utilizar con medidas de disimilitud arbitrarias, mientras que $los k$ -medias generalmente requieren la distancia euclidiana para soluciones eficientes. Debido a que $k$ -medoides minimiza una suma de diferencias por pares en lugar de una suma de distancias euclidianas al cuadrado , es más robusto al ruido y a los valores atípicos que $k$ -medias .

$k$ -medoids es una técnica clásica de partición de agrupamiento que divide el conjunto de datos de $n$ objetos en $k$ grupos, donde el número $k$ de grupos se supone conocido a priori (lo que implica que el programador debe especificar k antes de la ejecución de un $algoritmo k$ -medoids). La "bondad" del valor dado de $k$ se puede evaluar con métodos como el método de la silueta .

El medoide de un grupo se define como el objeto en el grupo cuya suma (y, equivalentemente, el promedio) de diferencias con todos los objetos del grupo es mínima, es decir, es el punto más centralmente ubicado en el grupo.

Algoritmos

En general, el problema $de los k$ -medoides es NP-difícil de resolver con exactitud, por lo que existen muchas soluciones heurísticas.

Particionado alrededor de medoides (PAM)

PAM ^[1] utiliza una búsqueda voraz que puede no encontrar la solución óptima, pero es más rápida que la búsqueda exhaustiva. Funciona de la siguiente manera:

(CONSTRUIR) Inicializar: seleccionar con avidez $k$ de los $n$ puntos de datos como medoides para minimizar el costo
Asocie cada punto de datos al medioide más cercano.
(SWAP) Mientras el costo de la configuración disminuye:
1. Para cada medoide m , y para cada punto de datos no medoide o :
  1. Considere el intercambio de $m$ y $o$ , y calcule el cambio de costo.
  2. Si el cambio de costo es el mejor actual, recuerde esta combinación m y o
2. Realizar el mejor intercambio de y , si disminuye la función de costo. De lo contrario, el algoritmo finaliza. $m_{\text{mejor}}$ $o_{\text{mejor}}$

La complejidad del tiempo de ejecución del algoritmo PAM original por iteración de (3) es , calculando únicamente el cambio en el costo. Una implementación ingenua que vuelva a calcular la función de costo completa cada vez estará en . Este tiempo de ejecución se puede reducir aún más a , dividiendo el cambio de costo en tres partes de modo que los cálculos se puedan compartir o evitar (FastPAM). El tiempo de ejecución se puede reducir aún más realizando intercambios con entusiasmo (FasterPAM), ^[2] en cuyo punto una inicialización aleatoria se convierte en una alternativa viable a BUILD. $O(k(nk)^{2})$ $O(n^{2}k^{2})$ $O(n^{2})$

Optimización alternada

También se han sugerido en la literatura algoritmos distintos de PAM, incluido el siguiente método de iteración de Voronoi conocido como heurística "Alternativa" en la literatura, ya que alterna entre dos pasos de optimización: ^[3]^[4]^[5]

Seleccionar medoides iniciales aleatoriamente
Iterar mientras el coste disminuye:
1. En cada grupo, haga que el punto que minimice la suma de distancias dentro del grupo sea el medoide.
2. Reasignar cada punto al grupo definido por el medoide más cercano determinado en el paso anterior

La iteración de Voronoi de estilo k -means tiende a producir peores resultados y exhibe un "comportamiento errático". ^[6]^{: 957} Debido a que no permite reasignar puntos a otros clústeres mientras se actualizan los medios, solo explora un espacio de búsqueda más pequeño. Se puede demostrar que incluso en casos simples, esta heurística encuentra soluciones inferiores a las que pueden resolver los métodos basados en intercambio. ^[2]

Agrupamiento jerárquico

Se han propuesto múltiples variantes de agrupamiento jerárquico con un "enlace medoide". El criterio de enlace de suma mínima ^[7] utiliza directamente el objetivo de los medoides, pero se ha demostrado que el enlace de aumento de suma mínima produce mejores resultados (de forma similar a cómo el enlace de Ward utiliza el aumento del error cuadrático). Los enfoques anteriores simplemente utilizaban la distancia de los medoides del grupo de los medoides anteriores como medida de enlace, ^[8]^[9] pero esto tiende a dar como resultado peores soluciones, ya que la distancia de dos medoides no garantiza que exista un buen medoide para la combinación. Estos enfoques tienen una complejidad de tiempo de ejecución de , y cuando el dendrograma se corta en un número particular de grupos k , los resultados normalmente serán peores que los resultados encontrados por PAM. ^[7] Por lo tanto, estos métodos son principalmente de interés cuando se desea una estructura de árbol jerárquico. $O(n^{3})$

Otros algoritmos

Otros algoritmos aproximados, como CLARA y CLARANS, sacrifican calidad por tiempo de ejecución. CLARA aplica PAM a múltiples submuestras, conservando el mejor resultado. CLARANS trabaja con todo el conjunto de datos, pero solo explora un subconjunto de los posibles intercambios de medoides y no medoides mediante muestreo. BanditPAM utiliza el concepto de bandidos multiarmados para elegir candidatos a intercambios en lugar de un muestreo uniforme como en CLARANS. ^[10]

Software

ELKI incluye varias variantes de k -medoides, incluidos k -medoides de iteración de Voronoi , el algoritmo PAM original, las mejoras de Reynolds y los algoritmos O(n²) FastPAM y FasterPAM, CLARA, CLARANS, FastCLARA y FastCLARANS.
Julia contiene una implementación k -medoid del algoritmo de estilo k-means (rápido, pero con una calidad de resultados mucho peor) en el paquete JuliaStats/Clustering.jl.
KNIME incluye una implementación de k -medoides que admite una variedad de medidas de distancia de matriz eficientes, así como una serie de implementaciones de k -medias nativas (e integradas de terceros).
Python contiene FasterPAM y otras variantes en el paquete "kmedoids", se pueden encontrar implementaciones adicionales en muchos otros paquetes
R contiene PAM en el paquete "cluster", incluidas las mejoras de FasterPAM a través de las opciones variant = "faster"y medoids = "random". También existe un paquete "fastkmedoids".
RapidMiner tiene un operador llamado KMedoids, pero no implementa ninguno de los algoritmos KMedoids anteriores. En cambio, es una variante de k-means, que sustituye la media por el punto de datos más cercano (que no es el medoide), lo que combina las desventajas de k-means (limitación a los datos de coordenadas) con el costo adicional de encontrar el punto más cercano a la media.
Rust tiene una caja "kmedoids" que también incluye la variante FasterPAM.
MATLAB implementa PAM, CLARA y otros dos algoritmos para resolver el problema de agrupamiento k -medoides.

Referencias

^ de Kaufman, Leonard; Rousseeuw, Peter J. (8 de marzo de 1990), "Partitioning Around Medoids (Program PAM)", Wiley Series in Probability and Statistics , Hoboken, NJ, EE. UU.: John Wiley & Sons, Inc., págs. 68-125, doi :10.1002/9780470316801.ch2, ISBN 978-0-470-31680-1, consultado el 13 de junio de 2021
^ ab Schubert, Erich; Rousseeuw, Peter J. (2021). "Agrupamiento rápido y entusiasta de k-medoides: mejora del tiempo de ejecución O(k) de los algoritmos PAM, CLARA y CLARANS". Sistemas de información . 101 : 101804. arXiv : 2008.05171 . doi :10.1016/j.is.2021.101804. S2CID 221103804.
^ Maranzana, FE (1963). "Sobre la localización de puntos de abastecimiento para minimizar los costos de transporte". IBM Systems Journal . 2 (2): 129–135. doi :10.1147/sj.22.0129.
^ T. Hastie, R. Tibshirani y J. Friedman. Los elementos del aprendizaje estadístico, Springer (2001), 468–469.
^ Park, Hae-Sang; Jun, Chi-Hyuck (2009). "Un algoritmo simple y rápido para la agrupación de K-medoides". Expert Systems with Applications . 36 (2): 3336–3341. doi :10.1016/j.eswa.2008.01.039.
^ Teitz, Michael B.; Bart, Polly (1968-10-01). "Métodos heurísticos para estimar la mediana generalizada de vértices de un gráfico ponderado". Investigación de operaciones . 16 (5): 955–961. doi :10.1287/opre.16.5.955. ISSN 0030-364X.
^ ab Schubert, Erich (2021). HACAM: agrupación aglomerativa jerárquica alrededor de medoides y sus limitaciones (PDF) . LWDA'21: Lernen, Wissen, Daten, Analysen del 1 al 3 de septiembre de 2021, Múnich, Alemania. págs. 191-204 - vía CEUR-WS.
^ Miyamoto, Sadaaki; Kaizu, Yousuke; Endo, Yasunori (2016). Agrupamiento jerárquico y no jerárquico de medoides utilizando medidas de similitud asimétrica. 2016, 8.ª Conferencia internacional conjunta sobre informática blanda y sistemas inteligentes (SCIS) y 17.º Simposio internacional sobre sistemas inteligentes avanzados (ISIS). págs. 400–403. doi :10.1109/SCIS-ISIS.2016.0091.
^ Herr, Dominik; Han, Qi; Lohmann, Steffen; Ertl, Thomas (2016). Reducción del desorden visual mediante proyección basada en jerarquía de datos etiquetados de alta dimensión (PDF) . Interfaz gráfica. Interfaz gráfica . doi :10.20380/gi2016.14 . Consultado el 4 de noviembre de 2022 .
^ Tiwari, Mo; Zhang, Martin J.; Mayclin, James; Thrun, Sebastian; Piech, Chris; Shomorony, Ilan (2020). "BanditPAM: Agrupamiento de k-medoides en tiempo casi lineal mediante bandidos multiarmados". Avances en sistemas de procesamiento de información neuronal . 33 .