La Cluster Analysis è un insieme di tecniche statistiche che hanno come obiettivo la costruzione di gruppi di unità tali per cui siano massime l'omogeneità all'interno dei gruppi e la differenza tra i gruppi, in altri termini che gli oggetti all'interno di un cluster si assomiglino tra loro mentre oggetti in cluster diversi siano dissimili.

In linea generale, per costruire dei gruppi di unità, è necessario:

• definire i caratteri rispetto a cui effettuare il raggruppamento delle unità,
• definire una misura del grado di diversità tra le coppie di unità,
• scegliere un algoritmo con cui procedere alla ricerca dei cluster.

La classificazione più diffusa dei metodi di cluster è basata sull'algoritmo e ,li distingue in:

• metodi gerarchici
• metodi non gerarchici.

In questo documento verranno trattate alcune procedure di S-Plus specificatamente sviluppate per la cluster analysis, in particolare verranno affrontati i seguenti argomenti:

Una volta scelte le variabili rispetto alle quali procedere alla costruzione dei gruppi, il primo passaggio è definire un criterio rispetto a cui misurare quanto due unità sono simili in riferimento a tutti i caratteri prescelti.

Tradizionalmente viene utilizzata la matrice di distanza, costruita su variabili continue ed utilizzando diverse misure della distanza (euclidea, manhattan,…).

La procedura daisy costruisce una matrice detta di dissimilarità, utilizzando sia variabili continue sia variabili categoriche (binarie, ordinali o nominali)-

Indichiamo con

la matrice n oggetti x p variabili dei dati

la matrice nxn di dissimilarità

dove

è la misura di dissimilarità tra gli oggetti i e j.

Nel caso di queste variabili è necessaria una standardizzazione dei dati per evitare la

dipendenza del valore dell’unità di misura delle variabili. Per il calcolo della misura

standardizzata, detta z-score, è conveniente fare uso della deviazione assoluta media:

deviazione assoluta media

dove

z-score

La deviazione assoluta media è più robusta della deviazione standard, infatti non è elevato al quadrato, riducendo i problemi dovuti a outliers

Per misurare la similarità tra due oggetti i cui attributi sono variabili continue, viene utilizzata normalmente una funzione-distanza.

dove e sono due oggetti p-dimensionali, e dove q è un intero positivo.

Questa distanza permette di incrementare o decrementare il peso assegnato a dimensioni lungo le quali gli oggetti risultano molto diversi:

E' il caso in cui, nella distanza di Minkowski, q=1

E' il caso in cui, nella distanza di Minkowski, q=2

E' il tipo di distanza più utilizzata, e rappresenta la distanza geometrica di un punto in uno spazio multi-dimensionale. Sono valide le seguenti proprietà:

Sono variabili per cui sono possibili due stati: "0" oppure "1". Si distinguono in

• simmetriche se i due stati sono equivalenti, cioè se non vi sono preferenze su quale stato debba essere codificato con "1";
• asimmetriche, se invece gli stati della variabile non sono equivalenti

nel caso di variabili binarie, per determinare la similarità di due oggetti si può ricorrere ad una tabella di contingenza:

Il grado di similarità viene poi calcolato mediante un coefficiente di corrispondenza:

coefficiente di Corrispondenza Semplice per variabili binarie simmetriche

coefficiente di Jaccard per variabili binarie asimmetriche

Sono variabili che possono assumere più stati, ad esempio: "bianco", "rosso", "blu", e possono essere considerate come una generalizzazione delle variabili binarie da 2 ad n stati.

Per determinare la similarità tra due oggetti si può calcolare un coefficiente di corrispondenza semplice:

dove p = numero di variabili e m = numero di corrispondenze; in alternativa si può creare una nuova variabile binaria per ciascuno degli m stati nominali.

Una variabile ordinale è in pratica una variabile nominale con un ordine tra i valori assunti

Per misurare la similarità nel caso di variabili ordinali, queste vengono trattate come continue:

1. si assegna un rango numerico ad ogni valore assunto
2. si sostituiscono le nominali con i rispettivi ranghi numerici
3. si mappano i valori di ciascuna variabile sull’intervallo [0, 1] rimpiazzando l’i-esimo valore della f-esima variabile con
4. si calcola la dissimilarità tra variabili ordinali come se fossero variabili numerico di tipo continuo

Si tratta di variabili numeriche misurate su una scala non lineare di valori, ad esempio su una scala esponenziale. Può quindi risultare problematico misurare le distanze a causa della distorsione della scala, potremo infatti avere distanze piccole tra valori consecutivi vicini allo zero e distanze grandi tra valori lontani dallo zero.

Per ovviare a questo problema di scala si può:

• applicare una trasformazione (logaritmica) in modo da trasformarli in variabili continue,
• considerare i valori come ordinali, assegnando un rango e applicare la distanza usata per variabili numeriche di tipo continuo.

Nella pratica capita però che vengano osservate, per ciascuna unità/oggetto, una molteplicità di caratteri espressi in variabili di tipi diversi. Per determinare la misura di similarità tra due oggetti caratterizzati da un set misto di variabili si può utilizzare una formula che combini i loro effetti.

[1]

dove:

= contributo della variabile a e che dipende dal tipo di variabile

• se binaria o nominale: se , e altrimenti
• se continua (distanza assoluta normalizzata)
• se ordinale o ratio-scaled: vengono calcolati i ranghi e

e dove:

= peso della variabile , con:

• se o sono missing
• se e la variabile e binaria asimmetrica
• 

La sintassi è la seguente:

dove:

