Elegir el método de enlace correcto para agrupamiento jerárquico

Question

Estoy realizando clustering jerárquico en datos que he recopilado y procesado del volcado de datos de Reddit en Google BigQuery.

Mi proceso es el siguiente:

• Obtener los últimos 1000 mensajes en /r/politics
• Recopilar todos los comentarios
• Procesar los datos y calcular una matriz de datos n x m (n: usuarios/muestras, m: mensajes/características)
• Calcular la matriz de distancias para el clustering jerárquico
• Elegir un método de enlace y realizar el clustering jerárquico
• Representar los datos como un dendrograma

Mi pregunta es, ¿cómo determino cuál es el mejor método de enlace? Actualmente estoy utilizando Ward, pero ¿cómo sé si debería estar utilizando single, complete, average, etc?

Soy muy nuevo en este tema, pero no puedo encontrar una respuesta clara en línea, ya que no estoy seguro de que haya una. Entonces, ¿qué podría ser una buena idea para mi aplicación? Ten en cuenta que los datos son relativamente dispersos en el sentido de que la matriz n x m tiene muchos ceros (la mayoría de las personas no comentan en más que unos pocos mensajes).

Answer 1

Resumen de los métodos

Breve referencia sobre algunos métodos de vinculación de análisis aglomerativo jerárquico de conglomerados (HAC).

La versión básica del algoritmo HAC es una genérica; consiste en actualizar, en cada paso, mediante la fórmula conocida como fórmula de Lance-Williams, las proximidades entre el cluster emergente (fusionado de dos) y todos los demás clusters (incluyendo los objetos singleton) existentes hasta el momento. Existen implementaciones que no utilizan la fórmula de Lance-Williams. Pero usarla es conveniente: permite codificar varios métodos de vinculación 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 establecen de forma diferente y así la fórmula desenvuelta obtiene una vista específica. Muchos textos sobre HAC muestran la fórmula, sus vistas específicas y explican los métodos. Yo 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 clústeres o entre un clúster y un objeto único podría formularse de muchas formas distintas. HAC fusiona en cada paso los dos clusters o puntos más cercanos, pero el problema que hay que formular es cómo calcular la mencionada proximidad cuando la matriz de proximidad de entrada está definida sólo entre objetos únicos.

Así pues, los métodos difieren en cuanto a la forma de definir la proximidad entre dos conglomerados cualesquiera en cada paso. El "coeficiente de coligación" (que aparece en el programa/historial de aglomeración y que forma el eje "Y" en un dendrograma) es simplemente la proximidad entre los dos clusters fusionados en un paso determinado.

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

• Método de completa vinculación o vecino más lejano . La proximidad entre dos cúmulos es la proximidad entre sus dos objetos más distantes más distantes. Este valor es uno de los valores de la matriz de entrada. La metáfora de esta construcción de cluster es círculo (en el sentido, por afición o trama) donde dos miembros más distantes entre sí no pueden ser mucho más disímiles que otros pares bastante disímiles (como en el círculo). Tales agrupaciones son contornos "compactos" por sus bordes, pero no son necesariamente compactos por dentro.

• Método de media entre grupos enlace (UPGMA). La proximidad entre dos clusters es la media aritmética de todas las proximidades entre los objetos de uno, por un lado, y los objetos del otro, en el otro lado. La metáfora de esta construcción de cluster es bastante genérica, simplemente unida clase o colectivo unido; y el método se establece con frecuencia como el predeterminado en los paquetes de agrupación jerárquica. Se pueden producir clústeres de formas y contornos diversos.

• Media simple o método de media equilibrada entre grupos (WPGMA) es el anterior modificado. La proximidad entre dos clusters es la media aritmética de todas las proximidades entre los objetos de uno, por un lado, y los objetos del otro, en el otro lado; mientras que los subclústeres de los que cada uno de estos dos clústeres se fusionó recientemente tienen una influencia igualada en esa proximidad - incluso si los subclústeres difieran en el número de objetos.

• Método de media del grupo de enlace (MNDIS). La proximidad entre dos clusters es la media aritmética de todas las proximidades en su clústeres conjuntos. Este método es una alternativa a UPGMA. Por lo general, perderá frente a él en términos de densidad de clústeres, pero a veces descubrirá formas de clústeres que el UPGMA no puede.

