Corso di Basi di Dati Introduzione al Data Mining Home page del corso: difelice/dbsi

Corso di Basi di Dati

Introduzione al Data MiningHome page del corso:

http://www.cs.unibo.it/~difelice/dbsi/

Introduzione al Data Mining

Data Mining: tecniche di apprendimento computerizzato per analizzare ed estrarre conoscenze da collezioni di dati.

Pattern e relazioni non note a priori e non immediatamente identificabili.

Disciplina complessa: utilizzo di tecniche di machine learning, intelligenza artificiale e statistiche …

Previsioni di dati temporali (es. vendite)

Market Basket Analysis (vi siete mai chiesti come mai tanti tornei di golf sono sponsorizzati da societa’ di brokeraggio? )

Scoperta di truffe (es. clonazioni di carte di credito)

Campagne pubblicitarie mirate Churn Analysis (analisi della clientela che

potrebbe passare alla concorrenza) Segmentazione della clientela …

ESEMPI di APPLICAZIONI (aziendali)


BUSINESS INTELLIGENCE (BI) (def.) Insieme di processi aziendali, metodologie tool per raccogliere i dati di un’azienda, ed estrarre informazioni di supporto alla decisioni strategiche.


DATA MINING componente essenziale del processo di BI, si occupa di estrarre informazioni utili dai dati per aiutare il processo decisionale …

BUSINESS INTELLIGENCE (BI) (def.) Insieme di processi aziendali, metodologie tool per raccogliere i dati di un’azienda, ed estrarre informazioni di supporto alla decisioni strategiche.


DATA MINING componente essenziale del processo di BI, si occupa di estrarre informazioni utili dai dati per aiutare il processo decisionale …Sorgente: http://www.conbusinessintelligence.com/

Q. Da dove derivano i dati da analizzare?


Dati posseduti da un’azienda/organizzazione e custodoti in un DB operazionale.

Dati estratti dal Web (es. OPEN DATA)

Dati estratti dai social media

DBMS

Q. Da dove derivano i dati da analizzare?


Dati posseduti da un’azienda/organizzazione e custodoti in un DB operazionale.

Dati estratti dal Web (es. OPEN DATA)

Dati estratti dai social media

DBMS

+

+


Q. Dove memorizzare i dati necessari per l’analisi?

DBMS

DW ANALISI

REPORT

Un data warehouse e’ una collezione di dati (non volatile) finalizzata al supporto del processo decisionale.


Un data warehouse e’ un database relazionale finalizzato all’analisi ed al processo decisionale.

Q. Che differenza c’e’ tra un data warehouse ed i database operazionali visti fin qui nel corso?

R. A basso livello, nessuna (modello relazionale chiavi, tabelle, vincoli integrita’, SQL, etc)

R. Le differenze principali sono nella progettazione!


Differenze principali tra database operazionali (visti fin qui) e data warehouse.

OPERAZIONI sui DATI

Database operazionali Accessi multipli ai dati, aggiornamenti costanti nel tempo, possibile alta concorrenza delle operazioni lettura/scrittura.

Data warehouse Accesso in sola lettura, dati storici e non soggetti a cambiamento.



RAPPRESENTAZIONI dei DATI

Database operazionali I dati delle tabelle sono normalizzati (Prima/Seconda/Terza Forma Normale) per ridurre la ridondanza dei dati.

Data warehouse I dati sono rappresentati in forma denormalizzata per evitare operazioni (costose) di join tra le tabelle troppo frequenti.



GRANULARITA’ dei DATI

Database operazionali Ogni riga contiene informazioni relative ad operazioni di inserimento(insert SQL), eseguite sul database.

Data warehouse I dati rappresentano informazioni aggregate, utili per la reportistica, spesso ottenute processando altri dati (del db).


Esistono opportune metodologie (che non vedremo) per progettare un data warehouse relazionale.

MODELLO OLAPMODELLO A STELLA

Noi ci concentriamo ora sul processo di analisi dei dati …


Data mining estrae informazioni da un DB.

Data query (SELECT) estrae dati da un DB relazionale (in particolare, dalle tabelle della FROM).Q. Che differenza esiste tra i due

approcci?A. Il processo di data mining estrae regolarita’ e pattern sui dati che non sono note a priori, e che non possono essere ricavate da query SQL.


Un’azienda di telefonia vuole analizzare il data-set dei propri clienti abbonati, in modo da:

Costruire una profilazione della clientela, in modo da individuare un possibile nuovo cliente, a partire dai suoi dati (es. eta’, sesso, lavoro, etc).

Determinare quali utenti abbonati possono essere interessati ad una nuova offerta (es. abbonamento Internet con tecnologia LTE).Q. Da dove partire per effettuare l’analisi?

ESEMPIO di PROCESSO di DATA-MINING


CRISP-DM (Cross Industry Data Process for Data Mining) metodologia standard e generale per l’implementazione di un processo di data mining.

BUSINESSUNDERSTANDING

DATAUNDERSTANDING

DATAPREPARATION

MODELINGEVALUATION

DEPLOYMENT DB DW


In questa fase, e’ necessario comprendere bene gli obiettivi che il sistema dovrebbe raggiungere (es. modello predizione costi?) ed i requisiti del committente.

Inventario delle risorse disponibili. Requisiti, presupposti e vincoli. Analisi dei rischi/imprevisti. Analisi dei costi/benefici.

BUSINESS UNDERSTANDING


Nel caso di studio (azienda di telefonia), la fase di business understanding include la formulazione delle risposte ai seguenti quesiti: Che margine di profitto mi aspetto di ottenere

dal modello di previsione dei nuovi clienti? Che margine di risparmio mi aspetto di

ottenere effettuando pubblicita’ mirata delle nuove offerte?

Quali sono i costi necessari per implementare il modello di data-mining nel processo decisionale?

…





DATAUNDERSTANDING

DATAPREPARATION

MODELINGEVALUATION

DEPLOYMENT DB DW


In questa fase, e’ necessario comprendere bene quali dati sono fondamentali per la costruzione del modello di data mining.

Report dei dati disponibili. Costruzione del dataset. Strategie di recupero dati mancanti. Criteri di verifica della qualita’ dei dati.

DATA UNDERSTANDING


Nel caso di studio (azienda di telefonia), la fase di data understanding include la formulazione delle risposte ai seguenti quesiti: Ho a disposizione tutti i dati necessari per

poter classificare gli utenti del mio servizio? Devo prevedere campagne di raccolte dati (es.

attraverso survey o interviste telefoniche?) Posso estendere il mio data-set includendo dati

provenienti da altre fonti (es. social media)? …





DATAUNDERSTANDING

DATAPREPARATION

MODELINGEVALUATION

DEPLOYMENT DB DW


Molti algoritmi di data-mining richiedono di trasformare i dati in un opportuno formato per poter essere eseguiti efficacemente.

Es. Gli algoritmi di classificazione lavorano spesso su un numero discreto di classi da riconoscere, sebbene i dati in questione abbiano un dominio “continuo”.

DATA PREPARATION


DATA PREPARATION

Codice Macchina

Eta Casa Reddito

Erogazione

1332 SI 26 SI 10500 SI

2232 NO 40 SI 20000 SI

4323 NO 60 NO 5000 NO

STORICO EROGAZIONI

Se Reddito <= 10000 0Se Reddito> 10000 & Reddito < 15000 1Se Reddito >= 15000 2

Reddito

1

2

0REGOLE di CLASSIFICAZIONE

Costruire un modello di data-miningper decidere l’erogazione di una carta di credito

sulla base della segmentazione degli utenti.


Molti algoritmi di data-mining lavorano su dati normalizzati su un intervallo (es. [0,1]).

DATA PREPARATION

Normalizzazione Massimo/Minimo:

0

0.11

0.55

1

15

20

40

60

ValMin ValMax

0 1


Molti algoritmi di data-mining lavorano su dati normalizzati in base alla media dei valori.

DATA PREPARATION

Normalizzazione con Deviazione Standard:

0

0.11

0.55

1

15

20

40

600

Media


In molti data-set, possono essere presenti dati anomali (out-lier) che possono alterare l’analisi.

DATA PREPARATION

Reddito

1-R

isch

io

1

1

0

Dati anomali …1) Come identificarli?2) Come gestirli?

In molti casi, l’obiettivo del processo di data

mining consiste nella ricerca degli outlier (es.

analisi frodi)!


In molti data-set, possono essere presenti dati anomali (outlier) che possono alterare l’analisi.

DATA PREPARATION

Reddito

1-R

isch

io

1

1

0

Dati anomali …1) Come identificarli?

Es. Range valori consentiti:[Media – Y*Dev: Media+Y*Dev]

Se X fuori dal range OUTLIER!



DATA PREPARATION

Reddito

1-R

isch

