Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Massimo Aria » 10.Introduzione alla Cluster Analysis


Introduzione

Il termine classificazione viene utilizzato per varie attività che si possono ricondurre alla gestione delle conoscenze.

L’attività di classificazione è propria dell’essere umano. Molte classificazioni si incontrano nella vita quotidiana, nelle opere di riferimento come i trattati, i cataloghi, le collezioni, gli atlanti non necessariamente geografici e le opere enciclopediche. In questi raccoglitori di conoscenze si possono individuare molti esempi significativi di classificazioni e queste constatazioni mostrano che le classificazioni svolgono ruoli di grande importanza nella organizzazione e nella gestione delle conoscenze.

In statistica, con il termine classificazione si intende l’insieme delle attività che, facendo uso di un algoritmo di analisi dei dati, individuano una rappresentazione di alcune caratteristiche di una entità da classificare (oggetto o nozione) e le associano ad una etichetta classificatoria.

Metodi statistici di classificazione

Nell’ambito dei metodi statistici di classificazione si è soliti distinguere tra classificazione non supervisionata e classificazione supervisionata.

I primi, anche detti metodi di analisi dei gruppi (o clustering), ricercano negli oggetti una struttura appunto a gruppi che non esiste o almeno non è nota a priori.

I secondi (metodi di segmentazione) mirano ad individuare quali attributi determinano l’appartenenza di un oggetto all’uno o all’altro di G gruppi predefiniti.

Tale suddivisione trae ragione dal differente ruolo giocato dalle p variabili osservate sugli n oggetti da classificare.
Un ruolo simmetrico nel clustering, un ruolo asimmetrico nella classificazione supervisionata. Infatti in questo ultimo caso dei p caratteri misurati sugli oggetti, uno di essi gioca il ruolo di variabile discriminate o dipendente sintesi della classificazione degli oggetti nota a priori.
Obiettivo dell’analisi supervisionate è quindi spiegare come la conoscenza delle modalità assunte dalle n unità sulle restanti p-1 variabili (dette variabili esplicative) possa spiegare l’appartenenza ad uno o ad un altro dei gruppi.

La Cluster Analysis

L’Analisi dei Gruppi (Cluster Analysis, CA) consiste in un insieme di tecniche statistiche atte ad individuare gruppi di unità tra loro simili rispetto ad un insieme di caratteri presi in considerazione, e secondo uno specifico criterio.

L’obiettivo che ci si pone è sostanzialmente quello di riunire unità tra loro eterogenee in più sottoinsiemi tendenzialmente omogenei e mutuamente esaustivi.

Le unità statistiche vengono, in altri termini, suddivise in un certo numero di gruppi a seconda del loro livello di “somiglianza” valutata a partire dai valori che una serie di variabili prescelte assume in ciascuna unità.

Obiettivi della Cluster Analysis

La cluster analysis consente allora di pervenire ai seguenti risultati (Fabbris, 1997):

  • la generazione di ipotesi di ricerca, infatti per effettuare una analisi di raggruppamento non è necessario avere in mente alcun modello interpretativo;
  • la riduzione dei dati in forma (anche grafica) tale da rendere facile la lettura delle informazioni rilevate e parsimoniosa la presentazione dei risultati;
  • la ricerca tipologica per individuare gruppi di unità statistiche con caratteristiche distintive che facciano risaltare la fisionomia del sistema osservato;
  • la costruzioni di sistemi di classificazione automatica attraverso la definizione di un “classificatore accurato” che consenta di classificare nuove unità;
  • la ricerca di classi omogenee, dentro le quali si può supporre che i membri siano mutuamente surrogabili.

Obiettivi della Cluster Analysis (segue)

Operativamente, in ambito turistico, la cluster analysis può essere utilizzata, ad esempio da un operatore alberghiero, per l’identificazione di gruppi di turisti sulla base di:

  • comportamento nella fruizione del servizio alberghiero;
  • opinioni sul prodotto/servizio;
  • importanza assegnata a varie caratteristiche di un prodotto/servizio (segmentazione del mercato);
  • abitudini di spesa che delineano profili tipologici dei clienti;
  • ecc.

Fasi di una Cluster Analysis

L’applicazione della cluster analysis si articola in alcune fasi fondamentali che prescindono dallo specifico algoritmo scelto per l’analisi:

  1. La scelta delle variabili di classificazione.
  2. La scelta di una adeguata misura della dissomiglianza esistente fra le unità statistiche.
  3. La scelta dell’algoritmo di raggruppamento.

