Spatial Clusters: finding hotspots with DBSCAN, and why k-means can't

The data in this project is synthetic — incident coordinates generated locally by data/make_data.py, no real 311 or crime feed. That is deliberate: grading needs each point’s known true label (which hotspot, or noise), which real incident data doesn’t come labelled with — and it keeps the project download-free and PII-free. No signup, no GPU.

Before you start

New to clustering? Start here.

Clustering means grouping points that are close together, without being told the groups in advance. The famous method, k-means, has two habits that hurt here:

You must tell it k, the number of clusters, up front.
It assigns every point to a cluster and its clusters are round — there’s no “this point belongs to nothing,” and an elongated or oddly-shaped group gets forced into circles.

Real spatial data breaks both. Incidents pile up in a few hotspots of different shapes and densities, surrounded by scattered one-off points that belong to no hotspot at all. DBSCAN (Density-Based Spatial Clustering of Applications with Noise) fits this exactly. It grows a cluster outward through regions where points are densely packed and stops at the edges, so:

it discovers how many clusters there are (you don’t set k),
it follows any shape a dense region takes, and
it labels sparse points as noise (-1) instead of forcing them in.

It has two knobs: eps (how close counts as “neighbouring”) and min_samples (how many neighbours make a point part of a dense core). Part A builds both methods and shows k-means fail; Part B is a new week of data where you tune DBSCAN yourself. What you’ll learn is in Section 3.

New to Python too? See Start Here — it starts from zero, and shows how to run this in your browser with nothing to install.

1. The Brief

You have a week of a county’s 311 service requests as map coordinates. Most requests cluster into a few hotspots — a stadium on game night, a flooded underpass, a construction zone — but a third of them are scattered one-off complaints that belong to no hotspot. Part A: cluster them with k-means and watch it sweep every scattered complaint into a hotspot (it has no “none of the above”), then with DBSCAN, which recovers the hotspots and sets the scatter aside as noise. Part B: a fresh week, and you choose DBSCAN’s eps from the k-distance curve to recover the hotspot-vs-noise labelling yourself.

Density clustering is how hotspot maps get made — crime and disease surveillance, outage and defect clustering, GPS stop detection, store-visit footprints. The recurring mistake is reaching for k-means because it’s familiar, then quietly mislabelling the background as signal.

2. Difficulty & time

Difficulty 5 / 10. One library call each, but the judgment is real: recognise that the background is noise (not a cluster), choose eps and min_samples from the k-distance curve rather than guessing, and know why k-means is the wrong tool here. Calibrated against the ledger (G10): a peer of hidden-communities (5, finding groups without being told how many), geohash-rollup (5), and bullwhip-effect (5). Above nearest-facility (4), a single distance formula; below warehouse-sim (6), which adds a whole simulation paradigm.

Time is separate from difficulty: Part A is about an hour; Part B is 2–3 hours. The scripts run in a second or two.

3. What you’ll be able to do after

Cluster spatial points with DBSCAN — recover dense hotspots and label sparse background as noise, without setting the number of clusters in advance.
Choose eps from the k-distance curve instead of guessing — read the knee between the dense and sparse regimes.
Explain why k-means fails here — it forces every point into one of k round clusters and has no noise label, so it mislabels the scattered background.
Score a clustering objectively with the Adjusted Rand Index against known labels, understanding why a label-invariant metric is needed.

The finished result

By the end of Part A you’ll have clustered one week of 620 incidents two ways and seen why density clustering — not k-means — is the right tool for hotspots:

k-means (k=4):    all 620 points forced into a cluster, 0 labelled noise  ->  sizes [168, 168, 164, 120]
DBSCAN(eps=3.0):  4 hotspots discovered, 195 points (31%) labelled noise  ->  sizes [132, 115, 99, 79]
choosing eps:     8th-nearest-neighbour distance ~1.6 km inside hotspots, ~6.1 km out in the scatter

k-means has no “none of the above,” so it sweeps every scattered complaint into a hotspot; DBSCAN recovers the four dense hotspots and sets the background aside as noise. In Part B that same method, with eps re-derived for a denser week, reaches 0.94 ARI — where blindly reusing this eps scores only 0.50.

4. Prereqs & time box

You can write a function, use numpy arrays and a pandas DataFrame, and call a scikit-learn estimator (.fit_predict). No clustering background needed — the orientation above covers DBSCAN’s two knobs, and Part A builds the k-distance method step by step.

Where to write and run code

Two ways to run this project — pick either:

In your browser (no install). If the project page shows a ▶ Run button, click it to run Part A right here — nothing to set up. Part A uses pandas, numpy, and scikit-learn, which run in the browser.
On your computer. The one-time setup — installing Python, downloading the code from the course site (no GitHub, no git), opening a terminal, creating a virtual environment, installing the requirements, and running Part A step by step — is covered once in Start Here. Come back here once python -c "import sklearn" runs without error. Part B (writing your own solution) needs this local setup.

Time box

Part A — Guided Build: 60–90 minutes. Hard cap.
Part B — Your Turn: 2–4 hours. Hard cap.

5. Setup & data

The data is synthetic and generated locally — see the banner above and SOURCES.md for full provenance. One command creates both parts’ data:

python data/make_data.py

That writes two CSVs into data/ (git-ignored; regenerate anytime, byte-for-byte identical because the seeds are fixed):

Part A — incidents_a.csv (620 rows: point_id, x_km, y_km) — a spread-out suburban county on a ~100 km grid.
Part B — incidents_b.csv (620 rows, same columns) — a dense downtown on a ~40 km grid.

Both are projected planar km, each with four hotspots (one elongated) and ~34% scattered background. The scale differs on purpose: an eps tuned for the suburban grid is far too big downtown, so Part B makes you re-derive it. The true label of each point is known from the seed and used only for grading — it is not in the CSV.

6. Part A — Guided Build

You’ll cluster one week of incidents with k-means and DBSCAN and learn to pick eps. Run the whole thing, or (better) one # %% cell at a time — see Start Here:

python part_a/cluster.py

Prefer the browser? If this page has a ▶ Run button, click it instead of the command above — Part A runs in your browser with nothing to install. The STEP output and every checkpoint below are identical either way.

The full, commented script is in part_a/cluster.py. The spine:

Step 1 — The incidents.

Checkpoint: 620 points over a ~100 km grid — a few dense blobs inside a haze of scattered complaints. You are not told how many blobs.

Step 2 — k-means (k=4): every point must join a cluster.

Checkpoint: k-means assigns all 620 points (0 unclustered) — it has no noise label, so every scattered complaint is swept into the nearest hotspot, inflating cluster sizes to [168, 168, 164, 120] versus true cores of ~75–130. And you had to tell it k=4.

Step 3 — DBSCAN(eps=3.0, min_samples=8): density finds the hotspots.

Checkpoint: DBSCAN discovers 4 clusters (you never passed k) and labels 195 points (31%) as noise; cluster sizes [132, 115, 99, 79] track the true cores. That noise label is exactly what k-means cannot produce.

Step 4 — Choosing eps: the k-distance elbow.

Checkpoint: the sorted 8th-nearest-neighbour distance stays low (~1.6 km at the median — points inside dense hotspots) then jumps past the ~65th percentile (2.6 km → 6.1 km by the 70th — the scattered points). eps=3.0 sits in that gap. Writes part_a/clusters_a.csv.

Why this and not that

Why DBSCAN, not k-means. The background isn’t a cluster — it’s noise. k-means has no way to say that, so it mislabels a third of the data. DBSCAN’s whole premise is “dense = cluster, sparse = noise,” which is the actual structure here.
Why you don’t set k. You genuinely don’t know how many hotspots a new week has. DBSCAN reads it off the density; passing a wrong k to k-means silently returns a wrong partition.
Why the k-distance curve. eps isn’t a guess — the knee in the sorted k-distance plot separates “typical spacing inside a cluster” from “typical spacing out in the scatter,” and eps belongs in between.

