Mining Frequent patterns without Candidate Generation

De Faveri Alessandro

Matricola 795135

L’association mining

• Trova le associazioni tra insiemi di articoli (items) in database transazionali.

• Dall’analisi delle transazioni crea regole del tipo:

Body → head [supporto, confidenza]

• Esempio:– age(x, “30..39”) ^ income(x, “42..48K”) →

buys(x, “PC”) [1%, 75%]

Analisi dei dati• Data la regola:

X → Y• Supporto:

– è la probabilità che un certo itemset appaia nelle transazioni del database.

– Probabilità che una transazione contenga (X Y).– Si misura come rapporto tra le transazioni che contengono (X Y) sul

numero totale di transazioni.σ(X Y) / |T|

• Confidenza:– è la probabilità condizionale che una transazione che include X includa

anche Y.– Si misura come rapporto tra le transazioni che contengono (X Y) sulle

transazioni che contengono Y.σ(X Y) / σ(X)

Esempio 1

TID Items

1 A,C

2 B,C

3 A,E

4 B,C,E

5 A,B,C,E

6 B,E

7 B,C

• Regola:B → E

• Supporto:3/7 = 43%

• Confidenza:3/5 = 60%

Principio Apriori

B 71%

C 71%

E 57%

B,C 57%

“Ogni sottoinsieme di un itemset frequente deve essere frequente”

• Se il supporto minimo è 50% troviamo gli itemset frequenti nell’esempio precedente.

Algoritmo Apriori - 1

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;

• Ck: itemset di lunghezza k (candidati).

• Lk: itemset frequenti di lunghezza k.

• L’algoritmo si compone di due passi:– Gen step (candidate

set generation)– Prune step (test)

Esempio 2

• Min_support = 2• Database D:

itemset Supporto

A 2

B 3

C 3

D 1

E 3

TID ITEMS

1 A C D

2 B C E

3 A B C E

4 B E

Scan D…K=1Gen step…

Prune step…

CK:K=2K=3LK:

itemset Supporto

A 2

B 3

C 3

E 3

itemset

{A,B}

{A,C}

{A,E}

{B,C}

{B,E}

{C,E}

itemset supporto

{A,B} 1

{A,C} 2

{A,E} 1

{B,C} 2

{B,E} 3

{C,E} 2

itemset supporto

{A,C} 2

{B,C} 2

{B,E} 3

{C,E} 2

Itemset

{B,C,E}

itemset supporto

{B,C,E} 2

Analisi performance

• In certe situazioni, l’algoritmo Apriori non dà buone prestazioni, soprattutto in presenza di:– Patterns lunghi– Patterns frequenti molto lunghi.– Soglia minima del supporto abbastanza bassa.

• Portano ai seguenti costi:– È dispendioso gestire grandi insiemi di candidati.

• 104 1-itemset frequenti -> più di 107 2-itemsets di candidati.• per trovare pattern frequenti di lunghezza 100 si devono generare

circa 1030 candidati.

– È svantaggioso accedere ripetutamente al database e controllare un grande insieme di candidati, in modo particolare se si tratta di lunghi patterns. Sono necessarie (n +1) scansioni, dove n è la lunghezza del pattern più lungo.

Soluzioni

• Collo di bottiglia dell’algoritmo Apriori: generazione dell’insieme dei candidati e test.

• Soluzioni:– Creazione di una nuova e compatta struttura dati:

Frequent Pattern Tree (FP-tree).– È stato creato un metodo basato su FP-tree che parte

da un pattern frequente di lunghezza 1 ed esamina il suo conditional pattern base (un sub-database che consiste in un insieme di items frequenti che ricorrono assieme al pattern suffisso).

– La tecnica di mining utilizzata è di tipo “divide-et-impera” piuttosto che il bottom-up dell’algoritmo Apriori.

FP-tree: regole di base (1)

• Estensione della struttura del prefix-tree che memorizza informazioni quantitative sui pattern frequenti.

• Solamente gli items frequenti di lunghezza 1 hanno i nodi corrispondenti nell’albero.

FP-tree: regole di base (2)

• Solamente gli items frequenti sono importanti per il mining. Per identificare gli items frequenti è necessaria una sola scansione del database.

• Se si memorizzano gli insiemi di items frequenti (in ordine decrescente in base alla frequenza) per ogni transazione si può evitare di accedere ripetutamente al database.

