Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D La Corte in Rete
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Massimo Aria » 12.Cluster Analysis non Gerarchica


Metodi non gerarchici

I metodi non gerarchici sono caratterizzati da un procedimento che mira a ripartire direttamente le n unità in G grappoli (o gruppi), fornendo come prodotto finale una sola partizione delle n osservazioni.
Ciò avviene attraverso una procedura iterativa che permette di ottenere, quale risultato finale, un’unica partizione (mentre nei metodi gerarchici si ottiene una gerarchia innestata di partizioni).

Il costo computazionale della procedura

L’individuazione della partizione ottimale comporterebbe a rigore l’esame di tutte le possibili assegnazioni distinte degli n individui a G gruppi.

Immaginando, ad esempio, una partizione formata da due gruppi (G=2), il numero P di possibili potenziali soluzioni è pari a 2^{n-1}-1 , dove n rappresenta il numero di osservazioni da classificare.

Es. n=4 → {A, B, C, D}, G=2 e P=2^{4-1}-1 = 7

Le P=7 potenziali partizione ottenute dalle quattro osservazioni sono:
(A)(B,C,D)….. (B)(A,C,D)….. (C)(A,B,D)….. (D)(A,B,C)….. (A,B)(C,D)….. (A,C)(B,D) …..(A,D)(B,C)

Per dare un idea del costo computazionale richiesto dalla ricerca della migliore partizione con G=2:
Con
n=4 → P=7
n=10 → P=511
n=1000 →P=10^{29} - 1

Come risulta evidente dall’esempio, una ricerca esaustiva della migliore partizione determina una enorme mole di calcoli che, anche per numerosità ridotte, rende inutilizzabile la tecnica per qualunque applicazione pratica.

Scelte iniziali nel metodo non gerarchico

Per risolvere il problema legato all’elevato costo computazionale, le procedure non gerarchiche adottano una strategia di raggruppamento che richiede la valutazione solo di un numero accettabile di possibili partizioni alternative. Ciò avviene rinunciando alla ricerca dell’ottimo in assoluto in favore di una soluzione soddisfacente rispetto al numero di ricerche che la procedura è in grado di effettuare.

Tale compromesso si ottiene fissando a priori il punto di partenza della procedura in termini di:

  • numero dei gruppi da considerare (G);
  • valori dei centri iniziali dei G gruppi da cui partire nel processo di aggregazione.

La logica del metodo non gerarchico

Sulla base delle scelte iniziali, l’algoritmo partiziona le unità in un numero predefinito di gruppi basandosi sulla ottimizzazione di un criterio (es. massimizzazione dell’omogeneità all’interno dei gruppi).
L’inizializzazione dell’algoritmo avviene indicando G centri di partenza intorno a cui aggregare le unità.
A differenza dei metodi gerarchici, l’assegnazione di un oggetto ad un cluster non e’ irrevocabile. Ovvero le unità vengono riassegnate ad un diverso cluster se l’allocazione iniziale risulta inappropriata.

Anche in questo caso esistono diversi algoritmi.
Differiscono tra loro nei seguenti aspetti:

  1. come sono inizializzati i centri di partenza;
  2. come gli elementi vengono assegnati ai diversi centri;
  3. come alcune o tutte le unità vengono eventualmente riassegnate ad un diverso gruppo.

Di solito, scelta una partizione iniziale, si cerca di migliorarla in funzione del criterio di minimizzazione della varianza (o più in generale “diversità”) interna.

Fasi del raggruppamento non gerarchico

Le procedure non gerarchiche si articolano sostanzialmente nelle seguenti fasi:

PASSO 0 – L’inizializzazione
Si scelgono G “centri provvisori”, i quali inducono una prima partizione temporanea.
Tale aggregazione avviene sulla base della minima distanza di un’unità da uno di questi centri.
L’unità A apparterrà al primo gruppo se la distanza tra A e il centro del primo gruppo sarà inferiore a quella tra A e qualunque altro centro dei restanti gruppi.

PASSO 1 – Determinazione dei nuovi centri
Si calcolano i baricentri dei gruppi ottenuti attraverso il processo di aggregazione del passo precedente.
Si assumono i baricentri appena calcolati come nuovi “centri provvisori”.

PASSO 2 – Individuazione della nuova partizione
Si ripete il procedimento di allocazione delle unità ai centri sulla base della minima distanza.
Si itera la partizione tornando al passo 1.

STOP – Arresto della procedura
Se tra un passo e il successivo non vi sono riallocazioni dei punti tra un gruppo e un altro, la procedura si arresta in quanto la partizione ottenuta può ritenersi soddisfacente.

I passi dell’algoritmo : un esempio grafico


Algoritmi di raggruppamento gerarchico

In letteratura sono stati proposti diversi algoritmi che differiscono tra loro nei seguenti aspetti:

  1. come sono inizializzati i centri di partenza;
  2. come gli elementi vengono assegnati ai diversi centri;
  3. come alcune o tutte le unità vengono eventualmente riassegnate ad un diverso gruppo.

Il metodo delle k-medie costituisce, seppur con alcune varianti, l’algoritmo di classificazione non gerarchico di uso più comune ed è implementato nei principali software di analisi statistica.

Metodo delle k-medie

Il metodo delle K-medie (proposto da McQueen) rappresenta l’algoritmo più diffuso per la definizione di raggruppamenti di tipo non gerarchico.
L’algoritmo segue i passi generali di una procedura non gerarchica con alcune varianti che consentono di raggiungere più velocemente la soluzione ottimale.

Passo 0 – Inizializzazione
Si scelgono G punti iniziali che fungono da centri provvisori (la scelta può essere causale o guidata da un criterio empirico). Si costruisce la partizione iniziale assegnando ogni punto al gruppo il cui centro risulta più vicino.

PASSO 1 – Determinazione dei nuovi centri
Si calcolano i baricentri dei gruppi ottenuti attraverso il processo di aggregazione del passo precedente. Si assumono i baricentri appena calcolati come nuovi “centri provvisori“.

PASSO 2 – Individuazione della nuova partizione
Si ripete il procedimento di allocazione delle unità ai centri sulla base della minima distanza. Ad ogni assegnazione di un nuovo punto a un nuovo gruppo, si procederà alla rideterminazione del baricentro del nuovo e del vecchio gruppo. Si itera la partizione tornando al passo 1.

STOP – Arresto della procedura
Se tra un passo e il successivo non vi sono riallocazioni dei punti tra un gruppo e un altro, la procedura si arresta in quanto la partizione ottenuta può ritenersi soddisfacente.

Alcune osservazioni sul metodo delle k-medie

L’algoritmo delle k-medie si distingue dalla procedura generica di raggruppamento non gerarchico in un elemento chiave.

Nella procedura classica, al passo 2 i centri sono ricalcolati solo al termine della fase di aggregazione di tutti i punti ai diversi gruppi.
Nelle k-medie, invece ogni volta che un punto viene assegnato ad un gruppo , il baricentro di questo gruppo viene immediatamente ricalcolato (così come quello del gruppo dove il punto apparteneva in precedenza). Ciò implica un “assestamento” dei centri che avviene ad ogni singola assegnazione e non al termine di ogni passo della procedura (si veda la figura a lato).

In questo modo si garantisce un raggiungimento della convergenza dell’algoritmo più rapido (cioè con un minor numero di iterazioni) rispetto alle soluzioni classiche.

Aggregazione con il metodo delle k-medie.

Aggregazione con il metodo delle k-medie.


Alcune osservazioni sul metodo delle k-medie(segue)

La procedura iterativa su cui si fonda l’algoritmo delle k-medie presenta alcuni potenziali problemi.
In particolare i risultati dell’analisi possono dipendere da:

  • la scelta dei centri iniziali. La scelta dei centri iniziali rappresenta il punto di partenza da cui prende avvio la ricerca di una partizione finale che possa essere considerata una soluzione soddisfacente. L’approccio più banale si basa sulla scelta di G punti in maniera completamente casuale. Ovviamente tale modo di procedere rende fortemente instabile la procedura (che se eseguita più volte fornirà risultati spesso differenti). Un modo alternativo consiste nel generare, per ognuno dei G gruppi, L punti casuali il cui baricentro rappresenterà il centro provvisorio iniziale del gruppo oppure in alternativa quello di eseguire più volte l’analisi e considerare come partizione finale dei dati la “partizione media” ottenuta aggregando le singole soluzioni.
  • la scelta del numero dei gruppi. In merito al numero di gruppi G, se questa informazione non è nota a priori sulla base delle informazioni possedute sulla popolazione, allora si potrà eseguire più volte la procedura facendo variare G (con G=2, 3, …) e scegliendo poi il valore di G che consente di avere la migliore partizione (in termini di massima eterogeneità tra i gruppi o minima omogeneità interna ai gruppi).
  • l’ordine in cui le osservazioni sono riportate nella matrice dei dati. Infine per ridurre il problema legato all’ordine delle osservazioni, si può condurre una analisi con l’approccio classico in cui i centri vengono ricalcolati solo alla fine del processo di aggregazione e non punto dopo punto (Metodo dei centri mobili).

Confronto tra cluster gerarchica e non gerarchica

La scelta dell’algoritmo delle K-medie piuttosto che di uno di classificazione gerarchica risiede, oltre che nella possibilità di scegliere a priori il numero di cluster da ottenere, principalmente nel risparmio computazionale che si ottiene utilizzando il primo metodo piuttosto che il secondo. Ciò è vero quando le unità da classificare sono numerose.

Infatti ad ogni iterazione:

  • la cluster gerarchica compie n*(n-1)/2 calcoli, dove n rappresenta il numero di oggetti da raggruppare (unità o gruppi di unità) ad ogni iterazione;
  • la cluster non gerarchica compie n*G calcoli.

Inoltre il numero di iterazioni del secondo metodo è sempre molto più ridotto rispetto a quello di una cluster gerarchica.

Nella tabella a lato si riporta un esempio numerico di comparazione tra il costo computazionale delle due tecniche.
NB. Il numero delle iterazione è supposto uguale ma in realtà la procedura k-medie raggiunge solitamente la soluzione ottimale dopo poche decine di iterazioni.

Comparazione tra metodi: G=3 e n=1000.

Comparazione tra metodi: G=3 e n=1000.


  • 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

Fatal error: Call to undefined function federicaDebug() in /usr/local/apache/htdocs/html/footer.php on line 93