Un moyen efficace pour calculer les distances entre les centroïdes à partir de la matrice de distance

8

Faisons matrice carrée symétrique des carrés des distances euclidiennes entre points et vecteur lengthed indiquant cluster ou appartenance à un groupe ( clusters) des points; un cluster peut consister en un point .Dnnk1

Quel est le moyen le plus efficace ou vraiment efficace (en termes de vitesse) pour calculer les distances entre les centroïdes de cluster ici?

Jusqu'à présent, j'ai toujours fait une analyse des coordonnées principales dans cette situation. PCoA, ou MDS de Torgerson revient à convertir d'abord en la matrice de produits scalaires ("double centrage") puis à effectuer PCA de celui-ci. De cette façon, nous créons des coordonnées pour les points dans l'espace euclidien qu'ils couvrent. Après cela, il est facile de calculer les distances entre les centroïdes de la manière habituelle - comme vous le feriez avec des données. PCoA doit faire la décomposition propre ou SVD du semi-fini positif symétrique , maisDSngrouped points x variablesn x nSnpeut être assez gros. De plus, la tâche n'est pas une réduction de dimensionnalité et nous n'avons pas réellement besoin de ces axes principaux orthogonaux. J'ai donc le sentiment que ces décompositions pourraient être une exagération.

Alors, avez-vous des connaissances ou des idées sur un moyen potentiellement plus rapide?

ttnphns
la source

Réponses:

6

Soit les points indexés , tous dans . Soit les index d'un cluster et les index d'un autre cluster. Les centroïdes sontx1,x2,,xnRdIJ

cI=1|I|iIxi, cJ=1|J|jJxj

et on souhaite trouver leur distance au carré en termes de distances au carré .||cIcJ||2Dij=||xixj||2

Exactement comme nous décomposerions des sommes de carrés dans les calculs d'ANOVA, une identité algébrique est

||cIcJ||2=1|I||J|(SS(IJ)(|I|+|J|)(1|I|SS(I)+1|J|SS(J)))

où " " fait référence à la somme des carrés des distances entre chaque point d'un ensemble et leur centroïde. L' identité de polarisation le ré-exprime en termes de distances au carré entre tous les points:SS

SS(K)=12i,jK||xixj||2=i<jKDij.

L'effort de calcul est donc , avec une très petite constante implicite. Lorsque les grappes ont approximativement la même taille et qu'il y en a , c'est , qui est directement proportionnel au nombre d'entrées dans : ce serait le meilleur que l'on puisse espérer.O((|I|+|J|)2)kO(n2/k2)D


R Le code pour illustrer et tester ces calculs suit.

ss <- function(x) {
  n <- dim(x)[2]
  i <- rep(1:n, n)
  j <- as.vector(t(matrix(i,n)))
  d <- matrix(c(1,1) %*% (x[,i] - x[,j])^2 , n) # The distance matrix entries for `x`
  sum(d[lower.tri(d)])
}
centroid <- function(x) rowMeans(x)
distance2 <- function(x,y) sum((x-y)^2)
#
# Generate two clusters randomly.
#
n.x <- 3; n.y <- 2
x <- matrix(rnorm(2*n.x), 2)
y <- matrix(rnorm(2*n.y), 2)
#
# Compare two formulae.
#
cat("Squared distance between centroids =",
    distance2(centroid(x), centroid(y)),
    "Equivalent value =", 
    (ss(cbind(x,y)) - (n.x + n.y) * (ss(x)/n.x + ss(y)/n.y)) / (n.x*n.y),
    "\n")
whuber
la source
Parfait! Je dois avouer qu'en dépit je connaissais les identités du parallélogramme je ne pouvais pas moi-même voir clairement le lien avec ma tâche et en déduire la formule. Merci beaucoup à vous. J'ai déjà programmé la fonction (dans SPSS) en fonction de votre formule pour un certain nombre de centroïdes et elle est en effet plus rapide avec une grande matrice D que la manière indirecte via PCoA.
ttnphns
J'ajouterais également que la formule reste valable si les groupes / clusters se croisent par les compositions des objets.
ttnphns
Oui, c'est exact: l'identité que j'utilise ne suppose pas que les clusters sont disjoints.
whuber
Ajout d'un lien tardif: votre méthode en notation matricielle, sur laquelle j'ai basé cette fonction, j'ai dit plus haut. stats.stackexchange.com/a/237811/3277
ttnphns
1
@amoeba fait référence à tout sous-ensemble deK{1,2,,n}.
whuber