• Se transazioni diverse identificano lo stesso insieme di items frequenti si possono unire e salvare in una variabile il numero di transazioni.

• Se transazioni diverse hanno un prefisso in comune (nella lista degli item frequenti ordinati secondo lo stesso criterio), la parte comune può essere memorizzata a parte insieme al contatore del numero di transazioni.

FP-tree: costruzione• Illustriamo la costruzione di un FP-tree

con un esempio. La soglia minima di supporto () è 3.

• Con una scansione del database si individua la lista degli items frequenti in ordine decrescente: <(f:4),(c:4),(a:3),(b:3),(m:3),(p:3)>. Per ogni TID si crea una lista ordinata di items frequenti.

• Si crea la radice dell’albero con etichetta null.

• Seconda scansione del database:– la scansione della prima riga crea il

primo ramo dell’albero.– la seconda riga ha un prefisso in

comune con la precedente: questi elementi verranno incrementati e si aggiungeranno i nuovi elementi.

– la terza riga ha solo f come prefisso comune.

– la scansione della quarta riga porta alla formazione del secondo ramo dell’albero.

– l’ultima riga è identica alla prima: tutti i nodi del ramo più a sinistra vengono incrementati di uno.

TID Items

100 f,a,c,d,g,i,m,p

200 a,b,c,f,l,m,o

300 b,f,h,j,o

400 b,c,k,s,p

500 a,f,c,e,l,p,m,n

Items frequenti

f,c,a,m,p

f,c,a,b,m

f,b

c,b,p

f,c,a,m,p

null

f:1

c:1

a:1

m:1

p:1

f:2

c:2

a:2

m:1

p:1

b:1

m:1

f:3

b:1 b:1

p:1

c:1f:4

c:3

a:3

m:2

p:2

FP-tree: definizione (1)• È formato da un nodo radice etichettato come

“null”, un insieme di sottoalberi di prefissi come figli della radice e da una tabella per il collegamento diretto alle liste degli item frequenti (Header table).

null

f:1

c:1

a:1

m:1

p:1

f:2

c:2

a:2

m:1

p:1

b:1

m:1

f:3

b:1 b:1

p:1

c:1f:4

c:3

a:3

m:2

p:2

item node-link

f

c

a

b

m

p

FP-tree: definizione (2)

• Ogni nodo è composto da tre campi:– nome dell’item: indica quale item è rappresentato dal

nodo.– contatore: numero di transazioni rappresentate dalla

porzione di percorso per raggiungere il nodo.– node-link: link al prossimo nodo con lo stesso nome o

null se è l’ultimo.• Ogni riga nella Header Table è composta da due

campi:– nome dell’item– link al primo nodo del FP-tree che porta lo stesso

nome dell’item.

FP-tree: algoritmo1. Scansione del database per

ottenere la lista (F) degli item frequenti e il loro supporto. Ordinare la lista secondo l’ordine decrescente per il supporto ottenendo la lista degli item frequenti (L).

2. Creazione della radice dell’albero (T). Per ogni transazione (Trans) eseguire le seguenti operazioni:

1. Selezionare e ordinare gli item frequenti in Trans secondo l’ordine di L.

2. Trans = lista di item frequenti appena creata. La lista ha la forma [p|P], dove p è il primo elemento della lista e P è il resto della lista. Chiamata alla funzione insert_tree(p|P,T).

Funzione insert_tree([p|P,T]):

•se T ha un figlio N, tale che N.item_nome=p.item_nome

•Incrementa il contatore di N di 1.

•Altrimenti:

•Crea un nuovo nodo N e imposta il contatore ad 1. Il suo link al padre deve essere impostato a T. Il node-link deve essere impostato ai nodi con lo stesso itemname. Se P non è vuota, chiama insert_tree(P,N) ricorsivamente.

Analisi dell’algoritmo

• Come si può vedere dal processo di costruzione dell’albero sono necessari solo due scansioni del database:– La prima crea la lista degli items frequenti– La seconda costruisce l’FP-tree.

• Il costo di inserimento di una transazione Trans nell’FP-tree è O(|Trans|), dove |Trans| è il numero di item frequenti in Trans.

Completezza del FP-tree

Lemma 1:“Dato un database di transazioni (DB) e una soglia del

supporto (), il corrispondente FP-tree contiene le informazioni complete di DB riguardanti il mining di pattern frequenti.”

Dimostrazione:Guardando il processo di costruzione del FP-tree, ogni

