8 votos

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

Vamos a tener la plaza matriz simétrica de los cuadrados de las distancias euclídeas $\bf D$ $n$ puntos y vectores lengthed $n$, lo que indica cluster o grupo de pertenencia ($k$ clusters) de los puntos; un clúster puede consistir $\ge1$ punto.

¿Cuál es el más eficaz o muy eficaz (en términos de velocidad) forma de calcular las distancias entre el clúster de los centroides de aquí?

Hasta ahora siempre lo hice Principal Coordinar el análisis en esta situación. PCoA, o Torgerson del MDS asciende a primera conversión de $\bf D$ en la matriz de productos escalares $\bf S$ ("doble centrado") y, a continuación, realizar la PCA. De esta manera podemos crear las coordenadas de la $n$ puntos en el espacio euclidiano que abarcan. Después de eso, es fácil de calcular las distancias entre los centroides de la forma habitual - como lo harías con grouped points x variables de datos. PCoA tiene que ver eigen-descomposición o de enfermedad vesicular porcina de la n x n simétrica positiva semidefinite $\bf S$, pero $n$ puede ser bastante grande. Además, la tarea no es una reducción de dimensionalidad uno y que en realidad no necesitan de esas ortogonal de los ejes principales. Así que tengo una sensación de que estas descomposiciones podría ser una exageración.

Entonces, ¿tiene usted conocimiento o ideas acerca de una potencial forma más rápida?

7voto

jldugger Puntos 7490

Deje que los puntos sean indexados $x_1, x_2, \ldots, x_n$, todos ellos en $\mathbb{R}^d$. Deje $\mathcal{I}$ los índices de un clúster y $\mathcal{J}$ los índices de otro clúster. 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$$

and it is desired to find their squared distance $||c_\mathcal{I} - c_\mathcal{J}||^2$ in terms of the squared distances $D_{ij} = ||x_i - x_j||^2$.

Exactly as we would break down sums of squares in ANOVA calculations, an algebraic identity is

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

where "$SS$" refers to the sum of squares of distances between each point in a set and their centroid. The polarization identity re-expresses this in terms of squared distances between all points:

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

The computational effort therefore is $O((|\mathcal{I}|+|\mathcal{J}|)^2)$, with a very small implicit constant. When the clusters are approximately the same size and there are $k$ of them, this is $O(n^2/k^2)$, which is directly proportional to the number of entries in $D$: que sería la mejor que se podía esperar.


R código para ilustrar y probar estos cálculos de la siguiente manera.

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

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X