際際滷

際際滷Share a Scribd company logo

Algoritmi di clustering e correlazione: una panoramica

Paolo Caressa
Paolo Caressa

Le slide di una presentazione su alcuni concetti fondamentali relativi agli algoritmi di clustering e correlazione comunemente utilizzati nell'industria. 際際滷 presentate internamente alla CODIN s.p.a. nel giugno 2012.

1 of 16
Downloaded 12 times
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 la probabilit`a P(B) di veri鍖carsi di B non dipende dal veri鍖carsi o meno dellevento A, e viceversa. In formule: P(A B) = P(A) 揃 P(B). Utilizzando il concetto di probabilit`a condizionata P(A|B), la probabilit`a di A dato B, allora lindipendenza equivale a P(A|B) = P(A). Indipendenza di variabili aleatorie Una variabile aleatoria X (in soldoni un insieme di numeri associati a eventi) `e indipendente da unaltra Y se sono indipendenti gli eventi {X a} e {Y b} per ogni a, b R. Lespressione matematica rigorosa `e 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 rilevazioni numeriche o da un dataset, possiamo calcolarne la media E(X), la varianza Var(X) = E(X2) 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 lindipendenza lineare fra due variabili Indipendenza = XY = 0 XY = 0 = Indipendenza Nel caso di n variabili X1, ..., Xn le correlazioni Xi Xj formano la matrice di correlazione Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 4/ 16
PCA: Principal Component Analysis LAnalisi per Componenti Principali viene utilizzata per costruire, a partire da un insieme di variabili che possono essere correlate, un insieme di variabili linearmente scorrelate (cio`e 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 spazio cartesiano, e di trasformare lo spazio con una trasformazione ortogonale (cio`e che preserva le distanze) in modo che nel nuovo sistema di coordinate abbia le componenti principali come assi cartesiani. La PCA pu`o essere usata per scoprire correlazioni lineari, uniformi e globali in un insieme di dati. Come nel caso della correlazione, la PCA `e un metodo classico della statistica (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 che consente di misurare quanto sono correlati fra loro gli elementi di un singolo gruppo rispetto a una data categorizzazione di un dataset. Intraclass correlation ICC = 2 e 2 e + 2 c dove 2 e `e la varianza fra gli elementi di una stessa classe, e 2 c `e la varianza fra tutti gli elementi. Il calcolo delle varianze in questa formula costituisce un problema non banale: un approccio utilizza la metodologia ANOVA (ANalysis Of VAriance). Approcci diversi possono condurre a risultati diversi!!! In questo caso la correlazione che viene analizzata `e fra eventi gi`a inclusi in una stessa classe: allopposto abbiamo la scoperta di correlazioni fra eventi 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 in classi fra questi oggetti in base a un criterio di somiglianza: se non `e dato un criterio a priori, il clustering consiste nel determinare delle classi in base alle relazioni statistiche che possono esistere fra i dati, una volta che questi siano stati codi鍖cati numericamente. In data mining esistono moltissimi algoritmi di clustering, a seconda degli ambiti e degli scopi. Il clustering e la correlazione sono concetti distinti ma collegati: in particolare partizionare un insieme di eventi in base a classi di correlazione (per esempio se sono correlati per pi`u di un certo valore 鍖ssato) fornisce un criterio di clustering. Allopposto, il risultato di un clustering pu`o essere validato 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, n osservazioni in k classi distinte, stimando che una osservazione appartiene a una classe in base a un criterio di similarit`a basato sulla vicinanza alla media. Lo spazio degli eventi risulta in questo modo partizionato da un diagramma di Voronoi. De鍖nizione di k-mean cluster argmin sS k i=1 xs x 袖i 2 dove S = {S1, ..., Sk} sono le classi e 袖i la media dei valori nella classe i-esima Si . Il problema `e NP-completo!!! Tuttavia esistono algoritmi euristici computazionalmente e鍖cienti 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 densit`a non partizionano in modo esatto sulla base di una distanza (come nel caso k-means) ma si basano sulla densit`a di accumulazione dei punti nello spazio. DBSCAN (1996) Questo algoritmo considera come appartenenti a uno stesso cluster elementi la cui distanza di鍖erisca per meno di un 鍖ssato: in pratica se allinterno di un certo raggio sono racchiusi dei punti, si considerano parte di un medesimo cluster. I punti di forza di DBSCAN sono la sua riproducibilit`a (algoritmo non probabilistico) e la sua complessit`a O(n log n) che lo rende implementabile in modo e鍖ciente. Le debolezze sono che dipende dalla distanza impiegata 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 non solo nello spazio ma in tutti i suoi sottospazi: uno stesso punto pu`o quindi fare parte di pi`u cluster, che vivono in sottospazi diversi. CLIQUE (2005) Si tratta di un algoritmo che utilizza le tecniche dei density based clustering sui sottospazi di dimensione massimale rispetto a questa propriet`a. CLIQUE `e particolarmente adatto per dati di dimensione alta, dove i metodi di densit`a performano male. Un algoritmo dello stesso tipo `e SUBCLU (2004) che estende DBSCAN alla 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 ra鍖nare il clustering utilizzando la correlazione come criterio guida invece che la distanza. 4C: Computing Correlation Connected Clusters: (2004) Si tratta di un algoritmo che combina PCA e DBSCAN per ottenere cluster di oggetti che sono fra loro correlati senza doversi limitare a considerare correlazioni globali. In soldoni, 4C correla localmente secondo le componenti principali, e determina il concetto di localit`a in base allanalisi di densit`a tipica di DBSCAN. Da non confondere con lanalogo concetto (correlation clustering) di teoria dei gra鍖, che consiste nel cercare il numero ottimale di cluster dando per note 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 lattenzione!!! Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 16/ 16

More Related Content

Algoritmi di clustering e correlazione: una panoramica

  • 1. Algoritmi di clustering e correlazione: una panoramica Paolo Caressa 20 giugno 2012 Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 1/ 16
  • 2. 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
  • 3. Indipendenza Abbiamo a che fare con concetti probabilistici. Indipendenza di eventi Se A e B sono due eventi qualsiasi, diciamo che sono indipendenti se la probabilit`a P(B) di veri鍖carsi di B non dipende dal veri鍖carsi o meno dellevento A, e viceversa. In formule: P(A B) = P(A) 揃 P(B). Utilizzando il concetto di probabilit`a condizionata P(A|B), la probabilit`a di A dato B, allora lindipendenza equivale a P(A|B) = P(A). Indipendenza di variabili aleatorie Una variabile aleatoria X (in soldoni un insieme di numeri associati a eventi) `e indipendente da unaltra Y se sono indipendenti gli eventi {X a} e {Y b} per ogni a, b R. Lespressione matematica rigorosa `e in termini di distribuzioni, etc. Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 3/ 16
  • 4. Correlazione lineare Se X `e una variabile aleatoria, per esempio una serie storica di rilevazioni numeriche o da un dataset, possiamo calcolarne la media E(X), la varianza Var(X) = E(X2) 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 lindipendenza lineare fra due variabili Indipendenza = XY = 0 XY = 0 = Indipendenza Nel caso di n variabili X1, ..., Xn le correlazioni Xi Xj formano la matrice di correlazione Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 4/ 16
  • 5. PCA: Principal Component Analysis LAnalisi per Componenti Principali viene utilizzata per costruire, a partire da un insieme di variabili che possono essere correlate, un insieme di variabili linearmente scorrelate (cio`e 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 spazio cartesiano, e di trasformare lo spazio con una trasformazione ortogonale (cio`e che preserva le distanze) in modo che nel nuovo sistema di coordinate abbia le componenti principali come assi cartesiani. La PCA pu`o essere usata per scoprire correlazioni lineari, uniformi e globali in un insieme di dati. Come nel caso della correlazione, la PCA `e un metodo classico della statistica (inventato agli inizi del Novecento). Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 5/ 16
  • 6. ICC: Intraclass Correlation La intraclass correlation `e un metodo della statistica descrittiva che consente di misurare quanto sono correlati fra loro gli elementi di un singolo gruppo rispetto a una data categorizzazione di un dataset. Intraclass correlation ICC = 2 e 2 e + 2 c dove 2 e `e la varianza fra gli elementi di una stessa classe, e 2 c `e la varianza fra tutti gli elementi. Il calcolo delle varianze in questa formula costituisce un problema non banale: un approccio utilizza la metodologia ANOVA (ANalysis Of VAriance). Approcci diversi possono condurre a risultati diversi!!! In questo caso la correlazione che viene analizzata `e fra eventi gi`a inclusi in una stessa classe: allopposto abbiamo la scoperta di correlazioni fra eventi non categorizzati, ovvero la scoperta delle classi stesse. Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 6/ 16
  • 7. Clustering Un clustering di un insieme di eventi, oggetti, etc. `e la suddivisione in classi fra questi oggetti in base a un criterio di somiglianza: se non `e dato un criterio a priori, il clustering consiste nel determinare delle classi in base alle relazioni statistiche che possono esistere fra i dati, una volta che questi siano stati codi鍖cati numericamente. In data mining esistono moltissimi algoritmi di clustering, a seconda degli ambiti e degli scopi. Il clustering e la correlazione sono concetti distinti ma collegati: in particolare partizionare un insieme di eventi in base a classi di correlazione (per esempio se sono correlati per pi`u di un certo valore 鍖ssato) fornisce un criterio di clustering. Allopposto, il risultato di un clustering pu`o essere validato con una intraclass correlation. Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 7/ 16
  • 8. k-means clustering Un k-means clustering consiste nel determinare, per un insieme di dati, n osservazioni in k classi distinte, stimando che una osservazione appartiene a una classe in base a un criterio di similarit`a basato sulla vicinanza alla media. Lo spazio degli eventi risulta in questo modo partizionato da un diagramma di Voronoi. De鍖nizione di k-mean cluster argmin sS k i=1 xs x 袖i 2 dove S = {S1, ..., Sk} sono le classi e 袖i la media dei valori nella classe i-esima Si . Il problema `e NP-completo!!! Tuttavia esistono algoritmi euristici computazionalmente e鍖cienti per stimare la k-mean. Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 8/ 16
  • 9. k-means clustering Una k-means clustering Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 9/ 16
  • 10. Density based clustering I metodi di clustering basati sulla densit`a non partizionano in modo esatto sulla base di una distanza (come nel caso k-means) ma si basano sulla densit`a di accumulazione dei punti nello spazio. DBSCAN (1996) Questo algoritmo considera come appartenenti a uno stesso cluster elementi la cui distanza di鍖erisca per meno di un 鍖ssato: in pratica se allinterno di un certo raggio sono racchiusi dei punti, si considerano parte di un medesimo cluster. I punti di forza di DBSCAN sono la sua riproducibilit`a (algoritmo non probabilistico) e la sua complessit`a O(n log n) che lo rende implementabile in modo e鍖ciente. Le debolezze sono che dipende dalla distanza impiegata e quindi la stima dell non `e immediata. Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 10/ 16
  • 11. DBSCAN Una DBSCAN clustering Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 11/ 16
  • 12. OPTICS Una OPTICS clustering (1999), un miglioramento di DBSCAN Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 12/ 16
  • 13. Density based clustering I metodi di clustering basati sui sottospazi vanno a ricercare i cluster non solo nello spazio ma in tutti i suoi sottospazi: uno stesso punto pu`o quindi fare parte di pi`u cluster, che vivono in sottospazi diversi. CLIQUE (2005) Si tratta di un algoritmo che utilizza le tecniche dei density based clustering sui sottospazi di dimensione massimale rispetto a questa propriet`a. CLIQUE `e particolarmente adatto per dati di dimensione alta, dove i metodi di densit`a performano male. Un algoritmo dello stesso tipo `e SUBCLU (2004) che estende DBSCAN alla ricerca di cluster in sottospazi di dimensione distinta. Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 13/ 16
  • 14. Correlation Clustering Un correlation clustering si propone di ra鍖nare il clustering utilizzando la correlazione come criterio guida invece che la distanza. 4C: Computing Correlation Connected Clusters: (2004) Si tratta di un algoritmo che combina PCA e DBSCAN per ottenere cluster di oggetti che sono fra loro correlati senza doversi limitare a considerare correlazioni globali. In soldoni, 4C correla localmente secondo le componenti principali, e determina il concetto di localit`a in base allanalisi di densit`a tipica di DBSCAN. Da non confondere con lanalogo concetto (correlation clustering) di teoria dei gra鍖, che consiste nel cercare il numero ottimale di cluster dando per note le relazioni di correlazione: c`e un legame ma sono algoritmi diversi. Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 14/ 16
  • 15. 4C clustering Comparazione di DBSCAN e 4C Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 15/ 16
  • 16. Algoritmi di clustering e correlazione: una panoramica Domande/Suggerimenti??? Grazie per lattenzione!!! Paolo Caressa Algoritmi di clustering e correlazione: una panoramica 16/ 16