“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, “100110”) [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: Xs,c y Support: s =(Xy) / |D| Confidence: c = (Xy) / (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 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) 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