Clusters of any shape: DBSCAN and hierarchies

Choosing eps and min points

Start min points around twice the number of features (4 for two-dimensional data) and raise it if the data is noisy. For eps, a standard trick: for every point, find the distance to its k-th nearest neighbor (k = min points), sort those distances and plot them. The curve stays flat across the crowded regions, then bends sharply upward for the isolated points; eps belongs near the bend.

DBSCAN's weakness is uneven density. One eps can't fit a dense city cluster and a sparse rural one at the same time: small enough for the city and the countryside is all noise; large enough for the countryside and neighborhoods in the city merge. Its relative HDBSCAN handles that by trying every radius and keeping the clusters that persist, and is often the better default today. Scale your features first, too: eps is a distance, and a feature measured in thousands will dominate one measured in single digits.

import math


def neighbors(points, i, eps):
    return []


pts = [(0, 0), (0, 1), (3, 3), (0.5, 0.5)]
print(neighbors(pts, 0, 1.0))

Hierarchical clustering: a family tree of groups

Agglomerative clustering starts with every point as its own cluster and repeatedly merges the two closest clusters until one remains. Recording the merges gives a tree, a dendrogram: cut it high and you get a few big groups, cut it low and many small ones, without rerunning anything.

What "closest clusters" means is the linkage, and it decides the shapes you get:

• single: the distance between the two nearest points, one from each cluster. Follows chains and curves, so it finds the crescents, but one stray point between two groups can join them;
• complete: the distance between the two farthest points. Gives compact, similar-sized clusters;
• average: the average distance over all pairs, a middle ground;
• Ward: the merge that adds the least spread. Behaves much like k-means.

from sklearn.datasets import make_moons
from sklearn.cluster import AgglomerativeClustering
from sklearn.metrics import adjusted_rand_score

X, true_groups = make_moons(n_samples=200, noise=0.06, random_state=0)
for linkage in ("single", "ward"):
    labels = AgglomerativeClustering(n_clusters=2, linkage=linkage).fit(X).labels_
    print(linkage, round(adjusted_rand_score(true_groups, labels), 2))

Single linkage follows the crescents perfectly; Ward splits them like k-means did.

To read a dendrogram, look at the heights of the merges: a big jump between one merge and the next means two well-separated groups were forced together, so cut just below the jump. Many merges at similar heights mean there's no natural number of clusters, and any cut is a choice you should be able to justify.

import math


def cluster_distance(a, b):
    return max(math.dist(p, q) for p in a for q in b)


print(cluster_distance([(0, 0), (1, 0)], [(2, 0), (9, 0)]))

Choosing a method

Start from what you know about the data. If you expect a known number of compact, similar-sized groups, k-means is fast and hard to beat. If groups can be any shape, the number is unknown, or some points belong nowhere, use DBSCAN or HDBSCAN. If you want to explore groupings at several levels, such as product families and then sub-families, hierarchical clustering's tree shows them all at once. It needs every pairwise distance, though, so beyond a few tens of thousands of points it gets slow.

Whatever you choose, check the result by looking: plot the clusters (after reducing to two dimensions if needed), read a sample from each, and compare methods with the adjusted Rand index when you have some known groups. Clustering always returns an answer; only checking tells you whether it's a useful one. A useful clustering is one someone can act on: delivery zones a dispatcher can staff, customer groups a marketer can write to.