Introduzione

La cluster analysis (analisi di raggruppamento o dei gruppi) è uno strumento molto popolare per analizzare dati multivariati non strutturati. La metodica è composta di diversi algoritmi, ciascuno dei quali cerca di organizzare un dataset in sottogruppi omogenei, o “cluster”. Non c’è garanzia che si trovi più di un gruppo. Tuttavia, l’ipotesi fondamentale è che i dati formino un insieme eterogeneo che dovrebbe suddividersi in gruppi naturali, familiari agli esperti dell’area analizzata.

Il clustering si differenzia dalla classificazione (si veda il relativo capitolo) per:

  1. nella classificazione è noto a priori il numero di classi o gruppi presenti nei dati e quali item sono membri di quale classe o gruppo; nell’analisi dei cluster, il numero di classi è usualmente sconosciuto, così come l’appartenenza degli item alle classi;

  2. nella classificazione, l’obiettivo è classificare nuovi item in una delle classi date; il clustering ricade più all’interno del framework dell’analisi esplorativa dei dati, quando non si hanno informazioni a priori sulla struttura in classi dei dati.

I metodi per raggruppare gli item (che siano osservazioni o variabili) si basano sulla somiglianza (o dissomiglianza) degli item tra loro. Gli item simili sono quindi trattati come classe o gruppo omogeneo. Gran parte dell’output di una analisi dei cluster è visiva, con i risultati visualizzati usando scatterplot, alberi, dendrogrammi, grafici a silhouette, ed altri strumenti grafici.

Gli algoritmi di clustering (o di partizionamento) sono usualmente suddivisi tra approcci gerarchici e non gerarchici; gli algoritmi gerarchici sono a loro volta suddivisi tra metodi agglomerativi e divisivi. I metodi gerarchici operano aggregando (o separando) tutti gli item sequenzialmente. I metodi agglomerativi iniziano con ciascun item che compone il suo proprio cluster; in seguito, vengono aggregati un successione i cluster più “simili”, fino ad ottenere un unico cluster. Gli algoritmi di clustering divisivi operano in maniera opposta: iniziano con tutti gli item che appartengono ad un unico cluster; dividono quindi questo cluster in due cluster separati “internamente omogenei”, e via di seguito; al termine della procedura ciascun item formerà il “suo” cluster.

In questo manuale presenterò per ora solo esempi sui metodi gerarchici agglomerativi e non gerarchici, applicati a dati di tipo numerico.

In questa parte del corso vedremo quindi:

  1. Algoritmi di Clustering Gerarchico (Agglomerativo) (HC);
  2. Algoritmi di Clustering Non-Gerarchici (K-Means) (NHC);
  3. Una breve introduzione ai modelli Mistura Gaussiani (GMM), che possono essere visti come una alternativa model-based ai metodi di clustering puri, ma con obiettivi simili.
  4. Algoritmo DBSCAM: algoritmo density-based, ma non parametrico (non applica assunti distributivi);
  5. Algoritmo di Affinity Propagation (AFPROP): può (a grandi linee) essere visto come una versione di clustering gerarchico, ma ben più sofisticato e, spesso, efficace.