Bioinformatica
Classificazione
Dr. Giuseppe Pigola – [email protected]
Classificazione e Predizione
CLASSIFICAZIONE
 Processo di individuazione di una etichetta della classe categoriale di
appartenenza di un oggetto;

Se una banca deve decidere se assegnare o meno un prestito ad un
correntista, «lo classifica» assegnando una etichetta categoriale (ad es.
affidabile / non affidabile);

Il medico che deve fare una diagnosi su un paziente «lo classifica»
assegnando una etichetta (ad es. malato / sano);
PREDIZIONE
 La predizione modella una funzione continua (mentre la classificazione ha a
che fare con valori discreti) e consente di individuare dati sconosciuti o
mancanti.
2
Bioinformatica
Classificazione
CLASSIFICAZIONE: TRE FASI

ADDESTRAMENTO: Costruzione del modello tramite un training set;

STIMA DELL’ACCURATEZZA: Calcolo della percentuale di correttezza
nell’individuazione della classe durante il processo di classificazione.




Velocità;
Robustezza: Capacità di discriminare dati corretti e errati;
Scalabilità;
Interpretabilità di ciò che si ottiene dal classificatore;
UTILIZZO: Il modello viene utilizzato per classificare input sconosciuti;

3
Bioinformatica
Classificazione: Preparazione dei Dati

DATA CLEANING: Si cerca di eliminare o ridurre il rumore provvedendo
a risolvere il problema di dati mancanti;

RELEVANCE ANALYSIS: Analizzare i dati e mantenere solo quelli
effettivamente discriminanti per la fase di classificazione;

DATA TRANSFORMATION AND REDUCTION: Si normalizzano alcuni
tipi di dati. La normalizzazione consiste nello scalare i valori di un attributo
in un range predefinito (ad esempio [0,1]);

Dato un set di dati generalmente viene suddiviso in due parti: Una parte
verrà utilizzata per addestrare il modello, l’altra verrà usata per testare il
modello;
4
Bioinformatica
Support Vector Machines - SVM
5
Bioinformatica
Support Vector Machines - SVM

Le SVM machines sono state sviluppate negli AT&T Bell Laboratories da
Vapnik e Chervonenkis;

Prime applicazioni:





OCR (optical character recognition);
Riconoscimento di oggetti [Blanz et al., 1996];
Indentificazione di oratori [Schmidt, 1996];
Identificazione di facce in immagini [Osuna, et al. 1997];
Classificazione di testi [Joachims, 1997].
Software:



6
http://www.csie.ntu.edu.tw/~cjlin/libsvm/
http://bengio.abracadoudou.com/SVMTorch.html
Bioinformatica
Support Vector Machines - SVM

Sono metodi di classificazione che garantiscono una elevata accuratezza
della predizione;

Necessitano di pochi dati. Non sono generalmente affette da overfitting;

Spesso però è difficile modellare un problema con le SVM, specialmente
quando si ha a che fare con spazi multidimensionali;

Obiettivo del metodo è quello di costruire una «funzione di classificazione»
che si spera possa classificare nuovi dati;

Considereremo il caso di classificazione con 2 classi, ma tutto può essere
esteso al caso di k classi;
7
Bioinformatica
Support Vector Machines - SVM
Per il calcolo della funzione f distinguiamo due casi:

8

Classificazione Lineare (I dati sono linearmente separabili): Esiste nello
spazio Rn almeno un iperpiano in grado di separare le tuple del training set (punti di
Rn) di classe C1 da quelle di classe C2;

Classificazione non Lineare (I dati non sono linearmente separabili): Non
esiste nello spazio Rn un iperpiano in grado di separare le tuple di classi diverse;
Bioinformatica
SVM – Classificazione Lineare

Trovare l’iperpiano che separa «meglio», cioè l’iperpiano che rende
massimo il margine, ovvero la distanza tra l’iperpiano e il punto di classe C1
(o C2) più vicino ad esso;

Tale iperpiano è detto Maximum Marginal Hyperplane (MMH);

Per R2 bisogna trovare la retta che rende massima la distanza dal punto più
vicino di C1 o C2;
9
Bioinformatica
SVM – Classificazione Lineare

H1,H2 = i due iperpiani passanti, rispettivamente, per i punti di C1 e C2 più
vicini al MMH.

I punti di C1 e C2 per cui passano H1 e H2 sono detti vettori di supporto e
m è il margine.
10
Bioinformatica
SVM – Classificazione Lineare

Date m coppie (x,y) con xRn e y{-1,1}, vogliamo trovare wRn e bR
tali che:
w  xi  b  0 Se yi  1
w  xi  b  0 Se yi  1

L’iperpiano separatore H è l’insieme di punti tali che
H  {x  R n | w  x  b  0}
11
Bioinformatica
SVM – Classificazione Lineare

Osserviamo che l’iperpiano H1 passa per un punto (una tupla) (xi,yi) con
yi=1 mentre H2 passa per un punto (xi,yi) con yi = -1. Dunque:
w  xi  b  1
Per H1
w  xi  b  1 Per H 2

Gli elementi del training set (xi,yi) soddisferanno i vincoli
w  xi  b  1
w  xi  b  1

