Riassunto esame Data mining, Prof. Marinai Simone, libro consigliato Mining of massive datasets, J.D Ullman

Complessità: dove N = numero di transazioni, M = numero di candidati,

2

ovvero , w = numero massimo di item in una transazione.

2

Dati item unici, e il numero di itemset possibili, allora il numero di possibili R.A. è

−1 −

⎡ ⎤

() ( ) +1

−

⎢ ⎥

. . = ∑ ∑ = 3 − 2 +1

dato da: ⎢ ⎥

⎣ ⎦

=1 =1

= 6 . . = 602

Es.: se allora .

Strategie per rendere più efficiente la generazione di itemset frequenti:

- escludere alcuni possibili itemset,

- ridurre il numero di transazioni considerate,

- euristiche per evitare di confrontare ogni possibile itemset con ogni

transazione.

→

Principio Apriori ridurre il numero di possibili itemset (= candidati): se un certo

itemset è frequente (ovvero ha un supporto maggiore della threshold), allora ogni

sottoinsieme di quell’itemset sarà frequente. Viceversa, se un certo sottoinsieme di

un itemset non è frequente, allora neanche l’itemset stesso sarà frequente.

∀, : ( ⊆ ) → () ≥ ()

La generazione dei candidati avviene assemblando K-itemsets basandosi sulla

frequenza allo step K-1.

Il pruning dei candidati avviene basandosi sul principio Apriori che dice appunto che

se un sottoinsieme di un itemset è poco frequente, allora lo è anche l’itemset stesso

→ ciò significa che, man mano creando itemset sempre più grandi, posso eliminare i

rami che avevano frequenze basse allo step K-1.

Inoltre, per generare un K-itemset candidato, la procedura Apriori unisce una coppia

= { , ..., } = { , ..., }

e per un (K-1)-itemset frequente SOLO nel caso

1 −1 1 −1

= , ∀ = 1, ..., − 2 ≠

in cui i primi K-2 item siano uguali: −1 −1

NB: l’ordine in cui gli item appaiono dovrebbe essere sempre lessicografico!

Es.:

= {, , , , }

3 ×

Join step: per la generazione dei candidati:

3 3

- a partire da e ,

- a partire da e .

Poi è rimosso dai candidati perché non è contenuto in .

3

= {}

Perciò si ha: 4

Es.:

Dati i seguenti itemset frequenti di 3 elementi:

