CLUSTER ANALYSIS
Insieme di tecniche con l’obiettivo di unire le
unità di un insieme statistico in un numero finito
di classi o gruppi i quali devono risultare quanto
più possibile OMOGENEI al loro interno e
diversificati tra di loro. L’ideale sarebbe:
Si necessita di una MATRICE DEI DATI,
osservazioni per variabili, la quale deve
possedere alcune caratteristiche:
OMOGENEITA’
DIMENSIONE
e cioè che abbia un senso il calcolo
e la comparazione delle distanze
che intercorrono tra gli individui o delle
relazioni tra i caratteri della tabella
Elevato numero di righe e di colonne
AMORFITA’ DEI DATI
Non deve esistere una struttura
definibile a priori tra gli individui o
tra le variabili
Le variabili da inserire nella tabella dei dati sono
strettamente legate al fenomeno analizzato e
sono la base per stabilire l’omogeneità delle
unità all’interno delle classi risultanti.
Le tecniche di classificazione utilizzano
ALGORITMI
Serie di operazioni
definite in modo ricorrente e ripetitivo da
cui risulteranno i raggruppamenti
Il ricercatore deve scegliere:
misura di prossimita’
per rilevare la somiglianza
o dissomiglianza tra gli
elementi della tabella
tecnica di
classificazione
più adeguata
più adeguato per il
identificazione
del numero di classi
raggiungimento degli
obiettivi dell’analisi
Interpretazione dei
risultati della classificazione
LE TECNICHE DI CLUSTER POSSONO
DISTINGUERSI, IN BASE AI
RISULTATI FORNITI IN
GERARCHICHE e NON GERARCHICHE
TECNICHE in cui un'unità può
appartenere esclusivamente
ad una sola classe (partizione)
o a più classi (clump)
TECNICHE DI ANALISI GERARCHICA
AGGLOMERATIVE
DIVISIVE
O ASCENDENTI
applicate solo a matrici
di dati poco numerose
 Le CLASSI formate ad ogni livello devono
essere disgiunte (intersezione vuota) e la loro
unione deve essere uguale all'insieme degli
elementi da classificare.
 Nei metodi gerarchici la costruzione della
gerarchia è di tipo
BINARIO
Considera 2
elementi alla
volta
Gli elementi possono essere:
 2 individui
 1 individuo ed 1 classe
2 classi
E’
necessario
definire
una
REGOLA
SEQUENZIALE per il passaggio da una generica
partizione alla successiva, che consenta di:
misurare la
Prossimità tra
due classi,
selezionare tra le classi di una
partizione quelle che saranno
unite (algoritmo ascendente)
o quella che sarà divisa
(algoritmo discendente), per
ottenere una famiglia di partizioni
Una PARTIZIONE dell’insieme delle unità statistiche
U è un insieme di parti (A1…. AG ) che siano disgiunte
a due a due e la cui riunione sia uguale ad U
Ad ogni classe della gerarchia sono associati due
numeri:
il nodo
il livello di
prossimità
che etichetta l'ordine
di formazione delle classi
(2 n -1)
(dissimilarità, distanza) in
base al quale è ottenuta
la classe stessa.
La tecniche gerarchiche si possono rappresentare
su un sistema di assi cartesiani mediante un
diagramma ad albero detto DENDROGRAMMA.
Prossimita’
o distanza
25
nodo 9
20
15
nodo 8
nodo 7
10
5
0
nodo 6
1 4
3
2
5
Unità da classificare
CRITERI DI AGGREGAZIONE
 LEGAME MINIMO
 LEGAME MASSIMO
INERZIA
 VARIANZA
LEGAME
MINIMO
la dissimilarità tra due classi qi e qj di
una partizione è misurata attraverso
la più piccola dissimilarità tra le unità
delle due classi d(qi, qj) = min (dkz)
qi
qj
K
Z
LEGAME
MASSIMO
qi
K
la dissimilarità tra due classi di una
partizione qi e qj è misurata attraverso
la più grande dissimilarità che separa
le unità tra le due classi
d(qi, qj) = max (dkz)
qj
Z
INERZIA
inerzia (i) = pi d2 (g, i )
N(I)
g
i
L’INERZIA TOTALE di N(I) è la somma delle
inerzie dei diversi punti i di N(I) calcolate in
relazione al centro di gravità g.
Inerzia N (I) = Spi d2 (g, i )
Se l'insieme I è tagliato in
o sole 2 classi: q i e q j
o con centri di gravità gi e g j
o pesi f qi e f qj,
N(I)
qi
qj
gj
gi
g
l'inerzia totale della nube N(I)
N(I) =fqi d2 (g, gi ) + fqj d2 (g, gj)
inerzia interclasse
+
+(fid2(gi,i)iqi) + (fj d2 (gj, j )j qj)
inerzia intraclasse
 LA SOMMA (inerzia interclasse + inerzia
intraclasse di una partizione Q)
È COSTANTE
qualunque sia la partizione Q considerata, poiché
è sempre uguale all'inerzia totale
della
nube
N(I).
 È solo LA RIPARTIZIONE dell'inerzia totale
in:
inerzia
interclasse
e intraclasse che
varia con il variare della partizione Q di I.
AUMENTO dell'INERZIA
Considerando l'inerzia più una classe è
compatta e più l'inerzia di questa classe
rispetto al suo centro di gravità è piccola
poiché
le distanze dei punti della classe
sono prossime al centro della classe
 Tra due partizioni con lo stesso numero di classi,
si preferirà quella con le classi più compatte,
cioè quella
minore.
che avrà
un'inerzia
intraclasse
Data una partizione Q, si può esaminare LA
VARIAZIONE DELL'INERZIA INTRACLASSE nel
raggruppare due classi qi e qj in una sola
classe qo.
L'inerzia intraclasse di qo
(che coincide con l'inerzia totale della partizione Q)
è uguale alla somma dell'inerzia interclasse della
partizione (qi e qj) e dell'inerzia intraclasse delle due
classi.
Per le classi qi, qj, qo:
gi , gj e go sono i
centri di gravità
fqi, fqj e fqo
sono i pesi
I (qo ) = fqi d2 (go, gi ) + fqj d2 (go ,gj) + I (qi ) + I (qj)
Tra le due partizioni comparate l'unica differenza è
che in una sono presenti le classi qi e qj nell'altra
la classe qo che sostituisce le classi qi e qj.
 Si rileva con immediatezza che I (qo ) supera
I(qi) + I (qj) della quantità:
fqi d (go, gi ) + fqj d (go ,gj)
 Il raggruppamento delle classi qi e qj in
una
sola classe qo fa aumentare l'inerzia intraclasse
della quantità indicata con crit (qi, qj):
o crit(qi, qj )= fqi d(go, gi )+fqj d(go,gj)
misura il livello di dissimilarità della partizione
CRITERIO DELLA
VARIANZA
C
A
B
1
var(qo )  var(qi  q j ) 
I (qi  q j ) 
fqi  fq j
f (qi ) f (q j )
1
1

I (qi ) 
I (q j ) 
d 2 ( gi , g j )
fqi  fq j
fqi  fq j
( f (qi )  f (q j ) 2
PROBLEMA
QUAL’E’ IL NUMERO OTTIMALE DELLE
CLASSI DA PRENDERE IN CONSIDERAZIONE?
 DOVE
EFFETTUARE
IL
COSIDDETTO
TAGLIO DELL’ALBERO DEL DENDROGAMMA?
Si possono utilizzare ALCUNI CRITERI, che
permettono di facilitare la scelta riguardo la
partizione ottimale:
Prossimita’
o distanza
25
nodo 9
20
15
nodo 8
nodo 7
10
5
0
nodo 6
1 4
3
2
5
Unità da classificare
TASSO DI
INERZIA
t(k) = inerzia intraclasse/inerzia totale
t(k) varia tra 0e 1, è uguale a 0 quando tutte le
unità costituiscono una classe a sé stante, sarà
pari a 1 quando tutte le unità sono comprese in
una sola classe.
CALINSKY
HARABASZ
f(k) = inerzia interclasse /
inerzia intraclasse
La partizione ottimale è quella in cui i valori f(k)
sono pressoché costanti e tra di loro non
presentano grosse differenze.
 Questi due metodi sono COMPLEMENTARI,
poiché l'inerzia totale, il cui valore è costante per
ogni livello di aggregazione, si divide in:
I=
inerzia interclasse + inerzia intraclasse
 Inoltre quando si aggregano due unità e poi due
classi,
per
ottenere
una
nuova
partizione,
necessariamente si ha un aumento dell'inerzia
intraclasse e una riduzione dell'inerzia interclasse.
METODI BASATI SULLA VARIANZA
Dalla relazione tra la varianza totale e la sua
scomposizione in varianza interna ai gruppi e
varianza tra i gruppi
CALINSKY
HARABASZ
T = W+ B
trB
nk
C
*
k  1 trW
dove la partizione ottimale è quella relativa al
numero di classi k che fornisce un valore di C
pressoché costante
CRITERIO DI
BEALE
sottopone a test se il numero di
classi k1 sia da preferire ad un
numero di classi k2 con k1 < k2.
Il test utilizzato è quello di FISHER
F
W(k1)  W(k 2)
W ( k 2)
Dove il numeratore ha p(k2 – k1) e il
denominatore p (n-k2) gradi di libertà e p è il
numeor di variabili rilevate su ciascuna unità
TECNICHE DI ANALISI NON GERARCHICHE
 Forniscono classi tra di loro non strutturate, per
cui non prevedono la storia dell’aggregazione.
 Necessitano che sia fornito in input il numero
delle classi da formare e per ogni classe
bisogna identificare un ELEMENTO LEADER
della classe intorno a cui aggregare sulla base
di un criterio gli altri elementi da classificare.
 I risultati di tale tecnica variano sia in funzione
del numero di classi che dell’elemento leader
 Gli algoritmi k-medie sono caratterizzati da una
procedura iterativa che cerca di ottenere un
progressivo miglioramento delle partizioni
ottenute.
 Tali metodi assumono che il numero di cluster
desiderato sia fissato a priori, ma ripetendo
l’analisi più volte e cambiando il numero dei
cluster si possono confrontare le diverse
soluzioni ottenute.
Quali sono gli aspetti da considerare per
l’applicazione della tecnica?
 - il numero dei centri
 - un metodo per la scelta dei centri dei cluster
iniziali
 - un metodo per allocare gli elementi nei cluster
iniziali
 - un criterio per l’uscita dalla procedura iterativa
La scelta dei k centri iniziali (provvisori)
può essere casuale o avvenire attraverso un
criterio prestabilito:
-alcune procedure scelgono le prime k
osservazioni del database,
- altre casualmente k osservazioni del file
- altre scelgono in modo ottimale i centri iniziali
utilizzando le k osservazioni più DIVERSE TRA di
loro
La regola di assegnazione è tale per cui un
elemento i appartiene al gruppo Ij se il punto i è più
vicino al centro di Ij che a tutti gli altri centri
L’algoritmo si ferma quando:
- due successive iterazioni conducono alla stessa
partizione
- la funzione obiettivo scelta non decresce più in
maniera significativa
- è stato raggiunto il numero di iterazioni
precedentemente stabilito
Per la determinazione del numero dei cluster più
opportuno gli elementi utili per la scelta e
l’interpretazione della soluzione sono essenzialmente:
la numerosità delle
osservazioni di
ciascun cluster
tabella di
analisi della
varianza
Le dimensioni di ciascun cluster
dovrebbero essere preferibilmente
omogenee o almeno non inferiore ad
un limite che definisce la
significatività operativa del cluster
Per valutare la qualità statistica
della clusterizzazione e cioè ad esempio
attraverso un test F verificare se le medie
tra i diversi cluster siano statisticamente
diverse
caratteristiche dei
centri finali
Rispetto alle variabili considerate