Si la agrupación k-means es una forma de modelización de mezclas gaussianas, ¿puede utilizarse cuando los datos no son normales?

Question

Estoy leyendo a Bishop sobre el algoritmo EM para GMM y la relación entre GMM y k-means.

En este libro se dice que k-means es una versión de asignación dura de GMM. Me pregunto si eso implica que si los datos que intento agrupar no son gaussianos, no puedo usar k-means (o al menos no es adecuado usarlo). Por ejemplo, ¿qué pasa si los datos son imágenes de dígitos escritos a mano, que consta de 8 * 8 píxeles cada uno con valor 0 o 1 (y asumir que son independientes por lo tanto debe ser mezcla de Bernoulli)?

Estoy un poco confuso al respecto y agradeceré cualquier opinión.

Answer 1

En situaciones típicas de EM GMM, se tienen en cuenta la varianza y la covarianza. Esto no se hace en k-means.

Pero, de hecho, una de las heurísticas populares para k-means (nota: k-means es un problema, no un algoritmo) -el algoritmo Lloyd- es esencialmente un algoritmo EM, que utiliza un modelo de centroide (sin varianza) y asignaciones duras.

Cuando se realiza una agrupación al estilo k-means (es decir, minimización de la varianza), usted

• casualmente minimizan la distancia euclídea al cuadrado, porque la contribución de la varianza WCSS (suma de cuadrados dentro del cluster) = distancia euclídea al cuadrado.
• asignan casualmente los objetos al cluster más cercano por distancia euclidiana, ya que la función sqrt es monótona (nótese que la media no no optimizar las distancias euclidianas, sino la función WCSS)
• representar conglomerados utilizando sólo un centroide
• obtener agrupaciones en forma de células de Voronoi, es decir, polígonos
• funciona mejor con grupos esféricos

La función objetivo k-means puede formalizarse de la siguiente manera: $$\text{argmin}_S \sum_{i=1}^{k} \sum_{x_j \in S_i} \sum_{d=1}^{D} \left(x_{jd} - \mu_{id} \right)^2$$ donde $S=\{S_1 \ldots S_k\}$ son todas las particiones posibles del conjunto de datos en $k$ particiones, $D$ es la dimensionalidad del conjunto de datos, y por ejemplo $x_{jd}$ es la coordenada del $j$ ª instancia en la dimensión $d$ .

Se suele decir que k-means asume clusters esféricos. También se suele reconocer que los clusters de k-means son células de Voronoi, es decir, no esféricas. Ambas cosas son correctas, y ambas son erróneas. En primer lugar, los clusters no son células de Voronoi completas, sino sólo los objetos conocidos que contienen. No hay necesidad de considerar el espacio muerto entre los clusters como parte de ninguno de los clusters, ya que tener un objeto allí afectaría al resultado del algoritmo. Pero tampoco es mucho mejor llamarlo "esférico", sólo porque la distancia euclídea es esférica. A K-means no le importa la distancia euclidiana. Todo lo que es, es una heurística para minimizar la desviaciones . Y eso es en realidad, lo que usted debe considerar k-means a ser: la minimización de la varianza.

Answer 2

El MMG utiliza solapamiento colinas que se extienden hasta el infinito (pero prácticamente sólo cuentan para 3 sigma). Cada punto recibe todos las puntuaciones de probabilidad de las colinas. Además, las colinas tienen "forma de huevo" [vale, son simétricas elipses ] y, utilizando la matriz de covarianza completa, puede ser inclinado .

K-means asigna un punto a un solo por lo que se ignoran las puntuaciones de los otros centros de cluster (se ponen implícitamente a cero/no importan). Las colinas son pompas de jabón esféricas. Cuando dos pompas de jabón se tocan, el límite entre ellas se convierte en un (hiper)plano. Del mismo modo que cuando soplas una espuma de muchas pompas de jabón, las pompas del interior no son planas, sino que tienen forma de caja, los límites entre muchas (hiper)esferas forman en realidad una partición de Voronoi del espacio. En 2D, esto tiende a parecerse vagamente a un empaquetamiento hexagonal, como una colmena de abejas (aunque, por supuesto, no está garantizado que las celdas de Voronoi sean hexágonos). Una colina K-means es redonda y no se inclina, por lo que tiene menos poder de representación; pero es mucho más rápida de calcular, especialmente en las dimensiones más altas.

Como K-means utiliza la métrica de distancia euclidiana, asume que las dimensiones son comparables y tienen el mismo peso. Así que si la dimensión X tiene unidades de millas por hora, que varían de 0 a 80, y la dimensión Y tiene unidades de libras, que varían de 0 a 400, y usted está ajustando círculos en este espacio XY, entonces una dimensión (y su dispersión) va a ser más potente que la otra dimensión y eclipsará los resultados. Por eso es habitual normalizar los datos al tomar K-means.

Tanto GMM como K-means modelo los datos ajustando las mejores aproximaciones a lo dado. GMM se ajusta a los huevos inclinados y K-means a las esferas inclinadas. Pero los datos subyacentes podrían tener la forma que quisieran, podrían ser una espiral o un cuadro de Picasso, y cada algoritmo seguiría funcionando y haciendo su mejor intento. Que el modelo resultante se parezca o no a los datos reales depende del proceso físico subyacente que los genera. (Por ejemplo, las mediciones de retardo temporal son unilaterales; ¿se ajusta bien una gaussiana? Tal vez).

Sin embargo, tanto GMM como K-means asumen implícitamente ejes/dominios de datos procedentes del campo de los números reales $R^n$ . Esto importa en función de lo que amable del eje/dominio de datos que está intentando agrupar. Los recuentos enteros ordenados se asignan bien a los reales. Los símbolos ordenados, como los colores de un espectro, no tanto. Símbolos binarios. Los símbolos desordenados no se asignan a los reales en absoluto (a menos que esté utilizando nuevas matemáticas creativas desde el año 2000).

Así, su imagen binaria de 8x8 se interpretará como un hipercubo de 64 dimensiones en el primer hipercuadrante. A continuación, los algoritmos utilizan analogías geométricas para encontrar clusters. La distancia, con K-means, aparece como distancia euclidiana en un espacio de 64 dimensiones. Es una forma de hacerlo.