ABEDUL
BIRCH ( agrupación y reducción iterativa equilibrada mediante jerarquías ) es un algoritmo de minería de datos no supervisado que se utiliza para realizar agrupaciones jerárquicas en conjuntos de datos particularmente grandes. [1] Con modificaciones, también se puede utilizar para acelerar la agrupación de k-medias y el modelado de mezcla gaussiana con el algoritmo de maximización de expectativas . [2] Una ventaja de BIRCH es su capacidad para agrupar de forma incremental y dinámica puntos de datos métricos multidimensionales entrantes en un intento de producir la agrupación de mejor calidad para un conjunto dado de recursos ( restricciones de tiempo y memoria). En la mayoría de los casos, BIRCH solo requiere un único escaneo de la base de datos.
Sus inventores afirman que BIRCH es el "primer algoritmo de agrupación propuesto en el área de la base de datos para manejar el 'ruido' (puntos de datos que no forman parte del patrón subyacente) de manera efectiva", [1] superando a DBSCAN por dos meses. El algoritmo BIRCH recibió el premio SIGMOD de prueba de tiempo de 10 años en 2006. [3]
Los algoritmos de agrupación en clústeres anteriores funcionaron con menos eficacia en bases de datos muy grandes y no consideraron adecuadamente el caso en el que un conjunto de datos era demasiado grande para caber en la memoria principal . Como resultado, hubo una gran cantidad de gastos generales para mantener una alta calidad de agrupación mientras se minimizaba el costo de operaciones adicionales de E / S (entrada / salida). Además, la mayoría de los predecesores de BIRCH inspeccionan todos los puntos de datos (o todos los grupos existentes actualmente) por igual para cada 'decisión de agrupamiento' y no realizan una ponderación heurística basada en la distancia entre estos puntos de datos.
Es local en el sentido de que cada decisión de agrupación se toma sin escanear todos los puntos de datos y las agrupaciones existentes actualmente. Aprovecha la observación de que el espacio de datos no suele estar ocupado de manera uniforme y no todos los puntos de datos son igualmente importantes. Hace un uso completo de la memoria disponible para derivar los mejores subgrupos posibles mientras minimiza los costos de E / S. También es un método incremental que no requiere todo el conjunto de datos por adelantado.
El algoritmo BIRCH toma como entrada un conjunto de N puntos de datos, representados como vectores de valor real , y un número deseado de grupos K. Funciona en cuatro fases, la segunda de las cuales es opcional.
La primera fase crea un árbol de características de agrupamiento ( ) a partir de los puntos de datos, una estructura de datos de árbol con equilibrio de altura , definida de la siguiente manera:
