Blog divulgativo sulla matematica applicata

Clustering [Parte 2]

Ed eccoci di nuovo qui, come promesso, con la seconda parte un pochino più “tecnica” riguardante la cluster analysis.

Dove eravamo rimasti? Ah sì, avevamo cercare di capire quale fosse l’idea sottostante l’analisi dei gruppi (la c.d. cluster analysis per l'appunto) e come venga in realtà applicata anche in azioni semplici e quotidiane (per chi si fosse perso la prima parte può recuperarla  cliccando qui).

Facendo un rapido recap potremmo così sintetizzare: la cluster analysis è un metodo statistico multivariato (in quanto considera più informazioni relative alla stessa unità statistica) il quale partendo da una matrice dati permette di classificare le unità osservate in gruppi omogenei. Con il termine omogenei si intende un alto livello di coesione interna (le unità assegnate a un medesimo gruppo devono essere tra loro simili) e un elevato grado di separazione esterna (i gruppi devono essere il più possibile distinti). L'immagine che segue esplicita visivamente tale concetto.

download

Tale tecnica statistica si applica per effettuare una ridimensionamento della matrice dati di lavoro, passando da n unità statistiche a g gruppi (e g<<n) con il vantaggio d’una notevole parsimonia nella descrizione e d’una interpretazione più semplice. E’ un metodo cosiddetto “esplorativo” in quanto non è noto a priori se esistono effettivamente dei gruppi omogenei all’interno del data set (o della popolazione) considerato.

Mentre nella prima parte è stato introdotto il concetto di cluster analysis anche tramite un esempio concreto di possibile applicazione nella realtà, in questa seconda parte verrà illustrata la teoria sottostante.

Partiamo dal presupposto che una stessa unità statistica può essere classificata in modi diversi. Nell'immagine che segue, per esempio, si può vedere come ci siano delle sovrapposizioni (intersezioni) tra i diversi cluster individuati; con parole meno tecniche, vi sono alcuni casi in cui un "pallino blu" non appartiene solo al cluster blu ma anche al cluster viola e al verde. 

cluster_analysis

La prima domanda, pertanto, che ci si deve porre di fronte a un problema classificatorio è: “Per quale motivo si vuole effettuare una classificazione delle unità considerate?”

Una volta definito lo scopo della classificazione, sarà necessario proseguire con una serie di scelte, che passiamo ad illustrare.

 Scelta delle variabili

Dalle finalità per cui si decide di effettuare una cluster analysis discende la scelta delle variabili. A questo riguardo la metodologia statistica è di scarso aiuto…

Sono le conoscenze specifiche di chi affronta il problema che indirizzeranno la scelta. In generale la classificazione dovrebbe fondarsi su tutti gli aspetti che si ritengono importanti per gli scopi prefissati, tenendo sempre a mente il trade-off tra interpretabilità e qualità della classificazione ottenuta.

Scelta della distanza (o indice di similarità)

Per poter individuare correttamente gruppi di unità omogenee, occorre poter misurare quanto due unità statistiche sono fra loro simili. A questo punto risulta fondamentale introdurre il concetto di “prossimità” tra due unità statistiche, intendendo sia il concetto di rassomiglianza sia quello antitetico di diversità.

Tali indici vengono distinti a seconda che essi di applichino a fenomeni quantitativi (distanze) oppure a qualitativi (indici di similarità).

similarita

Un indice di similarità assume valori nell'intervallo chiuso [0,1].

 Nel caso si stesse lavorando con una matrice dati con n unità statistiche e p variabili quantitative non si parlerebbe più di similarità tra le unità ma sarebbe possibile, e appropriato, introdurre il concetto di distanza (per approfondire ulteriormente si suggerisce di leggere  questa serie di articoli di questo blog) .

distanza

Le quattro proprietà che definiscono la distanza non sono tra loro indipendenti: si può dimostrare che se valgono le proprietà di identità e di disuguaglianza triangolare sussistono anche le proprietà di non negatività e di simmetria.

cluster5

In questa clusterizzazione, ad esempio, sono state proiettate, disegnate, tutte le possibili distanze fra un cluster e un altro prendendo come riferimento i punti medi (anche detti centroidi) dei diversi cluster.

Calcolando la distanza,o l’indice di similarità, tra ciascuna delle possibili coppie d’elementi si ottiene la cosiddetta matrice delle distanze, di dimensione (n x n), simmetrica e semi-definita positiva, la quale contiene le misure di prossimità di tutte le coppie di unità.

matrice

Chi effettua l’analisi dovrà quindi scegliere la distanza, o l’indice di similarità (a seconda del tipo di variabili con il quale sta lavorando) che intende utilizzare. Tale scelta condizionerà i risultati della classificazione, poiché variando il tipo di funzione considerata potrebbe cambiare l’ordinamento delle coppie di unità e di conseguenza differirebbero anche i gruppi di unità considerate omogenee.

La scelta della distanza più opportuna dovrà basarsi sulle caratteristiche delle singole metriche.

In questo contesto ci limiteremo a presentare, come esempio, la cosiddetta distanza di Minkowski di ordine k1:

minkowski

La distanza di Minkowski è una delle metriche più utilizzate, in quanto gode di due importanti proprietà utili nell'analisi di dati statistici:

  1. è funzione non crescente dell’indice k, quindi per esempio con riferimento alla stessa matrice dati di partenza la matrice delle distanze della città a blocchi avrà elementi ordinatamente non minori della matrice della distanza euclidea;
  2. la distanza di Minkowski è invariante per traslazione delle variabili, e quindi la distanza rimane invariata anche quando viene calcolata invece che sulle variabili originali sui rispettivi scostamenti dalla media.

Un’altra distanza ampiamente usata nei problemi di clustering è la cosiddetta distanza di Mahalanobis, ma lasceremo ai lettori interessati il piacere di indagare da soli su tale metrica ;)

Scelta del metodo di formazione dei gruppi

Esistono vari metodi che permettono di ottenere una partizione delle n unità statistiche considerate (si definisce partizione d’un insieme di elementi una suddivisione in sottoinsiemi due a due disgiunti e la cui unione coincide con l’insieme di partenza). Tali metodi seguono la seguente classificazione:

  • clustering esclusivo (hard clustering): ogni elemento può essere assegnato ad uno e ad un solo gruppo. I clusters risultanti, quindi, non possono avere elementi in comune. A sua volta si distingue in:
    • clustering partizionale (detto anche non gerarchico, o k-clustering), in cui per definire l'appartenenza ad un gruppo viene utilizzata una distanza da un punto rappresentativo del cluster avendo prefissato il numero di gruppi della partizione risultato. Tali modelli si fondano solitamente sull’esecuzione d’una procedura iterativa;
    • clustering gerarchico, consentono di ottenere una famiglia di partizioni con un numero di gruppi da n a 1, partendo da quella banale in cui tutte le unità sono distinte per giungere a quella, sempre banale, in cui tutti gli elementi sono riuniti in un unico gruppo. Possono essere di tipo:
      • aggregativo: partono dal basso e procedono a riunificazioni successive delle unità statistiche;
      • scissori: procedono esattamente al contrario
  • clustering non-esclusivo (soft clusteringfuzzy clustering): un elemento può appartenere a più cluster con gradi di appartenenza diversi.

classificazione-algoritmi-clustering

La scelta di quale metodo applicare solitamente è influenzata da tre fattori principali:

  1. tipo di variabili con cui si lavora: quantitative, qualitative, dicotomiche, miste.
  2. velocità di convergenza dell'algoritmo richiesta
  3. qualità della soluzione desiderata

Criterio di valutazione della partizione ottenuta

Dopo aver ottenuto la famiglia di partizioni (se applicato un metodo gerarchico) oppure una singola partizione (se applicato un metodo non gerarchico) occorre valutare la classificazione ottenuta, al fine di verificare se essa soddisfa le condizioni di coesione interna e separazione esterna. Occorre inoltre tener presente il trade-off tra il numero dei gruppi e l’omogeneità all’interno degli stessi: riducendo il numero dei gruppi si ottiene una classificazione più sintetica (e quindi generalmente più utile a fini operativi) ma si deve “pagare un prezzo” in termini di maggiore variabilità nei gruppi in quanto saranno state aggregate unità maggiormente diverse tra loro. La partizione con il numero ottimo di gruppi sarà quella che meglio riesce a contemperare queste opposte esigenze di sintesi delle unità in classi e di coesione interna dei gruppi.

