Usar k-means con otras métricas

Así que me doy cuenta de que esto se ha preguntado antes: por ejemplo, ¿cuáles son los casos de uso relacionados con el análisis de conglomerados de diferentes métricas de distancia? pero he encontrado que las respuestas son algo contradictorias con lo que se sugiere que debería ser posible en la literatura.

Recientemente, he leído dos documentos que mencionan el uso del algoritmo kmeans con otras métricas, por ejemplo, editar la distancia entre cadenas y la "Distancia del desplazador de la tierra" entre distribuciones. Dado que estos documentos mencionan el uso de kmeans con otras métricas sin especificar cómo , particularmente cuando se trata de calcular la media del conjunto de puntos, me sugiere que tal vez exista algún método "estándar" para tratar esto que simplemente no estoy eligiendo sobre.

Tomemos por ejemplo este documento , que brinda una implementación más rápida del algoritmo k-means. Citando el párrafo 4 en la introducción, el autor dice que su algoritmo "se puede usar con cualquier métrica de distancia de recuadro negro", y en el siguiente párrafo menciona la distancia de edición como un ejemplo específico. Sin embargo, su algoritmo todavía calcula la media de un conjunto de puntos y no menciona cómo esto podría afectar los resultados con otras métricas (estoy especialmente perplejo en cuanto a cómo la media funcionaría con la distancia de edición).

Este otro artículo describe el uso de k-means para agrupar las manos de póker para una abstracción hold-em de texas. Si salta a la página 2 en la parte inferior de la columna de la izquierda, la escritura del autor "y luego k-means se usa para calcular una abstracción con el número deseado de grupos utilizando la Distancia de movimiento de la Tierra entre cada par de histogramas como la métrica de distancia".

Realmente no estoy buscando a alguien que me explique estos documentos, pero ¿me estoy perdiendo algún método estándar para usar k-means con otras métricas? Parece que el promedio estándar con la distancia de movimiento de tierra podría funcionar de forma heurística, pero la distancia de edición parece no encajar en absoluto en el molde. Agradezco cualquier idea que alguien pueda dar.

(editar) : Seguí adelante y probé k-means en histogramas de distribución usando la distancia de movimiento de tierra (similar a lo que está en el papel de póker) y parecía haber funcionado bien, los grupos que producía se veían bastante bien para mi caso de uso. Para promediar, simplemente traté los histogramas como vectores y promedié de la manera normal. Lo único que noté es que la suma sobre todos los puntos de las distancias a los medios no siempre disminuía de manera monótona. Sin embargo, en la práctica, se resolvería en un mínimo local en 10 iteraciones a pesar de los problemas monótonos. Voy a suponer que esto es lo que hicieron en el segundo artículo, la única pregunta que queda entonces es, ¿cómo diablos promediarías al usar algo como la distancia de edición?

No es que k-means necesariamente explote y falle si usa una métrica diferente.

En muchos casos devolverá algún resultado . Simplemente no se garantiza que encuentre los centroides o particiones óptimos con otras métricas, porque la media puede no ser adecuada para minimizar las distancias.

Considere la distancia de los motores de la Tierra. Dados los tres vectores

3 0 0 0 0
0 0 3 0 0
0 0 0 0 3

La media aritmética es

1 0 1 0 1

que tiene distancias EMD 6, 4, 6 (total 16). Si el algoritmo hubiera usado en su lugar

0 0 3 0 0

las distancias EMD habrían sido 6, 0, 6; es decir, mejor (total 12).

La media aritmética no minimiza la DME, y el resultado del uso de k-medias (con media artihmetic) no dará representantes óptimos.

Cosas similares se mantendrán para editar distancias.

El uso de K-means es apropiado en combinación con la distancia euclidiana porque el objetivo principal de k-means es minimizar la suma de las variaciones dentro del cluster , y la varianza dentro del cluster se calcula exactamente de la misma manera que la suma de Euclidean distancias entre todos los puntos en el grupo al centroide del grupo. Como señalan otras respuestas , se garantiza que el algoritmo solo convergerá (incluso si se trata de un mínimo local) si tanto el paso de actualización del centroide como el paso de reasignación de puntos de datos se realizan en el mismo espacio euclidiano n-dimensional .

Además, se ha demostrado (y pongo un enlace aquí porque yo mismo no puedo explicar esto) que la media es el mejor estimador que se utiliza cuando se necesita minimizar la varianza total . Por lo tanto, el enlace k-means con la distancia euclidiana es doble: el algoritmo debe tener alguna forma de calcular la media de un conjunto de puntos de datos (de ahí el nombre k- means ), pero este significado solo tiene sentido y garantiza la convergencia de proceso de agrupamiento si la distancia euclidiana se usa para reasignar puntos de datos a los centroides más cercanos.

Todavía puede usar k-means con otras medidas de distancia, como en este artículo , en el que el autor usa el algoritmo con la distancia de Minkowski, que es una generalización de las distancias de Manhattan, Euclidiana y Chebyshev. Sin embargo, en estos casos, la convergencia no está garantizada y, como consecuencia, es de esperar que las futuras iteraciones del algoritmo realmente tengan una mayor varianza total que las iteraciones anteriores.

Aun así, como se muestra en el documento anterior, incluso sin la garantía de convergencia, k-means puede lograr mejores resultados de agrupamiento en algunos escenarios mediante el uso de otras medidas de distancia. Si toma las normas , por ejemplo, y sabiendo que la distancia euclidiana es la norma y que la distancia de Manhattan es la norma , se ha demostrado que, para matrices de distancias dispersas, k-significa usado junto con una norma con logra una mayor precisión de agrupamiento que cuando se usa la distancia euclidiana.$L^p$$L^2$$L^1$$L^p$$0 < p \leq 1$

Por último, creo que es interesante señalar que hay algunas medidas de similitud que de alguna manera se pueden convertir a la distancia euclidiana, de tal manera que si usa dicha medida de similitud junto con k-means, debería obtener resultados similares Un ejemplo de eso es la similitud del coseno .

No sé si esto es lo que están haciendo los documentos vinculados, pero es posible hacer k-means con funciones de distancia no euclidianas utilizando el truco del kernel . Es decir, asignamos implícitamente las entradas a un espacio de alta dimensión (a menudo de dimensión infinita) donde las distancias euclidianas corresponden a la función de distancia que queremos usar, y ejecutamos el algoritmo allí. Para el algoritmo k-means de Lloyd en particular, podemos asignar puntos a sus grupos fácilmente, pero representamos los centros de los grupos implícitamente y encontrar su representación en el espacio de entrada requeriría encontrar una media de Fréchet . El siguiente artículo analiza el 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.

Hay núcleos basados ​​en la distancia de edición y en la distancia del movimiento de tierra .