DBMG Data mining: regole di associazione -...

Pag. 1

Data mining: regole di associazione

Elena BaralisPolitecnico di Torino

DataBase and Data Mining Group of Politecnico di Torino

DBMG

DA TA MINING: REGOLE DI ASSOCIAZIONE - 1Copyright – Tutti i diritti riservati

Database and data mining group, Politecnico di Tor ino

D ataB ase and D ata Mi ning G roup of Pol i tecni co di T ori no

DBMG


Regole di associazione



DBMG




DBMG


Regole di associazione

• Ricerca di correlazioni in una collezione di dati– strumento efficace per analizzare i dati senza conoscenza

a priori delle correlazioni cercate– può restituire un numero elevato di regole– versatili: estraibili da tipologie di dati eterogenee (basi di

dati, testo, XML, …)– non rappresentano un nesso causa-effetto

• Numerosi ambiti applicativi– market basket analysis, cross-marketing, progettazione di

layout o di cataloghi




DBMG


Esempio• E` data una collezione di transazioni di cassa di

un supermercato (scontrini)• Regola di associazione

pannolini � birra– il 2% delle transazioni contiene entrambi gli elementi

– il 30% delle transazioni che contengono pannolini contiene anche birra

transazionicontenentibirra

transazionicontenentipannolini




DBMG


Definizione generale• Data una collezione di insiemi di oggetti

– insieme di oggetti = transazione– gli oggetti nella transazione non sono ordinati

• Regola di associazioneA, B � C

– A, B = oggetti nel corpo della regola

– C = oggetti nella testa della regola

• Esempi– fiocchi, biscotti � latte

– età = 42, assicurazione-vita = sì � figli = sì

– customer, relationship � data, mining




DBMG


Misure di qualitàA, B � C

• Supporto è la frequenza di A, B, Cnum. trans. contenenti A,B,C

num. trans. in base dati

– probabilita a priori dell’insieme A, B, C– frequenza statistica della regola

• Confidenza è la frequenza di C nelle transazioni contenenti A, B

num. trans. contenenti A,B,Cnum. trans. contenenti A,B

– probabilità condizionata di trovare C avendo trovatoA,B

– “forza” dell’implicazione




DBMG


Misure di qualità: esempio

• Estrazione regole con supporto minimo 50%

• Regola: A � C– supporto 50% – confidenza 66,6%

• Regola: C � A– supporto 50% – confidenza 100%

ID transazione Oggetti2 A,B,C1 A,C4 A,D5 B,E,F

Pag. 2




DBMG




DBMG


Uso delle regole di associazione

• Regole a supporto elevato(visione di alto livello delle correlazioni presenti, spesso già note)

• Regole a confidenza elevata(correlazioni forti, eventualmente poco frequenti)

• Analisi degli antecedenti* � birra

(cosa proporre per promuovere le vendite di birra?)• Analisi dei conseguenti

pannolini� *(cosa si vende contestualmente ai pannolini?)




DBMG


Tipologie di regole

• Regole di associazione “tradizionali”– richiedono attributi categorici– registrano la presenza/assenza di un oggetto

• Regole quantitative– definite su attributi con valori continui– soluzione più semplice è la discretizzazione

• Regole multilivello– definite su gerarchie di generalizzazione

• Maximal itemsets, closed itemsets




DBMG


Procedimento di estrazione

Itemset frequenti Supporto{A} 75%{B} 50%{C} 50%{A,C} 50%

ID transazione Oggetti2 A,B,C1 A,C4 A,D5 B,E,F

1. Estrazione degli item frequenti

2. Estrazione degli itemset con due elementi a partire dagli item frequenti

3. Se possibile, continua con n>2

• Supporto minimo 50%• Confidenza minima 50%

Principio Apriori: ogni sottoinsieme di un itemset frequente deve essere a sua volta frequente




DBMG


Procedimento di estrazione

1. Estrazione degli itemset frequenti• procedimento iterativo a livelli (Apriori)• procedimento senza generazione dei candidati (FP-

growth)• passo computazionalmente più costoso• limitazione della complessità mediante soglia di

supporto

2. Estrazione delle regole di associazione• generazione di tutte le combinazioni a partire dagli

itemset frequenti




DBMG


Regole di associazione multilivello

• Combinano elementi a livelli diversi della gerarchia– le correlazioni interessanti potrebbero non essere a

livello di singolo codice a barre

• Soglie di supporto diverse– livelli inferiori caratterizzati da elementi con supporto

basso– elementi nei livelli superiori hanno supporto elevato




DBMG


Esempio

• Gerarchia merceologica: codice UPC, sottocategoria, categoria merceologica

alimentari

bevande dolci

limonata vino panforte panettone

• regola Moscato XYZ

– vino � dolci valida anche se

• bevande � dolci non ha confidenza suff.• Moscato XYZ � dolci non ha supporto suff.

Pag. 3




DBMG




DBMG


Misure di interesse

• Misure oggettive– supporto: frequenza della regola– confidenza: forza della regola, talvolta non

attendibile

• Misure soggettive– imprevedibilità

– usabilità




DBMG


Confidenza: una misura sempre affidabile?

• Sono dati 5000 studenti (high school USA)– 3750 mangiano cereali a colazione– 3000 giocano a basket– 2000 mangiano cereali e giocano a basket

• La regolagioca a basket �mangia cereali

supporto = 40%, confidenza = 66,7% è fuorviante perchémangia cereali ha supporto 75% (>66,7%)

basket not basket totalecereali 2000 1750 3750not cereali 1000 250 1250totale 3000 2000 5000

• Problema causato dalla frequenza elevata della testa della regola– correlazione

negativa




DBMG


Correlazione o lift

Correlazione =)()(

),(

BPAP

BAP

sup(B)

conf(r)=

• Indipendenza statistica– Correlazione = 1

• Correlazione positiva– Correlazione > 1

• Correlazione negativa– Correlazione < 1

r: A � B




DBMG


Esempio

• La regola di associazionegioca a basket � mangia cereali

ha corr = 0.89• È presente una correlazione negativa

gioca a basket � not (mangia cereali)

con corr = 1,34

DBMG Data mining: regole di associazione -...

Documents

Transcript of DBMG Data mining: regole di associazione -...