Diferencia entre los algoritmos k-means estándar y esférico

Question

Me gustaría entender cuál es la principal diferencia de implementación entre los algoritmos de clustering k-means estándar y esférico.

En cada paso, k-means calcula las distancias entre los vectores de los elementos y los centroides de los clusters, y reasigna el documento a este cluster, cuyo centroide es el más cercano. A continuación, se vuelven a calcular todos los centroides.

En k-means esférico, todos los vectores están normalizados y la medida de distancia es la disimilitud del coseno.

¿Es eso todo, o hay algo más?

Answer 1

La pregunta es:

¿Cuál es la diferencia entre el k-means clásico y el k-means esférico?

K-means clásico:

En el k-means clásico, se busca minimizar la distancia euclidiana entre el centro del cluster y los miembros del mismo. La intuición detrás de esto es que la distancia radial desde el centro del clúster a la ubicación del elemento debe "tener la misma" o "ser similar" para todos los elementos de ese clúster.

El algoritmo es:

• Establecer el número de clusters (también conocido como recuento de clusters)
• Inicializar asignando aleatoriamente los puntos del espacio a los índices de los clústeres
• Repita la operación hasta que converja
  • Para cada punto, encontrar el clúster más cercano y asignar el punto al clúster
  • Para cada clúster, hallar la media de los puntos miembros y actualizar la media central
  • El error es la norma de la distancia de los clusters

K-means esférico:

En el k-means esférico, la idea es fijar el centro de cada cluster de forma que haga uniforme y mínimo el ángulo entre componentes. La intuición es como mirar las estrellas: los puntos deben tener un espaciamiento consistente entre sí. Ese espaciamiento es más sencillo de cuantificar como "similitud del coseno", pero significa que no hay galaxias de la "vía láctea" que formen grandes franjas brillantes en el cielo de los datos. (Sí, estoy intentando hablar con la abuela en esta parte de la descripción).

Una versión más técnica:

Piensa en los vectores, las cosas que se grafican como flechas con orientación y longitud fija. Se puede trasladar a cualquier lugar y ser el mismo vector. ref

La orientación del punto en el espacio (su ángulo con respecto a una línea de referencia) puede calcularse utilizando el álgebra lineal, en particular el producto punto.

Si movemos todos los datos para que su cola esté en el mismo punto, podemos comparar los "vectores" por su ángulo, y agrupar los similares en un solo clúster.

Para mayor claridad, las longitudes de los vectores están escaladas, para que sea más fácil compararlas "a ojo".

Se podría pensar en ello como una constelación. Las estrellas de un mismo cúmulo están cerca unas de otras en algún sentido. Estas son las constelaciones que yo considero a ojo.

El valor del enfoque general es que nos permite crear vectores que de otro modo no tendrían dimensión geométrica, como en el método tf-idf, donde los vectores son frecuencias de palabras en los documentos. Dos palabras "y" sumadas no equivalen a un "el". Las palabras no son continuas ni numéricas. No son físicas en un sentido geométrico, pero podemos concebirlas geométricamente, y luego utilizar métodos geométricos para manejarlas. Se puede utilizar el método k-means esférico para agrupar las palabras.

Así que los datos (2d aleatorios, continuos) eran estos: $$\begin{bmatrix} x1&y1&x2&y2&group\\ 0&-0.8&-0.2013&-0.7316&B\\ -0.8&0.1&-0.9524&0.3639&A\\ 0.2&0.3&0.2061&-0.1434&C\\ 0.8&0.1&0.4787&0.153&B\\ -0.7&0.2&-0.7276&0.3825&A\\ 0.9&0.9&0.748&0.6793&C\\ \end{bmatrix}$$

Algunos puntos:

• Se proyectan a una esfera unitaria para tener en cuenta las diferencias en el documento longitud de los documentos.

Vamos a trabajar a través de un proceso real, y ver cómo (mal) mi "eyeballing" era.

El procedimiento es:

1. (implícito en el problema) conectan las colas de los vectores en el origen
2. proyectar en la esfera de la unidad (para tener en cuenta las diferencias en la longitud del documento)
3. utilizar la agrupación para minimizar " disimilitud del coseno "

$$J = \sum_{i} d \left( x_{i},p_{c\left( i \right)} \right)$$ donde
$$d \left( x,p \right) = 1- cos \left(x,p\right) = \frac{\langle x,p \rangle}{\left \|x \right \|\left \|p \right \|}$$

(más ediciones en breve)

Enlaces:

1. http://epub.wu.ac.at/4000/1/paper.pdf
2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.8125&rep=rep1&type=pdf
3. http://www.cs.gsu.edu/~wkim/index_files/papers/refinehd.pdf
4. https://www.jstatsoft.org/article/view/v050i10
5. http://www.mathworks.com/matlabcentral/fileexchange/32987-the-spherical-k-means-algorithm
6. https://ocw.mit.edu/courses/sloan-school-of-management/15-097-prediction-machine-learning-and-statistics-spring-2012/projects/MIT15_097S12_proj1.pdf