Distanza media assoluta

La distanza media assoluta tra le unità statistiche h e k nello spazio p-dimensionale definito dalle p variabili osservate è data da:

1

d

= Σi |x

-x

|w

ed è particolarmente appropriata quando le variabili sono su scala ordinale. Rispetto alla distanza euclidea, la distanza media assoluta non è invariante rispetto a traslazioni o a rotazioni degli assi coordinati.

Scelta di un’opportuna procedura di raggruppamento delle entità

Principalmente, esistono due differenti tipi di algoritmi di classificazione: quelli gerarchici, suddivisi in agglomerativi e in divisivi, e quelli non gerarchici.

algoritmi gerarchici: ogni gruppo fa parte di un gruppo più ampio, il quale è contenuto a sua volta in uno di ampiezza maggiore e così in progressione fino al

gruppo che contiene l’intero insieme di unità analizzate. Gli algoritmi gerarchici si suddividono in:

aggregativi: Gli algoritmi gerarchici aggregatavi assumono come situazione di partenza una configurazione in cui ciascuna unità costituisce un gruppo a sé stante. Se dunque le unità osservate sono in numero pari ad n, si parte da n gruppi formati da una sola unità per procedere alla aggregazione dei due gruppi meno dissimili. Il risultato è una ripartizione delle n unità in n - 1 gruppi, di cui n - 2 composti da una sola unità ed uno composto da due. Il processo descritto viene iterato per n -1 volte fondendo assieme di volta in volta i due gruppi meno dissimili, finché non si perviene alla riunione di tutte le n unità statistiche in un solo gruppo

divisivi (o scissori): quando l’insieme delle n unità, in n-1 passi, si ripartisce in gruppi che sono, ad ogni passo d’analisi, sottoinsieme di un gruppo formato alla stadio precedente, e che termina con la situazione in cui ogni gruppo è composto da una unità.

algoritmi non gerarchici: in questo caso è necessario conoscere a priori il numero di cluster che si vogliono ottenere ed i centroidi (vettori contenenti i valori medi delle p variabili) iniziali di tali cluster. L’algoritmo procede in maniera iterativa cercando di ottenere la migliore classificazione degli elementi secondo il numero di classi prestabilito: ad ogni iterazione dispari vengono accorpati i due cluster più vicini mentre ad ogni interazione pari viene separato il cluster più disomogeneo. Si procede poi al calcolo dei centroidi fino a quando lo spostamento dei centroidi da un’iterazione all’altra diventa infinitesimale. Le procedure di analisi non gerarchica si suddividono in due categorie a seconda che generino partizioni, ossia classi mutamente esclusive,o classi sovrapposte, per le quali si ammette la possibilità che un elemento appartenga contemporaneamente a più cluster.

Gli algoritmi gerarchici non necessitano della definizione a priori del numero di cluster che si vuole ottenere e risultano molto onerosi e poco efficienti dal punto di vista computazionale. Inoltre, sono fortemente influenzati da outlier.

Nel caso di database di elevate dimensioni, gli algoritmi non gerarchici risultano estremamente più efficienti e meno influenzati da valori anomali inoltre, essendo non

monotoni, che permettono che un’unità statistica, inizialmente inserita in un cluster, possa modificare il proprio gruppo di appartenenza durante il processo iterativo. Gli algoritmi gerarchici aggregativi comprendono al loro interno:

metodo della media di gruppo metodo del centroide

metodo della mediana metodo del legame singolo metodo del legame completo metodo della media ponderata metodo di Ward

metodo flessibile di Lance e Williams.

Tali algoritmi si differenziano unicamente per il diverso criterio che regola la valutazione delle distanze tra i gruppi ai fini delle successive aggregazioni. Nel caso del metodo del legame singolo, ad esempio, tale distanza è posta pari alla più piccola delle distanze istituibili a due a due tra tutti gli elementi dei due gruppi; in quello del legame completo, alla maggiore di tali distanze; in quello del legame medio, al valor medio aritmetico di tutte le distanze tra gli elementi. Quando si applica il metodo del centroide vanno determinati i vettori (centroidi) contenenti i valori medi delle p variabili, gruppo per gruppo, e la distanza tra i gruppi viene assunta pari alla distanza tra i rispettivi centroidi. Vedremo più avanti la trattazione specifica di questi metodi.

Gli algoritmi gerarchici divisivi, invece, comprendono al loro interno: metodo di analisi k-means

metodo basati sulla distanza tra centroidi.

Algoritmi gerarchici aggregativi

Per effettuare un’analisi agglomerativa si segue un procedimento iterativo:

data una matrice simmetrica di prossimità tra n entità (si può trattare di entità singole, soprattutto all’inizio del processo, o da gruppi composti da più unità), si individua la coppia di entità che sono più prossime e con queste si costituisce un gruppo, al cui interno gli oggetti hanno distanza, che si assume nulla. Il modo in cui si calcola la distanza tra il gruppo e le rimanenti entità dipende dal criterio di

aggregazione prescelto, che può consistere nel metodo della media di gruppo, del centroide, ecc

per aggregare un’altra entità, si individua nella matrice di prossimità, che è ora di ordine n-1, l’entità più prossima. Si formerà in tal modo un altro cluster e si ricalcoleranno le distanze tra il gruppo formato e i rimanenti oggetti

l’individuazione dell’entità più prossima e il ricalcolo delle distanze si ripetono finché tutte le unità rientrano in un unico gruppo.

Date tre entità i, j e k di numerosità rispettivamente nh, nk, nl, le tecniche di analisi gerarchica aggregative prevedono di utilizzare la matrice delle distanze per trovare la coppia di elementi i e j che sono più vicine a formare così il primo cluster. Successivamente si ricalcala la matrice di dissomiglianze sostituendo le righe e le colonne relative ai gruppi i e j con una riga e una colonna di distanze dk(i,j) tra il gruppo (i,j) e il gruppo k.

Il calcolo della distanza dk(i,j) tra l’entità k e il gruppo (i,j) può essere effettuato mediante vari criteri: