Appunti Classificazione e interpretazione di dati biomedici

Classificazione 07.03.17

Il dato non fornisce informazione se non applico la conoscenza. Conoscenza e dati sono gli strumenti attraverso i quali si ottiene l'informazione che è l'elemento che serve per prendere una decisione. La conoscenza può essere nota da fonti (libri, internet) oppure la si può ottenere dall'insieme di dati attraverso al processo di apprendimento. Ad esempio, a una percezione di dolore può essere associato un numero, ma la percezione è soggettiva; il numero non illustra direttamente una misura.

Incertezza

Il concetto di misura ha sempre associato un certo livello di incertezza più o meno basso. Anche il giudizio ha una sua incertezza, a volte meno problematica dell'incertezza associata alla misura.

Validità del dato

Di solito le variabili hanno dei range di valori che sono accettabili e range di valori che sono chiaramente sbagliati. Sono errori che si possono identificare già dall'input. È più difficile quando l'errore è all'interno del range di validità.

Conoscenza dei dati

Modellizzazione di qualcosa che esiste e che deve essere rappresentato. Problema → concettualizzazione del problema → identificazione degli elementi che lo costituiscono → quali dati avrò a disposizione? I dati possono essere a disposizione perché li ho o devono essere ricavati oppure sono mancanti. Dopo la prima fase di analisi costruisco un modello per rappresentare il problema.

System Tuning

Si regolano i parametri per massimizzare le prestazioni del sistema che sto costruendo.

Verifica

Le prestazioni si verificano con il processo di verifica e validazione. Si va a vedere se il sistema si comporta come avevo definito le specifiche nel processo di analisi.

Validazione

Verifica rispetto a quello che dovrò fare, dati male interpretati nella fase di analisi. Se tutto va a buon fine ottengo il sistema.

Processo di costruzione

I dati sono l'elemento di riferimento. Abbiamo una serie di approcci e una serie di metodi. Molte delle decisioni sull'implementazione dei metodi dipendono dai dati. Con la statistica comprendiamo meglio i dati.

Statistica

2 approcci:

• Statistica descrittiva: descrive il set di dati.
• Statistica inferenziale: partendo dall'insieme di dati si cerca di dare caratteristiche non al campione ma all'intera popolazione.

Campionamento

Come si prendono gli elementi del campione dalla popolazione: si possono prendere in modo casuale, fare un campionamento di tipo sistematico (es: 1 ogni 5), dividere la popolazione in gruppi e prendere elementi dai gruppi, dividere in strati.

Misure di localizzazione

(formule vedi slides) Moda: valore con frequenza maggiore, ci possono essere più di una moda. Mediana: ottenuta ordinando i valori, se pari si prende la media dei valori centrali, se dispari si prende il valore centrale.

Misure di variabilità

• Varianza
• Deviazione standard
• Coefficiente di variazione
• Range

In molti casi è più interessante il range del valor medio che senza una varianza o deviazione standard associata dice poco.

Distribuzione delle frequenze

• Skewness e Kurtosis

Fanno riferimento alla distribuzione gaussiana, media, mediana e moda coincidono. È simmetrica rispetto al valor medio. La Skewness valuta il grado di simmetria quando ha una distribuzione simile alla gaussiana. Kurtosis: confronta la mia distribuzione con la gaussiana e dice se è più piatta rispetto alla normale di riferimento o ha un picco più pronunciato.

Classificazione 08.03.17

Caratteristica

Ogni elemento è rappresentato da un vettore di caratteristiche che derivano da dati anche di tipologia diversa. Alcuni metodi richiedono caratteristiche di un determinato tipo.

• Dati binari: assumono valore 0 o 1
• Dati categorici: assumono un numero definito di valori che può essere ordinato oppure no
• Dati interi
• Dati numerici
• Dati come serie temporali
• Immagini: bidimensionali
• Dati temporali
• Dati fuzzy

Il primo passo per costruire il sistema è individuare le caratteristiche che possono essere direttamente i dati. Con la feature extraction si estraggono le caratteristiche del dato. Possiamo estrarre un sottoinsieme delle caratteristiche utili al fine di implementare il metodo.

Feature extraction

