Hierarchical Clustering, Agglomerative Clustering & DBSCAN

What is hierarchical clustering

A clustering approach that builds a hierarchy of clusters, where each node is a cluster made up of its “daughter” clusters - often visualized as a dendogram

What are the two main types of hierarchical clustering

Agglomerative (bottom up, more popular) and Divisive (top down, dividing clusters)

What is the basic idea of agglomerative hierarchical clustering

Start with each object in its own cluster, then repeatedly merge the closest pair of clusters until only one cluster containing everything remains

What is a proximity (distance) matrix in agglomerative clustering?

A square using n*n matrix showing the distance between every pair of points, calculated using a distance formula like Euclidean distance; diagonal elements are always 0

What is the initial step of agglomerative clustering

Assign every point to its own individual cluster and compute the initial proximity/distance matrix

At each step of agglomerative clustering what do you do

Find the smallest distance in the (derived) proximity matrix, merge those two clusters, and update the matrix with the new inter cluster distances

What happens by the final step of agglomerative clustering

All clusters are merged into a single cluster containing every point - starting from n clusters and ending at 1

Do you need to specify the number of clusters upfront in hierarchical clustering

No instead you can decide “when to stop” merging, using a dendogram

What does the vertical distance in a dendrogram represent

The greater the distance the greater the distance between the clusters being merged at that point

How do you determine the number of clusters from a dendrogram using a threshold line

Draw a horizontal threshold line (often set to cut the tallest vertical line); the number of clusters equal the number of vertical lines the threshold line intersect

What is single linkage clustering

Inter cluster distance is defined as the minimum distance across all cross cluster point pairs

What is complete linkage clustering

Inter clustering distance is defined as the maximum distance across all cross cluster point pairs

What is average linkage clustering

Inter cluster distance is defined as the average distance across all cross cluster point pairs

What is centroid linkage clustering

Inter cluster distance is defined as the distance between the two clusters’ centroids (means)

What is Ward’s linkage method

It defines inter cluster distance as the increase in total within cluster variance (SSE) that would result in merging two clusters and chooses the merge that causes the smallest increase in SSE

How is SSE (sum of Squared Errors) defined for a cluster

The sum of squared distances of each point in the cluster from that cluster’s centroid

What is DBSCAN

Density Based Spatial Clustering of Applications with Noise - a clustering algorithm that groups points based on density rather than distance to a centroid

What are wo key drawbacks of K-Means that DBSCAN addresses

K-Means forces every point into some cluster (even outliers) and it requires you to pre specify K, DBSCAN doesn’t require specifying the number of clusters and can separate out noise/outliers

Why does DBSCAN tend to produce more reasonable clusters than K-Means on odd shaped data

Because it locates regions of high density and separates outliers, rather than assigning every point to a cluster based on mean distance

What are DBSCAN’s two key parameters

minPts (minimum number of points required for a region to be considered dense) and epochs (the distance threshold defining a point’s neighborhood)

What is “density reachability” in DBSCAN

A point is density reachable from another point if it lies within distance epoch of it

What is “density connectivity” in DBSCAN

A transitive, chaining relationship - points p and q are connected if there’s a chain p→r→ s→ t→ q where each point is in the nieghborhood of the previous one

What is a Core point in DBSCAN

A point that has at least minPts points within distance epoch (including itself)

What is a Border point in DBSCAN

A point with fewer than minPts neighbors within epoch, but that’s itself within epoch distance of a Core point

What is a Noise point in DBSCAN

A point that is neither a Core point nor a Border point

What are the main steps of the DBSCAN algorithm

1) Set epoch and minPts

2) mark all points unvisited

3) pick an unvisited point and retrieve it’s epoch neighborhood

4) if the neighborhood has >= minPts points, start a new cluster and expand it via density reachability, otherwise mark the points as noise

5) recursively expand cluster to density reachable neighbors

6) repeat until all points are visited

Why is a point marked “noise” only temporarily during DBSCAN

Because it could later turn out to be a Border point if it’s found to be within epoch of a Core point discovered later in the process

What is the rule of thumb minimum for minPts based on data dimensionality D

MinPts >= D + 1; minPts = 1 doesn’t make sense (every point becomes it’s own cluster), and minPts should be chosen at least 3, with minPts = 2 * dimension as a common rule

What happens with DBSCAN if minPts <= 2

The result becomes equivalent to hierarchical clustering with single linkage with the dendogram cut at height epoch

How can a good value of epoch be chosen

Using a k-distance graph, plotting the distance to th k = minPts - 1 nearest neighbor ordered from largest to smallest and picking the “elbow” point of that plot

What happens if epoch is chosen too small or too large

Too small: much of the data won’t get clustered (ends up as noise)

Too large: clusters merge together from largest to smallest, and picking “elbow point” of that plot

Why is the choice of distance function important for DBSCAN

It’s tightly linked to the choice of epoch and has a major impact on results, an appropriate similarity measure for the dataset must be identified first, since there’s no formulaic way to estimate the best distance function.