io

1

1

0

Dati anomali …1) Come identificarli?

Es. : Metodo dei viciniX(x1,y1) e Y (x2,y2) sono vicini se:

Se #Vicini(X) < Soglia OUTLIER!



DATA PREPARATION

Reddito

1-R

isch

io

1

1

0

Dati anomali …1) Come identificarli?2) Come gestirli?

Rimovere gli outlier Sostituirli con valori NULL Sostituirli con Media(Val) …


In molti data-set, possono essere presenti dati incompleti che possono condizionare l’analisi.

DATA PREPARATION

Codice Macchina

Eta Casa Reddito

Erogazione

1332 SI ??? SI 10500 SI

2232 NO 40 ??? 20000 SI

4323 ??? 60 NO ??? NO

STORICO EROGAZIONI

Q. Come gestire i record con informazioni incomplete?


In molti data-set, possono essere presenti dati incompleti che possono condizionare l’analisi.

DATA PREPARATION

Codice Macchina

Eta Casa Reddito

Erogazione

1332 SI ??? SI 10500 SI

2232 NO 40 ??? 20000 SI

4323 ??? 60 NO ??? NO

STORICO EROGAZIONI

Q. Come gestire i record con informazioni incomplete?

Diverse possibilita’:

Scartare record incompleti Rimpiazzare ??? con valori NULL Rimpiazzare ??? con il valore medio dell’attributo Rimpiazzare ??? Con un valore che non alteri la deviazione Standard dei valori dell’attributo Rimpiazzare ??? Con valori “plausibili” dell’attributo sulla base di valori simili. …


In molti contesti e’ opportuno ridurre il numero di attributi del data-set da analizzare …

DATA PREPARATION

STORICO EROGAZIONI

Ragioni di efficienza + Attributi: > Maggior tempo di computazione Ragioni di accuratezza Alcuni attributi non sono utili per l’analisi

Codice

CF Macchina Eta Casa Reddito

Erogazione

1332 ADFDS802M

SI 26 SI 10500 SI

2232 FSFSS102M NO 40 SI 20000 SI

4323 MRGTY43R NO 60 NO 5000 NO

Informazione non utile per il modello …


L’attivita’ di data preparation e’ molto delicata, le scelte effettuate possono condizionare l’analisi …

DATA PREPARATION

STORICO EROGAZIONI

Codice Macchina

Eta Casa Reddito

Erogazione

1332 SI 20 SI 10500 SI

2232 NO 40 SI 20000 SI

4323 SI 60 NO 500000

NO

SCELTA 1: Seleziono la riga come outlier e la rimuovo …



DATA PREPARATION

STORICO EROGAZIONI

Codice Macchina

Eta Casa Reddito

Erogazione

1332 SI 20 SI 10500 SI

2232 NO 40 SI 20000 SI

4323 SI 60 NO 500000

NO

SCELTA 1: Seleziono la riga come outlier e la rimuovo …

Valore medio Reddito: 15250



DATA PREPARATION

STORICO EROGAZIONI

Codice Macchina

Eta Casa Reddito

Erogazione

1332 SI 20 SI 10500 SI

2232 NO 40 SI 20000 SI

4323 SI 60 NO 500000

NO

SCELTA 2: Non rimuovo la riga, nessun outlier …

Valore medio Reddito: 176833




DATAUNDERSTANDING

DATAPREPARATION

MODELINGEVALUATION

DEPLOYMENT DB DW


Algoritmi diversi, per risolvere problemi diversi:Classificazione

Determinare se gli attributi di una certa istanza appartengono o meno ad una classe.

PredizionePredire il valore di una serie temporale (valori

continui).Associazione

Determinare regole del tipo: Se X allora Y.Segmentazione

Scoprire pattern sui dati, raggruppare istanze simili in gruppi (cluster) di istanze.


Data un’istanza (record) di dati su N attributi:

A(x1,x2,x3,x4,x5, … xN)Dato un insieme di M possibili classi:

C={c1,c2, … cM}

INPUT

OUTPUT

Determinare la classe cj cui appartiene l’istanza A.COME?

Mediante apprendimento supervisionato …


Un Training-Set e’ definito come un insieme di record: T={(Aj,cjk)}

Aj e’ un record su N attributi: (xj1,xj2, … xjN)

cjk e’ la classe cui appartiene il record Aj

TRAINING-SET

Q. Da dove ottengo il Training-Set?

