Hierarchical Clustering

xS = arg min m X i2S xi m ². (2.18)

Quindi si pu`o ottenere C⇤ risolvendo il problema di ottimizzazione

min C,n mk oK 1 K X k=1 Nk X C(i)=k xi mk 2 , (2.19)

per esempio alternando le procedure date dall’Algoritmo 1. In pratica, ciascu-na delle fasi 1 e 2 riduce il valore del criterio (2.19) in modo tale da assicurare la convergenza, anche se il risultato pu`o rappresentare un minimo locale sub-ottimo.

In generale, si dovrebbe avviare l’algoritmo pi`u volte scegliendo diversi valori di

k e scegliere la soluzione che porta al valore pi`u piccolo della funzione obiettivo.

In Figura 2.13 viene mostrato un esempio di applicazione dell’algoritmo k-means clustering su dati simulati. Alla prima iterazione vengono individuati i centroidi dei cluster e si prosegue con il partizionamento dei dati; alle iterazioni successive si cerca di migliorare il partizionamento alternando i seguenti due passaggi:

- per ogni punto, viene identificato il centro cluster pi`u vicino (mediante

distanza Euclidea);

- ogni centro cluster viene rimpiazzato dalle coordinate della media di tutti i punti che si trovano al suo interno.

Quest’algoritmo, a di↵erenza di altre tipologie di clustering, adotta una procedura top-down, in quanto parte da un singolo cluster, che viene iterativamente diviso

in pi`u cluster, i quali, a loro volta, vengono migliorati in modo iterativo. Al

contrario, negli approcci bottom-up, si parte col considerare ogni elemento del dataset come un cluster a s´e stante e, ad ogni iterazione, si procede con l’accorpare due cluster in un unico cluster. Hiearchical clustering `e un algoritmo che pu`o essere eseguito scegliendo di adottare quest’ultima strategia.

Algorithm 1 K-means Clustering.

1. Per un dato cluster di assegnazione C, la varianza totale del cluster (2.19) `e

mi-nimizzata rispetto a m1, ..., mK producendo i means dei cluster attualmente

assegnati (2.18).

2. Dato un insieme corrente di medie m1, ..., mK , (2.19) `e miminizzata

as-segnando a ogni osservazione la media del cluster (corrente) pi`u vicino,

cio`e

C(i) = arg min

1kK

xi mk

2

. (2.20)

3. I passaggi 1 e 2 sono iterati finch´e gli assegnamenti non cambiano.

2.3.2 Hierarchical Clustering

L’algoritmo hierarchical clustering, o clustering gerarchico, a di↵erenza di K-means, non richiede di specificare a priori il numero di cluster che si vuole otte-nere. In questo caso, per`o, assume ruolo cruciale la metrica scelta per misurare

Figura 2.13: Esempio di applicazione dell’algoritmo k-means clustering sui dati rappresentati in Figura 2.12.

la dissimilarity tra gruppi disgiunti di osservazioni. L’algoritmo produce in usci-ta una rappresenusci-tazione gerarchica in cui i cluster di ogni livello possono essere creati unendo i cluster al livello inferiore. I nodi esterni di questa struttura ad albero rappresentano le singole osservazioni.

Si pu`o e↵ettuare clustering gerarchico seguendo due strategie:

- agglomerativa (bottom-up), che parte considerando ogni osservazione come un cluster a s´e stante e, ad ogni iterazione, raggruppa coppie di cluster in un unico cluster, in modo da formare gruppi a minima dissimilarity; - divisiva (top-down), che parte considerando l’insieme di tutte le osservazioni

come un unico cluster e divide ricorsivamente ogni livello di cluster in pi`u

cluster ; a ciacun livello, la divisione viene e↵ettuata in modo da creare due nuovi gruppi con massima dissimilarity.

Se N `e il numero di osservazioni, con entrambi gli approcci alla fine si produce

una struttura gerarchica ad N 1 livelli, che pu`o essere visualizzata sotto forma

di albero binario in cui:

- le foglie rappresentano le singole osservazioni; - i nodi intermedi rappresentano i raggruppamenti; - la radice rappresenta l’intero dataset.

L’albero binario pu`o essere raffigurato in modo tale che l’altezza di ogni no-do sia proporzionale al valore di dissimilarit`a tra i suoi due nodi figli, mentre i nodi terminali si trovano ad altezza zero. Il grafico che ne risulta, comunemente

Figura 2.14: Esempio di dendrogramma costruito mediante clustering gerarchico agglomerativo.

chiamato dendrogramma, fornisce una descrizione completa e facilmente interpre-tabile del risultato del clustering gerarchico e se ne pu`o osservare un esempio in Figura 2.14.

Un dendrogramma pu`o essere visto come una sintesi della struttura dei da-ti. Tuttavia questa interpretazione presenta dei limiti, perch´e diversi metodi di linkage dei dati possono generare dendrogrammi molto diversi. Inoltre, i metodi gerarchici impongono una struttura gerarchica anche se tale struttura non esiste realmente nei dati. Per questi motivi ha senso misurare la qualit`a di un dendro-gramma e a tal scopo si utilizza il coefficiente di correlazione cofenetica. Questo

coefficiente non `e altro che la misura della correlazione tra le N (N 1)/2 coppie

di dissimilarit`a delle osservazioni d_ii0 in input all’algoritmo e le loro

corrispon-denti dissimilarit`a cofenetiche C<sub>ii</sub>0 derivanti dal dendrogramma. La dissimilarit`a

cofenetica C_ii0 tra due osservazioni (i, i⁰) `e la dissimilarit`a alla quale le

osserva-zioni i e i⁰ sono per la prima volta uniti insieme nello stesso cluster. Il coefficiente

di correlazione cofenetica, in sintesi, misura quanto una struttura gerarchica in forma di dendrogramma rappresenta e↵ettivamente i dati.

In Figura 2.15 viene mostrato un esempio di dendrogramma plottato mediante la funzione dendrogram del Statistics and Machine Learning Toolbox di MATLAB.

Figura 2.15: Esempio di dendrogramma costruito mediante la funzione dendrogram del Statistics and Machine Learning Toolbox di MATLAB.

Capitolo 3

Descrizione dell’esperimento

In questo capitolo verr`a descritto il setup dell’esperimento e↵ettuato per va-lutare la capacit`a del calcolatore di riconoscere le equalizzazioni di pre-enfasi e post-enfasi applicate a documenti sonori di origine analogica, utilizzando tecniche di machine learning, o apprendimento automatico.

In particolare, si discuteranno:

- il workflow e gli strumenti utilizzati per la costruzione del dataset (Sezione 3.1);

- le strutture dati utilizzate per memorizzare i campioni audio digitali (Se-zione 3.2);

- le feature estratte dai dati che verranno utilizzate come input per gli algo-ritmi di cluster analysis e di fitting dei modelli predittivi (Sezione 3.3); - la struttura del codice per la cluster analysis (Sezione 3.4);

- la struttura del codice per la classificazione (Sezione 3.5).

3.1 Creazione del dataset

Il dataset per l’esperimento `e stato creato al Centro di Sonologia Compu-tazionale (CSC) dell’Universit`a degli Studi di Padova, in collaborazione con la Dott.ssa Valentina Burini e sotto la supervisione dell’Ing. Niccol`o Pretto e del Prof. Sergio Canazza.

Il procedimento seguito per la generazione dei campioni audio si pu`o riassumere nei seguenti passaggi:

1 generazione delle tracce audio;

2 registrazione delle tracce audio su nastro magnetico vergine;

3 riproduzione e digitalizzazione dei documenti sonori registrati al passo pre-cedente.

Figura 3.1: Modello di nastro magnetico utilizzato per l’esperimento.