Elegir el método de enlace correcto para la agrupación jerárquica

Estoy realizando una agrupación jerárquica en los datos que he recopilado y procesado desde el volcado de datos reddit en Google BigQuery.

Mi proceso es el siguiente:

• Recibe las últimas 1000 publicaciones en / r / política
• Reúne todos los comentarios
• Procese los datos y calcule una n x mmatriz de datos (n: usuarios / muestras, m: publicaciones / características)
• Calcular la matriz de distancia para la agrupación jerárquica
• Elija un método de vinculación y realice el agrupamiento jerárquico
• Graficar los datos como un dendrograma

Mi pregunta es, ¿cómo determino cuál es el mejor método de vinculación ? Actualmente estoy usando Wardpero ¿cómo puedo saber si debo utilizar single, complete, average, etc?

Soy muy nuevo en estas cosas, pero no puedo encontrar una respuesta clara en línea, ya que no estoy seguro de que haya una. Entonces, ¿cuál podría ser una buena idea para mi aplicación? Tenga en cuenta que los datos son relativamente escasos en el sentido de que la n x mmatriz tiene muchos ceros (la mayoría de las personas no comentan más que unas pocas publicaciones).

Resumen de métodos

Breve referencia sobre algunos métodos de enlace del análisis jerárquico de conglomerados aglomerativos (HAC).

La versión básica del algoritmo HAC es una genérica; equivale a actualizar, en cada paso, mediante la fórmula conocida como fórmula de Lance-Williams, las proximidades entre el grupo emergente (combinado de dos) y todos los otros grupos (incluidos los objetos únicos) existentes hasta ahora. Existen implementaciones que no usan la fórmula de Lance-Williams. Pero usarlo es conveniente: permite codificar varios métodos de enlace por la misma plantilla.

La fórmula de recurrencia incluye varios parámetros (alfa, beta, gamma). Dependiendo del método de vinculación, los parámetros se configuran de manera diferente y, por lo tanto, la fórmula sin envolver obtiene una vista específica. Muchos textos sobre HAC muestran la fórmula, sus puntos de vista específicos del método y explican los métodos. Recomendaría los artículos de Janos Podani como muy completos.

El espacio y la necesidad de los diferentes métodos surgen del hecho de que una proximidad (distancia o similitud) entre dos grupos o entre un grupo y un objeto singleton podría formularse de muchas maneras diferentes. HAC combina en cada paso los dos grupos o puntos más cercanos, pero el problema es formular cómo calcular la proximidad mencionada anteriormente en la cara que la matriz de proximidad de entrada se definió solo entre objetos singleton.

Por lo tanto, los métodos difieren con respecto a cómo definen la proximidad entre dos grupos en cada paso. El "coeficiente de coligación" (salida en el programa / historial de aglomeración y formando el eje "Y" en un dendrograma) es solo la proximidad entre los dos grupos combinados en un paso dado.

• Método de enlace único o vecino más cercano . La proximidad entre dos grupos es la proximidad entre sus dos objetos más cercanos. Este valor es uno de los valores de la matriz de entrada. La metáfora conceptual de este construido de clúster, su arquetipo, es espectro o cadena . Las cadenas pueden ser rectas o curvilíneas, o pueden ser como una vista de "copo de nieve" o "ameba". Los dos miembros del clúster más diferentes pueden ser muy diferentes en comparación con los dos más similares. El método de enlace único controla solo la similitud de los vecinos más cercanos.

• Método de enlace completo o vecino más lejano . La proximidad entre dos grupos es la proximidad entre sus dos objetos más distantes. Este valor es uno de los valores de la matriz de entrada. La metáfora de este grupo formado es el círculo (en el sentido, por pasatiempo o trama) donde los dos miembros más distantes entre sí no pueden ser mucho más diferentes que otros pares bastante diferentes (como en círculo). Dichos grupos son contornos "compactos" por sus bordes, pero no son necesariamente compactos por dentro.

• Método de vinculación promedio entre grupos (UPGMA). La proximidad entre dos grupos es la media aritmética de todas las proximidades entre los objetos de uno, en un lado, y los objetos del otro, en el otro lado. La metáfora de este conjunto de clúster es bastante genérica, solo clase unida o colectiva unida; y el método se configura con frecuencia como el predeterminado en los paquetes de agrupación jerárquica. Se pueden producir grupos de formas y contornos diversos.

• El promedio simple , o método de enlace de equilibrio entre grupos promedio (WPGMA) es el anterior modificado. La proximidad entre dos grupos es la media aritmética de todas las proximidades entre los objetos de uno, en un lado, y los objetos del otro, en el otro lado; mientras que los subgrupos de los cuales cada uno de estos dos grupos se fusionaron recientemente tienen una influencia igualada en esa proximidad, incluso si los subgrupos diferían en la cantidad de objetos.

