Post on 18-Feb-2019
Ing. Igor RossiniLaurea in Ingegneria InformaticaPolitecnico di MilanoPolo Regionale di Como
Metodologie per Sistemi Intelligenti
Clustering
© Igor Rossini
Cos’è il clustering?
• Il processo di raggruppamento di un insieme di oggetti fisici o astratti in classi di oggetti simili (Han 2001).
• Un cluster è una collezione di oggetti “simili” tra loro che sono “dissimili”rispetto agli oggetti degli altri cluster.
© Igor Rossini
Definizione
• Dati un insieme di esempi, descritti da un insieme di attributi, e una misura di similarità trovare un insiemedi cluster tali che:– Gli esempi appartenenti allo stesso cluster risultino simili– Gli esempi appartenenti a cluster differenti dissimili
• La misura di similarità è il cuore del problema e ilcuore della soluzione al problema– Distanza Euclidea se gli attributi sono tutti numerici
e se ha senso…– Nella maggior parte dei casi, è specifica al problema
© Igor Rossini
A cosa si applica?
• In biologia può essere utilizzato per derivare tassonomie di animali e piante.
• Nel marketing può essere impiegato per derivare e caratterizzare gruppi di consumatori.
• ...per derivare aree geografiche simili.• Nell’analisi dei dati viene impiegato per
studiare come i dati si distribuiscono nello spazio.
© Igor Rossini
Clustering (1)
• Cerchiamo raggruppamenti interessanti• Alla base c’è l’ipotesi che si possa
definire una distanza o misura di similarità• La distanza deve essere
significativa per il dominio• L’ipotesi implicita è più i dati sono vicini,
più sono simili• Lo scopo generale è trovare
dei cluster tali che– Le distanze intracluster siano minime– Le distanze intercluster siano massime
© Igor Rossini
Clustering (2)
Distance based clustering• Un gruppo di oggetti appartengono allo stesso
cluster se sono “vicini” rispetto ad una determinata distanza.
Conceptual Clustering• Gli oggetti appartengono ad un cluster se questo
definisce un concetto comune ai diversi oggetti.
© Igor Rossini
Applicazioni di Clustering
• Pattern Recognition• Spatial Data Analysis
– Creare mappe tematiche negli strumenti GIS per individuare raggruppamenti simili nello spazio
• Image Processing• Economic Science (especially market research)• WWW
– Classificazione dei documenti– Analisi dei dati di Weblog per scoprire gruppi
caratterizzati da comuni profili di accesso e navigazione
© Igor Rossini
Esempi di Applicazioni (1)
• Marketing– Aiuta i marketing managers a scoprire segmenti distinti
all’interno della customer base, e quindi ad utilizzare questaconoscenza per lo sviluppo di campagne mirate di marketing
• Utilizzo del Territorio– Identificare aree territoriali di simile utilizzo mediante
l’analisi di un database di osservazioni sul territorio
• Assicurazioni– Partizionare il portafoglio clienti auto in segmenti a
supporto delle attività di target marketing
© Igor Rossini
Esempi di Applicazioni (2)
• Pianificazione urbana– Identificare gruppi di edifici per tipologia, valore e
localizzazione geografica
• Studi sismici– Formare cluster di epicentri di eventi sismici e
verificare che si trovino lungo le faglie dei continenti
• Astronomia– Analisi delle immagini del cielo
– Analisi delle esplosioni di raggi gamma
© Igor Rossini
Requisiti
• Scalabilità• Possibilità di trattare molteplici tipi di attributi• Minimo numero possibile di parametri• Possibilità di trattare dati affetti da “rumore”• Indipendenza dall’ordine degli esempi• Possibilità di trattare esempi con
molti attributi
© Igor Rossini
Quali sono i problemi tipici?
• L’efficacia dipende dalla definizione di distanza• Se non esiste una misura di distanza ovvia,
bisogna “inventarla”• La bontà del risultato dipende completamente
dall’adeguatezza della misura rispetto al problema• L’interpretazione del risultato dipende dalla
distanza. • I risultati in molti casi possono essere arbitrari…
…come pure la loro interpretazione!
© Igor Rossini
Esempio
• Abbiamo dei dati relativi agli accessi ad un sito
• Conosciamo gli IP degli utenti che accedono al sito
• Provare a definire una distanza fra indirizzi IP
© Igor Rossini
Tassonomie
• Tassonomia degli Algoritmi– Gerarchici
viene generata una gerarchia di possibilisuddivisioni
– Partition-Basedviene generata una sola partizione
• Tassonomia delle tecniche– Bottom-up– Top-down
© Igor Rossini
Algoritmi di Clustering
• Partition-based clustering– Dato k, partiziona gli esempi in k cluster di almeno un elemento;
ogni esempio può appartenere solo ad un elemento.
• Hierarchical clustering– Scompone l’insieme degli esempi in una gerarchia di
partizioni di diversa complessità.
• Density-based clustering– Gli esempi vengono suddivisi in cluster via via sempre più
numerosi fino a quando la “densità” di ogni cluster rimaneaccettabile.
• Grid-based e Model-based clustering
© Igor Rossini
Algoritmi Partition-Based
• Scopo: trovare una suddivisione dei dati in k cluster (k fissato all’inizio)
• Strategie Locali– formare i cluster sfruttando la struttura locale dei dati
• Strategie Globali– ogni cluster viene rappresentato da un prototipo,– ogni esempio viene assegnato al cluster
il cui prototipo è maggiormente simile
© Igor Rossini
Algoritmi Gerarchici
• Si parte– Da un unico cluster contenente tutti gli esempi (top-
down)– Da un cluster per ogni esempio (bottom-up)
• Ad ogni passo, – Si divide un cluster in due (top-down)– Si raggruppano due cluster (bottom-up)
• In questo modo si forma una gerarchia di suddivisioni, fusioni di cluster
• La gerarchia viene rappresentata con un dendrogramma
© Igor Rossini
Nearest Neighbor Clustering
• Input– Una soglia t sulla distanza– Un insieme di n esempi x1...xn
– Una misura di distanza
• Output– k cluster in cui la distanza fra elementi
appartenenti a cluster distinti è almeno t
© Igor Rossini
Funzionamento del NN
INPUT t e gli n esempi {x1...xn}OUTPUT k cluster
C1 = {x1}; i=1; k=1;do {
i=i+1;x’ = elemento più vicino a xi
tra quelli assegnati ai cluster;// assumiamo x’ appartenga al cluster Cm;if (distanza(xi,x’)>t){
k = k + 1;Ck = {xi};
} else {Cm = Cm +{xi};
}} while (i!=n);
© Igor Rossini
NN per Classificazione
• E’ possibile utilizzare il NN come modello di classificazione
• Per ogni nuovo caso da classificare occorre:– Calcolare la similitudine di quest’ultimo rispetto ai
cluster individuati dal modello non supervisionato– Attribuire al nuovo caso la stessa classificazione
del cluster cui risulta più simile– Aggiungere il nuovo caso classificato alla tabella dei
casi noti
© Igor Rossini
Esempio Nearest Neighbor (1.1)
25 30 35 40 45 50
1
2
3
4
?
?
?
Programma televisivo A
Programma televisivo B
Programma televisivo C
Programma televisivo D
© Igor Rossini
Esempio Nearest Neighbor (1.2)
25 30 35 40 45 50
1
2
3
4
Z
X
W
Programma televisivo A
Programma televisivo B
Programma televisivo C
Programma televisivo D
© Igor Rossini
Esempio Nearest Neighbor (2.1)
RaffreddoreSiSiNoSiNo9
RaffreddoreSiSiNoSiSi10
AllergiaSiSiNoNoSi8
Affezione da StreptococcoNoNoSiNoNo7
AllergiaNoSiNoNoNo6
RaffreddoreNoSiNoSiNo5
Affezione da StreptococcoNoNoSiNoSi4
RaffreddoreNoSiNoSiSi3
AllergiaSiSiNoNoNo2
Affezione da StreptococcoSiSiSiSiSi1
DiagnosiMal di Testa
CongestioneGhiandole Ingrossate
FebbreMal di Gola
Codice Paziente
© Igor Rossini
Esempio Nearest Neighbor (2.2)
• Nuovo paziente da classificare
• Similitudine in base al conteggio delle corrispondenze attributo-valore
NoNoNoNoSi14
Mal di Testa
CongestioneGhiandole Ingrossate
FebbreMal di Gola
Codice Paziente
43, 6, 7, 82, 5, 101, 9Pazienti
4321Corrispondenze
Affezione da Streptococco
© Igor Rossini
Considerazioni sul NN (1)
• Vantaggi– Per la sua efficacia è necessario un pretrattamento dei
dati per la determinazione degli attributi rilevanti– Ridotti tempi di calcolo confrontando i casi da
classificare con un sottoinsieme di casi tipici tratti daogni classe rappresentata nei dati
– La descrizione generale di ciascuna classe può essereottenuta esaminando gli insiemi dei casi più tipici delleclassi
© Igor Rossini
Considerazioni sul NN (2)
• Svantaggi– Tempi di calcolo elevati nel caso di dataset di
grandi dimensioni– Non effettua distinzioni tra attributi rilevanti e
irrilevanti– Difficoltà nel capire se gli attributi scelti siano
in grado di differenziare le classi contenute neidati
© Igor Rossini
k-means
• Dati– Un numero k– Un insieme di n esempi– Una misura di distanza– Un criterio di stop (minimo errore quadratico)
• Il k-means partiziona gli n esempi in k cluster• La similarità fra esempi appartenenti
allo stesso cluster deve essere alta• La similarità fra oggetti appartenenti
a cluster diversi deve essere bassa
© Igor Rossini
Funzionamento del k-means?
INPUT k e gli n esempiOUTPUT k cluster che minimizzano l’errore quadratico
Dato k e n esempiSeleziona k esempi tra n come centroidi inizialiRepeat
assegna ogni esempio al cluster corrispondente al centroide a cui l’esempio e’ più vicino.
calcola “il valore medio degli elementi del cluster”ovvero calcola i nuovi centroidi.
Until criterio soddisfatto
© Igor Rossini
Come funziona il k-means?
• Come criterio di stop viene solitamente utilizzato l’errore quadratico:
• Dove mi rappresenta il centroide del cluster Ci
© Igor Rossini
Esempio k-means
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
© Igor Rossini
Applicazione k-means (1)
• Valori di input
6.05.062.53.053.52.041.52.034.51.021.51.01YXOsservazione
© Igor Rossini
Diagramma dei dati di input
f(x)
0,0
1,0
2,0
3,0
4,0
5,0
6,0
7,0
0,0 1,0 2,0 3,0 4,0 5,0 6,0
x
© Igor Rossini
Assegnazione del valore k
• Hp due cluster distinti: k=2• Hp centri dei due cluster:
– Osservazione 1– Osservazione 2
f(x)
0,0
1,0
2,0
3,0
4,0
5,0
6,0
7,0
0,0 1,0 2,0 3,0 4,0 5,0 6,0
x
© Igor Rossini
Prima iterazione algoritmo
• C1=(1.0, 1.5), C2=(2.0, 1.5)
Centroide 1
6.02(C1-6)2.24(C1-5)2.24(C1-4)1.00(C1-3)3.00(C1-2)0.00(C1-1)
ValoreDistanze
Centroide 2
5.41(C2-6)1.41(C2-5)2.00(C2-4)0.00(C2-3)3.16(C2-2)1.00(C2-1)
ValoreDistanze
© Igor Rossini
• Cluster ottenutiC1 ∈ {1, 2} C2 ∈ {3, 4, 5, 6}
• Calcolo nuovi centroidi– Cluster C1
x=(1.0+1.0)/2=1.0y=(1.5+4.5)/2=3.0
– Cluster C2
x=(2.0+2.0+3.0+5.0)/4=3.0y=(1.5+3.5+2.5+6.0)/4=3.3
Risultati prima iterazione
© Igor Rossini
• C1=(1.0, 3.0), C2=(3.0, 3.375)
Centroide 1
5.00(C1-6)2.06(C1-5)1.12(C1-4)1.80(C1-3)1.50(C1-2)1.50(C1-1)
ValoreDistanze
Centroide 2
3.30(C2-6)0.875(C2-5)1.01(C2-4)2.125(C2-3)2.29(C2-2)2.74(C2-1)
ValoreDistanze
Seconda iterazione algoritmo
© Igor Rossini
• Cluster ottenutiC1 ∈ (1, 2, 3) C2 ∈(4, 5, 6)
• Calcolo nuovi centroidi– Cluster C1
x=(1.0+1.0+2.0)/3=1.3y=(1.5+4.5+1.5)/3=2.5
– Cluster C2
x=(2.0+3.0+5.0)/3=3.3y=(3.5+2.5+6.0)/3=4.0
Risultati seconda iterazione
© Igor Rossini
Terza iterazione algoritmo
• C1=(1.3, 2.5) C2=(3.3, 4.0)
Centroide 1
…(C1-6)…(C1-5)…(C1-4)…(C1-3)…(C1-2)…(C1-1)
ValoreDistanze
Centroide 2
…(C2-6)…(C2-5)…(C2-4)…(C2-3)…(C2-2)…(C2-1)
ValoreDistanze
© Igor Rossini
Cluster risultanti
61, 2, 3, 4, 52, 4, 5, 6
1, 31, 3, 52, 4, 6
Punti dei Cluster
(5,0, 6.0)(1.8, 2.7)(2.7, 4.1)(1.5, 1.5)(2.0, 1.8)(2.6, 4.6)
Centri dei Cluster
9,63
15,92
14,51
Errore Quadratico
Risultato
© Igor Rossini
Visualizzazione risultato 2
f(x)
0,0
1,0
2,0
3,0
4,0
5,0
6,0
7,0
0,0 1,0 2,0 3,0 4,0 5,0 6,0
x
© Igor Rossini
Considerazioni sul k-means (1)
• Vantaggi– Di immediata comprensione e
implementazione– Relativamente efficiente: O(tkn), dove n è #
records, k è # clusters, e t è # di iterazioni. Normalmente, k, t << n
– Spesso si arresta in un ottimo locale. L’ottimoglobale può essere determinato utilizzandoaltre tecniche di analisi come gli algoritmigenetici
© Igor Rossini
Considerazioni sul k-means (2)
• Svantaggi– Applicabile solo quando la media è definita, quindi non
nel caso di attributi categorici– Occorre specificare a priori il numero dei cluster k– Difficoltà nel trattare dati con rumore e outliers– Non adatto a scoprire clusters con forme geometriche
non convesse– I risultati sono migliori quando i cluster presenti nei
dati hanno la stessa dimensione– Necessità di interpretare i risultati ottenuti
© Igor Rossini
Clustering Gerarchico
• I cluster non vengono creati in un unico passo• Si inizia con una partizione in cui:
– ogni elemento è un potenziale cluster; oppure– tutti gli elementi formano un unico cluster.
• A partire da questa situazione iniziale è possibile– creare agglomerati dai singoli cluster
per formare via via cluster più grandi– dividere i cluster più grandi per
formare cluster via via più piccoli
© Igor Rossini
Clustering Gerarchico
• Supponiamo di avere cinque elementi di cui vogliamotrovare gli agglomerati interessanti.
• Primo Passo: Calcolo della Matrice delle distanze
⎟⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜⎜
⎝
⎛
=
0.00.30.50.80.90.00.40.90.10
0.00.50.60.00.2
0.0
D
• Dij è la distanza fra l’elemento “i” e l’elemento “j”
© Igor Rossini
Clustering Gerarchico
• Secondo Passo– Si trovano i due elementi più “vicini” e si raggruppano in
un singolo cluster.– In questo caso i primi due elementi sono più vicini.
• Terzo Passo: ricalcolo della matrice delle distanze.
• Qual è la distanza fra due cluster?
© Igor Rossini
Single Linkage Clustering
• d(12)3 = min[d13,d23] = d23 = 5.0• d(12)4 = min[d14,d24] = d24 = 9.0• d(12)5 = min[d15,d25] = d25 = 8.0
© Igor Rossini
Clustering Gerarchico
• La nuova matrice D2 è:
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
=
0.00.30.50.80.00.40.9
0.00.50.0
2D
• Il processo continua fino a trovare un solo cluster
© Igor Rossini
Clustering Gerarchico
• Per visualizzare il risulato di un’operazionedi clustering gerarchico usiamo un dendrogramma.
© Igor Rossini
Complete Linkage Clustering
• d(12)3 = max[d13,d23] = d23 = 6.• d(12)4 = max[d14,d24] = d24 = 10.0• d(12)5 = max[d15,d25] = d25 = 9.0
© Igor Rossini
AGNES (Agglomerative Nesting)
• Introdotto da Kaufmann e Rousseeuw (1990)• Implementato in tool di analisi statistica
(es. Splus)• Utilizza il metodo del Single-Linkage e la matrice
di dissimilarità• Crea i cluster unendo i nodi con il più basso
valore di dissimilarità• I cluster sono creati secondo una modalità di tipo
“bottom-up”• Eventualmente tutti i nodi sono raggruppati in un
unico cluster
© Igor Rossini
Esempio AGNES
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
© Igor Rossini
DIANA (Divisive Analysis)
• Introdotto da Kaufmann e Rousseeuw(1990)
• Implementato in tool di analisi statistica (es. Splus)
• Formazione dei cluster in ordine inversorispetto all’algoritmo AGNES
• Eventualmente ogni nodo forma un singolocluster
© Igor Rossini
Esempio DIANA
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 100
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
0
1
2
3
4
5
6
7
8
9
10
0 1 2 3 4 5 6 7 8 9 10
© Igor Rossini
Considerazioni
• Non necessitano della definizione a priori del numero di gruppi
• Onerosi dal punto di vista computazionale• Scarsamente efficienti con grandi moli di
dati• Fortemente influenzati dalla presenza di
outliers
© Igor Rossini
Analisi Fattoriale
• E’ una tecnica statistica per lo studio dell’interdipendenza tra variabili di tipo quantitativo
• Lo scopo è condensare l’informazione contenuta in un numero elevato di variabili in un numero esiguo di nuove variabili (fattori latenti)
• I fattori latenti sono ottenuti come combinazione lineare delle variabili di partenza con una perdita minima di informazione
© Igor Rossini
Esempio (1)
• Matrice di Input
01100005
…
0
1
1
0
3 * 2
…
1
1
0
0
Riduzione diPrezzo
000004
CampioneOmaggio
ANALISI FATTORIALE
101113
………………
110102
010011
QuantitàProdottoAggiuntiva
ConcorsoRaccolta
PuntiPremioCliente
© Igor Rossini
Esempio (2)
• Tabella di Output
RISULTATI
- Riduzione di Prezzo- 3 * 2- Quantità Aggiuntiva di Prodotto
- Concorso
- Premio,- Campione Omaggio,- Raccolta Punti
Variabili
Indica l’esistenza di un fattore che si può denominare “economia di spesa”
Legata esclusivamente al concorso, esprime una preferenza per il “Regalo Incerto”
Esprime un interesse per il “Regalo Certo”
Interpretazione
3
2
1
Componenti
© Igor Rossini
• Criterio più comune di estrazione dei fattori da un insieme di dati
• Consiste nella trasformazione del set di dati originale in un nuovo insieme di variabili composite definite componenti principali
Analisi delle Componenti Principali (1)
© Igor Rossini
• Le componenti principali sono:– una combinazione lineare del set iniziale di dati– non correlate fra di loro– ordinate in maniera decrescente rispetto alla variabilità
spiegata del set di dati di input
• Le varianze delle componenti principali, indicate con λi, sono chiamate autovalori
• Gli autovettori identificano la direzione di ogni componente principale
Analisi delle Componenti Principali (2)
© Igor Rossini
Principal Direction Divisive Partitioning• Algoritmo gerarchico divisivo• Opera su valori numerici (anche con valori
missing)• Lo split non è basato su alcuna misura di
distanza o similarità ma sul calcolo delleComponenti Principali
© Igor Rossini
PDDP
• Inizia con un cluster iniziale contenente l’intero set di dati
• Divide inizialmente il cluster iniziale in due clusterfigli
• Divide ricorsivamente i due cluster figli in ulteriori due cluster
• L’algoritmo termina quando un criterio di stop èsoddisfatto
• Le partizioni generate sono visualizzate in un albero binario (“PDDP tree”)
© Igor Rossini
Esempio: clustering di documenti
• Abbiamo un insieme di documenti• Ogni documento è caratterizzato da un
vettore di frequenze, che ci dice quanto una parola compare in un documento
• Vogliamo applicare il clustering per ottenere raggruppamenti interessanti di documenti
© Igor Rossini
Set di Dati di Ingresso
• Ogni esempio è rappresentato da un vettore d n-dimensionale– d documento di testo
• La componente di rappresenta la frequenza relativa della componente i-esima– di frequenza relativa della i-esima parola del
documento
• Ogni esempio è standardizzato al fine di avere uno stesso ordine di grandezza– ⎮⎮d⎮⎮=1
© Igor Rossini
Matrice di Frequenza
10001Ucla
1
0
0
2
2
Housing Crunch
1220Wisconsin
Closes For Snow
1020Minnesota
0101Caltech
0203Stantofrd
0001Berkeley
Big 10 Sanctions
Rose Bowl Result
Quake Risk High
• I vettori sono raggruppati nella Matrice di Frequenza M=(d1, d2, …, dn,)
© Igor Rossini
Processo di Split (1)
• A partire dalla matrice M si calcolano le Direzioni Principali
• Lo split avviene in base ai valori ottenuti dalla proiezione dei vettori d sulle Direzioni Principali
• Il processo si ripete sull’intero set di dati
© Igor Rossini
Funzionamento del PDDP?INPUT matrice M (n × m) contenente gli n esempi e un numero
desiderato di cluster pari a cmaxOUTPUT un albero binario con cmax nodi foglie formanti una partizione
dell’intero set di dati
Inizializzazione dell’albero binario con un singolo nodo radice (contenente tutto il set di dati)
Repeat for c=2, 3, …, cmaxseleziona il nodo con il più alto valore di “dissimilarità”
calcolo del centroide e della direzione principale
proiezione degli esempi del nodo secondo la direzione principale
split degli esempi nel nodo di sinistra o di destra dell’albero a seconda che il segno della proiezione sia positivo o negativo (se coincidente con il centroide lo split dell’esempio è per convenzione a sinistra)
Until sono ottenuti cmax cluster
© Igor Rossini
Considerazioni
• Necessita della definizione a priori del numero di gruppi
• Veloce, Scalabile, Efficiente con grandi moli di dati
• Riducendo la dimensionalità del set di dati iniziale risulta poco sensibile agli outliers
Ing. Igor RossiniLaurea in Ingegneria InformaticaPolitecnico di MilanoPolo Regionale di Como
Metodologie per Sistemi Intelligenti
Clustering – Metodologia di Analisi
© Igor Rossini
Fasi della Cluster AnalysisScelta delle VARIABILI Eventuale riduzione in Componenti
Principali
Selezione della Misura di Prossimità tra le variabili
Selezione dell’Algoritmo di Classificazione
Identificazione del numero dei gruppi entro i quali ripartire le entità
Valutazione della soluzione ottenuta
Analisi della soluzione più appropriataEventuale riciclo del processo di analisi
© Igor Rossini
• Data la matrice di dati relativa ad n osservazioni e p variabili…
• …occorre decidere quali variabili inserire e le opportune trasformazioni da effettuare (standardizzazione, analisi fattoriale)
⎥⎥⎥⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢⎢
⎣
⎡
npx...nfx...n1x...............ipx...ifx...i1x...............1px...1fx...11x
Scelta delle Variabili
© Igor Rossini
Selezione della Misura di Prossimità
• Indici di Similarità– forniscono informazioni preliminari indispensabili per
poter individuare gruppi di unità omogenee– sono definiti come funzione dei vettori riga della
matrice di datiIPij=f(x’i, x’j) i, j=1,2,…,nx’i, x’j vettori riga
– Differiscono a seconda che i dati considerati siano quantitativi, categorici, binari o misti
© Igor Rossini
Tipi di dati nel clustering
• Scala per Intervallo• Binarie• Nominali, Ordinali, Scala per Rapporto• Miste
© Igor Rossini
Scala per Intervallo
• Standardizzazione dei dati
– Calcolare la deviazione media assoluta:
where
– Calcolare il valore standardizzato (z-score)
• La deviazione media assoluta è più “robusta” delladeviazione standard
|)|...|||(|121 fnffffff mxmxmxns −++−+−=
.)...211
nffff xx(xn m +++=
f
fifif s
mx z
−=
© Igor Rossini
Indici di Similarità (1)
• Le distanze sono utilizzate per misurare il grado di similarità e dissimilarità tra coppie di dati
• La distanza tra due vettori riga x, y gode delle seguenti proprietà
– d(x,y) ≥ 0 non negatività
– d(x,x) = 0 identità
– d(x,y) = d(y,x) simmetria
– d(x,y) ≤ d(x,k) + d(k,y) disuguaglianza triangolare
© Igor Rossini
Indici di Similarità (2)
• Per raggruppare le diverse unità statistiche si calcola la distanza tra tutte le coppie di dati presenti nella matrice dei dati
• L’insieme di tali distanze definisce la matrice delle distanze
⎥⎥⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢⎢
⎣
⎡
0...)2,()1,(:::
)2,3()
...ndnd
0dd(3,10d(2,1)
0
© Igor Rossini
Misure di Distanza (1)
• Distanza Euclidea
dove i = (xi1, xi2, …, xip) e j = (xj1, xj2, …, xjp) sono due vettori riga p-dimensionali con i, j=1,2,…,n
• Distanza Euclidea Quadratica
)||...|||(|),( 22
22
2
11 pp jxixjxixjxixjid −++−+−=
)||...|||(|),( 22
22
2
11 pp jxixjxixjxixjid −++−+−=
© Igor Rossini
Misure di Distanza (2)
• Esempio della distanza Euclidea su un sistema cartesiano di due generiche entitài,j
b
a
Distanza euclideai (xi1, yi1)
J (xj2, yj2)
© Igor Rossini
Misure di Distanza (3)
• Distanza di Manhattan
||...||||),(2211 pp jxixjxixjxixjid −++−+−=
b
a
i (xi1, yi1)
J (xj2, yj2)
Distanza di Manhattan
© Igor Rossini
Misure di Distanza (4)
• Distanza di Lagrange-Tchebychev
| )|...||||),(2211 pp jxixjxixjxixjid −,,−,−= Maxp (
b
a
i (xi1, yi1)
J (xj2, yj2)
Distanza di Lagrange
© Igor Rossini
Misure di Distanza (5)
• Distanza di Minkowski
dove q è un intero positivo
q q
pp
jxixjxixjxixjid )||...|||(|),(2211
−++−+−=
© Igor Rossini
Considerazioni (1)
• Distanza Euclidea:– Invariante rispetto a traslazioni o rotazioni degli assi
• Distanza di Manhattan:– Particolarmente indicata per variabili su scala ordinale– Non invariante rispetto a traslazioni o rotazioni degli
assi– Pone meno enfasi sulle variabili con distanze maggiori
non elevando al quadrato le differenze
© Igor Rossini
Considerazioni (2)
• Distanza di Minkowski:– E’ la generalizzazione delle altre distanze:
q=1 Manhattanq=2 Euclideaq=∞ Lagrange-Tchebychev
• Standardizzazione:– Necessaria per eliminare distorsioni nel caso di
fenomeni con unità di misura e ordini di grandezza diversi
© Igor Rossini
Binary Variables (1)
• Rappresentati con una tabella di contingenza
pdbcasumdcdcbaba
sum
++++
01
01O
bjec
t i
Object j
© Igor Rossini
Binary Variables (2)
• Simple matching (invariante se la variabilebinaria è simmetrica)
• Coefficiente di Jaccard (non-invariante se la variabile binaria è asimmetrica):
dcbacb jid+++
+=),(
cbacb jid++
+=),(
© Igor Rossini
Esempio
• gender è un attributo simmetrico• i rimanenti attributi sono asimmetrici• assumiamo i valori Y e P uguali ad 1, il valore N a 0
Fever
N
P
N
Test-3
N
N
N
Test-4
NNPYMJim
NPNYFMary
NPNYMJack
Test-2Test-1CoughGenderName
75.0211
21),(
67.0111
11),(
33.0102
10),(
=++
+=
=++
+=
=++
+=
maryjimd
jimjackd
maryjackd
© Igor Rossini
Variabili Nominali
• Generalizzazioni delle variabili binarie (possono assumere molteplici etichette es. giallo, verde, rosso, ecc.)
• Metodo 1: Simple Matching– m: # of matches, p: total # of variables
• Metodo 2: utilizzo di un set di variabili binarie– Creazione di una nuova variabile per ciascuna delle M
etichette
pmpjid −=),(
© Igor Rossini
Variabili Ordinali
• Possono essere discrete o continue• L’ordine è importante (es. rank) • Possono essere trattate come le variabili a scala
per intervallo– Sostituendo xif con il rank corrispondente
– Scalando i valori nel range [0, 1] sostituendo l’i-esimovalore nell’ f-esima variabile da
– Calcolo degli indici di similarità con i metodi delle variabili a scala per intervallo
},...,1{ fif Mr ∈
11−−
=f
ifif M
rz
© Igor Rossini
Variabili a Scala per rapporto
• Valori positivi su una scala non lineare come ad esempio l’esponenziale AeBt or Ae-Bt
• Metodi:– trattarle come variabili a scala per intervallo
– applicare una trasformazione logaritmica
yif = log(xif)– trattarle come variabili ordinali continue e trattare i
loro rank come variabili a scala per intervallo
© Igor Rossini
Variabili di Tipo Misto
• Un set di dati può contenere qualsiasi tipo di variabili binari(simmetriche e asimmetriche),nominali, ordinali, a scala per intervallo, a scala per rapporto
• La seguente misura di prossimità pesata tiene conto degli effetti delle diverse variabili
– f is binary or nominal:dij
(f) = 0 if xif = xjf , or dij(f) = 1 o.w.
– f is interval-based: use the normalized distance– f is ordinal or ratio-scaled
• compute ranks rif and • and treat zif as interval-scaled
)(1
)()(1),(
fij
pf
fij
fij
pf d
jidδ
δ
=
=
ΣΣ
=
© Igor Rossini
Selezione dell’algoritmo
• Gerarchici– Scissori– Agglomerativi
• Non Gerarchici– Generazione di Partizioni– Con Sovrapposizione
© Igor Rossini
Metodi per il calcolo delle distanze
• Richiedono come input la matrice delle distanze:– Single Linkage (Metodo del Legame Singolo)– Complete Linkage (Metodo del Legame Completo)– Average Linkage (Metodo del Legame Medio)
• Richiedono come input la matrice dei dati:– Metodo di Ward
• Richiedono come input la matrice dei dati e lamatrice delle distanze:– Metodo del Centroide
© Igor Rossini
Single Linkage Clustering
• La distanza tra due gruppi è definita come il minimo delle n1n2 distanze tra ciascuna unità di un gruppo A e ciascuna unità dell’altro gruppo B
d(A,B)=min(dij)
i∈A, j∈B
A
B
A
B
© Igor Rossini
Complete Linkage
• La distanza tra due gruppi è definita come il massimo delle n1n2 distanze tra ciascuna delle unità di un gruppo e ciascuna delle unità dell’altro gruppo
d(A,B)=max(dij)
i∈A, j∈B
A
B
© Igor Rossini
Average Linkage
• La distanza tra due gruppi è definita come la media aritmetica delle n1n2 distanze tra ciascuna delle unità di un gruppo e ciascuna delle unitàdell’altro gruppo
d(A,B)=
i∈A, j∈B
∑∑= =
1 2n
1i
n
1j21dijnn
1
A
B
© Igor Rossini
x1
Metodo del Centroide
• La distanza tra due gruppi A e B di numerosità n1 e n2 è definita come la distanza dei rispettivi centroidi (medie aritmetiche) x1 e x2
d(A,B)=d( , )x2
© Igor Rossini
Metodo di Ward
• Questo metodo crea gruppi con la massima coesione interna e la massima separazione esterna
• La creazione dei gruppi avviene minimizzando la seguente funzione obiettivo:
T=W+BT=devianza totaleW=devianza nei gruppi (within groups)B=devianza fra i gruppi (between groups)
• Ad ogni passo della procedura si aggregano i gruppi che comportano il minor incremento W e il maggior incremento in B
© Igor Rossini
Valutazione del Risultato
• Per ogni livello gerarchico dell’algoritmo di classificazione si calcolano degli indicatori statistici
• Tali indicatori statistici misurano la variabilità:– tra i cluster, ovvero il livello di eterogeneità tra un
gruppo e l’altro (separazione esterna)– entro i cluster, ovvero il livello di omogeneità
all’interno dei gruppi (coesione interna)
• Il valore di tali indicatori fornisce una misura della qualità della clusterizzazione
© Igor Rossini
Indicatori Statistici (1)
• R2 = rapporto tra la varianza tra i cluster e la varianza totale
R2=1-(W/T)=B/T• RSQ = valore di R2 per ogni livello gerarchico
• Caratteristiche dell’indicatore:– R2 ∈[0,1]– Valori prossimi ad 1 indicano partizioni ottimali– R2=0 in presenza di un solo gruppo
• La sola massimizzazione dell’R2 porta a gruppi costituiti da una sola unità (necessario l’uso congiunto di altri criteri)
© Igor Rossini
Indicatori Statistici (2)
• PSF (Pseudo F Statistic) = misura del grado di separazione tra i cluster ad ogni livello gerarchico
• Diminuisce al diminuire del numero di cluster che originano dal processo di classificazione gerarchica
• Brusche variazioni indicano raggruppamenti di cluster molto diversi fra loro
c)W/(n1)B/(cPSF−−
=c=numero di gruppi
n=numero di osservazioni
© Igor Rossini
Indicatori Statistici (3)
• RMSSTD = indica la devianza fra i gruppi “aggiuntiva” che si forma al corrispondente passo della procedura di classificazione
• Un forte incremento rispetto al passo precedente indica l’unione di due gruppi fortemente eterogenei
h=passo h-esimo della proceduraWh=devianza del gruppo del passo hnh=numerosità del gruppo del passo h
p=numero di variabili considerate1)p(n
WRMSSTDh
h
−=
© Igor Rossini
Indicatori Statistici (4)
• SPRSQ (Semipartial R2) = misura l’incremento della devianza all’interno del gruppo ottenuto unendo i gruppi r e s
• Un forte incremento rispetto al passo precedente indica l’unione di due gruppi fortemente eterogenei
T)WW(WSPRSQ srh −−
=
h=nuovo gruppo ottenuto al passo h come fusione dei gruppi r e s
Wh=varianza interna al gruppo h
Wr=varianza interna al gruppo r
Ws=varianza interna al gruppo s
© Igor Rossini
Esempio (1)
• Clusterizzazione gerarchica con il metodo della MEDIA DI GRUPPO
CLUSTER HISTORY
-
38.7
27.6
32.6
34.2
38.0
57.9
51.8
62.0
6.3
PSF
38.7
14.4
35.3
28.4
34.8
90.7
10.0
63.2
40.4
7.9
PST2
4.1698
2.5363
1.9538
1.4506
1.0961
1.0139
0.945
0.9253
0.8981
0.8598
Norm RMS Dist
.1300.0461260OB178CL32
.0000.1299261OB177CL21
.1760.0996259CL11CL43
.2760.0726255CL17CL54
.3480.0790249CL7CL65
.4270.1505233CL9CL86
.5780.011216CL13CL107
.5890.0740190CL14CL168
.6630.044143CL12CL159
.7070.004713OB250CL1810
RSQSPRQSFREQCluster JoinedNCL
© Igor Rossini
Esempio (2)• Clusterizzazione gerarchica con il metodo di
WARDCLUSTER HISTORY
-
58.1
70.2
74.8
83.1
91.6
93,7
97.9
99.6
193
PSF
58.1
77.8
115
51.0
28.4
50.8
44.0
86.3
19.6
16.2
PST2
.1830.1692218CL3CL52
.0000.1832261CL4CL21
.3520.1137178CL8CL63
.4660.098843OB117CL74
.5650.077540CL10CL95
.6420.046471CL15CL136
.6890.041742CL17CL197
.7300.0294107CL11CL1818
.7600.026622OB178CL129
.7860.025118CL24CL1410
RSQSPRQSFREQCluster JoinedNCL
© Igor Rossini
Indicatori Statistici
• Frequency = numero di unità statistiche appartenenti a ciascun cluster
• Max Distance from Seed to Observation = indica la distanza massima tra il centroide di ciascun cluster e la relativa osservazione maggiormente distante
• Distance between Cluster Centroids = indica la distanza tra i centroidi dei cluster individuati
• R_Squared = quota di varianza spiegata dall’analisi a livello totale e relativamente a ciascuna delle variabili di input
© Igor Rossini
Esempio (1)
• Clusterizzazione non gerarchica
1.948228.07820.67734034
RMS Std Deviation
CLUSTER SUMMARY
2.728329.40410.77062413
2.708126.04030.82792765
1.948241.78440.433912782
2.315127.71490.96952271
Distance between Cluster Centroids
Nearest Cluster
Maximum Distance from
seed toObservation
FrequencyCluster
© Igor Rossini
Esempio (2)
• Clusterizzazione non gerarchica
1.0882120.5211210.692681.00015CONSUMO
Within STD
STATISTICS FOR VARIABLES
0.5945380.3728590.724760.91444ACCUMULO
1.3969960.5828110.632540.97850OVER-ALL
2.4635200.7112760.536310.99728FEDEL_A
2.2514430.6924440.554700.99940FEDEL_B
RSQ/(1-RSQ)
R-SquareTotal STDVariable
© Igor Rossini
Esempio (3)
• Statistiche descrittive per i clusterindividuati
1.3632070.175172-0.607266-0.6180304
FEDEL_A
CLUSTER MEANS
0.556859-0.588238-0.1742112.1502743
0.342491-0.0769832.307065-0.2371535
-0.490447-0.230027-0.263096-0.3417842
-0.6642001.613325-0.0773651.0355741
CONSUMOACCUMULOFEDEL_BCluster
© Igor Rossini
Esempio (4)
• Statistiche descrittive per i clusterindividuati
0.9524630.8166700.4050770.3106474
FEDEL_A
CLUSTER STANDARD DEVIATIONS
0.7651120.6865020.5152161.0263293
0.7114930.9591221.0234510.5178665
0.5772830.4772430.3450800.2701272
0.6351741.2375690.7474981.1251301
CONSUMOACCUMULOFEDEL_BCluster
Ing. Igor RossiniLaurea in Ingegneria InformaticaPolitecnico di MilanoPolo Regionale di Como
Metodologie per Sistemi Intelligenti
Clustering – Esempi Applicativi
© Igor Rossini
Hierarchical Clustering Case
• A study to classify the cost impact of deregulation
• Need to build a detailed cost model of the various utilities
• The objects to be clustered are the utilities and there are 8 measurements on each utility
• Use of XLMinerTM tool
© Igor Rossini
Dialog Box XLMinerTM tool (1)Data Range: Specify the range containing the data to be clustered
Data Type: Hierarchical clustering can be used on Raw data (like the Utilities dataset above) or data in the distance matrix format (Explained in Ex 2.) Choose Raw data here
Variable Names in the First Row: When this box is checked, XLMinerTM picks up variable names from the headers in the first row of the selected data range
Variables: This list box displays all the available variables in the data range
Selected Variables: From the list of all available variables, select those to be used in the clustering process
© Igor Rossini
Dialog Box XLMinerTM tool (1)Normalize input data: Normalizing the data (subtracting the mean and dividing by the standard deviation) is important to ensure that the distance measure accords equal weight to each variable
Similarity Measure: The option Euclidean distance is automatically chosen as explained in "Using Hierarchical Clustering"
Clustering Method: Select average group linkage method
© Igor Rossini
Dialog Box XLMinerTM tool (1)Draw dendogram: shows the dendogram
Show cluster membership: gives the history of cluster raggrupmenf for each iteration
# Clusters: the desired number of clusters
© Igor Rossini
Clustering StagesClustering Stages:This output details the history of the cluster formation
© Igor Rossini
K-mean Case
• A telecommunications provider wants to segment its customer base by service usage patterns
• Need to build a model to classify customers in order to offer more attractive packages
• The objects to be clustered are the client and there are 42 measurements on each client
• Use of SPSS tool
© Igor Rossini
Dialog Box SPSS tool (1)Variables: displays the variables you have chosen for the anaysis
Method: updates initial cluster centers in an iterative process
Label Cases By: optionally you can use the values of a string variables to identify cases
© Igor Rossini
Dialog Box SPSS tool (2)Maximum iterations: limits the number of iterations in the k-means algorithm.
Convergence criterion:determines when iteration ceases
Use running means: allows you to request that cluster centers be updated after eachcase is assigned
© Igor Rossini
Dialog Box SPSS tool (3)Initial cluster centers: first estimate of the variable means for each of the clusters
ANOVA table: displays an analysis-of-variance table wich includes univariate F test for each clustering variable
Cluster information for eachcase: displays for each case the final cluster assignment and the euclidean distance between the case and the cluster center
Exclude cases listwise:escludes cases with missingvalues for any clusteringvariable from the analysis
Exclude cases pairwise:assigns cases to clusters based on distances computed from all variable with no missing values
© Igor Rossini
Iteration Historyshows the progress of the clustering process at each step
In early iterations, the cluster centers shift quite a lot.
By the 14th iteration, they have settled down to the general area of their final location, and the last four iterations are minor adjustments
© Igor Rossini
Change in Cluster CentersIf the algorithm stops becausethe maximum number of iterations is reached, you may want to increase the maximum because the solution may otherwise be unstable
For example, if you had left the maximum number of iterationsat 10, the reported solution would still be in a state of flux
© Igor Rossini
ANOVA Tableindicates which variables contribute the most to your cluster solution
Variables with large F values provide the greatest separation between clusters
© Igor Rossini
Final Cluster Centersare computed as the mean for each variable within each final cluster
Customers in cluster 1: tend to be big spenders who purchase a lot of services
Customers in cluster 2: tend to be moderate spenders who purchase the "calling" services
Customers in cluster 3: tend to spend very little and do not purchase many services
© Igor Rossini
Cluster Distance and Numerosity
Euclidean distances betweenthe final cluster centers
Clusters 1 and 3 are most different
Cluster 2 is approximately equally similar to clusters 1 and 3
Cluster Numerosity: indicatesthe number of records in eachcluster
Clusters 3 is the biggest which unfortunately is the least profitable group