Roberta Siciliano » 15.Cluster Analysis

Obiettivi e contenuti

Obiettivo
Introduzione all’analisi dei gruppi (cluster analysis) per l’analisi multivariata dei dati.
Comprendere la base metodologica per l’applicazione dei metodi gerarchici e non gerarchici.

Contenuti

Obiettivo della Cluster Analysis
Distinzione tra metodi gerarchici e non gerarchici
Criteri gerarchici di raggruppamento
Misure di distanza e passaggio all’ultrametrica
Aspetti metodologici della Cluster gerarchica
Algoritmo gerarchico
Metodi di raggruppamento
Il Dendrogramma
Caso studio: il mercato delle “automobili”
Strategia di analisiAspetti metodologici della cluster non gerarchica
Metodo delle Nubi Dinamiche
Metodo delle k-medie
Caso studio: il congresso americano

Obiettivo della Cluster Analysis

L’obiettivo della Cluster Analysis (CA) è la ricerca della partizione di un collettivo E di n unità statistiche in K (con K < n e intero) sottoinsiemi (gruppi o cluster) tali che le unità appartenenti ad uno stesso sottoinsieme siano il più possibile omogenei tra loro rispetto alle misurazioni di un insieme di variabili.

Gli ambiti di applicazione sono molteplici, come, per esempio:

• Segmentazione di mercato (riferita ad esempio a tipi di prodotto, a tipi di consumatori, etc.)
• Classificazione dei comuni di una regione in gruppi omogenei in base a pluralità di indicatori demografici, economici, sociali

A differenza dei metodi di segmentazione binaria (classificazione supervisionata) nei metodi di cluster analysis (classificazione non supervisionata) non vi è una variabile target che gioca il ruolo di variabile dipendente da spiegare in funzione di un insieme di predittori, per cui il criterio di omogeneità interna ai gruppi va ottimizzato rispetto a tutte le variabili misurate sugli individui del collettivo, ovvero gli individui all’interno di un gruppo sono simili nelle misurazioni osservate di tutte le variabili e non di una in particolare.

Distinzione tra metodi gerarchici e non gerarchici

Metodi gerarchici
Obiettivo: Prevedono l’individuazione di n partizioni ciascuna caratterizzata da un diverso numero k di gruppi (k = 1,….,n); le partizioni individuate costituiscono una struttura gerarchica di raggruppamento.

Risultato: Consentono di ottenere una famiglia di partizioni con numero di gruppi da n a 1, partendo da quella banale con numero di gruppi pari a n per giungere a quella, anch’essa banale, in cui tutti gli elementi sono riuniti in un unico gruppo.

Metodi non gerarchici
Obiettivo: Prevedono l’individuazione di una sola partizione delle unità in k gruppi, dove k è fissato a-priori o derivare dal processo di raggruppamento stesso.

Risultato: Forniscono un’unica partizione delle n unità in k gruppi.

Criteri gerarchici di raggruppamento

Le possibili partizioni

Misura di distanza e passaggio all’ultrametrica

Un indice d(x,y) che misuri la “dissimilarità” tra due unità statistiche rispetto alle misurazioni di p variabili, rispettivamente x e y, soddisfa le seguenti proprietà:

• Separabilità, nel senso che se d(x,y)=0 si ha che x=y
• Simmetria, ne senso che d(x,y)=d(y,x)

Le misure di dissimilarità sono utilizzate in presenza di variabili dicotomiche e di variabili qualitative.

Tale indice sarà anche una misura di “distanza” metrica se soddisfa anche la diseguaglianza triangolare, rispetto ad una terza unità statistica le cui misurazioni sono z:

• d(x,y) minore o uguale d(x,z) + d(z,y)

Misura di distanza e passaggio all’ultrametrica (segue)

Un esempio di distanza metrica è la distanza euclidea.

Lo spazio con riferimento al quale si sia definita una distanza è detto spazio metrico.

L’indice di distanza si dirà ultrametrica se inoltre soddisfa anche la seguente diseguaglianza di Krassner:

• D(x,y) minore o uguale sup [d(x,z),d(z,y)]

Le distanze ultrametriche che caratterizzano ciascuna terna di punti sono date dal triangolo isoscele la cui base è data dalla distanza dei punti più vicini tra loro. Il lato del triangolo isoscele è rappresentato da una delle altre due distanze, quella più grande (ultrametrica superiore minima), quella più piccola (ultrametrica inferiore massima).

Aspetti metodologici della Cluster gerarchica

In un metodo di partizione gerarchica:

• si considerano tutti i livelli di distanza tra coppie di unità statistiche o tra coppie di gruppi di unità
• i gruppi che si ottengono ad un certo livello della partizione comprendono i gruppi ottenuti ad un livello inferiore
• quando due o più unità si uniscono (o si dividono) non possono più essere divise (o unite) nei passi successivi

Le gerarchie possono essere rappresentate mediante dendrogrammi che si compongono di radici (le classi terminali) e di nodi (le classi non terminali) e di rami (le linee che congiungo le classi).

Il dendrogramma viene rappresentato sotto forma di gerarchia indicizzata in un diagramma cartesiano dove sull’asse delle ordinate vengono indicati i livelli di similarità o di diversità rispetto ai quali due gruppi si fondono per dar luogo ad un nuovo gruppo

