¿Cómo se puede mostrar una solución Kmeans única?

Question

Supongamos que tenemos una distribución de P y de una constante K. queremos minimizar el kmeans objetivo w.r.t centros de ${C1,..Ck}$:

¿Qué restricciones en $P$ se sabe que implica que la solución óptima es única (hasta el reordenamiento de los centros)? Ejemplos de ad hoc métodos también sería apreciada. En particular intereset para mí son continuas distribuciones.

Un ejemplo para unidimensional $P(x)$$k=2$, con una única solución óptima:

$P(X=1)=0.5$

$P(X=-1)=0.5$

La única óptimo de los centros de se $C1=1, C2=-1$

Answer 1

K-means es una versión simplificada de Gaussian mixture models (GMM) en que es equivalente a un GMM con todos los componentes tienen la misma varianza. Es útil pensar en términos de la varianza debido a que su distribución muestral va a tener no sólo de tendencia central, pero variacional de la tendencia. Voy a asumir en este punto que el GMM es apropiado para el ajuste a los datos, que no son la colocación de una GMM no GMM de datos.

Si la muestra de datos es muy bien portado, de tal manera que la probabilidad de una falsa clasificación es muy bajo en los centros de clúster se colocan cerca de el real de los centros, entonces usted puede tener portado bien EM convergencia. La trama de la AIC (o AICc) vs iteración tenderá a converger rápidamente hacia una estable y de bajo valor. Si la muestra es menor a los bien portados, a continuación, usted puede tener una serie de problemáticas fenómenos como la falta de convergencia o de ciclismo de los medios entre un número de ubicaciones del centro. Es útil pensar de Cpk cuando se mira en las variaciones entre agrupado los componentes porque es una eficaz medida de la tasa de error en la clasificación. Se utiliza en los gráficos de control y de control de procesos para indicar probable que las tasas de error en la clasificación.

En este punto es muy tentador utilizar algunos "difusión esqe" método en el algoritmo para realizar el suavizado de la AIC de la parcela para estimar el punto de convergencia. Bajo la relajación es simple de implementar. Se usa EM para calcular la actualización de la posición de los medios, pero sólo mover algo de pequeña distancia hacia la nueva posición, a continuación, calcular de nuevo. Esto reduce el "ruido" de algunos, pero no en su totalidad. Usted tendrá una nueva esfera, el "factor de aprendizaje" o "factor de relajación". Este es EWMA en la posición de la media.

Usted puede utilizar remuestreo bootstrap dentro de los grupos para la estimación de la variación en la media para el grupo entre EM pasos. Si su centro de racimo se mantiene dentro de los osciló indicado por el remuestreo para una cierta cantidad de tiempo, usted podría asumir la convergencia.

Esta respuesta se basa completamente en la experiencia, no en la teoría, y que se da el algoritmo de direcciones, en lugar de teórica de la prueba. Es algo Ad-hoc, por lo que esperamos que haya sido de valor.

Answer 2

Primer problema, la solución no es única.

Un simple ejemplo es $P(X=-1)=P(X=0)=P(X=1)= \frac{1}{3}$

Esto nos da:

Dependiendo de las condiciones iniciales. Nos encontramos con este problema cuando tenemos muy particular de simetrías. En la práctica esto es muy raro, casi imposible.

Usted puede ser la mezcla de este problema con una segunda. La convergencia de basic k-means se concede a un mínimo local de la función de costo, no el mínimo global. Un ejemplo de la Wikipedia:

Usted puede adress este problema en muchas maneras: a partir de cerca de la solución óptima, de forma aleatoria a los puntos de partida... etc

Mientras que la unicidad de la solución óptima es casi seguro, usted puede terminar con muchas de las soluciones locales.