K-means draws spheres and assigns every point to some cluster; hierarchical clustering merges as far up as you tell it to. Neither of them can say "this point belongs to no group at all" — and for MercaFresh that sentence is worth money, because an order that resembles no known pattern may be a data error, promotion abuse or fraud. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) clusters by density: a cluster is a zone where points crowd together, whatever its shape, and whatever is left in sparsely populated zones gets labeled as noise. In this lesson you will learn its three point types (core, border, noise), its two parameters (eps and min_samples) and how to choose them with the k-distance plot, you will see with make_moons a case where K-means fails and DBSCAN succeeds, and you will apply it to detecting anomalous orders at MercaFresh, connecting it with the statistical detectors from earlier modules.

1. Density-based clustering: the idea
2. Core, border and noise points
3. The eps and min_samples parameters
4. How to choose eps: the k-distance plot
5. Where K-means fails: non-spherical shapes (make_moons)
6. Anomaly detection in MercaFresh orders
7. Head to head: K-means vs. hierarchical vs. DBSCAN
8. Limitations of DBSCAN

The two previous algorithms defined a cluster by proximity to a center (K-means) or by merge order (hierarchical). DBSCAN defines it by local density: a cluster is a set of points connected to each other through dense zones. The intuition is cartographic: if customers were houses, clusters would be villages — it doesn't matter whether the village is round, elongated or horseshoe-shaped; what matters is that the houses stand close together. And the isolated houses out in the wilderness belong to no village: they are noise.

From this definition, the three properties that set DBSCAN apart come for free:

• Clusters of any shape (it follows density, not distance to a center).
• No need to fix K: it finds as many clusters as there are dense zones.
• A native concept of noise: points in sparsely populated zones receive the special label −1.

DBSCAN classifies each point by how much company it has in its neighborhood of radius eps:

The algorithm works like this: take an unvisited point; if it is a core, open a cluster and expand it recursively with every point reachable through chained cores (each core annexes its neighborhood, and the cores in that neighborhood annex theirs); borders join whichever cluster reaches them; when nothing more is reachable, the cluster is closed and the next free core is sought. Whatever is never reached remains as noise. Note the kinship with single linkage from 05-02 — it too chained nearby neighbors — but with a density filter that prevents a bridge of two or three stray points from joining two villages: building a bridge takes cores, and being a core takes company.

DBSCAN's entire behavior hangs on two parameters:

• eps: the neighborhood radius. It is the operational definition of "near". Too small → hardly anyone gathers enough neighbors, almost everything is noise. Too large → neighborhoods overlap across distinct groups and everything collapses into one mega-cluster.
• min_samples: how many neighbors it takes to be a core. It is the definition of "dense". Larger values demand more solid clusters and expel more points into the noise. A common rule of thumb: min_samples ≈ 2 × number of dimensions, and never less than 4 except on tiny datasets.

And a now-familiar warning: eps is a Euclidean distance, so the features must be scaled (03-05). An eps=0.5 means radically different things in euros and in standard deviations.

min_samples is set with the rule of thumb; for eps there is a standard graphical method, the k-distance plot:

1. For each point, compute the distance to its k-th nearest neighbor, with k = min_samples (a familiar tool: NearestNeighbors, the machinery from 04-05).
2. Sort those distances from smallest to largest and plot them.
3. The curve rises gently while it traverses points in dense zones (their k-th neighbor is close) and shoots up when it reaches the isolated points. The curve's elbow is the candidate eps: the boundary between "a normal distance to your neighbors" and "you're on your own".

If the curve stays below ~0.6 and shoots up from there, eps=0.6 is a good starting point — which we will fine-tune by looking at how many clusters and how much noise it produces. This is the module's third "elbow" (inertia in 05-01, dendrogram in 05-02): looking for the sharp jump in a curve is a recurring pattern for separating signal from noise.

The classic demonstration uses make_moons, a synthetic dataset with two interlocking half-moons — two groups obvious to the human eye, but not spherical:

The result speaks for itself:

• K-means draws a straight boundary between its two centroids and splits each moon in half, mixing pieces of both into each cluster. It is not a fitting failure: it is its geometry — every point goes to the nearest centroid, and the centroids of two interlocking moons land where they land. No n_init will fix it.
• DBSCAN walks along each moon by chaining neighboring cores: density is continuous along the half-moon and breaks between one and the other. It recovers the two exact shapes and marks the stray noise points as −1.

This example closes the warning from 05-01 ("spherical clusters"): when the structure is not convex, you don't need a better-tuned K-means but an algorithm with a different definition of cluster.

Now the star use case for MercaFresh. We switch tables: instead of customers, individual orders, with features such as amount, number of items and time of day. The question is no longer "what groups are there?" but "which orders fit into no group at all?" — and there DBSCAN's −1 label goes from by-product to protagonist.

What each label finds:

• The clusters (0, 1, 2...) are the normal buying patterns: the big weekly midday shop, the quick late-night order of a few items, and so on. Nobody asked for them: they emerge from the density.
• The −1 points are orders with no pattern: a €900 amount at 4 in the morning with 3 items; 70 units of the same product on promotion. Candidates for manual review, not automatic culprits: a statistical anomaly is an alert, not a verdict.

This detector is the third in a series the course has been building, and it pays to see them as complementary:

In a real MercaFresh system all three would coexist: the z-score as a cheap first per-variable filter, DBSCAN hunting down unprecedented combinations, and the Bayesian signals scoring the documented fraud patterns. (Project 09-04 builds a complete fraud detector; here we stick to DBSCAN's role.)

With the module's three clustering algorithms on the table, the decision matrix:

The choice is not a contest: at MercaFresh we just used K-means/hierarchical to segment customers (compact, interpretable groups) and DBSCAN to watch over orders (free shapes and noise). Each question picked its own algorithm.

• Varying densities. The Achilles heel: a single global eps cannot serve a very dense cluster and a diffuse one at the same time — the eps that preserves the second merges the first with its neighbors, and the eps of the first disintegrates the second into noise. (There are variants such as HDBSCAN that build a hierarchy of densities; they fall outside this course, but the name is worth knowing.)
• Delicate choice of eps. The k-distance helps, but a few tenths up or down change the number of clusters and the % of noise. Always analyze sensitivity by trying 2-3 values around the elbow.
• High dimensionality. DBSCAN is as much a victim of the curse (05-03) as any distance-based method: with many dimensions, densities dilute and "near" loses meaning. PCA before DBSCAN is a common combination.
• Ambiguous border points. A border reachable from two clusters is assigned to whichever visits it first: small variations in ordering can move boundary points (noise and cores, in contrast, are stable).
• No centroids. There is no per-cluster "average order" to profile directly; to interpret a DBSCAN cluster you compute descriptive statistics (02-01) of its members.

• Running DBSCAN without scaling. eps is a distance: with features in mismatched units, the radius only "sees" the big variable. StandardScaler first, as throughout the module.
• Treating −1 as just another cluster. When profiling results or computing silhouettes, the noise is not a group: filter it out (labels != -1) before describing clusters, and report it separately as a noise %.
• Tuning eps until the noise disappears. If your goal is to detect anomalies, the noise is the result! Some 1-5% of noise is usually reasonable; 0% means you grew eps until it swallowed the anomalies; 40% means you shrank it until it disintegrated the clusters.
• Copying the eps from another dataset. eps depends on the scale, dimensionality and density of your data: recompute the k-distance for every problem, even between versions of the same dataset.
• Tip: always report three numbers alongside the clustering — number of clusters, noise % and the size of the largest cluster. They are the instant diagnostic of a badly chosen eps (1 giant cluster = eps too big; massive noise = eps too small).

Exercise 1. By hand, with eps=2 and min_samples=3, classify as core, border or noise the 1D points: [1, 2, 3, 10, 11, 30]. (Distance = absolute value of the difference; remember that a point counts as its own neighbor.) How many clusters result, and which points end up as noise?

Exercise 2. Generate make_moons(n_samples=500, noise=0.1, random_state=0), scale, and run DBSCAN with min_samples=5 and three eps values: 0.1, 0.3 and 1.0. For each one, print the number of clusters (excluding −1) and the noise %, and plot the three results. Relate what you see to the elbow of the k-distance.

Exercise 3. Simulate 300 normal MercaFresh orders (order_amount ~ N(45, 15), num_items ~ N(18, 6)) and add 5 anomalous orders (amount 400-600 with 2-4 items). Scale, choose eps via the k-distance and check whether DBSCAN flags the 5 as noise. Compare with a univariate z-score (02-02) on order_amount: would it have caught them too? What if the anomalous amount were €60 with 2 items?

Exercise 1

Neighborhoods of radius 2 (counting the point itself): 1 has {1,2,3} → 3 neighbors → core; 2 has {1,2,3} → core; 3 has {1,2,3} → core (10 sits at distance 7). 10 has {10,11} → 2 < 3 → not a core; a border? It is not within ≤2 of any core → noise; 11, likewise → noise; 30 stands alone → noise. Result: 1 cluster {1,2,3} and three noise points {10,11,30}. Note the subtlety: 10 and 11 sit together, but two points are not enough to found a cluster with min_samples=3 — density demands critical mass, not just closeness. With min_samples=2 they would have formed a second cluster.

Exercise 2

Expected pattern: eps=0.1 fragments the moons into many mini-clusters with lots of noise (the radius is smaller than the typical distance between neighbors); eps=0.3 gives 2 clusters with little noise — it sits close to the k-distance elbow, which for these data hovers around 0.2-0.3; eps=1.0 fuses everything into 1 cluster with no noise (the radius jumps the gap between moons). The sequence fragmentation → correct structure → collapse is eps's canonical behavior.

Exercise 3

The 5 anomalies show up as −1 (amounts more than 20 deviations away from the bulk: utterly isolated in the scaled space); some extreme normal order may fall into the noise too — check the overall %. The z-score on order_amount would also catch them (z ≈ +25). The difference emerges with the final case: €60 with 2 items has modest individual z-scores (z ≈ 1 on amount, z ≈ −2.7 on items, neither scandalous), but the combination "normal amount with only 2 items" (two €30 items? atypical in a supermarket) lives in a sparsely populated region of the plane, and DBSCAN can flag it. That is exactly the multivariate advantage over the univariate z-score that the lesson's table announced.

DBSCAN completes your trio of clustering algorithms with a new definition: cluster = dense zone, noise = whatever is left outside. You know how to classify points into core, border and noise, choose min_samples by rule of thumb and eps with the k-distance plot, you have seen in the make_moons half-moons why K-means' geometry has limits no tuning can fix, and you have put DBSCAN to work at what it does best for MercaFresh: flagging orders that fit no pattern, complementing the univariate z-score of 02-02 and the Bayesian approach of 02-05. The comparison table of the three algorithms is, alongside the table of the seven supervised ones from 04-07, your second navigation chart for the course.

One piece remains to close the module. We have segmented, built hierarchies, compressed and detected — but to communicate all of this, one image is worth a thousand centroid tables, and PCA's 2D map (05-03) was honest but linear and sometimes blurry. The module's final lesson presents the two modern visualization techniques that unfold nonlinear structure into two dimensions: t-SNE and UMAP, with their powers and their interpretation traps.