A. Spesso disponibile come storico di dati disponibili nel DB o nel DW, o costruito da fonti esterne.


Un Training-Set e’ definito come un insieme di record: T={(Aj,cjk)}

Aj e’ un record su N attributi: (xj1,xj2, … xjN)

cjk e’ la classe cui appartiene il record Aj

TRAINING-SET

DATA-SET

ALGORITMOCLASSIFICAZIONE+

MODELLO

Istanza Ai

CjFase di TRAINING

Fase di TESTING{<Aj,cij>}


Esempio. Determinare se un certo cliente puo’ essere interessato o meno ad acquistare un auto berlina, ai fini di migliorare la campagna pubblicitaria. TRAINING SET

NrUtente

StatoConiugale

Sesso #NucleoFamiliare

RedditoAnnuo

Acquisto

1 Celibe M 1 30000 SI

2 Nubile F 1 45000 NO

3 Sposato M 4 35000 SI

Data-set derivato dai risultati diprecedenti campagne pubblicitarie

TESTING SET <4, Sposato, M, 3, 38000> ACQUISTO??


A. Quale algoritmo usare?Q. Non esiste un classificatore ottimo in assoluto, dipende dallo scenario applicativo …

Naïve Bayes Reti Bayesiane Alberi di decisione Random Forest Support Vector Machines (SVM) …

ALGORITMI di CLASSIFICAZIONE


Il classificatore NB utilizza una tecnica statistica con la quale si cerca di stimare la probabilita’ di un istanza di appartenere ad una certa classe.

CLASSIFICATORE NAÏVE BAYES (NB)

Istanza A(x1, …xN) da classificare. P(cj|A) probabilita’ condizionata di avere unaclasse cj,vendendo un’istanza A.

In NB, scelgo la classe ck, tale che:

Come calcolare P(cj|A)??


Probabilita’ condizionata:

Probabilita’ congiunta (in caso di eventi indipendenti):

Teorema di Bayes:

Applicando il Teorema di Bayes al nostro problema:


Semplificando il problema …

Il record A e’ composto di N Attributi: A(x1,x2, …xN)

Assumendo che gli N attributi siano tutti indipendenti …


Conclusione L’algoritmo di NB sceglie la classe cj che massimizza la quantita’:

PROBLEMA: Come stimare P(cj) e P(xi|cj)?

Possibile Soluzione: Approssimo le probabilita’ come frequenze relative, rispetto ai valori del mio training set.


NrUtente

Sposato Sesso #NucleoFamiliare

RedditoAnnuo

Acquisto

1 NO M 4 0 NO

2 NO F 1 1 NO

3 SI M 4 1 SI

4 SI F 3 0 NO

5 NO M 1 1 NO

6 SI F 3 1 SI

Reddito <30000 0, Reddito >=30000 1

A=<4, Sposato, M, 3, 38000>

C(SI)=2/6=0.33

C={SI, NO}

C(NO)=4/6=0.67


NrUtente


RedditoAnnuo

Acquisto

1 NO M 4 0 NO

2 NO F 1 1 NO

3 SI M 4 1 SI

4 SI F 3 0 NO

5 NO M 1 1 NO

6 SI F 3 1 SI

Reddito <30000 0, Reddito >=30000 1

A=<4, Sposato, M, 3, 38000>

C(4|SI)=1/2=0.5 C(4|NO)=1/4=0.25


NrUtente


RedditoAnnuo

Acquisto

1 NO M 4 0 NO

2 NO F 1 1 NO

3 SI M 4 1 SI

4 SI F 3 0 NO

5 NO M 1 1 NO

6 SI F 3 1 SI

Reddito <30000 0, Reddito >=30000 1A=<4, Sposato, M, 3, 38000>

C(Sposato|NO)=1/4=0.25C(Sposato|SI)=2/2=1

C(M|SI)=1/2=0.5 C(M|NO)=2/4=0.5 C(3|SI)=1/2=0.5

C(3|NO)=1/2=0.5 C(1|SI)=1/2=1 C(1|NO)=2/4=0.5


NrUtente


RedditoAnnuo

Acquisto

1 NO M 4 0 NO

2 NO F 1 1 NO

3 SI M 4 1 SI

4 SI F 3 0 NO

5 NO M 1 1 NO

6 SI F 3 1 SI


C(SI|<4,Sposato,M,3,38000>) 0.33*0.5*1*0.5*0.5*1=0.04125

C(NO|<4,Sposato,M,3,38000>) 0.67*0.25*0.25*0.5*0.5*0.5=0.0108