Si identificano le caratteristiche che ci interessano. Le caratteristiche possono essere i dati o una loro elaborazione (es. elaborazione di segnali o immagini). Es: si estraggono caratteristiche per identificare diversi tessuti da un'immagine: intensità. Ogni quadretto è un pixel: l'intensità è la media di 4 pixel per ridurre la variabilità del singolo pixel. Su aree più grandi sono state ricavate le caratteristiche. Nel lume la deviazione standard di due rettangoli è simile, cosa che non succede in prossimità del bordo o quando i due rettangoli sono in verticale.

Dimensionality reduction

Quando si hanno tante variabili si cerca di ridurle. Esistono più metodi per la riduzione e si deve scegliere il più appropriato. Vogliamo ridurre la dimensionalità per ridurre la complessità computazionale togliendo le variabili non utili; vogliamo togliere le variabili che danno informazioni ridondanti (variabili altamente correlate tra loro).

Due approcci

1. Feature construction: costruisco altre features sulla base delle variabili a disposizione. Se riduco molto perdo il legame con il contesto perché perdo le variabili originali. I due metodi più usati sono PCA e LDA. Dobbiamo essere sicuri di avere sempre tutti i valori per tutte le variabili. Spesso non a tutte le variabili mancano gli stessi valori.
2. Feature selection: dal gruppo seleziono solo quelle di interesse. Non perdo variabili originali, più affidabile. Si seleziona un numero minimo di variabili che consentono di preservare le informazioni originali e le caratteristiche che permettono di comprendere i risultati. La rilevanza può essere forte (indispensabile) o debole (può essere tolta).

Se confronto due caratteristiche individualmente una di queste può essere irrilevante ma sull'insieme di tutte le variabili le conservo entrambe. Quindi inizialmente si parte con tutte le variabili anche se alcune sono correlate e poi si scarta solo se la correlazione è davvero molto alta.

Selezione features

• Ranking: si prendono le prime k tra quelle importanti. Col ranking si ha il problema si capire che valore dare a k.
• Si seleziona in base alle prestazioni che si ottengono dal sistema.
• Supervisionato: feature selection selezionata se siamo in grado di capire la correttezza delle prestazioni del sistema perché abbiamo un data set valido. Non supervisionato se dobbiamo solo dire se i dati sono accettabili o no.

La feature selection può anche migliorare le prestazioni del metodo. Ci sono varie misure per capire come si comporta il subset rispetto all'insieme di caratteristiche.

Valutare i risultati

Si possono confrontare le prestazioni prima e dopo la feature selection oppure confrontare diversi algoritmi.

Sviluppo

Modello: dobbiamo formalizzare una descrizione del problema. Sistema: è un set di elementi legati tra loro di differenti relazioni. Il sistema dipende dal problema e la rappresentazione del sistema dipende dal costruttore ed esistono più modelli validi.

System Modelling

Un modello molto usato è quello che si basa su equazioni matematiche, non partiamo dall'individuazione degli elementi tramite le descrizioni. Costruiamo una mappa in cui gli elementi sono nodi connessi tra loro.

Computational Intelligence

Contiene una serie di metodi di tipo diverso.

Classificazione 13.03.17

Ottimizzazione

L'ottimizzazione è l'insieme di soluzioni che possono essere realizzate (non sempre le soluzioni sono realizzabili) e di una funzione obiettivo. Vogliamo andare a cercare nello spazio delle soluzioni una soluzione che sia ottimale e per fare questo dobbiamo definire cosa per noi è ottimale. Usiamo la funzione obiettivo che associa ad ogni soluzione un valore che indica quanto è buona la nostra soluzione. Dobbiamo decidere come rappresentare le possibili soluzioni ed identificare la nostra funzione obiettivo. Possiamo andare ad ottimizzare andando a cercare un massimo o un minimo. Parliamo di minimizzazione perché tutti i problemi possano essere ricondotti a un problema di ottimizzazione.

Normalmente abbiamo delle funzioni non lineari. Se avessimo una funzione lineare, sappiamo che essa ha un solo ottimo ed è facilmente individuabile. Se la funzione è non lineare sappiamo che la funzione ha più ottimi, alcuni dei quali sono ottimi locali e altri sono ottimi globali. Il problema delle funzioni non lineari è che non abbiamo una sola variabile e non abbiamo la possibilità di disegnarla. Un algoritmo che permette di provare l'ottimo è un algoritmo che richiede grosse risorse in termini di tempo computazionale e di memoria utilizzata per andarne a memorizzare tutti i dati che servono, è un algoritmo di tipo iterativo e il tempo è legato al numero di iterazioni che usiamo per risolvere il problema. Solitamente consideriamo il caso peggiore.

