CLUSTER ANALYSISInsieme 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

AMORFITA’ DEI DATI

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

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 operazionidefinite 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 tabellatecnica di

classificazione più adeguata

identificazionedel numero di classi

più adeguato per il

raggiungimento degli

obiettivi dell’analisi

Interpretazione deirisultati 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)

Le CLASSI formate ad ogni livello devono

essere disgiunte (intersezione vuota) e la loro

unione deve essere uguale all'insieme degli

elementi da classificare.

TECNICHE DI ANALISI GERARCHICA

AGGLOMERATIVE

O ASCENDENTIDIVISIVE

applicate solo a matrici

di dati poco numerose

Nei metodi gerarchici la costruzione della

gerarchia è di tipo

BINARIOConsidera 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à tradue classi,

selezionare tra le classi di unapartizione quelle che sarannounite (algoritmo ascendente) o quella che sarà divisa (algoritmo discendente), perottenere una famiglia di partizioni

Una PARTIZIONE dell’insieme delle unità statisticheU è 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 nodoche etichetta l'ordine

di formazione delle classi(2 n -1)

il livello di prossimità

(dissimilarità, distanza) inbase al quale è ottenuta

la classe stessa.

nodo 8

La tecniche gerarchiche si possono rappresentare

su un sistema di assi cartesiani mediante un

diagramma ad albero detto DENDROGRAMMA.

Unità da classificare

Prossimita’

o distanza

1 4 23 5

nodo 6

nodo 7

nodo 9

5

0

10

15

20

25

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

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)

qi qj

K Z

INERZIA inerzia (i) = pi d2 (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.

g

i

N(I)

Inerzia N (I) = pi 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,

q i q j

gigj

N(I)

g

N(I) =fqi d2 (g, gi ) + fqj d2 (g, gj)

inerzia interclasse

+

+(fid2(gi,i)iqi) + (fj d2 (gj, j )j qj)

inerzia intraclasse

l'inerzia totale della nube N(I)

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.

Tra due partizioni con lo stesso numero di classi,

si preferirà quella con le classi più compatte,

cioè quella che avrà un'inerzia intraclasse

minore.

AUMENTO dell'INERZIA

Considerando l'inerzia più una classe è

compatta e più l'inerzia di questa classerispetto al suo centro di gravità è piccola

poiché le distanze dei punti della classe

sono prossime al centro della classe

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.

Data una partizione Q, si può esaminare LA

VARIAZIONE DELL'INERZIA INTRACLASSE nel

raggruppare due classi qi e qj in una sola

classe qo.

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.

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)

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

AB

)(1

)var()var( jiji

jio qqIfqfq

qqq

),()()((

)()()(

1)(

1 22 jiji

jij

jii

jiggd

qfqf

qfqfqI

fqfqqI

fqfq

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:

PROBLEMA

nodo 8

Unità da classificare1 4 23 5

nodo 6

nodo 7

nodo 9

5

0

10

15

20

25

Prossimita’

o distanza

La partizione ottimale è quella in cui i valori f(k) sono pressoché costanti e tra di loro non

presentano grosse differenze.

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.

CALINSKYHARABASZ

f(k) = inerzia interclasse /

inerzia intraclasse

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.

dove la partizione ottimale è quella relativa al

numero di classi k che fornisce un valore di C

pressoché costante

trW

kn

k

trBC

*1

METODI BASATI SULLA VARIANZA

Dalla relazione tra la varianza totale e la sua

scomposizione in varianza interna ai gruppi e

varianza tra i gruppi T = W+ B

CALINSKYHARABASZ

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à

)2(

)2()1(

k

kk

W

WWF

CRITERIO DIBEALE

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

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

TECNICHE DI ANALISI NON GERARCHICHE

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.

- 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

Quali sono gli aspetti da considerare per l’applicazione della tecnica?

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:

tabella di analisi della

varianza

Le dimensioni di ciascun clusterdovrebbero essere preferibilmente

omogenee o almeno non inferiore ad un limite che definisce la

significatività operativa del cluster

Per valutare la qualità statisticadella clusterizzazione e cioè ad esempio attraverso un test F verificare se le medie tra i diversi cluster siano statisticamente

diverse

la numerosità delle osservazioni di ciascun cluster

Rispetto alle variabili consideratecaratteristiche dei

centri finali