Algoritmo de agrupación de dosel

El algoritmo de agrupamiento de dosel es un algoritmo de preagrupamiento no supervisado introducido por Andrew McCallum , Kamal Nigam y Lyle Ungar en 2000. ^[1] A menudo se utiliza como paso de preprocesamiento para el algoritmo K-means o el algoritmo de agrupamiento jerárquico . Su objetivo es acelerar las operaciones de agrupamiento en grandes conjuntos de datos , donde usar otro algoritmo directamente puede resultar poco práctico debido al tamaño del conjunto de datos.

Descripción

El algoritmo procede de la siguiente manera, utilizando dos umbrales (la distancia suelta) y (la distancia corta), donde . ^{[1] [2]} ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}>T_{2}}$

1. Comience con el conjunto de puntos de datos que se agruparán.
2. Elimina un punto del conjunto, comenzando un nuevo 'dosel' que contenga este punto.
3. Para cada punto que quede en el conjunto, asígnelo a la nueva cubierta si su distancia al primer punto de la cubierta es menor que la distancia suelta . ${\displaystyle T_{1}}$
4. Si la distancia del punto es además menor que la distancia estrecha , retírela del conjunto original. ${\displaystyle T_{2}}$
5. Repita desde el paso 2 hasta que no haya más puntos de datos en el conjunto para agrupar.
6. Estas marquesinas agrupadas relativamente económicas se pueden subagrupar utilizando un algoritmo más caro pero preciso.

Una nota importante es que los puntos de datos individuales pueden ser parte de varias marquesinas. Como aceleración adicional, se puede usar una métrica de distancia rápida y aproximada para el paso 3, mientras que para el paso 4 se puede usar una métrica de distancia más precisa y lenta.

Aplicabilidad

Dado que el algoritmo utiliza funciones de distancia y requiere la especificación de umbrales de distancia, su aplicabilidad para datos de alta dimensión está limitada por la maldición de la dimensionalidad . Sólo cuando esté disponible una función de distancia barata y aproximativa (de baja dimensión), las marquesinas producidas conservarán los grupos producidos por K-means.

Sus beneficios incluyen:

• Se reduce el número de instancias de datos de entrenamiento que deben compararse en cada paso.
• Existe cierta evidencia de que los grupos resultantes mejoran. ^[3]

Referencias

1. McCallum, A.; Nigam, K.; y Ungar LH (2000) "Efficient Clustering of High Dimensional Data Sets with Application to Reference Matching", Actas de la sexta conferencia internacional ACM SIGKDD sobre descubrimiento de conocimientos y minería de datos, 169-178 doi :10.1145/347090.347123
2. "El algoritmo de marquesinas". cursos.cs.washington.edu . Consultado el 6 de septiembre de 2014 .
3. Descripción de Mahout de Canopy-Clustering Consultado el 2 de julio de 2022.