k-medoides

El problema de $los k$ -medoides es un problema de agrupamiento similar al $de las 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 $k$ -means como $el k$ -medoids son particionales (dividen el conjunto de datos en grupos) e intentan minimizar la distancia entre los puntos etiquetados como parte de un grupo y un punto designado como el centro de ese grupo. En contraste con el algoritmo $k -means,$ $k$ -medoids elige puntos de datos reales como centros ( medoides o ejemplares) y, por lo tanto, permite una mayor interpretabilidad de los centros del grupo que en $k$ -means, 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 $k$ -medias generalmente requiere una distancia euclidiana para soluciones eficientes. Debido a que $k$ -medoids minimiza una suma de disimilitudes por pares en lugar de una suma de distancias euclidianas al cuadrado , es más robusto al ruido y los valores atípicos que $k$ -means .

$k$ -medoids es una técnica de partición clásica 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 de 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 del grupo cuya suma (y, equivalentemente, el promedio) de diferencias con todos los objetos del grupo es mínima, es decir, es un punto ubicado más centralmente en el grupo.

Algoritmos

En general, el problema de $los k$ -medoides es NP-difícil de resolver exactamente. Como tal, existen muchas soluciones heurísticas.

Partición 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: seleccione 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 coste de la configuración disminuye:
1. Para cada medoide m y para cada punto de datos que no sea 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. Realice el mejor intercambio de y , si disminuye la función de costo. De lo contrario, el algoritmo termina. $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. Se implementará una implementación ingenua que recalcule toda la función de costos cada vez . 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 (FasterPAM), ^[2] momento en el cual 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 alterna

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]

Seleccione los medioides iniciales al azar
Iterar mientras el costo disminuye:
1. En cada grupo, haga que el punto que minimiza la suma de distancias dentro del grupo sea el medoide.
2. Reasigne cada punto al grupo definido por el medoide más cercano determinado en el paso anterior

La iteración Voronoi 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 durante la actualización, 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 que los métodos basados en swap pueden resolver. ^[2]

Agrupación jerárquica

Se han propuesto múltiples variantes de agrupamiento jerárquico con un "enlace medoide". El criterio de vinculación de suma mínima ^[7] utiliza directamente el objetivo de los medoides, pero se demostró que el vínculo de aumento de suma mínima produce mejores resultados (similar a cómo el vínculo Ward utiliza el aumento del error al cuadrado). Los enfoques anteriores simplemente usaban la distancia de los medoides del grupo de los medoides anteriores como medida de vinculación, ^[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árquica. $O(n^{3})$

Otros algoritmos

Otros algoritmos aproximados como CLARA y CLARANS intercambian calidad por tiempo de ejecución. CLARA aplica PAM en múltiples submuestras, manteniendo 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 con múltiples brazos para elegir intercambios de candidatos en lugar de un muestreo uniforme como en CLARANS. ^[10]

Software

ELKI incluye varias variantes de k -medoid, incluida una iteración de Voronoi k -medoids, 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 resultado mucho peor) en el paquete JuliaStats/Clustering.jl.
KNIME incluye una implementación k -medoid que admite una variedad de medidas de distancia matricial eficientes, así como una serie de implementaciones k -means nativas (y de terceros integradas)
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 de KMedoids anteriores. En cambio, es una variante de k-medias, que sustituye la media con el punto de datos más cercano (que no es el medoide), que combina los inconvenientes de k-medias (limitado a 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 de k -medoides.

Referencias

^ ab Kaufman, Leonard; Rousseeuw, Peter J. (8 de marzo de 1990), "Partitioning Around Medoids (Program PAM)", Serie Wiley en probabilidad y estadística , Hoboken, Nueva Jersey, EE. UU.: John Wiley & Sons, Inc., págs. doi :10.1002/9780470316801.ch2, ISBN 978-0-470-31680-1, recuperado el 13 de junio de 2021
^ ab Schubert, Erich; Rousseeuw, Peter J. (2021). "Agrupación rápida y entusiasta de k -medoids: 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 ubicación de los puntos de suministro para minimizar los costes de transporte". Revista de sistemas IBM . 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.
^ Parque, Hae-Sang; Jun, Chi-Hyuck (2009). "Un algoritmo simple y rápido para la agrupación de K-medoides". Sistemas Expertos con Aplicaciones . 36 (2): 3336–3341. doi : 10.1016/j.eswa.2008.01.039.
^ Teitz, Michael B.; Bart, Polly (1 de octubre de 1968). "Métodos heurísticos para estimar la mediana del vértice generalizado de un gráfico ponderado". La 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). Agrupación de medoides jerárquica y no jerárquica mediante medidas de similitud asimétricas. 2016 Octava Conferencia Internacional Conjunta sobre Computación Suave y Sistemas Inteligentes (SCIS) y 17º Simposio Internacional sobre Sistemas Inteligentes Avanzados (ISIS). págs. 400–403. doi :10.1109/SCIS-ISIS.2016.0091.
^ Señor, 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, Martín J.; Mayclin, James; Thrun, Sebastián; Piech, Chris; Shomorony, Ilán (2020). "BanditPAM: agrupación de k-Medoides en tiempo casi lineal a través de bandidos con múltiples brazos". Avances en los sistemas de procesamiento de información neuronal . 33 .