“Association mining”
Salvatore Orlando
Data Mining - S. Orlando
1
Cos’è l’association mining
 Identifica frequenze/collegamenti/correlazioni/causalità
tra insiemi di item (articoli) in database transazionali
– Ogni transazione contiene una lista di item
– Es.: gli acquisti fatti dai vari clienti sono memorizzati come
transazione nel database di un negozio

Esempi:
–
Forma della regola:
“Body Head [support, confidence]”.
compra(x, “pannolini”)  compra(x, “birra”) [0.5%, 60%]
– laurea(x, “Informatica”) ^ esame(x, “DB”) 
voto(x, “100110”) [1%, 75%]
–

Applicazioni:
–
Basket data analysis, cross-marketing, catalog design, clustering,
classification, etc.
Data Mining - S. Orlando
2
Regole associative: concetti base
 Dati:
– (1) database di transazioni
– (2) ogni transazioni è una lista di articoli (acquistati da un cliente
in una visita al supermercato)
– I = {i1 , i2 , …,in} è un insieme di item distinti
– Una transazione T è un sottoinsieme di I, T  I.
– D, il database, è un insieme di transazioni
 Trova: tutte le regole che correlano la presenza di un insieme di
articoli con quello di un altro insieme di articoli
– Una regola associativa ha la forma: A->B,
• dove A  I, B  I, e A∩B =
– Es.: il 98% della gente che acquista pneumatici e accessori per auto
richiede anche di effettuare manutenzioni periodiche dell’auto
Data Mining - S. Orlando
3
Esempio di dataset transazionale e MBA
Market-Basket transactions
TID
Items
1
Bread, Milk
2
3
4
5
Bread, Diaper, Beer, Eggs
Milk, Diaper, Beer, Coke
Bread, Milk, Diaper, Beer
Bread, Milk, Diaper, Coke
Market Basket Analysis (MBA)
Esempio di regola associativa:
TID Bread Milk Diaper Beer Eggs Coke
1
1
1
0
0
0
0
2
1
0
1
1
1
0
3
0
1
1
1
0
1
4
1
1
1
1
0
0
5
1
1
1
0
0
1
Data Mining - S. Orlando
4
Misure di interesse delle regole
Clienti che
comprano
entrambi
Clienti che
comprano
pannolini
 Esempio: pannolini  birra
 Trova tutte le regole X  Z con
confidenza e supporto minimo
– Supporto, s, è la probabilità che una
transazione contenga {X  Z}
• Sup (X  Z ) = Probabilità(X  Z )
Clienti che
comprano birra
D
– Confidenza, c, è la probabilità
condizionale che una transazione che
include X contenga anche Z
• Conf (X  Z ) = Probabilità(Z | X )
Transaction ID
2000
1000
4000
5000
Items Bought
A,B,C
A,C
A,D
B,E,F
Per
50% : supporto minimo
50% : confidenza minima
abbiamo che
– A  C (50%, 66.6%)
– C  A (50%, 100%)
Data Mining - S. Orlando
5
Calcolo di regole frequenti e confidenti
 Sia X un itemset, e sia (X)  |D| il numero di transazioni in D che
contengono X
Esempio:
TID
1
2
3
4
5
{Pannolini,Latte} s,c Birra
Items
Pane, Latte
Birra, Pane, Pannolini, Uova
Birra, Coca, Pannolini, Latte
Birra, Pane, Pannolini, Latte
Coca, Pane, Pannolini, Latte
Association rule: Xs,c y
Support: s =(Xy) / |D|
Confidence:
c = (Xy) / (X)
s = ({Pannolini,Latte,Birra}) / Tot_trans =
= 2/5 = 0.4 = 40%
c = ({Pannolini,Latte,Birra}) /
({Pannolini,Latte}) =
= 2/3 = 0.66 = 66 %
Il supporto è la probabilità che un certo
itemset appaia nelle transazioni del dataset.
s=P({Pannolini,Latte, Birra})
La confidenza è una probabilità condizionata
c=P({Pannolini,Latte, Birra} |
{Pannolini,Latte}) Data Mining - S. Orlando 6
Estrazione di Regole Associative: Applicazione 1
 Marketing e Promozione delle Vendite:
– Supporre che sia stata scoperta la regola
{Coca, … } --> {Patatine}
– Patatine come conseguenza => Regola può essere
impiegata per capire cosa può essere usato per
promuovere le vendite di patatine.
Coca nell’antecedente => Regola può essere usata per
vedere le vendite di quali prodotti sarebbero interessati
se il negozio smettesse di vendere Coca.
Data Mining - S. Orlando
7
Estrazione di Regole Associative: Applicazione 2
 Gestione degli scaffali nel supermercato
– Scopo: Identificare gli articoli che sono comprati assieme da un
numero sufficientemente grande di clienti
– Approccio: Processare i dati collezionati con gli scanner di
codici a barre per trovare dipendenze tra gli articoli.
– Una regola classica:
• Se un cliente acquista pannolini e latte, allora con alta probabilità
acquisterà birra
• Quindi, non bisogna essere sorpresi se troviamo pacchi da 6 birre
disposti negli scaffali a fianco dei pannolini! 
Data Mining - S. Orlando
8
Estrazione di Regole Associative: Applicazione 3
 Gestione dell’inventario:
– Scopo: Un’azienda di riparazione di piccoli elettrodomestici ha
necessità di:
• anticipare la natura delle riparazioni dei prodotti richiesti dai clienti
• mantenere i veicoli (usati dai riparatori) equipaggiati con i pezzi di
ricambio giusti, questo per ridurre i numeri delle visite alle
abitazioni dei clienti
– Approccio: Processa i dati sugli strumenti e parti richieste nelle
precedenti riparazioni presso le varie visite presso i clienti, e
scopri le co-occorrenze dei pattern
Data Mining - S. Orlando
9
Tipi di analisi associative

Boolean vs. quantitative associations (Dipende dal tipo di valori
analizzati)
buys(x, “SQLServer”) ^ buys(x, “DMBook”) buys(x, “DBMiner”)
[0.2%, 60%]
– age(x, “30..39”) ^ income(x, “42..48K”) buys(x, “PC”) [1%, 75%]
–

Single dimension vs. multiple dimensional associations (vedi il
secondo esempio di sopra)

Single level vs. multiple-level analysis
–

