La agrupación con una matriz de distancias

Question

Tengo una (simétrica) de la matriz M que representa la distancia entre cada par de nodos. Por ejemplo,

 A B C D E F G H I J K L
Un 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
Yo 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

¿Hay algún método para extraer los clústeres de M (si es necesario, el número de grupos puede ser fija), de tal manera que cada grupo contiene los nodos con pequeñas distancias entre ellos. En el ejemplo, los grupos serían (A, B, C, D), (E, F, G, H) y (I, J, K, L).

Ya he probado UPGMA y k-medio, pero el resultado de los clústeres son muy malas.

Las distancias son el promedio de pasos al azar walker iba a tomar para ir desde el nodo A al nodo B (!= A) y vaya al nodo A. Se garantiza que M^1/2 es una métrica. Para ejecutar k-medio, yo no uso el centroide. Puedo definir la distancia entre el nodo n clúster c como la distancia promedio entre n y todos los nodos en c.

Muchas gracias :)

Answer 1

Hay un número de opciones.

k-medoids la agrupación

En primer lugar, usted podría tratar de partición alrededor de medoids (pam) en lugar de utilizar k-means clustering. Este es más robusto, y podría dar mejores resultados. Van der Laan reelabora el algoritmo. Si vas a aplicar a ti mismo, de su artículo es la pena leer.

Hay un tipo específico de k-medoids algoritmo de clustering para grandes conjuntos de datos. El algoritmo se llama Clara en R, y se describe en el capítulo 3 de Encontrar Grupos de Datos: Una Introducción al Análisis de Cluster. por Kaufman, L y Rousseeuw, PJ (1990).

la agrupación jerárquica

En lugar de UPGMA, usted podría tratar de alguna otra agrupación jerárquica de opciones. Primero de todo, cuando se utiliza el agrupamiento jerárquico, asegúrese de definir el método de partición correctamente. Este método de partición es esencialmente cómo las distancias entre las observaciones y los clústeres se calcula. Que en su mayoría utilizan el método de Ward o de unión completa, pero que otras opciones pueden ser la opción para usted.

No sé si la he probado, pero el único método de vinculación o vecino de unión es a menudo preferido por encima de UPGMA en filogenético de las aplicaciones. Si no lo intenté, sin embargo, usted podría darle un tiro así, como a menudo se da muy buenos resultados.

---

En R, usted puede tener una mirada en el paquete de clúster. Todo lo descrito se implementan los algoritmos de allí. Ver ?pam ?clara, ?hclust, ... Ver también los diferentes implementación del algoritmo ?kmeans. A veces eligiendo otro algoritmo puede mejorar la agrupación sustancialmente.

---

EDIT : Solo pensamiento acerca de algo: Si trabajar con gráficos y los nodos y los gustos, usted debe echar un vistazo a la markov algoritmo de clustering así. Que uno es utilizado, por ejemplo, en la agrupación de secuencias basado en las similitudes blast, y funciona increíblemente bien. Se puede hacer la agrupación para usted, o le dará algunas ideas sobre cómo resolver el problema de investigación que se está concentrando. Sin saber nada acerca de él, de hecho, supongo que sus resultados son definitivamente vale la pena mirar. Si puede decirse así, sigo pensando que este método de Stijn van Dongen uno de los mejores resultados en la agrupación que me he encontrado.

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

Answer 2

Una forma de resaltar el clústeres en su matriz de distancias es por medio de escalamiento Multidimensional. Cuando la proyección de los individuos (esto es lo que usted llame a su nodos) en un 2D-espacio, proporciona una solución comparable a la PCA. Este es sin supervisión, por lo que no será capaz de especificar a priori el número de grupos, pero creo que puede ayudar a resumir rápidamente una distancia determinada o matriz de similitud.

Aquí es lo que puedes conseguir con tus datos:

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

He añadido una pequeña variación en las coordenadas x e y para permitir distinguir los casos. Reemplace tmp por 1-tmp si usted prefiere trabajar con las diferencias, pero esto produce esencialmente la misma imagen. Sin embargo, aquí es el agrupamiento jerárquico de solución, con la única aglomeración criterios:

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

Usted puede refinar la selección de los grupos basados en el dendrograma, o más métodos robustos, ver, por ejemplo, esta relacionada con la pregunta: ¿Qué parada-criterios para agglomerative de agrupamiento jerárquico se utilizan en la práctica?

Answer 3

Antes de intentar ejecutar la agrupación en clústeres en la matriz puede tratar de hacer uno de los factor de técnicas de análisis, y mantener sólo las variables más importantes para calcular la matriz de distancias. Otra cosa que puedes hacer es tratar de usar difusa de los métodos que tienden a funcionar mejor (al menos en mi experiencia) en este tipo de casos, intente primero Cmeans, Fuzzy K-medoids, y Especialmente GKCmeans.

Answer 4

Co-agrupación es una de las respuestas, creo. Pero no soy experto aquí. Co-clustring no es recién nacido, método, así que usted puede encontrar algunos de los algos en R, wiki muestra que los conceptos de buena manera. Otro método que no es menthioned es el gráfico de partición (pero puedo ver que el gráfico no se dispersa,el gráfico de partición podría ser útil si su matriz sería dominado por los valores de significado=distancia máxima=no existe similitud entre los nodos).

Answer 5

Buscar en la PROPAGACIÓN de AFINIDAD, Esta técnica toma como entrada la matriz de similitud y produce un número óptimo de clusters, junto con un ejemplo representativo de cada grupo.