Algoritmo gerarchico

Con impiego iniziale di una matrice delle distanze (o di una matrice di indici di dissimilarità) D:
1. Si individuano in D le due unità con minor distanza (più simili) e si riuniscono a formare il primo gruppo
2. Si ricalcola la distanza del gruppo ottenuto dagli altri gruppi ricavando una nuova matrice delle distanze D1 con dimensioni diminuite di uno
3. Si individua in D1 la coppia di unità (o gruppi) con minore distanza e la si riunisce
4. Si ripetono le fasi 2 e 3 fino a che tutte le unità si riuniscono in un unico gruppo

Metodi di raggruppamento

• Metodo del legame singolo (single linkage) o del vicino più prossimo (nearest neighbour)

La distanza tra due gruppi è definita come il minimo delle distanze tra ciascuna delle unità di un gruppo e ciascuna delle unità dell’altro gruppo.

• Metodo del legame completo (complete linkage) o del vicino più lontano (furthest neighbour)

La distanza tra due gruppi è definita come il massimo delle distanze tra ciascuna delle unità di un gruppo e ciascuna delle unità dell’altro gruppo.

• Metodo del legame medio (average linkage) tra i gruppi

La distanza tra due gruppi è definita come la media aritmetica delle distanze tra ciascuna delle unità di un gruppo e ciascuna delle unità dell’altro gruppo.

Metodi di raggruppamento (segue)

• Metodo del centroide

La distanza tra due gruppi è definita come la distanza tra i rispettivi “centroidi” o centri del gruppo di unità.

• Metodo di Ward, o della devianza minima

Considera la decomposizione della Devianza Totale delle p variabili in Devianza Between e Devianza Within. Ad ogni passo della procedura gerarchica si aggregano tra di loro i gruppi che comportano il minor incremento della Devianza Within, cioè che assicurano la maggior coesione interna possibile.

I passi dell’algoritmo gerarchico

La descrizione dei cluster

Il primo cluster (11 auto) è formato dai veicoli di grandi dimensioni. Essi sono pesanti, potenti, consumano molto e sono, soprattutto, auto statunitensi.

Il secondo cluster (8 auto) è formato dai veicoli di medie dimensioni. Essi sono mediamente potenti, sono caratterizzate da un'elevata manovrabilità e sono auto europee.

Il terzo cluster (19 veicoli) è formato dai veicoli di piccole dimensioni. Essi sono caratterizzati da bassi consumi, potenza non alta e basso peso.

Strategia di analisi

Dall'applicazione di un metodo fattoriale sugli stessi dati è possibile evincere dalla mappa fattoriale (che spiega il 90% della variabilità) la struttura in tre gruppi del collettivo.

Aspetti metodologici delle cluster non gerarchica

Richiede la determinazione a priori del numero di classi che definiscono la partizione.

L’algoritmo è convergente e il numero di iterazioni richieste è generalmente limitato: ciò rende questo metodo applicabile anche a grossi insiemi di dati.

La soluzione ottenuta non rappresenta la soluzione ottimale ma solo una delle tante possibili, ottenuta avendo determinato a priori quel numero di classi e avendo scelto quelle unità iniziali.
Principali metodi:

• Metodo delle nubi dinamiche (Forgy, 1965)
• Metodo delle k-medie (k-means, Mac Queen, 1967)

Metodo delle nubi dinamiche

Perviene ad una partizione del collettivo E di unità statistiche attraverso un procedimento iterativo che, a partire da una soluzione iniziale arbitraria, la “migliora” fino a pervenire a quella “ottima”, definita tale in base ad un determinato criterio.

L’algoritmo richiede generalmente poche iterazioni e consente il trattamento di grossi insiemi di dati ma:

• Il numero delle classi deve essere fissato a priori
• La soluzione dipende dalle assegnazioni (nuclei) iniziali
• Non esiste un unico criterio ottimale, per cui la partizione ottimale è una tra le tante possibili partizioni

Metodo delle k-medie

Si assumono come nuclei i primi K individui, si allocano via via le n-K unità e ad ogni assegnazione si calcola subito il centroide del gruppo che si è modificato: in tal modo si accelera il miglioramento della classificazione.

Al termine di questa prima assegnazione si riparte dai centroidi così calcolati e si riassegnano le unità via via al gruppo più vicino.

Regola di stop: come per il metodo delle nubi dinamiche.

Punti di debolezza del metodo delle k-medie

Spesso termina su un ottimo locale. L’ottimo globale può essere trovato usando tecniche alternative (deterministic annealing e genetic algorithm).

Può essere applicato solo quando il tipo di dato permette di definire la media (che serve per determinare i centroidi del cluster) →Problemi con dati categorici.

Bisogna specificare in anticipo k, il numero di cluster.

Caso studio: il congresso americano

Come caso studio per la cluster non gerarchica si prende in considerazione il dataset “vote”, che analizza attraverso il voto dei rappresentati della Camera dei Rappresentanti l’appartenenza ad uno schieramento o all’altro.
Il dataset, anche se non molto recente, ci permette di elaborare 17 votazioni dei membri (435 individui) del congresso americano.
La variabile “class” indica l’appartenenza o al partito democratico o a quello repubblicano e non entrerà a far parte dell’analisi, ma la si utilizzerà per confrontare il risultato finale della cluster analysis.