Maneira eficiente de calcular distâncias entre centróides a partir da matriz de distância

8

Vamos ter uma matriz simétrica quadrada de distâncias euclidianas quadradas entre n pontos e o vetor alongado n indicando a associação de grupos ou grupos ( k clusters) dos pontos; um cluster pode consistir em \ ge1 point.nDnk 1nk1

Qual é a maneira mais eficiente ou realmente eficiente (em termos de velocidade) de calcular distâncias entre os centróides do cluster aqui?

Até agora, eu sempre fazia a análise da coordenada principal nessa situação. PCoA ou MDS de Torgerson equivale a converter primeiro D na matriz de produtos escalares S ("centralização dupla") e depois executar o PCA. Dessa forma, criamos coordenadas para os n pontos no espaço euclidiano que eles ocupam. Depois disso, é fácil calcular as distâncias entre os centróides da maneira usual - como você faria com os grouped points x variablesdados. PCoA precisa decompor-se ou SVD do n x nsemidefinido positivo simétrico S , mas npode ser bem grande. Além disso, a tarefa não é uma redução de dimensionalidade e, na verdade, não precisamos desses eixos principais ortogonais. Então, sinto que essas decomposições podem ser um exagero.

Então, você tem conhecimento ou idéias sobre uma maneira potencialmente mais rápida?

ttnphns
fonte

Respostas:

6

Permita que os pontos sejam indexados , todos eles em . Seja os índices de um cluster e os índices de outro cluster. Os centróides sãoR d I Jx1,x2,,xnRdIJ

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

e é desejado encontrar a distância ao quadrado em termos das distâncias ao quadrado .D i j = | | x i - x j | | 2||cIcJ||2Dij=||xixj||2

Exatamente como decomporíamos somas de quadrados nos cálculos da ANOVA, uma identidade algébrica é

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

onde " " refere-se à soma dos quadrados das distâncias entre cada ponto de um conjunto e seu centróide. A identidade da polarização reexpressa isso em termos de distâncias ao quadrado entre todos os pontos:SS

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

O esforço computacional, portanto, é , com uma constante implícita muito pequena. Quando os clusters são aproximadamente do mesmo tamanho e existem , é , diretamente proporcional ao número de entradas em : seria o melhor que se poderia esperar.k O ( n 2 / k 2 ) DO((|I|+|J|)2)kO(n2/k2)D


R código para ilustrar e testar esses cálculos a seguir.

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
fonte
Perfeito! Devo confessar que, apesar de conhecer as identidades do paralelogramo, não conseguia ver claramente o link para minha tarefa e deduzir a fórmula. Muito obrigado a você. Eu já programei a função (no SPSS) com base em sua fórmula para qualquer número de centróides e é realmente mais rápido com matriz grande D do que a maneira indireta via PCoA.
Ttnphns
Eu também acrescentaria que a fórmula permanece válida se os grupos / clusters se cruzarem pelas composições dos objetos.
Ttnphns
Sim, isso está correto: a identidade que eu uso não assume que os clusters sejam disjuntos.
whuber
Apenas adicionando um link tardio: seu método em notação matricial, no qual baseei essa função que eu disse acima. stats.stackexchange.com/a/237811/3277
ttnphns
1
@amoeba refere-se a qualquer subconjunto de { 1 , 2 , , n } .K{1,2,,n}.
whuber