La scelta delle variabili di classificazione

La scelta delle variabili rispecchia essenzialmente le convinzioni e le idee del ricercatore, ed è una operazione che implica un grado molto alto di soggettività:

può capitare di non considerare variabili fortemente selettive
ed avere quindi una partizione in gruppi “sbagliata”

d’altra parte, l’inclusione di variabili dotate di una elevata capacità discriminante,
ma non rilevanti ai fini dell’indagine, può portare a risultati di scarso rilievo pratico.

La scelta della misura di dissomiglianza

I caratteri rilevati possono essere espressi in quattro distinte scale di misura:

  • Variabili qualitative: in nominali e ordinali.
  • Variabili quantitative: in scala per intervalli e per rapporti.

La definizione di un criterio per la misurazione della dissomiglianza tra le unità statistiche è il punto di partenza di qualunque analisi dei gruppi.

Infatti solo dopo aver definito cosa si intende per somiglianza o dissomiglianza tra due unità è allora possibile definire un algoritmo mirato alla costruzione di gruppi omogenei (somiglianti) di osservazioni.

Proprietà di un indice di dissomiglianza

La definizione di un indice di dissomiglianza si basa su alcune proprietà fondamentali.

Siano h e k due unità del collettivo in esame su cui sono state osservate p variabili X.
In uno spazio geometrico, questi possono essere intesi come due punti Ph e Pk corrispondenti ai vettori h e k contenenti le realizzazioni delle p variabili per le due unità considerate.

Allora si dice che la funzione gode delle seguenti proprietà se:

1) Non negatività

{\rm d(h}{\rm ,k)} \ge {\rm 0}

2) Identità

{\rm d(h}{\rm ,k)} = {\rm 0} se h=k

3) Simmetria

{\rm d(h}{\rm ,k)} = {\rm d(k}{\rm ,h)}

4) disuguaglianza triangolare

{\rm d(h}{\rm ,k)} \le {\rm d(h}{\rm ,e) + d(e}{\rm ,k)}

5) condizione di Krassner (o del triangolo isoscele)

{\rm d(h}{\rm ,k)} \le {\rm max}\left[ {{\rm (h}{\rm ,e); d(e}{\rm ,k)}} \right]{\rm }

Definizione della misura di dissomiglianza

Una misura di dissomiglianza che gode delle proprietà di non negatività, identità e simmetria prende il nome di indice di dissimilarità.

Si parla invece di distanza o di metrica nel caso di funzioni d() che rispettano, oltre alle prime 3 proprietà, anche la disuguaglianza triangolare.

Infine si definisce distanza ultrametrica una funzione di dissomiglianza che gode delle prime 3 proprietà e della condizione di krassner.

Indice di dissimilarità: tabella presenza/assenza

Nel caso di caratteri qualitativi dicotomici (in cui per ogni variabile si misura la presenza-assenza di un fenomeno, 1=presenza, 0=assenza), per ogni coppia di unità h e k, i due vettori di risposte relativamente alle p variabili osservate possono essere rappresentati in una tabella 2 x 2 come rappresentata in figura.

Le frequenze b e c segnalano gli aspetti di diversità tra le due unità statistiche considerate.
Le frequenze a e d indicano invece l’entità della rassomiglianza tra le due unità, ma il loro significato non è identico.
Infatti, la co-presenza d’un carattere costituisce sempre un aspetto che concorre a definire la similarità, mentre la co-assenza d’un fenomeno in alcuni casi può risultare di scarso o di nessun interesse ai fini della valutazione della rassomiglianza tra due unità.

Tabella di presenza/assenza per le unità h e k.

Tabella di presenza/assenza per le unità h e k.


Principali indici di dissimilarità

Indice di dissimilarità di Russel e Rao
é pari a 1 meno il rapporto tra il numero di co-presenze (a) e il numero totale di caratteri considerati (p).

Indice di dissimilarità di Jaccard
é pari a 1 meno il rapporto tra il numero di co-presenze (a) e il numero totale di caratteri con l’esclusione di quelli che manifestano co-assenze in h e k (a+b+c).

Indice di similarità di Sokal e Michener
é pari a 1 meno il rapporto tra il numero di caratteri che risultano uguali tra le due unità (a+d) e il numero totale di caratteri (p).

Distanza tra caratteri quantitativi

Nel caso di caratteri quantitativi, la formulazione della metrica di Minkowski ponderata:

{}_{\rm r}{\rm d}_{{\rm h}{\rm ,k}} = \left\{ {\sum\limits_{v = 1}^p {w_v \left( {\left| {x_{hv} - x_{kv} } \right|} \right)^r } } \right\}^{1/r}

