Si la agrupación k-means es una forma de modelado de mezcla gaussiana, ¿se puede usar cuando los datos no son normales?

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

En este libro dice que k-means es una versión difícil 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). Por ejemplo, ¿qué pasa si los datos son imágenes de dígitos escritos a mano, que consisten en 8 * 8 píxeles cada uno con valor 0 o 1 (y suponiendo que son independientes, por lo tanto, debería ser una mezcla de Bernoulli)?

Estoy un poco confundido con esto y agradeceré cualquier pensamiento.

clustering data-mining k-means gaussian-mixture eddie.xie
fuente

Si está preguntando si es válido realizar la agrupación de k-medias en datos no normales, la respuesta es sí si se supone que los datos son continuos. Los datos binarios no son continuos. Algunas personas hacen k-means en tales datos, lo que es heurísticamente permisible, pero teóricamente inválido.

ttnphns

No hay un modelo de probabilidad para k-means, por lo que no hay un supuesto de normalidad para invalidar. (no significa que vaya a funcionar bien sin embargo)

conjeturas

@conjeturas Hmm ... Pero k-menas es equivalente a GMM, y GMM supone normal.

eddie.xie

@ttnphns Gracias por tu respuesta! Entonces, supongo que si uso TF-IDF para transferir texto a puntajes y hacerlo continuo, ¿puedo aplicar y es válido?

eddie.xie

De repente me doy cuenta de que GMM es una mezcla (suma de) unos pocos gaussianos y debería ser capaz de expresar cualquier distribución dada suficientes mezclas. Por lo tanto, incluso GMM y K-means son equivalentes no significa que K-means no pueda usar datos no normales porque GMM puede expresar cualquier distribución. ¿Es eso correcto?

eddie.xie

Respuestas:

En situaciones típicas de EM GMM, uno tiene 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 de Lloyd, es esencialmente un algoritmo EM, que utiliza un modelo de centroide (sin varianza) y asignaciones difíciles.

Al hacer clustering de estilo k-means (es decir, minimización de varianza), usted

casualmente minimice la distancia euclidiana al cuadrado, porque la contribución de la variación WCSS (suma de cuadrados dentro del grupo) = distancia euclidiana al cuadrado
casualmente asigne objetos al grupo más cercano por distancia euclidiana, porque la función sqrt es monótona (tenga en cuenta que la media no optimiza las distancias euclidianas, sino la función WCSS)
representar grupos utilizando solo un centroide
obtener racimos en forma de células Voronoi, es decir, polígonos
funciona mejor con grupos esféricos

{argmin}_{S} \sum_{yo = 1}^{k} \sum_{X_{j} \in S_{yo}} \sum_{re = 1}^{re} {(X_{j re} - μ_{yo re})}^{2}

$\text{argmin}_S \sum_{i=1}^{k} \sum_{x_j \in S_i} \sum_{d=1}^{D} \left(x_{jd} - \mu_{id} \right)^2$

S = {S_{1} \dots S_{k}}

$S=\{S_1 \ldots S_k\}$

k

$k$

D

$D$

x_{j d}

$x_{jd}$

j

$j$

d

$d$

Se dice comúnmente que k-means asume grupos esféricos. También se reconoce comúnmente que los grupos k-means son células Voronoi, es decir, no esféricas. Ambos son correctos y ambos están equivocados. En primer lugar, los grupos no son células Voronoi completas, sino solo los objetos conocidos en ellas. No es necesario considerar que el espacio muerto entre los grupos sea parte de cualquiera de los grupos, ya que tener un objeto allí afectaría el resultado del algoritmo. Pero tampoco es mucho mejor llamarlo "esférico", solo porque la distancia euclidiana es esférica. A K-means no le importa la distancia euclidiana. Todo lo que es, es una heurística para minimizar las variaciones . Y eso es, en realidad, lo que debe considerar k-significa: minimización de varianza.

Anony-Mousse -Reinstate a Monica
fuente

Permítame sugerirle que refine un poco algunas de sus expresiones, para mayor precisión. Por ejemplo, ¿qué es minimize squared euclidean distanceo minimize the variances? Debe haber palabras "suma de" o "agrupadas" o algo así, porque tenemos más de 2 grupos, ¿no?

ttnphns

Por cierto, dado que k-means minimiza la suma agrupada dentro del grupo de d ^ 2 dividida por el número de objetos en el grupo respectivo, su punto coincidentally minimize Euclidean distance, because the sqrt function is monotonees, para ser precisos, no correcto.

ttnphns

La función objetivo adecuada, para la cual puede probar la convergencia, es WCSS, suma de cuadrados dentro del clúster . Y, de hecho, no minimiza las distancias euclidianas, pero la distancia centroide-por-euclidiana más cercana es también la asignación óptima de WCSS.

Anony-Mousse -Reinstalar Monica

Su redacción sigue siendo lamentablemente dudosa . ¿Qué frase minimize squared Euclidean distance, because WCSS variance contribution = squared euclidean distance significa ? ¿Está diciendo que "las d cuadradas entre los objetos en los grupos se minimizan porque el WCSS de las desviaciones se minimiza", o simplemente "el WCSS de las desviaciones se minimiza, que, las desviaciones, son distancias euclidianas por naturaleza"? ¿O algo más?

ttnphns

Obviamente, k-means es una buena opción solo si desea un modelo centroide de sus datos. Si desea optimizar distancias por pares, use la agrupación jerárquica.

Anony-Mousse -Reinstalar Monica

GMM utiliza colinas superpuestas que se extienden hasta el infinito (pero prácticamente solo cuentan para 3 sigma). Cada punto obtiene los puntajes de probabilidad de todas las colinas. Además, las colinas tienen "forma de huevo" [bueno, son elipses simétricas ] y, usando la matriz de covarianza completa, pueden inclinarse .

K-significa asigna un punto a un solo grupo, por lo que las puntuaciones de los otros centros de grupo se ignoran (se restablecen implícitamente a cero / no me importa). Las colinas son pompas de jabón esféricas. Cuando dos burbujas de jabón se tocan, el límite entre ellas se convierte en un plano (hiper) plano. Al igual que cuando se sopla una espuma de muchas pompas de jabón, las burbujas en el interior no son planas, sino cuadradas, por lo que los límites entre muchas (hiper) esferas en realidad forman una partición Voronoi del espacio. En 2D, esto tiende a parecerse vagamente al empaquetamiento hexagonal cerrado, piense en una colmena de abejas (aunque, por supuesto, no se garantiza que las células Voronoi sean hexágonos). Una colina K significa que es redonda y no se inclina, por lo que tiene menos poder de representación; pero es mucho más rápido de calcular, especialmente en las dimensiones superiores.

Debido a que K-means utiliza la métrica de distancia euclidiana, supone que las dimensiones son comparables y de igual peso. Entonces, si la dimensión X tiene unidades de millas por hora, que varía de 0 a 80, y la dimensión Y tiene unidades de libras, que varían de 0 a 400, y está ajustando círculos en este espacio XY, entonces una dimensión (y su extensión) será más poderoso que la otra dimensión y eclipsará los resultados. Es por eso que se acostumbra normalizar los datos al tomar K-means.

Tanto GMM como K-means modelan los datos ajustando las mejores aproximaciones a lo que se proporciona. GMM se adapta a los huevos inclinados, y K-means se adapta a las esferas hasta. Pero los datos subyacentes podrían tener la forma de cualquier cosa, podría ser una espiral o una pintura de Picasso, y cada algoritmo aún se ejecutaría y tomaría su mejor tiro. Si el modelo resultante se parece a los datos reales depende del proceso físico subyacente que genera los datos. (Por ejemplo, las mediciones de retardo de tiempo son unilaterales; ¿es un Gaussiano un buen ajuste? Quizás).

$R^n$

Por lo tanto, su imagen binaria de 8x8 se interpretará como un hipercubo de 64 dimensiones en el primer hiperquadrante. Los algoritmos luego usan analogías geométricas para encontrar grupos. La distancia, con K-medias, aparece como distancia euclidiana en un espacio de 64 dimensiones. Es una forma de hacerlo.

Señor de los Dragones
fuente

Tenga en cuenta que ambos algoritmos también suponen implícitamente que los ejes espaciales son igualmente densos en todos los puntos, por lo que el ajuste de datos que varían exponencialmente, logarítmicamente o sinusoidalmente generalmente se beneficia de una pretransformación para reasignar los datos en un dominio que varía aproximadamente linealmente.

DragonLord