¿Puede alguien explicar los pros y los contras de la agrupación jerárquica?
Las respuestas a este post explican muy bien los inconvenientes de los medios k. Cómo entender los inconvenientes de K-means
Mientras que $k$ -means trata de optimizar un objetivo global (varianza de los clusters) y alcanza un óptimo local, el clustering jerárquico aglomerativo tiene como objetivo encontrar el mejor paso en cada fusión de clusters (algoritmo greedy) que se realiza de forma exacta pero dando como resultado una solución potencialmente subóptima.
Se debe utilizar la agrupación jerárquica cuando los datos subyacentes tienen una estructura jerárquica (como las correlaciones en los mercados financieros) y se quiere recuperar la jerarquía. También se puede aplicar $k$ -para hacerlo, 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 tanto, no constituyen una jerarquía adecuada.
Si quiere profundizar en las propiedades más finas de la agrupación, es posible que no quiera oponerse a la agrupación plana como $k$ -significa a la agrupación jerárquica, como los enlaces simples, medios y completos. Por ejemplo, todos estos clústeres conservan el espacio, es decir, cuando se construyen clústeres no se distorsiona el espacio, mientras que un clúster jerárquico como el de Ward no conserva el espacio, es decir, en cada paso de fusión distorsionará el espacio métrico.
En conclusión, los inconvenientes de los algoritmos de clustering jerárquico pueden ser muy diferentes entre sí. Algunos pueden compartir propiedades similares a $k$ -significa: Ward busca optimizar la varianza, pero Single Linkage no. Pero también pueden tener propiedades diferentes: Ward dilata el espacio, mientras que Single Linkage conserva el espacio como $k$ -significa.
-- editar para precisar las propiedades de conservación y dilatación del espacio
Conservación del espacio: $$D_{ij} \in \left[ \min_{x \in C_i, y \in C_j} d(x,y), \max_{x \in C_i, y \in C_j} d(x,y) \right]$$ donde $D_{ij}$ es la distancia entre clusters $C_i$ y $C_j$ que desea fusionar, y $d$ es la distancia entre puntos de datos.
Dilatación del espacio: $$D(C_i \cup C_j, C_k) \geq \max(D_{ik}, D_{jk}),$$ es decir, fusionando $C_i$ y $C_j$ el algoritmo alejará más el clúster $C_k$ .
$k$ significa es el claro ganador aquí. $O(n\cdot k\cdot d\cdot i)$ es mucho mejor que el $O(n^3 d)$ (en algunos casos $O(n^2 d)$ ) la escalabilidad de la agrupación jerárquica porque normalmente tanto $k$ y $i$ y $d$ son pequeños (por desgracia, $i$ tiende a crecer con $n$ Así que $O(n)$ hace no normalmente). Además, el consumo de memoria es lineal, en lugar de cuadrático (normalmente, existen casos especiales lineales).
$k$ -significa que su aplicabilidad es muy limitada. Se limita esencialmente a las distancias euclidianas (incluidas las euclidianas en los espacios del núcleo, y las divergencias de Bregman, pero éstas son bastante exóticas y nadie las utiliza realmente con $k$ -medios). Aún peor, $k$ -las medias sólo funcionan con datos numéricos (que en realidad deberían ser continuos y densos para ser un buen ajuste para $k$ -medios).
La agrupación jerárquica es la clara ganadora aquí. Ni siquiera requiere una distancia: se puede utilizar cualquier medida, incluidas las funciones de similitud, simplemente prefiriendo los valores altos a los bajos. ¿Datos categoriales? Claro, sólo hay que utilizar, por ejemplo, Jaccard. ¿Cadenas? Pruebe con la distancia Levenshtein. ¿Series temporales? Seguro. ¿Datos de tipo mixto? Distancia de Gower. Hay millones de conjuntos de datos en los que se puede utilizar la agrupación jerárquica, pero en los que no se puede utilizar $k$ -significa.
No hay ganador aquí. $k$ -La media tiene una puntuación alta porque produce una gran reducción de datos. Los centroides son fáciles de entender y utilizar. La agrupación jerárquica, por otra parte, produce un dendrograma. Un dendrograma también puede ser muy útil para entender su conjunto de datos.
Sólo quería añadir a las otras respuestas un poco sobre cómo, en cierto sentido, hay una fuerte razón teórica para preferir ciertos métodos de agrupación jerárquica.
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 $f$ al que no tenemos acceso. Pero supongamos que tenemos acceso a ella. ¿Cómo definiríamos el racimos de $f$ ?
Un enfoque muy natural e intuitivo es decir que los grupos de $f$ son las regiones de alta densidad. Por ejemplo, considere la densidad de dos picos de abajo:
Al trazar una línea a través del gráfico, inducimos un conjunto de clusters. Por ejemplo, si dibujamos una línea en $\lambda_1$ obtenemos los dos clusters mostrados. Pero si trazamos la línea en $\lambda_3$ , obtenemos un único clúster.
Para hacer esto más preciso, supongamos que tenemos un $\lambda > 0$ . ¿Cuáles son los grupos de $f$ en el nivel $\lambda$ ? Son el componente conectado del conjunto de superniveles $\{x : f(x) \geq \lambda \}$ .
Ahora, en lugar de elegir un $\lambda$ podríamos considerar todo $\lambda$ , tal que el conjunto de agrupaciones "verdaderas" de $f$ son todos los componentes conectados de cualquier conjunto de superniveles de $f$ . La clave es que esta colección de racimos tiene jerárquico estructura.
Permítanme ser más preciso. Supongamos que $f$ es compatible con $\mathcal X$ . Ahora dejemos que $C_1$ sea un componente conexo de $\{ x : f(x) \geq \lambda_1 \}$ y $C_2$ sea un componente conexo de $\{ x : f(x) \geq \lambda_2 \}$ . En otras palabras, $C_1$ es un cluster en el nivel $\lambda_1$ y $C_2$ es un cluster en el nivel $\lambda_2$ . Entonces, si $\lambda_2 < \lambda_1$ Entonces, o bien $C_1 \subset C_2$ o $C_1 \cap C_2 = \emptyset$ . Esta relación de anidamiento es válida para cualquier par de clusters de nuestra colección, por lo que lo que tenemos es de hecho un jerarquía de grupos. A esto lo llamamos árbol de racimos .
Así que ahora tengo algunos datos muestreados de una densidad. ¿Puedo agrupar estos datos de forma que se recupere el árbol de conglomerados? En particular, nos gustaría que un método consistente en el sentido de que, a medida que reunimos más y más datos, nuestra estimación empírica del árbol de conglomerados se acerca cada vez más al verdadero árbol de conglomerados.
Hartigan fue el primero en plantear estas cuestiones, y al hacerlo definió con precisión lo que significaría que un método de agrupación jerárquica estimara de forma coherente el árbol de conglomerados. Su definición fue la siguiente: Sea $A$ y $B$ ser verdad disyuntiva grupos 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 llamamos a este conjunto $X_n$ . Aplicamos un método de agrupación jerárquica a los datos $X_n$ y obtenemos una colección de empírico racimos. Sea $A_n$ sea el El más pequeño clúster empírico que contiene todos los $A \cap X_n$ y que $B_n$ sea el más pequeño que contenga todos los $B \cap X_n$ . Entonces se dice que nuestro método de clustering es Hartigan es consistente si $\Pr(A_n \cap B_n) = \emptyset \to 1$ como $n \to \infty$ para cualquier par de conglomerados disjuntos $A$ y $B$ .
Esencialmente, la consistencia de Hartigan dice que nuestro método de agrupación debería separar adecuadamente las regiones de alta densidad. Hartigan investigó si la agrupación de enlace único podría ser consistente, y encontró que es no consistente en dimensiones > 1. El problema de encontrar un método general y consistente para estimar el árbol de conglomerados estaba abierto hasta hace pocos años, cuando Chaudhuri y Dasgupta introdujeron robusto enlace único , lo cual es demostrablemente consistente. Le sugiero que lea su método, ya que es bastante elegante, en mi opinión.
Así que, para responder a sus preguntas, hay un sentido en el que la agrupación jerárquica es lo "correcto" cuando se intenta recuperar la estructura de una densidad. Sin embargo, fíjate en las comillas que rodean a "correcto"... En última instancia, los métodos de clustering basados en la densidad tienden a funcionar mal en dimensiones altas debido a la maldición de la dimensionalidad, y así, aunque una definición de clustering basada en que los clusters son regiones de alta probabilidad es bastante limpia e intuitiva, a menudo se ignora en favor de métodos que funcionan mejor en la práctica. Esto no quiere decir que la vinculación única robusta no sea práctica: de hecho, funciona bastante bien en problemas de dimensiones inferiores.
Por último, diré que la consistencia de Hartigan no concuerda en cierto modo con nuestra intuición de convergencia. El problema es que la consistencia de Hartigan permite que un método de agrupación sobre-segmento clústeres, de manera que un algoritmo puede ser consistente con Hartigan, y sin embargo producir clústeres que son muy diferentes del verdadero árbol de clústeres. Este año hemos elaborado un trabajo sobre una noción alternativa de convergencia que aborda estas cuestiones. El trabajo apareció en "Beyond Hartigan Consistency: Merge distortion metric for hierarchical clustering" en COLT 2015.
Una ventaja práctica adicional de la agrupación jerárquica es la posibilidad de visualizar los resultados mediante un dendrograma. Si no sabe de antemano qué número de conglomerados busca (como suele ser el caso...), el gráfico de dendrograma puede ayudarle a elegir $k$ sin necesidad de crear agrupaciones separadas. El dedrograma también puede dar una gran visión de la estructura de los datos, ayudar a identificar los valores atípicos, etc. La agrupación jerárquica también es determinista, mientras que k-means con inicialización aleatoria puede dar resultados diferentes cuando se ejecuta varias veces en los mismos datos. En k-means, también se pueden elegir diferentes métodos para actualizar las medias de los clusters (aunque el enfoque de Hartigan-Wong es, con mucho, el más común), lo que no es un problema con el método jerárquico.
EDIT gracias a ttnphns: Una característica que la agrupación jerárquica comparte con muchos otros algoritmos es la necesidad de elegir una medida de distancia. Esto suele depender en gran medida de la aplicación y los objetivos particulares. Esto puede verse como una complicación adicional (otro parámetro a seleccionar...), pero también como una ventaja: más posibilidades. Por el contrario, el algoritmo clásico K-means utiliza específicamente la distancia euclidiana.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