• Centroide (UPGMC). La proximidad entre dos clusters es la proximidad entre sus centros geométricos: [al cuadrado] euclidiano entre ellos. La metáfora de esta construcción de cluster es proximidad de las plataformas (política). Al igual que en los partidos políticos, estas agrupaciones pueden tener fracciones o "facciones", pero a menos que sus figuras centrales estén separadas entre sí, la unión es consistente. Las agrupaciones pueden ser varias por su contorno.

• Mediana o centroide de equilibrio (WPGMC) es el anterior modificado. La proximidad entre dos clusters es la proximidad entre sus centros geométricos centroides (distancia euclidiana [al cuadrado] entre ellos); mientras que los centroides se definen de forma que los subclústeres de los que cada uno de estos dos clústeres se han fusionado recientemente tienen una influencia igualada en su centroide - incluso si los subclústeres difieren en el número de objetos. El nombre "mediana" es en parte engañoso porque el método no utiliza las medianas de las distribuciones de datos, sino que sigue basándose en los centroides (las medias).

• Ward's método, o mínimo aumento de la suma de los cuadrados (MISSQ), a veces llamado incorrectamente método de "varianza mínima". La proximidad entre dos clusters es la magnitud por la que el cuadrado sumado en su conglomerado conjunto será mayor que el cuadrado sumado combinado en estos dos clusters: $SS_{12}-(SS_1+SS_2)$ . (Entre dos objetos singleton esta cantidad = distancia euclidiana al cuadrado / $2$ .) La metáfora de esta agrupación construida es tipo . 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 pueden estar dispersos con relativa libertad.

Algunos entre los métodos menos conocidos (véase Podany J. New combinatorial clustering methods // Vegetatio, 1989, 81: 61-77.) [también implementado por mí como una macro de SPSS que se encuentra en mi página web]:

• Método del mínimo suma de cuadrados (MNSSQ). La proximidad entre dos clusters es el cuadrado sumado en su cluster conjunto: $SS_{12}$ . (Entre dos objetos únicos esta cantidad = distancia euclidiana al cuadrado / $2$ .)

• Método del mínimo aumento de la varianza (MIVAR). La proximidad entre dos clusters es la magnitud por la que el cuadrado medio en su cluster conjunto conjunto será mayor que el cuadrado medio ponderado (por el número de de objetos) del cuadrado medio en estos dos clústeres: $MS_{12}-(n_1MS_1+n_2MS_2)/(n_1+n_2) = [SS_{12}-(SS_1+SS_2)]/(n_1+n_2)$ . (Entre dos objetos únicos esta cantidad = distancia euclidiana al cuadrado / $4$ .)

• Método del mínimo desviación (MNVAR). La proximidad entre dos clusters es el cuadrado medio en su cluster conjunto: $MS_{12} = SS_{12}/(n_1+n_2)$ . (Entre dos objetos únicos esta cantidad = distancia euclidiana al cuadrado distancia euclidiana / $4$ .).

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

Los últimos 6 métodos requieren distancias; y totalmente correcto será utilizar sólo distancias euclidianas al cuadrado 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 conjuntamente geométrico métodos de vinculación). En el peor de los casos, podría introducir otros métrica distancias al admitir un análisis más heurístico y menos riguroso. Ahora bien, sobre el "cuadrado". El cálculo de los centroides y las desviaciones de los mismos es más conveniente matemáticamente/programáticamente realizarlo sobre las distancias al cuadrado, por eso los paquetes HAC suelen requerir que se introduzcan y se ajusten para procesar los cuadrados. Sin embargo, existen implementaciones - totalmente equivalentes aunque un poco más lentas - basadas en la entrada de distancias no cuadradas y que requieren de éstas; ver por ejemplo "Sala 2" aplicación del método de Ward. Debe consultar la documentación de su programa de clustering para saber qué distancias -cuadradas o no- espera como entrada a un "método geométrico" para hacerlo bien.

Los métodos MNDIS, MNSSQ y MNVAR requieren otros pasos, además de la actualización de 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 utilizan con más frecuencia en los estudios en los que se espera que los conglomerados sean nubes sólidas más o menos redondas, - son los métodos de vinculación media, el método de vinculación completa y el método de Ward.

El método de Ward es el más cercano, por sus propiedades y eficiencia, al clustering de K-means; comparten la misma función objetivo: minimización del SS agrupado dentro del cluster "al final". Por supuesto, K-means (al ser iterativo y si se le proporcionan centros iniciales decentes) suele minimizarla mejor que Ward. Sin embargo, Ward me parece un poco más preciso que K-means a la hora de descubrir clusters de tamaños físicos desiguales (varianzas) o clusters lanzados por el espacio de forma muy irregular. El método MIVAR me resulta extraño, no puedo imaginar cuándo podría ser recomendable, no produce clusters suficientemente densos.