• Método de vinculación promedio dentro del grupo (MNDIS). La proximidad entre dos grupos es la media aritmética de todas las proximidades en su grupo articular. Este método es una alternativa a UPGMA. Por lo general, perderá en términos de densidad de conglomerados, pero a veces descubrirá formas de conglomerados que UPGMA no detectará.

• Método centroide (UPGMC). La proximidad entre dos grupos es la proximidad entre sus centroides geométricos: [al cuadrado] distancia euclidiana entre ellos. La metáfora de este construido de clúster es la proximidad de plataformas (política). Al igual que en los partidos políticos, tales grupos pueden tener fracciones o "facciones", pero a menos que sus figuras centrales estén separadas entre sí, el sindicato es consistente. Los grupos pueden ser varios por esquema.

• La mediana , o método centroide equilibrado (WPGMC) es el anterior modificado. La proximidad entre dos grupos es la proximidad entre sus centroides geométricos (distancia euclidiana [al cuadrado] entre ellos); mientras que los centroides se definen de modo que los subgrupos de los cuales cada uno de estos dos grupos se fusionaron recientemente tengan influencia igualada en su centroide, incluso si los subgrupos diferían en el número de objetos.

• $SS_{12}-(SS_1+SS_2)$$2$. Intuitivamente, un tipo es una nube más densa y más concéntrica hacia su centro, mientras que los puntos marginales son pocos y podrían dispersarse con relativa libertad.

