Agrupamiento jerárquico

En minería de datos y estadística , el agrupamiento jerárquico ^{[ 1 ]} (también llamado análisis de clúster jerárquico o HCA ) es un método de análisis de clúster que busca construir una jerarquía de clústeres. Las estrategias para el agrupamiento jerárquico generalmente se dividen en dos categorías:

• Aglomerativo : El agrupamiento aglomerativo, a menudo denominado enfoque "de abajo hacia arriba", comienza con cada punto de datos como un clúster individual. En cada paso, el algoritmo fusiona los dos clústeres más similares según una métrica de distancia elegida (p. ej., distancia euclidiana ) y un criterio de enlace (p. ej., enlace simple , enlace completo ). ^{[ 2 ]} Este proceso continúa hasta que todos los puntos de datos se combinan en un solo clúster o se cumple un criterio de parada. Los métodos aglomerativos se utilizan con mayor frecuencia debido a su simplicidad y eficiencia computacional para conjuntos de datos pequeños y medianos. ^{[ 3 ]}
• Agrupamiento divisivo : El agrupamiento divisivo, también conocido como enfoque "de arriba hacia abajo", comienza con todos los puntos de datos en un único clúster y lo divide recursivamente en clústeres más pequeños. En cada paso, el algoritmo selecciona un clúster y lo divide en dos o más subconjuntos, a menudo utilizando un criterio como maximizar la distancia entre los clústeres resultantes. Los métodos divisivos son menos comunes, pero pueden ser útiles cuando el objetivo es identificar primero clústeres grandes y distintos.

En general, las fusiones y divisiones se determinan de manera voraz . Los resultados del agrupamiento jerárquico ^{[ 1 ]} se suelen presentar en un dendrograma .

El agrupamiento jerárquico tiene la clara ventaja de que se puede utilizar cualquier medida válida de distancia. De hecho, las observaciones en sí mismas no son necesarias: todo lo que se utiliza es una matriz de distancias . Por otro lado, excepto en el caso especial de la distancia de enlace simple, ninguno de los algoritmos (excepto la búsqueda exhaustiva en${\displaystyle {\mathcal {O}}(2^{n})}$) se puede garantizar que se encontrará la solución óptima.

El algoritmo estándar para la agrupación jerárquica aglomerativa (HAC) tiene una complejidad temporal de${\displaystyle {\mathcal {O}}(n^{3})}$y requiere${\displaystyle \Omega (n^{2})}$memoria, lo que lo hace demasiado lento incluso para conjuntos de datos medianos. Sin embargo, para algunos casos especiales, los métodos aglomerativos eficientes óptimos (de complejidad${\displaystyle {\mathcal {O}}(n^{2})}$) son conocidos: SLINK ^{[ 4 ]} para agrupamiento de enlace simple y CLINK ^{[ 5 ]} para agrupamiento de enlace completo . Con un montón , el tiempo de ejecución del caso general se puede reducir a${\displaystyle {\mathcal {O}}(n^{2}\log n)}$en lugar de${\displaystyle {\mathcal {O}}(n^{3})}$, a costa de aumentar los requisitos de memoria. En muchos casos, la sobrecarga de memoria de este enfoque es demasiado grande para que sea prácticamente utilizable. Existen métodos que utilizan quadtrees que demuestran${\displaystyle {\mathcal {O}}(n^{2})}$tiempo total de ejecución con${\displaystyle {\mathcal {O}}(n)}$espacio. ^{[ 6 ]}

La agrupación divisiva con una búsqueda exhaustiva es${\displaystyle {\mathcal {O}}(2^{n})}$, pero es común utilizar heurísticas más rápidas para elegir divisiones, como k -means .

Si bien el criterio de vinculación determina cómo se calcula la disimilitud entre conjuntos de observaciones, la métrica de distancia subyacente determina cómo se mide la disimilitud entre observaciones individuales. Dado que el agrupamiento jerárquico permite cualquier medida de distancia válida, la elección de la métrica está guiada por la naturaleza de los datos y puede tener un efecto significativo en el agrupamiento resultante. ^{[ 7 ]}

