Clustering com uma matriz de distância

Eu tenho uma matriz (simétrica) Mque representa a distância entre cada par de nós. Por exemplo,

    ABCDEFGHIJKL
A 0 20 20 20 40 60 60 60 100 120 120 120
B 20 0 20 20 60 80 80 80 120 140 140 140
C 20 20 0 20 60 80 80 80 120 140 140 140
D 20 20 20 0 60 80 80 80 120 140 140 140
E 40 60 60 60 0 20 20 20 60 80 80 80
F 60 80 80 80 20 0 20 20 40 60 60 60
G 60 80 80 80 20 20 0 20 60 80 80 80
H 60 80 80 80 20 20 20 0 60 80 80 80
I 100 120 120 120 60 40 60 60 0 20 20 20
J 120 140 140 140 80 60 80 80 20 0 20 20
K 120 140 140 140 80 60 80 80 20 20 0 20
L 120 140 140 140 80 60 80 80 20 20 20 0

Existe algum método para extrair clusters M(se necessário, o número de clusters pode ser corrigido), de modo que cada cluster contenha nós com pequenas distâncias entre eles. No exemplo, os clusters seria (A, B, C, D), (E, F, G, H)e (I, J, K, L).

Eu já tentei UPGMA e k-means, mas os clusters resultantes são muito ruins.

As distâncias são os passos médios que um caminhante aleatório tomaria para ir de nó Aem nó B( != A) e voltar ao nó A. É garantido que M^1/2é uma métrica. Para rodar k-means, eu não uso o centróide. Defino a distância entre o ncluster de nós ccomo a distância média entre ne todos os nós c.

Muito obrigado :)

Há uma série de opções.

agrupamento de k-medoids

Primeiro, você pode tentar particionar em torno do medoids (pam) em vez de usar o cluster do k-means. Este é mais robusto e pode dar melhores resultados. Van der Laan reformulou o algoritmo. Se você mesmo vai implementá-lo, vale a pena ler o artigo dele .

Existe um algoritmo específico de agrupamento k-medoids para grandes conjuntos de dados. O algoritmo é chamado Clara em R e é descrito no capítulo 3 de Localização de grupos em dados: uma introdução à análise de cluster. por Kaufman, L e Rousseeuw, PJ (1990).

agrupamento hierárquico

Em vez de UPGMA, você pode tentar outras opções de cluster hierárquico. Primeiro de tudo, quando você usa cluster hierárquico, certifique-se de definir o método de particionamento corretamente. Esse método de particionamento é essencialmente como as distâncias entre observações e clusters são calculadas. Uso principalmente o método de Ward ou a ligação completa, mas outras opções podem ser a escolha para você.

Ainda não sei se você tentou, mas o método de ligação única ou a junção de vizinhos é geralmente preferido acima do UPGMA em aplicações filogenéticas. Se você ainda não experimentou, pode tentar também, pois geralmente oferece resultados notavelmente bons.

---

No R, você pode dar uma olhada no cluster de pacotes . Todos os algoritmos descritos são implementados lá. Veja? Pam,? Clara,? Hclust, ... Verifique também a implementação diferente do algoritmo em? Kmeans. Às vezes, escolher outro algoritmo pode melhorar substancialmente o cluster.

---

Edição: Apenas pensei em algo: se você trabalha com gráficos e nós e os gostos, você deve dar uma olhada no algoritmo de cluster Markov também. Essa é usada, por exemplo, no agrupamento de seqüências com base em similaridades de explosão e tem um desempenho incrivelmente bom. Ele pode fazer o agrupamento para você ou fornecer algumas idéias sobre como resolver o problema de pesquisa em que você está se concentrando. Sem saber nada sobre isso, acho que vale a pena olhar para os resultados dele. Se assim posso dizer, ainda considero esse método de Stijn van Dongen um dos melhores resultados em cluster que já encontrei.

http://www.micans.org/mcl/

Uma maneira de destacar clusters em sua matriz de distância é por meio do dimensionamento multidimensional . Ao projetar indivíduos (aqui o que você chama de nós) em um espaço 2D, ele fornece uma solução comparável ao PCA. Isso não é supervisionado, portanto você não poderá especificar a priori o número de clusters, mas acho que pode ajudar a resumir rapidamente uma determinada distância ou matriz de similaridade.

Aqui está o que você obteria com seus dados:

