Algoritmo CURE

CURE (Clustering Using REpresentatives) es un algoritmo de agrupamiento de datos eficiente para grandes bases de datos . En comparación con el agrupamiento K-means, es más robusto frente a valores atípicos y capaz de identificar clústeres con formas no esféricas y variaciones de tamaño.

El popular algoritmo de agrupamiento K-means minimiza el criterio de suma de errores al cuadrado :

${\displaystyle E=\sum _{i=1}^{k}\sum _{p\in C_{i}}(p-m_{i})^{2},}$

Dadas las grandes diferencias en tamaños o geometrías de diferentes clústeres, el método del error cuadrático podría dividir los clústeres grandes para minimizar el error cuadrático, lo cual no siempre es correcto. Además, con los algoritmos de agrupamiento jerárquico existen estos problemas ya que ninguna de las medidas de distancia entre clústeres (${\displaystyle d_{min},d_{media}}$) tienden a funcionar con diferentes formas de clúster. Además, el tiempo de ejecución es alto cuando n es grande.

El problema con el algoritmo BIRCH es que, una vez generados los clústeres tras el paso 3, utiliza los centroides de los clústeres y asigna cada punto de datos al clúster con el centroide más cercano. Redistribuir los datos únicamente mediante el centroide presenta problemas cuando los clústeres carecen de tamaños y formas uniformes.

Para evitar problemas con clústeres de tamaño o forma no uniformes, CURE emplea un algoritmo de agrupamiento jerárquico que adopta un punto intermedio entre el basado en el centroide y el de todos los extremos de los puntos. En CURE, se selecciona un número constante c de puntos bien dispersos de un clúster y se reducen hacia el centroide del clúster en una fracción α. Los puntos dispersos después de la reducción se utilizan como representantes del clúster. Los clústeres con el par de representantes más cercano son los que se fusionan en cada paso del algoritmo de agrupamiento jerárquico de CURE. Esto permite a CURE identificar correctamente los clústeres y lo hace menos sensible a los valores atípicos.

El tiempo de ejecución es${\displaystyle O(n^{2}\log n)}$, lo que lo hace bastante caro, y la complejidad espacial es${\displaystyle O(n)}$.

El algoritmo no puede aplicarse directamente a bases de datos grandes debido a su alta complejidad computacional. Las mejoras implementadas abordan este requisito.

• Muestreo aleatorio: el muestreo aleatorio admite grandes conjuntos de datos. Generalmente, la muestra aleatoria cabe en la memoria principal . El muestreo aleatorio implica un equilibrio entre precisión y eficiencia.
• Particionamiento: La idea básica es dividir el espacio muestral en p particiones. Cada partición contiene n/p elementos. En la primera pasada, cada partición se agrupa parcialmente hasta que el número final de grupos se reduce a n/pq para alguna constante q ≥ 1. Una segunda pasada de agrupamiento sobre n/q agrupa parcialmente las particiones. En la segunda pasada, solo se almacenan los puntos representativos, ya que el procedimiento de fusión solo requiere los puntos representativos de los grupos anteriores antes de calcular los puntos representativos para el grupo fusionado. El particionamiento de la entrada reduce los tiempos de ejecución.
• Etiquetado de datos en disco: Dados únicamente los puntos representativos de k clústeres, los puntos de datos restantes también se asignan a los clústeres. Para ello, se elige una fracción de puntos representativos seleccionados aleatoriamente para cada uno de los k clústeres y cada punto de datos se asigna al clúster que contiene el punto representativo más cercano.

CURACIÓN (número de puntos, k )

Entrada: Un conjunto de puntos S

Salida: k clústeres

• Para cada clúster u (cada punto de entrada), u.mean y u.rep almacenan la media de los puntos del clúster y un conjunto de c puntos representativos del clúster (inicialmente c = 1, ya que cada clúster tiene un punto de datos). Además, u.closest almacena el clúster más cercano a u.
• Todos los puntos de entrada se insertan en un árbol kd T
• Trate cada punto de entrada como un clúster separado, calcule u.closest para cada u y luego inserte cada clúster en el montón Q. (Los clústeres están ordenados en orden creciente de distancias entre u y u.closest).
• Mientras el tamaño (Q) > k
• Elimine el elemento superior de Q (digamos u) y fúndalo con su clúster más cercano u.closest (digamos v) y calcule los nuevos puntos representativos para el clúster fusionado w.
• Retira u y v de T y Q.
• Para todos los clústeres x en Q, actualiza x.closest y reubica x.
• insertar w en Q
• repetir

• La biblioteca de código abierto pyclustering incluye una implementación del algoritmo CURE en Python y C++.

• agrupamiento k-means
• Algoritmo BFR

• Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). "CURE: Un algoritmo de agrupamiento eficiente para bases de datos grandes" (PDF) . Sistemas de información . 26 (1): 35– 58. doi : 10.1016/S0306-4379(01)00008-4 .
• Kogan, Jacob; Nicholas, Charles K.; Teboulle, M. (2006). Agrupación de datos multidimensionales: avances recientes en clustering . Springer. ISBN 978-3-540-28348-5.
• Theodoridis, Sergios; Koutroumbas, Konstantinos (2006). Reconocimiento de patrones . Academic Press. pp. 572–574 . ISBN  978-0-12-369531-4.