Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Economia
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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


Il dendrogramma

Gli algoritmi forniscono una gerarchia di n-1 partizioni rappresentate dal dendrogramma.
L’importanza della lettura del dendrogramma è nella possibilità di suggerire il numero di classi effettivamente presenti nell’insieme osservato.
In corrispondenza di ciascun taglio si osserva una partizione di E ed un determinato numero di k.

Selezione della partizione

Selezione della partizione


Caso studio: il mercato delle “automobili”

Si considera il mercato delle “automobili” di diversa nazionalità. Quali descrittori utili per la classificazione si considerano le sole variabili numeriche: il Consumo, il Peso, il Rapporto di trasmissione, la Cilindrata, i Cavalli, etc.
L’applicazione di un metodo di Cluster Analysis gerarchica con il criterio di raggruppamento di Ward consente di individuare tre gruppi finali.


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 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 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.

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.

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.


Un approfondimento

Selezionando la partizione in quattro gruppi, consente di suddividere il terzo gruppo (19 automobili) in altri due gruppi.

Il nuovo terzo cluster (8 auto) deve essere contrapposto al secondo: infatti, ora è composto dalle auto di medie dimensioni fabbricate in USA. Il quarto (11 automobili) è composto dalle citycar.

Descrizione del Terzo e Quarto Cluster

Descrizione del Terzo e Quarto Cluster


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

L’algoritmo del metodo delle nubi dinamiche

  1. Definizione del numero delle classi e selezione delle unità rappresentative (nuclei di ciascuna classe)
  2. Calcolo delle distanze tra i nuclei e le unità attribuite al punto seme più vicino
  3. Definizione dei nuovi nuclei per ciascuna classe considerando le unità più vicine al centroide del gruppo
  4. Calcolo delle distanze tra i nuovi nuclei e le unità statistiche allocate ai gruppi più vicini
  5. Ripetizione dei passi 2:4 fino alla convergenza ad una soluzione stabile
Sequenza di formazione di 2 cluster attraverso il metodo delle nubi dinamiche

Sequenza di formazione di 2 cluster attraverso il metodo delle nubi dinamiche


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.

Strategia di analisi

Le variabili sono tutte discrete, di conseguenza sarà necessario sintetizzare queste variabili qualitative in variabili di sintesi quantitative attraverso l’Analisi delle Corrispondenze Multiple.
I primi 5 assi fattoriali raggiungono il 50% dell’informazione disponibile. Si possono utilizzare questi assi come descrittori per il metodo delle k-medie.

Si scelgono ovviamente k=2 cluster, perché sono due i partiti presenti nella Camera dei Rappresentanti.


I risultati

Il primo cluster è composto da 197 individui, il secondo da 238. L’inerzia spiegata è quasi pari al 40%.
Per capire in che modo sono stati strutturati i cluster, si inserisce come Target la nuova “variabile” Cluster_Kmeans_1 e come Input tutte le variabili originali (questa volta anche la variabile “class”), mentre gli assi non devono essere inseriti.
Confrontando i due cluster con i due partiti si può verificare che nel primo cluster si trova il 79% dei repubblicani, mentre nel secondo il 95% dei democratici. Ciò sta a dimostrare come la composizione dei due cluster sia molto vicina alla reale affiliazione politica dei membri della Camera.

Descrizione dei due Cluster con metodo non gerarchico.

Descrizione dei due Cluster con metodo non gerarchico.


I materiali di supporto della lezione

Zani, S., Cerioli, A., Analisi dei dati e data mining per le decisioni aziendali, Giuffrè Milano, ultima edizione.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion