Algorisme CURE

CURE (Clustering Using REpresentatives) és un algorisme d'agrupació de dades eficient per a grans bases de dades. En comparació amb l'agrupació de K-means, és més robusta davant de valors atípics i capaç d'identificar clústers amb formes no esfèriques i variàncies de mida.^[1]

El popular algorisme de clústering K-means minimitza el criteri de la suma d'errors quadràtics:^[2]

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

Donades les grans diferències en les mides o geometries dels diferents clústers, el mètode de l'error quadràtic podria dividir els clústers grans per minimitzar l'error quadràtic, cosa que no sempre és correcta. A més, amb els algoritmes de clústering jeràrquic aquests problemes existeixen, ja que cap de les mesures de distància entre clústers (${\displaystyle d_{min},d_{mean}}$) tendeixen a treballar amb diferents formes de clúster. A més, el temps d'execució és alt quan n és gran.^[3]

El problema amb l'algoritme BIRCH és que un cop generats els clústers després del pas 3, utilitza els centroides dels clústers i assigna cada punt de dades al clúster amb el centroide més proper. Utilitzar només el centroide per redistribuir les dades té problemes quan els clústers no tenen mides i formes uniformes.^[4]

Per evitar els problemes amb clústers de mida o forma no uniformes, CURE utilitza un algorisme de clústering jeràrquic que adopta un punt intermedi entre el basat en el centroide i tots els extrems dels punts. A CURE, es tria un nombre constant c de punts ben dispersos d'un clúster i es redueixen cap al centroide del clúster per una fracció α. Els punts dispersos després de la reducció s'utilitzen com a representants del clúster. Els clústers amb el parell de representants més proper són els clústers que es fusionen a cada pas de l'algoritme de clústering jeràrquic de CURE. Això permet a CURE identificar correctament els clústers i el fa menys sensible als valors atípics.^[5]

El temps d'execució és ${\displaystyle O(n^{2}\log n)}$, cosa que el fa força car, i la complexitat espacial és ${\displaystyle O(n)}$.

L'algoritme no es pot aplicar directament a bases de dades grans a causa de l'alta complexitat en temps d'execució. Les millores aborden aquest requisit.

• Mostreig aleatori: el mostreig aleatori admet grans conjunts de dades. Generalment, la mostra aleatòria cap a la memòria principal. El mostreig aleatori implica un compromís entre precisió i eficiència.
• Particionament: La idea bàsica és particionar l'espai mostral en p particions. Cada partició conté n/p elements. La primera passada agrupa parcialment cada partició fins que el nombre final de clústers es redueix a n/pq per a alguna constant q ≥ 1. Una segona passada d'agrupament sobre n/q agrupa parcialment les particions. Per a la segona passada només s'emmagatzemen els punts representatius, ja que el procediment de fusió només requereix punts representatius de clústers anteriors abans de calcular els punts representatius del clúster fusionat. El particionament de l'entrada redueix els temps d'execució.
• Etiquetatge de dades al disc: donats només punts representatius per a k clústers, els punts de dades restants també s'assignen als clústers. Per això, es tria una fracció de punts representatius seleccionats aleatòriament per a cadascun dels k clústers i s'assigna el punt de dades al clúster que conté el punt representatiu més proper.^[6]

Entrada: Un conjunt de punts S

Sortida: k clústers

• Per a cada clúster u (cada punt d'entrada), a u.mean i u.rep s'emmagatzema la mitjana dels punts del clúster i un conjunt de c punts representatius del clúster (inicialment c = 1 ja que cada clúster té un punt de dades). També u.closest emmagatzema el clúster més proper a u.
• Tots els punts d'entrada s'insereixen en un arbre kd T
• Tractar cada punt d'entrada com un clúster separat, calculeu u.closest per a cada u i després inserir cada clúster al heap Q. (els clústers s'ordenen en ordre creixent de distàncies entre u i u.closest).
• Mentre que la mida (Q) > k
• Eliminar l'element superior de Q (per exemple, u) i fusionar-lo amb el clúster més proper u.closest (per exemple, v) i calcular els nous punts representatius per al clúster fusionat w.
• Eliminar u i v de T i Q.
• Per a tots els clústers x de Q, actualitza x.closest i reubica x
• inserir w a Q
• repetir

La biblioteca de codi obert Pyclustering inclou una implementació de l'algoritme CURE en Python i C++.