Es probable que a menudo se sienta decepcionado por la solución que se le ocurre a cualquier ejecución particular del "algoritmo k-medias" (es decir, el algoritmo de Lloyd). Eso es porque el algoritmo de Lloyd a menudo se queda atascado en malos mínimos locales.
Afortunadamente, Lloyd's es solo una forma de resolver k-means. Y hay un enfoque que casi siempre encuentra mejores mínimos locales.
El truco consiste en actualizar las asignaciones de clúster de los puntos de datos de uno en uno. Puede hacerlo de manera eficiente manteniendo un recuento de la cantidad de puntos n asignados a cada media. Para que pueda volver a calcular significa el cluster m después de quitar el punto x de la siguiente manera:
m_new = (n * m - x)/(n - 1)
Y añadir x a agruparse media m usando:
m_new = (n * m + x)/(n + 1)
Por supuesto, ya que no puede ser vectorizado, es un poco doloroso ejecutar MATLAB, pero no está mal en otros idiomas.
Si está realmente interesado en obtener los mejores mínimos locales posibles y no le molesta utilizar clústeres basados en ejemplos, debe consultar affinity propagation. Las implementaciones de MATLAB están disponibles en el Frey lab affinity propagation page.
Supongo que tiene razón. Para obtener una mejor convergencia, en cambio, modifiqué mi algoritmo para hacer varios intentos con diferentes centros de masa iniciales, y luego determinar el mejor midiendo la varianza de los clústeres. La varianza media baja en un intento es igual a los grupos compactos. ¿Como suena eso? – Theodor
@Theodor: Este es un posible criterio de hecho. –