L'algoritmo comunemente utilizzato per la costruzione di gruppi, nell'ambito dei non gerarchici, è quello delle k-means. Lo ricordiamo brevemente: fissato k, ovvero il numero di cluster che si vogliono ottenere, i) vengono ripartiti gli n oggetti casualmente nei k gruppi, ii) vengono calcolati i punti medi dei cluster (centroidi), iii) viene assegnato ciascun punto al cluster il cui centro risulta essere il più vicino, iv) si calcolano nuovamente i centroidi (punti medi)dei gruppi, v) si ripete l'operazione ripartendo dal secondo punto, e si termina quando l'assegnamento dei punti non cambia più.

Il partizionamento attorno ai medoidi, detto anche k-medoids, si basa invece sulla ricerca di oggetti rappresentativi all'interno dei dati. Questi punti, detti medoidi, sono determinati in modo tale che la dissimilarità totale di tutti i punti dai medoidi più vicini sia minima. Si tratta quindi di trovare l'insieme dei medoidi che minimizza la funzione obiettivo:

[2]

L'algoritmo è sostanzialmente diviso in due fasi:

fase 1: BUILD in cui vengono individuati i medoidi iniziali

• è l'oggetto per cui è minimo
• è l'oggetto che riduce il più possibile la funzione obiettivo
• …..

fase 2: SWAP, in cui si verifica se sono possibili delle modifiche dei medoidi:

finché il processo non converge si considerano tutte le coppie di oggetti con e e si sostituisce se ciò comporta una diminuzione della funzione obiettivo.

Confrontando gli algoritmi k-means e k-medoid si può notare che:

Dopo avere calcolato per tutti i cluster consideriamo la minore:

Calcoliamo quindi:

= silhouette width dell'unità i

Il valore di è sempre compreso tra -1 e 1, per cui può essere interpretato come segue:

Sulla base dei silhoutte width è possibile determinare la loro media complessiva che fornisce un'indicazione sulla bontà globale della cluster (detto anche silhouette coefficient SC), oppure la media per singolo gruppo che invece è indicativa della coesione del cluster.

I silhoutte width possono inoltre essere rappresentati graficamente tramite un istogramma detto silhoutte plot.

dove:

tess.pam <- pam(tess.diss,3,diss=T)

plot(tess.pam)

I grafici prodotti sono 2, il primo è un silhouette plot

Il silhouette plot è utile per decidere il numero ottimale di cluster, infatti si può eseguire la procedura più volte con valori diversi di k e confrontare i risultati del silhouette plot, ed in particolare la silhouette width media (SC).

I valori di SC possono essere utilizzati per valutare il grado di "intensità" della struttura di raggruppamento, in particolare avremo che:

intervallo di SC

0.71 - 1.00 è stata trovata una struttura forte

0.51 - 0.70 è stata individuata una struttura plausibile

0.26 - 0.50 la struttura è debole

< 0.26 non è stata individuata alcun struttura

Il secondo grafico è il clusplot che riporta su di un piano cartesiano i punti dei cluster.

In particolare viene utilizzata una procedura di multidimensional scaling (MDS) sulla matrice di dissimilarità, vengono quindi utilizzate le prime due componenti per visualizzare rispetto ad esse i punti. Nel grafico di esempio le prime due componenti spiegano oltre l'84% della variabilià. I gruppi vengono inoltre evidenziati da un ellisse e da marcatori diversi. Anche questo grafico può essere utile per valutare la validità della cluster elaborata, infatti in presenza di valori alti della variabilità spiegata da parte delle prime due componenti, è possibile capire se siamo in presenza di una struttura di raggruppamento più o meno forte.

La sintassi è la seguente:

clara(x, k, metric = "euclidean", stand = F;
samples = 5, sampsize = 40 + 2 * k)

Il vantaggio della procedura clara risiede nel fatto che può gestire data-set più grandi rispetto a pam, ma di contro è da precisare che la sua efficienza dipende dalla dimensione dei campioni estratti e che una "buona" cluster basata su un campione non necessariamente costituisce una "buona" cluster del collettivo da cui è estratto.

Le procedure di cluster viste in precedenza conducono all'assegnazione di un punto ad un unico gruppo. Quindi se un oggetto si trova tra due gruppi viene assegnato ad uno solo di essi. Con una cluster sfocata ogni punto viene invece associato un coefficiente di appartenenza a ciascun gruppo. Se indichiamo con il coefficiente di appartenenza di ciascun punto i a ciascun gruppo v, tale coefficiente dovrà essere tale per cui:

In S-Plus è implementata la funzione di fuzzy clustering denominata fanny. La sintassi è la seguente:

Un oggetto fanny ha le seguenti proprietà:

Anche per la procedura fanny vengono prodotti due output grafici, il silhouette plot ed il cluster plot.

Come si può osservare vi è differenza tra i gruppi identificati precedentemente con pam e quelli ottenuti con fanny.

In particolare la diversificazione si registra nel gruppo 2 ottenuto con fanny

Più in dettaglio si può osservare che 2 unità classificate nel gruppo 1 con pam cadono invece nel gruppo 2 secondo il metodo dei nearest crisp clustering di fanny (che corrisponde alla cluster 3 secondo la partizione pam). Come si può notare dalla tabella seguente sono unità per le quali il miglior vicino è il cluster 3, che presentano coefficienti di appartenenza molto vicini ed inoltre forniscono i valori più bassi di silhouette width all'interno del loro gruppo.

Vi sono altri 15 casi classificati nel gruppo 2 secondo il metodo dei k-medoids, che ricadono invece nel cluster 2 secondo fanny (corrispondente sempre al cluster 3 pam). Anche in questo caso si tratti di unità particolarmente "sfumate", la loro appartenenza al gruppo 2, secondo la silhouette width, è molto bassa ed il coefficiente di appartenenza ai due cluster in esame è sostanzialmente simile, oltre a presentare valori significativi