DBSCAN

Look at a map of a city at night, from above. You see bright, dense areas, and dark gaps between them. Those bright areas have all sorts of strange shapes, and they are not circles. You would never ask how many there are in advance. You simply see them. DBSCAN finds clusters the same way, by density.

• City lights from above
• Dense areas, strange shapes
• Clustering by density

How DBSCAN thinks

DBSCAN has two settings. Epsilon is the size of a neighbourhood, and min samples is how many points must be inside it. A core point has plenty of neighbours. Clusters grow outward from core points, spreading to everything that they can reach. Any point that cannot be reached by any cluster is labelled as noise. So you do not choose the number of clusters, and it can reject outliers.

Two moons

Here are two interlocking crescent moons, a shape that defeats k means. We run both algorithms, and compare each with the truth. Run it. K means cuts straight across the moons, and matches poorly. DBSCAN follows the curves, and scores nearly perfectly. It found the two clusters by itself, and on data this clean, no point needed to be called noise. Same data, and a totally different result, because it looks at density instead of distance to a centre.

from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

X, truth = make_moons(n_samples=500, noise=0.06, random_state=0)

km = KMeans(n_clusters=2, n_init=10, random_state=0).fit_predict(X)
db = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)

print("K-Means match:", round(adjusted_rand_score(truth, km), 3))
print("DBSCAN match: ", round(adjusted_rand_score(truth, db), 3))
print("Clusters found:", len(set(db)) - (-1 in db))
print("Points called noise:", (db == -1).sum())

K-Means match: 0.253
DBSCAN match:  1.0
Clusters found: 2
Points called noise: 0

Which clustering method?

Here is your guide. K means is fast and simple, for round groups on big data. Hierarchical gives a full tree, on smaller data. And DBSCAN handles odd shapes and noise, but struggles if the density varies a lot. Most projects start with k means, because it is quick, and move on if the groups do not make sense.

Summary