Che tipo di birra è associata con che marca di pannolini?
Varie estensioni
–
Correlazione, analisi di causalità
•
Associazioni non necessariamente implica correlazione o causalità
–
Maxpatterns e closed itemsets
– Vincoli
•
Es: piccole svendite (sum < 100) danno luogo a grandi acquisti (sum >
1,000)?
Data Mining - S. Orlando
10
Mining di regole booleane a singola-dimensione
Transaction ID
2000
1000
4000
5000
Items Bought
A,B,C
A,C
A,D
B,E,F
Min. support 50%
Min. confidence 50%
Frequent Itemset Support
{A}
75%
{B}
50%
{C}
50%
{A,C}
50%
Per la regola A  C:
support = support({A  C}) = 50%
confidence = support({A  C}) / support({A}) = 66.6%
Il principio Apriori:
Ogni sottoinsieme di un itemset frequente DEVE essere
frequente
Data Mining - S. Orlando
11
Generazione delle regole dagli itemset frequenti
Esempio di regole:
TID
Items
1
Bread, Milk
2
3
4
5
Bread, Diaper, Beer, Eggs
Milk, Diaper, Beer, Coke
Bread, Milk, Diaper, Beer
Bread, Milk, Diaper, Coke
{Milk,Diaper}  {Beer} (s=0.4, c=0.67)
{Milk,Beer}  {Diaper} (s=0.4, c=1.0)
{Diaper,Beer}  {Milk} (s=0.4, c=0.67)
{Beer}  {Milk,Diaper} (s=0.4, c=0.67)
{Diaper}  {Milk,Beer} (s=0.4, c=0.5)
{Milk}  {Diaper,Beer} (s=0.4, c=0.5)
Osservazione:
• Tutte le regole di sopra fanno
riferimento allo stesso itemset
frequente (s=40%):
{Milk, Diaper, Beer}
• Le regole così ottenute hanno
supporto identico ma
possono avere confidenza differente
Data Mining - S. Orlando
12
Mining frequent itemset: il passo chiave dell’
association mining
 Trova i frequent itemsets: gli insiemi di item che hanno supporto
minimo
– Un sottoinsieme di un frequent itemset è anch’esso frequente
(proprietà anti-monotonica)
• Se {AB} è un frequent itemset, sia {A} e sia {B} sono frequenti
• ({A})  ({AB})
e
({B})  ({AB})
– Sia I un itemset. Se un sottoinsieme di I non è frequente, allora I non è
frequente
• Se {A} NON è un frequente, allora anche {A,B} NON è frequente
 I frequent itemsets possono essere individuati iterativamente
– Prima quelli di cardinalità 1 (1-itemset)
– Poi quelli di cardinalità 2 (2-itemset)
….
– Infine quelli di cardinalità k (k-itemset)
 Usa i frequent itemsets per generare le regole associative
Data Mining - S. Orlando
13
Il reticolo degli itemsets
null
A
B
C
D
E
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
ABCD
ABCE
ABDE
ABCDE
ACDE
BCDE
Power Set di un
insieme di d items (d=5
in questo caso)
Ci sono 2d itemset
possibili
Data Mining - S. Orlando
14
Come calcolare gli itemset frequenti
 Approccio naive:
– Ogni itemset nel reticolo è un candidato itemset frequente
– Conta il supporto di ogni candidato con la scansione di tutte le
transazioni del database
Transactions
N
TID
1
2
3
4
5
Candidates
Items
Bread, Milk
Bread, Diaper, Beer, Eggs
Milk, Diaper, Beer, Coke
Bread, Milk, Diaper, Beer
Bread, Milk, Diaper, Coke
M
– Complessità ~ O(NM) => costosa poiché M = 2d !!!
Data Mining - S. Orlando
15
Approcci per il mining degli Itemset Frequenti
 Ridurre il numero di candidati (M)
– Ricerca completa: M=2d
– Usa invece l’euristica Apriori per ridurre M
 Redurre il numero di transazioni (N)
– Ridurre la dimensione N via via che la dimensione k degli
itemset aumenta
– Dataset pruning
 Ridurre il numero di confronti necessari (NM)
– Usa strutture dati efficienti/compresse per memorizzare
candidati/frequenti/transazioni
– Lo scopo è evitare di effettuare il matching di ogni candidato
contro ciascuna transazione
Data Mining - S. Orlando
16
Usare il principio di Apriori per il pruning dei
candidati
null
Se un itemset è NON
frequente, allora tutti i suoi
superset devono anche
essere NON frequenti
Abbiamo
scoperto
che è NON
frequente
A
B
C
D
E
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
ABCD
Super-itemset
eliminati (pruned),
e non controllati
ABCE
ABDE
ACDE
BCDE
ABCDE
Data Mining - S. Orlando
17
L’algoritmo Apriori
 Ck è l’insieme dei candidati (k-itemset) all’iterazione k
 Il supporto dei candidati deve essere calcolato per generare Lk
 Lk è l’insieme dei frequent itemset (k-itemset) all’iterazione k
 Si tratta di un sottoinsieme di Ck
 Assieme ad ogni itemset in Lk, viene restituito anche il supporto
relativo
 Nota: L sta per large. Nell’articolo originale di Apriori, gli itemset
frequenti erano chiamati “large itemset”
 Gen Step:
Ck+1 è generato facendo il join di Lk con sé stesso, e
prendendo solo, tra gli itemset otenuti, quelli di lunghezza k+1 che
contengono item distinti
 Prune Step: Un k-itemset non può essere frequente, e quindi
non sarà un candidato, se qualcuno dei suoi sottoinsiemi non è
frequente
Data Mining - S. Orlando
18
L’algoritmo Apriori
 Pseudo-code:
Ck: Candidate itemset of size k
Lk : frequent itemset of size k
L1 = {frequent items};
for (k = 1; Lk !=; k++) do begin
Ck+1 = candidates generated from Lk;
for each transaction t in database D do
increment the count of all candidates in Ck+1
that are contained in t
Lk+1 = candidates in Ck+1 with min_support
end
return k Lk
Data Mining - S. Orlando
19
L’algoritmo Apriori: un esempio (minsup = 2)
itemset sup.
2
C1 {1}
{2}
3
Scan D {3}
3
{4}
1
{5}
3
Database D
TID
100
200
300
400
Items
134
235
1235
25
C2 itemset sup
L2 itemset sup
2
2
3
2
{1
{1
{1
{2
{2
{3
C3 itemset
{2 3 5}
Scan D
{1 3}
{2 3}
{2 5}
{3 5}
2}
3}
5}
3}
5}
5}
1
2
1
2
3
2
itemset sup.
L1
{1}
2
{2}
3
{3}
3
{5}
3
C2 itemset
{1 2}
Scan D
{1
{1
{2
{2
{3
3}
5}
3}
5}
5}
L3 itemset sup
{2 3 5} 2
Data Mining - S. Orlando
20
Apriori: visita Breadth first del reticolo
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
21
Genera i Candidati di dimensione 1
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
22
Conta i supporti dei Candidati di dim. 1
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
23
Genera i Candidati di dimensione 2
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
24
Conta i supporti dei Candidati di dim. 2
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
25
Pruna gli itemset infrequenti
a
ac
ad
b
c
d
e
ae
bc
bd
be
cd
ce
de
acd
ace
ade
bcd
bce
bde
cde
acde
bcde
Data Mining - S. Orlando
26
Genera i Candidati di dimensione 3
a
ac
ad
b
c
d
e
ae
bc
bd
be
cd
ce
de
acd
ace
ade
bcd
bce
bde
cde
acde
bcde
Data Mining - S. Orlando
27
Conta i supporti dei Candidati di dim. 3
a
ac
ad
b
c
d
e
ae
bc
bd
be
cd
ce
de
acd
ace
ade
bcd
bce
bde
cde
acde
bcde
Data Mining - S. Orlando
28
Pruna gli itemset infrequenti
a
ac
ad
b
c
d
ae
bc
bd
acd
ace
ade
e
be
cd
ce
de
bce
bde
cde
acde
Data Mining - S. Orlando
29
Genera i Candidati di dimensione 4
a
ac
ad
b
c
d
ae
bc
bd
acd
ace
ade
e
be
cd
ce
de
bce
bde
cde
acde
Data Mining - S. Orlando
30
Conta i supporti dei Candidati di dim. 3
a
ac
ad
b
c
d
ae
bc
bd
acd
ace
ade
e
be
cd
ce
de
bce
bde
cde
acde
Data Mining - S. Orlando
31
Passo di generazione dei candidati
 Supponi che
– gli item all’interno degli itemset siano ordinati,
– gli itemset in Lk-1 siano ordinati secondo l’ordine lessicografico indotto
 Step 1: self-joining Lk-1
insert into Ck
all pairs (p, q) Lk-1
where p.item1=q.item1, ……, p.itemk-2=q.itemk-2,
p.itemk-1 < q.itemk-1
(p e q condividono un prefisso comune di lunghezza k-2)
(la condizione p.itemk-1 < q.itemk-1 assicura che non vengano prodotti duplicati)
 Step 2: pruning
forall itemsets c in Ck do
forall (k-1)-subsets s of c do
if (s is not in Lk-1) then delete c from Ck
Data Mining - S. Orlando
32
Esempio di generazione dei candidati
 L3={abc, abd, acd, ace, bcd}
 Self-joining: L3*L3
– abcd da abc e abd
– acde da acd e ace
 Pruning:
– acde è rimosso perché ade non è in L3
 C4={abcd}
Data Mining - S. Orlando
33
Conteggio del supporto dei candidati
 Perchè contare il supporto dei candidati potrebbe essere
problematico?
– Il numero di candidati potrebbe essere enorme
– Una transazione potrebbe contenere molti candidati
 Metodo:
– Itemsets Candidati memorizzati in un hash-tree
– La profondità massima dell’hash-tree dipende dalla lunghezza k
dei candidati memorizzati
– Nodi foglia dell’hash-tree contengono una lista di itemset
candidati, con i contatori associati
– Nodi interni contengono un hash table
– Funzione di subsetting: trova tutti i candidati contenuti in una
transazione visitando l’hash tree
Data Mining - S. Orlando
34
Metodi per migliorare l’efficienza di Apriori
 Hash-tree per
memorizzare i candidati:
– Albero ternario, con
funzione hash di modulo
sul valore degli item
– Foglie memorizzano lista
di candidati (ordered sets)
– Subsetting check sulla
radice dell’albero, data la
transazione {1,2,3,5,6}
Data Mining - S. Orlando
35
Hash-tree per memorizzare i candidati
Hash Function
1,4,7
Candidate Hash Tree
Nota che 4 e 7 appaiono
anche in questi bin
3,6,9
2,5,8
234
567
145
136
345
Hash on
1, 4 or 7
124
457
125
458
159
356
357
689
367
368
Data Mining - S. Orlando
36
Hash-tree per memorizzare i candidati
Hash Function
1,4,7
Candidate Hash Tree
3,6,9
2,5,8
234
567
145
136
345
Hash on
2, 5 or 8
124
457
125
458
159
356
357
689
367
368
Data Mining - S. Orlando
37
Hash-tree per memorizzare i candidati
Hash Function
1,4,7
Candidate Hash Tree
3,6,9
2,5,8
234
567
145
136
345
Hash on
3, 6 or 9
124
457
125
458
159
356
357
689
367
368
Data Mining - S. Orlando
38
Operazione di Subsetting su una transazione
Data una transazione t, quali
sono i possibili sottoinsiemi di
size 3?
Transaction, t
1 2 3 5 6
Level 1
1 2 3 5 6
2 3 5 6
3 5 6
Level 2
12 3 5 6
13 5 6
123
125
126
135
136
Level 3
15 6
156
23 5 6
235
236
25 6
256
35 6
356
Subsets of 3 items
Data Mining - S. Orlando
39
Operazione di Subsetting su una transazione
•
Controllo di subsetting ricorsivo
Hash Function
1 2 3 5 6 transaction
1+ 2356
2+ 356
1,4,7
3+ 56
234
567
145
136
345
124
457
125
458
159
356
357
689
367
368
3,6,9
2,5,8
Per evitare duplicati,
cerco sempre insiemi
ordinati di 3 elementi
1 combinato con
2, o 3, o 5, ma non
con 6
non esiste {1,6,x}, x>6,
nella transazione !!!
Data Mining - S. Orlando
40
Operazione di Subsetting su una transazione
Hash Function
1 2 3 5 6 transaction
1+ 2356
2+ 356
12+ 356
1,4,7
3+ 56
3,6,9
2,5,8
13+ 56
234
567
15+ 6
145
136
345
124
457
125
458
159
356
357
689
367
368
Data Mining - S. Orlando
41
Operazione di Subsetting su una transazione
Hash Function
1 2 3 5 6 transaction
1+ 2356
2+ 356
12+ 356
1,4,7
3+ 56
3,6,9
2,5,8
13+ 56
234
567
15+ 6
145
136
345
124
457
125
458
159
356
357
689
367
368
La transazione contiene ben 11 di tutti i 15
candidati
Data Mining - S. Orlando
42
Metodi per migliorare l’efficienza di Apriori
 Hash-based itemset counting:
– All’iterazione k-1 provo a prevedere gli itemset che finiranno in Ck
• Scopo: aumentare la capacità di pruning per ridurre la dimensione di Ck
– I k-itemset presenti in una transazione sono mappati, tramite una
funzione hash, in una tabella hash relativamente piccola
 meno contatori di Ck
– Tutti gli k-itemset la cui locazione hash corrispondente è al di sotto del
supporto minimo
• Non possono essere frequenti
• Possono essere prunati da Ck

Esempio: All’iterazione k=1, crea la tabella hash H2
– hash function: h(x; y) = (x * 10 + y) mod 7
– min_supp = 3
Data Mining - S. Orlando
43
Metodi per migliorare l’efficienza di Apriori
 Transaction pruning: Una transazione che non contiene nessun kitemset frequente, è inutile nelle successione scansione del
database
 Sampling: mining su un sottoinsieme dei dati. Perdiamo in
accuratezza ma miglioriamo in efficienza
 Partitioning: Un itemset che è frequente nel database D deve essere
frequente in almeno una delle partizioni di D (relativamente al size
della partizione).
Purtroppo un itemset frequente in una partizione di D potrebbe
essere NON frequente nel database completo D.
Data Mining - S. Orlando
44

D1, D2, D3

Se X è frequent, allora:
supp(X) = suppD1(X) + suppD2(X) + suppD3(X)
i, suppDi(X) < s% |Di|
A B

>= s% (|D1| +|D2| +|D3|)
X è infrequente globalmente
(per def. è equivalente a:
¬ A  B)
A  B è equivalente a:
¬ B  ¬ A (che per def. è equiv. a B  ¬ A)
X è frequente globalmente  i, suppDi(X) >= s% |Di|
Data Mining - S. Orlando
45
Generazione delle regole
 Algoritmo non ottimizzato:
c è frequente per
definizione
for each frequent itemset l do
for each subset c of l do
if (support(l) / support(l-c)  minconf) then
output rule (l-c)  c, with
confidence = support(l) / support(l-c)
support = support(l);
Data Mining - S. Orlando
46
Generazione delle regole (2)
 Considera la regola (l-c)  c
l
 Se c1  c, allora
c
c1
l – c  l - c1
support(l - c)  support(l – c1)
support(l)/support(l - c1)  support(l)/support(l - c)
conf((l - c1)  c1)  conf((l - c)  c)
 Quindi, se una conseguenza c genera una regola valida, usando
tutti i sottoinsiemi c1 di c generiamo regole valide (con confidenza
maggiore)  proprietà di antimonotonia
 Possiamo quindi usare questa proprietà per effettuare il pruning
delle regole candidate, generando prima le regole con le
conseguenze più corte (a livelli):
– Considera un itemset ABCDE.
– se ACDE  B e ABCE  D sono le sole regole valide con singola
conseguenza (cioè con confidenza minima), allora ACE  BD è la sola
altra regola che deve essere testata.
– se ACD  BE fosse valida, dovrebbe essere valida anche se ABCD  E
Data Mining - S. Orlando
47
Colli di bottiglia di Apriori
 I concetti base di Apriori:
– Visita a livelli dello spazio di ricerca
– Usa i (k – 1)-itemset per generare i k-itemset candidati
– Ad ogni livello, scandisci il database, usa pattern matching per
aggiornare i contatori dei k-itemsets candidati
– Approccio Counting-based
 Colli di bottiglia
– I candidati possono essere tantissimi:
• 104 1-itemset frequenti genereranno 107 2-itemset candidati
• Per scoprire un pattern frequente di dimensione 100,
es. {a1, a2, …, a100}, è necessario contare 2100  1030 candidati.
– Scansioni multiple del database:
• Necessari (n +1 ) scansioni, dove n è la lunghezza del pattern più
lungo
Data Mining - S. Orlando
48
Mining dei pattern frequenti senza generazione
dei candidati
 Comprimi il database in una strutura dati compatta:
Frequent-Pattern tree (FP-tree)
– Struttura dati TRIE, solitamente utile per memorizzare stringhe ed
effettuare ricerche
– FP-tree è compresso, ma completo per l’estrazione dei pattern frequenti
con i relativi supporti
– Si riducono le scansioni del database
 Metodo efficiente basato sull’ FP-tree per effettuare il mining dei
pattern frequenti
– Metodo divide-and-conquer: decomponiamo il task completo in altri più
piccoli
– Si evita la generazione dei candidati
Data Mining - S. Orlando
49
Costruzione dell’FP-tree a partire dal DB
TID
100
200
300
400
500
Items bought
(ordered) frequent items
{f, a, c, d, g, i, m, p}
{f, c, a, m, p}
{a, b, c, f, l, m, o}
{f, c, a, b, m}
{b, f, h, j, o}
{f, b}
{b, c, k, s, p}
{c, b, p}
{a, f, c, e, l, p, m, n}
{f, c, a, m, p}
Passi:
1. Scandisci il database per
trovare gli 1-itemset
frequenti
2. Ordina gli items frequenti in
ordine decrescente
3. Scandisci il DB nuovamente,
e costruisci l’ FP-tree
min_support = 0.5
{}
Header Table
Item frequency head
f
4
c
4
a
3
b
3
m
3
p
3
f:4
c:3
c:1
b:1
a:3
b:1
p:1
m:2
b:1
p:2
m:1
Data Mining - S. Orlando
50
Costruzione FP-tree
Transaction
Database
TID
1
2
3
4
5
6
7
8
9
10
Items
{A,B}
{B,C,D}
{A,C,D,E}
{A,D,E}
{A,B,C}
{A,B,C,D}
{B,C}
{A,B,C}
{A,B,D}
{B,C,E}
null
Letura TID=1:
A:1
B:1
Lettura TID=2:
null
A:1
B:1
B:1
C:1
D:1
Data Mining - S. Orlando
51
Costruzione FP-tree
TID
1
2
3
4
5
6
7
8
9
10
Items
{A,B}
{B,C,D}
{A,C,D,E}
{A,D,E}
{A,B,C}
{A,B,C,D}
{B,C}
{A,B,C}
{A,B,D}
{B,C,E}
Header table
Item
Pointer
A
B
C
D
E
Transaction
Database
null
B:3
A:7
B:5
C:1
C:3
D:1
C:3
D:1
D:1
D:1
D:1
E:1
E:1
Puntatori utili per estrarre gli
itemset frequenti
Data Mining - S. Orlando
52
Proprietà dell’FP-tree
 Preserva l’informazione completa per estrarre i pattern frequenti
 Riduzione delle informazioni irrilevanti — gli item non frequenti
