Realice clusters de K-means (o sus parientes cercanos) con solo una matriz de distancia, no datos de puntos por características

Quiero realizar la agrupación K-means en los objetos que tengo, pero los objetos no se describen como puntos en el espacio, es decir, por objects x featuresconjunto de datos. Sin embargo, puedo calcular la distancia entre dos objetos (se basa en una función de similitud). Entonces, dispongo de la matriz de distancia objects x objects.

He implementado K-means antes, pero eso fue con la entrada del conjunto de datos de puntos; y con la entrada de matriz de distancia no me queda claro cómo actualizar los clústeres para que sean los "centros" del clúster sin una representación de puntos. ¿Cómo se haría esto normalmente? ¿Hay versiones de K-means o métodos cercanos para eso?

Obviamente, k-means necesita poder calcular medios .

Sin embargo, existe una variación bien conocida de este, conocida como k-medoides o PAM (Particionamiento alrededor de los medoides), donde el medoide es el objeto existente más central para el grupo. K-medoides solo necesita las distancias por pares.

Está describiendo exactamente la configuración del problema de kernel -means; cuando no puede representar un punto de datos como un vector euclidiano, pero si aún puede calcular (o definir) el producto interno entre dos puntos de datos, puede kernelizar el algoritmo. La siguiente página web proporciona una breve descripción del algoritmo:$k$

Kernel significa página$k$

Este truco del kernel es una idea muy popular y fundamental en estadísticas y aprendizaje automático.

Página Wiki sobre el truco del kernel

Si está interesado, el libro Aprendiendo con granos de Bernhard Schölkopf y Alexander J. Smola será una muy buena introducción.

Esta nota de Max Welling parece muy agradable; También, si está utilizando R se puede echar un vistazo a este paquete R .

MDS puede ser una forma de resolver su problema, pero no ataca directamente el problema que desea resolver; mientras que el núcleo k-means sí.

@gung es absolutamente correcto, sugiriendo una escala multidimensional (MDS) como una herramienta preliminar para crear points X dimensions datos fuera de la matriz de distancia. Debo agregar solo algunos trazos. La agrupación de K-medias implica distancias euclidianas . MDS le dará coordenadas de puntos en dimensiones, garantizando así distancias euclidianas. Debe usar MDS métrico y solicitar un número de dimensiones lo más grande posible, porque su objetivo es minimizar el error de retracción de los datos, no mapearlos en 2D o 3D.

¿Qué sucede si no tiene un software MDS a mano pero tiene algunas funciones de matriz como la descomposición de valores propios o la descomposición de valores singulares? Entonces usted mismo podría hacer MDS métrico simple : Torgerson MDS, también conocido como análisis de coordenadas principales (PCoA). Es un análisis un poco "retorcido" de los componentes principales. No lo describiré aquí, aunque es bastante simple. Puede leer sobre esto en muchos lugares, por ejemplo, aquí .

Finalmente, es posible programar "K-means para la entrada de matriz de distancia" directamente , sin llamar o escribir funciones haciendo PCoA u otro MDS métrico. Sabemos que (a) la suma de las desviaciones al cuadrado del centroide es igual a la suma de las distancias euclidianas al cuadrado divididas en pares divididas por el número de puntos; y (b) sepa cómo calcular las distancias entre los centroides del grupo fuera de la matriz de distancia ; (c) y además sabemos cómo las sumas de cuadrados están interrelacionadas en K-medias. Todo junto hace que la escritura del algoritmo que desea sea una tarea sencilla y no compleja. Sin embargo, uno debe recordar que K-medias es solo para distancias euclidianas / espacio euclidiano. Use K-medoides u otros métodos para distancias no euclidianas.

Una pregunta similar .

Ciertamente no sé cómo se hace "normalmente", y para el registro, no sé mucho sobre el análisis de conglomerados. Sin embargo, ¿está familiarizado con el Escalado multidimensional ? ( Esto es otra referencia, la wiki , y que podría buscar CV bajo el escalamiento multidimensional etiqueta.) Escalamiento multidimensional toma en una matriz de distancias por parejas, que suena como su situación. Desde el MDS, puede obtener las ubicaciones de los objetos en el espacio dimensional más bajo necesario para representarlos adecuadamente. Supongo que podría usar esas ubicaciones para hacer un análisis de clúster posterior como k-means; alternativamente, una vez que tuvo la salida, es posible que ya no necesite la CA.

No sé si usa R, pero aquí está la vista de tareas para Psicometría, que incluye una sección sobre MDS en R. Espero que ayude.

$k$

En su caso, lo que básicamente necesita hacer es:

1. $D$
2. $D_{ij}$$D_{ji}$
3. $D^c$
4. $S^c = -\frac{1}{2}D^c$
5. $S^c$$S^c$$\tilde S^c$
6. Calcule la descomposición del vector propio de $\tilde S^c = V \Lambda V^\top$
7. $n-1$$X = V\Lambda^{1/2}$

$n$

Sus datos también se pueden ver como una red, y puede usar uno de los muchos algoritmos de agrupación en red disponibles. Para esto, probablemente deba aplicar un umbral en los pesos de los bordes y transformar las distancias en similitudes. Para empezar, no es la forma "estadística" de hacer las cosas, pero el análisis de conglomerados es un problema poco especificado, y como herramientas de exploración, los algoritmos de agrupación en red funcionan muy bien.

No sé por qué es tan poco común en la literatura, sin embargo, la solución sugerida por @gung y @ttnphns (primero proyectando sus distancias por pares en un espacio euclidiano usando el Análisis de coordenadas principales, por ejemplo a través de este paquete si usa R, y luego hacer K-significa de manera habitual) es simple y no requiere algoritmos especializados. Personalmente lo usé aquí incrustado en un marco de optimización y funcionó bastante bien.

Con respecto a la agrupación y MDS, sugeriría los siguientes recursos:

• Ecología numérica (Pierre Legendre y Louis Legendre): http://www.sciencedirect.com/science/bookseries/01678892/20 o http://tinyurl.com/cgrdfqk (google books) - capítulo sobre 'Ecological semejanza'
• Análisis de conglomerados (Brian S. Everitt, Sabine Landau, Morven Leese, Daniel Stahl): http://tinyurl.com/bld7k8h (google books) - capítulo sobre 'Medición de proximidad'
• Curso 'Bioestadística-II, métodos multivariados' por el profesor Brian C. McCarthy en la Universidad de Ohio: http://www.ohio.edu/plantbio/staff/mccarthy/multivariate/multivariate.htm

Estas referencias también cubren muy bien los temas de similitud y funciones de distancia (medidas de proximidad) para datos binarios y continuos.