ABEDUL

Este artículo trata sobre el algoritmo de agrupación en clústeres. Para el árbol, vea Birch . Para otros usos, vea Birch (desambiguación) .

Parte de una serie sobre
Aprendizaje automático y minería de datos
Problemas Clasificación Agrupación Regresión Detección de anomalías AutoML reglas de asociación Aprendizaje reforzado Predicción estructurada Ingeniería de características Aprendizaje de funciones Aprender en línea Aprendizaje semi-supervisado Aprendizaje sin supervisión Aprendiendo a clasificar Inducción gramatical
Aprendizaje supervisado ( clasificación  • regresión ) Árboles de decisión Conjuntos Harpillera Impulsando Bosque aleatorio k -NN Regresión lineal Bayes ingenuo Redes neuronales artificiales Regresión logística Perceptrón Máquina de vectores de relevancia (RVM) Máquina de vectores de soporte (SVM)
Agrupación ABEDUL CURA Jerárquico k -significa Expectativa-maximización (EM) DBSCAN ÓPTICA Cambio medio
Reducción de dimensionalidad Análisis factorial CCA ICA LDA NMF PCA PGD t-SNE
Predicción estructurada Modelos graficos Red de Bayes Campo aleatorio condicional Markov oculto
Detección de anomalías k -NN Factor de valor atípico local
Red neuronal artificial Autoencoder Computación cognitiva Aprendizaje profundo DeepDream Perceptrón multicapa RNN LSTM GRU ESN Máquina de Boltzmann restringida GAN SOM Red neuronal convolucional U-Net Transformador Red neuronal en aumento Memtransistor RAM electroquímica (ECRAM)
Aprendizaje reforzado Q-aprendizaje SARSA Diferencia temporal (TD)
Teoría Compensación entre sesgo y varianza Teoría del aprendizaje computacional Minimización de riesgos empíricos Aprendizaje de Occam Aprendizaje PAC Aprendizaje estadístico Teoría de VC
Lugares de aprendizaje automático NeurIPS ICML ML JMLR ArXiv: cs.LG
Artículos relacionados Glosario de inteligencia artificial Lista de conjuntos de datos para la investigación de aprendizaje automático Esquema del aprendizaje automático
v t mi

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]

Problema con los métodos anteriores

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.

Ventajas con BIRCH

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.

Algoritmo

El algoritmo ABEDUL toma como entrada un conjunto de N puntos de datos, representado 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 de altura equilibrada , definida de la siguiente manera:${\displaystyle CF}$

