ABEDUL

La reducción iterativa balanceada y el agrupamiento mediante jerarquías ( BIRCH ) es un algoritmo de minería de datos no supervisado que se utiliza para realizar el agrupamiento jerárquico en grandes conjuntos de datos [1] . La ventaja de BIRCH es la capacidad del método para agruparse dinámicamente a medida que llegan puntos de datos métricos multidimensionales en un intento de obtener una agrupación de mejor calidad para el conjunto de recursos disponibles (memoria y marco de tiempo ). En la mayoría de los casos, el algoritmo BIRCH requiere un paso a través de la base de datos .

Los desarrolladores de BIRCH afirmaron que era "el primer algoritmo de agrupamiento en ofrecer un manejo eficiente del 'ruido' (puntos de datos que no forman parte del esquema) en las bases de datos" [1] superando a DBSCAN en dos meses. El algoritmo recibió el premio SIGMOD en 2006 después de 10 años de pruebas [2] .

Problema con los métodos anteriores

Los algoritmos de agrupamiento anteriores funcionaban de forma menos eficiente en bases de datos grandes y se comportaban de forma inadecuada cuando los datos eran demasiado grandes para caber en la RAM . Como resultado, hubo un gran costo para obtener un agrupamiento de alta calidad mientras se minimizaba el costo de E/S adicional. Además, la mayoría de los predecesores de BIRCH analizaron todos los puntos de datos (o todos los grupos actualmente seleccionados) por igual para cada "decisión de agrupación" y no hicieron una ponderación heurística basada en las distancias entre estos puntos de datos.

Beneficios del ABEDUL

Cada solución de agrupación en clústeres es local y se realiza sin mirar todos los puntos de datos y los clústeres existentes actualmente. El método funciona en observaciones cuyo espacio de datos generalmente no se llena de manera uniforme y no todos los puntos de datos son igualmente importantes. El método permite usar toda la memoria disponible para obtener los subclusters más precisos posibles mientras se minimiza el costo de E/S. El método es incremental y no requiere el conjunto completo de datos a la vez.

Algoritmo

El algoritmo BIRCH toma como entrada un conjunto de N puntos de datos, representados como vectores reales , y el número deseado de grupos , K. El algoritmo se divide en cuatro fases, la segunda de las cuales es opcional.

La primera fase construye un árbol CF de puntos de datos, una estructura de árbol altamente equilibrada definida de la siguiente manera:

Dado un conjunto de N puntos de datos de dimensión d, la característica de agrupación del conjunto se define como un triple , donde es una suma lineal y es la suma de los cuadrados de los puntos de datos. ${\ estilo de visualización CF}$ ${\ Displaystyle CF = (N, LS, SS)}$ ${\displaystyle {\overrightarrow {LS}}=\sum _{i=1}^{N}{\overrightarrow {X_{i))))$ ${\overrightarrow {SS}}=\sum_{i=1}^{N}({\overrightarrow {X_{i}}})^{2}$
Las funciones de agrupación se organizan en un árbol CF , un árbol muy equilibrado con dos parámetros: factor de ramificación y umbral . Cada nodo que no es hoja consiste en la mayoría de las entradas del formulario , donde es un puntero a su enésimo hijo , y es un indicador de agrupación que representa el subclúster asociado. La hoja contiene como máximo entradas, cada una de la forma . También tiene dos punteros, anterior y siguiente, que se utilizan para encadenar todas las hojas. El tamaño del árbol depende del parámetro T. Se requiere que el nodo A quepa en una página de tamaño P. B y L están determinados por el valor de P. Por lo tanto, P se puede cambiar para ajustar el rendimiento . Esta es una representación muy compacta del conjunto de datos porque cada hoja no es un único punto de datos sino un subgrupo. $B$ $T$ $B$ $[CF_{i},niño_{i}]$ $niño_{i}$ $i$ $CF_{i}$ $L$ ${\ estilo de visualización [CF_{i}]}$

En el segundo paso, el algoritmo pasa por todas las hojas del árbol CF inicial para construir un árbol CF más pequeño eliminando los abandonos y agrupando las subclases desbordadas en subclases más grandes. Este paso está marcado como opcional en la vista de origen de BIRCH.

El tercer paso utiliza el algoritmo existente para agrupar todas las hojas. Aquí, el algoritmo de agrupamiento jerárquico aglomerativo se aplica directamente a los subgrupos representados por sus vectores CF. También brinda la flexibilidad de permitir que el usuario especifique el número deseado de grupos o el umbral de diámetro de grupo deseado. Después de este paso, obtenemos un conjunto de clústeres que contienen los principales patrones de distribución de los datos. Sin embargo, puede haber pequeñas imprecisiones locales que pueden ser manejadas por el paso 4 opcional. En el paso 4, los centros de gravedad de los grupos obtenidos en el paso 3 se utilizan como semillas y puntos de redistribución de puntos de datos para obtener un nuevo conjunto de grupos. . El paso 4 también proporciona una opción para descartar valores atípicos. Es decir, un punto que está demasiado lejos del núcleo más cercano puede considerarse un valor atípico.

Cálculo de signos de conglomerados

Si solo se da , se pueden obtener las mismas medidas sin conocer los valores verdaderos. $CF=[N,{\overrightarrow {LS}},{\overrightarrow {SS}}]$

Centroide: ${\overrightarrow {C}}={\frac {\sum _{i=1}^{N}{\overrightarrow {X_{i}}}}{N}}={\frac {\overrightarrow { LS}}{N}}$

Radio : $R={\sqrt {\frac {\sum _{i=1}^{N}({\overrightarrow {X_{i))}-{\overrightarrow {C)))^{2)){ N}}}={\sqrt {\frac {N\cdot {\overrightarrow {C}}^{2}+{\overrightarrow {SS}}-2\cdot {\overrightarrow {C}}\cdot {\overrightarrow {LS}}}{N}}}$

Distancia media entre racimos y : $CF_{1}=[N_{1},{\overrightarrow {LS_{1}}},{\overrightarrow {SS_{1}}}]$ $CF_{2}=[N_{2},{\overrightarrow {LS_{2}}},{\overrightarrow {SS_{2}}}]$ $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 {\overrightarrow {SS_{2}}}+N_{2}\cdot {\overrightarrow {SS_{1}}}-2\cdot {\overrightarrow {LS_{1}}}\cdot {\overrightarrow {LS_{ 2}}}}{N_{1}\cdot N_{2}}}}$

En casos multifactoriales, la raíz cuadrada se puede reemplazar por una norma apropiada.

Notas

↑ 1 2 Zhang, Ramakrishnan, Livny, 1996 , p. 103–114.
↑ Premio SIGMOD Test of Time 2006 (enlace no disponible) . Archivado desde el original el 23 de mayo de 2010. (indefinido)

Literatura

Zhang T., Ramakrishnan R., Livny M. BIRCH: un método eficiente de agrupación de datos para bases de datos muy grandes // Actas de la conferencia internacional ACM SIGMOD de 1996 sobre gestión de datos - SIGMOD '96. - 1996. - doi : 10.1145/233269.233324 .

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ICA LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG