¿Por qué el algoritmo de agrupamiento k-means utiliza solo métrica de distancia euclidiana?

¿Hay un propósito específico en términos de eficiencia o funcionalidad por qué el algoritmo k-means no usa, por ejemplo, coseno (des) similitud como una métrica de distancia, sino que solo puede usar la norma euclidiana? En general, ¿cumplirá y será correcto el método K-means cuando se consideren o usen otras distancias además de Euclidiana?

[Adición por @ttnphns. La pregunta es doble. La "distancia (no) euclidiana" puede referirse a la distancia entre dos puntos de datos o la distancia entre un punto de datos y un centro de agrupación. Ambas formas se han intentado abordar en las respuestas hasta ahora.]

El procedimiento K-Means, que es un método de cuantificación vectorial que a menudo se usa como método de agrupamiento, no utiliza explícitamente distancias de pares en puntos de datos en blanco y negro (en contraste con los agrupamientos jerárquicos y algunos otros que permiten una medida de proximidad arbitraria). Equivale a asignar puntos repetidamente al centroide más cercano, utilizando así la distancia euclidiana desde los puntos de datos a un centroide . Sin embargo, K-Means se basa implícitamente en distancias euclidianas por pares en puntos de datos b / n, porque la suma de las desviaciones al cuadrado del centroide es igual a la suma de las distancias euclidianas al cuadrado divididas por el número de puntos. El término "centroide" es en sí mismo de la geometría euclidiana. Es una media multivariada en el espacio euclidiano. El espacio euclídeo se trata de distancias euclidianas. Las distancias no euclidianas generalmente no abarcarán el espacio euclidiano. Es por eso que K-Means es solo para distancias euclidianas.

Pero una distancia euclidiana b / w dos puntos de datos se puede representar de varias maneras alternativas . Por ejemplo, está estrechamente relacionado con coseno o producto escalar b / w los puntos. Si tiene coseno, covarianza o correlación, siempre puede (1) transformarlo en distancia euclidiana (al cuadrado) y luego (2) crear datos para esa matriz de distancias euclidianas (por medio de coordenadas principales u otras formas de métrica Escalamiento multidimensional) para (3) ingresar esos datos en la agrupación de K-Means. Por lo tanto, es posible hacer que K-Means "trabaje" con cosenos pareados o similares; de hecho, tales implementaciones de agrupación de K-Means existen. Ver también sobre la implementación de "K-medias para la matriz de distancia".

Es posible programar K-medias de una manera que calcule directamente en la matriz cuadrada de distancias euclidianas por pares, por supuesto. Pero funcionará lentamente, por lo que la forma más eficiente es crear datos para esa matriz de distancia (convertir las distancias en productos escalares, etc., el pase que se describe en el párrafo anterior) y luego aplicar el procedimiento estándar de K-medias a ese conjunto de datos.

Tenga en cuenta que estaba discutiendo el tema sobre si la disimilitud euclidiana o nouclidiana entre los puntos de datos es compatible con K-means. Está relacionado, pero no es exactamente la misma pregunta, si las desviaciones nouclidianas del centroide (en sentido amplio, centro o cuasicentroide) pueden incorporarse en K-means o "K-means" modificados.

Vea la pregunta relacionada K-significa: ¿Por qué minimizar WCSS es maximizar la distancia entre grupos? .

Vea también la respuesta @ttnphns para una interpretación de k-means que en realidad involucra distancias euclidianas puntiagudas.

La forma en que se construye k-means no se basa en distancias .

K-means minimiza la varianza dentro del grupo. Ahora, si nos fijamos en la definición de varianza, es idéntica a la suma de las distancias al cuadrado euclidianas desde el centro. (¡La respuesta de @ttnphns se refiere a distancias euclidianas por pares!)

La idea básica de k-means es minimizar los errores al cuadrado . No hay "distancia" involucrada aquí.

Por qué no es correcto usar distancias arbitrarias: porque k-means puede dejar de converger con otras funciones de distancia . La prueba común de convergencia es así: el paso de asignación y el paso de actualización media optimizan el mismo criterio. Hay un número finito de tareas posibles. Por lo tanto, debe converger después de un número finito de mejoras. Para usar esta prueba para otras funciones de distancia, debe demostrar que la media (nota: k- medias ) también minimiza sus distancias.

