Tengo los resultados de los mejores centroides para múltiples (10) ejecuciones de k-means. ¿Cómo puedo comparar estos pesos para comprobar si están cerca o son diferentes?
Mi objetivo es comprobar si llego a los mismos mínimos locales después de entrenar con centros iniciales aleatorios.
En primer lugar, a menos que su problema de agrupación sea un problema de agrupación trivial, los mínimos globales serán prácticamente imposibles de resolver (requiere enumerar todos los puntos de agrupación posibles). Por lo tanto, la solución de múltiples ejecuciones diferentes probablemente lo colocará en múltiples mínimos locales.
Aquí hay un par de recursos que discuten por qué los algoritmos de k-means no encuentran los mínimos globales. https://stackoverflow.com/questions/14577329/why-doesnt-k-means-give-the-global-minima
¿Por qué k-means no da el mínimo global?
Una forma de comparar los pesos aprendidos es comparar la potencia expresiva de sus respectivos clasificadores. Una forma de hacerlo es utilizando la diferencia L2 al cuadrado. $$\sum_{c}\sum_{x \in c}{(c-x)^2}$$ Dónde $c$ es siempre clúster, y $x$ representa cada punto de datos registrado en ese clúster. Cuanto menor sea la pérdida, mejor será el clasificador.
No creo que la comparación directa de los pesos de los clusters te dé mucha información sobre las ejecuciones individuales de k-means.
EDITAR: El comentario de los autores aclaró un poco más la cuestión.
Digamos que queremos comparar los pesos de dos k-means. Digamos que el $i$ El k-means produce $k$ del centroide $C_i: {c^i_0,c^i_1,...c^i_k}$ Ahora bien, el problema de comparar directamente los clusters en el mismo índice para diferentes ejecuciones de k-mean es que los clusters no tienen que estar necesariamente localizados en un índice específico. En una ejecución un centroide puede aparecer en el primer índice, mientras que en otra ejecución ese mismo centroide puede aparecer en un índice diferente. Este es un enfoque muy ingenuo. $$D[i,j]=\begin{bmatrix} ||c^i_0-c^j_0||_2^2&||c^i_0-c^j_1||_2^2&||c^i_0-c^j_k||_2^2 \\0&||c^i_1-c^j_1||_2^2&||c^i_1-c^j_k||_2^2 \\0&0&||c^i_k-c^j_k||_2^2 \end{bmatrix}.$$ Es la distancia entre cada centroide en dos ejecuciones de k-means. Tenga en cuenta que esta matriz sólo tiene que ser calculada para el triángulo superior debido a la simetría en la función de distancia utilizada (cuadrado $L2$ ).Entonces se puede calcular la distancia total entre dos recorridos k-mean como $$D(i,j)=\sum_i{min(D_i)}$$ .
Este es un enfoque muy ingenuo. No establece la restricción de que los índices sólo pueden aparecer una vez en la función mínima ( $1$ a $1$ entre cada centroide en dos recorridos k-mean). Para generalizar este enfoque a $n$ k-mean corre, se puede construir otra matriz de distancia como la anterior con cada entrada $D_{i,j}=D[i,j]$ Permítanme reiterar que este es un enfoque muy ingenuo. Pero muestra la distancia entre dos k-means, y tiene la buena propiedad de que si dos ejecuciones de k-mean aprenden los mismos centroides exactos, independientemente del orden de la distancia $D[i,j]=0$ .
Hazme saber si esto ayuda.
Gracias @ArmenAghajanyan tu respuesta es brillante para comparar lo bien que los pesos clasificaron los datos. Lo que estoy tratando de hacer es ligeramente diferente, estoy utilizando una función de coste diferente de k-means estándar, estoy tratando de comprobar si la función tiene múltiples mínimos locales, por favor, vea mi pregunta completa aquí stats.stackexchange.com/questions/186130/
¿No podrías comprobar si obtienes el mismo valor de la función de coste para todas las soluciones? en ese caso significa que llegas al mismo mínimo local.
@Young_DataAnalyst He añadido un posible enfoque a mi problema, en la edición de mi respuesta.
Para complementar la respuesta de Armen Aghajanyan, supongo que es difícil comprobar si se obtiene el mínimo global a menos que se conozcan las propiedades teóricas del problema de agrupación.
Como sugirió, podría limitarse a comparar las 10 soluciones entre sí. Una forma empírica de cuantificar la similitud entre agrupaciones podría ser el uso de la distancia L2 al cuadrado de hecho.
Si tiene etiquetas de clústeres, también puede calcular la similitud entre clústeres mediante la función índice de consenso . Se trata de una similitud media entre todos los pares de agrupaciones.
Por ejemplo, puede utilizar la información mutua ajustada (AMI) en Matlab ( aquí o aquí ) como medida de similitud entre dos agrupaciones $U$ y $V$ . A continuación, el índice de consenso (IC) entre $n$ Las agrupaciones se definen como: $$ \mbox{CI} = \frac{2}{n(n-1)}\sum_{i < j} \mbox{AMI}(U_i,V_j) $$ Intenta echar un vistazo aquí como referencia. Si utiliza un medida de similitud ajustada para las comparaciones de clustering el IC es igual a 0 si allí las agrupaciones son aleatorias e independientes y es igual a 1 cuando son idénticas.
El índice Rand y el índice rand ajustado proporcionan un enfoque clásico, esta estadística se basa simplemente en los recuentos por pares entre agrupaciones. es.wikipedia.org/wiki/Rand_index
Gracias @JonathanLisic, sí, puedes utilizar cualquier medida de similitud entre agrupaciones que quieras. En realidad, el índice rand ajustado y la información mutua ajustada están conectados: arxiv.org/abs/1512.01286
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
