¿Por qué ' t k-significa dar el mínimo global?

Question

He leído que el k-means el algoritmo sólo converge a un mínimo local y no a un mínimo global. ¿Por qué es esto? Yo, lógicamente, pensar en cómo inicialización podría afectar a la final de la agrupación y hay una posibilidad de sub-óptima de la agrupación, pero no he encontrado nada que demostrar matemáticamente que.

También, ¿por qué k-significa un proceso iterativo? No podemos sólo parcialmente diferenciar la función objetivo w.r.t. a los centroides, igualar a cero para encontrar los centroides que minimiza esta función? ¿Por qué tenemos que usar el gradiente de la pendiente para alcanzar el mínimo paso por paso?

Answer 1

Usted puede ver k-means como una versión especial del algoritmo EM, que puede ayudar un poco.

Digamos que usted está en la estimación de una distribución normal multivariante para cada clúster con la matriz de covarianza fija a la matriz de identidad para todos, pero la variable media de $\mu_i$ donde $i$ es el cluster del índice. Claramente, si los parámetros de $\{\mu_i\}$ son conocidos, se puede asignar a cada punto de $p$ su probabilidad máxima de clúster (es decir. el $\mu_i$ para que la distancia de a $p$ mínimo). El algoritmo EM para este problema es casi equivalente a k-means.

De la otra manera, si usted sabe que los puntos que pertenecen a cada cluster, se puede estimar el óptimo $\mu_i$. La forma cerrada de la solución a este (que busca un óptimo global) básicamente dice que para encontrar los modelos de máxima verosimilitud $\{\hat\mu_i\}$ integrar sobre todas las posibles asignaciones de puntos a los clústeres. Ya que incluso con sólo treinta puntos y dos grupos, hay cerca de mil millones de posibles asignaciones, esto es imposible de calcular.

En su lugar, podemos tomar algunos adivinar los parámetros ocultos (o los parámetros del modelo) y repetir los dos pasos (con la posibilidad de acabar en un máximo local). Si usted permite que cada grupo para tomar una responsabilidad parcial por un punto, se termina con EM, si usted acaba de asignar el clúster óptimo, se obtiene k-means.

Así, resumen ejecutivo: en términos probabilísticos, no es una solución global, pero se requiere de usted para iterar sobre todos los posibles conglomerados. Claramente si se tiene una función objetivo, el mismo que es verdadero. Usted puede iterar sobre todas las soluciones y maximizar la función objetivo, pero el número de iteraciones es exponencial en el tamaño de los datos.

Answer 2

Un ejemplo sencillo podría ayudar..

Vamos a definir el conjunto de puntos que se agrupan como A = {1,2,3,4}.

Digamos que usted está tratando de encontrar 2 apropiadas de clústeres para Un (2-medio).Hay (al menos) dos configuraciones diferentes que satisfacen el estado estacionario de k-means.

Configuración 1: Center1 = 1, Cluster1 = {1} Center2 = 3, Cluster1 = {2,3,4} Aquí el objetivo es de 2. Como cuestión de hecho, este es un punto de silla (prueba center1= 1+epsilon y center1 = 1-epsilon)

Configuración 1: Center1 = 1.5, Cluster1 = {1,2} Center2 = 3.5, Cluster1 = {3,4} aquí el objetivo es de 1/4.

Si k-means se inicializaría como la primera opción sería, entonces, pegado.. y que no es un mínimos locales. Usted puede usar una variante del ejemplo anterior para crear dos mínimos locales. para A = {1,2,3,4,5}, configuración cluster1={1,2} y cluster2={3,4,5} se obtiene el mismo valor objetivo como cluster1={1,2,3} y cluster2={4,5}

por último, ¿qué pasaría si usted elige A = {1,2,3,4,6} center1={2.5} cluster1={1,2,3,4} y center1={6} cluster1={6} vs center1={2} cluster1={1,2,3} y center1={5} cluster1={4,6} ?

Answer 3

[Esto fue antes de la @Pedro respondió]
Después de una pequeña discusión (en la sección de comentarios), creo que debo responder a mi propia pregunta.

Yo creo que cuando me parcialmente diferenciar la función objetivo con respecto al centroide de los puntos en el cluster de otro centro de gravedad se desvanecen en el derivado. Así, el centroide podemos conseguir minimizar sólo la suma de los cuadrados de las distancias de sólo el clúster determinado.

@whuber añade:

Esa es, en parte, pero realmente no explicar el comportamiento. De mucho más importa es el hecho de que la asignación de puntos a los centroides es la gran parte de lo que k-means está haciendo. (Una vez que la tarea está hecha, los centroides son fácil de calcular, y no hay nada que hacer.) Que la asignación se discretos: no es algo que puede ser diferente a todos.

Sería estupendo si alguien tiene más que añadir.