• Dado un conjunto de N puntos de datos dimensionales, la característica de agrupamiento del conjunto se define como el triple , donde es la suma lineal y es la suma cuadrada de los puntos de datos.${\displaystyle CF}$${\displaystyle CF=(N,{\overrightarrow {LS}},SS)}$${\displaystyle {\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}$${\displaystyle SS=\sum _{i=1}^{N}({\overrightarrow {X_{i}}})^{2}}$
• Las características de agrupamiento se organizan en un árbol CF , un árbol de altura equilibrada con dos parámetros: ^{[ aclaración necesaria ]} factor de ramificación y umbral . Cada nodo no hoja contiene en la mayoría de las entradas de la forma , donde es un puntero a su ésimo nodo hijo y la función de agrupación que representa el subgrupo asociado. Un nodo hoja contiene como máximo las entradas de cada formulario . También tiene dos punteros prev y next que se utilizan para encadenar todos los nodos de hojas. El tamaño del árbol depende del parámetro . Se requiere un nodo para caber en una página de tamaño . y${\displaystyle B}$${\displaystyle T}$${\displaystyle B}$${\displaystyle [CF_{i},child_{i}]}$${\displaystyle child_{i}}$${\displaystyle i}$${\displaystyle CF_{i}}$${\displaystyle L}$${\displaystyle [CF_{i}]}$${\displaystyle T}$${\displaystyle P}$${\displaystyle B}$${\displaystyle L}$están determinados por . Por lo que se puede variar para ajustar el rendimiento . Es una representación muy compacta del conjunto de datos porque cada entrada en un nodo hoja no es un solo punto de datos sino un subcluster.${\displaystyle P}$${\displaystyle P}$

En el segundo paso, el algoritmo escanea todas las entradas de hojas en el árbol inicial para reconstruir un árbol más pequeño , mientras elimina los valores atípicos y agrupa los subgrupos abarrotados en más grandes. Este paso está marcado como opcional en la presentación original de BIRCH.${\displaystyle CF}$${\displaystyle CF}$

En el paso tres, se utiliza un algoritmo de agrupamiento existente para agrupar todas las entradas hoja. Aquí, un algoritmo de agrupamiento jerárquico aglomerativo se aplica directamente a los subgrupos representados por su${\displaystyle CF}$vectores. También proporciona la flexibilidad de permitir al usuario especificar el número deseado de racimos o el umbral de diámetro deseado para los racimos. Después de este paso, se obtiene un conjunto de conglomerados que captura el patrón de distribución principal en los datos. Sin embargo, pueden existir inexactitudes menores y localizadas que se pueden manejar con un paso opcional 4. En el paso 4, los centroides de los grupos producidos en el paso 3 se utilizan como semillas y redistribuyen los puntos de datos a sus semillas más cercanas para obtener un nuevo conjunto de racimos. El paso 4 también nos brinda la opción de descartar valores atípicos. Ese es un punto que está demasiado lejos de su semilla más cercana y puede tratarse como un valor atípico.

Cálculos con las funciones de agrupamiento

Dada solo la característica de agrupamiento , las mismas medidas se pueden calcular sin el conocimiento de los valores reales subyacentes.${\displaystyle CF=[N,{\overrightarrow {LS}},SS]}$

• Centroide: ${\displaystyle {\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow {LS}}{N}}}$
• Radio: ${\displaystyle R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i}}}-{\overrightarrow {C}})^{2}}{N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+SS-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}={\sqrt {{\frac {SS}{N}}-({\frac {\overrightarrow {LS}}{N}})^{2}}}}$
• Distancia de vinculación promedio entre clusters y :${\displaystyle CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},SS_{1}]}$${\displaystyle CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},SS_{2}]}$${\displaystyle D_{2}={\sqrt {\frac {\sum _{i=1}^{N_{1}}\sum _{j=1}^{N_{2}}({\overrightarrow {X_{i}}}-{\overrightarrow {Y_{j}}})^{2}}{N_{1}\cdot N_{2}}}}={\sqrt {\frac {N_{1}\cdot SS_{2}+N_{2}\cdot SS_{1}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{2}}}}{N_{1}\cdot N_{2}}}}}$

En casos multidimensionales, la raíz cuadrada debe reemplazarse por una norma adecuada.

Problemas numéricos en las funciones de agrupación en clústeres de BIRCH

Desafortunadamente, existen problemas numéricos asociados con el uso del término en BIRCH. Al restar o similar en las otras distancias, como , puede ocurrir una cancelación catastrófica y producir una precisión pobre, y que en algunos casos incluso puede causar que el resultado sea negativo (y la raíz cuadrada se vuelva indefinida). ^[2] Esto se puede resolver utilizando características de clúster BETULA en su lugar, que almacenan el recuento , la media y la suma de las desviaciones cuadradas en su lugar basándose en algoritmos en línea numéricamente más confiables para calcular la varianza.${\displaystyle SS}$${\displaystyle {\frac {SS}{N}}-{\big (}{\frac {\vec {LS}}{N}}{\big )}^{2}}$${\displaystyle D_{2}}$${\displaystyle CF=(N,\mu ,S)}$${\displaystyle N}$${\displaystyle \mu }$. Para estas características, se aplica un teorema de aditividad similar. Al almacenar un vector respectivamente una matriz para las desviaciones cuadradas, el árbol BIRCH CF resultante también se puede utilizar para acelerar el modelado de mezcla gaussiana con el algoritmo de maximización de expectativas , además de la agrupación de k-medias y la agrupación aglomerativa jerárquica .

Notas

1. Zhang, T .; Ramakrishnan, R .; Livny, M. (1996). "BIRCH: un método de agrupación de datos eficiente para bases de datos muy grandes". Actas de la conferencia internacional ACM SIGMOD de 1996 sobre Gestión de datos - SIGMOD '96 . págs. 103-114. doi : 10.1145 / 233269.233324 .
2. Lang, Andreas; Schubert, Erich (2020), "BETULA: Numerically Stable CF-Trees for BIRCH Clustering" , Similarity Search and Applications , págs. 281–296, arXiv : 2006.12881 , doi : 10.1007 / 978-3-030-60936-8_22 , ISBN 978-3-030-60935-1, S2CID  219980434 , consultado el 16 de enero de 2021
3. "Premio a la prueba de tiempo SIGMOD 2006" . Archivado desde el original el 23 de mayo de 2010.