How are hierarchical clusters obtained in practice?
Agglomerative clustering (bottom up)
‚ Initiallyplaceeachdatapointinitsownclusters ‚ Repeatedlymergemostsimilarclusters
Divisive clustering (top down)
‚ Splitusingbisectionk-means(orsparsestcut) ‚ Recurseoneachpart
⃝c -Trenn, King’s College London 2
Agglomerative Clustering
b11fh 2d
a 43 2 4 3 1 5 5e1i
cg
An edge can mean similarity or dissimilarity In this lecture we’ll only consider similarities.
A high similarity value means that the corresponding two nodes are very similar and should be in the same cluster
⃝c -Trenn, King’s College London 3
Agglomerative Clustering
b11fh 2d
a 43 2 4 3 1 5 5e1i
Each node starts in a separate cluster
The similarity between two clusters C1 “ ta, bu, C2 “ tc, du is
cg
Single Linkage
Average Linkage
Complete Linkage
b 5 2 3
a1
b 5 2 3
a1
b 5 2 3
a1
c
Similarity: 5
d
c
Similiarity: 2.75
c
Similiarity: 1
d
d
⃝c -Trenn, King’s College London
4
Single-Linkage
Round0:
b1 1f h 2d
a 43 2 4 3 1 5 5e1i
cg
b1 1f h
2d
a 43 2 4 3 1 5
5e1i cg
b1 1f h 2d
a 43 2 4 3 1 5
5e1i cg
Round1:
Round2:
⃝c -Trenn, King’s College London
5
Single-Linkage
Round3:
b1 1f h 2d
a 43 2 4 3 1 5 5e1i
cg
b1 1f h
2d
a 43 2 4 3 1 5
5e1i cg
b1 1f h 2d
a 43 2 4 3 1 5
5e1i cg
Round4:
Round5:
⃝c -Trenn, King’s College London
6
Single-Linkage
Round6:
b1 1f h 2d
a 43 2 4 3 1 5 5e1i
cg
b1 1f h
2d
a 43 2 4 3 1 5
5e1i cg
b1 1f h 2d
a 43 2 4 3 1 5
5e1i cg
Round7:
Round8:
⃝c -Trenn, King’s College London
7
Hierarchical Clustering: Dendogram
acebdfghi
The obtained merges can be represented in a dendogram
⃝c -Trenn, King’s College London 8
Hierarchical Clustering: Divisive Heuristics
21 1 43 2
168 24
4 3 1 5 19
7
Find a partition of the input similarity graph (or set of points) ‚ Splitusingbisectionk-means
‚ on each part
Builds cluster-tree top-down
55 3
⃝c -Trenn, King’s College London 9
Sparsest cut
GivenagraphwithnodesV andedgesinE ĂV ˆV The sparsity of a cut φpSq, is given by
φpSq“ EpS,S ̄q , minp|S|, |S ̄|q
where EpS, S ̄q is the sum of weights of edges crossing the cut. Here S ̄ “ V zS. The sparsest cut of a graph is given by the S ̊ that minimises φpS ̊q, i.e.,
φpS ̊q “ min φpSq S
⃝c -Trenn, King’s College London
10