La distancia euclidiana es la métrica más utilizada para datos numéricos continuos. Corresponde a la distancia en línea recta entre dos puntos en el espacio euclidiano y es la opción predeterminada en la mayoría de los programas estadísticos: ^{[ 7 ]}

${\displaystyle d(\mathbf {x} ,\mathbf {y} )={\sqrt {\sum _ {i=1}^{n}(x_{i}-y_{i})^{2}}}}$

La distancia de Manhattan (también llamada distancia de manzana de ciudad o distancia L ₁ ) suma las diferencias absolutas entre las características: ^{[ 7 ]}

${\displaystyle d(\mathbf {x} ,\mathbf {y} )=\sum _ {i=1}^{n}|x_ {i}-y_ {i}|}$

Suele preferirse cuando las características se miden en diferentes escalas o cuando los datos contienen valores atípicos, ya que es menos sensible a las grandes desviaciones que la distancia euclidiana.

La distancia coseno mide la disimilitud angular entre dos vectores distintos de cero: ^{[ 8 ]}

${\displaystyle d(\mathbf {x} ,\mathbf {y} )=1-{\frac {\mathbf {x} \cdot \mathbf {y} }{\lVert \mathbf {x} \rVert \,\lVert \mathbf {y} \rVert }}}$

Debido a que no tiene en cuenta la magnitud del vector, se utiliza con frecuencia en la minería de texto y la agrupación de documentos, donde los documentos se representan como vectores de frecuencia de términos de alta dimensión. ^{[ 8 ]}

La distancia de Mahalanobis tiene en cuenta las correlaciones entre características al incorporar la inversa de la matriz de covarianza de los datos S : ^{[ 9 ]}

${\displaystyle d(\mathbf {x} ,\mathbf {y} )={\sqrt {(\mathbf {x} -\mathbf {y} )^{\top }S^{-1}(\mathbf {x} -\mathbf {y} )}}}$

A diferencia de la distancia euclidiana, es invariante a la escala y resulta útil cuando las características están correlacionadas o se miden en unidades diferentes.

La distancia de Hamming se utiliza para datos categóricos o binarios y cuenta el número de posiciones en las que dos observaciones difieren. Se aplica comúnmente a secuencias genéticas y vectores de características binarias. ^{[ 10 ]}

La elección de la métrica interactúa con la elección del criterio de enlace. Por ejemplo, el método de Ward y los enlaces basados ​​en centroides se definen en términos de distancias euclidianas al cuadrado, mientras que la agrupación de enlace simple y de enlace completo se puede utilizar con cualquier métrica válida. ^{[ 7 ]}

Para decidir qué grupos deben combinarse (para agrupamiento aglomerativo) o dónde debe dividirse un grupo (para agrupamiento divisivo), se requiere una medida de disimilitud entre conjuntos de observaciones. En la mayoría de los métodos de agrupamiento jerárquico, esto se logra mediante el uso de una distancia apropiada d , como la distancia euclidiana, entre observaciones individuales del conjunto de datos, y un criterio de enlace, que especifica la disimilitud de los conjuntos en función de las distancias por pares de las observaciones en los conjuntos. La elección de la métrica, así como del criterio de enlace, puede tener un gran impacto en el resultado del agrupamiento, donde la métrica de nivel inferior determina qué objetos son más similares , mientras que el criterio de enlace influye en la forma de los grupos. Por ejemplo, el enlace completo tiende a producir grupos más esféricos que el enlace simple.

El criterio de vinculación determina la distancia entre conjuntos de observaciones en función de las distancias entre pares de observaciones.

Algunos criterios de enlace comúnmente utilizados entre dos conjuntos de observaciones A y B y una distancia d son: ^{[ 11 ] [ 12 ]}