tmp <- matrix(c(0,20,20,20,40,60,60,60,100,120,120,120,
                20,0,20,20,60,80,80,80,120,140,140,140,
                20,20,0,20,60,80,80,80,120,140,140,140,
                20,20,20,0,60,80,80,80,120,140,140,140,
                40,60,60,60,0,20,20,20,60,80,80,80,
                60,80,80,80,20,0,20,20,40,60,60,60,
                60,80,80,80,20,20,0,20,60,80,80,80,
                60,80,80,80,20,20,20,0,60,80,80,80,
                100,120,120,120,60,40,60,60,0,20,20,20,
                120,140,140,140,80,60,80,80,20,0,20,20,
                120,140,140,140,80,60,80,80,20,20,0,20,
                120,140,140,140,80,60,80,80,20,20,20,0),
              nr=12, dimnames=list(LETTERS[1:12], LETTERS[1:12]))
d <- as.dist(tmp)
mds.coor <- cmdscale(d)
plot(mds.coor[,1], mds.coor[,2], type="n", xlab="", ylab="")
text(jitter(mds.coor[,1]), jitter(mds.coor[,2]),
     rownames(mds.coor), cex=0.8)
abline(h=0,v=0,col="gray75")

Adicionei um pequeno tremor nas coordenadas xey para permitir casos distintos. Substitua tmppor 1-tmpse preferir trabalhar com diferenças, mas isso gera essencialmente a mesma imagem. No entanto, aqui está a solução hierárquica de clustering, com um único critério de aglomeração:

plot(hclust(dist(1-tmp), method="single"))

Você pode refinar ainda mais a seleção de clusters com base no dendograma, ou métodos mais robustos, consulte, por exemplo, esta pergunta relacionada: Quais critérios de parada para clustering hierárquico aglomerativo são usados ​​na prática?

O agrupamento espectral [1] requer uma matriz de afinidade, sendo o agrupamento definido pelas primeiras funções próprias da decomposição de$K$

$$\textbf{L} = \textbf{D}^{-1/2} \textbf{A} \textbf{D}^{-1/2}$$

Com sendo a matriz de afinidade dos dados e sendo a matriz diagonal definida como (edit: desculpe por não ser clara, mas você pode gerar uma matriz de afinidade a partir de uma matriz de distância, desde que saiba o máximo possível / distância razoável como , embora outros esquemas também existam)$\textbf{A}$$\textbf{D}$$A_{ij}=1-d_{ij}/\max(d)$

