¿Cómo entender los inconvenientes de la agrupación jerárquica?

¿Alguien puede explicar los pros y los contras de la agrupación jerárquica?

1. ¿El agrupamiento jerárquico tiene los mismos inconvenientes que K significa?
2. ¿Cuáles son las ventajas del agrupamiento jerárquico sobre K?
3. ¿Cuándo debemos usar los medios K sobre el agrupamiento jerárquico y viceversa?

Las respuestas a esta publicación explican los inconvenientes de k significa muy bien. Cómo entender los inconvenientes de K-means

Mientras que significa intenta optimizar un objetivo global (varianza de los grupos) y logra un clúster jerárquico aglomerativo óptimo local que busca encontrar el mejor paso en cada fusión de grupo (algoritmo codicioso) que se realiza exactamente pero que da como resultado una solución potencialmente subóptima .$k$

Uno debe usar la agrupación jerárquica cuando los datos subyacentes tienen una estructura jerárquica (como las correlaciones en los mercados financieros) y desea recuperar la jerarquía. Todavía puede aplicar significa para hacer eso, pero puede terminar con particiones (desde la más gruesa (todos los puntos de datos en un clúster) hasta la más fina (cada punto de datos es un clúster)) que no están anidadas y, por lo tanto, No es una jerarquía adecuada.$k$

Si desea profundizar en las propiedades más finas de la agrupación, es posible que no desee oponerse a la agrupación plana, como significa, a la agrupación jerárquica, como los enlaces simples, promedio y completos. Por ejemplo, todas estas agrupaciones conservan el espacio, es decir, cuando construyes agrupaciones no distorsionas el espacio, mientras que una agrupación jerárquica como Ward no conserva el espacio, es decir, en cada paso de fusión distorsionará el espacio métrico.$k$

Para concluir, los inconvenientes de los algoritmos de agrupamiento jerárquico pueden ser muy diferentes de uno a otro. Algunos pueden compartir propiedades similares a $k$ significa: Ward apunta a optimizar la varianza, pero Single Linkage no. Pero también pueden tener diferentes propiedades: Ward dilata el espacio, mientras que Single Linkage conserva el espacio como $k$ significa.

- edite para precisar las propiedades de conservación y dilatación del espacio

espacio: es decir al fusionar y el algoritmo empujará más lejos el cluster .C i C j C

Escalabilidad

significa que es el claro ganador aquí. O ( n ⋅ k ⋅ d ⋅ i ) es mucho mejor que laescalabilidad O ( n 3 d ) (en algunos casos O ( n 2 d ) ) del agrupamiento jerárquico porque generalmente tanto k como i y d son pequeños (desafortunadamente, i tiende a crecer con n , de modo O ( n ) haceno$k$$O(n\cdot k\cdot d\cdot i)$$O(n^3 d)$$O(n^2 d)$$k$$i$$d$$i$$n$$O(n)$por lo general espera). Además, el consumo de memoria es lineal, en oposición a cuadrático (por lo general, existen casos especiales lineales).

Flexibilidad

significa es extremadamente limitado en aplicabilidad. Se limita esencialmente a las distancias euclidianas (incluidas las euclidianas en los espacios del núcleo y las divergencias de Bregman, pero estas son bastante exóticas y nadie las usa realmente con k- medias). Peor aún, k- significa solo funciona con datos numéricos (que en realidad deberían ser continuos y densos para ser una buenaopciónpara k- medios).$k$$k$$k$$k$

El agrupamiento jerárquico es el claro ganador aquí. Ni siquiera requiere una distancia: se puede usar cualquier medida, incluidas las funciones de similitud, simplemente prefiriendo valores altos a valores bajos. Datos categoriales? seguro solo usa, por ejemplo, Jaccard. ¿Instrumentos de cuerda? Prueba la distancia de Levenshtein. ¿Series de tiempo? seguro. Datos de tipo mixto? Gower distancia. Hay millones de conjuntos de datos en los que puede usar la agrupación jerárquica, pero en los que no puede usar significa.$k$

Modelo

No hay ganador aquí. significa puntajes altos porque produce una gran reducción de datos. Los centroides son fáciles de entender y usar. La agrupación jerárquica, por otro lado, produce un dendrograma. Un dendrograma también puede ser muy útil para comprender su conjunto de datos.$k$

Solo quería agregar un poco a las otras respuestas sobre cómo, en cierto sentido, hay una razón teórica fuerte para preferir ciertos métodos de agrupamiento jerárquico.

Una suposición común en el análisis de conglomerados es que los datos se muestrean a partir de alguna densidad de probabilidad subyacente que no tenemos acceso. Pero supongamos que tenemos acceso a él. ¿Cómo definiríamos los grupos de f ?$f$$f$

Un enfoque muy natural e intuitivo es decir que los grupos de son las regiones de alta densidad. Por ejemplo, considere la siguiente densidad de dos picos:$f$

Al dibujar una línea a través del gráfico, inducimos un conjunto de grupos. Por ejemplo, si dibujamos una línea en , obtenemos los dos grupos que se muestran. Pero si dibujamos la línea en λ 3 , obtenemos un solo grupo.$\lambda_1$$\lambda_3$

Para hacer esto más preciso, supongamos que tenemos un arbitrario . ¿Cuáles son los grupos de f en el nivel λ ? Son el componente conectado del conjunto de supernivel { x : f ( x ) ≥ λ } .$\lambda > 0$$f$$\lambda$$\{x : f(x) \geq \lambda \}$

Ahora, en lugar de elegir una arbitraria , podríamos considerar todas las λ , de modo que el conjunto de grupos "verdaderos" de f son componentes conectados de cualquier conjunto de supernivel de f . La clave es que esta colección de clústeres tiene una estructura jerárquica .$\lambda$ $\lambda$$f$$f$