Si está buscando una variante de k-medias en la distancia de Manhattan, hay k-medianas. Porque la mediana es un mejor estimador de L1 conocido.

Si desea funciones de distancia arbitrarias, eche un vistazo a k-medoids (también conocido como: PAM, particionamiento alrededor de medoids). El medoide minimiza las distancias arbitrarias (porque se define como el mínimo), y también solo existe un número finito de medoides posibles. Sin embargo, es mucho más caro que la media.

Podría ser un poco pedante aquí, pero K-means es el nombre dado a un algoritmo particular que asigna etiquetas a los puntos de datos de modo que dentro de las variaciones del clúster se minimizan, y no es el nombre de una "técnica general".

El algoritmo K-means se ha propuesto independientemente de varios campos, con fuertes interpretaciones aplicables al campo. Resulta, muy bien, que también es una distancia euclidiana al centro. Para una breve historia de K-means, lea Agrupación de datos: 50 años más allá de K-means

Hay una gran cantidad de otros algoritmos de agrupación que utilizan métricas distintas de Euclidean. El caso más general que conozco es el de usar Bregman Divergences para la agrupación, de los cuales Euclidiana es un caso especial.

Dado que aparentemente esta es ahora una pregunta canónica, y aún no se ha mencionado aquí:

Una extensión natural de k-means para usar métricas de distancia que no sean la distancia euclidiana estándar en es usar el truco del kernel . Esto se refiere a la idea de mapear implícitamente las entradas a un espacio de Hilbert dimensional alto o infinito, donde las distancias corresponden a la función de distancia que queremos usar, y ejecutar el algoritmo allí. Es decir, dejar que sea ​​un mapa de características tal que la métrica deseada pueda escribirse , ejecutamos k-means en los puntos . En muchos casos, no podemos calcular el mapa explícitamente, pero que puedo$\mathbb R^d$$\varphi : \mathbb R^p \to \mathcal H$$d$$d(x, y) = \lVert \varphi(x) - \varphi(y) \rVert_{\mathcal H}$$\{ \varphi(x_i) \}$$\varphi$calcule el núcleo . No todas las métricas de distancia se ajustan a este modelo, pero muchas lo hacen, y hay funciones definidas en cadenas, gráficos, imágenes, distribuciones de probabilidad y más ...$k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{\mathcal H}$

En esta situación, en el algoritmo de k-medias estándar (Lloyd's), podemos asignar fácilmente puntos a sus grupos, pero representamos los centros de los grupos de forma implícita (como combinaciones lineales de los puntos de entrada en el espacio de Hilbert). Encontrar la mejor representación en el espacio de entrada requeriría encontrar una media de Fréchet , que es bastante costosa. Por lo tanto, es fácil obtener asignaciones de clúster con un núcleo, más difícil obtener los medios.

El siguiente artículo analiza este algoritmo y lo relaciona con la agrupación espectral:

I. Dhillon, Y. Guan y B. Kulis. Kernel k-means, agrupación espectral y cortes normalizados. KDD 2005.

He leído muchos comentarios interesantes aquí, pero permítanme agregar que la implementación "personal" de Matlab de k-means admite 4 distancias no euclidianas [entre puntos de datos y centros de agrupación]. El único comentario de la documentación que puedo ver al respecto es:

Medida de distancia, en espacio p-dimensional, utilizada para minimización, especificada como el par separado por comas que consiste en 'Distancia' y una cadena.

kmeans calcula los grupos de centroides de manera diferente para las diferentes medidas de distancia admitidas. Esta tabla resume las medidas de distancia disponibles. En las fórmulas, x es una observación (es decir, una fila de X) yc es un centroide (un vector de fila).

Luego una lista de funciones de cy xsigue. Por lo tanto, teniendo en cuenta que esa pes la dimensionalidad de los datos de entrada, parece que no se realiza ninguna incrustación euclidiana de antemano.

Por cierto, en el pasado he estado usando los medios k de Matlab con la distancia de correlación y (como era de esperar) hizo lo que se suponía que debía hacer.

Desde aquí :

Consideremos dos documentos A y B representados por los vectores en la figura anterior. El coseno trata ambos vectores como vectores unitarios normalizándolos, dándole una medida del ángulo entre los dos vectores. Proporciona una medida precisa de similitud pero sin tener en cuenta la magnitud. Pero la magnitud es un factor importante al considerar la similitud.