Manera eficiente de calcular distancias entre centroides desde la matriz de distancia

Tengamos una matriz simétrica cuadrada de distancias euclidianas cuadradas entre puntos y un vector alargado indica la pertenencia a un grupo o grupo ( grupos) de los puntos; un clúster puede consistir en punto.$\bf D$$n$$n$$k$$\ge1$

¿Cuál es la forma más eficiente o realmente eficiente (en términos de velocidad) para calcular las distancias entre los centroides del grupo aquí?

Hasta ahora siempre hice el análisis de la Coordinadora Principal en esta situación. PCoA, o MDS de Torgerson equivale a convertir primero en la matriz de productos escalares ("doble centrado") y luego realizar PCA de él. De esta manera creamos coordenadas para los puntos en el espacio euclidiano que abarcan. Después de eso, es fácil calcular las distancias entre los centroides de la manera habitual, como lo haría con los datos. PCoA tiene que hacer descomposición propia o SVD de la semidefinida simétrica positiva , pero$\bf D$$\bf S$$n$grouped points x variablesn x n$\bf S$$n$puede ser bastante grande Además, la tarea no es una reducción de dimensionalidad y en realidad no necesitamos esos ejes principales ortogonales. Así que tengo la sensación de que estas descomposiciones pueden ser una exageración.

Entonces, ¿tiene conocimiento o ideas sobre una forma potencialmente más rápida?

Deje que los puntos sean indexados $x_1, x_2, \ldots, x_n$todos ellos en $\mathbb{R}^d$. Dejar$\mathcal{I}$ ser los índices para un clúster y $\mathcal{J}$los índices para otro grupo. Los centroides son

$$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$$

y se desea encontrar su distancia al cuadrado $||c_\mathcal{I} - c_\mathcal{J}||^2$ en términos de las distancias al cuadrado $D_{ij} = ||x_i - x_j||^2$.

Exactamente como desglosaríamos sumas de cuadrados en los cálculos de ANOVA, una identidad algebraica es

$$||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)$$

dónde "$SS$"se refiere a la suma de cuadrados de distancias entre cada punto en un conjunto y su centroide. La identidad de polarización re-expresa esto en términos de distancias al cuadrado entre todos los puntos:

$$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}.$$

El esfuerzo computacional por lo tanto es $O((|\mathcal{I}|+|\mathcal{J}|)^2)$, con una constante implícita muy pequeña. Cuando los grupos son aproximadamente del mismo tamaño y hay$k$ de ellos, esto es $O(n^2/k^2)$, que es directamente proporcional al número de entradas en $D$: eso sería lo mejor que uno podría esperar.

---

R código para ilustrar y probar estos cálculos a continuación.

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")