Functions you’ll meet (and where to read more)

Function	What it does here	Docs
`KMeans(...).fit_predict`	The baseline that forces k round clusters	KMeans
`DBSCAN(eps, min_samples).fit_predict`	Density clustering with a noise label (-1)	DBSCAN
`NearestNeighbors(...).kneighbors`	k-distance curve for choosing eps	NearestNeighbors
`adjusted_rand_score`	Score a clustering against known labels	adjusted_rand_score

If something looks off

DBSCAN gave a lot of points the label -1 — did something break? No. -1 is DBSCAN’s noise label, not an error code: it marks the scattered one-off complaints that belong to no hotspot. Seeing it is the whole point — k-means cannot produce it, so it buries those points inside clusters instead. In Part A about 195 points (31%) come back as -1, and that is the correct result. (If no point is -1, you’ve slipped back to k-means-style “assign everything”; if most points are -1, your eps is too small for the hotspots to form.)
A checkpoint number doesn’t match. The data is seeded, so the numbers are exact. Re-run python data/make_data.py (you may have skipped or edited it), then re-run Part A.
Setup problems (Python not found, pip, FileNotFoundError, re-activating the venv): see the troubleshooting list in Start Here.

7. Part B — Your Turn

Part B is the optional “your turn” half — a guided fill-in-the-blank, not a blank page. You get a working starter (part_b/starter.py) that already handles the easy version; your job is to finish the # TODO it marks out. More open than Part A’s step-by-step, but you are never staring at an empty file. If you finished Part A and want to prove the skill, this is where it happens. New to Python? It’s completely fine to stop after Part A and come back later.

Same core skill — density clustering — on a denser downtown (incidents_b.csv, a ~40 km grid). Label every point as a hotspot (0, 1, 2, …) or noise (-1), recovering the dense hotspots and leaving the scattered one-off complaints as noise. The starter reuses Part A’s eps=3.0 — far too big at this scale, so it chains the background into the hotspots and scores 0.50 ARI, so it fails. (k-means with k=4 fares no better, 0.46 — no noise label.) Re-derive eps from this week’s own k-distance curve.

The transfer: Part A handed you a working eps=3.0 for a spread-out suburb; here the metro is denser, so that value no longer fits and the number you can copy is the wrong one. You have to read Part B’s k-distance curve and pick a new eps (it lands near ~1 km). Same DBSCAN skill, different data scale, and a tuning decision that Part A’s answer can’t shortcut.

How you’re scored (reproduce the yardstick)

The grader compares your labels to the truth with the Adjusted Rand Index (adjusted_rand_score). ARI is label-invariant — it doesn’t matter whether you call the stadium cluster 0 or 3 — and it treats noise (-1) as its own group, so mislabelling background as a hotspot costs you. The reference (DBSCAN with eps re-derived for this week) reaches ~0.94; the floor is 0.85.

Acceptance criteria (checkable)

Your solution writes into part_b/out/:

labels.csv — columns point_id, label (every point, one row; label is a hotspot id ≥ 0 or -1 for noise).
report.json — with keys points, achieved_metric (you can leave achieved_metric null; the grader scores you).

Then:

python part_b/starter.py
pytest part_b/test_solution.py -q

If pytest reports everything as skipped, it just means the output files don’t exist yet — run python part_b/starter.py first (once your solution fills in the TODOs), then re-run.

You’re done when the tests pass (ARI ≥ 0.85; the reference reaches ~0.94).

Constraints — what must be true of your solution, not how to get there

Scattered background points must be labelled noise (-1), not folded into a hotspot.
Don’t hard-code the number of clusters — let the method discover it.
Choose eps from the data (the k-distance curve), not by trying numbers until the test passes.
Use the map coordinates as given; no need to rescale (they’re already in km).