Possiamo avere una ottimizzazione non vincolata oppure una ottimizzazione vincolata dove le nostre soluzioni devono soddisfare dei vincoli che possono essere uguaglianze, disuguaglianze, legati ad alcune o tutte le variabili. Una soluzione ammissibile è una soluzione che soddisfa i vincoli che noi imponiamo.

Esempio di ottimizzazione

Supponiamo che una regione in ambito sanitario decida di identificare un certo numero di centri per i pazienti cronici con una certa patologia (dialisi). La regione vuole garantire un livello qualitativo della cura e vuole garantire che i centri siano equamente raggiungibili da tutti i cittadini, distribuire i centri in modo ottimale. La raggiungibilità è legata alle vie di collegamento (strade, treni, ecc.) e alla numerosità dei cittadini. Non possiamo semplicemente minimizzare il tempo di collegamento tra il nostro centro e la città ma dobbiamo pesare il tempo con il numero potenziale di persone che dovrebbero spostarsi. Si può andare ad identificare la numerosità della patologia per ogni centro abitato e usare quello come peso oppure possiamo usare semplicemente la numerosità degli abitanti dei centri di ogni città. Nel nostro caso la funzione è pesata dal numero di abitanti e dalla distanza. Per ogni centro potenziale prendo la distanza minima. Il vincolo è che sia uguale a 5. Quando i vincoli sono di uguaglianza spesso sono i più difficili da soddisfare. In questo caso abbiamo 120 locazioni e diciamo che il valore della variabile della locazione vale 1 se vogliamo mettere in quella locazione il centro e 0 in caso contrario (yes no variable). Si è tenuto conto della densità della popolazione, dei centri ospedalieri e delle strade.

Metodi di ottimizzazione

Se vogliamo ragionare di metodi che permettono di risolvere problemi di ottimizzazione essi sono suddivisi in sottoinsiemi. Metodi di ottimizzazione → ricerca locale Euristica. I metodi di ottimizzazione sono di tipo iterativo, partono da una o più soluzioni per cercare di trovare almeno un ottimo locale e potenzialmente l'ottimo globale. Alcuni di questi metodi sono strettamente dipendenti dalle soluzioni di partenza e questo è uno svantaggio.

Ricerca locale

La ricerca locale decide di volta in volta quale soluzione è candidata ad essere l'ottimo delle informazioni locali. Spesso il numero di soluzioni che noi dobbiamo esaminare è molto grande quindi non possiamo esaminarle tutte sempre.

Euristica

L'euristica permette di trovare una soluzione usando delle tecniche che da un lato riducono il tempo computazionale e dall'altra il risultato ottenuto è meno soddisfacente. Spesso si usa un metodo euristico per trovare una buona soluzione di partenza e poi un altro metodo che migliori questa soluzione di partenza.

Nell'euristica si ha il sottoinsieme delle metaheuristic che permettono di trovare delle buone soluzioni in tempi sufficientemente brevi.

Ricerca operativa

Ha una serie di problemi che ha badge mark usati per valutare quanto sono buone le soluzioni del metodo.

Le metaheuristic hanno alcune caratteristiche: molte volte sono ispirati da fenomeni naturali. Ci sono metodi che hanno memoria, quindi procedendo con le iterazioni si mantiene traccia dei risultati ottenuti e altri che sono memory less e che ad ogni iterazione usano solo l'informazione locale di quella iterazione.

Metodi deterministici: dando una soluzione iniziale si basa su delle regole di tipo deterministico, partendo da una soluzione ottengo sempre la stessa soluzione finale.

Metodo stocastico: basa le sue soluzioni su probabilità, possono avere soluzioni finali diverse a partire dalla stessa iniziale. In questo caso si ripete più volte il metodo per verificare quanto è ripetibile la soluzione che si ottiene come risultato.

Metodi che si basano su una singola soluzione o su una popolazione: ad ogni iterazione faccio evolvere una sola soluzione o una popolazione di soluzioni. Con la popolazione posso razionare come se stessi procedendo in parallelo su tante singole soluzioni.

Metodi greedy: mentre gli iterativi partono da una soluzione e la soluzione è un vettore che ha un valore per ognuno delle variabili ad ogni iterazione. I Greedy partono da una soluzione vuota o una variabile e man mano aggiungono i valori delle variabili che potenzialmente danno una soluzione migliore.

