Clustering: k-Mean 72

Un metodo di segmentazione alternativo a qu descritti è il clustering.

Il clustering è un

numero arbitrario di gruppi, i cui

Si tratta di una tecnica di analisi dei dati volta alla sel

raggruppamento di elementi omogenei in un insieme di dati. L’approccio è di tipo non supervisionato nel senso che il clustering riesce a suddividere i dati in una serie di insiemi avendo come unico input il numero di insiemi da trovare.

Gli algoritmi di clustering possono essere divisi nelle categorie:

Clustering esclusivo
Clustering non esclusivo

Figura 48: Inizzializzazione dello snake.

Figura 49: Risultato della segmentazione con snake.

3.3.3.3 Clustering: k-Mean

Un metodo di segmentazione alternativo a quelli precedentemente descritti è il clustering.

Il clustering è un processo di organizzazione di un set di oggetti in un numero arbitrario di gruppi, i cui membri sono simili per qualche aspetto Si tratta di una tecnica di analisi dei dati volta alla sel

raggruppamento di elementi omogenei in un insieme di dati. L’approccio è di tipo non supervisionato nel senso che il clustering riesce a suddividere i dati in una serie di insiemi avendo come unico input il numero di insiemi da trovare.

oritmi di clustering possono essere divisi nelle quattro

sclusivo non esclusivo

- 72 - elli precedentemente

organizzazione di un set di oggetti in un membri sono simili per qualche aspetto. Si tratta di una tecnica di analisi dei dati volta alla selezione e al raggruppamento di elementi omogenei in un insieme di dati. L’approccio è di tipo non supervisionato nel senso che il clustering riesce a suddividere i dati in una serie di insiemi avendo come unico input il

- 73 -
Clustering gerarchico

Clustering probabilistico

Nel primo caso i dati sono raggruppati in modo esclusivo, così se un certo dato appartiene ad un determinato cluster allora esso non potrà appartenere ad un altro cluster.

Il secondo tipo, a differenza del primo, usa delle regole fuzzy per raggruppare i dati, in modo tale che ogni dato può appartenere a due o più cluster con un differente grado di appartenenza.

Il cluster gerarchico, invece, si basa sulla fusione dei due cluster più “vicini” in modo iterativo. La condizione iniziale imposta, è quella di considerare ogni dato dell’insieme come un cluster. Dopo alcune iterazioni viene quindi raggiunto il raggruppamento desiderato.

Nel clustering probabilistico i dati sono modellati come delle distribuzioni probabilistiche, spesso gaussiane, centrate sui centroidi. I centroidi rappresentano un punto medio rappresentativo di un cluster. Quando i parametri di tali gaussiane non sono note l’algoritmo di clustering dovrà stimare oltre ai cluster anche i parametri delle singole distribuzioni, al fine di ottenere i parametri delle gaussiane che hanno la maggior probablilità di aver generato i dati osservati. Il procedimento da utilizzare per tali stime è detto Expectation Maximization (EM) ed è di tipo iterativo.

L’algoritmo di clustering utilizzato in questo lavoro è il clustering esclusivo, chiamato cosi poiché ogni dato può appartenere ad uno ed un solo cluster.

L’algoritmo di clustering esclusivo, detto anche k-means (Mac Queen, 1967) richiede la definizione di un numero di cluster noto a priori (k), in cui suddividere i dati, e di k centroidi, uno per ogni cluster da trovare, in modo casuale ma allo stesso tempo in modo che siano abbastanza lontani tra loro, per migliorare la convergenza dell’algoritmo. Per ogni dato si calcola la distanza dai centroidi e si associa il dato al centroide più vicino. A questo punto si ricalcolano i nuovi k centroidi come centro di massa dei cluster ottenuti al passo precedente e si ricalcola la distanza di tutti i dati dai nuovi centroidi creando cosi dei nuovi cluster. Iterando il procedimento, si arriva ad un punto in cui i centroidi si stabilizzano senza

- 74 - cambiare più la loro posizione. Si giunge quindi alla condizione di

convergenza dell’algoritmo che fornisce il clustering desiderato.

In modo formale, si definisce una funzione obiettivo da minimizzare. Questa funzione è la seguente:

» = ¼ ¼ ½_(¾)− 3¾½ 

¿ 

¾¿ (27)

dove: ½_?(Á)− @_Á½è la distanza tra il dato ›_Â(Ã) del cluster j e un centroide TÃ.

La funzione J cosi definita è un indicatore della distanza degli n dati dai centri dei rispettivi cluster.

L’algoritmo si articola nei seguenti passi:

1. si posizionano i K punti nello spazio degli oggetti che devono essere clusterizzati, tali punti rappresentano i centroidi dei gruppi iniziali

2. si assegna ogni oggetto al gruppo il cui centroide è più vicino all’oggetto stesso

3. quando tutti gli oggetti sono stati assegnati, si ricalcola la posizione dei

K centroidi

4. si ripetono i passi 2 e 3 fin quando i centroidi non si stabilizzano. La procedura descritta precedentemente converge sempre, ma non è detto che la condizione di convergenza sia quella che trova un minimo assoluto della funzione obiettivo. Poiché lo stato di convergenza dell’algoritmo dipende dalla definizione iniziale dei centroidi, che è casuale; è possibile ripetere il procedimento più volte e prendere tra le varie configurazioni stabili quella dove la funzione obiettivo è minima. In generale l’algoritmo presenta alcune difficoltà:

necessità di stimare il numero di cluster;

necessità inizializzare correttamente i centroidi poiché il risultato finale dipenderà anche da questi;

svuotamento di un cluster durante le iterazioni con conseguenza che il centroide non può essere più aggiornato nelle successive iterazioni. Nel caso delle immagini in esame i problemi precedentemente elencati sono facilmente superabili grazie al fatto che si conosce esattamente il

- 75 - numero di cluster, poiché è noto il numero di inserti e inoltre sono noti i

valori teorici di livelli di grigio dei materiali di cui sono costituiti gli inserti e del fantoccio per cui i centroidi in un primo momento sono stati inizializzati con tali valori.

La procedura di assegnazione dei pesi iniziali noti i valori teorici di livelli di grigio dei materiali di cui sono costituiti gli inserti, non è generalizzabile a tutte le immagini a causa delle variazioni di livello di grigio che si hanno al variare dei parametri di scansione, in particolare è stato notato che il numero CT diminuisce al all’aumentare dell’energia dei fotoni (cioè aumentando i kVp). Una alternativa è quella di assegnare i centroidi manualmente in base all’istogramma. Questo approccio non porta a risultati ripetibili della segmentazione, tuttavia ha il vantaggio estrarre dei pixel dagli inserti il cui centro di massa si osserva cadere approssimativamente al centro dello stesso. Tale centro può essere sfruttato per estrarre una ROI circolare posta all’interno dell’inserto e valutando la distribuzione dei pixel al suo interno in modo da calcolare il rapporto contrasto rumore (CNR).

(a) (b)

Figura 50: In (a) è mostrata una fetta da cui si vogliono estrarre delle ROI sugli inserti per il calcolo del CDR; in (b) è mostrato un ingrandimento del risultato.