Realice agrupaciones K-means (o similares) sólo con una matriz de distancias, no con datos de puntos por características.

Question

Quiero realizar un clustering K-means sobre objetos que tengo, pero los objetos no están descritos como puntos en el espacio, es decir, por objects x features conjunto de datos. Sin embargo, soy capaz de calcular la distancia entre dos objetos cualesquiera (se basa en una función de similitud). Así pues, dispongo de la matriz de distancias objects x objects .

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

Answer 1

Obviamente, k-means tiene que ser capaz de calcular significa .

Sin embargo, existe una variante muy conocida conocida como k-medoids o PAM (Particionamiento en torno a medoides), donde el medoide es el existente objeto más central de la agrupación. K-medoids sólo necesita las distancias entre pares.

Answer 2

Usted está describiendo exactamente la configuración del problema de kernel $k$ -medias; cuando no se puede representar un punto de datos como un vector euclidiano, pero si aún se puede calcular (o definir) el producto interior entre dos puntos de datos, entonces se puede kernelize el algoritmo. La siguiente página web ofrece una breve descripción del algoritmo:

Núcleo $k$ -página de medios

Este truco del núcleo es una idea muy popular y fundamental en Estadística y aprendizaje automático.

Página Wiki sobre el truco del núcleo

Si le interesa, el libro Aprender con núcleos de Bernhard Schölkopf y Alexander J. Smola será una muy buena introducción.

Esta nota de Max Welling parece muy agradable; además, si utiliza R puede echar un vistazo a este paquete R .

MDS puede ser una forma de resolver su problema, pero no ataca directamente el problema que quiere resolver; mientras que kernel k-means sí lo hace.

Answer 3

@gung tiene toda la razón al sugerirle el escalado multidimensional (MDS) como un herramienta preliminar para crear points X dimensions datos de la matriz de distancias. Voy a añadir sólo unas pinceladas. Agrupación K-means implica distancias euclidianas . El MDS le proporcionará coordenadas de puntos en dimensiones, garantizándole así distancias euclidianas. Debe utilizar el MDS métrico y solicitar un número de dimensiones lo más grande posible, ya que su objetivo es minimizar el error de reconstracción de los datos, no mapearlos en 2D o 3D.

¿Y si no tiene a mano el software MDS pero dispone de algunas funciones matriciales como la descomposición de valores propios o la descomposición de valores singulares? Entonces podría haga usted mismo un simple MDS métrico - MDS de Torgerson, también conocido como análisis de coordenadas principales (PCoA). Se trata de un análisis de componentes principales un poco "retorcido". No voy a describirlo aquí, aunque es bastante sencillo. Puede leer sobre él en muchos sitios, por ejemplo aquí .

Por último, es posible programa "K-means para entrada de matriz de distancia" directamente - sin llamar o escribir funciones que hagan PCoA u otra métrica MDS. Sabemos que (a) la suma de las desviaciones al cuadrado del centroide es igual al suma de las distancias euclidianas al cuadrado por pares dividida por el número de puntos; y (b) saber calcular las distancias entre los centroides de los clusters de la matriz de distancias (c) y además sabemos cómo Sumas de cuadrados están interrelacionados en K-means. Todo ello junto hace que la escritura del algoritmo deseado sea una tarea sencilla y no compleja. Uno debe recordar, sin embargo, que K-means es sólo para distancias euclidianas / espacio euclidiano. Utilice K-medoids u otros métodos para distancias no euclidianas.

Una pregunta similar .

Answer 4

Desde luego, no sé cómo se hace "normalmente", y que conste que no sé mucho de análisis de conglomerados. Sin embargo, ¿está familiarizado con Escala multidimensional ? ( Aquí está otra referencia, la wiki y puede buscar CV en escala multidimensional etiqueta). El escalado multidimensional toma una matriz de distancias entre pares, lo que se parece a su situación. A partir del MDS, puede obtener las ubicaciones de los objetos en el espacio de menor dimensión necesario para representarlos adecuadamente. Supongo que podría utilizar esas ubicaciones para realizar un análisis de conglomerados posterior, como k-means; alternativamente, una vez obtenido el resultado, es posible que ya no necesite el AC.

No sé si usas R, pero aquí es la vista de tareas para Psicometría, que incluye una sección sobre MDS en R. Espero que le sirva de ayuda.

Answer 5

Incrustación óptima de datos de proximidad no métricos para preservar los conglomerados debería ajustarse a su caso. El artículo muestra cómo se puede obtener una representación vectorial métrica de los objetos dada sólo una matriz de función de disimilitud por pares, de forma que las asignaciones de clúster se mantengan para una serie de algoritmos de clustering, incluyendo $k$ -significa.

En tu caso, lo que básicamente tienes que hacer es:

1. Tenga su matriz de desemejanza $D$ con autodisimilitud cero.
2. En caso de que no sea simétrica, simetrícela calculando la media. $D_{ij}$ y $D_{ji}$ .
3. centrarla (es decir, restar la media de filas y columnas) para obtener $D^c$
4. Calcule $S^c = -\frac{1}{2}D^c$
5. Realiza un desplazamiento espectral: Restar el $S^c$ del valor propio más pequeño de $S^c$ para asegurar que se convierte en semidefinido positivo. De este modo se obtiene $\tilde S^c$ .
6. Calcular la descomposición de los vectores propios de $\tilde S^c = V \Lambda V^\top$ .
7. Restaurar una representación vectorial en un $n-1$ -espacio métrico dimensional de sus datos: $X = V\Lambda^{1/2}$ .

Esto supone que $n$ no es demasiado grande. Si lo es, un ACP adicional le proporcionará una representación más significativa de los datos. (En el documento también se describe cómo hacerlo).