$$\left\{\begin{matrix}\begin{align}&\textbf{D}_{i,i}=\sum_{j}{\textbf{A}_{i,j}}\\ &\textbf{D}_{i \neq j}=0\end{align}\end{matrix}\right.$$

Com sendo a composição automática de , com funções próprias empilhadas como colunas, mantendo apenas os maiores vetores próprios em , definimos a matriz normalizada de linhaL K $\textbf{X}$$\textbf{L}$$K$$\textbf{X}$

$$\textbf{Y}_{ij}=\frac{\textbf{X}_{ij}}{\left(\sum_{j}{\left( \textbf{X}_{ij} \right)^{2}}\right)^{1/2}}$$

Cada linha de é um ponto em e pode ser agrupada em cluster com um algoritmo de agrupamento comum (como K-means).R $\textbf{Y}$$\mathbb{R}^{k}$

Veja a minha resposta aqui para ver um exemplo: https://stackoverflow.com/a/37933688/2874779

---

_{[1] Ng, AY, Jordânia, MI, e Weiss, Y. (2002). Sobre agrupamento espectral: Análise e um algoritmo. Avanços nos sistemas de processamento de informações neurais, 2, 849-856. Pág.2}

O que você está fazendo é tentar agrupar nós de um gráfico ou rede que estejam próximos um do outro. Existe todo um campo de pesquisa dedicado a esse problema, que às vezes é chamado de detecção comunitária em redes . Olhar para o seu problema deste ponto de vista provavelmente pode esclarecer as coisas.

Você encontrará muitos algoritmos dedicados a esse problema e, de fato, alguns deles são baseados na mesma idéia que você teve, que é medir distâncias entre nós com passeios aleatórios.

O problema é frequentemente formulado como otimização da modularidade [1], em que a modularidade de um cluster mede o quão bem o cluster separa a rede em clusters densamente conectados (ou seja, clusters onde os nós estão próximos uns dos outros).

Na verdade, você pode mostrar que a modularidade é igual à probabilidade de um caminhante aleatório permanecer, após uma etapa, nos mesmos aglomerados do que inicialmente menos a mesma probabilidade para dois caminhantes aleatórios independentes [2].

Se você permitir mais etapas dos caminhantes aleatórios, estará procurando um cluster mais grosseiro da rede. O número de etapas da caminhada aleatória desempenha, portanto, o papel de um parâmetro de resolução que permite recuperar uma hierarquia de clusters. Nesse caso, a quantidade que expressa a tendência de caminhantes aleatórios permanecerem em seu cluster inicial após as etapas t é chamada de estabilidade de Markov de uma partição no tempo t [2] e é equivalente à modularidade quando t = 1 .

Portanto, você pode resolver seu problema localizando o agrupamento do gráfico que otimiza a estabilidade em um determinado momento t , onde t é o parâmetro de resolução ( t maior fornecerá clusters maiores). Um dos métodos mais utilizados para otimizar a estabilidade (ou modularidade com um parâmetro de resolução) é o algoritmo de Louvain [3]. Você pode encontrar uma implementação aqui: https://github.com/michaelschaub/generalizedLouvain .

[1] Newman, MEJ e Girvan, M. Encontrando e avaliando a estrutura da comunidade em redes. Phys. Rev. E 69, 026113 (2004).

[2] Delvenne, J.-C., Yaliraki, SN & Barahona, M. Estabilidade de comunidades gráficas em escalas de tempo. Proc. Natl. Acad. Sci. 107, 12755-12760 (2010).

[3] Blondel, VD, Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Desenvolvimento rápido de comunidades em grandes redes. J. Stat. Mech. Teoria Exp. 2008, P10008 (2008).

Bem, é possível executar o agrupamento de médias K em uma determinada matriz de similaridade; primeiro, você precisa centralizar a matriz e, em seguida, obter os autovalores da matriz. O passo final e o mais importante é multiplicar os dois primeiros conjuntos de vetores próprios para a raiz quadrada das diagonais dos valores próprios para obter os vetores e depois seguir com K-médias. Abaixo o código mostra como fazê-lo. Você pode alterar a matriz de similaridade. fpdist é a matriz de similaridade.

mds.tau <- function(H)
{
  n <- nrow(H)
   P <- diag(n) - 1/n
   return(-0.5 * P %*% H %*% P)
  }
  B<-mds.tau(fpdist)
  eig <- eigen(B, symmetric = TRUE)
  v <- eig$values[1:2]
#convert negative values to 0.
v[v < 0] <- 0
X <- eig$vectors[, 1:2] %*% diag(sqrt(v))
library(vegan)
km <- kmeans(X,centers= 5, iter.max=1000, nstart=10000) .
#embedding using MDS
cmd<-cmdscale(fpdist)

Antes de tentar executar o clustering na matriz, você pode tentar executar uma das técnicas de análise fatorial e manter apenas as variáveis ​​mais importantes para calcular a matriz de distância. Outra coisa que você pode fazer é tentar usar métodos difusos que tendem a funcionar melhor (pelo menos na minha experiência) nesse tipo de casos, tente primeiro Cmeans, K-medoids difusos e Especialmente GKCmeans.

O agrupamento em cluster é uma das respostas que eu acho. Mas não sou especialista aqui. Co-clustrar não é um método recém-nascido, então você pode encontrar alguns algos em R, o wiki mostra esses conceitos de maneira adequada. Outro método que não é mencionado é o particionamento de gráficos (mas vejo que o gráfico não seria escasso, o particionamento de gráficos seria útil se sua matriz fosse dominada por valores que significam = distância máxima = sem similaridade entre os nós).

Veja a PROPAGAÇÃO DE AFINIDADE. Essa técnica utiliza como entrada a matriz de similaridade e produz um número ideal de clusters, juntamente com um exemplo representativo para cada cluster.

Primeiro converta a matriz de distância em uma matriz de coordenadas via https://math.stackexchange.com/a/423898; então, você poderá usar facilmente qualquer algoritmo de armazenamento em cluster existente com eficiência.

Você também pode usar o algoritmo Kruskal para encontrar árvores abrangentes mínimas, mas terminando assim que obtiver os três grupos. Eu tentei dessa maneira e produz os clusters que você mencionou: {ABCD}, {EFGH} e {IJKL}.