Descripción general del análisis de agrupamiento jerárquico
Antes de seguir adelante y comprender el análisis de agrupamiento jerárquico, primero intentemos comprender qué es un cluster. ¿Y qué es el análisis de conglomerados? Un clúster es una colección de objetos de datos; Los puntos de datos dentro de un grupo son más similares entre sí y diferentes a los puntos de datos en el otro grupo. El análisis de conglomerados es básicamente una agrupación de estos puntos de datos en el conglomerado. La agrupación es un tipo de algoritmo de aprendizaje automático no supervisado, en el que no hay conjuntos de datos etiquetados de entrenamiento. Existen varios tipos de análisis de agrupación, uno de estos tipos es la agrupación jerárquica.
La agrupación jerárquica ayudará a crear agrupaciones en un orden / jerarquía adecuados. Ejemplo: el ejemplo cotidiano más común que vemos es cómo ordenamos nuestros archivos y carpetas en nuestra computadora por la jerarquía adecuada.
Tipos de agrupamiento jerárquico
La agrupación jerárquica se clasifica además en dos tipos, es decir, agrupación aglomerativa y agrupación divisiva (DIANA)
Agrupamiento aglomerativo
En este caso de agrupamiento, la descomposición jerárquica se realiza con la ayuda de una estrategia de abajo hacia arriba donde comienza creando grupos atómicos (pequeños) agregando un objeto de datos a la vez y luego los fusiona para formar un gran grupo al final, donde este clúster cumple todas las condiciones de terminación. Este procedimiento es iterativo hasta que todos los puntos de datos se agrupan en un solo clúster grande.
AGNES (AGLomerative NESting) es un tipo de agrupamiento aglomerativo que combina los objetos de datos en un clúster basado en la similitud. El resultado de este algoritmo es un árbol estructurado llamado Dendrogram. Aquí utiliza las métricas de distancia para decidir qué puntos de datos deben combinarse con qué clúster. Básicamente, construye una matriz de distancia y comprueba el par de grupos con la distancia más pequeña y los combina.
La figura anterior muestra el agrupamiento aglomerativo versus divisivo
Según cómo se mide la distancia entre cada grupo, podemos tener 3 métodos diferentes
- Enlace único : donde la distancia más corta entre los dos puntos en cada grupo se define como la distancia entre los grupos.
- Enlace completo : en este caso, consideraremos la distancia más larga entre los puntos en cada grupo como la distancia entre los grupos.
- Enlace promedio: Aquí tomaremos el promedio entre cada punto en un grupo a cualquier otro punto en el otro grupo.
Ahora discutamos sobre las fortalezas y debilidades en AGNES; este algoritmo tiene una complejidad temporal de al menos O (n 2 ), por lo tanto, no funciona bien en el escalado, y otro inconveniente importante es que lo que se haya hecho nunca se puede deshacer, es decir, si agrupamos incorrectamente cualquier grupo en una etapa anterior el algoritmo entonces no podremos cambiar el resultado / modificarlo. Pero este algoritmo también tiene un lado positivo, ya que se forman muchos grupos más pequeños, puede ser útil en el proceso de descubrimiento y produce un orden de los objetos que es muy útil en la visualización.
Agrupación divisiva (DIANA)
Diana básicamente significa Análisis Divisivo; Este es otro tipo de agrupamiento jerárquico donde básicamente funciona según el principio del enfoque de arriba hacia abajo (inverso de AGNES) donde el algoritmo comienza formando un gran grupo y divide recursivamente el grupo más diferente en dos y continúa hasta que nosotros ' Todos los puntos de datos similares pertenecen a sus respectivos grupos. Estos algoritmos divisivos resultan en jerarquías altamente precisas que el enfoque aglomerativo, pero son computacionalmente caros.
La figura anterior muestra el proceso de agrupamiento divisivo paso a paso.
Agrupación jerárquica multifase
Para mejorar la calidad de los grupos generados por las técnicas de agrupación jerárquica mencionadas anteriormente, integramos nuestras técnicas de agrupación jerárquica con otras técnicas de agrupación; Esto se llama agrupación multifásica. Los diferentes tipos de agrupamiento multifásico son los siguientes:
- BIRCH (Reducción iterativa equilibrada y agrupamiento mediante jerarquías)
- ROCK (RObust Clustering usando enlaces)
- CAMALEÓN
1. Reducción iterativa equilibrada y agrupamiento mediante jerarquías
Este método se utiliza principalmente para agrupar una gran cantidad de datos numéricos al integrar nuestro agrupamiento jerárquico / micro en la fase inicial y el agrupamiento macro / partición iterativa en la fase posterior. Este método ayuda a superar el problema de escalabilidad que enfrentamos en AGNES y la incapacidad de deshacer lo que se hizo antes del paso. BIRCH usa dos conceptos importantes en su algoritmo
a. Función de agrupación (ayuda a resumir la agrupación)
CF se define como (n- número de puntos de datos en el grupo, la suma lineal de n puntos, la suma cuadrada de n puntos). Almacenar la característica de un clúster de esta manera ayuda a evitar el almacenamiento de información detallada sobre él y la CF es de naturaleza aditiva para diferentes clústeres.
CF 1 + CF 2 =
si. Árbol de características de agrupación (ayuda a representar un cluster como una jerarquía)
El árbol CF es un árbol equilibrado con factor de ramificación B (número máximo de hijos) y umbral T (número máximo de subgrupos que pueden almacenarse en nodos de hoja).
El algoritmo básicamente funciona en 2 fases; en la fase 1 escanea la base de datos y construye un árbol CF en memoria y en la fase 2 usa el algoritmo de agrupamiento que ayuda a agrupar los nodos de la hoja eliminando los valores atípicos (grupos dispersos) y agrupa el grupo con la máxima densidad. El único inconveniente de este algoritmo es que maneja solo el tipo de datos numéricos.
2. Agrupación robusta usando enlaces
Enlace se define como el número de vecinos comunes entre dos objetos. El algoritmo ROCK es un tipo de algoritmo de agrupación que utiliza este concepto de enlace con el conjunto de datos categórico. Como sabemos que los algoritmos de agrupación de distancia medida no proporcionan agrupaciones de alta calidad para el conjunto de datos categórico, pero en el caso de ROCK, también considera las vecindades de los puntos de datos, es decir, si dos puntos de datos tienen la misma vecindad, entonces son es más probable que pertenezca al mismo grupo. El algoritmo construirá un gráfico disperso en el primer paso teniendo en cuenta la matriz de similitud con el concepto de vecindad y umbral de similitud. En el segundo paso, utiliza la técnica de agrupamiento jerárquico aglomerativo en el gráfico disperso.
3. Camaleón
Este tipo de algoritmo de agrupamiento jerárquico utiliza el concepto de modelado dinámico. ¿Se pregunta por qué se llama dinámico? Se llama dinámico porque tiene la capacidad de adaptarse automáticamente a las características internas del clúster al evaluar la similitud del clúster, es decir, qué tan bien conectados están los puntos de datos dentro de un clúster y en la proximidad de los clústeres. Uno de los inconvenientes del camaleón es que el costo de procesamiento es demasiado alto (O (n 2 ) para n objetos es la peor complejidad de tiempo).
Fuente de imagen - Google
Conclusión
En este artículo, hemos aprendido qué es un clúster y qué es el análisis de clúster, diferentes tipos de técnicas de agrupamiento jerárquico, sus ventajas y desventajas. Cada una de las técnicas que discutimos tiene su propio más y menos, por lo tanto, antes de seguir adelante con un algoritmo, debemos comprender nuestros datos con un análisis exploratorio de datos adecuado y elegir el algoritmo con precaución.
Artículos recomendados
Esta es una guía para el Análisis de agrupamiento jerárquico. Aquí discutimos la descripción general, el agrupamiento aglomerativo, el agrupamiento divisivo (DIANA) y el agrupamiento jerárquico multifásico. También puede consultar los siguientes artículos para obtener más información.
- Agrupación jerárquica en R
- Algoritmo de agrupamiento
- racimos
- Métodos de agrupamiento
- Agrupación en Machine Learning
- Agrupación jerárquica | Agrupamiento Aglomerativo y Divisivo