CURE: AN EFFICIENT CLUSTERING
ALGORITHM FOR LARGE DATABASES
GRUPPO 12
Filippo Bindi
Massimiliano Ceccarini
Andrea Giuliodori
PRESENTAZIONE
Sistemi Informativi per
le Decisioni LS
Prof. Marco Patella
INTRODUZIONE
GLI ALGORITMI TRADIZIONALI
Classi degli Algoritmi di Clustering:
 Partizionanti (K-means, Clarans, Expectation maximization)
TRADIZIONALI
 Gerarchici (Birch, Cure, Rock, Chamaleon)
agglomerativi
divisivi
 Basati sul collegamento (Linkage)
Principali debolezze dei Tradizionali:
 Basati sulla densità (Dbscan, Denclue) • Favoriscono le forme sferiche
 Statistici (Cobweb, Autoclass)
• Favoriscono forme con dimensioni
uniformi
• Affetti dal problema del Chaining effect
• Difficile gestione degli Outliers
• Scalabilità : complessità almeno O(n2)
nel numero di oggetti
13 Marzo 2006
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
INTRODUZIONE
LA “CURA”
CURE (Clustering Using REpresentatives)
 In grado di gestire opportunamente gli outliers
 In grado di identificare clusters di forma non sferica
e variabili nella dimensione
VANTAGGI
 Si basa sulla determinazione di punti rappresentativi
PARTICOLARITA’
ALGORITMO
 Utilizza un fattore di “gravità” denominato alpha
 I datasets di grandi dimensioni vengono “sintetizzati”
tramite il random sampling
 Il dataset “sintetizzato” viene successivamente
partizionato
13 Marzo 2006
TRATTAMENTI
PRELIMINARI
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
OVERVIEW
un cluster per
ogni punto
13 Marzo 2006
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
U.REP - T
u.rep
u
13 Marzo 2006
Per ogni cluster si calcolano i
punti rappresentativi , poi
inseriti nell’albero T
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
U.CLOSEST - Q
u.closest = min dist(p,q)
p u.rep, q v.rep
u
z
d2
d1
Una volta misurata la distanza
di tutti i cluster rispetto ai propri
.closest, viene creata una heap
in cui i cluster vengono inseriti
in base a distanze crescenti:
Q = (u,v,…,z,y)
v = u.closest
y = z.closest
13 Marzo 2006
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
13 Marzo 2006
STRUTTURA
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
MERGE
u
v
w
13 Marzo 2006
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
FATTORE 
Analisi di sensitività
Shrink factor 
 =1 Cure è simile al Birch
 =0 Cure è simile al MST
 Range consigliato  0.2 , 0.7 
13 Marzo 2006
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
N° RAPPRESENTATIVI
Analisi di sensitività
Numero di punti rappresentativi c
 Se c è un numero piccolo la geometria del cluster non è
rappresentata al meglio ( perdita qualità )
 Se c è un numero grande la geometria del cluster è ben
rappresentata
C piccolo
13 Marzo 2006
C grande
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
13 Marzo 2006
STRUTTURA
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
CLUSTER
x
x3
w.closest
x1
x
u
v
w
x4
13 Marzo 2006
x2
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
ALGORITMO
COMPLESSITA’
Prestazioni di CURE
 Nel caso peggiore la complessità temporale dell’algoritmo è O( n2 log n)
 Si riduce a O(n2) se la dimensionalità dei dati è bassa (es. 2 dimensioni)
 Con l’ausilio degli insiemi T, Q la complessità spaziale è pari a O(n)
 Il trattamento preliminare dei dati ci permette di mantenere n piccolo
13 Marzo 2006
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
LARGE DATASET
TRATTAMENTI PRELIMINARI
 Sampling
 Partitioning
13 Marzo 2006
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
LARGE DATASET
OUTLIER
Eliminazione degli Outlier

Step 1
Random Sampling : eliminazione casuale di alcuni outlier ed
isolamento dei restanti

Step 2
Prima semplificazione : l’algoritmo si ferma quando il numero di
cluster si è ridotto ad 1/m rispetto al numero iniziale (risultati
sperimentali fissano m=3); a questo punto vengono eliminati i
cluster la cui dimensione è sotto una certa soglia.

Step 3
Seconda semplificazione : quando all’algoritmo mancano poche
iterazioni al termine vengono eliminati i cluster di dimensione
molto piccola
13 Marzo 2006
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
RISULTATI
Conclusioni
 Cure è un algoritmo efficace nell’identificare cluster di forma
elissoidali e sferiche
 Offre prestazioni migliori rispetto a Birch
 Senza opportune tecniche la complessità temporale pari ad O(n2)
renderebbe ingestibili datasets di grandi dimensioni
13 Marzo 2006
Presentazione Sistemi Informativi per le Decisioni LS
GRUPPO 12
CURE: AN EFFICIENT CLUSTERING ALGORITHM FOR LARGE DATABASES
SLIDE DI SINTESI
 Cure è un algoritmo di clustering gerarchico-agglomerativo
 L’algoritmo ha una complessità temporale pari ad O(n2)
 Ogni cluster è identificato da un numero c di punti
rappresentativi; questi punti sono in grado di rappresentare
anche clusters di forma non sferica
 Tale complessità renderebbe Cure inapplicabile a datasets
di grandi dimensioni; da qui la necessità di “trattare”
preliminarmente il dataset attraverso le tecniche di sampling e
partitioning
 L’algoritmo utilizza un fattore alpha, detto shrink factor, per
modificare la posizione dei punti rappresentativi al fine di
limitare l’effetto di eventuali outliers
 Cure ingloba tecniche
particolarmente efficaci
GRUPPO 12
Filippo Bindi
Massimiliano Ceccarini
Andrea Giuliodori
di
gestione
degli
outliers