Corso di Basi di Dati Introduzione al Data Mining Home 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 … Introduzione al Data Mining ESEMPI di APPLICAZIONI (aziendali) 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 … Introduzione al Data Mining 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 … Introduzione al Data Mining 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/ Introduzione al Data Mining 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 Introduzione al Data Mining 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 Introduzione al Data Mining Q. Dove memorizzare i dati necessari per l’analisi? REPORT ANALISI Un data warehouse e’ una collezione di dati (non volatile) finalizzata al supporto del processo decisionale. Introduzione al Data Mining 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! Introduzione al Data Mining 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. Introduzione al Data Mining Differenze principali tra database operazionali (visti fin qui) e data warehouse. 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. Introduzione al Data Mining Differenze principali tra database operazionali (visti fin qui) e data warehouse. 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). Introduzione al Data Mining Esistono opportune metodologie (che non vedremo) per progettare un data warehouse relazionale. MODELLO A STELLA MODELLO OLAP Noi ci concentriamo ora sul processo di analisi dei dati … Introduzione al Data Mining 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. Introduzione al Data Mining ESEMPIO di PROCESSO di DATA-MINING 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? Introduzione al Data Mining CRISP-DM (Cross Industry Data Process for Data Mining) metodologia standard e generale per l’implementazione di un processo di data mining. BUSINESS UNDERSTANDING DEPLOYMENT EVALUATION DATA UNDERSTANDING DB DW DATA PREPARATION MODELING Introduzione al Data Mining CRISP-DM (Cross Industry Data Process for Data Mining) metodologia standard e generale per l’implementazione di un processo di data mining. BUSINESS UNDERSTANDING DEPLOYMENT EVALUATION DATA UNDERSTANDING DB DW DATA PREPARATION MODELING Introduzione al Data Mining BUSINESS UNDERSTANDING 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. Introduzione al Data Mining ESEMPIO di PROCESSO di DATA-MINING 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? … Introduzione al Data Mining CRISP-DM (Cross Industry Data Process for Data Mining) metodologia standard e generale per l’implementazione di un processo di data mining. BUSINESS UNDERSTANDING DEPLOYMENT EVALUATION DATA UNDERSTANDING DB DW DATA PREPARATION MODELING Introduzione al Data Mining DATA UNDERSTANDING 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. Introduzione al Data Mining ESEMPIO di PROCESSO di DATA-MINING 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)? … Introduzione al Data Mining CRISP-DM (Cross Industry Data Process for Data Mining) metodologia standard e generale per l’implementazione di un processo di data mining. BUSINESS UNDERSTANDING DEPLOYMENT EVALUATION DATA UNDERSTANDING DB DW DATA PREPARATION MODELING Introduzione al Data Mining DATA PREPARATION 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”. Introduzione al Data Mining DATA PREPARATION STORICO EROGAZIONI Costruire un modello di data-mining per decidere l’erogazione di una carta di credito sulla base della segmentazione degli utenti. Codice Macchina Eta Casa Reddito Erogazione 1332 SI 26 SI 10500 SI 2232 NO 40 SI 20000 SI 4323 NO 60 NO 5000 NO Se Reddito <= 10000 0 Se Reddito> 10000 & Reddito < 15000 1 Se Reddito >= 15000 2 REGOLE di CLASSIFICAZIONE Reddito 1 2 0 Introduzione al Data Mining DATA PREPARATION Molti algoritmi di data-mining lavorano su dati normalizzati su un intervallo (es. [0,1]). Normalizzazione Massimo/Minimo: Vali - Min(Val) ValNewi = Max(Val) - Min(Val) ValMax ValMin 0 1 15 0 20 0.11 40 0.55 60 1 Introduzione al Data Mining DATA PREPARATION Molti algoritmi di data-mining lavorano su dati normalizzati in base alla media dei valori. Normalizzazione con Deviazione Standard: Vali - Media(Val) ValNewi = Std(Val) Media 0 15 0 20 0.11 40 0.55 60 1 Introduzione al Data Mining DATA PREPARATION In molti data-set, possono essere presenti dati anomali (out-lier) che possono alterare l’analisi. Dati anomali … 1) Come identificarli? 2) Come gestirli? 1-Rischio 1 0 Reddito 1 In molti casi, l’obiettivo del processo di data mining consiste nella ricerca degli outlier (es. analisi frodi)! Introduzione al Data Mining DATA PREPARATION In molti data-set, possono essere presenti dati anomali (outlier) che possono alterare l’analisi. Dati anomali … 1) Come identificarli? 1-Rischio 1 0 Es. Range valori consentiti: [Media – Y*Dev: Media+Y*Dev] Reddito 1 Se X fuori dal range OUTLIER! Introduzione al Data Mining DATA PREPARATION 1 Dati anomali … 1) Come identificarli? 1-Rischio In molti data-set, possono essere presenti dati anomali (outlier) che possono alterare l’analisi. Es. : Metodo dei vicini X(x1,y1) e Y (x2,y2) sono vicini se: (x1 - x2 )2 + (y1 - y2 )2 < R 0 Reddito 1 Se #Vicini(X) < Soglia OUTLIER! Introduzione al Data Mining DATA PREPARATION In molti data-set, possono essere presenti dati anomali (outlier) che possono alterare l’analisi. Dati anomali … 1) Come identificarli? 2) Come gestirli? 1-Rischio 1 0 Reddito 1 Rimovere gli outlier Sostituirli con valori NULL Sostituirli con Media(Val) … Introduzione al Data Mining DATA PREPARATION In molti data-set, possono essere presenti dati incompleti che possono condizionare l’analisi. STORICO EROGAZIONI Codice Macchina Eta Casa Reddito Erogazione 1332 SI ??? SI 10500 SI 2232 NO 40 ??? 20000 SI 4323 ??? 60 NO ??? NO Q. Come gestire i record con informazioni incomplete? Introduzione al Data Mining DATA PREPARATION In molti data-set, possono essere presenti dati Diverse possibilita’: incompleti che possono condizionare l’analisi. Scartare record incompleti Rimpiazzare ??? con valori NULL STORICO EROGAZIONI Rimpiazzare ??? con il valore medio dell’attributo Codice Macchina??? Con Eta un valore Casa Reddito Erogazione Rimpiazzare che non alteri la deviazione 1332 Standard SI dei valori ??? dell’attributo SI 10500 SI ??? Con dell’attributo 2232 Rimpiazzare NO 40 valori “plausibili” ??? 20000 SI sulla base di valori simili. 4323 ??? 60 NO ??? NO … Q. Come gestire i record con informazioni incomplete? Introduzione al Data Mining DATA PREPARATION In molti contesti e’ opportuno ridurre il numero di attributi del data-set da analizzare … Ragioni di efficienza + Attributi: > Maggior tempo di computazione Ragioni di accuratezza Alcuni attributi non sono utili per l’analisi STORICO EROGAZIONI Informazione non utile per il modello … Codice CF Macchina Eta Casa Reddito Erogazione 1332 ADFDS802 M SI 26 SI 10500 SI 2232 FSFSS102M NO 40 SI 20000 SI 4323 MRGTY43R NO 60 NO 5000 NO Introduzione al Data Mining DATA PREPARATION In molti contesti e’ opportuno ridurre il numero di attributi del data-set da analizzare … Ragioni di efficienza + Attributi: > Maggior tempo di computazione Ragioni di accuratezza Alcuni attributi non sono utili per l’analisi STORICO EROGAZIONI Informazione non utile per il modello … Codice CF Macchina Eta Casa Reddito Erogazione 1332 ADFDS802 M SI 26 SI 10500 SI 2232 FSFSS102M NO 40 SI 20000 SI 4323 MRGTY43R NO 60 NO 5000 NO Introduzione al Data Mining DATA PREPARATION L’attivita’ di data preparation e’ molto delicata, le scelte effettuate possono condizionare l’analisi … 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 … Introduzione al Data Mining DATA PREPARATION L’attivita’ di data preparation e’ molto delicata, le scelte effettuate possono condizionare l’analisi … Valore medio Reddito: 15250 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 … Introduzione al Data Mining DATA PREPARATION L’attivita’ di data preparation e’ molto delicata, le scelte effettuate possono condizionare l’analisi … Valore medio Reddito: 176833 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 … Introduzione al Data Mining CRISP-DM (Cross Industry Data Process for Data Mining) metodologia standard e generale per l’implementazione di un processo di data mining. BUSINESS UNDERSTANDING DEPLOYMENT EVALUATION DATA UNDERSTANDING DB DW DATA PREPARATION MODELING Introduzione al Data Mining Algoritmi diversi, per risolvere problemi diversi: Classificazione Determinare se gli attributi di una certa istanza appartengono o meno ad una classe. Predizione Predire 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. Introduzione al Data Mining Algoritmi diversi, per risolvere problemi diversi: Classificazione Determinare se gli attributi di una certa istanza appartengono o meno ad una classe. Predizione Predire 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. Introduzione al Data Mining Algoritmi diversi, per risolvere problemi diversi: Classificazione Determinare se gli attributi di una certa istanza appartengono o meno ad una classe. Predizione Predire 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. Introduzione al Data Mining INPUT 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} OUTPUT Determinare la classe cj cui appartiene l’istanza A. COME? Mediante apprendimento supervisionato … Introduzione al Data Mining TRAINING-SET 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 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. Introduzione al Data Mining TRAINING-SET 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 Fase di TESTING {<Aj,cij>} DATA-SET Fase di TRAINING + ALGORITMO CLASSIFICAZIONE Istanza Ai MODELLO Cj Introduzione al Data Mining Esempio. Determinare se un certo cliente puo’ essere interessato o meno ad acquistare un auto berlina, ai fini di migliorare la campagna pubblicitaria. Data-set derivato dai risultati di precedenti campagne pubblicitarie TRAINING SET Nr Utente Stato Coniugale Sesso #Nucleo Familiare Reddito Annuo Acquisto 1 Celibe M 1 30000 SI 2 Nubile F 1 45000 NO 3 Sposato M 4 35000 SI TESTING SET <4, Sposato, M, 3, 38000> ACQUISTO?? Introduzione al Data Mining ALGORITMI di CLASSIFICAZIONE Naïve Bayes Reti Bayesiane Alberi di decisione Random Forest Support Vector Machines (SVM) … A. Quale algoritmo usare? Q. Non esiste un classificatore ottimo in assoluto, dipende dallo scenario applicativo … Introduzione al Data Mining CLASSIFICATORE NAÏVE BAYES (NB) 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. Istanza A(x1, …xN) da classificare. P(cj|A) probabilita’ condizionata di avere una classe cj,vendendo un’istanza A. In NB, scelgo la classe ck, tale che: Come calcolare P(cj|A)?? k = argmax j P(c j | A) Introduzione al Data Mining Probabilita’ condizionata: P(E1 | E2 ) = P(E1, E2 ) P(E2 ) Probabilita’ congiunta (in caso di eventi indipendenti): P(E1, E2 ) = P(E1 )× P(E2 ) Teorema di Bayes: P(E2 | E1 )× P(E1 ) P(E1 | E2 ) = P(E2 ) Applicando il Teorema di Bayes al nostro problema: argmax j P(c j | A) = argmax j P(A | c j )× P(c j ) P(A) Introduzione al Data Mining Semplificando il problema … argmax j P(A | c j )× P(c j ) P(A) argmax j P(A | c j )× P(c j ) Il record A e’ composto di N Attributi: A(x1,x2, …xN) argmax j P(A | c j )× P(c j ) = argmax j P(x1, x2,..., xN | c j )× P(c j ) Assumendo che gli N attributi siano tutti indipendenti … N argmax j P(x1, x2 ,..., x N | c j )× P(c j ) = argmax j P(c j )× Õ P(xi | c j ) i=1 Introduzione al Data Mining Conclusione L’algoritmo di NB sceglie la classe cj che massimizza la quantita’: N P(c j )× Õ P(xi | c j ) i=1 PROBLEMA: Come stimare P(cj) e P(xi|cj)? Possibile Soluzione: Approssimo le probabilita’ come frequenze relative, rispetto ai valori del mio training set. P(c j ) = # is tan ze classificate c j # is tan ze totali Introduzione al Data Mining Reddito <30000 0, Reddito >=30000 1 Nr Utente Sposato Sesso #Nucleo Familiare Reddito Annuo 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 A=<4, Sposato, M, 3, 38000> C(SI)=2/6=0.33 C={SI, NO} C(NO)=4/6=0.67 Introduzione al Data Mining Reddito <30000 0, Reddito >=30000 1 Nr Utente Sposato Sesso #Nucleo Familiare Reddito Annuo 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 A=<4, Sposato, M, 3, 38000> C(4|SI)=1/2=0.5 C(4|NO)=1/4=0.25 Introduzione al Data Mining A=<4, Sposato, M, 3, 38000> Reddito <30000 0, Reddito >=30000 1 Nr Utente Sposato Sesso #Nucleo Familiare Reddito Annuo 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(Sposato|SI)=2/2=1 C(Sposato|NO)=1/4=0.25 C(M|SI)=1/2=0.5 C(M|NO)=2/4=0.5 C(3|NO)=1/2=0.5 C(1|SI)=1/2=1 C(3|SI)=1/2=0.5 C(1|NO)=2/4=0.5 Introduzione al Data Mining A=<4, Sposato, M, 3, 38000> Reddito <30000 0, Reddito >=30000 1 Nr Utente Sposato Sesso #Nucleo Familiare Reddito Annuo 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 Introduzione al Data Mining A=<4, Sposato, M, 3, 38000> Nr Utente Sposato 1 NO #Nucleo Familiare Reddito Annuo Acquisto M 4 0 NO 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 2 Sesso Reddito <30000 0, Reddito >=30000 1 Classificata come 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 Introduzione al Data Mining Una rete bayesiana e’ un modello (visuale) per rappresentare le interazioni e le dipendenze tra variabili casuali (random variable). DAG Ogni nodo e’ una variabile casuale. Grafo Diretto Aciclico A 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. B C D Introduzione al Data Mining Una rete bayesiana e’ un modello (visuale) per rappresentare le interazioni e le dipendenze tra variabili casuali (random variable). 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 DAG Grafo Diretto Aciclico A B C D Introduzione al Data Mining Una rete bayesiana e’ un modello (visuale) per rappresentare le interazioni e le dipendenze tra variabili casuali (random variable). Ogni nodo Xi dispone di una distribuzione di probabilita’ P(Xi | Parents(Xi)) che quantifica gli effetti dei nodi padre sui figli. A B P(B|A) false false 0.01 false true 0.99 true false 0.7 true true 0.3 DAG Grafo Diretto Aciclico A B C D Introduzione al Data Mining Una rete bayesiana e’ un modello (visuale) per rappresentare le interazioni e le dipendenze tra variabili casuali (random variable). Ogni nodo Xi dispone di una distribuzione di probabilita’ P(Xi | Parents(Xi)) che quantifica gli effetti dei nodi padre sui figli. B C P(C|B) B D P(D|B) false false 0.4 false false 0.02 false true 0.6 false true 0.98 true false 0.9 true false 0.05 true true 0.1 true true 0.95 DAG Grafo Diretto Aciclico A B C D Introduzione al Data Mining 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 P(I=true)=0.2 P(I=false)=0.8 Pioggia Erba Bagnata 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 Introduzione al Data Mining Irrigazione ON P(I=true)=0.2 P(I=false)=0.8 Pioggia Erba Bagnata 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 P(E = true | R = true)× P(R = true) P(R = true | E = true) = = P(E = true) = P(E = true | R = true)× P(R = true) P(E = true | R = true)× P(R = true) + P(E = true | R = false)× P(R = false) Introduzione al Data Mining P(R = true | E = true) = Irrigazione ON P(I=true)=0.2 P(I=false)=0.8 0.95× 0.4 = 0.75 0.95× 0.4 + 0.2 × 0.6 Pioggia Erba Bagnata P(R=true)=0.4 P(R=false)=0.6 P(E|I=true, R=true)=0.95 P(E|I=true, R=false)=0.90 P(E|I=false, R=true)=0.90 P(E|I=false, R=false)=0.10 P(E = true | R = true)× P(R = true) P(R = true | E = true) = = P(E = true) = P(E = true | R = true)× P(R = true) P(E = true | R = true)× P(R = true) + P(E = true | R = false)× P(R = false) Introduzione al Data Mining 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: k = argmax j P(C j | A) = arg max j P(C j , A) P(A) Introduzione al Data Mining Un esempio di classificatore basato su reti Bayesiane. C={Spam, No Spam} 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? Spam Email A1 A2 Introduzione al Data Mining Un esempio di classificatore basato su reti Bayesiane. C={Spam, No Spam} 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 Spam Email … A1 P(A2=true|A1=true, C=Spam)=0.95 …. A2 Introduzione al Data Mining Un esempio di classificatore basato su reti Bayesiane. Supponendo di dover classificare A(true, false): P(C = Spam, A1 = true, A2 = false) P(C = NoSpam, A1 = true, A2 = 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? Introduzione al Data Mining Un esempio di classificatore basato su reti Bayesiane. Supponendo di dover classificare A(true, false): P(C = Spam, A1 = true, A2 = false) P(C = NoSpam, A1 = true, A2 = false) In una rete bayesiana con variabili casuali X1, X2, … XN, vale il seguente risultato: d P(X1, X2 ,...X N ) = Õ P(Xi | parents(Xi )) i=1 Introduzione al Data Mining Un esempio di classificatore basato su reti Bayesiane. Supponendo di dover classificare A(true, false): P(C = Spam, A1 = true, A2 = false) P(C = NoSpam, A1 = true, A2 = false) P(C = Spam)× P(A1 = true | C = Spam)× P(A2 = true | A1 = true,C = Spam) (C = NoSpam)× P(A1 = true | C = NoSpam)× P(A2 = true | A1 = true,C = NoSpam Introduzione al Data Mining Algoritmi diversi, per risolvere problemi diversi: Classificazione Determinare se gli attributi di una certa istanza appartengono o meno ad una classe. Predizione Predire 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. Introduzione al Data Mining Le regole associative rappresentano uno strumento per scoprire relazioni (possibilmente non banali) tra gli elementi di una base di dati. INPUT Insieme di M elementi A={a1,…aM} Ogni elemento e’ composto da N attributi OUTPUT Determinare regole della forma Se X allora Y Introduzione al Data Mining 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 1 ESEMPIO DI REGOLE Pasta Olio Pane, Burro Marmellata Pane Olio, Burro Introduzione al Data Mining 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 1 ItemSet Combinazione di valori degli attributi dello schema Supporto(ItemSet) # is tan ze _ di _ I s(I ) = # totale _ is tan ze Introduzione al Data Mining 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 1 Supporto{Pane}=2/4=0.5 Supporto{Pane,Pasta}=0/4=0 Supporto{Pane,Burro,Marmellata}=2/4=0.5 Introduzione al Data Mining 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 1 Data una regola associativa: XY Supporto della regola XY s(X- > Y ) = S(X,Y ) S(X) Introduzione al Data Mining 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 1 s(Pasta Olio) = 2/3=0.66 s(Pane Burro) = 1/3=0.33 s(Pane Burro Marmellata) = 2/3=0.66 Introduzione al Data Mining 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 Introduzione al Data Mining 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 PROBLEMA: Costo computazionale dell’algoritmo? Introduzione al Data Mining 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. Introduzione al Data Mining ESEMPIO di FUNZIONAMENTO ALGORITMO APRIORI 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 Introduzione al Data Mining ALGORITMO APRIORI ItemSet FREQUENZA ITEMSET (1 attributo) # 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 con cardinalita’ < cmin Introduzione al Data Mining 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 Introduzione al Data Mining ALGORITMO APRIORI FREQUENZA ITEMSET (3 attributi) 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. Introduzione al Data Mining ALGORITMO APRIORI FREQUENZA ITEMSET (3 attributi) ItemSet # Oggetti Promozione orologi=NO & Promozione Assicurazione Vita=NO & Assicurazione carta credito=NO 4 POSSIBILI REGOLE (3 attributi): 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) Introduzione al Data Mining ALGORITMO APRIORI FREQUENZA ITEMSET (3 attributi) ItemSet # Oggetti Promozione orologi=NO & Promozione Assicurazione Vita=NO & Assicurazione carta credito=NO POSSIBILI REGOLE (3 attributi): 4 s(X->Y)=4/4=1 SE (Promozione orologi=NO & Promozione Assicurazione Vita=NO) ALLORA Assicurazione carta credito=NO s(X->Y)=4/6=0.6 SE (Promozione orologi=NO) ALLORA (Promozione Assicurazione Vita=NO) & (Assicurazione carta credito=NO) s(X->Y)=4/5=0.8 SE (Promozione Assicurazione Vita=NO) & (Assicurazione carta credito=NO) ALLORA (Promozione orologi=NO) Introduzione al Data Mining ALGORITMO APRIORI FREQUENZA ITEMSET (3 attributi) ItemSet # Oggetti Promozione orologi=NO & Promozione Assicurazione Vita=NO & Assicurazione carta credito=NO 4 Definisco una soglia minima smin=0.75 s(X->Y)=4/4=1 SE (Promozione orologi=NO & Promozione Assicurazione Vita=NO) ALLORA Assicurazione carta credito=NO s(X->Y)=4/5=0.8 SE (Promozione Assicurazione Vita=NO) & (Assicurazione carta credito=NO) ALLORA (Promozione orologi=NO) Introduzione al Data Mining ALGORITMO APRIORI FREQUENZA ITEMSET (3 attributi) ItemSet # Oggetti Promozione giornali=SI & Promozione Orologi =NO 7 …. … FASI SUCCESSIVE DELL’ALGORITMO 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. Introduzione al Data Mining Algoritmi diversi, per risolvere problemi diversi: Classificazione Determinare se gli attributi di una certa istanza appartengono o meno ad una classe. Predizione Predire 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. Introduzione al Data Mining La cluster/segmentation analysis e’ un insieme di tecniche per raggruppare oggetti in classi tra loro omogenee, ossia con caratteristiche simili. INPUT Insieme di N elementi da partizionare Numero di Classi: NC OUTPUT Determinare la composizione di ogni classe c0<=i<nc Introduzione al Data Mining POSSIBILI APPLICAZIONI Ricerche di mercato Segmentazione della clientela Analisi dei social media Identificazione degli outlier … 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? Introduzione al Data Mining ALGORITMO DELLE K-MEDIE (K-MEANS CLUSTERING) 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 Introduzione al Data Mining Distanza tra due elementi in uno spazio euclideo 2D d(x, y) = (x1 - y1 )2 + (x2 - y2 )2 Distanza tra due elementi in uno spazio euclideo ND d(x, y) = n å (xi - yi )2 i=1 Centroide di un gruppo (2D): c(a1,a2, … aM) M æM ö ç å ai,x å ai,y ÷ ÷ c ç i=1 , i=1 ç M M ÷ ç ÷ è ø Introduzione al Data Mining 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 j 2.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). Introduzione al Data Mining 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. M e = å d(ai , c(ai ))2 i=1 La classificazione termina quando l’errore diventa minore di una soglia Emin (e<Emin). Introduzione al Data Mining 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 Eta 30 * 20 * ** * * * * * * = ax,y 10 5 10 15 20 25 30 35 40 Stipendio x 10000 Introduzione al Data Mining 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 Eta 30 * 20 * ** * * * * * Creazione casuale dei cluster * = ax,y 10 5 10 15 20 25 30 35 40 Stipendio x 10000 Introduzione al Data Mining 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 Eta 30 *+* 20 + * ** * *+* * Loop: Calcolo centroidi * = ax,y 10 5 10 15 20 25 30 35 40 Stipendio x 10000 Introduzione al Data Mining 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 Eta 30 *+* 20 + * ** * *+* * Loop: Calcolo distanze * = ax,y 10 5 10 15 20 25 30 35 40 Stipendio x 10000 Introduzione al Data Mining 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 Eta 30 * 20 * ** * * * * * Loop: Riassegnamento * = ax,y 10 5 10 15 20 25 30 35 40 Stipendio x 10000 Introduzione al Data Mining 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 Eta 30 * 20 * ** * * * * * CONVERGENZA? Non ancora … 10 5 10 15 20 25 30 35 40 Loop: Valuto condizione * = ax,y Stipendio x 10000 Introduzione al Data Mining 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 Eta 30 * 20 * ** * * * * * RISULTATO FINALE * = ax,y 10 5 10 15 20 25 30 35 40 Stipendio x 10000 Introduzione al Data Mining 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 Introduzione al Data Mining CRISP-DM (Cross Industry Data Process for Data Mining) metodologia standard e generale per l’implementazione di un processo di data mining. BUSINESS UNDERSTANDING DEPLOYMENT EVALUATION DATA UNDERSTANDING DB DW DATA PREPARATION MODELING Introduzione al Data Mining La fase di valutazione del modello e’ necessaria per quantificarne 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. Introduzione al Data Mining 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. Introduzione al Data Mining MATRICE di CONFUSIONE (CONFUSION MATRIX) Matrice di elementi a[x][y] #istanze appartenenti alla classe x (da Rreal), classificate come y. Classificazioni reali N possibili classi da riconoscere: C1, C2, … CN Classificazioni prodotte dal modello C1 C2 … C1 C2 CN Casi in cui la classificazione del modello coincide con quella reale … … CN CLASSIFICAZIONI CORRETTE! Introduzione al Data Mining ACCURATEZZA DEL MODELLO Classificazioni reali Rapporto delle istanze classificate correttamente sul numero totale di istanze di testing considerate. Classificazioni prodotte dal modello C1 C2 … C1 C2 CN Corrette Corrette … CN Riferendosi alla confusion matrix Corrette N Corrette accuracy = å a[i][i] i=1 # is tan ze Introduzione al Data Mining Classificazioni reali Esempio. Determinare se un certo cliente puo’ essere interessato o meno ad acquistare un auto berlina, ai fini di migliorare la campagna pubblicitaria. Classificazioni prodotte dal modello SI NO SI 50 75 NO 100 25 FALSI POSITIVI FALSI NEGATIVI ACCURACY= (50+25)/(50+75+100+25)= 0.375 Introduzione al Data Mining CRISP-DM (Cross Industry Data Process for Data Mining) metodologia standard e generale per l’implementazione di un processo di data mining. BUSINESS UNDERSTANDING DEPLOYMENT EVALUATION DATA UNDERSTANDING DB DW DATA PREPARATION MODELING Introduzione al Data Mining 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/