Evaluating Clustering Algorithms

DBSCAN stands for density-based spatial clustering of applications with noise. It is a clustering algorithm that groups points by how crowded their neighborhoods are, and it can also flag points that belong to no group at all. This article begins with code rather than theory, because the most useful way to understand DBSCAN is to run it and look at what comes back.

Many clustering methods ask you to choose the number of clusters before they run. DBSCAN does not. It looks for points that sit in crowded regions of the feature space, where many data points lie close together. These crowded regions are called dense regions. The core idea is that a cluster is a dense region of data, and clusters are separated from one another by regions that are comparatively empty.

DBSCAN has exactly two parameters, and every label it returns is a consequence of them. The first is eps, a distance. Two points count as close when the distance between them is eps or less. The second is min_samples, a count. It is the minimum number of data points that must lie within eps of a given point before that point counts as belonging to a dense region.

There is a trade-off in exchange for this flexibility. The source notes that DBSCAN is somewhat slower than agglomerative clustering and k-means, although it still scales to relatively large datasets.

After DBSCAN finishes, every point falls into exactly one of three kinds. Core points are dense enough to satisfy the min_samples rule: they have at least min_samples points within eps. Boundary points lie within distance eps of a core point but do not satisfy the rule themselves. Noise points are the rest; they belong to no cluster and receive the label -1.

The distinction between core and boundary points matters for reproducibility. Running DBSCAN repeatedly on the same dataset always gives the same clustering of core points, and the same points are always labeled as noise. A boundary point, however, may sit next to core samples from more than one cluster. Its membership then depends on the order in which points are visited. The source points out that there are usually only a few boundary points, so this dependence is rarely important in practice.

DBSCAN does not look at all points at once. It works through the dataset one unvisited point at a time, deciding for each point whether it starts a new cluster, joins an existing one, or is noise. Follow one starting point through this flow. If it lacks enough neighbors, it is set aside as noise and the algorithm moves on. If it has enough neighbors, a cluster is born, and growth proceeds outward through core samples only. A neighbor that is not itself a core sample joins the cluster but does not extend it further.

Read the flowchart as a loop. A cluster grows only when a newly reached point is itself a core sample. A boundary point is reached and labeled, but its own neighbors are not used to pull in further points. This is the mechanism behind the core and boundary distinction from the previous section.

DBSCAN labels each data point either as noise or as a member of a cluster. Cluster members receive non-negative integer labels such as 0, 1, and 2. Noise points receive the label -1. A result of [-1] therefore means every point was classified as noise and the algorithm formed no clusters. The position of each label in the returned array matches the position of the input point it describes, so labels[i] is the label for the i-th row of the data.

A useful way to think about -1 is that it is not a cluster at all. It is a bin for points that DBSCAN could not place in any density-based group. Because -1 is negative, it cannot be counted directly with a function that only accepts non-negative integers, so the source shifts every label up by one before counting. The noise bin then lands at index 0 of the count array, and the first number in the count is always the number of noise points.

The source uses a two-moons dataset, which consists of two interleaved half-circles. The data is rescaled to zero mean and unit variance before clustering, and DBSCAN runs with its default settings. With those defaults, the source reports that DBSCAN finds the two half-circles and separates them, which is the desired result. The default eps is 0.5.

A single trial is rarely enough to choose eps. The source loops over several eps values with min_samples held constant and prints the clusters present and the size of each one. Read that sweep from both directions. At the low end, noise dominates. Near the middle, many small clusters sit alongside a large noise group. At the high end, one big cluster accounts for most of the data. The source observes that there is never more than one large cluster at any setting.

Once DBSCAN has produced a result with both noise and clusters, the noise points can be pulled out and examined. The source uses a boolean mask, labels == -1, to select the images DBSCAN labeled as noise. Those images did not fit any dense group. Finding the odd one out in this way is called outlier detection, and DBSCAN can perform it, because noise is simply the set of points that do not belong to a cluster.

In the source's eps=15 run, DBSCAN produced 27 noise points. Because there were so few, it was practical to inspect every one. Comparing them with typical faces suggested why each was labeled as noise. One image showed a person drinking from a glass, several showed people wearing hats, one had a hand in front of the face, and others had odd angles or crops that were too close or too wide. The source adds that some of these issues can be fixed by better cropping, while others, such as hats or hands in front of faces, must simply be handled by any algorithm applied to this data.

The source then applies k-means to the same PCA data. The key difference is that k-means must be told how many clusters to produce, and it partitions every point into one of them. With n_clusters set to 10, the source reports cluster sizes ranging from 64 to 386, which it describes as relatively similarly sized. This differs strongly from the DBSCAN result, where cluster sizes were very uneven and noise was present.

The source also notes a consequence of k-means partitioning everything. Points far from a cluster center are still forced into that cluster, so their assignments can look arbitrary. Because k-means has no concept of noise, it cannot flag these points the way DBSCAN does. A larger number of clusters might reveal finer distinctions, but more clusters also make manual inspection harder.

To ask whether two methods agree, the source uses the adjusted Rand index, written ARI. It runs agglomerative clustering with 10 clusters and computes the ARI between its labels and the k-means labels. An ARI of 0.13 indicates the two partitions have little in common. The source reads this as expected, because points far from k-means centers have little in common with each other.

Most unexpected clustering results trace back to one of a few places in the workflow: the parameter values, the interpretation of labels, or the assumption that a clustering reflects real structure. Work through the pipeline in order and check each stage before blaming the algorithm. The earliest stage that looks wrong is usually where the surprise begins.