Algunos de estos solo pueden recalcularse recursivamente (WPGMA, WPGMC); para muchos, un cálculo recursivo con ecuaciones de Lance-Williams es más eficiente, mientras que para otros (Hausdorff, Medoid) las distancias deben calcularse con la fórmula completa, que es más lenta. Otros criterios de enlace incluyen:

• La probabilidad de que los clústeres candidatos se originen a partir de la misma función de distribución (enlace V).
• El producto del grado de entrada y el grado de salida en un grafo de k vecinos más cercanos (enlace de grado del grafo). ^{[ 20 ]}
• El incremento de algún descriptor de clúster (es decir, una cantidad definida para medir la calidad de un clúster) después de fusionar dos clústeres. ^{[ 21 ] [ 22 ] [ 23 ]}

Comparación de métodos de vinculación

La elección del criterio de enlace afecta significativamente la forma y la calidad de los clústeres resultantes. Cada método tiene fortalezas y debilidades distintas según la estructura de los datos. ^{[ 24 ]}

El método de enlace simple (también llamado método del vecino más cercano ) define la distancia entre dos clústeres como la distancia mínima entre cualquier par de puntos, uno de cada clúster. Este método puede detectar y manejar clústeres de forma arbitraria, incluyendo estructuras alargadas y no globulares . Sin embargo, es muy sensible al ruido y a los valores atípicos , ya que un solo par de puntos cercanos es suficiente para fusionar dos clústeres. ^{[ 24 ] [ 25 ]}

El enlace completo define la distancia entre dos grupos como la distancia máxima entre cualquier par de puntos en ambos grupos. Es menos susceptible al ruido y a los valores atípicos que el enlace simple. Sin embargo, el enlace completo tiende a producir grupos globulares de tamaño similar y puede separar incorrectamente grupos grandes o de forma irregular. ^{[ 24 ]}

El enlace promedio (específicamente UPGMA, el método de agrupamiento de pares no ponderados con media aritmética) define la distancia entre dos clústeres como el promedio de todas las distancias por pares entre los puntos de ambos clústeres. Representa un compromiso entre los extremos del enlace simple y el enlace completo. El enlace promedio es más robusto al ruido que el enlace simple, pero, al igual que el enlace completo, tiende a estar sesgado hacia la detección de clústeres globulares. ^{[ 24 ] [ 25 ]}

Complejidad computacional

La implementación ingenua del agrupamiento jerárquico aglomerativo tiene una complejidad temporal de O( n³ ) y una complejidad espacial de O( n² ), donde n es el número de puntos de datos, porque en cada uno de los n − 1 pasos de fusión el algoritmo debe buscar y actualizar una matriz de proximidad de n × n . Para el enlace simple, los algoritmos optimizados basados ​​en árboles de expansión mínima reducen la complejidad temporal a O( n² log n ). Para otros criterios de enlace, el uso de colas de prioridad y cadenas de vecinos más cercanos también puede lograr un tiempo de O( n² log n ) en la práctica.

El enlace de Hausdorff es un criterio de agrupamiento jerárquico basado en la distancia de Hausdorff , una métrica definida entre conjuntos de puntos en un espacio métrico dado. A diferencia de los métodos de enlace estándar que se basan en distancias por pares entre observaciones individuales, el enlace de Hausdorff evalúa las distancias entre clústeres completos, incorporando así información sobre su estructura geométrica. ^{[ 26 ] [ 27 ]}

Formalmente, dejemos${\displaystyle (S,\delta )}$Sea un espacio métrico y dejemos que${\displaystyle A}$y${\displaystyle B}$sean subconjuntos compactos no vacíos de${\displaystyle S}$La distancia desde un punto${\displaystyle a}$a un conjunto${\displaystyle B}$se define como:

${\displaystyle {\tilde {d}}(a,B)=\inf _{b\in B}\delta (a,b)}$

Extendiendo esto a conjuntos, la distancia dirigida desde${\displaystyle A}$a${\displaystyle B}$es:

${\displaystyle {\tilde {d}}(A,B)=\sup _{a\in A}\inf _{b\in B}\delta (a,b)}$

