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

62

¿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.]

curioso
fuente
Esta pregunta ya se ha hecho unas 10 veces en stackoverflow y este sitio. Por favor, utilice la función de búsqueda.
Anony-Mousse
3
@ Anony-Mousse: Si bien estoy totalmente de acuerdo con usted y levanté varias banderas recientemente sobre SO, encuentro inquietante la falta de cierre duplicado en la mayoría de estas preguntas.
Nikana Reklawyks
44
Esta es la página que aparece primero mientras buscas en Google sobre este tema.
haripkannan

Respuestas:

62

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? .

ttnphns
fuente
¿Puedes citar algunos ejemplos-documentos del enfoque que estás mencionando?
curioso
44
@ Douglas, por favor. Dije que k-means no usa distancias por pares. Está claramente establecido. Utiliza distancias al centroide. Pero eso significa automáticamente que está implícitamente vinculado con la tarea de optimizar distancias por pares dentro de los clústeres.
ttnphns
1
@ttnphns: en la cantidad de caracteres que escribió But a Euclidean distance b/w two data points can be represented in a number of alternative ways. For example, it is closely tied with cosine or scalar product b/w the points. If you have cosine, or covariance, or correlation, you can always (1) transform it to (squared) Euclidean distance, podría haber escrito con la misma facilidad: distance(x,y) = 1 - cosine_sim(x,y)o algo similar e informativo.
stackoverflowuser2010
1
Esto parece una crítica válida y constructiva: es mejor incluir información directamente en su publicación en lugar de confiar en un enlace; y generalmente es mejor ser explícito que vago. (cc @stackoverflowuser)
whuber
3
¿Qué estás conteniendo? ¿Que es mejor en este caso confiar en un enlace, o mejor ser vago, o ambos? ¿Y por qué?
whuber
46

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.

Anony-Mousse
fuente
Pero en el primer paso de k-significa cada punto se coloca en el grupo con la distancia euclidiana más cercana con el centroide del grupo ... Por lo tanto, hay una métrica de distancia
curioso
@AnonyMousse @ttnphns answer refers to pairwise Euclidean distances!En mi respuesta, primero párrafo, que claramente se refieren tanto a un "error SS" (directo) y "pares d ^ 2" (implícitas) interpretaciones.
ttnphns
3
Estoy de acuerdo con tu respuesta. Tenga en cuenta que su cuenta operativa k-means may stop converging with other distance functionses homóloga a mi teoría Non-euclidean distances will generally not span euclidean space.
ttnphns
Muy buena explicación. Nunca pensé en la distancia euclidiana un segundo pensamiento y no me di cuenta de que en realidad estaba minimizando la suma de cuadrados dentro del grupo.
Verena Haunschmid
Todavía no puedo ver por qué la media minimiza las distancias en términos de distancias euclidianas y en términos de coseno, no lo hace como parte de la prueba
curioso el
9

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.

usuario1669710
fuente
"métricas que no sean euclidianas" Podría ser un poco más pedante, pero esas divergencias no son métricas, en general :)
mic
cierto :); Probablemente debería editar la respuesta.
user1669710
8

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 puedoRdφ:RpHdd(x,y)=φ(x)φ(y)H{φ(xi)}φ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)=φ(x),φ(y)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.

Dougal
fuente
No entiendo cómo se puede usar el truco del núcleo con el algoritmo de Lloyd. Me parece que para calcular un centroide (incluso implícitamente en el espacio de Hilbert), ¿vamos a necesitar el mapa explícito φ (x_i)? Para asignar puntos a los clústeres, solo necesitamos el núcleo, pero para recalcular los centroides, no podemos salir con solo el núcleo, ya que el centroide es la media de {φ (x_i)} asignado a ese clúster. ¿Me estoy perdiendo de algo?
user2428107
Tienes razón en que no podemos calcular explícitamente los centroides. Pero podemos representarlos simplemente como , y calcular distancias a un punto como . 1nijCiφ(xj)xφ(x)1nijCiφ(xj)2=k(x,x)+1ni2j,jk(xj,xj)2nijk(x,xj)
Dougal
5

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.

Francesco Napolitano
fuente
2
Como nota, las distancias no euclidianas admitidas son cosine(que es solo la distancia euclidiana en los puntos de entrada normalizados), correlation(euclidiana en las entradas estandarizadas), cityblock( , en cuyo caso se usa la mediana en lugar de la media) y (que es solo para entradas binarias). L1hammingcityblock
Dougal
@Dougal, ¿cómo se acomoda la mediana en el algoritmo? ¿No cambia k- significa a algo básicamente diferente?
ttnphns
1
Tenga en cuenta también que para datos binarios "distancia de hamming" = cityblock = sq. Distancia euclidiana.
ttnphns
1
@ttnphns Sí, definitivamente ya no es k-means, pero tiene exactamente la misma estructura, excepto en lugar de calcular los centroides como si calcules una mediana. Y sí, en las entradas binarias hamming , pero Matlab usa la mediana para ello en lugar de la media. =L22=L1
Dougal
1
@Dougal, tenga en cuenta que el procedimiento matlab vinculado a dice de varias distancias entre un punto de datos y el centro del clúster; que no es lo mismo que los tipos de distancias por pares.
ttnphns
2

Desde aquí :

ingrese la descripción de la imagen 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.

DL Dahly
fuente
Esta es una respuesta general. No explica por qué en k-significa que no hay similitud de coseno. Por ejemplo, en la agrupación jerárquica se está utilizando ampliamente
curioso
3
@DLDahly: a veces la magnitud es importante, a veces es ruido. Depende del campo de investigación y es un problema de estandarización de datos.
ttnphns