Métodos centroide, mediana, aumento mínimo de la varianza - pueden dar a veces el llamado retrocesos : un fenómeno en el que los dos clusters que se fusionan en algún paso parecen estar más cerca el uno del otro que los pares de clusters fusionados anteriormente. Esto se debe a que estos métodos no pertenecen a los llamados ultramétricos. Esta situación es incómoda pero teóricamente está bien.

Los métodos de enlace único y centroide pertenecen al llamado espacio contratación o "encadenamiento". Esto significa -a grandes rasgos- que tienden a unir los objetos uno a uno a los clusters, y por ello demuestran un crecimiento relativamente suave de la curva "% de objetos agrupados". Por el contrario, los métodos de vinculación completa, de Ward, de suma de cuadrados, de aumento de la varianza y de varianza suelen obtener una parte considerable de los objetos agrupados incluso en los primeros pasos, y luego proceden a fusionarlos, por lo que su curva "% de objetos agrupados" es empinada desde los primeros pasos. Estos métodos se denominan espacio dilatando . Otros métodos son intermedios.

Versiones flexibles . Añadiendo el parámetro adicional en la fórmula de Lance-Willians es posible hacer que un método se convierta en algo específicamente autoajustable en sus pasos. El parámetro aporta una corrección para la proximidad entre clusters que se calcula, que depende del tamaño (cantidad de descompactación) de los clusters. El significado del parámetro es que hace que el método de aglomeración dilate o contraiga más el espacio de lo que está condenado a ser el método estándar. La implementación más conocida de la flexibilidad hasta ahora es la de los métodos de enlace promedio 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 el eje "Y" de un dendrograma, normalmente se muestra la proximidad entre los clusters que se fusionan, tal y como se definió en los métodos anteriores. Por lo tanto, por ejemplo, en el método del centroide el al cuadrado La distancia se suele calibrar (en última instancia, depende del paquete y de sus opciones); algunos investigadores no son conscientes de ello. Además, por tradición, con los métodos basados en incrementar de no densidad, como el de Ward, que suele aparecer en el dendrograma es acumulado valor - es antes por razones de conveniencia que teóricas. Por lo tanto, (en muchos paquetes) el coeficiente trazado en el método de Ward representa la suma de cuadrados global, en todos los clusters, dentro del cluster observado en el momento de un paso dado. No deje de leer la documentación de su paquete para averiguar en qué forma el programa particular muestra el coeficiente de coligación (distancia de cluster) en su dendrograma.

Uno debe abstenerse de juzgar qué método de vinculación es "mejor" para sus datos comparando el aspecto de los dendrogramas: no sólo porque el aspecto cambia cuando se cambia la modificación del coeficiente que se traza allí - como se acaba de describir, - sino porque el aspecto será diferente incluso en los datos sin clusters.

Para elegir el método "correcto"

No hay solo criterio. Algunas directrices 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 describen en esta respuesta y todo el hilo que contiene.

Answer 2

La correlación entre la matriz de distancia y la distancia cophenetic es una métrica que ayuda a evaluar qué enlace de agrupación 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 métrica de selección de enlace se menciona en la página 38 de este vegan vignette.

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

# Datos
d0=dist(USArrests)

# Agrupación jerárquica aglomerativa
h1=hclust(d0,method='average')
h2=hclust(d0,method='complete')
h3=hclust(d0,method='ward.D')
h4=hclust(d0,method='single')

# Distancias cophenetic, para cada enlace
c1=cophenetic(h1)
c2=cophenetic(h2)
c3=cophenetic(h3)
c4=cophenetic(h4)

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

# Dendogramas
par(mfrow=c(2,2))
plot(h1,main='Enlace Promedio')
plot(h2,main='Enlace Completo')
plot(h3,main='Enlace Ward')
plot(h4,main='Enlace Simple')
par(mfrow=c(1,1))

Vemos que las correlaciones para average y complete son extremadamente similares, y sus dendogramas parecen muy parecidos. La correlación para ward es similar a average y complete pero el dendograma se ve bastante diferente. El enlace single está haciendo lo suyo. El mejor juicio profesional de un experto en la materia, o la precedencia hacia un cierto enlace en el campo de interés, probablemente debería prevalecer sobre la salida numérica de cor().