Déjame hacer eso más preciso. Supongamos que está soportado en X . Ahora dejemos que C 1 sea ​​un componente conectado de { x : f ( x ) ≥ λ 1 } , y C 2 sea ​​un componente conectado de { x : f ( x ) ≥ λ 2 } . En otras palabras, C 1 es un grupo en el nivel λ 1 , y C 2 es un grupo en el nivel λ 2 . Entonces sí$f$$\mathcal X$$C_1$$\{ x : f(x) \geq \lambda_1 \}$$C_2$$\{ x : f(x) \geq \lambda_2 \}$$C_1$$\lambda_1$$C_2$$\lambda_2$ , entonces C 1 ⊂ C 2 o C 1 ∩ C 2 = ∅ . Esta relación de anidamiento es válida para cualquier par de clústeres en nuestra colección, por lo que lo que tenemos es unajerarquíade clústeres. Llamamos a esto elárbol de clúster.$\lambda_2 < \lambda_1$$C_1 \subset C_2$$C_1 \cap C_2 = \emptyset$

Así que ahora tengo algunos datos muestreados de una densidad. ¿Puedo agrupar estos datos de una manera que recupere el árbol del clúster? En particular, nos gustaría que un método sea consistente en el sentido de que a medida que recopilamos más y más datos, nuestra estimación empírica del árbol de clúster se acerca cada vez más al árbol de clúster verdadero.

Hartigan fue el primero en hacer tales preguntas, y al hacerlo definió con precisión lo que significaría para un método de agrupamiento jerárquico para estimar consistentemente el árbol de clúster. Su definición fue la siguiente: que y B sean verdaderos grupos disjuntos de f como se definió anteriormente, es decir, son componentes conectados de algunos conjuntos de supernivel. Ahora dibuje un conjunto de n muestras iid de f , y llame a este conjunto X n . Aplicamos un método de agrupación jerárquica a los datos X n , y recuperamos una colección de agrupaciones empíricas . Que A n sea ​​el más pequeño$A$$B$$f$$n$$f$$X_n$$X_n$$A_n$grupo empírico que contiene todo , y sea B n el más pequeño que contenga todo B ∩ X n . Entonces se dice nuestro método de agrupación para ser Hartigan consistente si Pr ( A n ∩ B n ) = ∅ → 1 como n → ∞ para cualquier par de grupos disjuntos A y B .$A \cap X_n$$B_n$$B \cap X_n$$\Pr(A_n \cap B_n) = \emptyset \to 1$$n \to \infty$$A$$B$

Esencialmente, la consistencia de Hartigan dice que nuestro método de agrupamiento debería separar adecuadamente las regiones de alta densidad. Hartigan investigó si sola vinculación agrupación podría ser consistentes, y se encontró que es no constante en las dimensiones> 1. La problema de encontrar un método general y consistente para estimar el árbol de racimo fue abierta hasta hace unos pocos años, cuando se introdujeron Chaudhuri y Dasgupta enlace único robusto , que es demostrablemente consistente. Sugeriría leer sobre su método, ya que es bastante elegante, en mi opinión.

Por lo tanto, para responder a sus preguntas, hay un sentido en el que el grupo jerárquico es lo "correcto" al intentar recuperar la estructura de una densidad. Sin embargo, tenga en cuenta las comillas de miedo alrededor de "correcto" ... En última instancia, los métodos de agrupación basados ​​en la densidad tienden a funcionar mal en las dimensiones altas debido a la maldición de la dimensionalidad, y por lo tanto, aunque una definición de agrupación basada en grupos sea regiones de alta probabilidad es bastante limpio e intuitivo, a menudo se ignora a favor de los métodos que funcionan mejor en la práctica. Eso no quiere decir que un enlace único robusto no sea práctico: en realidad funciona bastante bien en problemas en dimensiones más bajas.

Por último, diré que la consistencia de Hartigan no está de acuerdo con nuestra intuición de convergencia. El problema es que la consistencia de Hartigan permite que un método de agrupamiento sobre-segmente en gran medida los clústeres de manera que un algoritmo pueda ser coherente con Hartigan, pero produzca agrupaciones que son muy diferentes al verdadero árbol de clústeres. Hemos producido trabajo este año sobre una noción alternativa de convergencia que aborda estos problemas. El trabajo apareció en "Más allá de la coherencia de Hartigan: métrica de distorsión de fusión para agrupamiento jerárquico" en COLT 2015.

Una ventaja práctica adicional en el agrupamiento jerárquico es la posibilidad de visualizar resultados usando el dendrograma. Si no sabe de antemano qué número de grupos está buscando (como suele ser el caso ...), puede que el diagrama de dendrograma pueda ayudarlo a elegir$k$sin necesidad de crear agrupaciones separadas. Dedrogram también puede brindar una gran visión de la estructura de datos, ayudar a identificar valores atípicos, etc. La agrupación jerárquica también es determinista, mientras que k-means con inicialización aleatoria puede brindarle resultados diferentes cuando se ejecuta varias veces en los mismos datos. En k-means, también puede elegir diferentes métodos para actualizar los medios de clúster (aunque el enfoque de Hartigan-Wong es, con mucho, el más común), que no es un problema con el método jerárquico.

EDITAR gracias a ttnphns: una característica que el clúster jerárquico comparte con muchos otros algoritmos es la necesidad de elegir una medida de distancia. Esto a menudo depende en gran medida de la aplicación y los objetivos particulares. Esto podría verse como una complicación adicional (otro parámetro para seleccionar ...), pero también como un activo: más posibilidades. Por el contrario, el algoritmo clásico de K-medias utiliza específicamente la distancia euclidiana.