Dado que esta cantidad no es simétrica, la distancia de Hausdorff entre dos conjuntos se define como:

${\displaystyle d_{H}(A,B)=\max\{{\tilde {d}}(A,B),{\tilde {d}}(B,A)\}}$

Esta definición captura la mayor distancia desde un punto en un conjunto hasta el punto más cercano en el otro conjunto. Equivalentemente, puede interpretarse como el radio más pequeño.${\displaystyle r}$de tal manera que cada punto de${\displaystyle A}$se encuentra a poca distancia${\displaystyle r}$de algún punto en${\displaystyle B}$y cada punto de${\displaystyle B}$se encuentra a poca distancia${\displaystyle r}$de algún punto en${\displaystyle A}$En este sentido, la distancia de Hausdorff mide la máxima discrepancia entre dos conjuntos. ^{[ 26 ] [ 27 ]}

En la agrupación jerárquica, el enlace de Hausdorff utiliza${\displaystyle d_{H}(A,B)}$como medida de disimilitud entre clústeres. Inicialmente, cada punto de datos forma su propio clúster, y la distancia de Hausdorff entre conjuntos unitarios se reduce a la métrica original. En cada paso, los dos clústeres con la menor distancia de Hausdorff se fusionan y las distancias se recalculan utilizando la misma definición basada en conjuntos. Este proceso iterativo continúa hasta que todos los puntos pertenecen a un solo clúster, produciendo una estructura jerárquica (dendrograma). ^{[ 26 ] [ 27 ]}

En comparación con otros criterios de vinculación, como la vinculación simple, completa o promedio, la vinculación de Hausdorff opera conjunto a conjunto en lugar de basarse únicamente en distancias entre pares de puntos. Como resultado, captura la geometría global de los clústeres y puede preservar mejor las características estructurales de los datos. Se ha demostrado que proporciona un comportamiento intermedio entre la vinculación simple y la completa, evitando el efecto de encadenamiento de la primera y reduciendo la tendencia de la segunda a sobreestimar las distancias entre clústeres. ^{[ 26 ] [ 27 ]}

Sin embargo, estas ventajas conllevan un mayor coste computacional. El cálculo de la distancia de Hausdorff entre dos clústeres suele requerir la evaluación de las distancias entre todos los pares de puntos de los conjuntos, a menudo mediante un procedimiento de máximo-mínimo sobre una matriz de distancias. Esto hace que el enlace de Hausdorff sea computacionalmente más costoso que criterios de enlace más sencillos, especialmente para conjuntos de datos grandes. ^{[ 26 ] [ 27 ]}

En general, el enlace de Hausdorff proporciona un enfoque de agrupamiento matemáticamente bien fundamentado que es eficaz para distinguir estructuras complejas en los datos. ^{[ 27 ]}

Por ejemplo, supongamos que estos datos se van a agrupar y que la distancia euclidiana es la métrica de distancia .

El dendrograma de agrupamiento jerárquico sería:

Al cortar el árbol a una altura determinada, se obtiene una agrupación por particiones con una precisión seleccionada. En este ejemplo, al cortar después de la segunda fila (desde arriba) del dendrograma , se obtienen los clústeres {a} {bc} {de} {f}. Al cortar después de la tercera fila, se obtienen los clústeres {a} {bc} {def}, lo que representa una agrupación menos precisa, con un menor número de clústeres, pero de mayor tamaño.

Ejemplo animado

El proceso de agrupamiento también se puede ilustrar paso a paso para mostrar cómo se construye el dendrograma a partir de los datos subyacentes.

En esta visualización, cada punto comienza como un clúster independiente. En cada paso, se fusionan los dos clústeres con la menor distancia entre ellos. A la izquierda, las líneas discontinuas indican qué clústeres se combinan, y una lista secuencial de agrupaciones muestra cómo evolucionan los clústeres con el tiempo. A la derecha, el dendrograma se construye simultáneamente, y cada fusión se representa mediante una nueva rama.

