DBSCAN and OPTICS

You have already met k-means and hierarchical clustering. K-means forces clusters to be round and roughly equal in size; hierarchical clustering builds a tree but still needs you to decide where to cut it. DBSCAN and OPTICS are the tools you reach for when your data has clusters of any shape — a long curved street of shops, a ring of factories around a lake — and when some points simply do not belong to any cluster at all. They are used everywhere in applied machine learning: finding fraud rings that spread out irregularly, grouping similar customer behaviours that do not form neat blobs, and preprocessing data before you build a model. Learning this unlocks the skill of 'exploratory data analysis' — looking at a scatter plot of your data and finding structure in it without knowing in advance how many groups exist.

DBSCAN works like marking out friendship groups on a map of a city. Imagine every house in the city has a GPS coordinate, and you want to find neighbourhoods — clusters — of houses that are close together. The rule is simple: two houses are 'friends' if they are within some walking distance (call it 'epsilon'). But a house is not just friends with its immediate neighbours — it's friends with all the friends of its friends, and so on. So a cluster is all the houses you can reach by hopping from one house to another within epsilon distance, each hop taking you to a house that itself has at least a certain number of friends within epsilon. Houses that are part of a dense crowd — where each house has many neighbours — form the core of a cluster. Houses on the edge of the crowd, with some neighbours but not enough to be a core, are still part of the cluster because they are reachable from a core house. Houses that are all alone, with hardly any neighbours within epsilon, are labelled as noise — they don't belong to any cluster. This is the key difference from k-means: k-means forces every point into a cluster, but DBSCAN says 'this point is an outlier, it belongs to nothing'. The shape of the cluster is whatever the data naturally forms — a long thin line of houses along a river, a circle around a pond — because there is no requirement for a round shape.

Think of a national park ranger trying to map out wolf packs from GPS collar data. The ranger has a rule: a wolf is a 'neighbour' if it is within 10 kilometers of another wolf. But a pack is not just pairs of wolves within 10 km — it is the entire set of wolves you can reach by hopping from one wolf to another, where each wolf you hop from has at least 3 other wolves within 10 km (a 'core' wolf). Wolves on the edge of a pack, with fewer than 3 neighbours, are still part of the pack if they are within 10 km of a core wolf. A lone wolf, far away from any cluster of 3, is labelled as 'noise' — it doesn't belong to any pack. The ranger's map does not assume that packs are round or equal in size; a pack might be a long line of wolves following a river, or a sprawling group around a den, or a small tight group of 4 wolves and a separate one of 20. This is exactly what DBSCAN does with numbers. But the analogy breaks down in one place: the ranger knows what a 'pack' is, and can use her knowledge to set the two numbers — the distance (epsilon) and the minimum pack size (minPts). In DBSCAN, you have to choose these numbers yourself, and the result is very sensitive to them. If the ranger sets the distance too small (say 2 km), she will break every pack into tiny fragments; if too large (say 50 km), she will merge all packs into one blob. That sensitivity is the practical difficulty of DBSCAN, and OPTICS is a variant that softens it by not requiring you to fix the distance in advance — it shows you the structure at all distances at once.

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a clustering algorithm that groups points that are closely packed together — points with many nearby neighbours — into clusters of arbitrary shape, and labels points that lie alone in low-density regions as noise, based on two parameters: epsilon (the maximum distance for two points to be considered neighbours) and minPts (the minimum number of neighbours a point must have to start a cluster).

You have already studied k-means and hierarchical clustering in your notes, and DBSCAN and OPTICS are presented in Simplified Machine Learning as the answer to k-means' assumption of spherical, equally-sized clusters. K-means works by placing k centroids and assigning points to the nearest centroid; it inherits that geometry — clusters are always roughly circular in a 2D plot. DBSCAN has no centroids; it works purely on distances between points, so a cluster can be a spiral, a C-shape, or a long thin line. Your notes on hierarchical clustering mention that you can cut the dendrogram at any level to choose the number of clusters afterwards; DBSCAN instead asks you to commit to a density threshold (epsilon) up front, but OPTICS produces a structure like a dendrogram's 'reachability plot' that lets you choose clusters at various densities afterwards, similar in spirit to cutting a dendrogram. Noise labelling is a feature absent from both k-means and hierarchical clustering — every point belongs to a cluster there, but DBSCAN explicitly says some points are noise.