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).
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 , dove n rappresenta il numero di osservazioni da classificare.
Es. n=4 → {A, B, C, D}, G=2 e
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 →
n=10 →
n=1000 →
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.
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:
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:
Di solito, scelta una partizione iniziale, si cerca di migliorarla in funzione del criterio di minimizzazione della varianza (o più in generale “diversità”) interna.
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.
In letteratura sono stati proposti diversi algoritmi che differiscono tra loro nei seguenti aspetti:
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.
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.
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.
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 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:
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.
2. Scale di misura, scale di atteggiamenti e indicatori sociali
3. Alcune scale per la misurazione di atteggiamenti
5. L'Analisi in Componenti Principali
6. Introduzione all'utilizzo del software statistico Tanagra
7. Analisi delle Componenti Principali con il software statistico Tanagra
8. L'Analisi delle Corrispondenze Multiple
9. Analisi delle Corrispondenze Multiple con il software statistico TANAGRA
10. Introduzione alla Cluster Analysis
11. Cluster Analysis Gerarchica
12. Cluster Analysis non Gerarchica