Hints

Hint 1 — why the starter (and k-means) can't clear the floor

The starter reuses eps=3.0 from Part A, but downtown is denser: 3 km now spans the gaps between hotspots and out into the scatter, so DBSCAN chains everything together. And k-means has no noise label, so ~34% of the points (the background) are forced into hotspots and counted wrong. The fix for the first is a smaller, re-derived eps; the fix for the second is using DBSCAN at all.

Hint 2 — set eps from the curve

Sort every point’s distance to its min_samples-th nearest neighbour and look for the knee (Part A, Step 4). Points inside hotspots have a small such distance; scattered points have a large one. Put eps in the gap between the two regimes.

Hint 3 — min_samples

min_samples is how many neighbours within eps make a point a dense “core.” Larger values demand denser cores and push more borderline points into noise. Something around 5–10 works here; tune it alongside eps and watch the noise fraction and cluster count.

8. Self-check

You don’t need the answer key. You’re done when all of these hold:

pytest passes — ARI ≥ 0.85 against the true labels.
Your result has four hotspots and roughly a third of points labelled noise — not zero noise (that’s the k-means failure), not one giant blob (eps too big, the eps=3.0 reuse trap), and not everything-is-noise (eps too small).
Re-running from python data/make_data.py reproduces the same numbers — the data is seeded.

And the tell-tale: if no points are labelled -1, you’re still doing k-means-style “assign everything.” If most points are -1, your eps is too small or min_samples too large — the dense hotspots aren’t forming cores.

9. Stretch

Varying density. Add a fifth hotspot that’s genuinely sparser than the others and watch a single global eps struggle to catch it without also chaining the noise — the classic DBSCAN limitation. Read up on HDBSCAN, which handles variable density, and compare.
3-D or time. Add the hour-of-week as a third coordinate (scaled) and cluster in space-time, so a game-night spike and a daytime construction spike separate even at the same place.
(Genuinely hard) Label your own city. Pull a truly open, licence-clear incident feed (many city open-data portals publish 311 or crime extracts under an open licence — check the licence), project the coordinates, and find its hotspots. Note in your writeup that without ground-truth labels you can no longer compute ARI, so you must judge the clustering by stability and eyeballing.

10. Ship it

Put this in a portfolio repo and it counts. In that repo’s README:

State the finding in one sentence: “DBSCAN recovered four service-request hotspots and set ~34% of reports aside as noise (ARI 0.94 vs known labels); k-means scored 0.46, and blindly reusing a coarser week’s eps scored 0.50 — the scale has to be re-tuned.”
Show a scatter coloured by DBSCAN label (noise in grey) next to the k-means version — the difference is the whole story.
Include the k-distance plot and one paragraph on choosing eps. That paragraph is what signals you understand density clustering, not just .fit_predict.

Keep make_data.py and the tests in the repo so anyone can reproduce your numbers from zero.

11. Sources

Rendered from SOURCES.md.

Field	Value
Dataset	Synthetic incident points, 4 hotspots + ~34% background noise: Part A 620 on a ~100 km suburban grid, Part B 620 on a denser ~40 km downtown grid
Type	Synthetic
Generated by	`data/make_data.py` (this repo), seeds `20260752` (A) and `20260751` (B)
Source URL	Not applicable — generated, not fetched
License	Not applicable — synthetic, no third-party rights
Access / generation date	2026-07-18
Redistribution	Permitted — synthetic; output regenerated from the seeded script, never committed
robots.txt checked	Not applicable — no scraping
ToS URL	Not applicable — no external source

Synthetic data teaches the mechanic; it does not prove a finding about the real world. The hotspots and noise were generated on purpose — the density-clustering technique is the point, not a claim about any real county.

Next up

Finished this one? Continue the Geospatial track:

Spatial Autocorrelation: is the map clustered, and where — Moran’s I, global and local → · Browse all courses