Algoritmos de agrupamiento automático

Los algoritmos de agrupamiento automático son algoritmos que pueden realizar agrupaciones sin conocimiento previo de los conjuntos de datos. A diferencia de otras técnicas de agrupamiento , los algoritmos de agrupamiento automático pueden determinar el número óptimo de clústeres incluso en presencia de ruido y valores atípicos .

Dado un conjunto de n objetos, los algoritmos basados ​​en centroides crean k particiones a partir de una función de disimilitud, de modo que k ≤ n . Un problema importante al aplicar este tipo de algoritmo es determinar el número adecuado de clústeres para datos sin etiquetar. Por lo tanto, la mayor parte de la investigación en análisis de agrupamiento se ha centrado en la automatización del proceso.

La selección automatizada de k en un algoritmo de agrupamiento K -means , uno de los algoritmos de agrupamiento basados ​​en centroides más utilizados, sigue siendo un problema importante en el aprendizaje automático. La solución más aceptada a este problema es el método del codo . Consiste en ejecutar el agrupamiento K -means en el conjunto de datos con un rango de valores, calcular la suma de los errores cuadráticos para cada uno y representarlos en un gráfico de líneas . Si el gráfico se asemeja a un brazo, el mejor valor de k estará en el "codo". ^{[ 1 ]}

Otro método que modifica el algoritmo k -means para seleccionar automáticamente el número óptimo de clústeres es el algoritmo G -means. Este se desarrolló a partir de la hipótesis de que un subconjunto de los datos sigue una distribución gaussiana. Por lo tanto, k se incrementa hasta que los datos de cada centro k -means sean gaussianos. Este algoritmo solo requiere el nivel de significancia estadística estándar como parámetro y no establece límites para la covarianza de los datos. ^{[ 2 ]}

La agrupación basada en conectividad o agrupación jerárquica se basa en la idea de que los objetos tienen más similitudes con otros objetos cercanos que con los más lejanos. Por lo tanto, los clústeres generados por este tipo de algoritmo serán el resultado de la distancia entre los objetos analizados.

Los modelos jerárquicos pueden ser divisivos, donde las particiones se construyen a partir de todo el conjunto de datos disponible, o aglomerativos, donde cada partición comienza con un solo objeto y se agregan objetos adicionales al conjunto. ^{[ 3 ]} Si bien la agrupación jerárquica tiene la ventaja de permitir el uso de cualquier métrica válida como distancia definida, es sensible al ruido y a las fluctuaciones en el conjunto de datos y es más difícil de automatizar.

Se han desarrollado métodos para mejorar y automatizar los algoritmos de agrupamiento jerárquico existentes ^{[ 4 ],} como una versión automatizada del análisis de agrupamiento jerárquico de enlace simple (HCA). Este método computarizado basa su éxito en un enfoque de reducción de valores atípicos autoconsistente, seguido de la construcción de una función descriptiva que permite definir agrupaciones naturales. Los objetos descartados también pueden asignarse a estas agrupaciones. En esencia, no es necesario recurrir a parámetros externos para identificar agrupaciones naturales. La información recopilada del HCA, automatizada y confiable, puede resumirse en un dendrograma con el número de agrupaciones naturales y la separación correspondiente, una opción que no se encuentra en el HCA clásico. Este método incluye los dos pasos siguientes: eliminación de valores atípicos (esto se aplica en muchas aplicaciones de filtrado) y una clasificación opcional que permite expandir las agrupaciones con el conjunto completo de objetos. ^{[ 5 ]}

BIRCH (balanced iterative reduction and clustering using hierarchies) es un algoritmo utilizado para realizar agrupamiento basado en conectividad para grandes conjuntos de datos. ^{[ 6 ]} Se considera uno de los algoritmos de agrupamiento más rápidos, pero tiene la limitación de requerir el número de clústeres como entrada. Por lo tanto, se han desarrollado nuevos algoritmos basados ​​en BIRCH en los que no es necesario proporcionar el número de clústeres desde el principio, pero que preservan la calidad y la velocidad de los clústeres. La principal modificación es eliminar el paso final de BIRCH, en el que el usuario tenía que introducir el número de clústeres, y mejorar el resto del algoritmo, denominado tree-BIRCH, optimizando un parámetro umbral a partir de los datos. En este algoritmo resultante, el parámetro umbral se calcula a partir del radio máximo del clúster y la distancia mínima entre clústeres, que a menudo se conocen. Este método ha demostrado ser eficiente para conjuntos de datos de decenas de miles de clústeres. Si se supera esa cantidad, se introduce un problema de división de superclústeres. Para ello, se han desarrollado otros algoritmos, como MDB-BIRCH, que reduce la división de superclústeres con una velocidad relativamente alta. ^{[ 7 ]}

