DBSCAN and Density-Based Clustering

Once you have run a clustering algorithm, you need some way to judge the result. A tempting shortcut is to assume that the algorithm with the highest score has found the best grouping of the data. This article tests that assumption, and it uses DBSCAN as the running example. Most of the article is about judging a clustering, but the second half returns to DBSCAN itself, because a clustering run that looks wrong is where you learn the most about its parameters.

There are two broad families of measures for judging a clustering. The first compares the clustering against a ground truth clustering, which is a reference grouping already known to be correct. The second scores the clustering using only the data itself. Each family answers a different question. Measures in the first family ask whether the algorithm recovered a known answer. Measures in the second ask whether the groups look good by their own internal standard.

The adjusted rand index (ARI) and normalized mutual information (NMI) are the two most important metrics for assessing the outcome of a clustering algorithm relative to a ground truth clustering. Both give a quantitative measure between 0 and 1. Their role is to compare the predicted clustering against a reference clustering that is already known. Because the score is a comparison, the ground truth is an input to the metric, not something the metric discovers.

A useful way to read an ARI or NMI value is to see it as an agreement score between two labelings of the same points. The algorithm produces one labeling. The ground truth provides the other. The metric asks how well the two agree, and it is calibrated so that a value near 0 corresponds to agreement no better than chance, while a value near 1 corresponds to close agreement with the reference.

The source uses ARI to compare k-means, agglomerative clustering, and DBSCAN, and it adds a random assignment to two clusters as a baseline. Seeing a random assignment alongside the real algorithms helps you judge whether an algorithm has found any structure at all. A real algorithm should clearly beat chance. If it scores about the same as a random assignment, it has not captured the structure in the data.

The reason ARI and NMI are of limited use in practice is simple. When you apply a clustering algorithm to a real problem, there is usually no ground truth to compare the results against. This is why the summary of the source says these metrics are usually only practical for developing algorithms, where a reference grouping is available for testing.

This leads to the central question for the rest of the article. If you cannot compare against a ground truth, what can you measure? The source turns to scoring metrics that do not need one, and it explains where they fall short.

The silhouette coefficient is a scoring metric for clustering that does not require ground truth. It measures the compactness of clusters. Higher is better, and a perfect score is 1. A high score means that points sit close to other points in their own cluster, which is what compact clusters look like.

The limitation is that compactness does not allow for complex shapes. The source notes that silhouette scores often do not work well in practice for this reason. A method that finds elongated or curved clusters can have a lower silhouette score than a method that cuts the same data into tight, roundish blobs, even when the curved grouping is the one that matches the structure of the data. The score is rewarding a shape preference, not the structure itself.

A slightly better strategy for evaluating clusters is to use robustness-based clustering metrics. These metrics run an algorithm after adding some noise to the data, or using different parameter settings, and then compare the outcomes. The idea is that if many algorithm parameters and many perturbations of the data return the same result, the result is likely to be trustworthy. If the grouping changes whenever the data is nudged slightly, it is less likely to reflect real structure.

Even a very robust clustering or a very high silhouette score does not tell you whether the clusters carry any meaning. The source illustrates this with face images. We might hope to find groups such as men and women, older and younger people, or people with and without beards. Suppose all the algorithms agree on which points belong together. The clusters could still reflect side views versus front views, pictures taken at night versus during the day, or pictures taken with one brand of phone versus another.

The practical lesson is that no metric can confirm that a cluster has semantic meaning. Manual analysis of the clusters is still needed. You must look at what the points in each group actually have in common before you attach a name to it.

The source applies k-means, DBSCAN, and agglomerative clustering to the Labeled Faces in the Wild dataset. Before clustering, it represents the images with eigenfaces, produced by PCA with whiten=True and 100 components. This representation is more semantic than raw pixels and makes the computation faster. The DBSCAN run begins with default parameters, and that first run is the one to trace closely. The trace below follows what the labels tell you at each step.

The divergence happens at the label set step. The expectation is that a dataset of many faces should produce some groups, but the output contains only -1. In DBSCAN output as the source presents it, -1 marks noise, so every single image has been classified as noise and no cluster was formed at all. The labels have diverged from what you expected at this exact point, and everything after it is a question of which parameter caused the problem.

The two parameters pull in different directions in your search for a useful result. eps controls how far a point looks for neighbors, so it governs how large a neighborhood is. min_samples controls how many points a group must contain before it counts as a cluster. Because they interact, you should adjust them deliberately and then inspect the labels after each change rather than assuming the effect.

The before-and-after view shows the same dataset under two parameter settings. The default settings produce a label set containing only -1. Raising eps widens each neighborhood, and lowering min_samples lets smaller groups count as clusters. Whether clusters actually appear, and how many, depends on the data, so the after state is something you check by reading the labels rather than something you can assume from the parameter change alone.