DBSCAN and Clustering Evaluation

This article begins with a result that most learners do not expect. A short script runs DBSCAN on a dataset of face images and prints the unique labels that come back. The printed output is [-1]. Many learners read that as a clustering that failed in some strange way, or as a list with a stray value in it. The source treats this output as the starting point of the lesson, because once you understand why the output looks this way, DBSCAN's parameters and the process of evaluating a clustering result become much easier to reason about.

The data has already been transformed with PCA before clustering. The source describes this PCA representation as a more semantic description of the face images than raw pixels, and notes that it makes computation faster. The clustering runs on that transformed data, which the code refers to as X_pca. Every label and every cluster size in this article describes the PCA-transformed faces, not the original pixel values.

DBSCAN gives every data point a label. Each point is either a member of a cluster or noise. Cluster members receive non-negative integer labels: 0, 1, 2, and so on. Noise points receive the label -1. Because of this rule, the label list tells you which groups exist and whether any points were left out, but it does not tell you how many points belong to each group.

In the source run, the output [-1] means that the only label present is -1. Every point was classified as noise, and the algorithm formed no clusters at all. The source states this directly: all of the data was labeled as noise.

A label list is only a summary. A result that contains both -1 and 0 tells you that a cluster exists, but it does not tell you how large that cluster is or how much of the data is noise. To answer those questions, you count. The source counts labels with np.bincount, which takes a list of non-negative integers and returns how many times each integer appears. Because bincount does not accept negative numbers, the source adds 1 to every label before counting. This shifts the noise label from -1 to 0, so the noise bin lands at index 0 of the count array.

When every point comes back as noise, the source identifies two parameters to consider. The eps parameter controls the size of the neighborhood around each point, so raising it lets each point see more of its surroundings. The min_samples parameter controls how many points are needed before a group counts as a cluster, so lowering it allows smaller groups to qualify. Both parameters push in the same direction: each one makes it easier for points to end up in a group rather than being left as noise. The source's experiment shows that the two do not have equal effect, as the subsections below explain.

The before and after columns above describe the change in qualitative terms. The source does not give a general rule for predicting the exact number of clusters from a parameter value, so use the counting method from the previous section to verify each change rather than assuming it.

A noise point is a point DBSCAN could not place in any density-based group. The reason is that it has too few neighbors within the eps distance to form a dense group on its own or to join one. Because noise is simply the set of points that do not belong to a cluster, DBSCAN can be used to find the odd ones out. Finding them in this way is called outlier detection.

A single trial is rarely enough to choose eps. The source loops over several eps values while holding min_samples constant, and prints both the clusters present and the size of each one. The loop is the most direct way to see how the result changes as the neighborhood grows. The source notes that the search range should sit between 15 and the default of 0.5, which signals that the useful setting lies in the lower part of the range that was tried.

Read the sweep from both directions. At the low end, the output shows that noise dominates. Near the middle, the output contains many small clusters 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.

The sweep is also an evaluation result, not only a parameter result. The source reads the pattern, in which there is never more than one large cluster, as a sign that the faces do not split into several very distinct kinds. Instead, they are roughly equally similar or dissimilar to one another. That reading is a hypothesis to test by inspecting the groups, not a proven fact about the faces.

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. The flowchart below follows the faces experiment from the first fit to the final inspection. In that sequence, the first place an unexpected result appears is usually the label check, which is why the lesson begins there.

The check at label inspection is the one most worth automating in your own work. If the label list is [-1], stop there, adjust parameters, and refit. Only after the labels contain non-negative values does it make sense to count points and inspect the groups.

The source applies k-means to the same PCA data to show how a different algorithm behaves. The key difference is that k-means must be told how many clusters to produce, and it assigns every point to one of those clusters. With n_clusters set to 10, the source reports cluster sizes ranging from 64 to 386, which it describes as relatively similarly sized. That is quite different from the DBSCAN result, where cluster sizes were very uneven and noise was present.

The difference in cluster sizes follows from how each algorithm assigns points. DBSCAN grows clusters only where points are dense enough and sets the rest aside as noise, so its groups can be large or small and noise can absorb a significant share of the data. k-means has no such option. Points that sit far from a cluster center are still forced into that cluster, which keeps the sizes relatively even but can make individual assignments look somewhat arbitrary.

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