transazione in DB corrisponde ad un cammino nel FP-tree e le informazioni sugli itemset frequenti di ogni transazione sono completamente memorizzate nel FP-tree. Inoltre, più transazioni del DB possono essere rappresentate in un unico cammino nel FP-tree senza ambiguità.

Compattezza del FP-treeLemma 2:“Senza considerare la radice “null”, la dimensione di un FP-tree è limitata

dalla somma delle occorrenze degli item frequenti nel database, mentre l’altezza dell’albero è limitata dal numero massimo di item frequenti in ogni transazione del database.”

Dimostrazione:Per ogni transazione T nel database, c’è un cammino nel FP-

tree in modo che il numero di nodi del cammino è lo stesso degli item frequenti in T. Nessun item frequente presente in una transazione può creare più di un nodo nell’albero. La radice è l’unico nodo “extra” creato. L’altezza dell’albero è data dal numero massimo di item presenti nelle transazioni se non si prende in considerazione il livello aggiunto dal nodo radice.

Analisi performances

• Poiché ci sono spesso items frequenti nei prefissi delle transazioni, le dimensioni del FP-tree sono molto ridotte.

• L’algoritmo Apriori, nel caso peggiore, genera un numero esponenziale di candidati; mentre l’FP-tree non genera mai un numero esponenziale di nodi.

• FP-tree è molto più piccolo rispetto al database originale:– database con 67.557 transazioni e 43 items per ogni transazione

con supporto minimo del 50% -> numero totale di occorrenze degli items frequenti: 2.219.609.

– FP-tree corrispondente è formato da 13.449 nodi.

RIDUZIONE DEL 165.04 (RAPPORTO DI COMPRESSIONE)

FP-tree: proprietà dei node-link“Per ogni item frequente ai, tutti i possibili pattern frequenti

che contengono ai si possono ottenere seguendo la lista dei node-link a partire dalla Header Table.”

Esempio:

Analizziamo il processo di mining partendo dalla fine della Header Table.

p:

abbiamo il pattern frequente (p:3) e i due cammini <(f:4),(c:3),(a:3),(m:2),(p:2)> e

<(c:1),(b:1),(p:1)>questa stringa appare 2 volte nel DB

questa stringa appare 1 volta nel DB

Conditional Pattern Base

• I due cammini dei prefissi di p dell’esempio precedente (<(f:2),(c:2),(a:2),(m:2) > e <(c:1),(b:1)>) formano il sub-pattern base di p, chiamato Conditional Pattern Base (il sub-pattern base sotto la condizione dell’esistenza di p). items items frequenti

(f:2),(c:2),(a:2),(m:2) (c:2)

(c:1),(b:1) (c:1)

• Costruire l’FP-tree partendo dai Conditional Pattern Base (chiamato Conditional FP-Tree) di p porta ad un albero con un solo ramo: (c:3). Da questo deriva che c’è un solo pattern frequente: (cp:3).

• Così termina la ricerca di pattern frequenti associati a p.

Conditional FP-tree per m

• Ripetendo il procedimento precedente per m, si identificano due cammini (viene tralasciato il nodo p, in quanto già esaminato): <(f:4),(c:3),(a:3),(m:2)> e <(f:4),(c:3),(a:3),(b:1),(m:1)>

• Si trova che il Conditional FP-tree per m è <f:3,c:3,a:3>

Chiamate ricorsive

• A questo punto, si costruiscono i Conditional FP-tree ricorsivamente partendo da quello trovato per m, indicato come “mine(<f:3,c:3,a:3>|m)”

Conditional FP-tree per m:

root

f:3

c:3

a:3

item testa dei node-links

f

c

a

Conditional Pattern Base di am: (f:3,c:3)

root

f:3

c:3

Conditional Pattern Base di cm: (f:3)

root

f:3

fm: un solo pattern frequente (fm:3)

Ancora chiamate ricorsive...

• “mine(<f:3,c:3>|am)” -> (cam:3) e (fam:3)

• “mine(<f:3>|cam)” -> (fcam:3): otteniamo il pattern più lungo possibile.

• “mine(<f:3>|cm)”->(fcm:3)

• Tutti i patterns frequenti che coinvolgono m sono: {(m:3),(am:3),(cm:3),(fm:3),(cam:3),(fam:3),(fcam:3),(fcm:3)}

FP-tree: proprietà dei prefix path

“Per calcolare i pattern frequenti per un nodo ai nel cammino P, solo il prefix sub-path di ai in P deve essere accumulato e il suo contatore deve essere uguale al nodo ai”