NrUtente


RedditoAnnuo

Acquisto

1 NO M 4 0 NO

2 NO F 1 1 NO

3 SI M 4 1 SI

4 SI F 3 0 NO

5 NO M 1 1 NO

6 SI F 3 1 SI


C(SI|<4,Sposato,M,3,38000>) 0.33*0.5*1*0.5*0.5*1=0.04125

C(NO|<4,Sposato,M,3,38000>) 0.67*0.25*0.25*0.5*0.5*0.5=0.0108

Classificata come SI


Una rete bayesiana e’ un modello (visuale) per rappresentare le interazioni e le dipendenze tra variabili casuali (random variable).

A

B

C D

Ogni nodo e’ una variabile casuale.

Un arco da X ad Y indica che X ha un’influenza su Y, ossia che le due variabili NON sono indipendenti (P(Y|X) <> P(Y)).

L’assenza di archi tra due nodi indica che le due variabili sono indipendenti.

DAGGrafo Diretto Aciclico



A

B

C D

Ogni nodo Xi dispone di una distribuzione di probabilita’ P(Xi | Parents(Xi)) che quantifica gli effetti dei nodi padre sui figli.


A P(A)

false 0.6

true 0.4



A

B

C D



A B P(B|A)

false false 0.01

false true 0.99

true false 0.7

true true 0.3



A

B

C D



B C P(C|B)

false false 0.4

false true 0.6

true false 0.9

true true 0.1

B D P(D|B)

false false 0.02

false true 0.98

true false 0.05

true true 0.95


Tramite le reti Bayesiane, e’ possibile modellare comportamenti causa-effetto tra variabili casuali, ed effettuare diagnosi (= determinare la probabilita’ della causa dato l’effetto).

Irrigazione ON

Pioggia

Erba Bagnata

P(I=true)=0.2

P(I=false)=0.8

P(R=true)=0.4

P(R=false)=0.6

P(E|I=true, R=true)=0.05

P(E|I=true, R=false)=0.95

P(E|I=false, R=true)=0.90 P(E|I=false,

R=false)=0.10


Irrigazione ON

Pioggia

Erba Bagnata

P(I=true)=0.2

P(I=false)=0.8

P(R=true)=0.4

P(R=false)=0.6




R=false)=0.10


Tramite le reti Bayesiane, e’ possibile effettuare classificazioni di istanze A(x1, …xN). In questo caso la rete e’ composta da:

Nodo padre della rete Classi cj da determinare

Nodi foglia ed intermedi Singoli attributi xi

Si sceglie la classe ck, tale che:


Un esempio di classificatore basato su reti Bayesiane.

Spam Email

A1

C={Spam, No Spam}

A2

A={a1,a2} istanza da classificare

A1={true,false} Contiene Poste Spa nel subject della email?

A2={true,false} Contiene dei link HTML nel testo?


Un esempio di classificatore basato su reti Bayesiane.

Spam Email

A1

C={Spam, No Spam}

A2

A={a1,a2} istanza da classificare

A1={true,false} Contiene Poste Spa nel subject della email?

A2={true,false} Contiene dei link HTML nel testo?

P(C=Spam)=0.4

P(A1=true| C=Spam)=0.8…

P(A2=true|A1=true, C=Spam)=0.95….


Un esempio di classificatore basato su reti Bayesiane. Supponendo di dover classificare A(true, false):

Confronto i due valori, e scelgo la classe che garantisce la probabilita’ piu’ alta associata all’istanza A.

Q. Come calcolare la probabilita’ congiunta?



In una rete bayesiana con variabili casuali X1, X2, … XN, vale il seguente risultato:


Insieme di M elementi A={a1,…aM} Ogni elemento e’ composto da N

attributi

INPUT

OUTPUT

Determinare regole della forma Se X allora Y

Le regole associative rappresentano uno strumentoper scoprire relazioni (possibilmente non banali) tra gli elementi di una base di dati.


APPLICAZIONI

Market basket analysis identificare correlazioni(non banali) tra gli acquisti operati da un cliente.

Nr Transazione

Pane

Pasta Burro Olio Marmellata

1 0 1 0 1 1

2 1 0 1 0 1

3 1 0 1 1 1

4 0 1 1 1 1Pasta OlioPane, Burro MarmellataPane Olio, Burro

ESEMPIO DI REGOLE


APPLICAZIONI


Nr Transazione

Pane


