Formattazione del testo
(AB)(CD) AC AD BC BD
Al primo passo si fondono le 2 unità aventi distanza minore, ottenendo così n-1 gruppi.
Si calcola una nuova matrice di distanze tra gli n-1 clusters.
Si aggregano i due cluster aventi distanza minima.
Esempio:
Matrice delle distanze:
La distanza minima è rappresentata dal valore 1: devo fondere A e B con distanza di fusione d = 1.
AB
Calcolo le distanze tra cluster (AB) dalle altre unità:
Applico ancora il criterio della distanza minima che è quella tra D e E con d = 2.
DE
Fusione AB e C con d = 3
(AB)E 23
2) Legame completo
Il criterio è la distanza massima.
Date 5 unità A, B, C, D, E, abbiamo creato la matrice che si basa su un coefficiente di dissimilarità o di una misura di distanza tra le unità (d d d).
AB, AC, ... CD
Supponendo che le unità A e B vengano fuse in un solo cluster, la distanza tra il cluster (AB) e l'unità C è definita come:
d = max(d(A,B)C, AC, BC)
mentre la distanza tra...
il cluster (AB) e il cluster (CD) viene definita come: d = max(d ,d ,d ,d )(AB)(CD) AC AD BC BD
3) Metodo di McQuitty
La distanza tra cluster è calcolata con la media aritmetica delle distanze (o dissimilarità) tra tutte le possibili coppie di elementi appartenenti l'uno ad un cluster, l'altro ad un altro.
L'accorpamento dei gruppi avviene sempre secondo distanza minima.
Fusione A e B con d = 1
AB
Calcolo le distanze tra cluster (AB) dalle altre unità:
Fusione D e E
d = (1/2)x(1/2)(d +d +d +d )= 0,25 (6+8+8+7) = 7.25
(AB),(DE) A,D A,E B,D B,E
d = 1x(1/2) (d +d ) = 0,5 (4+6) = 5
C,(DE) C,D C,E
Fusione C e AB
4) Legame medio
La distanza tra cluster è calcolata come media aritmetica ponderata con numero di unità nel cluster delle distanze (o dissimilarità) tra tutte le possibili coppie di elementi appartenenti l'uno ad un cluster, l'altro ad un altro.
Dati 2 cluster A e B contenenti rispettivamente n e n unità, indichiamo con
L'indice i è il generico elemento del cluster A e con l'indice h il generico elemento del cluster B e con d la loro distanza.
Distanza tra A e B = media ponderata delle distanze 245)
Metodo del centroide
- Solo per variabili quantitative
- Non usa la matrice distanze ma i singoli vettori di osservazioni (ad ogni passo ricalcola matrice distanze partendo non da distanze precedenti ma dai baricentri di ciascun cluster)
- Per ogni gruppo (anche se una sola unità) si calcola il baricentro (o individuo medio, cioè un elemento che come modalità delle diverse variabili presenta le modalità medie del gruppo)
- Distanza calcolata come distanza dai baricentri.
Esempio:
Calcolo delle distanze euclidee al quadrato:
Matrice dei quadrati delle distanze euclidee:
Fusione A e B perché il valore minimo di distanza è 1.
La distanza è il baricentro (media aritmetica) del cluster AB con coordinate 1 per x1 e 1,5 per x2.
2(AB)C 2 2
Calcolo delle distanze
interna (all'interno dei cluster) Il metodo di Ward è un algoritmo gerarchico aggregativo che mira a minimizzare la varianza all'interno dei gruppi, ma può essere utilizzato solo per variabili quantitative. Ad ogni passo, l'algoritmo cerca di ottimizzare la partizione ottenuta aggregando due elementi. Una partizione è considerata migliore se le classi risultano omogenee al loro interno e diverse l'una dall'altra, ovvero se la varianza tra le classi è elevata e la varianza interna alle classi è bassa. La varianza totale di un insieme di unità può essere scomposta nella somma di due quantità: - Varianza interna (ai cluster) - Varianza interna (all'interno dei cluster)esterna (tra cluster). In maniera analoga, si scompone la matrice di varianze e covarianze S, ovvero: S = SW + SB S = matrice di varianze e covarianze totali SW = matrice delle varianze e covarianze "interne" (within) SB = matrice delle varianze e covarianze "esterne" (between) Come si decide di aggregare o meno il cluster? Individuo il primo cluster e decido se aggregare la prima unità in base al minor incremento di varianza interna che questa unità genera. L'algoritmo ricerca "il salto minimo di aumento della varianza interna", cioè ad ogni passo aggrega ad un cluster già individuato l'unità o il cluster che portino il minor incremento di varianza interna (regola di aggregazione). Il raggruppamento in classi non modifica la varianza complessiva: si modificano solo i due addendi (varianza interna ed esterna) ma la loro somma non varia. Aumentando il numero di unità contenute in un cluster, aumenta lavarianza interna (in un cluster di un solo elemento, la varianza interna è nulla). Al diminuire del numero di cluster, diminuisce la varianza esterna (pari alla somma di un minor numero di termini). Il caso limite è un solo cluster contenente tutte le unità:
- Varianza esterna nulla
- Varianza interna uguale alla varianza totale
La devianza totale delle p variabili è la somma delle distanze euclidee al quadrato tra le singole osservazioni e il vettore delle medie:
Dove totale p variabili = somma delle distanze euclidee al quadrato
È la media della variabile s con riferimento all'intero collettivo.
Devianza ENTRO i gruppi (riferita a p variabili): è la somma degli scarti al quadrato tra singoli valori rispetto a una variabile s e la media della variabile s con riferimento al gruppo k. Per ogni gruppo K avrò p variabili (da s=1 a p) e n unità (da i=1 a n). La devianza è riferita alle p variabili con riferimento al gruppo
kè la media della variabile s con riferimento al gruppo k
Devianza TRA i gruppi (riferita a p variabili): È la somma sulla p variabili delle devianze (ponderate per la numerosità di k) delle medie di gruppo rispetto alla media generale.
Devianza TOTALE
Esempio: 27
Confronto tra algoritmi di aggregazione
- Legame singolo:
- Poco sensibile a valori anomali, anche per gruppi singoli o di una sola unità (vantaggio)
- Tende a concatenare i gruppi Gruppi tendenzialmente allungati “ a salciccia”
- Distanze in fusioni successive sempre non decrescenti
- Legame completo:
- Molto influenzato da valori anomali
- Tende a produrre gruppi di dimensioni molto simili
- Distanze in fusioni successive sempre non decrescenti
- Legame medio:
- In posizione intermedia tra singolo e completo
- Tende ad unire i gruppi con bassa varianza interna e a produrre gruppi con varianze interne simili
- Distanze fusioni successive sempre non decrescenti
- Centroide:
- Più robusto
Sulle ascisse. Ai livelli successivi l'apertura dei rettangoli parte dal centro della base che unisce le entità di livello minore.
Rappresentazione grafica della classificazione:
- Asse ordinate: livello di distanza a cui sono avvenute le successive fusioni
- Asse ascisse: singole unità
Ogni ramo del diagramma (linea verticale) corrisponde ad un grappolo (gruppo o cluster).
La linea di congiunzione (orizzontale) congiunge due o più rami.
Quanti gruppi considerare
Il criterio è il livello di distanza a cui avvengono le aggregazioni successive: le aggregazioni che nel dendrogramma avvengono molto in alto indicano fusione di gruppi eterogenei, quindi è meglio fermarsi prima.
Dendrogramma riscalato
Le distanze sono riscalate rispetto all'intervallo 0-25. Le distanze originarie vengono riscalate in base ad una distanza che va da 0 al valore massimo delle distanze non riscalate.
d = [25 x (d - min)] / (max - min)
rs fsMin = valore minimo delle
codice HTML:distanze di fusioneMax = valore massimo delle distanze di fusione
d = dr1 f1s = stadio di fusione 29
Esempio1) Dendrogramma: taglio allo stadio in cui la distanza di fusione è troppo elevata
2R è coefficiente di determinazione 30
METODI DI RAGGRUPPAMENTO GERARCHICI DIVISIVI
Effettuano un percorso inverso rispetto agli agglomerativi: il punto di partenza è un unico gruppo formato da tutte le unità e si procede per divisioni successive (prima in due gruppi, poi il più eterogeneo dei due viene diviso in due, ...).
Metodi basati sulla distanza tra centroidi (solo per variabili quantitative)
- Si sceglie la soluzione che minimizza la somma delle devianze interne ai due gruppi (massima distanza tra centroidi)
- Si divide in due il gruppo che presenta la massima devianza interna con il medesimo criterio
È molto oneroso dal punto di vista computazionale (dei calcoli).
METODI DI RAGGRUPPAMENTO NON GERARCHICI
Effettuano il raggruppamento direttamente nel
o calcolati i centroidi dei gruppi provvisori4 Si ripetono i passaggi 2 e 3 fino a quando i centroidi non si stabilizzano o si raggiunge un numero massimo di iterazioni5 Si ottiene la partizione finale dei dati in k gruppi, con i centroidi che rappresentano i punti centrali di ciascun gruppo 2) Algoritmo Hierarchical Agglomerative Clustering (HAC) 1 Si parte con ogni unità come un singolo cluster 2 Si calcola la matrice delle distanze tra tutti i cluster 3 Si uniscono i due cluster più vicini in base alla distanza, formando un nuovo cluster 4 Si aggiorna la matrice delle distanze considerando il nuovo cluster 5 Si ripetono i passaggi 3 e 4 fino a quando tutti i cluster sono stati uniti in un unico cluster o si raggiunge un criterio di stop 6 Si ottiene la gerarchia dei cluster, rappresentata da un dendrogramma 3) Algoritmo DBSCAN 1 Si seleziona un punto a caso e si determina il suo vicinato entro una distanza specificata (epsilon) 2 Se il numero di punti nel vicinato supera una soglia specificata (minPts), il punto viene considerato un punto centrale e si forma un nuovo cluster 3 Si espande il cluster includendo tutti i punti raggiungibili dal punto centrale, rispettando i criteri di distanza e numero minimo di punti 4 Si ripetono i passaggi 1-3 per tutti i punti non ancora assegnati a un cluster 5 Si ottiene la partizione finale dei dati in cluster Questi sono solo alcuni degli algoritmi di clustering più comuni. Ogni algoritmo ha i suoi vantaggi e svantaggi e la scelta dipende dal tipo di dati e dagli obiettivi dell'analisi.Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
Scarica il documento per vederlo tutto.
-
Statistica Avanzata - Appunti
-
Appunti Statistica
-
Appunti di Statistica aziendale
-
Appunti lezioni Statistica aziendale