quando yi  1
quando yi  1
O equivalentemente
yi ( w  xi  b)  1
12
Bioinformatica
SVM – Classificazione Lineare

Vogliamo allora rendere massima

Sia P un vettore di supporto e H l’iperpiano separatore. Nel caso di R2
P=(x1,x2) e se H è una retta
d ( P, H )  d ( P, r ) 

w0  w1 x1  w2 x2
w12  w22
Generalizzando in Rn, se P(x,y) è un vettore di supporto con xRn avremo
d ( P, H ) 
13
w x  b
w12  w22  ...  wn2

w x  b
w2
Bioinformatica
SVM – Classificazione Lineare
d ( P, H ) 
w x  b
w12  w22  ...  wn2

w x  b
w2
1
se y  1
w2
1
se y  1
w2

Il segno + (-) indica che x giace sul lato positivo (negativo) dell’iperpiano;

Il problema di massimizzare il margine m
m2

1
w2
allora si riduce al problema di minimizzare la norma 2 del vettore dei pesi
W con la condizione
yi (w  xi  b)  1 i
14
Bioinformatica
SVM – Classificazione Lineare

Possiamo formulare la massimizzazione del margine come un problema di
ottimizzazione quadratica vincolata
2
min w,b 

w2
2
Con vincoli
yi (w  xi  b)  1 i

Metodo dei moltiplicatori di Lagrange
15
Bioinformatica
SVM – Classificazione Lineare

Potremo classificare una nuova tupla X mediante la funzione di
classificazione:

Dove

Gli i e b0 sono parametri legati a W e sono ottenuti col il metodo dei
moltiplicatori di Lagrange;

Se
allora X verrà classificata come C2;
Altrimenti sta in C1;

16
è un prodotto scalare riga per colonna;
Bioinformatica
SVM – Classificazione Non Lineare
17
Bioinformatica
SVM – Classificazione Non Lineare

Nello spazio di Rn non esiste un iperpiano in grado di separare le tuple di
classi diverse;

Soluzione «soft margin»: Si cerca l’iperpiano che divide i punti nel modo
più pulito possibile, introducendo delle costanti di scarto i per ogni tupla
ti.

Se H1 e H2 sono gli iperplani passanti per i vettori di supporto:
 i ha valore zero se la tupla ti sta nelle regioni esterne a H1 e H2 (cioè è
correttamente classificata);
 i avrà un valore maggiore di zero (corrispondente alla distanza di ti dal
vettore di supporto) se ti è classificata male (ovvero si trova nella
regione compresa tra gli iperpiani H1 e H2);
18
Bioinformatica
SVM – Classificazione Non Lineare

Potremo esprimere allora i vincoli
w  xi  b  1
w  xi  b  1
w  xi  b  1 - i
w  xi  b  1  i

quando yi  1
quando yi  1
quando yi  1
quando yi  1
O euqivalentemente
yi ( w  xi  b)  1  i
19
Bioinformatica
SVM – Classificazione Non Lineare

La funzione
F ( )    i
i
Diventa un limite superiore sul numero di errori possibili;

Assegnando un costo agli errori (e tenendo conto dei vincoli) la funzione
da minimizzare diverrà
Con c parametro (c elevato = alta penalità assegnata agli errori);
20
Bioinformatica
SVM – Classificazione Non Lineare

Un modo alternativo consiste nel proiettare il training set in uno spazio
dimensionale maggiore in cui sia possibile fare una classificazione lineare
21
Bioinformatica
SVM – Classificazione Non Lineare

Ad esempio un vettore tridimensionale X=(x1,x2,x3) può essere mappato in
uno spazio a 6 dimensioni utilizzando una funzione di mapping 

La tupla nel nuovo spazio sarà allora

La funzione di classificazione sarà allora trasformata in
22
Bioinformatica
SVM – Classificazione Non Lineare

Il mapping è però un’operazione molto complessa;

E’ possibile utilizzare invece le cosiddette «funzioni kernel»;

Se X è lo spazio dei dati originale e Z è quello dei dati mappati, una
funzione kernel K è tale che per ogni x,y
Cioè K restituisce il prodotto tra le immagini di x e y.

Con  funzione di mapping allora possiamo calcolare la funzione di
classificazione come
23
Bioinformatica
SVM – Classificazione Non Lineare

A ciò segue che, invece di applicare il mapping possiamo direttamente usare
una funzione kernel K (che deve soddisfare le proprietà del prodotto
scalare come commutativa, distributiva, etc etc);

Alcune tipiche funzioni Kernel:

Una funzione Kernel non lineare separerà (ad es. in R2) le tuple con delle
curve e non rette.
24
Bioinformatica
SVM – Applicazioni alla Bioinformatica

Una sequenza proteica può essere convertita in un punto 20-dimensionale
considerando la composizione aminoacidica (vettore di frequenze);

Predire la struttura secondaria e 3D di proteine;

Individuazione di omologie remote fra proteine;

Classificazione funzionale di geni e proteine;

Ricerca di pattern in sequenze biologiche;

Analisi di dati di espressione genica provenienti da microarrays;
25
Bioinformatica