Sudipto Guha, Rajeev Rastogi, Kyuseok Shim · ROCK Clustering Algorithm • Le fasi principali di...
Transcript of Sudipto Guha, Rajeev Rastogi, Kyuseok Shim · ROCK Clustering Algorithm • Le fasi principali di...
ROCKROCK
A Robust Clustering Algorithmfor Categorical Attributes
Sudipto Guha, Rajeev Rastogi, Kyuseok Shim
Sistemi Informativi per le Decisioni
a.a. 2005/2006
Prof. Marco Patella
Presentazione di Sara Liparesi e Francesco Nonni
• Sviluppato da Sudipto Guha, Rajeev Rastogi e KyuseokShim nel 1999
• Algoritmo gerarchico agglomerativo
• Adatto allo studio dei dati categorici
• Basato su misure di similarità non metriche
ROCK ROCK ClusteringClustering AlgorithmAlgorithmRObustRObust ClusteringClustering usingusing linKslinKs
Limiti degli algoritmi di Limiti degli algoritmi di clusteringclusteringtradizionalitradizionali
• Algoritmi gerarchici:• Non sempre adatti a trattare attributi categorici
• La distanza fra i centroidi dei cluster, nel caso di attributi categorici, è una povera stima della similarità fra i clusters
• Ripple Effect
• Alcuni algoritmi usano delle misure di distanza diverse da quelle euclidee (es. Jaccard coefficient), ma si concentrano solo su due punti per volta ignorando il vicinato dei punti stessi (approccio locale)
MARKETING
Dati categorici
????dati
dati
dati• Algoritmi partizionanti:• Non adatti ad attributi categorici
Concetti fondamentaliConcetti fondamentali
• Neighbors
• Links
• Criterion Function
• Goodness Measure
I vicini di un punto sono quei punti che possono essere considerati ragionevolmente simili ad esso:
NeighborsNeighbors
21
2121 ),(
TTTT
TTsim∪∩
=
Esempio: Market Basket Data
Date due transazioni T1, T2 una possibile funzione di similarità è:
θ≥),( ji ppsimDove:
• sim è una generica funzione di similarità che indica la vicinanza tra coppie di punti;
• Θ è un valore di soglia.
LinksLinks
Il concetto di links viene introdotto per definire il numero di vicini in comune fra una coppia di punti pi, pj.
• Tale numero viene espresso da link(pi,pj).• Questa proprietà permette all’algoritmo di individuare le coppie di punti che potenzialmente possono essere unite in un unico cluster.
• In generale, punti appartenenti a un singolo cluster avranno un grande numero di vicini in comune e conseguentemente un alto numero di links.
Esempio
LinksLinks: esempio: esempio
IDID GenereGenere RegistaRegista AttoreAttore DisponibilitDisponibilitàà al noleggioal noleggio
MrMr e e MrsMrs SmithSmith T1T1 adrenalinaadrenalina LimanLiman PittPitt non disponibilenon disponibile
TroyTroy T2T2 adrenalinaadrenalina PetersenPetersen PittPitt disponibiledisponibile
La Storia InfinitaLa Storia Infinita T3T3 in famigliain famiglia PetersenPetersen GunnGunn disponibiledisponibile
The The BourneBourne IdentityIdentity T4T4 adrenalinaadrenalina LimanLiman DamonDamon disponibiledisponibile
La Tempesta PerfettaLa Tempesta Perfetta T5T5 adrenalinaadrenalina PetersenPetersen ClooneyClooney disponibiledisponibile
Air Force OneAir Force One T6T6 adrenalinaadrenalina PetersenPetersen FordFord disponibiledisponibile
I Fratelli I Fratelli GrimmGrimm T7T7 in famigliain famiglia GilliamGilliam DamonDamon non disponibilenon disponibile
Fonte: Blockbuster.it
simsim(T1,T3)(T1,T3) 00 simsim(T2,T3)(T2,T3) 0,50,5 simsim(T3,T4)(T3,T4) 0,250,25 simsim(T4,T6)(T4,T6) 0,50,5
simsim(T1,T4)(T1,T4) 0,50,5 simsim(T2,T4)(T2,T4) 0,50,5 simsim(T3,T5)(T3,T5) 0,50,5 simsim(T4,T7)(T4,T7) 0,250,25
simsim(T1,T5)(T1,T5) 0,250,25 simsim(T2,T5)(T2,T5) 0,750,75 simsim(T3,T6)(T3,T6) 0,50,5 simsim(T5,T6)(T5,T6) 0,750,75
simsim(T1,T6)(T1,T6) 0,250,25 simsim(T2,T6)(T2,T6) 0,750,75 simsim(T3,T7)(T3,T7) 0,250,25 simsim(T5,T7)(T5,T7) 00
simsim(T1,T7)(T1,T7) 0,250,25 simsim(T2,T7)(T2,T7) 00 simsim(T4,T5)(T4,T5) 0,50,5 simsim(T6,T7)(T6,T7) 00
( ) 5,0, 21 ==pmTTsim
LinksLinks: esempio (2): esempio (2)
Ponendo θ=0,5 i vicini sono:
T4T2
T6T5T4T3T1
T6T5T2
T6T5T2T1
T6T4T3T2
T5T4T3T2
T1
T2
T3
T4
T5
T6
Link(T3,T4)=3
Link(T1,T5)=2
…
CriterionCriterion FunctionFunction
( )∑∑∈
+=
∗=Cipp
fi
rqk
iil
rq npplink
nE,
211
),(θ
Dove: •k = n° di clusters,
•ni = n° di punti nel cluster Ci
•(ni)1+2f(θ) è il numero atteso di links tra coppie di punti in Ci
Obiettivo:
• Massimizzare il numero di links tra i punti appartenenti allo stesso cluster
• Minimizzare il numero di links tra punti appartenenti a clusterdiversi
GoodnessGoodness MeasureMeasure
• La criterion function misura la bontà della soluzione trovata: il clustering migliore è quello che ha il più alto valore della funzione obiettivo.
• Ad ogni step è però necessaria una indicazione su quali sono i migliori 2 clusters da fondere.
• Per la coppia di cluster Ci,Cj si definisce la goodness measure g(Ci,Cj)
Intuitivamente possiamo pensare di unire due cluster che hanno molti vicini in comune
∑∈∈
=jriq CpCp
rq pplinkj)link(Ci, C,
),(
GoodnessGoodness MeasureMeasure (2)(2)
• E’ necessario anche un denominatore che rappresenti il numero atteso di cross-links fra clusters.
( )( ) ( ) ( ) ( )θθθ f
jf
if
ji
jiji nnnn
CClinkCCg 212121
,),( +++ −−+=
Dove:
• (ni+nj)1+2f(θ) è il numero di links atteso tra coppie di punti nel clusterunione dei singoli cluster Ci e Cj e composto da ni+nj elementi.
ROCK ROCK ClusteringClustering AlgorithmAlgorithm
• Le fasi principali di questo algoritmo sono:
• L’algoritmo ROCK non lavora su tutti i punti del data set, ma ne estrae un campione e esegue il clustering solo su di essi
• E’ necessario fornire a ROCK diversi parametri, tra cui il numero di clusters desiderati
• La nozione di links tra punti permette un approccio globale al problema del clustering
• I restanti punti sono inseriti nei clusters trovati da ROCK in un secondo momento
ROCK ROCK ClusteringClustering AlgorithmAlgorithm (2)(2)
Dati di input: (k,S)
1. Viene richiamata la proceduracompute-links(S)
Procedura Procedura computecompute--linkslinks
• Con questa procedura viene calcolato, per ogni coppia di punti, il numero di vicini in comune
• L’idea di base è che se considero un punto (A) e calcolo quali sono i suoi vicini (ad esempio B e C) allora ogni coppia di vicini (B e C in questo caso) avrà sicuramente un vicino in comune che è il punto stesso (A)
• La procedura deve essere ripetuta per ogni punto campionato e il contatore deve essere incrementato per ogni coppia di vicini
Procedura Procedura computecompute--linkslinks : esempio: esempio
Ponendo θ=0,5 i vicini sono:
T1 T4T2
T2 T6T5T4T3T1
T6T5T2T3
T6T5T2T1
T6T4T3T2
T5T4T3T2
T4
T5
T6
Link(T2,T4)= 1
Link(T1,T3)= 1
Link(T5,T6)= 1
Link(T2,T5)= 1
2
Link(T1,T4)= 1
Link(T1,T5)= 1
Link(T1,T6)= 1
Link(T3,T4)= 1
Link(T3,T5)= 1
Link(T3,T6)= 1
Link(T4,T5)= 1
Link(T4,T6)= 1
Link(T2,T6)= 1
ROCK ROCK ClusteringClustering AlgorithmAlgorithm (2)(2)
Dati di input: (k,S)
4. Viene inoltre costruita una pila globale Q contenente tutti i clusters/punti ordinati in modo decrescente secondo la loro miglior goodnessmeasure.
1. Viene richiamata la proceduracompute-links(S)
2. For each-loop
Per ogni valore campionato sviene costruita una pila locale q[s] contenente tutti i punti j con link[s,j]≠0, ordinati in maniera decrescente secondo la goodness measure rispetto a s.
ROCK ROCK ClusteringClustering AlgorithmAlgorithm (3)(3)
5. While-loop
Mediante questo loop si effettua la vera e proprio operazione di clustering.
Vengono identificati i clusters u e v come clusters che più si prestano a diventare un unico cluster.
Viene creato un nuovo cluster wche contiene tutti i punti di u e v.
Esempio
q[3]
4
1
5
q[4]312…
Q
4
312
5
u
Q
4
12
5
u3
q[u]
4
1
5
v
v1
Q
42
5
w1 U 3
Esempio: scelta dei miglior Esempio: scelta dei miglior clustersclusters da unireda unire
Q3
42
15
ROCK ROCK ClusteringClustering AlgorithmAlgorithm (4)(4)
10. for each sub-loop
E’ ora necessaria una fase in cui viene considerato il cluster unico w invece che i singoli clusters u e v.
Tutti i clusters x che precedentemente avevano relazioni con i singoli clusters u o v devono ora prendere in considerazione il cluster unico w.
16. Infine viene aggiornato Q con il nuovo custer w in base alla sua miglior goodnessmeasure (locale). Inoltre vengono deallocate le memorie che contenevano i local heapdei singoli cluster u e v.
LabelingLabeling dei datidei dati
• Non tutti i punti del data set sono stati forniti in input a ROCK
• Sono stati generati dei cluster a partire da un sottoinsieme del data set
• Come assegnare i punti che sono sul disco ai clusters individuati?
1. Estraggo da ogni cluster i un frazione dei punti (Li)
2. Per ogni punto p del data set letto da disco calcolo per ogni cluster i:
3. Il punto p è assegnato al cluster i dove la funzione precedentemente calcolata assume valore massimo
( ) ( )θfi
i
LN
1+
ComplessitComplessitàà spaziale e temporalespaziale e temporale
Nel caso peggiore la complessità temporale dell’algoritmo ROCK è:
( )nnmnmn am logΟ 22 ++
Dove:
• n è il numero di punti in input
• mm è il numero massimo di vicini
• ma è il numero medio di vicini
La complessità spaziale è: { }( )am mnmn ,minΟ 2
Risultati SperimentaliRisultati Sperimentali
L’algoritmo ROCK è stato testato su diversi data set:
Sono stati confrontati i risultati dell’algoritmo ROCK e di altri algoritmi di clustering gerarchico, applicati agli stessi data set.
RisultatiRisultati SperimentaliSperimentali