Fondamenti di Data Warehousing e Data...
Transcript of Fondamenti di Data Warehousing e Data...
Fondamenti di Fondamenti di Data Warehousing Data Warehousing e Data Mininge Data Mining
Luigi PontieriLuigi Pontieri
ICARICAR--CNRCNR
SommarioSommario
IntroduzioneMotivazioni, contesto e aree applicative
Data WarehousingArchitettura di un Data WarehouseParadigma multi-dimensionaleSistemi OLAP: aspetti tecnici
Data MiningData Mining e processo di KDD Task/Funzionalità di Data Mining
Cenni su tecniche e algoritmi
Problematiche e linee di sviluppo
Contesto e motivazioniContesto e motivazioni
“data explosion”La disponibilità di tecnologie efficienti e poco costose favorisce l’accumulo di enormi quantità di dati
DBs e altri tipi di repositoryElectronic data gathering: Internet, Satellite, Bar-code reader, …High perf. computers (PC-Cluster) e, in generale, cheaper & faster HW
Motivazioni:opportunità di trarre vantaggio competitivo dai dati
supportando i processi decisionali con nuova conoscenza
inadeguatezza dei sistemi di analisi tradizionali:“We are drowning in data, but starving for knowledge!”
AnalisiAnalisi e e estrazioneestrazione didi conoscenzaconoscenza::Data Warehouse e Data Mining Data Warehouse e Data Mining
Data Warehouse (DW)Archivio progettato in modo specifico per l’analisiDotato di strumenti efficienti e intuitivi per consultare, interrogare e visualizzare le informazioniData Warehousing: processo di costruzione/popolamento di un DW
Data Mining (DM) Estrazione automatica ed efficiente di pattern (“pepite” di conoscenza) da grosse collezioni di datiPattern: regolarità o proprietà valide nei dati di input
Data Mining: un approccio induttivo di Data Mining: un approccio induttivo di analisianalisi
Tecniche deduttive (“VerificationVerification--DrivenDriven”)TopTop--DownDown: : analisi “passivapassiva”, atta a verificare se un certo modello (ipotesi) è coerente con i dati a disposizioneL’ipotesi o il modello sono formulati dall’utente sulla base della sua esperienzaStrumenti: verifica di ipotesi (statistica), query language
Tecniche induttive (“DiscoveryDiscovery--DrivenDriven”)BottomBottom--UpUp: : analisi “attivaattiva”, in cui i dati stessi suggeriscono possibili ipotesi sul significato del loro contenutoIndividuazione di fatti, relazioni, tendenze, pattern, associazioni, eccezioni e anomalie, che sfuggono all’analisi manuale
Principali aree di applicazionePrincipali aree di applicazione
Marketing: product targeting, cross selling, segmentazione della clientela, CRM e Customer Retention, ...
Finanze: supporto a investmenti, gestione portafoglio, scoperta frodi
Banche/Assicurazioni: apertura di prestiti / polizze assicurative
Sicurezza: scoperta di intrusioni, controllo degli accessi
Scienze: progettazione di farmaci, studio di fattori genetici, scoperta di galassie e astri
Medicina: supporto a diagnosi e prognosi, valutazione cure, scoperta di relazioni fra malattie
Produzione: modellazione dei process, controllo di qualità, allocazione delle risorse
Internet: smart search engines, web marketing, web site design
Un poUn po’’ di storiadi storia
Data collectionData collection (1960’s, e prima):
- primitive file processing
Database management systems (1970’s): - network and relational database systems- data modeling tools, query languages- optimization methods
Advanced DB Systems Advanced DB Systems (1980’s - …):- nuovi tipi di dati e data model avanzati
- dati semi-strutturati, testuali, multimediali- extended-relational, OO, deductive,
- application-oriented DBMS (GIS, scientific, engineering, …)
- apertura verso le reti e il Web
Data Warehouse & Data Mining (1990’s -…)
- “data mining” usato dal 1983, con accezionenegativa, nella comunità statistica
- KDD workshop iniziato nel 1989
- “Padri fondatori”: Fayyad, Piatetsky-Shapiro, Agrawal
New-generation Intelligent Information Systems
Data WarehousingData Warehousing
IntroduzioneMotivazioni, contesto e aree applicative
Data WarehousingArchitettura di un Data WarehouseParadigma multi-dimensionaleSistemi OLAP: aspetti tecnici
Data MiningData Mining e processo di KDD Task/Funzionalità di Data Mining
Cenni su tecniche e algoritmi
Problematiche e linee di sviluppo
Il Data WarehousingIl Data Warehousing
Applicazione AApplicazione A
Applicazione BApplicazione B
Applicazione CApplicazione C
QueryQuery
ReportReport
AnalisiAnalisi
NavigazioneNavigazione
Data MiningData Mining
Ambiente OperativoAmbiente Operativo Ambiente DecisionaleAmbiente Decisionale
On-Line Transactional Processing(OLTP)
On-Line Analytical Processing (OLAP)
Idea di fondo: esigenze molto diverse per i due ambientiSeparazione permette di migliorare le prestazioni di entrambi:
Sistemi operazionali ottimizzati per operazioni OLTPData Warehouse ottimizzato per operazioni OLAP
OLTP vs. OLAPOLTP vs. OLAP
OLTP OLAPfunzione gestione
giornalierasupporto alle decisioni
progettazione orientata alle applicazioni
orientata al soggetto
frequenza gironaliera sporadicadati recenti, dettagliati storici, riassuntivi,
multidimensionalisorgente singola DB DB multipleuso ripetitivo ad hocaccesso read/write readflessibilità accesso uso di programmi
precompilati generatori di query
# record acceduti decine migliaiatipo utenti operatori manager# utenti migliaia centinaiatipo DB singola multiple, eterogeneeperformance alta bassadimensione DB 100 MB - GB 100 GB - TB
Data WarehouseData Warehouse
Gestisce dati utili per il supporto alle decisioni:orientati ai soggetti: non alle applicazioni
enfasi sui fatti (es.: vendite, forniture)
integrati: a livello aziendale e non dipartimentalerappresenta i dati in modo univoco, riconciliando le eterogeneitàdelle diverse rappresentazioni
temporali: ampio orizzonte temporale (anni) rappresentazione esplicita della dimensione tempo
aggregati: non interessa “chi” ma “quanti”somma, media, minimo, massimo su insiemi di valori
fuori linea: aggiornati periodicamenteoperazioni di accesso e interrogazione diurneoperazioni di caricamento e aggiornamento notturne
Architettura di base del DWArchitettura di base del DW
acquisizione memorizzazione accesso
dw
Back-end Front-endSorgenti
Operazioni di BackOperazioni di Back--EndEnd
ETL = Extract-Transform-Load
Estrazione dei dati rilevanti da sorgenti esterne
Rilevamento e correzione errori (Cleaning) nei dati
Conversione dei dati dal formato delle sorgenti a quello del DW
Integrazione: merging dei dati e gestione di eventuali conflitti
Popolamento del DWcalcolo di viste aggregate e indici
Monitoring:rileva le modifiche rilevanti nelle sorgenti e le propaga nel DW
Operazioni di FrontOperazioni di Front--EndEnd
InterrogazioneUso di un query-language tradizionale o del Paradigma Multidimensionale (Server OLAP)
Reportingtabelle, diagrammi, grafici
Analisi statistica di baseDistribuzione di un attributo, correlazione fra attributi
Data Miningestrazione di pattern “nascosti”
Visualizzazionedatipattern estratti
Architettura di un Data WarehouseArchitettura di un Data Warehouse
Enterprise Data Warehouse
(BDW)EstrazioneCleaningTrasformazioneCaricamentoRefresh
Accesso
Data Mart (BIW)ServerOLAP
Back-endFront-end
Data Warehouse (memorizzazione)
metadati
Sorgenti
USO Bimodale:•16-22 ore al giorno per operazioni di front-end •2-8 ore al giorno per operazioni di back-end
Componenti del Data WarehouseComponenti del Data Warehouse
Sistemi sorgente (sorgenti)vari archivi informativi dell’organizzazioneper lo più sistemi OLTP di supporto a processi operazionali, con dati real-time e transazioni R/W predefinite e “semplici”
Data mart (o BIW)dati derivati dalle sorgenti ed usati per il supporto alle decisioniun DW contiene spesso più data mart, di cui ognuno consiste di dati ed applicazioni mirate a specifiche analisi (es. Marketing)
Enterprise Data Warehouse (o BDW)garantisce una visione univoca, e piuttosto dettagliata, delle informazioni presenti nell’organizzazionedati riconciliati, ottenuti periodicamente dai dati delle sorgenti, mediante integrazione, storicizzazione e consolidamentofunge da unico punto di controllo e da unica sorgente dati per tutte le applicazioni decisionali fornite agli utenti finali
Informazioni in un DWInformazioni in un DW
Business datai dati da analizzare (il “patrimonio informativo”)real-time, riconciliati, derivati
Metadati = “dati sui dati”descrivono modalità, tempi e funzioni secondo cui i dati sono creati, controllati ed utilizzati nel DWmetadati di uso dei dati
migliorano il livello di comprensione dell’utente e la sua capacità di contestualizzazione dei datiEs.: catalogo dei dati, modellazione concettuale dei dati, informazioni sulle sorgenti,..
metadati di controllousati per controllare il funzionamento del DWEs.: tempi di “snapshotting”, livelli di aggregazione, “aging” dei dati e sicurezza
Dati multidimensionaliDati multidimensionali
E’ il paradigma di interrogazione più utilizzato per le analisi OLAPPermette di modellare ed interrogare i dati in base ai concetti:
fattorappresenta un un eventoè il concetto sul quale si centra l’analisi
misurauna proprietà atomica di un fatto da analizzarele misure sono solitamente valori numerici
dimensioneuna prospettiva rispetto alla quale effettuare l’analisile dimensioni descrivono domini discreti, solitamente organizzati in livelli di aggregazione
Dati multidimensionali: esempiDati multidimensionali: esempi
BIW delle venditefatto: vendite dei prodotti, giornaliere, per negozio
misure: quantità venduta, incasso, conteggio dei clienti
dimensioni: prodotto, giorno, negozio
BIW delle telefonatefatto: telefonata
misure: durata, costo
dimensioni: chiamante, chiamato, tariffa, ora del giorno
Rappresentazione dei dati:Rappresentazione dei dati:MultiMulti--Dimensionale vs. Dimensionale vs. TabellareTabellare
Prodotto
Anno
Zona
1999
2000
2001
2002
2003
Z1Z2
Z3Z4
18
17 15
10
16
12
P1 P2 P3 P415
12
15
15
34
23
25
Dimensioni Misura
Anno Prodotto Zona Vendita
1999 P1 Z1 18
1999 P2 Z2 15
2000 P1 Z2 12
2000 P3 Z1 16
2000 P1 Z4 15
2001 P1 Z2 15
2001 P3 Z3 34
2002 P1 Z1 17
2002 P2 Z1 15
2002 P2 Z3 25
2002 P3 Z2 12
2003 P2 Z1 10
2003 P4 Z2 23
Le dimensioni: gerarchieLe dimensioni: gerarchie
Di solito una singola dimensione contiene attributi organizzati gerarchicamente
Tempo:giornosettimanameseanno
Geografia:comuneprovinciaregionestato
Le gerarchie possono essere usate per raggruppare istanze, calcolando valori aggregati per le misure
Categoria Regione
Marca Provincia
Articolo Città
Magazzino
Anno
Settim. Mese
Giorno
Categoria Regione
Marca Provincia
Articolo Città
Magazzino
Categoria Regione
Marca Provincia
Articolo Città
Magazzino
Anno
Settim. Mese
Giorno
Anno
Settim. Mese
Giorno
AdditivitAdditivitàà delle misuredelle misure
Misure additive: si possono aggregare rispetto ad ogni dimensione utilizzando l’operazione di somma
Es: Incasso, unità vendute (su tempo, prodotti, dipartimenti)
Misure semi-additive: aggregabili solo su alcune dimensioniEs: Numero clienti
somma n° clienti su tempo (o dipartimenti): OKma “somma n° clienti su prodotto” genera problemi:
se 20 clienti che hanno comprato carne e 30 hanno comprato pesce, i clienti che hanno comprato carne o pesce potrebbero essere un qualunque numero tra 30 e 50
Misure non-additive: non possono essere sommate Es: costo unitario e quantità nel contesto di un ordine
i costi unitari non possono essere sommati se non sono moltiplicati per le rispettive quantità
Tipi di query OLAPTipi di query OLAP
Roll-up: aggrega i dati di un reportrimuove una dimensionediminuisce il livello di dettaglio su una dimensione
es: tempo da giorno a mese
Drill-down: inverso del roll-upaggiunge una dimensioneaumenta il livello di dettaglio su una dimensione
es: tempo da mese a giorno
Pivoting: riorienta il cubo scambia o modifica le dimensioni analizzate
drilldrill--downdown e e rollroll--upup: esempio: esempio
Dipartimento Incassi Unità vendute
Panificio Lit. 12100000 5088Cibo surgelato Lit. 23000000 15000…
down up
Dipartimento Marca Incassi Unità vendute
Panificio Barilla 6000000 2600Panificio Agnesi 6100000 2488Cibo surgelato Findus 15000000 6500Cibo surgelato Orogel 8000000 8500…
Tipi di query OLAPTipi di query OLAP
Slicingproduce “una fetta” dell’ipercuboconsiste in una selezione con un vincolo di uguaglianza
Dicingproduce un ipercubo cubo più piccolo estratto da quello corrente consiste in una selezione con uno o più vincoli di uguaglianza e di range combinati con OR e/o AND
Top-nricerca gli N fatti con i valori di misura maggiori (o minori)esempio: determinare i 10 prodotti più venduti ad una certa data e in un certo magazzino, ordinati per vendite
DatacubeDatacube e cuboidie cuboidi• Misure: somma quantità vendute• Dimensioni: Tempo, Prodotto, Località• Gerarchie:
Datacube:Totale delle Vendite perSettimana, Prodotto e Nazione
Categoria Regione
Marca Provincia
Articolo Città
Magazzino
Anno
Settim. Mese
Giorno
Categoria Regione
Marca Provincia
Articolo Città
Magazzino
Categoria Regione
Marca Provincia
Articolo Città
Magazzino
Anno
Settim. Mese
Giorno
Anno
Settim. Mese
Giorno
Totale delle vendite di Totale delle vendite di dischi in Lazio (per tutti i dischi in Lazio (per tutti i periodo)periodo)
Artico
lo (P
rodo
tto)
Artico
lo (P
rodo
tto)
Reg
ione
(L
ocal
ità)
Reg
ione
(L
ocal
ità)
1 2 … ALL
ALLLazioCalabriaPiemonteToscanaPuglia
ALLCD
dischi
Settimana (Tempo)Settimana (Tempo)
……………………………………
…………
Totale delle vendite di Totale delle vendite di dischi in Lazio (per tutti i dischi in Lazio (per tutti i periodo)periodo)
Artico
lo (P
rodo
tto)
Artico
lo (P
rodo
tto)
Reg
ione
(L
ocal
ità)
Reg
ione
(L
ocal
ità)
1 2 … ALL
ALLLazioCalabriaPiemonteToscanaPuglia
ALLCD
dischi
Settimana (Tempo)Settimana (Tempo)
……………………………………
…………
Lazio
Puglia
Cuboidi di un Cuboidi di un datacubedatacube
Un datacube può essere visto come una rete di cuboidi, corrispondenti a vari livelli di aggregazione
Il cuboide più in basso è detto “cuboide base” e corrisponde alle celle interne del datacubeIl cuboide (“cuboide apice”) contiene solo una cella
cuboidi 0-D (apice)
cuboidi 1-D
cuboidi 2-D
cuboidi 3-D (base)
all
articolo
mese, regione
mese regione
regione, articolomese, articolo
mese, regione, articolo
Strategie di memorizzazioneStrategie di memorizzazione
Multidimensional OLAP (MOLAP) Memorizzazione basata su array multidimensionali
tecniche ottimizzate per matrici sparse
Usa strutture di indicizzazione dedicate (veloci) e pre-calcolo di viste aggregateVantaggio: migliori prestazioni per le query utente
Relational OLAP (ROLAP) Usa tecniche basate sulla tecnologia dei RDBMSMaggiore flessibilità e facilità di uso/programmazione (e.g., join, API standad)Migliore scalabilità (o possibilità di rappresentare i dati con maggiore dettaglio)
Hybrid OLAP (HOLAP)Flessibilità per l’utenteEs: MOLAP per basso livello e ROLAP per alto livello
Modelli logici nei sistemi ROLAP: Modelli logici nei sistemi ROLAP: Star SchemaStar Schema
Modello a stellauna tabella per ogni fatto e una per ogni dimensione
“Specializzazione” del modello relazionale: la tabella dei fatti rappresenta una relazione molti-molti fra le dimensioni e contiene le misure (oltre alle chiavi delle tabelle delle dimensioni correlate)
Esempio: vendite dei prodotti, giornaliere, per negozio
Modello a fiocco di neve (Modello a fiocco di neve (snowflakesnowflake))Alcune gerarchie dimensionali sono decomposte in un insieme di tabelle dimensionali
una gerarchia implica molte relazioni molti-a-uno
aumenta il grado di normalizzazione, ma anche il tempo per l’esecuzione delle tipiche query di aggregazione
Impatto sul codice SQLImpatto sul codice SQL
Le tipiche query OLAP richiedono molte aggregazioni:fatti con k dimensioni2k query SQL aggregate
Estensione di SQL con nuovi operatori: CUBE, ROLL-UP
Estensioni di SQL: Estensioni di SQL: CUBE e ROLLCUBE e ROLL--UPUP
Operatore CUBEsintassi: SELECT …. GROUP BY CUBE (elenco colonne)calcola tutte le possibili aggregazioni (ogni cella del cubo)equivalente ad un insieme di query del tipo:
SELECT SUM (vendite)
FROM vendite S, GROUP BY grouping list
Operatore ROLL-UPsintassi: SELECT …. GROUP BY ROLLUP (elenco colonne)calcola l’aggregato standard rispetto all’elenco di colonnecalcola sub-totali di livello più alto, riducendo ad uno ad uno le colonne da aggregare, da destra a sinistra nella lista
operatore CUBE: esempiooperatore CUBE: esempio
SELECT città, mese, prodotto, SUM(vendite)
FROM Vendite v, Magazzini m, Tempo t, Prodotti p
WHERE m.Magazzino_k = v.Magazzino_k
AND p.Prodotto_k = v.Prodotto_k
AND t.Tempo_k = v.Tempo_k
GROUP BY CUBE (città,mese,prodotto)
operatore operatore RollRoll--upup: esempio: esempio
SELECT città, mese, prodotto, SUM(vendite)FROM Vendite v, Magazzini m,
Tempo t, Prodotti pWHERE m.Magazzino_k = v.Magazzino_k
AND p.Prodotto_k = v.Prodotto_k AND t.Tempo_k = v.Tempo_k
GROUP BY ROLLUP (città,mese,prodotto)
IndiciIndici susu datidati multidimensionalimultidimensionali
L’aggiornamento periodico del DW permette di usare indici piùpotenti e riorganizzarli in modo ottimo:
Bitmap indexJoin index
Gli indici si possono costruire su:Attributi non chiave delle dimension table
per accelerare le operazioni di selezioneChiavi importate della Fact Table
per accelerare l’esecuzione delle joinSi possono costruire su misure, della Fact Table, nel caso esistano selezioni su tali valori
Es: “vendite con quantitativi superiori a 1.000.”
IndiciIndici OLAP: Bitmap IndexOLAP: Bitmap Index
Indice definito su un attributo di una tabella (base)
Un indice Bitmap è composto da una matrice binariatante colonne quanti sono i possibili valori di un attributotante righe quante sono le tuple della relazionel’elemento (i,j) indica se la tupla i ha il valore j
Indice su Region Indice su TypeTabellaCust Region TypeC1 Asia RetailC2 Europe DealerC3 Asia DealerC4 America RetailC5 Europe Dealer
ID Asia Europe America1 1 0 02 0 1 03 1 0 04 0 0 15 0 1 0
ID Retail Dealer1 1 02 0 13 0 14 1 05 0 1
Data MiningData Mining
IntroduzioneMotivazioni, contesto e aree applicative
Data WarehousingArchitettura di un Data WarehouseParadigma multi-dimensionaleSistemi OLAP: aspetti tecnici
Data MiningData Mining e processo di KDD Task/Funzionalità di Data Mining
Cenni su tecniche e algoritmi
Problematiche e linee di sviluppo
Data MiningData Mining
Altri nomi:Data dredging, Data harvesting, Data archeology
Un settore interdisciplinare: Machine LearningStatistica Artificial IntelligenceInformation RetrievalDatabases e Data WarehousingData visualization
Tuttavia molta enfasi è posta su:Applicazione a varie tipologie di datiAlgoritmi efficienti e scalabiliUso di strutture di memorizzazione e di accesso
Categorie di algoritmi di Data MiningCategorie di algoritmi di Data Mining
Formato dei datiDB relazionali, Transactional DBs, Time-seriesDB Object-oriented, Spaziali o MultimedialiFlat file, Documenti testuali o ipertestuali
Tipi di pattern estratticlassificazione, clustering, associazioni, deviazioni,…Pattern ibridi, o a livelli multipli di aggregazione
Tecniche usateDatabase-oriented, modelli probabilistici, visualizzazione, reti neurali, alberi di decisione, programmi logici,..
Contesto applicativoDNA mining, Web mining, Weblog analysis, fraud analysis, …
Data Mining e KDD Data Mining e KDD
Knowledge Discovery in DatabasesEstrazione di conoscenza da dataset di grandi dimensioni, eventualmente affetti da rumore, eterogeneità, valori mancantiRisultato: pattern interessanti (validi, nuovi, comprensibili, utili)
Processo iterativo e interattivo
ProcessoProcesso didi KDDKDD
Selezione ePre-elaborazione
Data Mining
Interpretazione e Valutazione
Integrazione e Consolidamento
Conoscenza
p(x)=0.02
Sorgenti
Pattern e/o Modelli
Dati trasformati
DatiConsolidati
Selezione ePre-elaborazione
Data Mining
Interpretazione e Valutazione
Integrazione e Consolidamento
Conoscenza
p(x)=0.02
Sorgenti
Pattern e/o Modelli
Dati trasformati
DatiConsolidati
Data WarehouseData Warehouse
Task/Task/funzionalitfunzionalitàà didi Data MiningData Mining
PredizioneClassificazioneRegressione
ClusteringLink Analysis
Scoperta di Regole AssociativeAnalisi di sequenze e di time-series
Summarization Deviation DetectionSimilarity matching
Predizione: Predizione: classificazione e regressioneclassificazione e regressione
Obiettivo: indurre un modello in grado di prevedere il valore di un attributo target in base agli altri attributi
Classificazione: l’attributo target assume valori discreti Tecniche: Alberi di decisione, Regole di classificazione, Classificazione Bayesiana, K-nearest neighbors, Case-basedreasoning, Genetic algorithms, Rough sets, Fuzzy logic, Association-based classification, …
Regressione: l’attributo target assume valori continuiTecniche: Alberi di regressione, Reti neurali, regressione lineare e multipla, regressione non-lineare, regressione logistica e di Poisson, regressione log-lineare
Classificazione come Classificazione come apprendimento induttivoapprendimento induttivo
Task di apprendimento supervisionatole classi sono note a priori e si dispone di esempi già classificati
Classificazione: esempioClassificazione: esempio
training set: 14 giornate di cui è nota la classe
Tempo Tempo TemperTemper.(.(°°F)F) UmiditUmiditàà VentoVento ClasseClasse
SoleggiatoSoleggiato 8585 8585 NoNo Non si giocaNon si giocaSoleggiatoSoleggiato 8080 9090 SiSi Non si giocaNon si giocaNuvolosoNuvoloso 8383 7878 NoNo Si giocaSi giocaPiovosoPiovoso 7070 9696 NoNo Si giocaSi giocaPiovosoPiovoso 6868 8080 NoNo Si Si giocagiocaPiovosoPiovoso 6565 7070 SiSi Non si giocaNon si gioca
NuvolosoNuvoloso 6464 6565 SiSi Si giocaSi giocaSoleggiatoSoleggiato 7272 9595 NoNo Non si giocaNon si giocaSoleggiatoSoleggiato 6969 7070 NoNo Si giocaSi gioca
PiovosoPiovoso 7575 8080 NoNo Si giocaSi giocaSoleggiatoSoleggiato 7575 7070 SiSi Si giocaSi giocaNuvolosoNuvoloso 7272 9090 SiSi Si giocaSi giocaNuvolosoNuvoloso 8181 7575 NoNo Si giocaSi giocaPiovosoPiovoso 7171 8800 SiSi Non si giocaNon si gioca
Valutazione di un classificatoreValutazione di un classificatore
Capacità predittiva: capacità di classificare oggetti del dominio in modo corretto
accuratezza: % di oggetti classificati correttamente (errore di classificazione: 1 – accuratezza)L’accuratezza teorica (sul dominio) può essere stimata:
su un test-set (indipendente dal training set), cioè un insieme di oggetti del dominio di cui è nota la classesullo stesso training set, inducendo vari modelli su campioni (indipendenti) di esso: Cross-Validation
Capacità descrittiva: comprensibilità della conoscenza rappresentata dal modello
Dipende dal linguaggio delle ipotesi e dalla lunghezza della rappresentazione del modello (numero di nodi dell’albero di decisione, nr. di regole, …)
Classificazione Classificazione –– Tipi di modelliTipi di modelli
Vari tipi di modelli di classificazione Differiscono per il formalismo utilizzato per rappresentare la funzione di classificazione (Linguaggio delle ipotesi)
Alcuni tipi di modelli (classificatori):Basati sugli esempi (es. Nearest neighbor)Matematici (es. Reti Neurali Artificiali, SVM)Statistici (es.: Naive Bayes)
memorizzano i parametri delle varie distribuzioni di probabilitàrelative alle classi ed agli attributi → per classificare un generico oggetto si possono stimare le probabilità di appartenenza alle varie classi
Logici (es.: Alberi e Regole di Decisione)la funzione di classificazione è espressa mediante condizioni logiche sui valori degli attributi
Alberi di decisione Alberi di decisione
SE (Tempo=piovoso E Vento=no) ALLORA (Classe=Si Gioca)
Si gioca
tempo
umidità vento
soleggiatosoleggiato nuvolosonuvoloso piovosopiovoso
<=75<=75 >75>75 ssìì nonoSi gioca
Si giocaNon si gioca
Non si gioca
ogni nodo interno n è associato ad un attributo A(n)ogni arco uscente dal nodo n è associato ad un insieme di valori di Aogni foglia è etichettata con il valore atteso della classe per gli oggetti descritti dal cammino che collega la foglia alla radice
Un albero di decisione equivale ad un insieme di regole Un albero di decisione equivale ad un insieme di regole logiche mutuamente esclusive (logiche mutuamente esclusive (una regola per ogni foglia)una regola per ogni foglia)
Alberi di decisione Alberi di decisione
Predizione : applicazione della funzione di classificazione ad un nuovo oggetto Es.: l’albero assegna la classe Si Gioca alla giornata G
tempo
umidità vento
soleggiato nuvoloso piovoso
<=75 >75 sì no
Si gioca
Si gioca Si giocaNon si gioca
Non si gioca
giornata G
Tempo = Piovoso Tempo = Piovoso Temperatura = Temperatura = 79 Umidit79 Umiditàà = 85 = 85 Vento = noVento = no
Indurre un albero di decisioneIndurre un albero di decisione
Dati: Un insieme di esempi con classe nota
Problema: Generare un modello ad albero di decisione per classificare le tuple della popolazione (anche non presenti nel training set) con un errore minimale
Strategia : sviluppa l’albero in maniera top-down piazza la variabile di test più importante alla radice di ogni sottoalbero successivo
La variabile più importante:La variabile che ha la maggiore attendibilità nel distinguere l’insieme degli esempi di trainingquella che separa meglio le classi
SceltaScelta delladella variabile migliorevariabile migliore
Misure di impurità di un insieme rispetto alle classiInformation entropy
0 se è presente una sola classe, 1 se le classi sono distribuite equamente
Altre misure: Gini Index
Indice di splitting: Information Gainè pari alla diminuzione dell’entropia ottenuta partizionandol’insieme sulla base dei valori della variabile scelta
∑=
−=k
iii ppSEntropy
1log)(
Induzione di alberi : esempioInduzione di alberi : esempioTraining set T : 14 esempi [9 Si, 5 No]Come partizionarlo? quale attributo scegliere per la radice? →
S : [S : [9 Si, Si, 5 No]No]
Entropia = 0.94Entropia = 0.94
Tempo Tempo TempTemp. . UmidUmid. Vento Classe. Vento Classe
Sol.Sol. AltaAlta AltaAlta NoNo NoNoSol. Alta Alta Sol. Alta Alta SiSi NoNoNuvNuv. Alta Alta. Alta Alta NoNo SiSiPiovPiov. Media Alta. Media Alta NoNo SiSiPiovPiov. Bassa . Bassa NormNorm.. NoNo Si Si PiovPiov. Bassa . Bassa NormNorm.. SiSi NoNoNuvNuv. Bassa . Bassa NormNorm.. SiSi SiSiSol. Media AltaSol. Media Alta NoNo NoNoSol. Bassa Sol. Bassa NormNorm.. NoNo SiSiPiovPiov. Media . Media NormNorm.. NoNo SiSiSol. Media Sol. Media NormNorm.. SiSi SiSiNuvNuv. Media Alta. Media Alta SiSi SiSiNuvNuv. Alta . Alta NormNorm.. NoNo SiSiPiovPiov. Media Alta. Media Alta SiSi NoNo
1. Umidit1. Umiditàà??
umidità
Alta NormaleS: [S: [3 Si, Si, 4 No]No]
EntrEntr. = 0.985. = 0.985S: [S: [6 Si, Si, 1 No]No]
EntrEntr. = 0.592. = 0.592
Gain (S,Umidità) = 0.94 – (7/14) * 0.985 – (7/14) * 0.592
= 0.151
2. Vento?2. Vento?vento
No SiS: [S: [6 Si, Si, 2 No]No]
Entropia = 0.94Entropia = 0.94S: [S: [3 Si, Si, 3 No]No]
Entropia = 0.94Entropia = 0.94
Gain (S,Vento)= 0.94 – (8/14) * 0.811 – (6/14) * 1.000
= 0.048
Sull’intero training set T Umidità permette di discriminare le classi “meglio”diVento : Gain (T,Umidità)=0.151 > Gain (T,Vento)=0.048
OverfittingOverfitting
Overfitting: sovradattamento al training setIl modello classifica bene gli esempi da cui è stato indotto ma non altri oggetti del dominio
Alberi troppo grandi sono:poco comprensibili spesso soffrono di overfitting
Trovare l’albero più semplice che sia consistente con gli esempi di training è in generale un problema intrattabile
Fondamento “filosofico” → Rasoio di Ockham:“Ipotesi troppo complicate sono poco probabili”(le spiegazioni più semplici sono spesso quelle esatte)
Ricerca dellRicerca dell’’albero della albero della ““giusta tagliagiusta taglia””
Arresto della crescita dell’albero (pre-pruning)sulla base di un criterio di significatività degli splitting:
soglia minima per il numero di oggetti dei nodi generati soglia minima per il valore dell’indice di splitting (riduzione del disordine)
Pruning (potatura): dopo aver costruito l’albero si eliminano i sotto-alberi che non contribuiscono all’accuratezza sul dominio,
sostituendoli con una foglia (subtree replacement) oppure con un loro sotto-albero (subtree racing).
L’accuratezza sul dominio degli alberi considerati nella fase di pruning può essere stimata
mediante cross-validationoppure riservando una porzione del training set per il test (es:reduced error pruning)
Altre tecniche di apprendimentoAltre tecniche di apprendimento
Instance-base learning
Support Vector Machines
Reti neurali
Algoritmi genetici
InstanceInstance--BasedBased LearningLearning
Idea: Il processo di apprendimento si riduce alla memorizzazione degli esempi (Lazy learning)La generalizzazione viene ottenuta a tempo di classificazione (regressione) interpolando secondo una “qualche regola”Algoritmi: K-NN, RBFN, Locally weighted regression, …
k-Nearest Neighbor (k-NN)E’ definito in termini di una funzione di (dis)similaritàIl valore della funzione target è assegnato sulla base dei valori dei K esempi più vicini
Per funzioni reali (regressione), il valore medio nel vicinatoPer funzioni discrete (classificazione), il valore più frequente
kk--NNNN e classificazionee classificazione
Si selezionano i K piùvicini e si assegna la classe di maggioranza
K = 1 => classe = ++K = 3 => classe = --
Se scopro che la classe assegnata è sbagliata memorizzo il nuovo caso classificato correttamente da un maestro
Support vector machinesSupport vector machines
Trova l’iperpiano di separazione con margine massimo
Tecniche di ottimizzazione matematica (quadratica)
Efficace se estesa con kernel-methods -> superfici non lineari
RetiReti neuralineurali artificialiartificialiGrafo orientato e pesato sugli archi, e con una funzione associata ad ogni nodo (neurone)
ApprendimentoPropaga I valori di input nel grafoConfronta l’output con quello attesoModifica i pesi di conseguenza
Hidden nodes
Output nodes
x1
x2
x3
RetiReti neuralineurali artificialiartificiali
Contro:
- Bisogna indicare la giusta topologiadela rete
- Lunghi tempi di apprendimento
- Difficile interpretazione (black-box)
- Overfitting
Pro:
+ “complesse” superfici diseparazione (non lineari)
+ predizione veloce
+ possono gestire molti attributi
Altri task di Data MiningAltri task di Data Mining
ClusteringMisure di similarità
Scoperta di regole associative
ClusteringClustering
Clustering: Partizionamento dei dati in un insieme di classi non note a-priori (cluster) Qualità della partizione:
Alta omogeneità intra-classeBassa omogeneità inter-classe
In genere si basa su una misura di similarità/distanza
Esempi di applicazione:Customer segmentationcompressione dei datisuddivisione di corpora di documenti
ClusteringClustering: criteri di raggruppamento: criteri di raggruppamento
Distanza
••
• ••••
•
••
•• •
••
•••
• • •• •
•• •
••
• •••
• ••
••••• •
••
••
•
•
••
•
••
•• ••
•
•••
• • •• •• ••• •••
• • •• ••
•
•••
• ••••••
•
• •• ••
••• •
DensitàForma
(“Gestalt”)
• • • • • • • •
••••• • • ••
••••••
ClusteringClustering: misure di (: misure di (disdis)similarit)similaritàà
Misure classiche:Similarità: Jaccard, Coseno, Overlap,…Distanza: Euclidea, Manhattan,…
Non adatte a dati complessi es., Time series, Testi, Immagini, grafiPer dati con molte feature, la distanza Euclidea produce valori simili per tutte le coppie di punti
Sol1: Ridurre il numero di dimensionirandom projections, feature selectiontrasformazione delle feature con metodi statistici (es., PrincipalComponent Analysis)
Sol2: Definire misure specifiche o usare diverse featureimmagini: feature come nr. oggetti contenuti, distribuzione colori, …time series: misure shape-based
Clustering: Clustering: algoritmialgoritmi
Partizionalidistance-based: K-means
GerarchiciAgglomerativi o divisivisingle link o complete link
Model-Based Approcci StatisticiNeural network
Altri metodi:Density-BasedGrid-Based
Clustering: Clustering: algoritmoalgoritmo KK--meansmeans
Input:
Dati = tuple con attributi numerici (esistono varianti per dati categorici)
numero K di cluster desiderati
Criterio:
minimizzare la somma dei quadrati delle distanze di ogni punto dal centro del suo cluster
Algoritmo:
Fissa una partizione iniziale (random) in K cluster
Ripeti fino a che non si abbia nessuna variazione:Assegna ogni punto al centro più vicino
Genera i nuovi centri
Clustering:Clustering: KK--MeansMeans
Esempio
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
Clustering Clustering GerarchicoGerarchico
Raggruppano/Separano I dati sulla base di una matrice di distanze (o similarità)
La distanza fra due cluster è calcolata in funzione delle distanze fra le istanze che rispettivamente contengono
Step 0 Step 1 Step 2 Step 3 Step 4
b
dc
e
a a b
d ec d e
a b c d e
Step 4 Step 3 Step 2 Step 1 Step 0
agglomerativo(AGNES)
divisivo(DIANA)
Scoperta di Regole AssociativeScoperta di Regole Associative
Task di natura esplorativa:scoperta di associazioni tra fatti, proprietà o valori di variabili (“link analysis”)
Dati:insieme di transazioni
es. carrello della spesa di un clienteogni transazione é un insieme di item (itemset)
es.: prodotti nel carrello
Obiettivo:trovare tutte le regole che correlano la presenza di un insieme di item con un altro insieme di item
Es.: 98% delle persone che comprano {pannolini, cibo per bebè} comprano anche {birra}.
Regole Regole assocassoc.: qualit.: qualitàà delle regoledelle regole
L’utente specifica soglie minimeche le regole estratte devono essere superare, per alcune misuredi qualità (interestingness)
Supporto (indice di significatività)1 & 2 => 3 ha confidenza 5% se si applica nel 5% dei casi
Confidenza (indice di validità)1 & 2 => 3 ha confidenza 90% se quando viene acquistato 1 e 2, nel 90% dei casi viene acquistato anche 3.può essere sviante: non implica causalità, non riconosce correlazioni negative né indipendenza
Altre misure: Misura di correlazione (es.: lift, Interest)Soggettive: cercano di catturare novità e utilità delle regole
Regole associative: ricercaRegole associative: ricerca
Algoritmo Apriori:Principio: ogni sottoinsieme di un itemset frequente è frequenteFase 1: Trova tutti gli itemset che hanno un supporto minimo
usa (k – 1)-itemset frequenti per generare k-itemset candidatidatabase scan and pattern matching per verificare frequenza
Fase2: Genera le regole a partire dagli itemset frequenti trovati… La fase1 è costosa: spazio di ricerca enorme!
Miglioramenti: Ottimizzare la ricerca degli itemset frequenti
Campionamento, Dynamic itemset counting (aggiunge un nuovo candidato solo quando tutti i suoi sottoinsiemi sono stimati come frequenti), Hash-based itemset counting, Transaction reduction
Evitare di generare tutti itemset candidati (es, algoritmo FP-tree)
Problematiche e linee di sviluppo del Problematiche e linee di sviluppo del Data MiningData Mining
Potenziamento dei metodi di Data MiningSelezione automatica fra tecniche e modelli alternativiIncorporamento di conoscenza pregressa (background knowledge)Interpretazione (e visualizzazione) dei pattern estrattiGestione dei rumore e dati incompletiValutazione dei pattern: interestingness
Definizione di Data Mining Query LanguagesSpecifica dichiarativa del task di data miningSviluppo indipendente di algoritmi per le primitive di miningStrategie di query optimization
Integrazione con OLAPselezione interattiva (On-line) di funzioni di data miningmining di pattern a livelli multipli di astrazione
Problematiche e linee di sviluppo del Problematiche e linee di sviluppo del Data Mining (2)Data Mining (2)
Performance e scalabilitàAlgoritmi paralleli, distribuiti, Algoritmi incrementali (importanti nel caso di streaming data)Mining su dati multi-relazionali e dati complessi
Sfruttamento della conoscenza estrattaUso all’interno di applicazioni domain-specific: Intelligent query answering, recommendations, Inventory controlIntegrazione della conoscenza scoperta con quella preesistente
Impatto socialeProtezione di sicurezza, integrità, e privacy dei dati
Morale: un settore abbastanza maturo, ma con grandi prospettive (e aspettative) di sviluppi ulteriori, sia teorici sia applicativi