1 0 1 0 1 1

2 1 0 1 0 1

3 1 0 1 1 1

4 0 1 1 1 1ItemSet Combinazione di valori degli attributi dello schema

Supporto(ItemSet)


APPLICAZIONI


Nr Transazione

Pane


1 0 1 0 1 1

2 1 0 1 0 1

3 1 0 1 1 1

4 0 1 1 1 1 Supporto{Pane}=2/4=0.5 Supporto{Pane,Pasta}=0/4=0 Supporto{Pane,Burro,Marmellata}=2/4=0.5


APPLICAZIONI


Nr Transazione

Pane


1 0 1 0 1 1

2 1 0 1 0 1

3 1 0 1 1 1

4 0 1 1 1 1Data una regola associativa: XY

Supporto della regola XY


APPLICAZIONI


Nr Transazione

Pane


1 0 1 0 1 1

2 1 0 1 0 1

3 1 0 1 1 1

4 0 1 1 1 1s(Pasta Olio) = 2/3=0.66s(Pane Burro) = 1/3=0.33s(Pane Burro Marmellata) = 2/3=0.66


APPLICAZIONI

Market basket analysis identificare correlazioni(non banali) tra gli acquisti operati da un cliente.Possibile algoritmo:

1. Per ogni possibile sottoinsieme di attributi Y: si calcola il supporto s(Y).

2. Per ogni possibile coppia di combinazioni di attributi (X,Y) : Si calcola il supporto della regola s(XY).

3. Si scelgono le regole per cui: s(XY) > Soglia


APPLICAZIONI

Market basket analysis identificare correlazioni(non banali) tra gli acquisti operati da un cliente.Possibile algoritmo:

1. Per ogni possibile sottoinsieme di attributi Y si calcola il supporto s(Y).

2. Per ogni possibile coppia di combinazioni di attributi (X,Y) Si calcola il supporto della regola s(XY).

3. Si scelgono le regole per cui: s(XY) > SogliaPROBLEMA: Costo computazionale dell’algoritmo?


ALGORITMO APRIORI

L’algoritmo utilizza un approccio bottom-up.

Si costruiscono insiemi di oggetti (itemset) frequenti aggiungendo un elemento alla volta.

Regole di pruning: Se un itemset e’ frequente tutti i

suoi sottoinsiemi sono frequenti. Se un itemset non e’ frequente

neanche gli insiemi che lo contengono sono frequenti.


ALGORITMO APRIORI ESEMPIO di FUNZIONAMENTO

Promozione giornali

Promozione orologi

Promozione

assicurazione

Assicurazione Carta

Sesso

SI NO NO NO Maschio

SI SI SI NO Femmina

NO NO NO NO Maschio

SI SI SI SI Maschio

SI NO SI NO Femmina

NO NO NO NO Femmina

SI NO SI SI Maschio

NO SI NO NO Maschio

SI NO NO NO Maschio

SI SI SI NO Femmina


ALGORITMO APRIORI FREQUENZA ITEMSET (1 attributo)

ItemSet # Oggetti

Promozione giornali=SI 7

Promozione giornale=NO 3

Promozione orologi=SI 4

Promozione orologi=NO 6

Promozione assicurazione vita=SI

5

Promozione assicurazione vita=NO

5

Promozione carta credito=SI 2

Promozione carta credito=NO 8

Sesso=Maschio 6

Sesso=Femming 4

Definisco cardinalita’minima cmin=4

Scarto itemset concardinalita’ < cmin


ALGORITMO APRIORI FREQUENZA ITEMSET (2 attributi)

ItemSet # Oggetti

Promozione giornali=SI & Promozione Orologi =NO 7

Promozione giornali=SI & Promozione Assicurazione Vita = SI 4

Promozione giornali=SI & Assicurazione carta credito=NO 6

Promozione giornali=SI & Sesso=Maschio 5

Promozione orologi=NO & Promozione Assicurazione Vita=NO 5

Promozione orologi=NO & Assicurazione carta credito=NO 8

Promozione orologi=NO & Sesso=Maschio 6

Promozione Assicurazione Vita=NO & Assicurazione carta credito=NO

4

Promozione Assicurazione Vita=NO & Sesso=Maschio 4

Promozione Assicurazione Vita=NO & Sesso=Femmina 4

Assicurazione carta credito=NO & Sesso=Femmina 4



ItemSet # Oggetti

Promozione giornali=NO & Promozione Assicurazione Vita=NO &Assicurazione carta credito=NO

