¿Por qué es probabilístico el algoritmo k-means ++?

Question

El k-means++ del algoritmo proporciona una técnica para elegir la inicial k semillas para el k-means el algoritmo. Esto se hace por muestreo el siguiente punto de acuerdo a una distribución multinomial sobre el unchosen puntos (donde la probabilidad de que un punto de ser elegido como el próximo centro es proporcional a $D(x)^2$ $D(x)$ siendo la distancia del punto de $x$ a su más cercano centro).

El punto con la mayor distancia que tiene la mayor probabilidad de ser elegido, pero ¿por qué no puedo elegir este punto de cada vez? ¿Qué ventaja voy a ganar por ser 'fuzzy' con mi selección de la semilla?

Answer 1

Usted obtener teórica de las garantías de las soluciones: la solución encontrada por k-means inicializado de esta manera está cerca de la correcta k-means solución (en espera) con un conocido constante, cf. estas diapositivas, por ejemplo.

Con el método que mencionas (que fue utilizado previamente en la literatura), usted puede construir algunas configuraciones en las que se comporta mal (creo que de un punto en una separación de hyperplane pero muy lejos) de seguro (desde determinista).

Answer 2

1. K-means puede quedar atrapado en mínimos locales.

Debido a esto, es una mejor práctica para ejecutar varias veces y mantener el mejor resultado (mejor por SSQ).

Si usted elige siempre el punto más lejano, usted obtendrá el mismo resultado cada vez. Así que quieres un poco de aleatoriedad!

2. El punto más lejano es no el mejor centro de gravedad candidato. Por lo general es demasiado lejos.

El punto tiene la más alta probabilidad de ser elegido, pero el promedio del punto elegido es mucho más cercana. Si hay 10 puntos de distancia^2 10, y un punto en la distancia^2 11, entonces el algoritmo es más probable que elija uno de los clúster de puntos que el último valor atípico.