Algoritmos de agrupamiento en clústeres

Los conjuntos de datos de aprendizaje automático pueden tener millones de ejemplos, pero no todos los algoritmos de agrupamiento se escalan de manera eficiente. Muchos algoritmos de agrupamiento calculan la similitud entre todos los pares de ejemplos, lo que significa que su tiempo de ejecución aumenta como el cuadrado de la cantidad de ejemplos $n$, que se indica como $O(n^2)$ en la notación de complejidad.Los algoritmos $O(n^2)$ no son prácticos para conjuntos de datos con millones de ejemplos.

El algoritmo k-means tiene una complejidad de $O(n)$, lo que significa que el algoritmo se escala de forma lineal con $n$. Este algoritmo será el enfoque del curso.

Tipos de agrupamiento

Para obtener una lista exhaustiva de los diferentes enfoques del agrupamiento, consulta A Comprehensive Survey of Clustering Algorithms, de Xu, D. & Tian, Y. Ann. Datos. Sci. (2015) 2: 165. Cada enfoque es más adecuado para una distribución de datos en particular. En este curso, se analizan brevemente cuatro enfoques comunes.

Agrupamiento en clústeres basado en centroides

El centroide de un clúster es la media aritmética de todos los puntos del clúster. El agrupamiento en clústeres basado en centroides organiza los datos en clústeres no jerárquicos. Los algoritmos de agrupamiento basados en centroides son eficientes, pero sensibles a las condiciones iniciales y a los valores atípicos. De estos, k-means es el más utilizado. Requiere que los usuarios definan la cantidad de centroides, k, y funciona bien con clústeres de tamaño aproximadamente igual.

Figura 1: Ejemplo de agrupamiento en clústeres basado en centroides.

Agrupamiento en clústeres basado en la densidad

El agrupamiento basado en la densidad conecta áreas contiguas de alta densidad de ejemplos en clústeres. Esto permite descubrir cualquier cantidad de clústeres de cualquier forma. Los valores atípicos no se asignan a clústeres. Estos algoritmos tienen dificultades con los clústeres de diferente densidad y los datos con dimensiones altas.

Figura 2: Ejemplo de agrupamiento basado en la densidad.

Agrupamiento en clústeres basado en la distribución

Este enfoque de agrupamiento supone que los datos se componen de distribuciones probabilísticas, como las distribuciones gaussianas. En la Figura 3, el algoritmo basado en la distribución agrupa los datos en tres distribuciones gaussianas. A medida que aumenta la distancia del centro de la distribución, la probabilidad de que un punto pertenezca a la distribución disminuye. Las bandas muestran esa disminución en la probabilidad. Cuando no te sientas a gusto asumiendo una distribución subyacente particular de los datos, debes usar un algoritmo diferente.

Figura 3: Ejemplo de agrupación basada en la distribución.

Hierarchical clustering

El agrupamiento jerárquico crea un árbol de clústeres. No es de extrañar que el agrupamiento jerárquico sea muy adecuado para datos jerárquicos, como las taxonomías. Consulta Comparison of 61 Sequenced Escherichia coli Genomes de Oksana Lukjancenko, Trudy Wassenaar y Dave Ussery para ver un ejemplo. Se puede elegir cualquier cantidad de clústeres cortando el árbol en el nivel correcto.

Figura 4: Ejemplo de un árbol jerárquico que agrupa animales.

Términos clave:

• Algoritmo k-means
• centroide
• Distribuciones gaussianas