Clustering con una matrice di distanze

Question

Ho una matrice (simmetrica) M che rappresenta la distanza tra ciascuna coppia di nodi. Ad esempio,

 
    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 

Esiste un metodo per estrarre cluster da M (se necessario, il numero di cluster può essere fissato), in modo tale che ogni cluster contiene nodi con piccole distanze tra loro. Nell'esempio, i cluster sarebbero (A, B, C, D), (E, F, G, H) e (I, J, K, L).

Grazie mille :)

Answer 1

Hierarchical clustering lavora direttamente con la matrice di distanza invece delle osservazioni reali. Se conosci il numero di cluster, conoscerai già il tuo criterio di arresto (fermati quando ci sono k cluster). Il trucco principale qui sarà scegliere uno linkage method appropriato. Inoltre, this paper (pdf) offre un'eccellente panoramica di tutti i tipi di metodi di clustering.

Answer 2

Un altro modo possibile è utilizzare Partitioning Around Medoids che spesso viene chiamato K-Medoids. Se si guarda il pacchetto di R-clustering vedrete la funzione pam che riceve la matrice di distanza come dati di input.

Answer 3

Bene, è possibile eseguire il cluster K-medie su una matrice di similarità data, in un primo momento è necessario centrare la matrice e quindi prendere gli autovalori della matrice. Il passo finale e più importante è moltiplicare i primi due set di autovettori alla radice quadrata delle diagonali degli autovalori per ottenere i vettori e quindi proseguire con K-means. Sotto il codice mostra come farlo. Puoi cambiare la matrice di similarità. fpdist è la matrice di similarità.

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)