Cluster Analysis per Big Data Economico/Aziendali: Metodi e Limitazioni

Metodi (algoritmi) gerarchici

Nei metodi gerarchici si individua una sequenza di partizioni nidificate: la partizione in K + 1 gruppi si ottiene dalla partizione in K gruppi facendo di due degli elementi di questa un elemento di quella (AGNES) o viceversa (DIANA)

• Algoritmo Agglomerativo (AGNES, AGGlomerative NESting)
• Algoritmo Scissorio (DIANA, DIvisive ANAlysis)

1/19

Metodi gerarchici: rappresentazione visiva

F E A B C D 7 A B C D E F

2/19

Clustering Gerarchico: Matrice delle Distanze e Criterio di Stop

• Il Clustering Gerarchico fa uso della Matrice delle Distanze per implementare i raggruppamenti.
• Non richiede la definizione a priori di un numero di gruppi, ma necessita di un criterio di stop Step o Step 1 Step 2 Step 3 Step 4 Agglomerative a ab b abcde C cde de e Step 4 Step 3 Step 2 Step 1 Step o Divisive

3/19

Clustering gerarchico: Esempio Step 0

e f a b d C Step o Step 1 Step 2 Step 3 Step 4 5 b C d e f

4/19

Clustering gerarchico: Esempio Step 1

e f a b d C Step o Step 1 Step 2 Step 3 Step 4 a ab b C d e f

5/19

Clustering gerarchico: Esempio Step 2

e f a b d C Step o Step 1 Step 2 Step 3 Step 4 a ab b C d e ef f

6/19

Clustering gerarchico: Esempio Step 3

e f a b d C Step o Step 1 Step 2 Step 3 Step 4 a ab abc b C d e ef f

7/19

Clustering gerarchico: Esempio Step 4

e f a b d C Step o Step 1 Step 2 Step 3 Step 4 a ab abc b abcd d e ef f

8/19

Clustering gerarchico: Esempio finale

e f a b d C Step o Step 1 Step 2 Step 3 Step 4 a ab abc b abcd C d e ef f

9/19

Clustering gerarchico: Distanza

F E A B C D Distanza A B C D E F

10/19

Il dendrogramma: Rappresentazione e Interpretazione

• La successione di partizioni individuate può essere rappresentata con il dendogramma Nell'esempio abbiamo n = 6 unità statistiche, indicate con le lettere da a a f
• Le unità a e b sono unite tra di loro da una linea spezzata a forma di U rovesciata, che indica che vengono messe nello stesso gruppo e si ottiene la partizione (a, b), c, d, e, f Procedendo verso l'alto, la successiva unione tra gruppi è tra e e f, quindi al livello successivo si ottiene la partizione (a, b), c, d, (e, f).
• Andando su ancora di un livello, vengono uniti i gruppi (a, b) e c, formando la partizione (a, b, c), d, (e, f). Etc.

11/19

Clustering gerarchico agglomerativo: algoritmo

1. Calcolo matrice di distanza
2. Ogni punto rappresenta un cluster
3. Ripeti 3.1 Unisci i due clusters più vicini 3.2 Aggiorna la matrice di distanza utilizzando i nuovi clusters
4. Ripeti fino a quando rimane solo un singolo cluster

12/19

Clustering gerarchico agglomerativo: dipendenza dal Linkage Method

1. Calcolo matrice di distanza
2. Ogni punto rappresenta un cluster
3. Ripeti 3.1 Unisci i due clusters più vicini 3.2 Aggiorna la matrice di distanza utilizzando i nuovi clusters
4. Ripeti fino a quando rimane solo un singolo cluster

• Lo step 3.1 dipende da come viene definita la distanza tra due clusters GI e GL
• Linkage Method: metodo usato per unire i clusters, che definisce come misuriamo la prossimità tra clusters

13/19

Metodi di linkage

• Legame singolo (single linkage) d(GI, GL) = min{d(ui, ul), ui E GI, ul E GL}
• Legame completo (complete linkage) d(GI, GL) = max{d(uj, ul), ui E Gr, ul E GL}
• Legame medio (average linkage) d(GI, GL) = 1 NGINGL uiEGI WIEGL > > d(ui, u]) dove nG e nGy, sono le numerosità dei gruppi Gre GL e ui, ul sono osservazioni all'interno dei due gruppi, rispettivamente

14/19

Metodi di linkage: rappresentazione grafica

1 3 1. 1 1 1 1 4 1 1 + 1 5/ 2 1 (a) 1 ·3 1 1 1 1 . 4 1 1 1 1 (b) 1 1 1 1 1 4 1 1 5/ 2 (c) Cluster distance d 24 d13 + d14 + d15 + d23 + d24 + d25 6 15/19 d15 5 2. 1 1 3 1

Metodi di linkage: proprietà

• Legame singolo - Può gestire forme non ellittiche nei clusters - Rischia di legare osservazioni che non appartengono a uno stesso gruppo (chaining) - Suscettibile agli outliers
• Legame completo - Meno suscettibile agli outliers - Tende a dividere grandi clusters - Tende a creare clusters di forma sferica
• Legame medio - Tradeoff tra i primi due - Non invariate rispetto a trasformazioni monotone

16/19

Clustering Gerarchico: scelta del numero di clusters

• Fissata una distanza c > 0, disegnando una linea orizzontale ad altezza c si taglia il dendogramma e si ottiene il numero di gruppi, corrispondente al numero di aste intersecate dalla linea orizzontale 6 J 5 4 Distanza 3 - 2 1 3 5 2 4

17/19

Tagliare il dendrogramma: Interpretazione del taglio

In termini di distanza/dissimilarità tra unità statistiche, tagliare il dendogramma ad altezza c > 0

• Legame singolo: per ogni u; in un cluster (non singoletto), c'è almeno un'altra unità up tale per cui d(uj, ul) < c
• Legame completo: per ogni uj in un cluster (non singoletto), tutte le altre altra unità uį sono tali per cui d(ui, ul) < c
• Legame medio: no interpretazione

18/19

Clustering Gerarchico: problemi e limitazioni

• Maggiore complessità computazionale
• Una volta che la decisione di combinare due clusters è presa, non si può tornare indietro
• Non vi è ottimizzazione diretta di una funzione obiettivo.
• A seconda della scelta del linkage, il risultato che si ottiene può essere radicalmente diverso

19/19