L13 - Hierarchical Structuring and DBSCAN

Question 1

What is hierarchical clustering?

Answer 1

• An unsupervised learning method for clustering similar data points.
• The goal is to represent degrees of similarity within data.
• Enables the partition of data at various levels.

Question 2

What is the structure of hierarchical clustering?

Answer 2

• Clusters and sub-clusters.
• Results in tree-like structure.

Question 3

What are Dendrograms?

Answer 3

Tree diagrams that show a hierarchy of clusters, where each node represents a cluster.

Question 4

In Dendrograms, what are leaves called?

Answer 4

Singletons

Question 5

What are the 2 approaches of creating a Dendrogram?

Answer 5

1. Bottom up -> Agglomerative
   
   2. Top down -> Divisive

Question 6

How is a Dendrogram created using the Agglomerative method?

Answer 6

1. Starting with a set of individual data points
2. Iteratively:
   
   1. Create distance matrix between points
   2. Merge close ones

Question 7

How is a dendrogram created using Divisive method?

Answer 7

• Start with a large set of clustered data points
• Iteratively split the data points

Question 8

What is the time complexity of Hierarchical clustering?

Answer 8

O(N^3)

Question 9

When hierarchical clustering, what is the only thing we need to be able to create?

Answer 9

Distance matrix between points

Question 10

Why can’t we use Brute force to calculate Distance Matrix?

Answer 10

Too many points means too high complexity

Question 11

What are the 5 methods we can use to calculate distance between clusters?

Answer 11

1. Simple Linkage -> Distance defined as the distance between 2 closest data points of 2 separate clusters.
2. Complete Linkage -> Distance defined as the distance between 2 furthest data points of 2 separate clusters.
3. Average Linkage -> Distance is defined as the average distance between all members of each clusters.
4. Centroid Linkage -> Distance defined by the distance between the centroids of each cluster.
5. Wards Method -> Join clusters only if it reduces the total distance from he centroids.

Question 12

What is an issue with each of the 5 distance calculation methods?

Answer 12

1. Simple Linkage -> Can lead to a long chain of clusters
2. Complete Linkage -> Often breaks large clusters into 2 or more
3. Average Linkage -> High computational cost and complexity due to every data point needing to be visited.
4. Centroid Linkage -> Biased towards spherical clusters
5. Wards Method -> Biased towards spherical clusters

Question 13

What method do we use to know if we have a good cluster count?

Answer 13

Elbow method

Question 14

What is DBSCAN?

Answer 14

Not to compare every point (such as hierarchical clustering), but to have a density threshold around each point, and if the threshold area contains enough other data points, the point can be known as a Dense Point.

Question 15

What are the 2 hyper parameters of DBSCAN?

Answer 15

Epsilon -> Radius of density threshold

MinPts -> Min no of points need in threshold to be considered a dense point

Question 16

How are points categorised in DBSCAN?

Answer 16

Core point -> If a point has more than a specified number MinPts in its Epsilon. These points are in the interior of a cluster

Border point -> I the point has fewer points that MinPts in it’s Epsilon, but is in the neighbourhood of a core point

Noise point -> Any point that is not a core or border point

Question 17

What is the result of DBSCAN?

Answer 17

All points within a cluster can reach one another through steps of size Epsilon

Question 18

What are the pros and cons of DBSCAN?

Answer 18

Pros -> Resistant to noise. Can handle clusters of different shapes and sizes.

Cons -> Eps and MinPts interact and can be hard to specify.

Question 19

What are 2 limitations of DBSCAN?

Answer 19

• Struggles to cluster with varying densities
• Highly dependent on Eps and MinPts selection