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

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 .$\bf D$$n$$n$$k$$\ge1$

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 , mais$\bf D$$\bf S$$n$grouped points x variablesn x n$\bf S$$n$peut ê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?

Soit les points indexés , tous dans . Soit les index d'un cluster et les index d'un autre cluster. Les centroïdes sont$x_1, x_2, \ldots, x_n$$\mathbb{R}^d$$\mathcal{I}$$\mathcal{J}$

$$c_\mathcal{I} = \frac{1}{|\mathcal{I}|} \sum_{i\in\mathcal{I}} x_i,\ c_\mathcal{J} = \frac{1}{|\mathcal{J}|} \sum_{j\in\mathcal{J}} x_j$$

et on souhaite trouver leur distance au carré en termes de distances au carré .$||c_\mathcal{I} - c_\mathcal{J}||^2$$D_{ij} = ||x_i - x_j||^2$

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

$$||c_\mathcal{I} - c_\mathcal{J}||^2 = \frac{1}{|\mathcal{I}||\mathcal{J}|} \left(SS(\mathcal{I \cup J}) -\left(|\mathcal{I}|+|\mathcal{J}|\right) \left(\frac{1}{|\mathcal{I}|}SS(\mathcal{I}) + \frac{1}{|\mathcal{J}|}SS(\mathcal{J})\right)\right)$$

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(\mathcal{K}) = \frac{1}{2}\sum_{i,j\,\in\,\mathcal{K}} ||x_i - x_j||^2 = \sum_{i\lt j\,\in\,\mathcal{K}} D_{ij}.$$

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((|\mathcal{I}|+|\mathcal{J}|)^2)$$k$$O(n^2/k^2)$$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")