Hierarchical Clustering

Question 1

What are the 2 stratagies for hierarchical structuring

Answer 1

Top-down: start with one cluster, recursivly split

Bottom-up: start with singleton clusters, merge

Question 2

How does aglomerative clustering work?

Answer 2

1. Start with a cluster for each point
2. Find the pair of clusters that are clostest
3. Merge the clusters
4. Repeat until 1 cluster

Question 3

What is a hierarchical tree of clusters diagram called?

Answer 3

Dendrogram

Question 4

Whats the runtime complexity of aglormerative clustering?

Answer 4

O(n²d + n³)

Question 5

What is single link cluster distance measure?

Answer 5

Distance between clostest points

Question 6

What is complete link cluster distance measure?

Answer 6

Distance between farthest elements in cluster

Question 7

What is the problem with single link?

Answer 7

Produces long chains (often we want spherical clumps)

Question 8

What does complete link prefer (cluster shape)?

Answer 8

Spherical clusters with constant diameter

Question 9

What is average link cluster distance measure?

Answer 9

Question 10

What is centroid cluster distance measure?

Answer 10

Distance between centroids of clusters

Question 11

What is Ward’s method cluster distance measure?

Answer 11

The total distance from all points from the centroid formed if the two clusters where merged

Question 12

What is the Lance-Williams algorithm?

Answer 12

1. Compute D, the distance matrix between each point (singleton centroid)
2. For N iterations
   
   1. Pick smallest D_i,j
   2. Delete D_i and D_j and add D_i+j
   3. For each k != i or j update the distance (where alpha and beta are constants based on the cluster distance measure used)