Metaheuristics

La prima cosa importante è definire meglio cosa intendiamo per local search: DA ESAME: Il vicinato è un insieme di soluzioni raggiungibili dalla soluzione corrente. Un insieme di soluzioni vicine alla soluzione attuale con una certa misura che possiamo ottenere, è l'insieme di tutte le soluzioni raggiungibili dalla soluzione corrente attraverso una operazione elementare (es: somma, sottrazione).

Prendiamo un problema reale, lo rappresentiamo matematicamente e costruendo il modello si fanno delle semplificazioni; in questo modo, facendo semplificazioni la soluzione che trovo è l'ottimo del modello, tanto più la funzione è rappresentativa della funzione del sistema reale tanto più l'ottimo della funzione modello è l'ottimo del problema; ma può capitare che l'ottimo del modello non sia l'ottimo del problema. Si deve capire quanto la semplificazione è ammissibile quando vado ad implementare la soluzione. In alcuni casi devo usare modelli non matematici per trovare una soluzione più vicina al problema reale. La scelta del modello è importante e ad essa segue il metodo per cercare l'ottimo. Andare a cercare una soluzione sufficientemente buona è più che sufficiente per me perché potrei avere paradossalmente una soluzione migliore per il modello ma peggiore dal punto di vista del problema. Devo capire quanto la soluzione trovata è buona dal punto di vista del problema. Possiamo avere dei problemi che si risolvono una tantum oppure ci sono problemi che si ripetono per cui devo creare un modello che vada bene in modo iterativo (più complicato).

RICERCA LOCALE: DOMANDA DA ESAME

1. Inizializzazione: si cerca una soluzione ammissibile e si calcola la funzione obiettivo per quella soluzione.
2. Generazione vicinato: si ottiene con una soluzione semplice dalla soluzione iniziale e devo arrivare ad avere un certo numero si soluzione.
3. Test accettabilità: non sempre seleziono la soluzione migliore del vicinato. Seleziono una soluzione del vicinato o un insieme di soluzione del vicinato e ho delle regole per selezionare e accettare quella soluzione. Non sempre la soluzione che vado a scegliere è la migliore, se scegliessi sempre la migliore avrei un metodo deterministico che mi porterebbe sempre alla stessa soluzione. La soluzione se l'accetto diventa la soluzione corrente altrimenti procedo fino a trovare la soluzione accettabile.
4. Termination test: devo avere un test di terminazione che mi dica se fermare l'algoritmo.

Il vicinato è un insieme di soluzioni che si trovano sulla funzione in un certo intorno della soluzione di partenza (slide). Parto dalla soluzione X1 vedo il vicinato, selezioni X2, genero il vicinato fino ad arrivare in questo modo a Xn. Le soluzioni che ho a disposizione dipendono dalle dimensioni dell'intorno, l'intorno mi permette di andare nelle due direzioni.

Metodo del gradiente

Metodo che più risente della soluzione iniziale, si seleziona sempre il migliore dell'intorno passando da una soluzione all'altra scegliendo sempre la soluzione migliore. In questo modo si arriva sempre allo stesso ottimo.

Metodo simulated annealing

Ha come diversità dalla regola del gradiente la regola di accettabilità, estrae casualmente una soluzione dell'intorno, se è migliore l'accetta e se è peggiorativa l'accetta secondo una certa probabilità. Non sappiamo se finiamo in un ottimo locale o globale.

Uphill moves

Mosse che permettono di scollinare. Permette di implementare una soluzione che mi fa scollinare e arrivare all'ottimo globale accettando anche dei peggioramenti. Si ispira al raffreddamento dei metalli, la possibilità di accettare i peggioramenti come col raffreddamento gli ioni si fissano in una posizione, man mano che vado avanti riduco la probabilità di accettare peggioramenti fino ad arrivare ad accettare la soluzione solo se è migliorativa.

Parametri del metodo

S0 = soluzione iniziale T = inizializzato a Tmax, il valore di questo parametro viene diminuito durante le iterazioni ed è il parametro che man mano diminuisce la probabilità di accettare un peggioramento. Ripetiamo per un certo numero di volte queste operazioni: generiamo in modo random una soluzione del vicinato. Calcolo ΔE come il valore della soluzione attuale.