sono eliminati
 Ordinati in ordine decrescente di frequenza: item più frequenti
hanno più probabilità di essere condivisi
 L’FP-tree è solitamente più piccolo del database originale (senza
contare link e contatori)
– Esempio: per connect-4 DB, rapporto di compressione maggiore di 100
Data Mining - S. Orlando
53
Mining i pattern frequenti tramite l’FP-tree
 Idea generale
– In maniera ricorsiva, fai crescere i pattern frequenti usando l’FPtree
– Visita Depth-First del reticolo
Data Mining - S. Orlando
54
FIM attraverso una visita depth first

Supponi di avere un dataset che contenga gli item
– a, b, c, d, e


Conta il supporto degli item singoli
Rimuovi gli item non frequenti

Trova tutti gli itemset frequenti che contengono a
– possiamo rimuovere proiettare il dataset rimuovendo le trans. che non
contengono a

Trova tutti gli itemset frequenti che contengono b ma non a
– possiamo rimuovere proiettare il dataset rimuovendo le trans. che non
contengono b
– rimuovendo anche a da ogni trans. restante

Trova tutti gli itemset frequenti che contengono c ma non a e b
– possiamo rimuovere proiettare il dataset rimuovendo le trans. che non
contengono b
– rimuovendo anche a e b da ogni trans. restante

…

NOTA: anche se nell’esempio usiamo l’ordine lessicale tra gli item per
determinare l’ordine della visita, qualsiasi ordine potrebbe essere usato.
Un ordine spesso utilizzato è quello indotto dalla frequenze degli item,
considerando per primi gli item meno/più frequenti
Data Mining - S. Orlando
55
FIM attraverso una visita depth first
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
56
Trova itemset frequenti contenenti “a”
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
57
Trova itemset frequenti contenenti “a” ma “non b”
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
58
… contenenti “c” ma “non a” e “non b”
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
59
… contenenti “d” ma “non a”, “non b”, e “non c”
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
60
… contenenti “d” ma “non a, b, c, d”
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
61
Ricorsione: es. per gli itemset contenenti “a”
a
b
c
d
e
ab
ac
ad
ae
bc
bd
be
cd
ce
de
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
abcd
abce
abde
acde
bcde
abcde
Data Mining - S. Orlando
62
Passi di FP-growth
1) Costruisci il conditional pattern base per ciascun item nel’FPtree
 proiezione del database per prepararsi alla visita depth-first
 quando visito per estrarre gli itemset che iniziano per c, ma non
contengono né a e né b, mi è sufficiente un database ridotto
(proiettato), da cui ho rimosso a e b
2) Costruisci il conditional FP-tree da ciascun conditional patternbase
 ogni conditional FP-tree corrisponde alla compressione del
database proiettato (rimuovo gli itemset localmente infrequenti)
3) Passo ricorsivo sui conditional FP-trees
 rispetto al mining degli itemset che iniziano per a, calcolo prima
gli itemset che iniziano per ab, poi quelli che iniziano per ac e non
ab, poi quelli che iniziano per ad …
Data Mining - S. Orlando
63
Passo 1: dall’ FP-tree al Conditional Pattern Base
 A partire dal frequent header table dell’ FP-tree
 Attraversa nell’FP-tree la lista di ciascun item frequente
 Accumula i prefix path di quell’item in modo da formare la
conditional pattern base
Header Table
Item frequency head
f
4
c
4
a
3
b
3
m
3
p
3
{}
Conditional pattern bases
f:4
c:3
c:1
b:1
a:3
b:1
p:1
item
cond. pattern base
c
f:3
a
fc:3
b
fca:1, f:1, c:1
m:2
b:1
m
fca:2, fcab:1
p:2
m:1
p
fcam:2, cb:1
Data Mining - S. Orlando
64
Proprietà importanti per la creazione delle
basi condizionali
 Proprietà dei Node-link
– Per ogni frequent item ai, tutti i possibili frequent pattern che
contengono ai possono essere ottenuti seguendo i link del nodo
ai, iniziando dalla testa della lista di ai nell’FP-tree header
 Proprietà dei prefix path
– Per calcolare i frequent pattern per un nodo ai nel path P
dell’albero (P va dalla radice ad una foglia dell’albero), solo il
prefix sub-path di ai in P deve essere accumulato nella base, e il
suo conteggio di frequenza deve portare lo stesso conteggio del
nodo ai.
Data Mining - S. Orlando
65
Passo 2: costruzione dei conditional FP-tree
 Per ciascuna pattern-base
– Accumula i conteggi per ciascun item nella base
– Costruisci l’FP-tree condizionale includendo solo gli item
frequenti presenti nella pattern-base
• L’item b viene eliminato dall’ m-base perché non frequente
Header Table
Item frequency head
f
4
c
4
a
3
b
3
m
3
p
3
{}
f:4
c:3
c:1
b:1
a:3
b:1
p:1
m-conditional
pattern base:
fca:2, fcab:1
{}

f:3 
m:2
b:1
c:3
p:2
m:1
a:3
Passo 3
All frequent
patterns concerning
m
m,
fm, cm, am,
fcm, fam, cam,
fcam
m-conditional FP-tree
Data Mining - S. Orlando
66
Basi e FP-tree condizionali
Item
Conditional pattern-base
Conditional FP-tree
p
{(fcam:2), (cb:1)}
{(c:3)}|p
m
{(fca:2), (fcab:1)}
{(f:3, c:3, a:3)}|m
b
{(fca:1), (f:1), (c:1)}
Empty
a
{(fc:3)}
{(f:3, c:3)}|a
c
{(f:3)}
{(f:3)}|c
f
Empty
Empty
Data Mining - S. Orlando
67
Passo 3: ricorsione
 In modo ricorsivo, riapplica FP-growth agli FP-tree condizionali
{}
Cond. pattern base di “am”: (fc:3)
f:3
{}
c:3
f:3
am-conditional FP-tree
c:3
a:3
m-conditional FP-tree
{}
Cond. pattern base of “cm”: (f:3)
f:3
cm-conditional FP-tree
{}
Cond. pattern base of “cam”: (f:3)
f:3
cam-conditional FP-tree
Data Mining - S. Orlando
68
Generazione a partire da un FP-tree a singolo path
 Supponi che un FP-tree T ha un singolo path P
 L’insieme completo dei frequent pattern di T può essere
