Algoritmi di clustering e correlazione: una panoramica

Paolo Caressa

20 giugno 2012

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 1/ 16

Sommario

1 Indipendenza

2 Correlazione lineare

3 PCA

4 Intraclass correlation

5 Clustering

6 k-means clustering

7 Density based clustering

8 Subspace clustering

9 Correlation clustering

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 2/ 16

Indipendenza

Abbiamo a che fare con concetti probabilistici.

Indipendenza di eventi

Se A e B sono due eventi qualsiasi, diciamo che sono indipendenti se laprobabilita P(B) di verificarsi di B non dipende dal verificarsi o menodell’evento A, e viceversa. In formule: P(A ∩ B) = P(A) · P(B).

Utilizzando il concetto di probabilita condizionata P(A|B), la probabilitadi A dato B, allora l’indipendenza equivale a P(A|B) = P(A).

Indipendenza di variabili aleatorie

Una variabile aleatoria X (in soldoni un insieme di numeri associati aeventi) e indipendente da un’altra Y se sono indipendenti gli eventi{X ≤ a} e {Y ≤ b} per ogni a, b ∈ R. L’espressione matematica rigorosae in termini di distribuzioni, etc.

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 3/ 16

Correlazione lineare

Se X e una variabile aleatoria, per esempio una serie storica di rilevazioninumeriche o da un dataset, possiamo calcolarne la media E(X ), lavarianza Var(X ) = E(X 2)− E(X ), la deviazione standard σX =

√Var X .

Correlazione di due variabili X , Y

ρXY =E[X − E(X )]E[Y − E(Y )]

σXσY

La correlazione misura l’indipendenza lineare fra due variabili

Indipendenza =⇒ ρXY = 0

ρXY = 0 6=⇒ Indipendenza

Nel caso di n variabili X1, ..., Xn le correlazioni ρXiXjformano la matrice di

correlazione

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 4/ 16

PCA: Principal Component Analysis

L’Analisi per Componenti Principali viene utilizzata per costruire, a partireda un insieme di variabili che possono essere correlate, un insieme divariabili linearmente scorrelate (cioe la cui correlazione lineare sia nulla),chiamate componenti principali, ordinate secondo la varianza del dato.

Si tratta di rappresentare le variabili come dimensioni di uno spaziocartesiano, e di trasformare lo spazio con una trasformazione ortogonale(cioe che preserva le distanze) in modo che nel nuovo sistema dicoordinate abbia le componenti principali come assi cartesiani.

La PCA puo essere usata per scoprire correlazioni lineari, uniformi e globaliin un insieme di dati.

Come nel caso della correlazione, la PCA e un metodo classico dellastatistica (inventato agli inizi del Novecento).

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 5/ 16

ICC: Intraclass Correlation

La intraclass correlation e un metodo della statistica descrittiva checonsente di misurare quanto sono correlati fra loro gli elementi di unsingolo gruppo rispetto a una data categorizzazione di un dataset.

Intraclass correlation

ICC =σ2e

σ2e + σ2c

dove σ2e e la varianza fra gli elementi di una stessa classe, e σ2c e lavarianza fra tutti gli elementi.

Il calcolo delle varianze in questa formula costituisce un problema nonbanale: un approccio utilizza la metodologia ANOVA (ANalysis OfVAriance). Approcci diversi possono condurre a risultati diversi!!!

In questo caso la correlazione che viene analizzata e fra eventi gia inclusiin una stessa classe: all’opposto abbiamo la scoperta di correlazioni fraeventi non categorizzati, ovvero la scoperta delle classi stesse.

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 6/ 16

Clustering

Un clustering di un insieme di eventi, oggetti, etc. e la suddivisione inclassi fra questi oggetti in base a un criterio di somiglianza: se non e datoun criterio a priori, il clustering consiste nel determinare delle classi in basealle relazioni statistiche che possono esistere fra i dati, una volta chequesti siano stati codificati numericamente.

In data mining esistono moltissimi algoritmi di clustering, a seconda degliambiti e degli scopi.

Il clustering e la correlazione sono concetti distinti ma collegati: inparticolare partizionare un insieme di eventi in base a classi di correlazione(per esempio se sono correlati per piu di un certo valore fissato) fornisceun criterio di clustering. All’opposto, il risultato di un clustering puo esserevalidato con una intraclass correlation.

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 7/ 16

k-means clustering

Un k-means clustering consiste nel determinare, per un insieme di dati, nosservazioni in k classi distinte, stimando che una osservazione appartienea una classe in base a un criterio di similarita basato sulla vicinanza allamedia. Lo spazio degli eventi risulta in questo modo partizionato da undiagramma di Voronoi.

Definizione di k-mean cluster

argmins∈S

k∑i=1

∑x∈s‖x − µi‖2

dove S = {S1, ...,Sk} sono le classi e µi la media dei valori nella classei-esima Si .

Il problema e NP-completo!!! Tuttavia esistono algoritmi euristicicomputazionalmente efficienti per stimare la k-mean.

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 8/ 16

k-means clustering

Una k-means clustering

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 9/ 16

Density based clustering

I metodi di clustering basati sulla densita non partizionano in modo esattosulla base di una distanza (come nel caso k-means) ma si basano sulladensita di accumulazione dei punti nello spazio.

DBSCAN (1996)

Questo algoritmo considera come appartenenti a uno stesso clusterelementi la cui distanza differisca per meno di un ε fissato: in pratica seall’interno di un certo raggio sono racchiusi dei punti, si considerano partedi un medesimo cluster.

I punti di forza di DBSCAN sono la sua riproducibilita (algoritmo nonprobabilistico) e la sua complessita O(n log n) che lo rende implementabilein modo efficiente. Le debolezze sono che dipende dalla distanzaimpiegata e quindi la stima dell’ε non e immediata.

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 10/ 16

DBSCAN

Una DBSCAN clustering

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 11/ 16

OPTICS

Una OPTICS clustering (1999), un miglioramento di DBSCAN

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 12/ 16

Density based clustering

I metodi di clustering basati sui sottospazi vanno a ricercare i cluster nonsolo nello spazio ma in tutti i suoi sottospazi: uno stesso punto puo quindifare parte di piu cluster, che vivono in sottospazi diversi.

CLIQUE (2005)

Si tratta di un algoritmo che utilizza le tecniche dei density basedclustering sui sottospazi di dimensione massimale rispetto a questaproprieta.

CLIQUE e particolarmente adatto per dati di dimensione alta, dove imetodi di densita performano male.

Un algoritmo dello stesso tipo e SUBCLU (2004) che estende DBSCANalla ricerca di cluster in sottospazi di dimensione distinta.

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 13/ 16

Correlation Clustering

Un correlation clustering si propone di raffinare il clustering utilizzando lacorrelazione come criterio guida invece che la distanza.

4C: Computing Correlation Connected Clusters: (2004)

Si tratta di un algoritmo che combina PCA e DBSCAN per ottenerecluster di oggetti che sono fra loro correlati senza doversi limitare aconsiderare correlazioni globali.

In soldoni, 4C correla localmente secondo le componenti principali, edetermina il concetto di “localita” in base all’analisi di densita tipica diDBSCAN.

Da non confondere con l’analogo concetto (correlation clustering) di teoriadei grafi, che consiste nel cercare il numero ottimale di cluster dando pernote le relazioni di correlazione: c’e un legame ma sono algoritmi diversi.

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 14/ 16

4C clustering

Comparazione di DBSCAN e 4C

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 15/ 16

Algoritmi di clustering e correlazione: una panoramica

Domande/Suggerimenti???

Grazie per l’attenzione!!!

Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 16/ 16