k-medoids
Tanto el k-medoids como el k-means son algoritmos que trabajan con particiones (dividiendo el conjunto de datos en grupos) y ambos intentan minimizar la distancia entre puntos que se añadirían a un grupo y otro punto designado como el centro de ese grupo.
En contraste con el algoritmo k-means, k-medoids escoge datapoints como centros y trabaja con una métrica arbitraria de distancias entre datapoints en vez de usar la norma
En 1987 se propuso este método para el trabajo con la norma
Un medoid puede ser definido como el objeto de un grupo cuya disimilaridad media a todos los objetos en el grupo es mínima.
Es el punto ubicado más hacia el centro en todo el grupo.
PAM utiliza una búsqueda golosa que puede no encontrar la solución óptima, pero es más rápido que la búsqueda exhaustiva.Trabaja como sigue: Otros algoritmos han sido sugeridos en la literatura, incluyendo el siguiente método de Iteración Voronoi: Agrupar el siguiente conjunto de datos de diez objetos en dos grupos (k = 2).
Considera el siguiente conjunto de datos: Inicializar k centros.
El costo está calculado utilizando distancia de Manhattan.
Costos al medoid más cercano están mostrados en negrita en la tabla.
Donde el costo entre cualesquier dos puntos se ha calculado utilizando la fórmula:
Si c1 y O′ son nuevo medoids, calcular el coste total implicado.
Así que la configuración no cambia y el algoritmo termina aquí (ya que no hay ningún cambio en los medoids).
En algunas situaciones estándares, k-medoids demuestra rendimiento mejor que k-means.
La parte más costosa del algoritmo es el cálculo de las distancias entre los puntos u objetos.
Si fuera aplicable un preprocesamiento cuadrático y el almacenamiento, la matriz de distancias puede ser precalculada para conseguir una mayor rapidez.
Existen ejemplos, donde los autores también introducen una heurística para escoger los k medoids iniciales.