La altura de cada fusión en el dendrograma corresponde a la distancia o disimilitud entre los clústeres que se combinan. Las fusiones que ocurren a menor altura representan clústeres más similares, mientras que las fusiones a mayor altura indican una mayor disimilitud. Se utiliza un código de colores para asociar cada paso de fusión en la visualización de datos con su rama correspondiente en el dendrograma.

En el agrupamiento jerárquico, el número de clústeres no se determina automáticamente y debe elegirse analizando el dendrograma. Un enfoque común consiste en "cortar" el dendrograma a una altura determinada, lo que divide los datos en clústeres según el punto de intersección del corte con la estructura de árbol. La elección del nivel de corte tiene un impacto significativo en el agrupamiento resultante.

Una heurística muy utilizada consiste en identificar grandes huecos verticales en el dendrograma, que corresponden a incrementos sustanciales en la distancia entre fusiones sucesivas. Al cortar el dendrograma justo antes de dicho hueco, se pueden generar clústeres que reflejen agrupaciones naturales en los datos. Esto se basa en la observación de que las fusiones que ocurren a distancias mucho mayores suelen combinar clústeres disímiles.

^{[ 29 ]}

En la práctica, la selección del número de clústeres también puede depender del conocimiento del dominio o de los requisitos específicos de la aplicación. Se pueden utilizar medidas cuantitativas, como el coeficiente de silueta, para evaluar la calidad de las diferentes agrupaciones. Dado que la agrupación jerárquica es sensible a la elección de la métrica de distancia y del criterio de enlace, el número óptimo de clústeres puede variar en función de estos factores.

Este método construye la jerarquía a partir de los elementos individuales mediante la fusión progresiva de clústeres. En nuestro ejemplo, tenemos seis elementos: {a}, {b}, {c}, {d}, {e} y {f}. El primer paso consiste en determinar qué elementos fusionar en un clúster. Generalmente, se seleccionan los dos elementos más cercanos, según la distancia elegida.

Opcionalmente, también se puede construir una matriz de distancias en esta etapa, donde el número en la fila i y la columna j representa la distancia entre los elementos i y j . A medida que avanza el agrupamiento, las filas y columnas se fusionan al unirse los clústeres y se actualizan las distancias. Esta es una forma común de implementar este tipo de agrupamiento y tiene la ventaja de almacenar en caché las distancias entre clústeres. En la página sobre agrupamiento de enlace simple se describe un algoritmo de agrupamiento aglomerativo sencillo , que se puede adaptar fácilmente a diferentes tipos de enlace (véase más abajo).

Supongamos que hemos fusionado los dos elementos más cercanos b y c , ahora tenemos los siguientes clústeres { a }, { b , c }, { d }, { e } y { f }, y queremos fusionarlos aún más. Para ello, necesitamos tomar la distancia entre {a} y {bc}, y por lo tanto definir la distancia entre dos clústeres. Normalmente la distancia entre dos clústeres${\displaystyle {\mathcal {A}}}$y${\displaystyle {\mathcal {B}}}$es uno de los siguientes:

• La distancia máxima entre los elementos de cada clúster (también llamada agrupamiento de enlace completo ):

