Giorgio Pedrazzi CINECA Torino, 20 febbraio 2003.
-
Upload
macario-vitale -
Category
Documents
-
view
238 -
download
8
Transcript of Giorgio Pedrazzi CINECA Torino, 20 febbraio 2003.
Giorgio Pedrazzi CINECA
Torino, 20 febbraio 2003
Processo di estrazione di conoscenzaconoscenza da banche dati di
grandi dimensionigrandi dimensioni tramite l’applicazione di algoritmi che
individuano le associazioni associazioni “nascoste”“nascoste” tra le informazioni e
le rendono visibili.
Che cos’è il Data Mining
volumevolume
valorevalore
dati
informazione
conoscenza
decisione
• Quantità di dati
• Natura dei dati
• Rapida evoluzione del mercato
• Inadeguatezza degli strumenti tradizionali
Perché sono necessari strumenti di Data Mining
Dati
?
?
?
?
STRUMENTI STATISTICI
DATA RETRIEVAL
DATA MINING
• analisi descrittive
• analisi esplorative
Problemi:•quantità di dati (records, variabili)•tipo di dati (qualitativi, testi)•missing•interpretazione risultati
queryProblemi:•tempi di risposta•inadeguatezza nell’individuare associazioni
conoscenza
Statistica tradizionale
Statisticainferenziale
Statistica
Statisticadescrittiva
Sono i due campioni
identicamente distribuiti ?
Inferenze eprevisioni
Descrizione dei dati
Il processo di estrazione di conoscenza (KDD)
Database /Database /Data WarehouseData Warehouse
Target dataTarget data
Selection /Sampling
Transformed dataTransformed data
Transformationand reduction
Cleaned dataCleaned data
Preprocessingand cleaning
Patterns / modelsPatterns / models
Data MiningKnowledgeKnowledge
Visualization /Evaluation
clienti
Segmentazione della clientela
agenziestampa
Analisi testualeTEXT MINING
venditeAnalisi delle associazioni
brevetti
Technology Watch
DATA MININGClustering
Reti neurali
Alberi di decisione
Associazioni
Segmentazione
Classificaz./ Previsione
Tecniche e tradizionali ambiti applicativi del Data Mining
Perché il Data mining in biologia• Esplosione della informazione biologica
in forme diverse
• The Human Genome Project: più di 22.1 miliardi di basi; parecchie decine di migliaia di geni sono stati identificati a partire dalla sequenza genomica.L’analisi delle sequenze mostrano 38,000 geni confermati dall’evidenza sperimentale.
• Swiss Prot Database: più di 10,000 proteine
• Pubmed: più di 12,000,000 abstracts biologici , ed il loro numero sta ancora aumentando!
………
• Relazioni complesse tra i dati biologici
Perché il Data mining in biologia
Perché il Data mining in biologia
• L’industria biofarmaceutica genera più dati chimici e biologici di quanti ne riesca a trattare. Come risultato di tutto ciò la creazione di nuovi composti farmaceutici è spesso un lungo ed arduo lavoro.
Perché il Data mining in biologia• La biologia rappresenta un campo di applicazione interessante per il Data Mining con un notevole disponibilità di dati e di problemi complessi. I metodi tradizionali, a volte, non sono sufficienti per analizzare una simile quantità di dati. Le due discipline si possono avvantaggiare l’un l’altra nella collaborazione.
KDD per la Bioinformatica
Genomic
Literature
Experimental
Integrated Data
Repository
Prepareddata
Dati
NormalizationCurationValidation…
ClusteringSVMsILPClassification…
Patterns
EvaluationVisualization
ConoscenzaExpert
Knowledge
SamplingExpressed GenesHomologs…
Spesso non esplicitament
e implementata
Selezione dei dati
Interrogazione dei databases pubblici (Bioperl).Genbank.
Stanford microarray database.
SWISS-Prot.
….
Dati raccolti in esperimenti
Integrazione delle diverse fonti di dati
Preparazione dei dati (data cleansing)
• Rimozione dei dati non validi, ridondanti o privi di utilità.
• Trattamento dei dati mancanti.
• Selezione delle variabili
• Trasformazione dei dati.– Dicotomizzazione, normalizzazione,
riproporzionamento, etc.
Alcune tecniche di Data Mining
• Clustering (classificazione non supervisionata)
• Text Mining (Medmole)
• Regole di associazione
• Classificazione (Alberi di decisione)
• Visualizzazione dei risultati
Altre tecniche: analisi delle serie temporali, analisi delle sequenze
Il punto di partenza di tutti gli algoritmi di clustering è un modello che prescinde completamente alla natura dei dati impiegati e dalle specifiche problematiche disciplinari. Si fa riferimento in generale ad una matrice dei dati contenente informazioni su N oggetti (casi o osservazioni; righe della matrice) specificate dai valori assegnati a V variabili (colonne della matrice)
Clustering
• Scelta delle variabili
• Indice di somiglianza
•Metodo di formazione dei gruppi
•Determinazione dei criteri di valutazione
Clustering
N
D
X11 X12 X13 … X1d (L)
X21 X22 X23 … X2d (L)
…
Xn1 Xn2 Xn3 … xnd (L)
variabile
osservazione
Rappresentazione formale del dato in forma matriciale
Clustering
Dalla matrice dei dati originaria (di dimensione NxV) si passa ad una matrice di distanze o di similarità fra casi (di dimensione NxN)
n
d
d(1,1) d(1,2) d(1,3) … d(1,n)
d(2,2) d(2,3) … d(2,n)
d(n,n)
Distanze dall’oggetto j
Distanze dall’oggetto i
Clustering
Una volta stabiliti i criteri per la misura del grado di similarità/diversità, è possibile sviluppare molteplici algoritmi per la classificazione dei casi.
Per variabili di tipo quantitativo si calcolano misure di distanza.
Per variabili di tipo qualitativo si calcolano misure di similarità.
Clustering
Distanza euclidea (di norma 2)
Distanza di Manhattan (o a blocchi)
2/1
1
2)(),(
d
jkjij xxkid
Misure di distanza
d
jkjij xxkid
1
||),(
Alcuni esempi di misure di distanza
Clustering
Esempi di misura di distanza
x = (5,5)
y = (9,8)Distanza euclidea:d(x,y) =sqrt(42+32)= 5
Distanza di Manhattan:d(x,y) =4+3 = 7
4
35
Clustering
Misure di similarità
xk: 0 1 1 0 1
xj: 1 1 0 1 1
Jaccard: d(i,k)= (a11) / (a11 + a10 + a01 )
Condorcet: d(i,k)= a11 / [a11+0.5(a10 + a01)]
Dice bis: d(i,k)= a11 / [a11+0.25(a10 + a01)]
a11 a10
a01 a00
1 0
1
0
2 2
1 0
1 0
1
0
Numero di 1corrispondenti
Clustering
Clustering
Clusteringgerarchico
Clusteringpartitivo
K-medie, Som, … Analisi relazionale…………..
Tecniche di Clustering
Clustering partitivo Clustering gerarchico
E
E1
E2E3
E4
E7
E8
E
E1 E2
E7 E8
Tecniche di Clustering
Gene Expression clustering
• Per gene (rat spinal cord development, yeast cell cycle):
• Wen et al., 1998; Tavazoie et al., 1999; Eisen et al., 1998; Tamayo et al., 1999.
• Per condizione o tipo di cellaGolub, et al. 1999; Alon, et al. 1999; Perou, et al. 1999; Weinstein, et al. 1997 Cheng, ISMB 2000.
Le tecniche di clustering sono utilizzate anche nelle applicazione di Text Mining.
Medmole è un’applicazione di Text Mining sugli abstract di Medline
Text Mining (Medmole)
Resultsexample: RET <OR> BRCA1
ClusterResultsexample: RET <OR> BRCA1
Cluster Keywords
Resultsexample:
RET <OR> BRCA1
Results example: RET <OR> BRCA1
Regole di associazione
• Dati del problema:– I insieme di items
• Prodotti venduti da un supermercato
– Transazione T: insieme di items t.C. T i• Oggetti acquistati nella stessa transazione di cassa al
supermercato
– Base di dati D: insieme di transazioni
Regole di associazione
• Regola di associazione X YX,Y I
• Supporto S: #trans. contenenti XY #trans. in D
– rilevanza statistica
• Confidenza C: #trans. contenenti XY #trans. contenenti X
– significatività dell’implicazione
Regole di associazione tra Sequenze proteiche, Struttura e Funzione
PROSITE
Sequence Motif Database
SWISS-PROT
Protein Sequence Database
PDB
Protein 3D Structure Database
Classificazione
Quale classe?
Modello di classificazione
Nuovi dati
Classificazione
• Dati del problema:– insieme di classi– insieme di oggetti etichettati con il nome della classe di
appartenenza (training set)
• Problema:– trovare il profilo descrittivo per ogni classe, utilizzando
le features dei dati contenuti nel training set, che permetta di assegnare altri oggetti, contenuti in un certo test set, alla classe appropriata
Costruzione del modello
TrainingData
NAME Color Shape Class
A Brown Bell bad
M Gray Convex good
B Yellow Bell good
J Gray Conical good
D Brown Convex good
C Gray Bell bad
Metodo diclassificazione
IF Color = ‘Yellow’OR Shape = ‘Conical’ or …THEN Class = ‘good’
Modello
Valutazione del modello
TestingData
NAME Color Shape Class
T Gray Bell bad
J Yellow Bell bad
W Yellow Flat good
H Gray Convex good
Modello di classificazione
Quanto è accurato il modello ?
IF Color = ‘Yellow’OR Shape = ‘Conical’ or …THEN Class = ‘good’
Applicazioni
• Classificazione tendenze di mercato
• identificazione automatica di immagini
• identificazione del rischio in mutui/assicurazioni
• efficiacia trattamenti medici
Alberi di decisione
• Veloci rispetto agli altri metodi
• Facili da interpretare tramite regole di classificazione
• Possono essere convertiti in interrogazioni SQL per interrogare la base di dati
Esempio
Eta` < 26
Alto Tipo auto
BassoAlto
ETA`
4065202550
CLASSE RISCHIObassoaltoaltoalto
basso
TIPO AUTO
familiaresportivautilitariasportivafamiliaresi no
sportivafamiliare
Alto
utilitaria
Costruzione albero
• Due fasi:– fase di build: si costruisce l’albero iniziale,
partizionando ripetutamente il training set sul valore di un attributo, fino a quando tutti gli esempi in ogni partizione appartengono ad una sola classe
– fase di pruning: si pota l’albero, eliminando rami dovuti a rumore o fluttuazioni statistiche
Esempio di albero di decisione creato per la classificazione di tessuti in cancerosi o non cancerosi utilizzando come variabili l’espressione genica dei geni rilevanti nel B-cell Lymphoma
Altri metodi di classificazione
Reti neurali
Support Vector Machine
Naive Bayes
……
VisualizzazioneVisualizzazione dei cluster Coordinate parallele
Evoluzione Temporale
Alcuni libri introduttivi
1. Bioinformatics – the machine learning approach by P. Baldi & S. Brunak, 2nd edition, the MIT press, 2001
2. Data mining – concepts and techniques by J. Han & M. Kamber, Morgan Kaufmann publishers, 2001
3. Pattern classification by R. Duda, P. Hart and D. Stork, 2nd edition, john Wiley & sons, 2001