1 data mining - s. orlando “association mining” salvatore orlando
TRANSCRIPT
![Page 1: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/1.jpg)
1Data Mining - S. Orlando
“Association mining”
Salvatore Orlando
![Page 2: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/2.jpg)
2Data Mining - S. Orlando
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 ead [support, confidence]”.
– compra(x, “pannolini”) compra(x, “birra”) [0.5%, 60%]– laurea(x, “Informatica”) ^ esame(x, “DB”)
voto(x, “100110”) [1%, 75%]
Applicazioni:– Basket data analysis, cross-marketing, catalog design, clustering,
classification, etc.
![Page 3: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/3.jpg)
3Data Mining - S. Orlando
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
![Page 4: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/4.jpg)
4Data Mining - S. Orlando
Esempio di dataset transazionale e MBA
Market-Basket transactionsTID Items
1 Bread, Milk
2 Bread, Diaper, Beer, Eggs
3 Milk, Diaper, Beer, Coke
4 Bread, Milk, Diaper, Beer
5 Bread, Milk, Diaper, Coke
Esempio di regola associativa:
TID Bread Milk Diaper Beer Eggs Coke1 1 1 0 0 0 02 1 0 1 1 1 03 0 1 1 1 0 14 1 1 1 1 0 05 1 1 1 0 0 1
Market Basket Analysis (MBA)
![Page 5: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/5.jpg)
5Data Mining - S. Orlando
Misure di interesse delle regole
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 )
– Confidenza, c, è la probabilità condizionale che una transazione che include X contenga anche Z
• Conf (X Z ) = Probabilità(Z | X )
Transaction ID Items Bought2000 A,B,C1000 A,C4000 A,D5000 B,E,F
Per
50% : supporto minimo
50% : confidenza minima
abbiamo che
– A C (50%, 66.6%)
– C A (50%, 100%)
Clienti che comprano pannolini
Clienti checomprano birra
Clienti che comprano entrambi
D
![Page 6: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/6.jpg)
6Data Mining - S. Orlando
Calcolo di regole frequenti e confidenti
Sia X un itemset, e sia (X) |D| il numero di transazioni in D che contengono X
TID Items1 Pane, Latte
2 Birra, Pane, Pannolini, Uova
3 Birra, Coca, Pannolini, Latte
4 Birra, Pane, Pannolini, Latte
5 Coca, Pane, Pannolini, Latte
Association rule: Xs,c y
Support: s =(Xy) / |D|
Confidence: c = (Xy) / (X)
Esempio: {Pannolini,Latte} s,c Birra
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})
![Page 7: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/7.jpg)
7Data Mining - S. Orlando
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.
![Page 8: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/8.jpg)
8Data Mining - S. Orlando
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!
![Page 9: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/9.jpg)
9Data Mining - S. Orlando
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
![Page 10: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/10.jpg)
10Data Mining - S. Orlando
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)?
![Page 11: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/11.jpg)
11Data Mining - S. Orlando
Mining di regole booleane a singola-dimensione
Transaction ID Items Bought2000 A,B,C1000 A,C4000 A,D5000 B,E,F
Frequent Itemset Support{A} 75%{B} 50%{C} 50%{A,C} 50%
Min. support 50%Min. confidence 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
![Page 12: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/12.jpg)
12Data Mining - S. Orlando
Generazione delle regole dagli itemset frequenti
TID Items
1 Bread, Milk
2 Bread, Diaper, Beer, Eggs
3 Milk, Diaper, Beer, Coke
4 Bread, Milk, Diaper, Beer
5 Bread, Milk, Diaper, Coke
Esempio di regole:
{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
![Page 13: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/13.jpg)
13Data Mining - S. Orlando
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
![Page 14: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/14.jpg)
14Data Mining - S. Orlando
Il reticolo degli itemsets
null
AB AC AD AE BC BD BE CD CE DE
A B C D E
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
ABCD ABCE ABDE ACDE BCDE
ABCDE
Power Set di un insieme di d items (d=5 in questo caso)
Ci sono 2d itemset possibili
![Page 15: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/15.jpg)
15Data Mining - S. Orlando
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
– Complessità ~ O(NM) => costosa poiché M = 2d !!!
TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke
N
Transactions Candidates
M
![Page 16: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/16.jpg)
16Data Mining - S. Orlando
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
![Page 17: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/17.jpg)
17Data Mining - S. Orlando
Usare il principio di Apriori per il pruning dei candidati
Se un itemset è NON frequente, allora tutti i suoi superset devono anche essere NON frequenti
Abbiamo scoperto che è NON frequente
null
AB AC AD AE BC BD BE CD CE DE
A B C D E
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
ABCD ABCE ABDE ACDE BCDE
ABCDE
Super-itemset eliminati (pruned), e non controllati
![Page 18: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/18.jpg)
18Data Mining - S. Orlando
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
![Page 19: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/19.jpg)
19Data Mining - S. Orlando
L’algoritmo Apriori
Pseudo-code:Ck: Candidate itemset of size kLk : 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 endreturn k Lk
![Page 20: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/20.jpg)
20Data Mining - S. Orlando
TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5
Database D itemset sup.{1} 2{2} 3{3} 3{4} 1{5} 3
itemset sup.{1} 2{2} 3{3} 3{5} 3
Scan D
C1L1
itemset{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}
itemset sup{1 2} 1{1 3} 2{1 5} 1{2 3} 2{2 5} 3{3 5} 2
itemset sup{1 3} 2{2 3} 2{2 5} 3{3 5} 2
L2
C2 C2
Scan D
C3 L3itemset{2 3 5}
Scan D itemset sup{2 3 5} 2
L’algoritmo Apriori: un esempio (minsup = 2)
![Page 21: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/21.jpg)
21Data Mining - S. Orlando
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
Apriori: visita Breadth first del reticolo
![Page 22: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/22.jpg)
22Data Mining - S. Orlando
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
Genera i Candidati di dimensione 1
![Page 23: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/23.jpg)
23Data Mining - S. Orlando
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
Conta i supporti dei Candidati di dim. 1
![Page 24: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/24.jpg)
24Data Mining - S. Orlando
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
Genera i Candidati di dimensione 2
![Page 25: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/25.jpg)
25Data Mining - S. Orlando
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
Conta i supporti dei Candidati di dim. 2
![Page 26: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/26.jpg)
26Data Mining - S. Orlando
a b c d e
ac ad ae bc bd be cd ce de
acd ace ade bcd bce bde cde
acde bcde
Pruna gli itemset infrequenti
![Page 27: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/27.jpg)
27Data Mining - S. Orlando
a b c d e
ac ad ae bc bd be cd ce de
acd ace ade bcd bce bde cde
acde bcde
Genera i Candidati di dimensione 3
![Page 28: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/28.jpg)
28Data Mining - S. Orlando
a b c d e
ac ad ae bc bd be cd ce de
acd ace ade bcd bce bde cde
acde bcde
Conta i supporti dei Candidati di dim. 3
![Page 29: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/29.jpg)
29Data Mining - S. Orlando
a b c d e
ac ad ae bc bd be cd ce de
acd ace ade bce bde cde
acde
Pruna gli itemset infrequenti
![Page 30: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/30.jpg)
30Data Mining - S. Orlando
a b c d e
ac ad ae bc bd be cd ce de
acd ace ade bce bde cde
acde
Genera i Candidati di dimensione 4
![Page 31: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/31.jpg)
31Data Mining - S. Orlando
a b c d e
ac ad ae bc bd be cd ce de
acd ace ade bce bde cde
acde
Conta i supporti dei Candidati di dim. 3
![Page 32: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/32.jpg)
32Data Mining - S. Orlando
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
![Page 33: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/33.jpg)
33Data Mining - S. Orlando
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}
![Page 34: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/34.jpg)
34Data Mining - S. Orlando
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
![Page 35: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/35.jpg)
35Data Mining - S. Orlando
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}
![Page 36: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/36.jpg)
36Data Mining - S. Orlando
Hash-tree per memorizzare i candidati
1 5 9
1 4 5 1 3 63 4 5 3 6 7
3 6 8
3 5 6
3 5 7
6 8 9
2 3 4
5 6 7
1 2 4
4 5 71 2 5
4 5 8
1,4,7
2,5,8
3,6,9
Hash Function Candidate Hash Tree
Hash on 1, 4 or 7
Nota che 4 e 7 appaionoanche in questi bin
![Page 37: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/37.jpg)
37Data Mining - S. Orlando
Hash-tree per memorizzare i candidati
1 5 9
1 4 5 1 3 63 4 5 3 6 7
3 6 8
3 5 6
3 5 7
6 8 9
2 3 4
5 6 7
1 2 4
4 5 71 2 5
4 5 8
1,4,7
2,5,8
3,6,9
Hash Function Candidate Hash Tree
Hash on 2, 5 or 8
![Page 38: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/38.jpg)
38Data Mining - S. Orlando
Hash-tree per memorizzare i candidati
1 5 9
1 4 5 1 3 63 4 5 3 6 7
3 6 8
3 5 6
3 5 7
6 8 9
2 3 4
5 6 7
1 2 4
4 5 71 2 5
4 5 8
1,4,7
2,5,8
3,6,9
Hash Function Candidate Hash Tree
Hash on 3, 6 or 9
![Page 39: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/39.jpg)
39Data Mining - S. Orlando
Operazione di Subsetting su una transazione
1 2 3 5 6
Transaction, t
2 3 5 61 3 5 62
5 61 33 5 61 2 61 5 5 62 3 62 5
5 63
1 2 31 2 51 2 6
1 3 51 3 6
1 5 62 3 52 3 6
2 5 6 3 5 6
Subsets of 3 items
Level 1
Level 2
Level 3
63 5
Data una transazione t, quali sono i possibili sottoinsiemi di size 3?
![Page 40: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/40.jpg)
40Data Mining - S. Orlando
Operazione di Subsetting su una transazione
1 5 9
1 4 5 1 3 63 4 5 3 6 7
3 6 8
3 5 6
3 5 7
6 8 9
2 3 4
5 6 7
1 2 4
4 5 71 2 5
4 5 8
1 2 3 5 6
1 + 2 3 5 63 5 62 +
5 63 +
1,4,7
2,5,8
3,6,9
Hash Functiontransaction
Per evitare duplicati,cerco sempre insiemiordinati di 3 elementi 1 combinato con 2, o 3, o 5, ma non con 6non esiste {1,6,x}, x>6, nella transazione !!!
• Controllo di subsetting ricorsivo
![Page 41: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/41.jpg)
41Data Mining - S. Orlando
Operazione di Subsetting su una transazione
1 5 9
1 4 5 1 3 63 4 5 3 6 7
3 6 8
3 5 6
3 5 7
6 8 9
2 3 4
5 6 7
1 2 4
4 5 71 2 5
4 5 8
1,4,7
2,5,8
3,6,9
Hash Function1 2 3 5 6
3 5 61 2 +
5 61 3 +
61 5 +
3 5 62 +
5 63 +
1 + 2 3 5 6
transaction
![Page 42: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/42.jpg)
42Data Mining - S. Orlando
Operazione di Subsetting su una transazione
1 5 9
1 4 5 1 3 63 4 5 3 6 7
3 6 8
3 5 6
3 5 7
6 8 9
2 3 4
5 6 7
1 2 4
4 5 71 2 5
4 5 8
1,4,7
2,5,8
3,6,9
Hash Function1 2 3 5 6
3 5 61 2 +
5 61 3 +
61 5 +
3 5 62 +
5 63 +
1 + 2 3 5 6
transaction
La transazione contiene ben 11 di tutti i 15 candidati
![Page 43: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/43.jpg)
43Data Mining - S. Orlando
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
![Page 44: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/44.jpg)
44Data Mining - S. Orlando
Metodi per migliorare l’efficienza di Apriori
Transaction pruning: Una transazione che non contiene nessun k-itemset 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.
![Page 45: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/45.jpg)
45Data Mining - S. Orlando
D1, D2, D3
Se X è frequent, allora:
supp(X) = suppD1(X) + suppD2(X) + suppD3(X) >= s% (|D1| +|D2| +|D3|)
i, suppDi(X) < s% |Di| X è infrequente globalmente
A B (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|
![Page 46: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/46.jpg)
46Data Mining - S. Orlando
Generazione delle regole
Algoritmo non ottimizzato:
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);
c è frequente per definizione
![Page 47: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/47.jpg)
47Data Mining - S. Orlando
Generazione delle regole (2)
Considera la regola (l-c) c
Se c1 c, allora
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
lc
c1
![Page 48: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/48.jpg)
48Data Mining - S. Orlando
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
![Page 49: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/49.jpg)
49Data Mining - S. Orlando
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
![Page 50: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/50.jpg)
50Data Mining - S. Orlando
Costruzione dell’FP-tree a partire dal DB
{}
f:4 c:1
b:1
p:1
b:1c:3
a:3
b:1m:2
p:2 m:1
Header Table
Item frequency head f 4c 4a 3b 3m 3p 3
min_support = 0.5
TID Items bought (ordered) frequent items100 {f, a, c, d, g, i, m, p} {f, c, a, m, p}200 {a, b, c, f, l, m, o} {f, c, a, b, m}300 {b, f, h, j, o} {f, b}400 {b, c, k, s, p} {c, b, p}500 {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
![Page 51: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/51.jpg)
51Data Mining - S. Orlando
Costruzione FP-tree
TID Items1 {A,B}2 {B,C,D}3 {A,C,D,E}4 {A,D,E}5 {A,B,C}6 {A,B,C,D}7 {B,C}8 {A,B,C}9 {A,B,D}10 {B,C,E}
null
A:1
B:1
null
A:1
B:1
B:1
C:1
D:1
Letura TID=1:
Lettura TID=2:
Transaction Database
![Page 52: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/52.jpg)
52Data Mining - S. Orlando
Costruzione FP-tree
null
A:7
B:5
B:3
C:3
D:1
C:1
D:1C:3
D:1
D:1
E:1
TID Items1 {A,B}2 {B,C,D}3 {A,C,D,E}4 {A,D,E}5 {A,B,C}6 {A,B,C,D}7 {B,C}8 {A,B,C}9 {A,B,D}10 {B,C,E}
Puntatori utili per estrarre gli itemset frequenti
D:1
E:1
Transaction Database
Item PointerABCDE
Header table
![Page 53: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/53.jpg)
53Data Mining - S. Orlando
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
![Page 54: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/54.jpg)
54Data Mining - S. Orlando
Mining i pattern frequenti tramite l’FP-tree
Idea generale– In maniera ricorsiva, fai crescere i pattern frequenti usando l’FP-
tree– Visita Depth-First del reticolo
![Page 55: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/55.jpg)
55Data Mining - S. Orlando
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
![Page 56: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/56.jpg)
56Data Mining - S. Orlando
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
FIM attraverso una visita depth first
![Page 57: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/57.jpg)
57Data Mining - S. Orlando
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
Trova itemset frequenti contenenti “a”
![Page 58: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/58.jpg)
58Data Mining - S. Orlando
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
Trova itemset frequenti contenenti “a” ma “non b”
![Page 59: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/59.jpg)
59Data Mining - S. Orlando
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
… contenenti “c” ma “non a” e “non b”
![Page 60: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/60.jpg)
60Data Mining - S. Orlando
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
… contenenti “d” ma “non a”, “non b”, e “non c”
![Page 61: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/61.jpg)
61Data Mining - S. Orlando
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
… contenenti “d” ma “non a, b, c, d”
![Page 62: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/62.jpg)
62Data Mining - S. Orlando
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
Ricorsione: es. per gli itemset contenenti “a”
![Page 63: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/63.jpg)
63Data Mining - S. Orlando
Passi di FP-growth
1) Costruisci il conditional pattern base per ciascun item nel’FP-tree 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 pattern-
base 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 …
![Page 64: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/64.jpg)
64Data Mining - S. Orlando
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
Conditional pattern bases
item cond. pattern base
c f:3
a fc:3
b fca:1, f:1, c:1
m fca:2, fcab:1
p fcam:2, cb:1
{}
f:4 c:1
b:1
p:1
b:1c:3
a:3
b:1m:2
p:2 m:1
Header Table
Item frequency head f 4c 4a 3b 3m 3p 3
![Page 65: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/65.jpg)
65Data Mining - S. Orlando
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.
![Page 66: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/66.jpg)
66Data Mining - S. Orlando
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
m-conditional pattern base:
fca:2, fcab:1
{}
f:3
c:3
a:3m-conditional FP-tree
All frequent patterns concerning m
m,
fm, cm, am,
fcm, fam, cam,
fcam
{}
f:4 c:1
b:1
p:1
b:1c:3
a:3
b:1m:2
p:2 m:1
Header TableItem frequency head f 4c 4a 3b 3m 3p 3
Passo 3
![Page 67: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/67.jpg)
67Data Mining - S. Orlando
Basi e FP-tree condizionali
EmptyEmptyf
{(f:3)}|c{(f:3)}c
{(f:3, c:3)}|a{(fc:3)}a
Empty{(fca:1), (f:1), (c:1)}b
{(f:3, c:3, a:3)}|m{(fca:2), (fcab:1)}m
{(c:3)}|p{(fcam:2), (cb:1)}p
Conditional FP-treeConditional pattern-baseItem
![Page 68: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/68.jpg)
68Data Mining - S. Orlando
Passo 3: ricorsione
In modo ricorsivo, riapplica FP-growth agli FP-tree condizionali
{}
f:3
c:3
a:3m-conditional FP-tree
Cond. pattern base di “am”: (fc:3)
{}
f:3
c:3am-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
![Page 69: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/69.jpg)
69Data Mining - S. Orlando
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
![Page 70: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/70.jpg)
70Data Mining - S. Orlando
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’FP-
tree
![Page 71: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/71.jpg)
71Data Mining - S. Orlando
FP-growth: tempo di esecuzione rispetto al supporto minimo
0
10
20
30
40
50
60
70
80
90
100
0 0.5 1 1.5 2 2.5 3
Support threshold(%)
Ru
n t
ime(s
ec.)
D1 FP-grow th runtime
D1 Apriori runtime
Data set T25I20D10K
![Page 72: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/72.jpg)
72Data Mining - S. Orlando
FIM algorithms: formato database
Database Orizzontale vs. Verticale– Record orizzontale (transazione): Tid: Item0, …, Itemk
– Record verticale (tidlist): Item: Tid0, …, Tidh
Orizzontale
Verticale
![Page 73: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/73.jpg)
73Data Mining - S. Orlando
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
![Page 74: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/74.jpg)
74Data Mining - S. Orlando
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
TID Items1 A,B,E2 B,C,D3 C,E4 A,C,D5 A,B,C,D6 A,E7 A,B8 A,B,C9 A,C,D
10 B
HorizontalData Layout
A B C D E1 1 2 2 14 2 3 4 35 5 4 5 66 7 8 97 8 98 109
Vertical Data Layout
TID-list
Transaction
![Page 75: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/75.jpg)
75Data Mining - S. Orlando
Intersection-based
A1456789
B1257810
ABC
157
C1257
AB1578
BC1257
ABC
157
k-way intersection– Determina il supporto di un k-itemset
attraverso il set intersection di k tid-list atomiche, contando alla fine la cardinalità della lista ottenuta
– 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
![Page 76: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/76.jpg)
76Data Mining - S. Orlando
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
![Page 77: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/77.jpg)
77Data Mining - S. Orlando
Classificazione dei vari algoritmi per FSC
Support: Support: computing methodcomputing method
Apriori Partition FP-growth Eclat
Search space:Search space:visiting methodvisiting method
BFS DFS
Cou
ntin
g Intersecting Cou
ntin
g Intersecting
Level-wise, strictly iterative Divide & conquer, recursive
Horizontal DB Horizontal DBVertical DB Vertical DB
Support: Support: computing methodcomputing method
![Page 78: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/78.jpg)
78Data Mining - S. Orlando
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
![Page 79: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/79.jpg)
79Data Mining - S. Orlando
DCI: fase intersection-based
nk trans
mk items1 0
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)
![Page 80: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/80.jpg)
80Data Mining - S. Orlando
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:Cache size: k-2 bitvector di nk bit
![Page 81: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/81.jpg)
81Data Mining - S. Orlando
DCI: intersezione delle tidlist (bitvector)
Buffer di (k-2) vettori di nk bit usati per il caching delle intersezioni intermedie
3 5 11 17 24 315 11 17 24 475 11 17 31 47
i0 i1 i2 i3 i4 i5C6
3 & 5
3 & 5 & 11
3 & 5 & 11& 17
3 & 5 & 11& 17 & 24
Candidatocorrente
3 & 5 & 11& 17 & 24
Riuso di questa Intersezione presentein cache
33Candidato
corrente
![Page 82: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/82.jpg)
82Data Mining - S. Orlando
DCI: numero delle operazioni AND
![Page 83: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/83.jpg)
83Data Mining - S. Orlando
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
![Page 84: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/84.jpg)
84Data Mining - S. Orlando
DCI: migliore di FP-growth
Database denso• Pattern
lunghissimi
Apriori è troppo costoso • tempo di
Apriori non commensurabile
![Page 85: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/85.jpg)
85Data Mining - S. Orlando
DCI: migliore di FP-growth
Database reale e sparso
• Dati di click-stream da un sito web di e-commerce
Pattern di lunghezza media per supporti piccoli
![Page 86: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/86.jpg)
86Data Mining - S. Orlando
Visualizzazione di regole associative (Forma tabellare)
![Page 87: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/87.jpg)
87Data Mining - S. Orlando
Visualizzazione: grafico tridimensionale
![Page 88: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/88.jpg)
88Data Mining - S. Orlando
Visualizzazione: associazioni come link
![Page 89: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/89.jpg)
89Data Mining - S. Orlando
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
![Page 90: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/90.jpg)
90Data Mining - S. Orlando
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
breadmilk
skim
SunsetFraser
2% whitewheat
![Page 91: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/91.jpg)
91Data Mining - S. Orlando
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
![Page 92: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/92.jpg)
92Data Mining - S. Orlando
Regole associative multi-livello: Uniform Support vs. Reduced Support
Supporto uniforme
Milk
[support = 10%]
2% Milk
[support = 6%]
Skim Milk
[support = 4%]
Level 1min_sup = 5%
Level 2min_sup = 5%
![Page 93: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/93.jpg)
93Data Mining - S. Orlando
Regole associative multi-livello: Uniform Support vs. Reduced Support
Supporto ridotto
2% Milk
[support = 6%]
Skim Milk
[support = 4%]
Level 1min_sup = 5%
Level 2min_sup = 3%
Milk
[support = 10%]
![Page 94: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/94.jpg)
94Data Mining - S. Orlando
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
![Page 95: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/95.jpg)
95Data Mining - S. Orlando
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
La regolagioca 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
calcio non calcio sum(row)cereali 2000 1750 3750non cereali 1000 250 1250sum(col.) 3000 2000 5000
![Page 96: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/96.jpg)
96Data Mining - S. Orlando
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 0Y 1 1 0 0 0 0 0 0Z 0 1 1 1 1 1 1 1
Rule Support ConfidenceX=>Y 25% 50%X=>Z 37,50% 75%
)()(
)(
BPAP
BAP
Abbiamo bisogno di una misura che metta in evidenza eventi correlati, ovvero inter-dipendenti
P(B|A)/P(B) è anche chiamato il lift della regola A B
![Page 97: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/97.jpg)
97Data Mining - S. Orlando
Un’altra misura: Interesse
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
)()(
)(
BPAP
BAP
X 1 1 1 1 0 0 0 0Y 1 1 0 0 0 0 0 0Z 0 1 1 1 1 1 1 1
Itemset Support InterestX,Y 25% 2X,Z 37,50% 0,9Y,Z 12,50% 0,57
![Page 98: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/98.jpg)
98Data Mining - S. Orlando
Atri tipi di patterns
Maximal and Closed Itemsets Negative Associations Indirect Associations Frequent Subgraphs Cyclic Association Rules Sequential Patterns
![Page 99: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/99.jpg)
99Data Mining - S. Orlando
Maximal frequent itemsets
null
AB AC AD AE BC BD BE CD CE DE
A B C D E
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
ABCD ABCE ABDE ACDE BCDE
ABCDEBorder
Infrequent Itemsets
Maximal Itemsets
![Page 100: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/100.jpg)
100Data Mining - S. Orlando
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’)
111111111100000000000000000000111111111100000000000000000000111111111100000000000000000000111111111100000000000000000000000000000011111111110000000000000000000011111111110000000000000000000011111111110000000000000000000011111111110000000000000000000000000000001111111111000000000000000000001111111111000000000000000000001111111111000000000000000000001111111111
A1 … A10 B1 … B10 C1 … C10
Numero degli itemset frequenti:
Numero Closed Itemset = 3
{A1,…,A10}, {B1,…,B10}, {C1,…,C10}
Numero Itemset massimali = 3
10
1
103
k k
![Page 101: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/101.jpg)
101Data Mining - S. Orlando
Maximal vs Closed Itemsets
TID Items
1 ABC
2 ABCD
3 BCE
4 ACDE
5 DE
null
AB AC AD AE BC BD BE CD CE DE
A B C D E
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
ABCD ABCE ABDE ACDE BCDE
ABCDE
124 123 1234 245 345
12 124 24 4 123 2 3 24 34 45
12 2 24 4 4 2 3 4
2 4
Transaction Ids
Non supportati da alcuna transazione
![Page 102: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/102.jpg)
102Data Mining - S. Orlando
Maximal vs Closed Itemsets
null
AB AC AD AE BC BD BE CD CE DE
A B C D E
ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE
ABCD ABCE ABDE ACDE BCDE
ABCDE
124 123 1234 245 345
12 124 24 4 123 2 3 24 34 45
12 2 24 4 4 2 3 4
2 4
Minimum support = 2
# Closed = 10
# Maximal = 5
Closed and maximal
Closed but not maximal
CD
A D (s=2, c = 2/3 = 0,66%)
AC D (s=2, c = 2/3 = 0,66%)regola non generata se partiamo dai closed
![Page 103: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/103.jpg)
103Data Mining - S. Orlando
Classificatori basati su regole associative
Dati su cui costruire il classificatore– Insieme di record in D classificati, ovvero contenenti un attributo
categorico yY, 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)
![Page 104: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/104.jpg)
104Data Mining - S. Orlando
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 )
![Page 105: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/105.jpg)
105Data Mining - S. Orlando
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
![Page 106: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/106.jpg)
106Data Mining - S. Orlando
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 r i è 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
![Page 107: 1 Data Mining - S. Orlando “Association mining” Salvatore Orlando](https://reader036.vdocumenti.com/reader036/viewer/2022062303/5542eb75497959361e8debc2/html5/thumbnails/107.jpg)
107Data Mining - S. Orlando
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.