Basi di dati distribuite
Prof. M.T. PAZIENZA
a.a. 2003-2004
DATA MINING
Data Mining
Obiettivo del Data Mining è quello di:
• supportare l’analisi esplorativa di volumi di dati molto grandi
• con metodologie di tipo statistico • con l’intento di riconoscere nei dati ed estrarre
trend e fenomeni regolari sconosciuti e potenzialmente utili a supporto di decisioni in merito ad argomenti specifici
Data Mining - Tools
Il DM è il processo di identificazione di correlazioni o patterns tra decine e decine di campi in database di grandi dimensioni.
Software per il Data Mining: supportare l’utente nell’analisi di dati da diversi punti di viste (dimensioni), classificarli e sintetizzare le relazioni identificate.
Data Mining: scalabiltà
Il DM deve elaborare grandi quantità di dati per cui adotta algoritmi scalabili, ovvero per i quali i tempi di elaborazione crescono linearmente alla misura del data set mentre mantengono costante la quantità di risorse utilizzate.
Data Mining: caratteristiche
I sistemi di data mining sono caratterizzati dal dover gestire:
Grandi quantità di dati (ingestibili se non con strumenti automatici)
Dati incompleti e /o imprecisiDati inficiati da errori non prevedibili (alcuni
attributi si basano su giudizi o misure del tutto soggettivi)
Dati a struttura complessaDati eterogenei
Data Mining: tecniche usate
• Clustering i.e. cluster analysis
• Data summatization
• Learning classification rules
• Finding dependency network
• Analysing changes
• Detecting anomalies
Data Mining - Discovery
• Classi: i dati del db vengono usati per localizzare raggruppamenti predeterminati
• Cluster: data item vengono raggruppati secondo relazioni logiche o preferenze dell’utente
• Associazioni: i dati vengono analizzati per identificare associazioni (o cooccorrenze)
• Pattern sequenziali: i dati vengono analizzati per anticipare il loro comportamento (trend e pattern)
Clustering
L’attività del clastering o segmentazione di un data base è l’azione del partizionamento del data base cosicché ciascun gruppo o partizione sia simile in accordo ad un qualche criterio o metrica (->produzione di profili di utenti)
Con il clustering si ottengono sottogruppi (dei dati) cui verranno applicate ulteriori analisi
KDD-knowledge e data discovery
Si identificano quattro passi:
1. Data selection - identificazione dei dati ed attributi di interesse-
2. Data cleaning - rimozione del rumore, conversione in unità di misura comparabili -
3. Data mining - applicazione di algoritmi di estrazione di pattern-
4. Valutazione - i pattern sono visualizzati all’utente per una valutazione -
Cooccorrenze
Identificazione di eventi complessi (customer transaction) cooccorrenti (market basket)
Estrapolazioni (con qualche problema)Itemset è un set di item all’interno di una
transazione utenteIl supporto di un itemset è la frazione di
transazioni in una base dati che contiene tutti gli item dell’itemset
Cooccorrenze
Calcolo degli itemset frequenti
Algoritmo iterativo (ipotesi: ogni subset di un itemset frequente è un itemset frequente) Si parte da una numerosità 1 per incrementarla di passo in passo; nessun itemset viene perso.
Regole di associazione
Regole che associano un attributo di una relazione ad un altro
Una regola di associazione indica quanto un set di item sia implicato da un altro.
Ogni regola ha associate due misure:Supporto: percentuale di transazioni per le quali
l’implicazione è veraConfidenza: percentuali di transazioni che
contengono tutti gli item implicati; è una misura della validità della regola.
Regole di associazione (generaliz.)
Gerarchia ISA :ogni transazione contiene implicitamente, per ciascuno dei suoi item, gli antenati nella gerarchia.
E’ possibile riconoscere relazioni tra item a diversi livelli della gerarchia
Sostituire un itemset con uno dei suoi antenati nella gerarchia aumenta il valore del supporto da esso fornito alla transazione
Regole di associazione (generaliz.)
Analisi temporale (calendario=qualunque gruppo di date): dato un calendario, si possono calcolare regole associative relativamente al set di tuple il cui campo data cade all’interno del calendario.
Il supporto di una tupla all’interno di un calendario può essere significativamente diverso (sia > che < ) da quello all’interno della base di dati
Regole di associazione (generaliz.)
Il concetto di sequenze di item è associato a quello di sequenze di transazioni associate ad un particolare valore di un attributo
Una sottosequenza di una sequenza di itemset si ottiene cancellando uno o più itemset; una sottosequenza è ancora una sequenza di itemset.
Il supporto di una sottosequenza S è la percentuale di sequenze di cui S è una sottosequenza
Regole di associazione (generaliz.)
Funzioni per il riconoscimento di sequenze di pattern analizzano collezioni di record correlati e scoprono pattern che ricorrono frequentemente su un determinato periodo di tempo (sequenze temporali)
Regole predittive - predicati
Si vuole identificare regole con una struttura specifica
L’attributo designato il cui valore deve essere predetto, si chiama attributo dipendente
Tutti gli altri attributi si chiamano attributi predittivi
Gli attributi predittivi vengono usati per predire (desumere) il valore dell’attributo dipendente
Regole predittive - predicati
La forma del predicato dipende dal tipo dell’attributo predittivo (numerico, categoriale)
Attributi numerici -> analisi numeriche
(regole di regressioneregole di regressione)
Attributi categoriali -> test su valori
(regole di classificazioneregole di classificazione)
Regole
Le regole di regressione e di classificazione si applicano a valori continui e di categoria, mentre le regole associative ad un valore specifico appartenente ad un data set
Si possono combinare più regole tra loro anche se di tipo diverso instanziando una sorta di ragionamento definito di volta in volta sulla specifica applicazione (che ne identifica la forma ed i valori degli attributi)
Alberi di decisione
Un albero di decisione è una struttura dati ad albero che rappresenta set di decisioni.
Queste decisioni generano regole per la classificazione di un dataset.
Un albero di decisione è una rappresentazione grafica di una collezione di regole di classificazione
Alberi di decisione
Ogni nodo del cammino è un attributo predittivo
Il nodo foglia è un attributo dipendente e rappresenta la regola di classificazione
L’albero di decisione è una collezione di regole di classificazione: una per ogni foglia
Ottimizzare la costruzione del data base tenendo conto dell’albero di decisione
Alberi di decisione
• Usati per rappresentare conoscenza
• Costruiti tramite un training set
• Le regole sono in genere semplici ed intuitive
Problemi
• Difficili da mantenere
• Inadeguati per rappresentare molti tipi di conoscenza
Clustering
Partizionare in gruppi un set di record del data base in modo che all’interno di un gruppo e record siano simili (godano di una stessa proprietà), mentre due gruppi di record siano dissimili
Ciascun gruppo identifica un cluster ed ogni record appartiene ad un solo cluster
La similarità tra record è misurata dalla funzione distanza
Processo di Data Mining- Fasi
Data pre-processing• Risoluzione dell’eterogeneità dei dati• Pulizia dei dati• Organizzazione dei dati per la ricerca Applicazione di tool per il data mining• Estrazione di pattern dai dati preprocessati Interpretazione e valutazione• Orientati all’utente (attributi di interesse,
conoscenza del dominio, conoscenza a-priori
Processo di Data Mining- Issues
• Rumorosità dei dati
• Staticità dei dati
• Sparsità
• Rilevanza
• Eterogeneità
• Efficienza degli algoritmi
• Dimensione e complessità dei dati
• …
Processo di Data Mining- Tecniche
• Statistica
• Clustering
• Visualizzazione
• Induzione di regole
• ….
Data Mining- Infrastrutture tecnologiche
Applicazioni esistono su ogni tipo e misura di sistemi (piattaforme mainframe, client/server, e PC)
Prezzi da poche migliaia di euro su, su fino a più di milioni di euro.
Misura del data base: maggiore è la quantità di dati collezionati ed elaborati, maggiore è la potenziali del sistema di DM prodotto
Complessità delle query: maggiore è la complessità elle query, maggiore è il numero delle query processate, e maggiore è la potenza del sistema di DM prodotto
Data Mining- Infrastrutture tecnologiche
La tecnologia dei data base relazionali è adeguata nella maggior parte di applicazioni che gestiscono fino ad alcuni gigabyte di dati . Per applicazioni di dimensioni maggiori bisogna trovare soluzioni alternative (processori paralleli) per raggiungere tempi di processamento utili.
Top Related