Fondamenti di Data Warehousing e Data...

76
Fondamenti di Fondamenti di Data Warehousing Data Warehousing e Data Mining e Data Mining Luigi Pontieri Luigi Pontieri ICAR ICAR - - CNR CNR

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

Il paradigma multidimensionaleIl paradigma multidimensionale

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…

RollRoll--upup e e DrillDrill--downdown

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)

Regole AssociativeRegole Associative

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