Algoritmo de agrupamiento de dosel

El algoritmo de agrupamiento de canopy es un algoritmo de preagrupamiento no supervisado introducido por Andrew McCallum , Kamal Nigam y Lyle Ungar en 2000. ^{[ 1 ]} Se utiliza frecuentemente 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 conjuntos de datos grandes , donde el uso directo de otro algoritmo puede resultar poco práctico debido al tamaño del conjunto de datos.

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

1. Comience con el conjunto de puntos de datos que se van a agrupar.
2. Elimina un punto del conjunto, creando así un nuevo "dosel" que contenga dicho punto.
3. Para cada punto restante 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${\displaystyle T_{2}}$, retíralo del conjunto original.
5. Repita desde el paso 2 hasta que no queden más puntos de datos en el conjunto para agrupar.
6. Estas agrupaciones de copas de árboles, relativamente económicas, pueden subagruparse utilizando un algoritmo más costoso pero preciso.

Es importante tener en cuenta que los puntos de datos individuales pueden pertenecer a varias copas de árboles. Para acelerar aún más el proceso, se puede utilizar una métrica de distancia aproximada y rápida para el paso 3, mientras que para el paso 4 se puede utilizar una métrica de distancia más precisa y lenta.

Dado que el algoritmo utiliza funciones de distancia y requiere la especificación de umbrales de distancia, su aplicabilidad a datos de alta dimensión se ve limitada por la maldición de la dimensionalidad . Solo cuando se dispone de una función de distancia sencilla y aproximada (de baja dimensión), los mapas de distribución resultantes conservarán los clústeres generados 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 mejoran. ^{[ 3 ]}