DBSCAN and Semi-Supervised Learning: When Clustering Helps You Label

Lectures 9a and 9b. Bishop's book covers neither DBSCAN nor semi-supervised learning (both became more prominent in the literature after 2006), so this post leans more on what the professor showed, with far less direct citing of the book than usual around here.

Where K-means falls flat

The professor generates a classic synthetic dataset, make_moons: two interleaving arcs, like two crescent moons locked together.

from sklearn.datasets import make_moons
X, y = make_moons(n_samples=1000, noise=0.05, random_state=42)

Running the K-means I already covered in the previous post with K=2 on this data gives a poor result: K-means always cuts space into convex regions (every point goes to its nearest centroid, so the boundary between groups is always a straight line), but the two moons aren't convex, they nest into each other's curve. K-means ends up cutting nearly down the middle, ignoring the arcs' actual shape. Measuring agreement between K-means's grouping and the real moon split (using the adjusted Rand index, a metric that equals 1 when the groups perfectly match the real split and sits near 0 when it's about as good as guessing at random): 0.24. Barely any match.

DBSCAN: grouping by density, not distance to a center

The professor describes the algorithm in plain text, no formula:

• For every point, count how many other points sit within a small distance $\varepsilon$ (epsilon) of it. That's the $\varepsilon$-neighborhood.
• If a point has at least min_samples neighbors at that distance (counting itself), it's a core point (it lives in a dense region).
• Every point in a core point's neighborhood belongs to the same group. Since that neighborhood can contain other core points, a chain of neighboring core points forms a single group, no matter how long that "string" gets.
• Any point that isn't core and isn't in any core point's neighborhood is noise (label -1), it belongs to no group at all.

The core difference from K-means: DBSCAN never assumes a group has "a center." It just follows dense regions, so it can trace crooked shapes, like two crescent moons.

from sklearn.cluster import DBSCAN
dbscan = DBSCAN(eps=0.05, min_samples=5)
y_pred = dbscan.fit_predict(X)

Output (eps=0.05): 7 groups, 77 points marked as noise.

Too small an $\varepsilon$ fragments the whole dataset into little pieces, because too few points fall inside such a tight neighborhood.

dbscan = DBSCAN(eps=0.2, min_samples=5)

Output (eps=0.2): exactly 2 groups, zero noise points, adjusted Rand index of 1.0: a perfect match with the real moon split.

Interactive: nudging eps and min_samples live

My own reconstruction of the algorithm (on a sample of 300 points from the same two moons, to run fast in the browser). Move both controls and watch the number of groups and noise points shift:

With a tiny eps, almost everyone turns into noise (gray). Raising eps bit by bit, groups start forming, until at some point the two moons show up whole. Push past the right point and the two moons merge into one. min_samples works similarly: higher values demand a more crowded neighborhood before someone can become a core point, so groups get pickier (more noise, more "solid" groups).

The problem of having no .predict()

DBSCAN keeps no centroid at all, so there's no way to ask "which group does this new point belong to?" the way K-means does. The professor's fix: train a separate KNN, using only DBSCAN's core points (dbscan.components_) and each one's group as the label.

from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=50)
knn.fit(dbscan.components_, dbscan.labels_[dbscan.core_sample_indices_])
print(knn.predict(X_new))

Output: [1, 0, 1, 0] for the 4 new points tested.

But that has a catch: KNN always finds a nearest neighbor, no matter the distance, so it'll "predict" a group for any point, even one far from everything, that should really be noise. The fine-tuning: check the distance to the nearest neighbor and, if it's too large (the professor uses eps itself as the cutoff), mark it as noise (-1) instead of forcing it into a group.

Switching topics: what if labels are expensive?

The second half of the lecture switches problems, but reuses the idea of grouping without labels. Scenario: 1400 handwritten digit images for training, but labeling each one is expensive manual work, so only 50 can be labeled.

n_labeled = 50
log_reg = LogisticRegression(solver="liblinear", max_iter=5000)
log_reg.fit(X_train[:n_labeled], y_train[:n_labeled])

Output (labeling the first 50 images, in whatever order they came): 0.766 test accuracy.

Output (if I had labels for all 1400, the theoretical ceiling): 0.902.

The trick: choosing which 50 to label, not which come first

Instead of labeling the first 50 (an arbitrary order), the professor uses K-means with K=50 (the same label budget!) to find 50 groups in the 1400 unlabeled images, and picks, from each group, the image closest to the center (the most "typical" one in that group):

kmeans = KMeans(n_clusters=50)
X_digits_dist = kmeans.fit_transform(X_train)
representative_digit_idx = np.argmin(X_digits_dist, axis=0)

Only those 50 representative images get manually labeled (the professor pasted in the correct labels by hand, cell 8 of the notebook). Training on just those 50:

Output: 0.834. Better than the 50 random labels (0.766), with the same number of labels.

That tracks: 50 images chosen to represent 50 different groups cover more variety than 50 images in whatever order they arrived (which might repeat the same "7" style several times and never show a crooked "3").

Propagation: spreading the label to the whole group

If group 12's representative image is a "7," it's reasonable to assume everyone in group 12 is also a "7" (that's why they landed in the same group, after all). Propagating the representative's label to every member of the cluster:

y_train_propagated = np.empty(len(X_train), dtype=np.int32)
for i in range(k):
    y_train_propagated[kmeans.labels_==i] = y_representative_digits[i]

Output: training on all 1400 propagated labels (but only 50 truly hand-checked): 0.869. And checking against the real label (something only possible here because it's an exercise, in real life you wouldn't know it): the propagation is right 95.4% of the time.

One more refinement: dropping, from each group, the 20% farthest from the center (the "border" points, more likely to have been assigned to the wrong group) before propagating:

Output: 1111 examples left (out of 1400), with 97.7% propagation accuracy (up from 95.4%). Training on just those: 0.879, the lecture's best result using only 50 truly labeled examples.

And the pattern repeats swapping LogisticRegression for KNN, Random Forest, Gaussian Naive Bayes, and NearestCentroid: in every classifier tested, "representative" beats "50 random," and "propagated" beats "representative alone."

Wrapping up

Practical application

I reproduced the full chain (50 random → representative → propagated) on the same digits dataset, with a fixed seed, to confirm the gain wasn't a coincidence from one specific run.

log_reg = LogisticRegression(solver="lbfgs", max_iter=5000, random_state=42)
# ... same procedure as the professor, with random_state fixed at every step

My numbers land close to the original notebook's (0.766 / 0.834 / 0.869 / 0.954 / 0.902), the difference sits only in the random seed and the logistic regression solver (I swapped liblinear for lbfgs, because the newer scikit-learn version in my environment no longer accepts liblinear for problems with more than two classes). The order between strategies is identical in both runs: random loses to representative, which loses to propagated, confirming the gain is real, not luck from one specific run.