= { {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {2, 3, 4}, {2, 3, 5}, {3, 4, 5} }

3 ×

trovare i 4-itemset candidati generati da :

3 3

× = { {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5} }

3 3 = 4

confrontando, dato che , i primi 2 elementi e fondendo gli itemset che hanno i

− 2 = 4 − 2 = 2

primi elementi uguali.

Una volta che ottengo i K-itemset candidati, verifico che tutti i suoi sottoinsiemi di

dimensione K-1 siano frequenti →

{1, 2, 3, 4} → {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} i primi due sono quelli che

hanno generato la fusione, devo quindi verificare che anche gli altri due siano

{1, 2, 3, 4}

frequenti. La prioprietà è verificata in questo caso, quindi è un candidato

valido. →

{1, 2, 4, 5} → {1, 2, 4}, {1, 2, 5}, {1, 4, 5}, {2, 4, 5} i primi due sono quelli che

hanno generato la fusione, devo quindi verificare che anche gli altri due siano

{1, 4, 5}

frequenti. In questo caso si ha però che ad esempio non sono frequenti,

{1, 2, 4, 5}

quindi posso scartare per il principio Apriori.

× = { {1, 2, 3, 4}, {1, 2, 3, 5} }

Si ha quindi che .

3 3

05/11/2019 Generazione regole

Dividiamo quindi la generazione di regole in due step:

- creazione degli itemset frequenti, grazie alla proprietà monotona del supporto

∀, : ( ⊆ ) ⇒ () ≥ ()

che attesta che , ovvero che se un certo

itemset è infrequente, allora anche tutti i suoi sottoinsiemi sono infrequenti, e

possono essere scartati. Gli itemset risultanti possono essere controllati per

essere eletti come itemset candidati,

- generare gli itemset candidati appaiando itemset che hanno i primi k-2

elementi uguali. Controllare se i k-sottoitems sono frequenti.

Obiettivo: ridurre il numero di comparazioni. Per fare ciò memorizzo gli itemset

candidati in una hash table, cercando di confrontare il candidato con le sole

transazioni che possono contenere quel candidato.

Lo scopo è la costruzione di un hash tree.

Necessario: ℎ() =

- hash function, per esempio dove p è l’item e n è la lunghezza

dell’item,

- max leaf size, ovvero la massima dimensionalità dell’insieme di item in una

foglia.

Bisogna quindi distribuire gli itemset candidati sull’albero a seconda del risultato

dell’applicazione della funzione hash, ovvero il resto della divisione intera.

Es.:

= { {1 4 5}, {1 2 4}, {4 5 7}, {1 2 5}, {4 5 8}, {1 5 9}, {1 3 6}, ..., {3 6 8} }

→

{1 4 5} ℎ({1 4 5}) = ℎ(1) = 1

al primo confronto eseguo quindi lo distribuisco

nel primo ramo.

→

{1 2 4} ℎ({1 2 4}) = ℎ(1) = 1

al primo confronto eseguo quindi lo distribuisco

nel primo ramo.

Effettuo la scelta di dove distribuire l’itemset considerato eseguendo, ad ogni step i,

l’operazione con l’i-esimo elemento dell’itemset.

Una volta che raggiungo in un nodo, distribuendo man mano gli itemset, la

dimensionalità massima, ovvero max leaf size, devo scendere di un livello e

ridistribuire gli itemset considerando l’(i+1)-esimo elemento per l’applicazione della

funzione hash.

Come utilizzo questa struttura per effettuare il numero minimo di confronti tra

itemset nell’hash tree e le transazioni?

Per farlo, ripercorro l’albero creato con la transazione stessa, escludendo i nodi che

sicuramente non corrispondono a possibili sotto-itemset della transazione.

Trovo i subset di ogni transazione e per ogni subset percorro l’albero e vedo in quale

foglia devo cercare gli itemset di lunghezza K prescelta. Se trovo nella foglia j-esima

l’itemset, aumento il suo counter di candidato.

Una volta trovato l’insieme di itemset frequenti , bisogna ora trovare tutti i

⊂ → −

sottoinsiemi non vuoti tali che soddisfa la proprietà di avere una

confidenza maggiore di una certa soglia.

= {, , , }

Per esempio, se è un itemset frequente, allora i candidati per

essere regole sono:

→ , → , → , → , → , → , → ,

→ , → , → , → , → , → , → .

= |

| → 2 − 2

Dato che in generale le regole sono candidati anche la

generazione delle regole a partire da deve essere effettuata in modo efficiente.

Abbiamo anche qui una proprietà anti-monotona per aiutarci:

( → ) ≥ ( → ) ≥ ( → )

Il che significa che la confidenza è anti-monotona rispetto al numero di item nella

parte destra della regola.

Supponiamo:

: → −

1 1 1

: → −

2 1 1

⊆ ( ) ≥ ()

con quindi

Si ha quindi che:

σ(∪(−)) σ()

( ) = =

σ() σ()

1 1 1

σ( ∪(− )) σ()

( ) = =

1 1

2 σ( ) σ( )

1 1

σ( ) ≥ σ() ( ) ≤ ()

Ma siccome si ha che ne derivo che .

Si ha quindi che se una regola non soddisfa il criterio di confidenza, neanche una

1

regola con la parte sinistra di che è sottoinsieme della parte sinistra di ,

2 2 1

soddisferà il criterio di confidenza. Scarto quindi tutte le regole sottostanti e derivanti

da .

1

06/11/2019 Item freq. max e pattern eval.

Si nota una differenza all’interno di weka nel caso in cui il file csv sia di tipo:

ID, item1, item2, item3, item4 ID, item1, item2, item3, item4

1, ?, t, ?, ? 1, no, yes, no, no

2, t, t, ?, ? 2, yes, yes, no, no

3, ?, ?, t, t 3, no, no, yes, yes

Nel primo caso weka interpreta e crea regole solo a partire dagli item che sono

effettivamente stati acquistati, ovvero che hanno la t corrispondente nella tabella.

Nel secondo caso invece crea associazioni e regole anche a partire dagli item che non

sono stati comprati.

Un altro formato di input per weka è quello sparso, in cui le transazioni sono

rappresentate nella forma:

@attribute item0 {f, t}

@attribute item1 {f, t}

@attribute item2 {f, t}

{1 t}

{1 t, 2 t}

{0 t, 1 t, 2 t}

Questa rappresentazione presenta le transazioni con elencati solo ed esclusivamente

gli item che sono stati acquistati. Weka poi elabora questo file comprendendolo come

una tabella con t nella cella [i-transazione][j-item] se il j-item è stato comprato nella

j-transazione, f altrimenti.

Alcuni item però sono ridondanti, perché hanno lo stesso supporto dei loro super-set

di item.

Definiamo quindi come “itemset massimale frequente” un itemset i cui sovra-insiemi

sono tutti itemset NON frequenti.

{} {}, {} {}

Es.: è massimale frequente se sono infrequenti.

Definiti quindi gli itemset frequenti massimali, so che i loro sotto-insiemi sono tutti gli

itemset frequenti.

Un itemset è definito chiuso qualora nessuno dei suoi immediati superset ha il suo

stesso supporto. Equivalentemente si ha che un itemset non è chiuso se almeno uno

sei suoi immediati superset ha lo stesso suo supporto.

NB: se un itemset è massimale allora è anche chiuso, perché se i superset non sono

frequenti, allora non hanno di sicuro lo stesso supporto.

Il supporto degli itemset frequenti non chiusi può essere ricavato dal supporto dei

superset frequenti chiusi.

Pattern evaluation

Vi sono differenti misure di interesse per quanto riguarda l’analisi associativa:

- misure oggettive, che derivano il carattere di interesse dalla statistica

(supporto, co