${\displaystyle \max\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• La distancia mínima entre los elementos de cada clúster (también llamada agrupamiento de enlace simple ):

${\displaystyle \min\{\,d(x,y):x\in {\mathcal {A}},\,y\in {\mathcal {B}}\,\}.}$

• La distancia media entre los elementos de cada clúster (también llamada agrupamiento de enlace promedio, utilizado, por ejemplo, en UPGMA ):

${\displaystyle {1 \over {|{\mathcal {A}}|\cdot |{\mathcal {B}}|}}\sum _{x\in {\mathcal {A}}}\sum _{y\in {\mathcal {B}}}d(x,y).}$

• La suma de toda la varianza intraclúster.
• El aumento de la varianza para el clúster que se fusiona ( método de Ward ^{[ 14 ]} )
• La probabilidad de que los clústeres candidatos se originen a partir de la misma función de distribución (enlace V).

En caso de distancias mínimas empatadas, se elige un par al azar, lo que permite generar varios dendrogramas estructuralmente diferentes. Alternativamente, todos los pares empatados pueden unirse simultáneamente, generando un único dendrograma. ^{[ 30 ]}

Siempre se puede decidir detener la agrupación cuando hay un número suficientemente pequeño de clústeres (criterio numérico). Algunos enlaces también pueden garantizar que la aglomeración ocurra a una mayor distancia entre clústeres que la aglomeración anterior, y entonces se puede detener la agrupación cuando los clústeres están demasiado separados para fusionarse (criterio de distancia). Sin embargo, este no es el caso, por ejemplo, del enlace del centroide, donde pueden ocurrir las llamadas reversiones ^{[ 31 ]} (inversiones, desviaciones de la ultrametricidad).

El principio básico del agrupamiento divisivo se publicó como el algoritmo DIANA (DIvisive ANAlysis clustering). ^{[ 32 ]} Inicialmente, todos los datos están en el mismo clúster, y el clúster más grande se divide hasta que cada objeto está separado. Debido a que existe${\displaystyle O(2^{n})}$Para dividir cada grupo, se necesitan heurísticas. DIANA elige el objeto con la máxima disimilitud promedio y luego mueve a este grupo todos los objetos que sean más similares al nuevo grupo que al resto.

De manera informal, DIANA no es tanto un proceso de "división" como de "vaciado": en cada iteración, se elige un clúster existente (por ejemplo, el clúster inicial de todo el conjunto de datos) para formar un nuevo clúster en su interior. Los objetos se mueven progresivamente a este clúster anidado y vacían el clúster existente. Finalmente, lo único que queda dentro de un clúster son los clústeres anidados que se formaron allí, sin que contenga ningún objeto independiente.

Formalmente, DIANA opera siguiendo los siguientes pasos:

1. Dejar${\displaystyle C_{0}=\{1\dots n\}}$ser el conjunto de todos${\displaystyle n}$índices de objetos y${\displaystyle {\mathcal {C}}=\{C_{0}\}}$el conjunto de todos los clústeres formados hasta el momento.
2. Repita lo siguiente hasta que${\displaystyle |{\mathcal {C}}|=n}$:
   1. Encuentra el grupo actual con 2 o más objetos que tenga el diámetro más grande:${\displaystyle C_{*}=\arg \max _{C\in {\mathcal {C}}}\max _{i_{1},i_{2}\in C}\delta (i_{1},i_{2})}$
   2. Encuentra en este grupo el objeto que presente la mayor disimilitud con respecto al resto del grupo:${\displaystyle i^{*}=\arg \max _{i\in C_{*}}{\frac {1}{|C_{*}|-1}}\sum _{j\in C_{*}\setminus \{i\}}\delta (i,j)}$
   3. Estallido${\displaystyle i^{*}}$de su antiguo grupo${\displaystyle C_{*}}$y lo incorporó a un nuevo grupo disidente.${\displaystyle C_{\textrm {new}}=\{i^{*}\}}$.
   4. Mientras${\displaystyle C_{*}}$no está vacío, siga migrando objetos desde${\displaystyle C_{*}}$agregarlos a${\displaystyle C_{\textrm {new}}}$Para elegir qué objetos migrar, no solo considere la disimilitud con${\displaystyle C_{*}}$, pero también ajustar por la disimilitud con el grupo disgregado: sea${\displaystyle i^{*}=\arg \max _{i\in C}D(i)}$donde definimos${\displaystyle D(i)={\frac {1}{|C_{*}|-1}}\sum _{j\in C_{*}\setminus \{i\}}\delta (i,j)-{\frac {1}{|C_{\textrm {new}}|}}\sum _{j\in C_{\textrm {new}}}\delta (i,j)}$, entonces deje de iterar cuando${\displaystyle D(i^{*})<0}$o migrar${\displaystyle i^{*}}$.
   5. Agregar${\displaystyle C_{\textrm {new}}}$a${\displaystyle {\mathcal {C}}}$.

Intuitivamente,${\displaystyle D(i)}$Lo anterior mide la intensidad con la que un objeto desea abandonar su grupo actual, pero esta intensidad disminuye cuando el objeto tampoco encajaría en el grupo disgregado. Es probable que dichos objetos acaben formando su propio grupo disgregado.

El dendrograma de DIANA se puede construir dejando que el grupo fragmentado${\displaystyle C_{\textrm {new}}}$ser un hijo del cúmulo hueco${\displaystyle C_{*}}$cada vez. Esto construye un árbol con${\displaystyle C_{0}}$como su raíz y${\displaystyle n}$agrupaciones únicas de objetos individuales como sus hojas.

El agrupamiento jerárquico aglomerativo estándar es difícil de aplicar a conjuntos de datos muy grandes porque las implementaciones típicas requieren una cantidad sustancial de memoria para las estructuras de pares y pueden escalar mal.${\displaystyle n}$crece (véase § Complejidad más arriba). En biología computacional , las tecnologías de célula única , como la citometría de masas, producen rutinariamente decenas de millones de observaciones de alta dimensión, lo que motiva flujos de trabajo especializados que preservan la resolución biológica sin requerir que cada paso costoso se ejecute en la matriz completa a la vez. ^{[ 38 ]}

Descripción general

HAL-x es un algoritmo de agrupamiento de densidad jerárquica introducido para nubes de puntos grandes y de alta dimensión. En lugar de aglomerar únicamente a partir de un criterio de enlace fijo en una matriz de distancia precalculada , HAL-x construye un conjunto inicial de clústeres "puros" de alta densidad en una incrustación de baja dimensión de un subconjunto submuestreado de los datos, y luego fusiona los clústeres mediante enlace supervisado : entrena clasificadores supervisados ​​en el espacio de características original (sin reducir) para medir con qué fiabilidad se pueden separar dos clústeres propuestos, y utiliza esas puntuaciones de separación para decidir el orden de fusión. El método produce una jerarquía que se puede leer como un árbol de fusiones junto con un modelo predictivo que puede asignar etiquetas a las celdas reservadas o recién recopiladas sin volver a ejecutar todo el proceso de agrupamiento en cada punto durante las iteraciones exploratorias.

En resumen, la implementación publicada procede mediante (i) la normalización y el submuestreo para la reducción de dimensionalidad (comúnmente t-SNE o UMAP), (ii) la estimación de la densidad en el espacio incrustado para obtener clústeres iniciales, (iii) la construcción de un grafo disperso de k vecinos más cercanos entre clústeres con pesos de aristas derivados de la separabilidad basada en clasificadores en coordenadas no reducidas, y (iv) la fusión aglomerativa de las aristas más débiles mientras se conserva la información de precisión validada cruzadamente para que los usuarios puedan obtener múltiples resoluciones de un modelo ajustado. ^{[ 38 ]}

La figura resume el flujo de trabajo de HAL-x: reducción de dimensionalidad para la estimación de densidad, clústeres semilla basados ​​en densidad, un grafo de enlace supervisado entre clústeres y fusiones sucesivas hasta un umbral de generalización elegido.

• Kaufman, L.; Rousseeuw, PJ (1990). Finding Groups in Data: An Introduction to Cluster Analysis (1.ª  ed.). Nueva York: John Wiley. ISBN 0-471-87876-6.
• Hastie, Trevor ; Tibshirani, Robert ; Friedman, Jerome (2009). «14.3.12 Agrupamiento jerárquico» . Elementos del aprendizaje estadístico (2.ª  ed.). Nueva York: Springer. págs. 520-528 . ISBN  978-0-387-84857-0. Archivado del original (PDF) el 10-11-2009 . Consultado el 20-10-2009 .