Algoritmo CURE

CURE (Clustering Using REpresentatives) es un algoritmo de agrupamiento de datos eficiente para bases de datos grandes ^{[ cita requerida ]} . En comparación con el agrupamiento K-means, es más robusto a los valores atípicos y puede identificar agrupamientos que tienen 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 los tamaños o geometrías de los distintos clústeres, el método del error cuadrático podría dividir los clústeres grandes para minimizar el error cuadrático, lo que no siempre es correcto. Además, con los algoritmos de agrupamiento jerárquico estos problemas existen ya que ninguna de las medidas de distancia entre clústeres ( ) tiende a funcionar con diferentes formas de clúster. Además, el tiempo de ejecución es alto cuando n es grande. ${\displaystyle d_{min},d_{mean}}$

El problema con el algoritmo BIRCH es que una vez que se generan los clústeres después del paso 3, utiliza los centroides de los clústeres y asigna cada punto de datos al clúster con el centroide más cercano. ^{[ cita requerida ]} El uso solo del centroide para redistribuir los datos tiene problemas cuando los clústeres carecen de tamaños y formas uniformes.

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

El tiempo de ejecución es O( n ² log n ), lo que lo hace bastante caro, y la complejidad espacial es O( n ).

El algoritmo no se puede aplicar directamente a bases de datos grandes debido a la alta complejidad del tiempo de ejecución. Las mejoras 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.
• Particionado: La idea básica es particionar el espacio muestral en p particiones. Cada partición contiene n/p elementos. El primer paso agrupa parcialmente cada partición hasta que el número final de clústeres se reduce a n/pq para alguna constante q ≥ 1. Un segundo paso de agrupamiento en n/q agrupa parcialmente las particiones. Para el segundo paso solo se almacenan los puntos representativos ya que el procedimiento de fusión solo requiere puntos representativos de clústeres anteriores antes de calcular los puntos representativos para el clúster fusionado. La partición de la entrada reduce los tiempos de ejecución.
• Etiquetado de datos en el disco: Dados solo puntos representativos para k clústeres, los puntos de datos restantes también se asignan a los clústeres. Para esto, se elige una fracción de puntos representativos seleccionados aleatoriamente para cada uno de los k clústeres y el punto de datos se asigna al clúster que contiene el punto representativo más cercano a él.

CURA (n° de puntos, k )

Entrada: Un conjunto de puntos S

Salida: k clusters

• Para cada clúster u (cada punto de entrada), en u.mean y u.rep se almacena 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 grupo separado, calcule u.closest para cada u y luego inserte cada grupo en el montón Q. (los grupos se organizan en orden creciente de distancias entre u y u.closest).
• Mientras que el tamaño (Q) > k
• Elimine el elemento superior de Q (digamos u) y fusionelo con su grupo más cercano u.closest (digamos v) y calcule los nuevos puntos representativos para el grupo fusionado w.
• Eliminar u y v de T y Q.
• Para todos los clústeres x en Q, actualice x.closest y reubique x
• Insertar w en Q
• repetir

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

• Agrupamiento de k-medias
• Algoritmo BFR

• Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (1998). "CURE: Un algoritmo de agrupamiento eficiente para bases de datos de gran tamaño" (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). Agrupamiento de datos multidimensionales: avances recientes en clusterización . Springer. ISBN 978-3-540-28348-5.
• Theodoridis, Sergios; Koutroumbas, Konstantinos (2006). Reconocimiento de patrones. Academic Press. págs. 572–574. ISBN 978-0-12-369531-4.