WEKA: clustering

CLUSTERING
WITH
WEKA
Branca Stefano
Dosi Clio
Gnudi Edward William
Outline
Introduzione
• Clustering con weka
Algoritmi partizionanti
• K-Means
Algoritmi basati sulla densità
• DBScan
• OPTICS
Algoritmi per DB transazionali
• CLOPE
Tecniche di clusterizzazione con WEKA
Clusterizzazione del Dataset “Iris”
Tecniche di clusterizzazione con WEKA
Possibilità di scelta tra vari algoritmi
Tecniche di clusterizzazione con WEKA
Possibilità di scelta tra vari algoritmi
Tecniche di clusterizzazione con WEKA
Scelta dei parametri
Tecniche di clusterizzazione con WEKA
Scelta dei parametri
Tecniche di clusterizzazione con WEKA
Cluster Mode
Il “Cluster mode” è
utilizzato per
scegliere cosa
clusterizzare e le
modalità con cui
valutare i risultati
Tecniche di clusterizzazione con WEKA
Ignore attribute
Il pulsante “Ignore attribute” apre
una finestra che permette di
selezionare eventuali attributi da non
considerare nella formazione dei
cluster
Tecniche di clusterizzazione con WEKA
Premendo il tasto “Start”
si fa partire l'algoritmo.
Le informazioni
riguardanti il
processamento dei dati
vengono mostrate nel
riquadro a destra
Tecniche di clusterizzazione con WEKA
Tecniche di clusterizzazione con WEKA
Identificazione degli
attributi più significativi
Tecniche di clusterizzazione con WEKA
Tecniche di clusterizzazione con WEKA
K=2
K=5
Algoritmi partizionanti
K-Means
Applicazione al Dataset “Wine”
Algoritmi partizionanti
K-Means
Applicazione al Dataset “Wine”
Algoritmi basati sulla densità
DBScan
Algoritmi basati sulla densità - DBScan
Variando ε (IRIS)
Algoritmi basati sulla densità - DBScan
Variando MinPoints (IRIS)
Algoritmi basati sulla densità - DBScan
Limiti
1.
2.
Quali dimensioni dare a ε?
Non si possono individuare tutti i cluster e sottocluster in
presenza di densità diverse
Algoritmi basati sulla densità
OPTICS
( Ordering Points To Identify the Clustering Structure )
“it does not produce a clustering of a data set explicitly; but instead creates an augmented
ordering of the database representing its density-based clustering structure”
Al-Ri, optics ε=0.3
Algoritmi basati sulla densità - OPTICS
Algoritmo
= è un core object
Algoritmi basati sulla densità - OPTICS
Confronto con DBScan
ε = 0.9 ; MinPoints= 6
Clustered Instances
0
163 (100%)
ε = 0.5 ; MinPoints= 6
Clustered Instances
0
86 ( 58%)
1
63 ( 42%)
Unclustered instances : 14
(si perdono i cluster a bassa densità)
Algoritmi basati sulla densità - OPTICS
Confronto con DBScan
ε = 0.3 ; MinPoints= 6
Clustered Instances
0
23 ( 16%)
1
61 ( 43%)
2
57 ( 40%)
Unclustered instances : 22
cluster 0 23
cluster 1 61
Cluster 2
56
Undefined 23
Perché?
Algoritmi basati sulla densità - OPTICS
Confronto con DBScan
?? BORDER
rispetto ad un
core non
ancora
processato??
Algoritmi per DB transazionali
Caratteristiche dei dataset transazionali:
Alta dimensione
Sparsità
Grandi volumi di tuple
In questi casi, algoritmi basati sulle distanze (es. k-means)
sono inefficienti.
Gli algoritmi gerarchici (es. ROCK) sono, invece, abbastanza
efficienti ma poco scalabili
Algoritmi per DB transazionali
CLOPE
( Clustering with sLOPE )
Idea di base
Misurare la qualità di un cluster attraverso una funzione di
similarità globale basata sul rapporto altezza/larghezza
dell’istogramma del cluster.
Esempio: cluster formato dalle transazioni {ab, abc, acd}
H=2
a
b
c
d
W=4
Più alto è il rapporto H/W, migliore è il cluster perché viene
migliorato l’overlapping intra-cluster.
Algoritmi per DB transazionali - CLOPE
Sia C un cluster, si definiscono:
D(C)
insieme degli item distinti presenti nel cluster;
Occ(i,C) occorrenze dell’item i nel cluster;
S(C)
S(C) 
dimensione dell’istogramma del cluster.
 Occ(i, C)
