Agrupamiento con una matriz de distancia

Question

Tengo una matriz (simétrica) M que representa la distancia entre cada par de nodos. Por ejemplo,

 
    A B C D E F G H I J K L 
A 0 20 20 20 40 60 60 60 100 120 120 120 
B 20 0 20 20 60 80 80 80 120 140 140 140 
C 20 20 0 20 60 80 80 80 120 140 140 140 
D 20 20 20 0 60 80 80 80 120 140 140 140 
E 40 60 60 60 0 20 20 20 60 80 80 80 
F 60 80 80 80 20 0 20 20 40 60 60 60 
G 60 80 80 80 20 20 0 20 60 80 80 80 
H 60 80 80 80 20 20 20 0 60 80 80 80 
I 100 120 120 120 60 40 60 60 0 20 20 20 
J 120 140 140 140 80 60 80 80 20 0 20 20 
K 120 140 140 140 80 60 80 80 20 20 0 20 
L 120 140 140 140 80 60 80 80 20 20 20 0 

¿Hay algún método para extraer grupos de M (si es necesario, el número de grupos puede ser fijo), de tal manera que cada grupo contiene nodos con pequeñas distancias entre ellos. En el ejemplo, los clústeres serían (A, B, C, D), (E, F, G, H) y (I, J, K, L).

Muchas gracias :)

Answer 1

Hierarchical clustering trabaja directamente con la matriz de distancia en lugar de las observaciones reales. Si conoce la cantidad de clusters, ya sabrá su criterio de detención (detener cuando haya k clusters). El truco principal aquí será elegir un linkage method apropiado. Además, this paper (pdf) ofrece una excelente visión general de todo tipo de métodos de agrupamiento.

Answer 2

Una forma más de hacerlo es usar Partitioning Around Medoids que a menudo se llama K-Medoids. Si nos fijamos en el paquete R-clustering verá pam función que recibe la matriz de distancia como datos de entrada.

Answer 3

Bueno, es posible realizar clusters de K-means en una matriz de similitud dada, al principio se necesita centrar la matriz y luego tomar los valores propios de la matriz. El paso final y más importante es multiplicar los dos primeros conjuntos de autovectores por la raíz cuadrada de las diagonales de los valores propios para obtener los vectores y luego seguir con los K-means. Debajo del código se muestra cómo hacerlo. Puede cambiar la matriz de similitud. fpdist es la matriz de similitud.

mds.tau <- function(H) 
{ 
    n <- nrow(H) 
    P <- diag(n) - 1/n 
    return(-0.5 * P %*% H %*% P) 
    } 
    B<-mds.tau(fpdist) 
    eig <- eigen(B, symmetric = TRUE) 
    v <- eig$values[1:2] 
    #convert negative values to 0. 
v[v < 0] <- 0 
X <- eig$vectors[, 1:2] %*% diag(sqrt(v)) 
library(vegan) 
km <- kmeans(X,centers= 5, iter.max=1000, nstart=10000) . 
#embedding using MDS 
cmd<-cmdscale(fpdist)