Giorgio Pedrazzi
CINECA
Torino, 20 febbraio 2003
Che cos’è il Data Mining
Processo di estrazione di
conoscenza da banche dati di
grandi dimensioni tramite
l’applicazione di algoritmi che
individuano le associazioni
“nascoste” tra le informazioni e
le rendono visibili.
Perché sono necessari strumenti
di Data Mining
• Quantità di dati
valore
• Natura dei dati
• Rapida evoluzione
del mercato
• Inadeguatezza
degli strumenti
tradizionali
volume
decisione
conoscenza
informazione
dati
?
Dati
• analisi
descrittive
?
STRUMENTI
STATISTICI
?
DATA
RETRIEVAL
query
?
DATA
MINING
conoscenza
• analisi
esplorative
Problemi:
•quantità di dati (records, variabili)
•tipo di dati (qualitativi, testi)
•missing
•interpretazione risultati
Problemi:
•tempi di risposta
•inadeguatezza nell’individuare
associazioni
Statistica tradizionale
Statistica
Statistica
descrittiva
Statistica
inferenziale
Descrizione dei dati
Inferenze e
previsioni
Sono i due campioni
identicamente distribuiti
?
Il processo di estrazione di
conoscenza (KDD)
Visualization /
Evaluation
Data Mining
Transformation
and reduction
Preprocessing
and cleaning
Selection /
Sampling
Database /
Data Warehouse
Patterns / models
Transformed data
Cleaned data
Target data
Knowledge
clienti
Tecniche e tradizionali ambiti
applicativi del Data Mining
Segmentazione della clientela
vendite
DATA MINING
Clustering
Analisi delle
associazioni
Segmentazione
Reti neurali
Classificaz./
Alberi di decisione Previsione
Associazioni
agenzie
stampa
Technology Watch
brevetti
Analisi testuale
TEXT 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!
………
Perché il Data mining in biologia
• Relazioni complesse tra i dati biologici
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
Normalization
Curation
Validation
…
Sampling
Expressed Genes
Homologs
…
Integrated
Data
Repository
Evaluation
Clustering
Visualization
SVMs
ILP
Classification
…
Prepared
data
Patterns
Experimental
Dati
Spesso non
esplicitament
e
implementata
Conoscenza
Expert
Knowledge
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
Clustering
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
Rappresentazione formale del dato in forma matriciale
variabile
N
D
X11
X12
X13
…
X1d
(L)
X21
X22
X23
…
X2d
(L)
Xn2
Xn3
…
xnd
(L)
…
Xn1
osservazione
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
Distanze dall’oggetto j
d
d(1,1) d(1,2) d(1,3) …
d(1,n)
Distanze d(2,2) d(2,3) …
dall’oggetto i
d(2,n)
d(n,n)
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
Misure di distanza
Distanza euclidea (di norma 2)


2
d (i, k )   ( xij  xkj ) 
 j 1

d
1/ 2
Distanza di Manhattan (o a blocchi)
d
d (i, k )   | xij  xkj |
j 1
Alcuni esempi di misure di distanza
Clustering
Esempi di misura di distanza
Distanza euclidea:
d(x,y) =
sqrt(42+32)
=5
y = (9,8)
5
4
x = (5,5)
3
Distanza di Manhattan:
d(x,y) =
4+3 = 7
Clustering
Misure di similarità
Numero di 1
corrispondenti
xk:
01101
xj:
11011
1
0
1
a11
a10
0
a01
a00
1
0
1
2
2
0
1
0
 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)]
Tecniche di Clustering
Clustering
Clustering
gerarchico
…………..
Clustering
partitivo
K-medie, Som, …
Analisi relazionale
Tecniche di Clustering
Clustering partitivo
Clustering gerarchico
E
E1 E2
E
E7
E3
E7 E8
E8
E2
E4
E1
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 cella
Golub, et al. 1999; Alon, et al. 1999; Perou, et al.
1999; Weinstein, et al. 1997 Cheng, ISMB 2000.
Text Mining (Medmole)
Le tecniche di clustering sono utilizzate anche nelle
applicazione di Text Mining.
Medmole è un’applicazione di Text Mining sugli abstract
di Medline
Results
example:
RET <OR> BRCA1
Results
example:
RET <OR>
BRCA1
Cluster
Cluster
Results
example:
RET <OR>
BRCA1
Keywords
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

Y
X,Y  I
• Supporto S: #trans. contenenti XY
#trans. in D
– rilevanza statistica
• Confidenza C: #trans. contenenti XY
#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
Metodo di
classificazione
Training
Data
NAME
A
M
B
J
D
C
Color
Brown
Gray
Yellow
Gray
Brown
Gray
Shape
Class
Bell
bad
Convex
good
Bell
good
Conical
good
Convex
good
Bell
bad
Modello
IF Color = ‘Yellow’
OR Shape = ‘Conical’ or …
THEN Class = ‘good’
Valutazione del modello
Modello di
classificazione
Testing
Data
NAME
T
J
W
H
Color
Gray
Yellow
Yellow
Gray
Shape
Class
Bell
bad
Bell
bad
Flat
good
Convex
good
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` TIPO AUTO
si
Eta` < 26
Alto
no
familiare
sportiva
utilitaria
sportiva
familiare
40
65
20
25
50
Tipo auto
sportiva
utilitaria
familiare
Alto
Basso
Alto
CLASSE
RISCHIO
basso
alto
alto
alto
basso
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
……
Visualizzazione
Coordinate parallele
Visualizzazione dei cluster
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