Agrupamiento con una matriz de distancia: algoritmo, matriz, análisis de conglomerados, distancia

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

A B C D E F G H I J K L UN0 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, la cantidad de clústeres puede ser fija), de modo que cada grupo contenga nodos con distancias pequeñas entre ellos. En el ejemplo, los clusters serían (A, B, C, D), (E, F, G, H) y (I, J, K, L).

Muchas gracias :)

Respuestas

Agrupación jerárquica trabaja directamente con la matriz de distancia en su lugarde 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 apropiado método de vinculación. También, este papel(pdf) ofrece una excelente visión general de todos los tipos de métodos de agrupamiento.

Otra forma más posible es usar Particionando alrededor de Medoids que a menudo se llama K-Medoids. Si miras el paquete R-clustering, verás pam función que recibe la matriz de distancia como datos de entrada.

Bueno, es posible realizar K-meansAl agruparse en una matriz de similitud dada, primero debe 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)