4

Genero le regole associative, partendo dalla tabella con oggetti tripli e poi analizzando la tabella con oggetti doppi.

Definisco un livello minimo di supporto smin.

Genero solo le regole (XY) per cui: s(XY)>smin.



ItemSet # Oggetti

Promozione orologi=NO & Promozione Assicurazione Vita=NO &Assicurazione carta credito=NO

4

SE (Promozione orologi=NO & Promozione Assicurazione Vita=NO) ALLORA Assicurazione carta credito=NO

SE (Promozione orologi=NO) ALLORA (Promozione Assicurazione Vita=NO) & (Assicurazione carta credito=NO)

SE (Promozione Assicurazione Vita=NO) & (Assicurazione carta credito=NO) ALLORA (Promozione orologi=NO)

POSSIBILI REGOLE (3 attributi):



ItemSet # Oggetti


4


SE (Promozione orologi=NO) ALLORA (Promozione Assicurazione Vita=NO) & (Assicurazione carta credito=NO)


POSSIBILI REGOLE (3 attributi):s(X->Y)=4/4=1

s(X->Y)=4/6=0.6

s(X->Y)=4/5=0.8



ItemSet # Oggetti


4



Definisco una soglia minima smin=0.75s(X->Y)=4/4=1

s(X->Y)=4/5=0.8



Itero lo stesso processo di generazione delle regole anche

per itemset composti da 2 oggetti …

Al termine, l’insieme di regole generato dall’algoritmo potrebbe contenere delle regole banali o contenute in altre regole possibile una fase di pruning delle regole.

ItemSet # Oggetti

Promozione giornali=SI & Promozione Orologi =NO 7

…. …FASI SUCCESSIVE DELL’ALGORITMO


Insieme di N elementi da partizionare Numero di Classi: NC

INPUT

OUTPUT

Determinare la composizione di ogni classe c0<=i<nc

La cluster/segmentation analysis e’ un insieme di tecniche per raggruppare oggetti in classi tra loro omogenee, ossia con caratteristiche simili.


Ricerche di mercato Segmentazione della clientela Analisi dei social media Identificazione degli outlier …

POSSIBILI APPLICAZIONI

Es. Database dei correntisti di una banca. Quali attributi simili consentono di raggrupare i

clienti? Quali differenze tra i valori degli attributi (es. tipo

del conto, eta’, sesso, etc) segmentano il database?


Algoritmo di clusterizzazione non-gerarchico.

Richiede di indicare il numero di cluster (insiemi) che si vogliono creare (NC).

Gli elementi da classificare sono attributi con valori reali. Nel caso di attributi testuali, e’ necessaria una conversione di dominio.

Es. Colore: {rosso, blu, verde} {0,1,2} Basata sul concetto di distanza tra

elementi

ALGORITMO DELLE K-MEDIE (K-MEANS CLUSTERING)


Distanza tra due elementi in uno spazio euclideo 2D

Distanza tra due elementi in uno spazio euclideo ND

Centroide di un gruppo (2D):c(a1,a2, … aM)


1. Assegno casualmente gli elementi A={a1, …,aM} alle NC

classi di clusterizzazione.2. Ripeto le seguenti operazioni:

2.1 Calcolo il centroide cj di ogni classe j2.2 Calcolo la distanza tra ogni elemento ai ed

ogni centroide cj d(ai,cj)2.3 Assegno l’elemento ai al cluster j con

centroide piu’ vicino j=argmin(d(ai,cj))

3. Concludo il ciclo quando: Il passo 2.3 non produce differenze rispetto all’ assegnamento del passo precedente (convergenza). L’errore della clusterizzazione < Emin (soglia

d’errore).


Q. Come definire l’errore della classificazione?

Dato un elemento ai(ai,x,ai,y) c(ai) centroide del cluster cui e’ assegnato l’elemento ai.

A. Errore quadratico medio somma (al

quadrato) delle distanze tra ai e c(ai), per tutti gli elementi ai.La classificazione termina quando l’errore diventa

minore di una soglia Emin (e<Emin).


Es.: A={insieme di info sui clienti di una banca} A={ax,y} axReddito ayEta’ A={(12000,24), (28000,28), (15000,24), (36000,39), (34000,35), (19000,27), (39000,35), (26000,28), (32000,32) }

NC=#cluster da formare=3

5 10 15 20 25 30 35 40

10

20

30

Eta

Stipendio x 10000

**

*

**

*

*

* * * = ax,y




5 10 15 20 25 30 35 40

10

20

30

Eta

Stipendio x 10000

**

*

**

*

*

* *

* = ax,y

STEP 1

Creazionecasuale dei cluster




5 10 15 20 25 30 35 40

10

20

30

Eta

Stipendio x 10000

**

*

**

*

*

* *

* = ax,y

STEP 2.1

Loop:Calcolo centroidi

++

+




5 10 15 20 25 30 35 40

10

20

30

Eta

Stipendio x 10000

**

*

**

*

*

* *

* = ax,y

STEP 2.2

Loop:Calcolo distanze

++

+




5 10 15 20 25 30 35 40

10

20

30

Eta

Stipendio x 10000

**

*

**

*

*

* *

* = ax,y

STEP 2.3

Loop:Riassegnamento




5 10 15 20 25 30 35 40

10

20

30

Eta

Stipendio x 10000

**

*

**

*

*

* *

* = ax,y

STEP 3

Loop:Valuto condizione

CONVERGENZA?Non ancora …




5 10 15 20 25 30 35 40

10

20

30

Eta

Stipendio x 10000

**

*

**

*

*

* *

* = ax,y

RISULTATOFINALE


PROBLEMA: L’algoritmo delle k-medie richiede di conoscere a priori il numero di cluster (NC) da creare.

Q. Se non conosco il valore esatto di NC?

A. Provo con diversi valori di NC, e poi scelgo quello che garantisce il minor errore quadratico medio.

Numero cluster (NC) Errore quadratico medio

3 2.345

4 2.155

5 4.556




DATAUNDERSTANDING

DATAPREPARATION

MODELINGEVALUATION

DEPLOYMENT DB DW


La fase di valutazione del modello e’ necessaria perquantificarne l’accuratezza e quindi l’affidabilita’. Necessari opportuni indici di stima per

quantificare la bonta’ del modello … In base agli indici, si puo’ valutare se

occorre cambiare il modello oppure se si puo’ procedere con l’ultima fase del CRISP-DM (deployment). Necessaria una fase di testing del

modello.


Esempio. Determinare se un certo cliente puo’ essere interessato o meno ad acquistare un auto berlina, ai fini di migliorare la campagna pubblicitaria.

1.Costruisco il classificatore (es. Naïve Bayes) a partire dal Training Set.

2. Applico il classificatore su un certo insieme di istanze di test, ed ottengo un insieme di risposte R.

3. Osservo la classificazione reale dei dati (Rreal).

4. Confronto R ed Rreal, e calcolo indici di stima.


MATRICE di CONFUSIONE (CONFUSION MATRIX)

Matrice di elementi a[x][y] #istanze appartenentialla classe x (da Rreal), classificate come y.

N possibili classi da riconoscere: C1, C2, … CN

C1 C2 … CN

C1

C2

…

CN

Classificazioni prodotte dal modello

Cla

ssifi

cazi

on

i re

ali Casi in cui

la classificazio

nedel modellocoincide con quella reale

…CLASSIFICAZIONICORRETTE!


ACCURATEZZA DEL MODELLO

Rapporto delle istanze classificate correttamentesul numero totale di istanze di testing considerate.

C1 C2 … CN

C1 Corrette

C2 Corrette

… Corrette

CN Corrette


Cla

ssifi

cazi

on

i re

ali

Riferendosi alla confusion matrix


Esempio. Determinare se un certo cliente puo’ essere interessato o meno ad acquistare un auto berlina, ai fini di migliorare la campagna pubblicitaria.

SI NO

SI 50 75

NO 100 25


Cla

ssifi

cazi

on

i re

ali

FALSI NEGATIVI

FALSI POSITIVI

ACCURACY=(50+25)/(50+75+100+25)=

0.375




DATAUNDERSTANDING

DATAPREPARATION

MODELINGEVALUATION

DEPLOYMENT DB DW


La fase di deployment prevede l’effettivo utilizzo del modello di data mining all’interno di un processo strategico/decisionale.

Esistono molti tool in commercio che facilitano le operazioni del processo di data-mining: Pulizia dei dati Implementazione del modello Valutazione del modello

WEKA tool: http://www.cs.waikato.ac.nz/ml/weka/

Corso di Basi di Dati Introduzione al Data Mining Home page del corso: difelice/dbsi

Documents

Transcript of Corso di Basi di Dati Introduzione al Data Mining Home page del corso: difelice/dbsi