generato enumerando tutte le combinazioni dei sub-paths di P
{}
f:3
c:3

a:3
m-conditional FP-tree
Tutti i frequent
patterns
relativi a m
m,
fm, cm, am,
fcm, fam, cam,
fcam
Data Mining - S. Orlando
69
Prestazioni
 Performance
– FP-growth è un ordine di grandezza più veloce di Apriori
 Ragioni
– Non abbiamo candidate generation, e nemmeno candidate test
– Strutture dati compatte
• Solo per alcuni tipi di database, purtroppo
– Si evitano ripetuti scan del database
– L’operazione base diventa il conteggio e la costruzione dell’FPtree
Data Mining - S. Orlando
70
FP-growth: tempo di esecuzione rispetto al supporto
minimo
Data set T25I20D10K
100
D1 FP-grow th runtime
90
D1 Apriori runtime
80
Run time(sec.)
70
60
50
40
30
20
10
0
0
0.5
1
1.5
2
Support threshold(%)
2.5
3
Data Mining - S. Orlando
71
FIM algorithms: formato database
 Database Orizzontale vs. Verticale
– Record orizzontale (transazione):
– Record verticale (tidlist):
Tid: Item0, …, Itemk
Item: Tid0, …, Tidh
Verticale
Orizzontale
Data Mining - S. Orlando
72
FIM algorithms: metodo per calcolare i supporti
 Metodo per calcolare il supporto:
– Count-based
• E’ il metodo usato da Apriori
• Sfrutta un database orizzontale, confrontando le transazioni con i
candidati, incrementando i contatori associati
– Intersection-based
• Sfrutta un database verticale
• Per ogni itemset candidato, interseca (set-intersection) le tidlist
degli item che appaiono nel candidato
• la cardinalità del tidlist risultante dopo le intersezioni corrisponde al
supporto del candidato
Data Mining - S. Orlando
73
Count-based vs Intersection-based
 Come possiamo determinare il supporto dei candidati?
– Apriori è count-based, e usa un dataset orizzontale
– Partition/Eclat è intersection-based, e usa un dataset verticale
Horizontal
Data Layout
Transaction
TID
1
2
3
4
5
6
7
8
9
10
Items
A,B,E
B,C,D
C,E
A,C,D
A,B,C,D
A,E
A,B
A,B,C
A,C,D
B
Vertical Data Layout
A
1
4
5
6
7
8
9
B
1
2
5
7
8
10
C
2
3
4
8
9
D
2
4
5
9
E
1
3
6
TID-list
Data Mining - S. Orlando
74
Intersection-based
A
1
4
5
6
7
8
9

B
1
2
5
7
8
10
C
1
2
5
7
  
ABC  k-way intersection
– Determina il supporto di un k-itemset
1
attraverso il set intersection di k tid-list
atomiche, contando alla fine la
5
cardinalità della lista ottenuta
7
– Vantaggio: bassa occupazione di
memoria
– Svantaggio: lentezza nel conteggio
2-way intersection
– Determina il supporto di un k-itemset attraverso il set
intersection di 2 tid-list associate a due dei suoi
(k-1)-sottoinsiemi frequenti
– Vantaggio: velocissimo conteggio del supporto
Svantaggio: la dimensione di tutte le liste intermedie
può diventare grandissima
AB
1
5
7
8

BC
1
2
5
7

ABC
1
5
7
Data Mining - S. Orlando
75
Frequent Set Counting algorithms
 Spazio di ricerca: P(I), power set di I, |P(I)| = 2|I|
– Spazio di ricerca molto grande, ma la proprietà di Apriori introduce
molto pruning
 DFS
• Depth-First
Search
• in profondità
• non si riesce a
sfruttare
pienamente la
proprietà di
antimonotonia
per il pruning
 BFS
• Breadth-First
Search
• Per livelli, come
l’algoritmo di
Apriori
Data Mining - S. Orlando
76
Classificazione dei vari algoritmi per FSC
Search space:
visiting method
Support:
computing method
Support:
computing method
Apriori
Partition
FP-growth
Eclat
Horizontal DB
Vertical DB
Horizontal DB
Vertical DB
Level-wise, strictly iterative
Divide & conquer, recursive
Data Mining - S. Orlando
77
DCI: Direct Counting & Intersecting
 Algorithm Level-wise (BFS)
 Metodo ibrido per determinare il supporto dei
frequent itemsets
– Count-based durante the prime iterazioni
• Metodo innovative per memorizzare e accedere i candidati per
countare il loro supporto
• Pruning del database orizzontale (disk-stored)
– Intersection-based quando il database è piccolo
abbastanza da stare in memoria principale 
resource-aware
• Trasformazione Orizzontale-a-Verticale
• Intersezione k-way ottimizzata
Data Mining - S. Orlando
78
DCI: fase intersection-based


Quando il database prunato entra in memoria, DCI costruisce
“al volo” un bit-vector database verticale
Grazie alla rappresentazione bit-vector e al pruning, questo
accade molto presto (2o o 3o iterazione)
nk trans
1
0
mk items
Data Mining - S. Orlando
79
DCI: intersezione delle tidlist (bitvector)
 Intersectioni a k-vie
– Intersezione di tidlists associate con singoli item
(atomi)
– Poca memoria, ma troppe intersezioni!
 Intersectioni a 2-vie
– a partire da tidlist associate con frequent (k-1)itemset
– tantissima memoria, ma poche intersezioni!
 DCI  compromesso tra 2-vie e k-vie
– Basato su intersezioni a k-vie di bitvector,
– MA usa cache per memorizzare le intersezioni parziali
corrispondenti ai vari prefissi del candidato corrente
Cache size:
k-2 bitvector di nk bit
Data Mining - S. Orlando
80
DCI: intersezione delle tidlist (bitvector)
C6
Candidato
corrente
Candidato
corrente
i0
3
3
3
i1
5
5
5
i2
i3
i4
i5
11 17 24 31
11 17 24 47
11 17 31 47
Buffer di (k-2) vettori di nk bit
usati per il caching delle
intersezioni intermedie
3&5
3 & 5 & 11
3 & 5 & 11& 17
3 & 5 & 11& 17 & 24
Riuso di questa
Intersezione presente
in cache
Data Mining - S. Orlando
81
DCI: numero delle operazioni AND
Data Mining - S. Orlando
82
DCI: database sparsi vs. densi
 Sparsi:
– I bit-vector sono sparsi
• contengono pochi 1, e lunghe sequenze di 0
– è possibile identificare grandi sezioni di word uguali a zero
– possiamo skip-are queste sezioni durante le intersezioni
 Densi
– Forte correlazione tra gli item più frequenti, i cui bit-vectors
sono densi e molto simili
• contengono pochi 0, e lunghe sequenze di 1
 DCI
– Adotta automaticamente strategie di ottimizzazione differenti per
database densi e sparsi
Data Mining - S. Orlando
83
DCI: migliore di FP-growth

Database denso
•

Pattern
lunghissimi
Apriori è troppo
costoso
•
tempo di
Apriori non
commensurabile
Data Mining - S. Orlando
84
DCI: migliore di FP-growth

Database reale
e sparso
•

Dati di clickstream da un
sito web di
e-commerce
Pattern di
lunghezza media
per supporti
piccoli
Data Mining - S. Orlando
85
Visualizzazione di regole associative
(Forma tabellare)
Data Mining - S. Orlando
86
Visualizzazione: grafico tridimensionale
Data Mining - S. Orlando
87
Visualizzazione: associazioni come link
Data Mining - S. Orlando
88
Regole associative multi-livello
 Gli item spesso associati ad una gerarchia
 Item e relative regole ai livelli più bassi hanno supporti più
bassi
 Regole riguardanti itemset agli appropriati livelli possono
risultare utili e significative
 Possiamo esplorare regole a livelli multipli
– Dato un supporto assoluto, la regola "Outwear  Shoes" può
essere valida anche se "Jackets  Shoes" e “SkiPants  Shoes"
non lo sono
Data Mining - S. Orlando
89
Regole associative multi-livello
 Un approccio top_down, che progressivamente
scende di livello:
– Prima trova regole “più forti” ad alto-livello
milk  bread [20%, 60%]
– Poi trova regole “più deboli” al loro livello più basso:
2% milk  wheat bread [6%, 50%]
Food
bread
milk
skim
Fraser
2%
wheat
white
Sunset
Data Mining - S. Orlando
90
Regole associative multi-livello:
Uniform Support vs. Reduced Support
 Supporto uniforme: stesso supporto minimo per
tutti i livelli della gerarchia
– Un solo valore soglia per il supporto minimo
– Non abbiamo necessità di esaminare itemset che
contengono item i cui antenati non godono del
supporto minimo
• I livelli più bassi non sono sicuramente frequenti
– Se il valore soglia del supporto è
• Troppo alto  perdiamo regole a livello basso
• Troppo basso  generiamo troppe regole di alto livello
 Riduzione progressiva del supporto
– supporto minimo viene via via ridotto ai livelli più
bassi della gerarchia
Data Mining - S. Orlando
91
Regole associative multi-livello: Uniform Support
vs. Reduced Support
 Supporto uniforme
Level 1
min_sup = 5%
Level 2
min_sup = 5%
Milk
[support = 10%]
2% Milk
Skim Milk
[support = 6%]
[support = 4%]
Data Mining - S. Orlando
92
Regole associative multi-livello: Uniform Support
vs. Reduced Support
 Supporto ridotto
Level 1
min_sup = 5%
Level 2
min_sup = 3%
Milk
[support = 10%]
2% Milk
Skim Milk
[support = 6%]
[support = 4%]
Data Mining - S. Orlando
93
Regole associative multi-dimensionali
 Regole a singola dimensione:
– Regole intra-dimension (singolo predicato):
buys(X, “milk”)  buys(X, “bread”)
 Regole multi-dimensionali e quantitative:
– Regole inter-dimension (senza predicati ripetuti)
age(X,”19-25”)  occupation(X,“student”)  buys(X,“coke”)
– Regole hybrid-dimension (predicati ripetuti)
age(X,”19-25”)  buys(X, “popcorn”)  buys(X, “coke”)
 Problemi con dimensioni contenenti attributi quantitativi
– Attr. numerici, ordinati implicitamente
– Da discretizzare staticamente o dinamicamente
Data Mining - S. Orlando
94
Critiche alle misure di supporto/confidenza

Esempio 1:
– Tra 5000 studenti
• 3000 giocano a calcio
• 3750 mangiano cereali
• 2000 sia giocano a calcio e sia mangiano cereali
calcio
cereali
non cereali
sum(col.)


non calcio
sum(row)
2000
1750
3750
1000
250
1250
3000
2000
5000
La regola
gioca a calcio  mangia cereali [40%, 66.7%]
è fuorviante, poiché la percentuale totale di studenti che mangiano cereali
è del 75%, che è più grande del 66.7%
La misura di conf. ignora la prob. ass. della parte destra della regola
La regola
gioca a calcio  non mangia cereali [20%, 33.3%]
è più significativa, anche se ha un supporto e una confidenza minore
Data Mining - S. Orlando
95
Critiche alle misure di supporto/confidenza
 Esempio 2:
– X e Y: correlati positivamente,
– X e Z: correlati negativamente
– Supporto e confidenza di
X Z domina
X 1 1 1 1 0 0 0 0
Y 1 1 0 0 0 0 0 0
Z 0 1 1 1 1 1 1 1
 Abbiamo bisogno di una misura che
metta in evidenza eventi correlati,
Rule
ovvero inter-dipendenti
P( A B)
P( A) P( B)
Support Confidence
X=>Y 25%
50%
X=>Z 37,50%
75%
P(B|A)/P(B) è anche chiamato il lift
della regola A  B
Data Mining - S. Orlando
96
Un’altra misura: Interesse
P( A  B)
P( A) P( B)
 Interesse (lift)
