k-medoides
El problema k -medoids es un problema de agrupamiento similar a k -means . El nombre fue acuñado por Leonard Kaufman y Peter J. Rousseeuw con su algoritmo PAM. [1] Los algoritmos k -means y k -medoids son particionales (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. En contraste con el algoritmo k - means, k -medoids elige puntos de datos reales como centros ( medoidso ejemplares), y por lo tanto permite una mayor interpretabilidad de los centros de conglomerados que en k -means, donde el centro de un conglomerado no es necesariamente uno de los puntos de datos de entrada (es el promedio entre los puntos en el conglomerado). Además, k -medoids se puede usar con medidas de disimilitud arbitrarias, mientras que k -means generalmente requiere una distancia euclidiana para soluciones eficientes. Debido a que k -medoids minimiza una suma de diferencias por pares en lugar de una suma de distancias euclidianas al cuadrado , es más resistente 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 k -medoids ). La "bondad" del valor dado de k se puede evaluar con métodos como el método de la silueta .
El medoid de un clúster se define como el objeto en el clúster cuya diferencia promedio con todos los objetos en el clúster es mínima, es decir, es un punto ubicado en el centro del clúster.
En general, el problema de k -medoides es NP-difícil de resolver con exactitud. Como tal, existen muchas soluciones heurísticas.
PAM [1] 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:
La complejidad del tiempo de ejecución del algoritmo PAM original por iteración de (3) es , calculando solo el cambio en el costo. Una implementación ingenua que vuelve 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 , al dividir el cambio de costo en tres partes, de modo que los cálculos se puedan compartir o evitar (FastPAM). [2] El tiempo de ejecución se puede reducir aún más si se realizan swaps (FasterPAM) con entusiasmo, [3] momento en el que una inicialización aleatoria se convierte en una alternativa viable a BUILD.