Algunos de los métodos menos conocidos (ver Podany J. Nuevos métodos de agrupamiento combinatorio // Vegetatio, 1989, 81: 61-77.) [También implementado por mí como una macro SPSS encontrada en mi página web]:

• $SS_{12}$$2$

• $MS_{12}-(n_1MS_1+n_2MS_2)/(n_1+n_2) = [SS_{12}-(SS_1+SS_2)]/(n_1+n_2)$$4$

• $MS_{12} = SS_{12}/(n_1+n_2)$$4$

Los primeros 5 métodos permiten cualquier medida de proximidad (cualquier similitud o distancia) y los resultados, naturalmente, dependerán de la medida elegida.

Los últimos 6 métodos requieren distancias; y completamente correcto será usar solo distancias euclidianas cuadradas con ellos, porque estos métodos calculan los centroides en el espacio euclidiano. Por lo tanto, las distancias deben ser euclidianas en aras de la corrección geométrica (estos 6 métodos se denominan métodos de enlace geométrico ). En el peor de los casos, puede ingresar otra métricadistancias al admitir análisis más heurísticos, menos rigurosos. Ahora sobre ese "cuadrado". El cálculo de los centroides y las desviaciones de ellos son más convenientes matemáticamente / programáticamente para realizar en distancias cuadradas, es por eso que los paquetes HAC generalmente requieren entrada y se ajustan para procesar los cuadrados. Sin embargo, existen implementaciones, totalmente equivalentes pero un poco más lentas, basadas en la entrada de distancias no cuadradas y que las requieren; ver por ejemplo la implementación "Ward-2" para el método de Ward. Debe consultar con la documentación de su programa de agrupación para saber qué distancias cuadradas o no se esperan en la entrada a un "método geométrico" para hacerlo bien.

Los métodos MNDIS, MNSSQ y MNVAR requieren pasos, además de actualizar la fórmula de Lance-Williams, para almacenar una estadística dentro del clúster (que depende del método).

Los métodos que se usan con mayor frecuencia en los estudios en los que se espera que los grupos sean nubes sólidas más o menos redondas, son métodos de enlace promedio, método de enlace completo y método de Ward.

El método de Ward es el más cercano, por sus propiedades y eficiencia, a la agrupación de K-medios; comparten la misma función objetivo: minimizar el SS agrupado dentro del clúster "al final". Por supuesto, K-means (que es iterativo y si se proporciona con centroides iniciales decentes) suele ser un mejor minimizador que Ward. Sin embargo, Ward me parece un poco más preciso que K-means al descubrir grupos de tamaños físicos desiguales (variaciones) o grupos lanzados por el espacio de manera muy irregular. El método MIVAR es extraño para mí, no puedo imaginar cuándo podría recomendarse, no produce grupos suficientemente densos.

Los métodos centroide, mediana, aumento mínimo de la varianza pueden dar a veces las llamadas reversiones : un fenómeno cuando los dos grupos que se fusionan en algún momento parecen estar más cerca el uno del otro que los pares de grupos fusionados anteriormente. Esto se debe a que estos métodos no pertenecen al llamado ultramétrico. Esta situación es inconveniente, pero teóricamente está bien.

Los métodos de enlace único y centroide pertenecen a la llamada contratación de espacio , o "encadenamiento". Eso significa, en términos generales, que tienden a unir objetos uno por uno a los grupos y, por lo tanto, demuestran un crecimiento relativamente suave de la curva "% de objetos agrupados". Por el contrario, los métodos de enlace completo, Ward, suma de cuadrados, aumento de la varianza y varianza comúnmente obtienen una parte considerable de los objetos agrupados incluso en los primeros pasos, y luego continúan fusionando aquellos, por lo tanto, su curva "% de objetos agrupados "Es empinado desde los primeros pasos. Estos métodos se llaman dilatación del espacio . Otros métodos quedan en el medio.

Versiones flexibles . Al agregar el parámetro adicional a la fórmula de Lance-Willians, es posible hacer que un método se autoajuste específicamente en sus pasos. El parámetro trae corrección para la proximidad calculada entre grupos, que depende del tamaño (cantidad de falta de compactación) de los grupos. El significado del parámetro es que hace que el método de aglomeración tenga más dilatación o contracción espacial de lo que el método estándar está condenado a ser. La implementación más conocida de la flexibilidad hasta el momento es promediar los métodos de enlace UPGMA y WPGMA (Belbin, L. et al. A Comparison of Two Approaches to Beta-Flexible Clustering // Multivariate Behavioral Research, 1992, 27, 417–433. )

Dendrograma En un eje "Y" de dendrograma, normalmente se muestra la proximidad entre los grupos de fusión, como se define por los métodos anteriores. Por lo tanto, por ejemplo, en el método centroide, la distancia al cuadrado generalmente se mide (en última instancia, depende del paquete y sus opciones); algunas investigaciones no son conscientes de eso. Además, según la tradición, los métodos basados ​​en el incremento de la no densidad, como el de Ward, que generalmente se muestran en el dendrograma tienen un valor acumulativo ; es más rápido por razones de conveniencia que los teóricos. Por lo tanto, (en muchos paquetes) el coeficiente trazado en el método de Ward representa el total, en todos los grupos, la suma de cuadrados dentro del grupo observada en el momento de un paso dado.

Uno debe abstenerse de juzgar qué método de enlace es "mejor" para sus datos al comparar el aspecto de los dendrogramas: no solo porque el aspecto cambia cuando cambia qué modificación del coeficiente traza allí, como se acaba de describir, sino porque el aspecto diferirá incluso en los datos sin clústeres.

Para elegir el método "correcto"

No hay un criterio único . Algunas pautas sobre cómo seleccionar un método de análisis de conglomerados (incluido un método de vinculación en HAC como caso particular) se resumen en esta respuesta y en todo el hilo de la misma.

La correlación entre la matriz de distancia y la distancia cophenetic es una métrica para ayudar a evaluar qué enlace de agrupamiento seleccionar. De ?cophenetic:

Se puede argumentar que un dendrograma es un resumen apropiado de algunos datos si la correlación entre las distancias originales y las distancias cophenetic es alta.

Este uso de cor(dist,cophenetic(hclust(dist)))como una métrica de selección de vinculación se referencia en la página 38 de esta vegan viñeta .

Vea el código de ejemplo a continuación:

# Data
d0=dist(USArrests)

# Hierarchical Agglomerative Clustering
h1=hclust(d0,method='average')
h2=hclust(d0,method='complete')
h3=hclust(d0,method='ward.D')
h4=hclust(d0,method='single')

# Cophenetic Distances, for each linkage
c1=cophenetic(h1)
c2=cophenetic(h2)
c3=cophenetic(h3)
c4=cophenetic(h4)

# Correlations
cor(d0,c1) # 0.7658983
cor(d0,c2) # 0.7636926
cor(d0,c3) # 0.7553367
cor(d0,c4) # 0.5702505

# Dendograms
par(mfrow=c(2,2))
plot(h1,main='Average Linkage')
plot(h2,main='Complete Linkage')
plot(h3,main='Ward Linkage')
plot(h4,main='Single Linkage')
par(mfrow=c(1,1))

Vemos que las correlaciones para averagey completeson extremadamente similares, y sus dendogramas parecen muy similares. La correlación para wardes similar a averagey completepero el dendograma parece bastante diferente. singlela vinculación está haciendo lo suyo. El mejor juicio profesional de un experto en la materia, o la precedencia hacia un determinado enlace en el campo de interés probablemente debería anular la salida numérica de cor().