W(C)  D(C)
iD(C)
S(C)
H(C) 
W(C)
Per un clustering C={C1,…,Ck} la funzione profitto è:
k
k
Profit(C) 
S(C i )
 Ci

2
i 1 W(C i )
k
C
i 1
i
Profit(C) 
S(C i )
 Ci

r
i 1 W(C i )
k
C
i 1
i
Si introduce il parametro r detto repulsione usato per controllare il livello di
similarità intra-cluster
Algoritmi per DB transazionali - CLOPE
Algoritmo
/* Fase 1 - Initialization */
1: while not end of the database file
2: read the next transaction 〈t,unknown〉;
3: put t in an existing cluster or a new
cluster Ci that maximize profit;
4: write 〈t, i〉 back to database;
/* Fase 2 - Iteration */
5: repeat
6: rewind the database file;
7: moved = false;
8: while not end of the database file
9:
read 〈t, i〉;
10:
move t to an existing cluster or new
cluster Cj that maximize profit;
11:
if Ci ≠ Cj then
12:
write 〈t, j〉;
13:
moved = true;
14: until not moved;
Occupazione di memoria: nella RAM vengono
memorizzati solo la transazione corrente e alcune
informazioni (cluster feature) per ogni cluster come
numero di transazioni (N), numero di item distinti (W),
le occorrenze per ciascun item (occ) e la dimensione
del cluster (S).
Calcolo del profitto: è possibile individuare il miglior
cluster in cui inserire una transazione attraverso la
funzione DeltaAdd che calcola, utilizzando le
clustering feature, l‘aumento relativo della funzione
Profit
1:
2:
3:
4:
5:
6:
7:
int DeltaAdd(C, t, r) {
S_new = C.S + t.ItemCount;
W_new = C.W;
for (i = 0; i < t.ItemCount; i++)
if (C.occ[t.items[i]] == 0) ++W_new;
return S_new*(C.N+1)/(W_new)r-C.S*C.N /(C.W)r;
}
Algoritmi per DB transazionali - CLOPE
Vantaggi
Rapidità
• Complessità: O(N x K x A)
Bassa occupazione di memoria
• Database con 10.000 item e 1.000 cluster possono
essere memorizzati in 40 MB
Efficienza
• Qualità del clustering molto vicina a quella di
algoritmi come ROCK e scarsa sensibilità all’ordine
delle transazioni
Algoritmi per DB transazionali - CLOPE
Applicazione con WEKA
L’algoritmo è attivo solo se il dataset caricato è composto di
attributi categorici. L’unico parametro da introdurre è la
repulsione.
Per provare l’algoritmo con il dataset di prova (Iris), è stato
applicato un filtro per discretizzare gli attributi (10 bin
equi-frequenza) e renderli binari.
Algoritmi per DB transazionali - CLOPE
Risultati
Selezionati solo gli attributi sul petalo
e repulsione a 2.5
Tutti gli attributi selezionati e
repulsione a 2.8
CLOPE clustering results
===============================================
Clustered instances: 150
Clustered Instances
0
46 ( 31%)
1
57 ( 38%)
2
42 ( 28%)
3
5 ( 3%)
CLOPE clustering results
===============================================
Clustered instances: 150
Clustered Instances
0
49 ( 33%)
1
54 ( 36%)
2
46 ( 31%)
4
1 ( 1%)
Class attribute: class
Classes to Clusters:
0 1 2 3 <-- assigned to cluster
46 0 0 4 | Iris-setosa
0 49 1 0 | Iris-versicolor
0 8 41 1 | Iris-virginica
Class attribute: class
Classes to Clusters:
0 1 2 4 <-- assigned to cluster
49 1 0 0 | Iris-setosa
0 48 2 0 | Iris-versicolor
0 5 44 1 | Iris-virginica
Cluster 0 <-- Iris-setosa
Cluster 1 <-- Iris-versicolor
Cluster 2 <-- Iris-virginica
Cluster 3 <-- No class
Cluster 0 <-- Iris-setosa
Cluster 1 <-- Iris-versicolor
Cluster 2 <-- Iris-virginica
Cluster 4 <-- No class
Incorrectly clustered instances :
14.0
9.3333 %
Incorrectly clustered instances :
9.0
6
%
Algoritmi per DB transazionali - CLOPE
Applicazione al Dataset “Voting”
GRAZIE PER L’ATTENZIONE