A diferencia de los métodos de partición y jerárquicos, los algoritmos de agrupamiento basados ​​en la densidad son capaces de encontrar grupos de cualquier forma arbitraria, no solo esferas.

El algoritmo de agrupamiento basado en densidad utiliza aprendizaje automático autónomo que identifica patrones relacionados con la ubicación geográfica y la distancia a un número determinado de vecinos. Se considera autónomo porque no requiere conocimiento previo sobre qué es un clúster. ^{[ 8 ]} Este tipo de algoritmo proporciona diferentes métodos para encontrar clústeres en los datos. El método más rápido es DBSCAN , que utiliza una distancia definida para diferenciar entre grupos densos de información y ruido más disperso. Además, HDBSCAN puede autoajustarse utilizando un rango de distancias en lugar de una específica. Por último, el método OPTICS crea un gráfico de alcanzabilidad basado en la distancia a las características vecinas para separar el ruido de los clústeres de densidad variable.

Estos métodos aún requieren que el usuario proporcione el centro del clúster y no pueden considerarse automáticos. El Algoritmo de Agrupamiento Automático de Densidad Local (ALDC) es un ejemplo de la nueva investigación centrada en el desarrollo de agrupamientos automáticos basados ​​en la densidad. ALDC calcula la densidad local y la desviación de distancia de cada punto, ampliando así la diferencia entre el centro potencial del clúster y otros puntos. Esta ampliación permite que la máquina funcione automáticamente. La máquina identifica los centros de los clústeres y asigna los puntos que quedan por debajo de su vecino más cercano de mayor densidad. ^{[ 9 ]}

En la automatización de la densidad de datos para identificar clústeres, la investigación también se ha centrado en la generación artificial de algoritmos. Por ejemplo, el algoritmo de estimación de distribución (EDA) garantiza la generación de algoritmos válidos mediante el grafo acíclico dirigido (DAG), en el que los nodos representan procedimientos (bloques de construcción) y las aristas representan posibles secuencias de ejecución entre dos nodos. Los bloques de construcción determinan el alfabeto del EDA o, dicho de otro modo, cualquier algoritmo generado. Los algoritmos de agrupamiento generados artificialmente se comparan con DBSCAN, un algoritmo manual, en los resultados experimentales. ^{[ 10 ]}

Los recientes avances en el aprendizaje automático automatizado (AutoML) se han extendido al ámbito de la agrupación, donde los sistemas están diseñados para seleccionar automáticamente técnicas de preprocesamiento, transformaciones de características, algoritmos de agrupación y estrategias de validación sin intervención humana. A diferencia de los métodos de agrupación tradicionales que dependen de flujos de trabajo fijos y ajustes manuales, los marcos de agrupación basados ​​en AutoML buscan dinámicamente las configuraciones de mejor rendimiento a partir de índices de validación de agrupación internos (CVI) u otras métricas no supervisadas.

Una implementación en este ámbito es TPOT-Clustering, ^{[ 11 ]} una extensión de la herramienta de optimización de pipelines basada en árboles (TPOT), que automatiza el proceso de construcción de pipelines de clustering mediante programación genética . TPOT-Clustering explora combinaciones de transformaciones de datos, métodos de reducción de dimensionalidad, algoritmos de clustering (p. ej., K-means, DBSCAN, Clustering aglomerativo) y funciones de puntuación para optimizar el rendimiento del clustering. Utiliza un algoritmo evolutivo para explorar el espacio de pipelines posibles, empleando puntuaciones internas como el índice de silueta o el índice de Davies-Bouldin para guiar el proceso de selección.

El aprendizaje automático automatizado (AutoML) para la agrupación de datos resulta especialmente útil en ámbitos donde se desconoce la estructura de los datos y la optimización manual es inviable debido a la alta dimensionalidad o complejidad del espacio de características. Estos enfoques están ganando popularidad en áreas como la segmentación de imágenes, la segmentación de clientes y la bioinformática, donde la obtención de información no supervisada es fundamental.