consente di definire le principali misure distanza utilizzate in letteratura.

In particolare si fa riferimento alla:

  • Distanza euclidea.
  • Distanza city block.
  • Distanza di Chebichev.

Distanza euclidea

Fissando il grado r=2, la formulazione della metrica di Minkowski ponderata consente di definire la distanza euclidea.

{}_{\rm 2}{\rm d}_{{\rm h}{\rm ,k}} = \sqrt {\left\{ {\sum\limits_{v = 1}^p {w_v \left( {\left| {x_{hv} - x_{kv} } \right|} \right)^2 } } \right\}}

Essa corrisponde al concetto geometrico di distanza nello spazio multidimensionale.

La distanza euclidea è la tipica distanza fra due punti che si potrebbe misurare con un righello e che può essere ottenuta dall’applicazione ripetuta del teorema di Pitagora.

Distanza euclidea in uno spazio bidimensioanle.

Distanza euclidea in uno spazio bidimensioanle.


Distanze city block e di Chebichev

La distanza assoluta (r=1) (o city-block o distanza di Manhattan) è semplicemente la differenza media fra le dimensioni:

{}_{\rm 1}{\rm d}_{{\rm h}{\rm ,k}} = \left\{ {\sum\limits_{v = 1}^p {w_v \left( {\left| {x_{hv} - x_{kv} } \right|} \right)} } \right\}

consigliata in generale quando le variabili di classificazione sono su scala ordinale.

La distanza di Chebychev (r=infinito) può essere appropriata nei casi in cui si voglia definire due oggetti come “differenti” se essi sono diversi in ciascuna delle dimensioni:

{}_\infty {\rm d}_{{\rm h}{\rm ,k}} = \max \left| {x_{hv} - x_{kv} } \right|

Distanza tra caratteri qualitativi

Quando i dati di natura qualitativa, sono rappresentati in una tabella di contingenza, la distanza del Chi Quadrato rappresenta l’indice maggiormente utilizzato per misurare il grado di diversità tra le righe (o le colonne) della tabella.

Si considerino due modalità h e h’ di una variabile di riga di una tabella a doppia entrata. Siano j=1,…,K le modalità della variabile di colonna.
La distanza del Chi Quadrato fra le modalità h e h’ corrisponde alla distanza euclidea tra le due distribuzioni condizionate ponderate rispetto ai marginali di riga:

{}_\chi d_{h,h'}^2 = \sum\limits_{j = 1}^K {\left( {\frac{{n_{h,j} }}{{n_{h, + } }} - \frac{{n_{h',j} }}{{n_{h', + } }}} \right)^2 } \cdot \frac{n}{{n_{ + ,j} }}

Le misure illustrate precedentemente (metrica di minkowski) si calcolano su matrici di dati “individui x variabili” e, pertanto, esprimono una matrice di mutue distanze tra tutte le n unità statistiche mentre

la distanza del Chi Quadrato, calcolata su una tabella di contingenza,
esprime una mutua distanza fra gruppi di unità statistiche
che hanno in comune la stessa modalità di riga (o di colonna).

Algoritmi di raggruppamento

Una volta scelta la misura di dissomiglianza, si pone il problema di procedere alla scelta di un idoneo algoritmo di raggruppamento delle unità osservate.

La distinzione che normalmente viene proposta è fra:

  • metodi gerarchici che conducono ad un insieme di partizioni ordinabili (nidificate) secondo livelli crescenti.
    Esse infatti prevedono la individuazione di n partizioni ciascuna caratterizzata da un diverso numero G di gruppi (con G = 1,….,n) dove le partizioni individuate costituiscono una struttura gerarchica di raggruppamento;
  • metodi non gerarchici: forniscono un’unica partizione delle n unità in G gruppi, e G deve essere specificato a priori.

La scelta tra i due algoritmi dipende solitamente da due fattori:

  • la conoscenza a priori del numero dei gruppi G (necessaria per la scelta di un metodo non gerarchico).
  • Il numero di oggetti (unità) da raggruppare. I metodi gerarchici richiedono un costo computazionale che cresce esponenzialmente al crescere del numero di osservazioni. Quindi per matrici di elevate dimensioni si propenderà per un metodo non gerarchico viceversa si utilizzerà un metodo gerarchico.

Nella prossima lezione

Nella prossima lezione si affronteranno i seguenti argomenti:

  • Cluster analysis gerarchica.
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion