Capitolo 1
Elementi di Cluster Analysis
L’idea di dividere cose simili in categorie, ovvero di raggrupparle per produrre una
classificazione, è da sempre una delle "attività" più basilari di ogni essere umano. [22]
Trattare qualsiasi cosa come se appartenente ad un’unica grande entità, e magari non
differenziarla da un insieme di altre cose, potrebbe risultare sbagliato, soprattutto per-
chè non è detto che tutto ciò di cui si è circondati sia caratterizzato sempre dalle stesse
proprietà: esiste, cioè, una certa componente di diversità a cui fare riferimento, che
consente di non «fare di tutta l’erba un fascio».
Inserendo tale problema in ambito statistico, una delle tecniche più utilizzate dagli stu-
diosi dei dati che cerca di "smascherare" tale diversità è la cluster analysis (o cluste-
ring), valida per riconoscere ed organizzare, appunto, differenti tipi di eventi, oggetti,
persone, animali e tanto altro ancora. In questo primo capitolo, si presentano in ma-
niera semplice le caratteristiche e gli obiettivi della cluster analysis, evidenziandone
alcuni concetti importanti: quello di partizione, quello di cluster (classe, gruppo) e,
con le dovute differenze, quello di diversità.
Per renderne semplice la comprensione, si ritiene utile partire da due esempi.
1.1 Introduzione
Si pensi ad un’azienda che vive in un mercato caratterizzato da forte concorrenza.
Per attuare strategie di marketing vincenti, essa deve ricercare una serie di vantaggi
competitivi, tra cui le informazioni relative al target a cui punta, decisivi per conosce-
re i desideri/bisogni/problemi dei clienti e soddisfarli, così, in modo più efficace ed
efficiente. Per questo motivo le ricerche di mercato sulla clientela sono importanti;
riescono, infatti, a valutare le caratteristiche ed i comportamenti dei clienti, persona-
lizzando l’offerta, in un’ottica di fidelizzazione ed aumento delle quantità dei prodotti
venduti. I clienti, infatti, non sono tutti uguali, ma presentano preferenze, aspettati-
ve, e comportamenti diversi. Lo strumento attraverso il quale l’azienda tiene conto di
tutti questi aspetti psicologici, emotivi, comportamentali ecc., e raggruppa, appunto, i
clienti attraverso le variabili che li rendono simili, prende il nome di segmentazione.
A titolo di secondo esempio, si pensi ora ad un laboratorio di analisi che sta pensando
di studiare la situazione clinica di un insieme di pazienti diabetici. Quest’ultima varia
da paziente a paziente, visto che sono molteplici i segni ed i sintomi con i quali il dia-
bete si presenta agli occhi dei medici, e non è detto che tutti i pazienti ne presentino le
1
stesse caratteristiche. I pazienti non sono tutti uguali, ma presentano situazioni fami-
liari, personali, ed abitudinarie diverse. Per distinguere, dunque, i soggetti analizzati
in base ai sintomi rilevati (diagnosi) e magari anche al rischio di future complicanze
dovute al diabete, il laboratorio decide di prendere in considerazione una serie di para-
metri, tra cui quelli derivanti per esempio dall’analisi del movimento o dalle abitudini
alimentari, utili per raccogliere informazioni e per proporre soluzioni al problema.
In linea generale, procedimenti come la segmentazione empirica della clientela e la
strutturazione della diagnosi per i pazienti, avvengono tramite l’utilizzo, da parte di
chi sta effettuando l’analisi, di tecniche di data mining
1
in grado di individuare rela-
zioni, informazioni e schemi, che si trovano all’interno di grandi databases e che sono
utili anche ai fini previsionali. Tra di esse, particolare rilievo assume la cluster ana-
lysis (o analisi dei gruppi), che secondo Robert Tryon [61], colui che ne ha coniato
il termine nel 1939, è «un insieme di tecniche di analisi multivariata dei dati volte alla
selezione ed al raggruppamento di elementi omogenei in un insieme di dati».
Formalmente, lo scopo di una qualsiasi tecnica di cluster analysis è quello di scopri-
re la "naturale" struttura di gruppo di un set di osservazioni (clienti, per esempio, nel
caso dell’azienda, e pazienti diabetici nel caso del laboratorio) descritte da un insieme
di variabili: ognuna di queste tecniche, cioè, può essere interpretata come un metodo
per estrarre informazioni dai dati, con una logica orientata alle osservazioni, assai di-
versa da tutt’un’altra serie di metodi che si concentrano, invece, sulle variabili. Dato,
quindi, un set di osservazioni sulle quali sono state misurate determinate variabili, si
vogliono suddividere/distinguere gli elementi del primo in gruppi omogenei (rispetto
alle ultime), anche detti clusters, andandone poi a studiare le caratteristiche in termini
di informazioni condivise dagli appartenenti.
I due esempi illustrativi e le poche righe di presentazione del metodo permettono di
caratterizzare la cluster analysis con delle prime proprietà che la rendono una tecnica
molto utilizzata dagli studiosi. La cluster analysis, infatti, è:
• diffusa. Il marketing e la ricerca medica sono solo due dei possibili ambiti in cui
essa è prevalente; in effetti c’è un grande interesse nel raggruppare cose dovuto al
vasto ammontare di dati in settori che spaziano dall’astronomia alla psicologia,
dall’informatica all’archeologia, ecc. [22];
• una metodologia non supervisionata. Essa ricerca nelle osservazioni una strut-
tura, a gruppi, che non esiste o almeno non è nota a priori. Per questo motivo, si
distingue dalla discriminazione (o analisi discriminante), la quale si concentra
sul trovare dei confini ottimali sui gruppi da discriminare, e per la quale, quin-
di, esiste già una struttura all’interno dei dati - l’obiettivo, infatti, è quello di
assegnare correttamente ulteriori osservazioni al corrispondente gruppo;
• conosciuta anche con il nome di classificazione automatica. Per trasformare,
infatti, un numeroso complesso di unità di rilevazione in una serie coerente di in-
formazioni restituite sotto forma di gruppi, c’è bisogno di algoritmi formalizzati
e costruiti in base a criteri di ottimizzazione predefiniti (automatici).
1
Per data mining si intende l’insieme delle tecniche e delle metodologie che hanno per oggetto
l’estrazione di informazioni utili da grandi quantità di dati (ad esempio dai databases), attraverso metodi
automatici o semi-automatici e l’utilizzo scientifico, aziendale/industriale o operativo delle stesse.
2
1.2 Alla ricerca di una partizione
I dati base per la maggior parte delle applicazioni della cluster analysis sono rappre-
sentati da una matrice, nota come matrice dei dati o anche come matrice casi per
variabili, all’interno della quale sono riportati i valori delle q variabili - per semplicità
di natura quantitativa - misurate sugli n casi. La matrice è, dunque, di dimensioni n q:
ciascuna riga contiene le q informazioni relative ad una determinata osservazione (ca-
so), mentre ciascuna colonna contiene i valori assunti da un determinata variabile nelle
diverse osservazioni. V olendo scrivere la matrice in simboli, si ha:
X
n;q
=
x
i j
; per i= 1;2;3;:::;n e j= 1;2;3;:::;q
(1.1)
dove il generico elemento x
i j
rappresenta il valore che la j-esima variabile assume in
corrispondenza dell’ i-esima osservazione. In tabella 1.3 ne è illustrato un esempio.
Tabella 1.1: Matrice casi x variabiliX
Casi Variabili
Variabile 1 Variabile 2 Variabile 3 . . . Variabile q
Caso 1 x
11
x
12
x
13
. . . x
1q
Caso 2 x
21
x
22
x
23
. . . x
2q
Caso 3 x
31
x
32
x
33
. . . x
3q
. . . . . . . . . . . . . . . . . .
Caso n x
n1
x
n2
x
n3
. . . x
nq
X può essere vista come un insieme di n vettori riga (di dimensioni 1 q) contenenti
ciascuno il profilo dell’i-esima osservazione, ovvero i valori che in essa assumono le q
variabili osservate. In aggiunta, essa può essere vista come un insieme di q vettori co-
lonna (di dimensioni n 1) contenenti ciascuno il profilo della j-esima variabile, ovvero
i valori che essa assume per tutte le osservazioni. Queste caratteristiche sono molto
importanti, perchè consentono di fare alcune considerazioni.
Operando alcune trasformazioni sulla matrice X, il principale obiettivo della cluster
analysis è quello di ricercare la partizione del collettivo di n osservazioni in k (con
k < n ed intero, per k= 1;2;3;:::;K) sottoinsiemi (appunto i clusters) tali che le os-
servazioni appartenenti ad uno stesso sottoinsieme siano il più possibile omogenee tra
loro rispetto alle misurazioni dell’insieme di variabili. È fondamentale definire, quin-
di, il concetto di partizione, ricavabile dalla teoria degli insiemi [16], ed evidenziarne
quelle che sono le proprietà salienti.
Definizione 1.1. Una partizione P(E) di un insieme E è l’insieme delle parti o delle
classi di E tale che:
1. Due elementi A e B della partizione sono disgiunti o coincidenti:
A;B2 P(E)) A\ B=? oppure A[ B= A= B
2. L’unione di tutte le parti esaurisce E:
fA;B;:::;Zg= P(E) ) A[ B[:::[ Z= E
3
La definizone 1.1, applicata alla cluster analysis, esplicita la suddivisione (la partizione
P(E)) dell’insieme delle n osservazioni (E) in una serie di gruppi (le parti, le classi, i
clusters), tali per cui:
• ciascuno di essi non deve essere vuoto,
2
deve cioè contenere un determinato
numero di osservazioni. Per questo motivo la partizione si definisce rigida;
• presi a due a due non devono avere nessun elemento in comune, ciascuna osser-
vazione deve quindi appartenere ad uno ed un solo gruppo. A questo proposito
la partizione si definisce senza sovrapposizione;
• la loro unione deve ricostituire l’insieme di partenza; non vi devono essere ele-
menti al di fuori dei gruppi e quindi dell’insieme di partenza. In questo caso la
partizione si definisce esaustiva.
Algebricamente parlando, la suddivisione delle n oosservazioni in k gruppi prende la
forma di una matrice di dimensioni n K, denominata matrice di partizione ed indicata
con il simbolo Z
K
, che raccoglie l’appartenenza di ciascuna delle osservazioni al k-
esimo gruppo, per k= 1;2;:::;K. Essa è una matrice binaria le cui entrate z
ik
assumono
solamente due valori:
z
ik
=
(
1; se l’i-esima osservazione appartiene al k-esimo gruppo;
0; se l’i-esima osservazione non vi appartiene
Così costruita, Z
K
(un esempio in Tabella 1.2) rispecchia le prime due considerazioni
fatte precedentemente. In primo luogo, essa è tale per cui ogni colonna contiene alme-
no un valore pari ad 1, e non ci sono righe contenenti solo valori pari a 0, indi per cui
ciascun gruppo non è vuoto ma contiene informazioni sulle osservazioni. In secondo
luogo, essa è tale per cui ciascuna riga contiene un unico valore pari ad 1 e tutti gli altri
pari a 0, e ciò è esemplificativo del fatto che ciascuna osservazione è stata assegnata
correttamente ad uno ed un solo gruppo.
Tabella 1.2: Esempio di matrice di partizioneZ
K
Casi Gruppi
Gruppo 1 Gruppo 2 Gruppo 3 . . . Gruppo K
Caso 1 1 0 0 . . . 0
Caso 2 0 0 1 . . . 0
Caso 3 0 1 0 . . . 0
. . . . . . . . . . . . . . . . . .
Caso n 0 0 0 . . . 1
Analizzandone, ora, i totali (di riga e di colonna), è possibile tenere conto anche della
terza considerazione. Z
K
, infatti, è tale per cui i totali di riga - che rappresentano
il numero di gruppi a cui un’osservazione può essere assegnata - sono tutti pari ad 1,
mentre i totali di colonna - che sono delle frequenze assolute - rappresentano il numero
2
In alcuni casi, l’esistenza di gruppi vuoti potrebbe compromettere i risultati delle analisi.
4
di osservazioni appartenenti al k-esimo gruppo. Sommando, rispettivamente, i totali di
riga ed i totali di colonna, si ottiene la numerosità n dell’insieme di partenza (ottenibile
anche sommando tutti gli elementi presenti all’interno di Z
K
). In formule:
n
i=1
z
:i
=
K
k=1
z
k:
=
n
i=1
K
k=1
z
ik
= n (1.2)
dove z
:i
rappresenta il totale marginale dell’i-esima riga e z
k:
rappresenta, invece, il
totale marginale della k-esima colonna. È proprio considerando la somma di questi
ultimi che si riesce a capire come l’unione delle parti ricostituisca il tutto.
1.2.1 Una parte del tutto: il concetto di cluster
Fin qui, i termini "gruppo", "classe" e "cluster" sono stati utilizzati in maniera intuitiva
senza alcun accenno ad una definizione formale. Infatti, sembra che essa non sia solo
difficile da trovare, ma potrebbe addirittura non essere appropriata. Ciò che sicura-
mente può essere di aiuto è il fatto che ciascun gruppo deve contenere al suo interno
elementi che sono omogenei rispetto alle variabili osservate, come già definito.
Uno dei contributi più interessanti al riguardo è quello di Cormack [17]. Egli tenta di
definire ciò che un cluster rappresenta attraverso i concetti di coesione interna - omo-
geneità - e di separazione esterna - eterogeneità. La coesione interna è la proprietà
secondo cui le più piccole correlazioni tra le osservazioni accettate all’interno di un
cluster devono essere più grandi di una determinata soglia: le osservazioni all’inter-
no dei gruppi devono cioè condividere delle caratteristiche, presentare un qualcosa di
simile tra di loro. La separazione esterna, invece, è la proprietà secondo cui le osser-
vazioni che non hanno nulla di simile tra di loro devono essere posizionate in gruppi
differenti: i gruppi devono essere il più possibile distinti, nel senso che deve essere
osservabile una discontinuità tra di loro. L’obiettivo della cluster analysis è la massi-
mizzazione congiunta di entrambe. Può risultare ora interessante visualizzare, al meno
in maniera informale, queste due proprietà attraverso la Figura 1.1.
Figura 1.1: Illustrazione dei concetti di coesione interna e separazione esterna dei
gruppi: (a sinistra) i gruppi sono coesi ma non isolati; (al centro) i gruppi sono isolati
ma non coesi; (a destra) i gruppi sono isolati e coesi.
5
I clusters presenti in figura risultano chiari a chi li osserva anche senza alcuna defini-
zione formale, e risulta anche chiaro che la situazione migliore è quella definita nella
figura a destra, nella quale i clusters sembrano poter massimizzare sia la loro omo-
geneità che l’eterogeneità tra di loro. Ciononostante, la figura indica che non esiste
un’unica definizione valida per tutte le situazioni. Questo potrebbe spiegare il motivo
per il quale ci sono stati numerosi tentativi per rendere matematicamente precisi i con-
cetti di cui sopra, portando alla definizione di numerosi e diversi criteri.
Non è perfettamente chiaro come dovrebbe essere riconosciuto un cluster, ma un valido
ausilio è dato dalla valutazione delle relative diversità tra gli oggetti.
1.2.2 Ulteriori obiettivi della cluster analysis
La definizione di partizione e la presentazione dei concetti di omogeneità e di ete-
rogeneità hanno consentito di sviluppare un primo importante obiettivo della cluster
analysis: l’identificazione di gruppi di osservazioni simili nei dati originari.
Provvedendo, dunque, ad una partizione degli n oggetti in k gruppi, essa inoltre con-
corre alla determinazione di due ulteriori obiettivi, da non trascurare:
• descrizione ed esplorazione delle strutture interne ai dati, in particolare delle
relazioni nell’insieme delle osservazioni. Essa è una tecnica di tipo descrittivo,
perchè non ha le basi statistiche sulle quali fondare procedimenti inferenziali
dal campione osservato alla popolazione, e perchè consente di suggerire delle
interpretazioni circa il ruolo e l’effetto delle variabili presenti nei dati. Poichè
è anche una tecnica esplorativa, essa postula che i dati potrebbero contenere
gruppi distinti ma non parte da una precisa indicazione sul numero di gruppi già
esistenti [33];
• sintesi (seppur parziale) delle informazioni contenute all’interno della matrice
dei dati iniziali, attraverso la costruzione di pochi clusters. Essa, cioè, consente
di ridurre all’essenziale il numero di informazioni, e di riportarle all’interno di
ciascun cluster, attribuendo a quest’ultimo il significato di indicatore riassuntivo
e di "rappresentante" per confronti, valutazioni, e decisioni.
1.3 Distanze, (dis)similarità e prossimità
Lo studio delle diversità è un passaggio chiave in molte applicazioni del data mining.
La forma più effettiva per il loro studio può essere espressa solamente nei termini di
un particolare contesto, nel senso che dipende dalla tipologia di dati a disposizione, e
risulta una sfida non banale riuscire a trovarla. [2]
Nella cluster analysis, di centrale importanza nel tentativo di identificare gruppi omo-
genei nei dati originari è la conoscenza di quanto vicine (o lontane) siano le osser-
vazioni tra di loro. Generalmente, il punto di partenza per questo tipo di obiettivo è
rappresentato dalla trasformazione della matrice dei dati X in una matrice di diversità
D (simmetrica, semidefinita positiva e con valori nulli sulla diagonale principale) di
dimensioni n n (quindi anche quadrata), i cui elementi d
ii
0 (per i= 1;2;:::;n, e per
i
0
= 1;2;:::;n) rappresentano una misura di come differiscono tra di loro due osser-
vazioni a confronto, riflettono cioè una misura di vicinanza, più comunemente detta
6
dissimilarità, distanza o similarità, e con un termine specifico che è prossimità [22].
In Tabella 1.3 è presente la struttura generale di D.
Sostanzialmente, si fa il confronto fra tutte le n
2
possibili coppie di osservazioni, ana-
lizzandone le analogie e le differenze rispetto alle variabili osservate. Essendo poi D
una matrice simmetrica e con n valori pari a 0 sulla diagonale principale, il numero di
confronti di interesse è pari a
n
2
n
2
=
n(n 1)
2
.
Tabella 1.3: Matrice di diversitàD
Casi (i) Casi (i
0
)
Caso 1 Caso 2 Caso 3 Caso 4 Caso 5 . . . Caso n
Caso 1 0 d
12
d
13
d
14
d
15
. . . d
1n
Caso 2 d
21
0 d
23
d
24
d
25
. . . d
2n
Caso 3 d
31
d
32
0 d
34
d
35
. . . d
3n
Caso 4 d
41
d
42
d
43
0 d
45
. . . d
4n
Caso 5 d
51
d
52
d
53
d
54
0 . . . d
5n
. . . . . . . . . . . . . . . . . . . . . . . .
Caso n d
n1
d
n2
d
n3
d
n4
d
n5
. . . 0
Il concetto di cluster presuppone l’esistenza di un criterio globale - un indice - che
misuri la prossimità tra le osservazioni, e che sia quindi in grado di riempire le en-
trate della matrice sopra indicata. Si può allora definire un’applicazione D che faccia
corrispondere un numero reale positivo o nullo a ciascuna coppia (i;i
0
) appartenente
all’insieme di dati considerato, e le seguenti condizioni, ad alcune delle quali sono
collegate le caratteristiche di D:
1. Non negatività: D(i;i
0
) 0. L’applicazione D su due osservazioni i ed i
0
deve
essere un numero sempre positivo, al limite uguale a 0.
2. Separabilità, o coincidenza: (caso limite della condizione 1) D(i;i
0
)= 0, i= i
0
.
L’applicazione D è uguale a 0 se e solo se le due osservazioni coincidono. Non
a caso, gli elementi sulla diagonale principale della matrice D - che derivano
dall’incrocio dell’i-esima osservazione con sè stessa - sono pari a 0;
3. Simmetria: D(i;i
0
)= D(i
0
;i). L’applicazione D tra i ed i
0
assume lo stesso valore
rispetto all’applicazione D calcolata tra i
0
ed i. L’i-esima riga di D corrisponde,
cioè, all’i-esima colonna. D è simmetrica;
4. Disuguaglianza triangolare, o sub-additività: D(i;i
0
) D(i;i
00
)+ D(i
00
;i
0
). In
un triangolo la lunghezza di un lato (distanza che intercorre tra due punti) non
supera la somma delle lunghezze degli altri due (somma delle distanze tra tali
punti ed un altro). Considerate, quindi, tre osservazioni nella matrice D, le cui
applicazioni si incrociano tra di loro, si verifica che la somma di due applicazioni
D (con D6= 0, quindi per i6= i
0
) all’interno della corrispondente sottomatrice - di
dimensioni 3 3 - è sempre maggiore o uguale rispetto alla terza applicazione.
D è, dunque, semidefinita positiva;
7
5. Disuguaglianza ultrametrica, o di Krassner: D(i;i
0
) sup(D(i;i
00
);D(i
00
;i
0
)).
L’applicazione D tra i ed i
0
è minore o uguale rispetto all’applicazione più gran-
de tra D(i;i
00
) e D(i
00
;i
0
). Questa condizione è detta anche del triangolo isoscele,
perchè le lontananze che caratterizzano ciascuna terna di punti sono date dal
triangolo isoscele la cui base è data dalla distanza dei punti più vicini tra loro.
Considerate, quindi, tre osservazioni nella matrice D, le cui applicazioni si in-
crociano tra di loro, si verifica che una delle tre possibili applicazioni D (con
D6= 0, quindi per i6= i
0
), all’interno della sottomatrice di dimensioni 3 3, è
sempre minore o uguale rispetto alla più grande tra le altre due.
Si parlerà di indice di (dis)similarità se si verificano solamente le prime tre condizio-
ni; esso assume valori sempre compresi nell’intervallo chiuso[0;1]
3
, può risultare nul-
lo anche quando i6= i
0
, e consente il solo confronto tra le caratteristiche di coppie di ele-
menti dell’insieme [24]. La matrice D assumerà il nome di matrice di (dis)similarità,
e sarà soltanto simmetrica con elementi nulli sulla diagonale principale.
Si parlerà di indice di distanza, o di metrica, se si verificano soltanto le prime quattro
condizioni; esso può assumere qualsiasi valore non negativo, e consente la definizione
di una relazione d’ordine tra le distanze tra i punti - ossia la determinazione di una "so-
glia" che definisca una partizione dell’insieme iniziale in gruppi tale che un elemento
si trovi in uno di essi a seconda che la distanza da tutti gli altri elementi rispettivamente
sia minore o uguale della soglia fissata, o maggiore di questa [24]. In questo caso, la
matrice D assumerà il nome di matrice delle distanze: essa sarà simmetrica, semide-
finita positiva e con elementi sulla diagonale principale pari a 0.
Si parlerà, infine, di ultrametrica se si verificano le condizioni 1, 2, 3 e 5. La cor-
rispondente matrice D prenderà il nome di matrice delle distanze ultrametriche, e
sarà simmetrica e con elementi sulla diagonale principale pari a 0, ma non semidefinita
positiva. Tale matrice costituisce però a tutti gli effetti una matrice di distanze, perchè
la disuguaglianza ultrametrica implica la disuguaglianza triangolare.
La scelta della misura di diversità è strettamente legata alla natura dei dati, risultando
infatti diverse le misure da adottare a seconda che le osservazioni siano descritte da
variabili numeriche, da frequenze o da variabili non numeriche. Una scelta sbagliata
della misura di diversità può, a sua volta, influenzare i risultati della cluster analysis.
1.3.1 La distanza euclidea
Considerando che le n righe della matrice X sono rappresentabili come punti all’in-
terno dello spazio a q dimensioni formato dalle variabili [24], è possibile calcolare le
distanze all’interno dello stesso spazio tra tutte le coppie di osservazioni(i;i
0
), a partire
dalle loro coordinate. Per raggiungere tale scopo, probabilmente la più nota e la più
utilizzata misura di diversità è la distanza euclidea. Presi, quindi, due punti i ed i
0
in
uno spazio a q dimensioni, la loro distanza euclidea - risultante dall’applicazione del
Teorema di Pitagora - è calcolata come la radice quadrata della somma dei quadrati
3
Generalmente, un indice di similarità s
ii
0 è il complemento ad 1 di un indice di dissimilaritàd
ii
0 .
Due osservazioni i e i
0
sono, quindi, vicine tra di loro se la loro misura di dissimilarità è piccola, o
alternativamente se la loro misura di similarità è grande. Viceversa, sono lontane se la loro misura di
(dis)similarità è piccola (grande).
8
delle differenze tra i valori x
i j
ed x
i
0
j
delle variabili osservate rispettivamente per i ed
i
0
. In formule, si ha quanto segue:
d
2
(i;i
0
)=
v
u
u
t
q
j=1
(x
i j
x
i
0
j
)
2
(1.3)
Per j= 1;2;3 (cioè in uno spazio al massimo tridimensionale) risulta che d
2
(i;i
0
) rap-
presenta il segmento che congiunge i rispettivi punti [31].
La particolarità della distanza euclidea sta nel fatto che essa è in grado di rendere
euclidea una matrice di dissimilarità, nel senso che permette l’interpretazione delle
dissimilarità come se fossero delle distanze fisiche. Dunque la distanza euclidea tra
due punti i ed i
0
è pari ad una misura di dissimilarità. Se una matrice di dissimilarità è
euclidea, allora è anche metrica, ma non vale il contrario.
Sostituendo le medie dei gruppi (note anche come centroidi) al posto dei valori del-
le variabili nella (1.3), si costruisce una misura di distanza tra i gruppi, nota come
distanza euclidea tra i gruppi:
d
2
(k;k
0
)=
v
u
u
t
q
j=1
(x
k j
x
k
0
j
)
2
(1.4)
dove x
k j
e x
k
0
j
sono i vettori delle medie (relative alle variabili osservate) dei gruppi
presi a due a due.
La distanza euclidea pesata
Se le q variabili sono misurate attraverso differenti unità di misura, è necessario ri-
scalarle per rendere i loro valori comparabili. Ciò equivale a calcolare la cosiddetta
distanza euclidea pesata, che assume la seguente espressione:
d
w
(i;i
0
)=
v
u
u
t
q
j=1
w
j
(x
i j
x
i
0
j
)
2
(1.5)
dove w
j
rappresenta il peso attribuito alla j-esima variabile, e proviene da una matrice
diagonale W (di dimensioni q q) che ha elementi pari a w
j
sulla diagonale principale
e nulli altrove. Questa matrice viene utilizzata per evidenziare la differente importanza
delle variabili all’interno del processo. Se W è una matrice unitaria, cioè se tutte le
variabili hanno lo stesso peso pari ad 1, allora la (1.5) si riduce alla (1.3).
Un modo alternativo per scrivere la (1.5) è:
d
w
(i;i
0
)=
v
u
u
t
q
j=1
(x
i j
x
i
0
j
)
2
(1.6)
con x
i j
= x
i j
w
j
che rappresenta il valore pesato della j-esima variabile misurata per
l’i-esima osservazione.
Esistono due metodi per scegliere i valori dei pesi w
j
: 1) in maniera soggettiva, nel
senso che il ricercatore è libero di pesare le variabili secondo considerazioni al di fuori
dei dati; 2) i pesi sono scelti in maniera inversamente proporzionale alle varianze delle
variabili, e quindi sono scelti dai dati.
9
Caso particolare: la distanza di Mahalanobis
Quando si definisce la distanza euclidea, si suppone che le variabili non siano mu-
tualmente correlate, ossia che non abbiano nessuna relazione lineare prese a due a
due. Quando questa assunzione è violata, si potrebbe verificare una distorsione nella
computazione delle distanze tra le osservazioni. In tal caso, è applicata solitamente la
distanza di Mahalanobis, definita come:
d
S
(i;i
0
)=
q
(x
i
x
i
0)
T
S
1
M
(x
i
x
i
0) (1.7)
che è una variante generalizzata della distanza euclidea. La matriceS
M
rappresenta la
matrice di varianze e covarianze delle variabili calcolata nel seguente modo:
S
M
=
1
n
n
i=1
(x
i
x
j
)(x
i
x
j
)
T
(1.8)
con x
j
=
1
n
n
i=1
x
i
pari al vettore delle medie delle variabili. Quando le variabili sono
indipendenti, la matriceS
M
è diagonale: gli elementi diversi da 0 presenti sulla diago-
nale principale sono uguali alle varianze delle variabili. La risultante misura è perciò
definita distanza euclidea normalizzata.
La distanza di Mahalanobis è invariante rispetto a trasformazioni lineari delle variabili
originarie, e viene utilizzata per l’identificazione delle osservazioni atipiche (outliers)
all’interno dei dati. Esiste, inoltre, una versione di tale distanza riferibile ai gruppi, che
tiene conto dei rispettivi centroidi; essa assume la seguente espressione:
d
S
(k;k
0
)=
q
(x
k
x
k
0)
T
S
1
M
(x
k
x
k
0) (1.9)
dove S
M
ora rappresenta la matrice di varianze e covarianze riferite ai gruppi presi
a due a due. Essa aumenta all’aumentare delle distanze tra i centri dei gruppi, ed al
diminuire della varianza entro i gruppi. Tiene, infine, conto della forma (possibilmente
non sferica) dei clusters. [22]
1.3.2 Altre misure di distanza
Tra le misure di distanza utilizzate nel caso di osservazioni descritte da variabili quan-
titative rientrano anche altre due misure non meno frequenti rispetto alla distanza
euclidea.
La distanza City block
Detta anche distanza rettilineare (o metrica di Manhattan), è così chiamata in quanto
rappresenta la distanza che deve coprire un individuo che si muova in una città di
blocchi rettangolari, con strade tra di loro perpendicolari o parallele. L’individuo non
può attraversare diagonalmente la città, ma si deve muovere lungo una dimensione alla
volta del blocco (Figura 1.2). La sua espressione è:
d
1
(i;i
0
)=
q
j=1
jx
i j
x
i
0
j
j (1.10)
10
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
