algorithm - unica - teorema de existencia y unicidad ecuaciones diferenciales de primer orden ejemplos

K-means aglomeración unicidad de la solución

Question

¿El algoritmo de agrupamiento k-means siempre produce la misma solución? Se supone que la inicialización es aleatoria, ¿la agrupación converge al mismo resultado independientemente de la inicialización?

Answer 1

Se supone que la inicialización es aleatoria, ¿la agrupación converge al mismo resultado independientemente de la inicialización?

Todo lo contrario. Si el problema k- means fuera un problema agradable y convexo de optimización, no estaríamos inicializándolo aleatoriamente, ya que simplemente comenzar en (0,0, ..., 0) daría la respuesta correcta.

El motivo de la inicialización aleatoria es exactamente que puede obtener diferentes soluciones probando diferentes semillas aleatorias, y luego elegir la mejor cuando se ejecutan todas las ejecuciones de k- means. Diez carreras es una buena regla general para muchas aplicaciones.

Encontrar el mínimo global del problema k- means es NP-hard en general. El algoritmo común es realmente una heurística.

Answer 2

En realidad, la inicialización del algoritmo k-means tiene una clara influencia en el resultado obtenido. Para evitar una inicialización "mala" puede recurrir al algoritmo k-means ++ que soluciona este problema. Puede consultar esto en wikipedia ( http://en.wikipedia.org/wiki/K-means%2B%2B ).