– Si considerano sia P(A) e sia P(B)
– P(A^B)=P(B)*P(A), se A e B sono eventi indipendenti
– A e B sono correlati negativamente se il valore è minore di 1
– A e B sono correlati positivamente se il valore è maggiore di 1
X 1 1 1 1 0 0 0 0
Y 1 1 0 0 0 0 0 0
Z 0 1 1 1 1 1 1 1
Itemset
Support
Interest
X,Y
X,Z
Y,Z
25%
37,50%
12,50%
2
0,9
0,57
Data Mining - S. Orlando
97
Atri tipi di patterns






Maximal and Closed Itemsets
Negative Associations
Indirect Associations
Frequent Subgraphs
Cyclic Association Rules
Sequential Patterns
Data Mining - S. Orlando
98
Maximal frequent itemsets
null
Maximal
Itemsets
A
B
C
D
E
AB
AC
AD
AE
BC
BD
BE
CD
CE
DE
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
ABCD
ABCE
ABDE
Infrequent
Itemsets
ACDE
BCDE
Border
ABCDE
Data Mining - S. Orlando
99
Closed frequent itemsets
 Un itemset X è closed se NON esistono itemset X’ tali che:
– X’ è un superset di X
– Tutte le transazioni che contengono X contengono pure X’
• supp(X) = supp(X’)
A1 …
A10 B1 …
B10 C1 …
C10
111111111100000000000000000000
111111111100000000000000000000
111111111100000000000000000000
111111111100000000000000000000
000000000011111111110000000000
000000000011111111110000000000
000000000011111111110000000000
000000000011111111110000000000
000000000000000000001111111111
000000000000000000001111111111
000000000000000000001111111111
000000000000000000001111111111
Numero degli itemset frequenti:
10 
 3   
k
10
k 1
Numero Closed Itemset = 3
{A1,…,A10}, {B1,…,B10}, {C1,…,C10}
Numero Itemset massimali = 3
Data Mining - S. Orlando
100
Maximal vs Closed Itemsets
TID
Items
1
ABC
2
ABCD
3
BCE
4
ACDE
5
DE
Transaction Ids
null
124
123
A
12
124
AB
12
24
AC
ABC
ABD
ABE
AE
345
D
2
3
BC
BD
4
ACD
245
C
123
4
24
2
Non supportati da
alcuna
transazione
B
AD
2
1234
BE
2
4
ACE
ADE
E
24
CD
34
CE
45
3
BCD
DE
4
BCE
BDE
CDE
4
ABCD
ABCE
ABDE
ACDE
BCDE
ABCDE
Data Mining - S. Orlando
101
Maximal vs Closed Itemsets
Closed but
not maximal
null
Minimum support = 2
124
123
A
1234
B
245
C
345
D
E
Closed and
maximal
12
124
AB
12
ABC
24
AC
123
4
AD
AE
24
2
ABD
ABE
2
BD
4
ACD
3
BC
2
4
ACE
24
BE
ADE
CD
CD
34
CE
45
3
BCD
DE
4
BCE
BDE
CDE
4
2
ABCD
ABCE
ABDE
ACDE
BCDE
# Closed = 10
# Maximal = 5
A  D (s=2, c = 2/3 = 0,66%)
AC  D (s=2, c = 2/3 = 0,66%)
ABCDE
regola non generata se partiamo dai closed
Data Mining - S. Orlando
102
Classificatori basati su regole associative
 Dati su cui costruire il classificatore
– Insieme di record in D classificati, ovvero contenenti un attributo
categorico yY, che determina la classe di appartenenza
 Trasformiamo il dataset per poter applicare un algoritmo Apriori-like
– Ogni record deve diventare una transazione che contiene un insieme di
item  I
– Gli attributi categorici vengono mappati su insiemi di interi consecutivi
– Gli attributi continui sono discretizzati e trasformati come quelli
categorici
– Ogni record diventa una ennupla di item distinti appartenenti a I, dove
ogni item è una coppia (Attribute, Integer-value)
 Le regole estratte (CAR=Class Association Rule) con
supporto/confidenza minimi hanno quindi forma
– condset  y
– Dove condset è un insieme di item (Attribute, Integer-value)
Data Mining - S. Orlando
103
Classificatori basati su regole associative
 Una CAR ha confidenza c
– se il c% dei campioni in D che contengono condset contengono
anche y (ovvero appartengono alla classe y)
 Una CAR ha supporto s
– se l’ s% dei campioni in D contengono sia condset e sia y (ovvero
contengono condset ed appartengono anche alla classe y )
Data Mining - S. Orlando
104
Classificatori basati su CAR in dettaglio
 1° passo (generazione delle CAR)
– Algoritmo iterativo (come Apriori) che ricerca k-ruleitems frequenti
(CAR frequenti il cui condset contiene K item)
– Scansione multipla del database
– Cerca ad ogni iterazione k = 1, 2, 3, … i k-ruleitems frequenti
– La conoscenza dei k-ruleitems frequenti viene usata per generare i
(k+1)-ruleitems candidati
Data Mining - S. Orlando
105
Classificatori basati su CAR in dettaglio
 2 ° passo (generazione del Classificatore)
– Ricerca delle CAR più accurate
– Metodo euristico, basato su un ordinamento tra CAR
– Una regola ri precede una regola rj (ri < rj) se
• La confidenza di ri è più grande di rj
• La confidenza è la stessa, ma ri ha un supporto più grande
• La confidenza e il supporto delle due regole sono uguali, ma ri è
stata generata prima di rj
– Al termine l’algoritmo seleziona un insieme di CAR ordinate che
coprono tutti i campioni in D
 Uso del classificatore
– Nel classificare un nuovo campione, si usa l’ordine tra le CAR
• Si sceglie la prima regola il cui condset soddisfa il campione.
– E’ necessaria una regola di default, a precedenza minima, che specifica
una classe di default
• Serve per classificare nel caso in cui nessuna regola soddisfa il nuovo
campione da classificare
 Buoni risultati sia in velocità e sia in accuratezza rispetto a C4.5
Data Mining - S. Orlando
106
Conclusioni
 Association rule mining
– Probabilmente costituisce il contributo più notevole al KDD da
parte di ricercatori su DB e algoritmi
– Moltissimi algoritmi sono stati pubblicati
– Usato anche come analisi di base per alg. di clustering e
classificazione
 Direzioni di ricerca interessanti
– Analisi delle associazioni in altri tipi di dati: spaziali, multimedia,
serie temporali, grafi, etc.
Data Mining - S. Orlando
107