Algoritmo de agrupamiento 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 . Está destinado a acelerar las operaciones de agrupamiento en grandes conjuntos de datos , donde el uso directo de otro algoritmo 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 ajustada), 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 van a agrupar.
2. Eliminar un punto del conjunto y comenzar un nuevo “dosel” que contenga este punto.
3. Para cada punto que quede en el conjunto, asígnelo al nuevo dosel si su distancia al primer punto del dosel es menor que la distancia suelta . ${\displaystyle T_{1}}$
4. Si la distancia del punto es además menor que la distancia ajustada , retírelo 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 copas agrupadas de forma relativamente barata se pueden subagrupar utilizando un algoritmo más costoso pero preciso.

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

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 . Solo cuando se dispone de una función de distancia barata y aproximada (de baja dimensión), las copas producidas preservarán los cúmulos producidos por K-means.

Entre sus beneficios se incluyen:

• Se reduce el número de instancias de datos de entrenamiento que deben compararse en cada paso.
• Hay cierta evidencia de que los clústeres resultantes han mejorado. ^[3]

Referencias

1. McCallum, A.; Nigam, K.; y Ungar LH (2000) "Agrupamiento eficiente de conjuntos de datos de alta dimensión con aplicación a la correspondencia de referencias", Actas de la sexta conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos, 169-178 doi :10.1145/347090.347123
2. "El algoritmo de Canopies". courses.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.