Come si potrà notare, le numerose scelte che deve effettuare il ricercatore introducono forti elementi di soggettività nei risultati, i quali potrebbero quindi essere sottoposti a critiche. Tuttavia una classificazione d’un insieme di unità statistiche può ritenersi valida quando essa rimane approssimativamente stabile al variare degli algoritmi utilizzati per ottenerla, poiché in tal caso essa riflette una struttura realmente presente nei dati multidimensionali e non generata semplicemente dalla particolare procedura utilizzata.

Grazie alla definizione di particolari indici è possibile misurare numericamente la stabilità d’una classificazione al variare dei caratteri analizzati e delle opzioni scelte per ottenerla. In altre parole, date due, o più, differenti partizioni d’un medesimo insieme di n unità statistiche, è possibile valutare in che misura tali classificazioni differiscono tra loro.

Tale somiglianza può essere misurata a partire dal confronto tra le coppie di unità statistiche; al riguardo si ricorda che, dati n elementi, i confronti possibili sono pari a:

n(n-1)/2

Se si considera una sola partizione, a ciascuna delle n(n-1)/2 coppie di unità può essere associata una variabile indicatrice, che assume il valore

  • 1 se la coppia è costituita da elementi appartenenti allo stesso gruppo nella partizione
  • 0 se la coppia è costituita da elementi appartenenti a gruppi distinti nella partizione

Considerando due partizioni distinte del medesimo insieme di n elementi, si possono definire le medesime variabili indicatrici, andando a considerare il numero di coppie che appartengono, o meno, allo stesso gruppo in entrambe le partizioni.

Si definisce Indice di Rand per il confronto tra due partizioni P e P*, costituite da k e k* gruppi, l’espressione

RP;P* = (c11 + c00)/[n(n-1)/2]

dove le quantità c11 e c00 indicano il numero di coppie d’elementi “trattate” in modo analogo nelle due partizioni, fornendo una misura dell’accordo esistente tra P e P*.

Questa definizione non si dimostra appropriata a fini di calcolo. Innanzitutto essa richiede l’effettuazione di tutti i confronti a coppie, il cui numero si rivela ben presto disagevole da gestire al crescere dei valori di n. Inoltre i principali packages statistici non forniscono in genere nel loro output alcuna indicazione su tali confronti. Per fortuna, una procedura di calcolo così laboriosa in pratica non è necessaria, poiché è possibile riscrivere l’indice RP;P* in funzione degli elementi di P e P*. Per ottenere ciò occorre costruirsi la seguente tabella a doppia entrata:

tabelladoppiaentrata
L’indice di Rand è allora esprimibile nella seguente forma, equivalente alla precedente:

rand

L’indice assume valore 1 se le due partizioni sono identiche e valore 0 se tutte le coppie d’elementi appartenenti ad un gruppo in un partizione sono assegnate a gruppi diversi nell'altra.

*  *  *

Non so quanti di voi siano riusciti a leggere fino a questo punto. Mi rendo conto che tutte queste formule assieme potrebbero spaventare :) ma prendendoci confidenza non sono poi così malvagie ;) Quasi quasi mi sbilancerei affermando che la panoramica fornita a riguardo di una delle principali tecniche di analisi dati è piuttosto ampia ed esaustiva, riuscendo anche a dettagliare qualche dettaglio più articolato.

Noi ci rincontreremo prossimamente, questa volta con un argomento tutto nuovo... ;)

KEEP IN TOUCH!

CC BY-NC-SA 4.0
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Similar posts

Nessun commento ancora

Lascia una risposta

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *

È possibile utilizzare questi tag ed attributi XHTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Iscriviti alla nostra newsletter

Resta aggiornato sui nostri post e su quello che facciamo.

Canale Telegram dedicato alla Matematica

Iscriviti sul nostro canale Telegram

MIA15 - Nomination

Rimani aggiornato sui più interessanti articoli di divulgazione matematica e non solo!

Seguici su Twitter

Tag Cloud

Partecipa all’indagine “Io e la Matematica”

Clicca sull'immagine sottostante per rispondere al breve e anonimo questionario:

MIA15 - Nomination

Conviditi con i tuoi contatti questo link!

Grazie per il sostegno ai #MIA2015

Grazie a tutti per averci votato ai "Macchia Nera Awards 2015" nella categoria "Miglior Sito Tecnico-Divulgativo".

Siamo arrivati in finale grazie al vostro sostegno!

MIA15 - Nomination