Effiziente Methode zur Berechnung der Abstände zwischen Schwerpunkten aus der Entfernungsmatrix

Lassen Sie uns eine quadratische symmetrische Matrix quadratischer euklidischer Abstände zwischen Punkten und einem Vektor mit einer Länge von , die die Cluster- oder Gruppenzugehörigkeit ( Cluster) der Punkte anzeigt ; Ein Cluster kann aus Punkt bestehen.$\bf D$$n$$n$$k$$\ge1$

Was ist hier die effizienteste oder wirklich effizienteste (in Bezug auf die Geschwindigkeit) Methode, um Entfernungen zwischen den Cluster-Schwerpunkten zu berechnen ?

Bisher habe ich in dieser Situation immer eine Hauptkoordinatenanalyse durchgeführt. PCoA oder Torgersons MDS bedeutet , zuerst in die Matrix der Skalarprodukte ("doppelte Zentrierung") umzuwandeln und dann eine PCA davon durchzuführen. Auf diese Weise erstellen wir Koordinaten für die Punkte in dem euklidischen Raum, den sie überspannen. Danach ist es einfach, die Abstände zwischen den Zentroiden auf die übliche Weise zu berechnen - wie Sie es mit Daten tun würden . PCoA muss eine Eigenzerlegung oder SVD des symmetrischen positiven Semidefinits , aber$\bf D$$\bf S$$n$grouped points x variablesn x n$\bf S$$n$kann ziemlich groß sein. Außerdem ist die Aufgabe keine Dimensionsreduktionsaufgabe, und wir benötigen diese orthogonalen Hauptachsen tatsächlich nicht. Ich habe das Gefühl, dass diese Zerlegungen ein Overkill sein könnten.

Haben Sie Kenntnisse oder Ideen zu einem möglicherweise schnelleren Weg?

Lassen Sie die Punkte indizieren , alle in R d . Lassen Sie mich die Indizes für einen Cluster und J die Indizes für einen anderen Cluster sein. Die Zentroide sind$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$$

und es ist erwünscht , ihren quadratischen Abstand finden in Bezug auf die quadratischen Abstände D i j = | | x i - x j | | 2 .$||c_\mathcal{I} - c_\mathcal{J}||^2$$D_{ij} = ||x_i - x_j||^2$

Genau so, wie wir Quadratsummen in ANOVA-Berechnungen aufschlüsseln würden, ist eine algebraische Identität

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

wobei sich " " auf die Summe der Quadrate der Abstände zwischen jedem Punkt in einer Menge und ihrem Schwerpunkt bezieht. Die Polarisationsidentität drückt dies in quadratischen Abständen zwischen allen Punkten erneut aus:$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}.$$

$O((|\mathcal{I}|+|\mathcal{J}|)^2)$$k$$O(n^2/k^2)$$D$

---

R Es folgt ein Code zur Veranschaulichung und zum Testen dieser Berechnungen.

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