Alcune definizioni…

Il prefix subpath del nodo ai può essere copiato e trasformato in un prefix subpath “count-adjusted” correggendo il contatore di ogni nodo del subpath con quello del nodo ai. Questa trasformazione è detta trasformed prefix path di ai per il cammino P. L’insieme dei prefix path trasformati si chiama conditional pattern base di ai e si indica “pattern_base | ai”. Il conditional FP-tree di ai è l’FP-tree costruito partendo dal suo conditional pattern base e si indica con “FP-tree | ai”

Fragment Growth

Lemma :

“Sia un itemset nel DB, B un conditional pattern base di e un itemset di B. Il supporto di nel DB è equivalente al supporto di in B.”

Dimostrazione :In base alla definizione di conditional pattern base, ogni

sotto-transazione di B avviene con la condizione di occorrenza di nel database originale. Se un itemset appare in B n volte, appare n volte anche con nel database.

Pattern Growth

Corollario :

“Sia un itemset frequente nel DB, B un conditional pattern base di e un itemset di B. Allora è frequente nel database se e solo se è frequente in B”

Dimostrazione :Questo corollario illustra il caso in cui è un itemset

frequente nel DB e il supporto di in B è non minore della soglia .

Il mining dei dati viene migliorato identificando all’inizio gli 1-itemset frequenti, , nel database e costruendo i loro conditional pattern base. Così, il problema del mining di k-itemset frequenti diventa il mining di una sequenza di k 1-itemset frequenti tramite un insieme di conditional pattern base.

Considerazioni…

FP-tree con cammino singolo

Lemma :“Sia T un FP-tree a cammino singolo P. L’insieme

completo di tutti i pattern frequenti di T può essere generato dalla enumerazione di tutte le combinazioni dei sottocammini di P con supporto, il minimo tra quelli degli items contenuti nel sottocammino.”

Dimostrazione :Sia P (a1:s1 → a2:s2 →... → ak:sk). Il supporto si di ogni nodo ai è la

frequenza con la quale ai ricorre con il suo prefisso. Ogni combinazione di items nel cammino come <ai...aj> (con 1 ≤ i,j ≤ k) è un pattern frequente con frequenza pari al minimo supporto tra tutti gli items. Ogni item nel cammino è unico e non ci sono pattern che vengono generati dalla combinazione, inoltre, nessun pattern frequente viene generato fuori dal FP-tree.

Algotimo FP-growthInput: FP-tree costruito usando il DB e la soglia .Output: l’insieme completo dei pattern frequenti.Metodo: chiamata a FP-growth(FP-tree, null)

Procedure FP-growth (tree,){if (tree contiene un path singolo)

then per ogni combinazione () dei nodi di P do

genera il pattern con supporto = supporto minimo dei nodi di

elseper ogni ai in testa a tree do

{genera = ai con supporto = ai.supporto;costruisci il conditional pattern base

e il conditional FP-tree (tree) di if (tree≠ )

then chiama FP-growth(tree,);}

}

Lemma (completezza): FP-tree contiene tutte le informazioni utili.

Lemma:FP-tree a cammino singolo

Proprietà dei prefix path

Fragment e Pattern Growth:i pattern creati a partire da un Conditional FP-tree sono un insieme completo di items frequenti.

Efficenza dell’algoritmo

• FP-growth scansiona l’FP-tree dal database una sola volta e genera un piccolo pattern base Bai per ogni item frequente ai. FP-tree di solito è molto più piccolo rispetto alla dimensione del DB. Inoltre, il conditional FP-tree, “FP-tree | ai” costruito a partire da Bai è molto più piccolo o, almeno, non più grande di Bai .

• Le operazioni di mining sono solitamente di correzione dei contatori, conteggio e concatenazione; quindi molto meno costosi rispetto alla generazione e al test di un gran numero di candidati.

• FP-growth è un processo di tipo “divide-et-impera”. Il fattore di riduzione per la costruzione di un FP-tree da un database è di circa 20~100.

Valutazione delle prove e studio delle performances

• Tutte le prove sono state eseguite su una macchina PC Pentium 450MHz con 128 Mb di ram su sistema operativo Microsoft© Windows NT. I programmi sono stati scritti usando Microsoft Visual C++ 6.0.

• I diversi algoritmi per le prove comparative sono state scritte usando le migliori implementazioni presenti e sono state eseguite sulla stessa macchina.

