¿Por qué el algoritmo de agrupación de k-means sólo utiliza la métrica de la distancia euclidiana?

Question

¿Existe un propósito específico en términos de eficiencia o funcionalidad por el que el algoritmo k-means no utiliza, por ejemplo, la (des)similitud del coseno como métrica de distancia, sino que sólo puede utilizar la norma euclidiana? En general, ¿el método K-means cumplirá y será correcto cuando se consideren o utilicen otras distancias distintas de la euclidiana?

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

Answer 1

Procedimiento K-Means - que es un método de cuantificación vectorial que se utiliza a menudo como método de agrupación - no utiliza explícitamente distancias entre pares de puntos de datos en absoluto (a diferencia de las agrupaciones jerárquicas y algunas otras que permiten una medida de proximidad arbitraria). Se trata de asignar repetidamente los puntos al centroide más cercano, utilizando para ello Euclidiano distancia de los puntos de datos a un centroide . Sin embargo, K-Means se basa implícitamente en en la pareja Euclidiano distancias entre los puntos de datos, porque la suma de las desviaciones al cuadrado del centroide es igual a la suma de las distancias euclidianas al cuadrado por pares dividida por el número de puntos . El término "centroide" procede de la geometría euclidiana. Es la media multivariante en el espacio euclidiano. El espacio euclidiano se refiere a las distancias euclidianas. Las distancias no euclidianas no suelen abarcar el espacio euclidiano. Por eso K-Means es sólo para distancias euclidianas.

Pero una distancia euclidiana entre dos puntos de datos puede ser representado de varias formas alternativas . Por ejemplo, es estrechamente vinculado con el coseno o el producto escalar entre los puntos. Si se tiene coseno, o covarianza, o correlación, se siempre puede (1) transformarla en distancia euclidiana (al cuadrado), y luego (2) crear datos para esa matriz de distancias euclidianas (mediante coordenadas principales u otras formas de escalado multidimensional métrico) para (3) introducir esos datos en la agrupación K-Means. Por lo tanto, es posible para hacer K-Means "trabajar con" cosenos por pares o similares; de hecho, existen tales implementaciones de la agrupación K-Means. Ver también sobre la implementación de "K-means para la matriz de distancia".

Es posible para programar K-means de manera que directamente calcular en la matriz cuadrada de distancias euclidianas por pares, por supuesto. Pero funcionará con lentitud, por lo que la forma más eficiente es crear datos para esa matriz de distancias (convirtiendo las distancias en productos escalares y demás -el paso que se describe en el párrafo anterior-) y luego aplicar el procedimiento estándar de K-means a ese conjunto de datos.

Tengan en cuenta que estaba discutiendo el tema de la disimilitud euclidiana o no euclidiana entre puntos de datos es compatible con K-means. Está relacionado, pero no es exactamente la misma cuestión, con el hecho de si la nouclidiana desviaciones de El centroide (en sentido amplio, centro o cuasicentroide) puede incorporarse a K-means o "K-means" modificado.

Ver pregunta relacionada K-means: ¿Por qué minimizar el WCSS es maximizar la distancia entre clusters? .

Answer 2

Véase también la respuesta de @ttnphns para una interpretación de k-means que realmente implica distancias euclidianas puntuales.

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

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

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

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

Si lo que se busca es una variante de k-means con distancia de Manhattan, existe k-medians. Porque la mediana es un mejor estimador L1 conocido.

Si quieres funciones de distancia arbitrarias, echa un vistazo a los k-medoides (también conocido como PAM, partición alrededor de los medoides). El medoide minimiza las distancias arbitrarias (porque es definido como el mínimo), y además sólo existe un número finito de medoides posibles. Sin embargo, es mucho más caro que la media.

Answer 3

Puede que sea un poco pedante, pero K-means es el nombre dado a un algoritmo concreto que asigna etiquetas a los puntos de datos de forma que se minimicen las varianzas dentro de los clusters, y no es el nombre de una "técnica general".

El algoritmo K-means ha sido propuesto de forma independiente desde varios campos, con fuertes interpretaciones aplicables al campo. Resulta que, amablemente, también es la distancia euclidiana al centro. Para una breve historia de K-means, lea Agrupación de datos: 50 años después de K-means

Hay una plétora de otros algoritmos de clustering que utilizan métricas distintas a la euclidiana. El caso más general que conozco es el de utilizar Divergencias de Bregman para la agrupación, de la que la euclidiana es un caso especial.

Answer 4

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

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

En esta situación, en el algoritmo estándar (de Lloyd) de k-means, podemos asignar fácilmente los puntos a sus clusters, pero representamos los centros de los clusters implícitamente (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 un Fréchet significa que es bastante caro. Así que es fácil conseguir asignaciones de clúster con un núcleo, más difícil de conseguir 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, Spectral Clustering y Normalized Cuts. KDD 2005.

Answer 5

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

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

kmeans calcula los clusters del centroide de forma diferente para las distintas medidas de distancia soportadas. Esta tabla resume las medidas de distancia disponibles. En las fórmulas, x es una observación (es decir, una fila de X) y c es un centroide (un vector de fila).

A continuación, una lista de funciones de c y x se deduce. Así, considerando que p es la dimensionalidad de los datos de entrada, parece que no se realiza una incrustación euclidiana previa.

BTW en el pasado he estado usando k-means de Matlab con la distancia de correlación y (sin sorpresa) hizo lo que se supone que debe hacer.