El problema de k -medoides es un problema de agrupamiento similar a k -medias . Tanto los algoritmos k -medios como los k -medoides son particionales (dividiendo 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. En contraste con el algoritmo de k- medias, k -medoides elige puntos de datos reales como centros ( medoides o ejemplares) y, por lo tanto, permite una mayor interpretabilidad de los centros del clúster que en k-medios, donde el centro de un conglomerado no es necesariamente uno de los puntos de datos de entrada (es el promedio entre los puntos del conglomerado). Además, los k -medoides se pueden usar con medidas de disimilitud arbitrarias, mientras que los k -medios generalmente requieren una distancia euclidiana para soluciones eficientes. Debido a que k -medoides minimiza una suma de disimilitudes por pares en lugar de una suma de distancias euclidianas al cuadrado , es más robusto al ruido y valores atípicos que k- medias .
k -medoids es una técnica clásica de partición de clustering que divide el conjunto de datos de n objetos en k clusters, donde el número k de clusters se supone conocido a priori (lo que implica que el programador debe especificar k antes de la ejecución de unalgoritmo de k -medoids ). La "bondad" del valor dado de k puede evaluarse con métodos como el método de la silueta .
El medoide de un grupo se define como el objeto en el grupo cuya disimilitud promedio con todos los objetos en el 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 utiliza una búsqueda codiciosa que puede no encontrar la solución óptima, pero es más rápida que una 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
- Asocia cada punto de datos al medoide más cercano.
- (SWAP) Mientras que el costo de la configuración disminuye:
- Para cada medoide m , y para cada punto de datos no medoide o :
- Considere el canje de m y O , y calcular el cambio de costos
- Si el cambio de costo es el actual mejor, recuerda esto m y o combinación
- Realice el mejor intercambio de y , si disminuye la función de costo. De lo contrario, el algoritmo termina.
- Para cada medoide m , y para cada punto de datos no medoide o :
La complejidad en 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 vuelve a calcular la función de costo completa cada vez que 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. [1]
Otros algoritmos
En la literatura también se han sugerido algoritmos distintos de PAM, incluido el siguiente método de iteración de Voronoi : [2] [3] [4]
- Seleccionar medoides iniciales al azar
- Iterar mientras el costo disminuye:
- En cada grupo, haga el punto que minimiza la suma de distancias dentro del grupo el medoide
- Reasigne cada punto al grupo definido por el medoide más cercano determinado en el paso anterior.
Sin embargo, la iteración de Voronoi de estilo k -medias encuentra peores resultados, ya que no permite reasignar puntos a otros clústeres mientras se cambian las medias y, por lo tanto, solo explora un espacio de búsqueda más pequeño. [1] [5]
Otros algoritmos aproximados como CLARA y CLARANS intercambian optimización 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.
Software
- ELKI incluye varias variantes de k -medoides, incluyendo un k -medoides de iteración de Voronoi, el algoritmo PAM original, las mejoras de Reynolds y el algoritmo O (n²) FastPAM, CLARA, CLARANS, FastCLARA y FastCLARANS.
- Julia contiene una implementación k -medoid del algoritmo de estilo k-means (más rápido, pero con una calidad de resultado mucho peor) en el paquete JuliaStats / Clustering.jl .
- KNIME incluye una implementación de k- medoid que admite una variedad de medidas de distancia de matriz eficientes, así como una serie de implementaciones de k- medias 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 algunas de las mejoras de FastPAM a través de la opción pamonce = 5. También existe un paquete "fastkmedoids".
- RapidMiner tiene un operador llamado KMedoids, pero no implementa el algoritmo KMedoids correctamente. 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).
- 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
- ↑ a b Schubert, Erich; Rousseeuw, Peter J. (2019), Amato, Giuseppe; Gennaro, Claudio; Oria, Vincent; Radovanović, Miloš (eds.), "Agrupación de k-Medoides más rápida: mejora de los algoritmos PAM, CLARA y CLARANS", Búsqueda y aplicaciones de similitudes , Springer International Publishing, 11807 , págs. 171-187, arXiv : 1810.05691 , doi : 10.1007 / 978-3-030-32047-8_16 , ISBN 9783030320461
- ^ Maranzana, FE (1963). Sobre la ubicación de los puntos de suministro para minimizar los costos de transporte ”. Revista de sistemas de 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.
- ^ Park, 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". Investigación operativa . 16 (5): 955–961. doi : 10.1287 / opre.16.5.955 . ISSN 0030-364X .