• Il tempo di runtime misurato corrisponde al tempo totale di esecuzione, inoltre, il tempo per FP-growth comprende anche il tempo per la costruzione del FP-tree dal database originale.

• Per le prove sono stati utilizzati due database:– D1: nel quale la lunghezza della transazione media è pari a 25, l’itemset

frequente massimo è 10 e il numero di transazioni è 10.000 (T25.I10.D10K) con 1.000 items.

– D2: T25.I20.D100K con 10.000 items.

Confronto tra Apriori e FP-growth

Al diminuire della soglia nell’algoritmo Apriori, il numero e la lunghezza degli itemset frequenti aumenta notevolmente. L’insieme dei candidati che l’algoritmo deve gestire diventa molto alto e il test diventa molto dispendioso.

Analisi runtime/itemset

Il grafico sotto indica che se la soglia è bassa, il tempo per itemset con l’FP-growth diventa molto basso.

Scalaesponenziale

Scalabilità sul numero di transazioni

• Il grafico indica l’andamento dei due algoritmi al variare del numero di transazioni usando il database D2. La soglia è stata impostata a 1.5%.

• Entrambi gli algoritmi sono lineari, tuttavia FP-growth ha un runtime sempre inferiore ad Apriori

Confronto con TreeProjection

• TreeProjection è un efficente algoritmo basato sulla costruzione di un albero lessicografico. Il numero dei suoi nodi è quello delgi itemsets frequenti.

• TreeProjection risulta più efficente di Apriori.

• Come si vede dalla figura in alto, FP-growth e TreeProjection hanno buoni risultati ma il primo è sempre un po’ più veloce.

Modifiche future – FP-tree per database grandi (1)

• Quando il database è molto grande è impensabile costruire un FP-tree che possa risiedere tutte nella memoria principale.

• La soluzione è di partizionare il database e costruire un FP-tree e il mining per i vari database creati.

Modifiche future – FP-tree per database grandi (2)

• Un’alternativa alla soluzione precedente è quella di creare un FP-tree residente su disco.

• Il B+-tree viene utilizzato in molti databases e può essere usato per indicizzare l’FP-tree.

• I nodi del livello più alto del B+-tree possono essere divisi in base alle radici dei prefix-subtree.

Realizzazione di un FP-tree

• Ogni volta che si effettua una query, l’algoritmo deve costruire l’apposito FP-tree in base alla soglia passata come parametro.

• Se consideriamo, per esempio, che il 98% delle queries hanno 20, possiamo costruire un FP-tree con questa soglia e solamente nel 2% dei casi sarà necessario costruirne un’altro.

• Tenendo presente che un FP-tree è organizzato in modo che gli items meno frequenti siano posizionati più in basso, si potrà lavorare anche solo con la parte superiore dell’albero.

Aggiornamenti incrementali del FP-tree

• Avendo creato un FP-tree da usare per molteplici queries si deve pensare ad un sistema per aggiornarne i nodi quando nuove transazioni vengono inserite nel database.

• Se l’FP-tree è stato creato utilizzando = 1 (diventando quindi, una versione compatta del database), non ci sarebbero problemi, in quanto basterebbe aggiungere le ultime righe al FP-tree. In questo caso, l’albero potrebbe però diventare ingestibile per le grandi dimensioni.

• Nel caso generale, potrebbero sorgere dei problemi. Se l’albero originale era stato costruito con una certa , ad esempio 0,1% e si aggiungono molte entry al database potrebbe succedere che il supporto per certi items scenda sotto la soglia. La soluzione migliore è quella di ricostruire l’FP-tree.

Conclusioni (1)

• Ci sono tre vantaggi principali nell’uso di FP-growth:– Costruisce un FP-tree che è una struttura dati molto

compatta e che evita costose scansioni del database.– Applica il pattern growth metod che evita la

generazione di candidati concatenando successivamente 1-itemset frequenti trovati nel FP-tree.

– Utilizza un metodo basato sulle partizioni di tipo divide-et-impera che riduce drasticamente le dimensioni dei conditional pattern base e conditional FP-tree successivi.

Conclusioni (2)

• Gli studi sulle performances hanno dimostrato che il metodo è efficiente sia sui pattern corti che su quelli lunghi.

• Il metodo è stato implementato in una versione di DBMiner ed è stato testato in grandi databases industriali come il London Drugs database con performance soddisfacenti.