{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "dbscan.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# density-based spatial clustering of applications with noise (DBSCAN) \u2014 Python demo\n\nNumerical companion to the entry [density-based spatial clustering of applications with noise (DBSCAN)](https://dictionaryofml.org/terms/dbscan.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nNumerical companion to the glossary entry 'dbscan'. The aerial photograph assets/wachau_ortho.jpg (Weissenkirchen, Rossatz, Duernstein and the Loiben slopes along the Danube bend; 7.31 x 3.65 km; orthophoto (c) basemap.at, CC BY 4.0) is cut into square patches of 76 m, and the parcel mask assets/wachau_labels.png (INVEKOS Schlaege 2025-1, AgrarMarkt Austria, CC BY 3.0 AT) selects the patches that lie mostly on vineyard parcels. These are the data points, each with its position (easting, northing) in km as feature vector, and the wine-growing areas of the strip are the clusters to be found.\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/dbscan.py`](https://dictionaryofml.org/terms/dbscan.py); CC BY 4.0.\n\nBefore running a downloaded copy, scan it: `uvx bandit -q -t B102,B307,B602,B605 dbscan.py` (B102,B307,B602,B605 are the exec, eval and shell checks of [bandit](https://bandit.readthedocs.io/)) reports nothing: the script runs no shell command and evaluates no generated code."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# Notebook shim: the script resolves output paths relative to __file__,\n# which a notebook kernel does not define; everything lands in the\n# working directory instead.\nimport os\n__file__ = os.path.join(os.getcwd(), \"dbscan.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"DBSCAN on the vineyard patches of an aerial photograph of the Wachau:\ncore points, noise, the effect of eps, and the comparison with k-means.\n\nPurpose\n-------\nNumerical companion to the glossary entry 'dbscan'.  The aerial\nphotograph assets/wachau_ortho.jpg (Weissenkirchen, Rossatz, Duernstein\nand the Loiben slopes along the Danube bend; 7.31 x 3.65 km; orthophoto\n(c) basemap.at, CC BY 4.0) is cut into square patches of 76 m, and the\nparcel mask assets/wachau_labels.png (INVEKOS Schlaege 2025-1,\nAgrarMarkt Austria, CC BY 3.0 AT) selects the patches that lie mostly on\nvineyard parcels.  These are the data points, each with its position\n(easting, northing) in km as feature vector, and the wine-growing areas\nof the strip are the clusters to be found.\n\nThe demo checks the entry's claims: every DBSCAN cluster is a maximal\nset of patches connected through core points at most eps apart; every\nnoise patch has fewer than minPts patches within eps; DBSCAN is a\nsingle pass (a second run on its own output changes nothing); the\nnumber of clusters is an output that falls as eps grows, while the\nnoise share falls too; and k-means with the same number of clusters\nsplits at least one area and joins two areas in one cluster.\n\nDeterministic: DBSCAN has no random choices; k-means is initialized by\nsplitting the patches into equal parts ordered by easting.\nSelf-contained: numpy + matplotlib only.\n\nBlocks\n------\n[B-patches] Cut the photograph into 32x32-pixel patches (76 m), select\n            the patches that lie mostly on vineyard parcels, and take\n            their positions in km as feature vectors.\n[B-dbscan]  DBSCAN with eps = 1.5 patch spacings and minPts = 4: core\n            points, clusters as connected components of the\n            eps-neighborhood graph on the core points, border points,\n            noise.  Check the connectivity of every cluster, the noise\n            condition, and that the result is reached in one pass.\n[B-eps]     The same with eps = 1.1, 1.5 and 3.0 patch spacings: the\n            number of clusters and the noise share as eps grows.  Check\n            that both fall.\n[B-kmeans]  k-means with as many clusters as DBSCAN found areas of at\n            least 20 patches: check that it splits at least one area\n            and that one of its clusters joins two areas.\n[B-images]  The photograph at patch resolution with the vineyard patches\n            marked, and one painted copy per eps (noise in black).\n[B-plot]    Write the positions of the patches of each area, of the\n            small clusters and of the noise for the entry's scatter,\n            plus the preview.\n\nOutputs\n-------\ndbscan_points_area1.csv ... dbscan_points_area5.csv : x1, x2 -- the\n                       patches of the five wine-growing areas, ordered\n                       by size\ndbscan_points_small.csv : x1, x2 -- the patches of the clusters with\n                       fewer than 20 patches\ndbscan_points_noise.csv : x1, x2 -- the noise patches\ndbscan_wachau_vineyard.png : the photograph at patch resolution with\n                       the vineyard patches marked\ndbscan_wachau_eps1.png, _eps2.png, _eps3.png : the vineyard patches\n                       painted by cluster for eps = 1.1, 1.5, 3.0 patch\n                       spacings (noise in black)\ndbscan.png : preview (checking only) -- the scatter and the three\n             painted copies\n\"\"\"\n\n# /// script\n# requires-python = \">=3.10\"\n# dependencies = [\"matplotlib==3.10.7\", \"numpy==2.3.4\"]\n# ///\n\nfrom pathlib import Path\n\nimport urllib.request\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\nfrom matplotlib.image import imread\n\nOUT_DIR = Path(__file__).parent\n\nASSET_URL = \"https://dictionaryofml.org/demoassets/\"\n\n\ndef demo_asset(name):\n    \"\"\"Path to the input file `name`, fetched once if it is not already here.\n\n    Inside the repository the committed copy is used (pythondemos/ first,\n    then assets/), so a run there reproduces the committed outputs exactly.\n    Run from anywhere else -- from the copy published on dictionaryofml.org,\n    say -- the file is downloaded and cached beside the script, so the demo\n    is runnable without the repository.\n    \"\"\"\n    for cand in (OUT_DIR / name, OUT_DIR.parent / \"assets\" / name):\n        if cand.exists():\n            return cand\n    cached = OUT_DIR / name\n    print(f\"    fetching {name} from {ASSET_URL}{name}\")\n    with urllib.request.urlopen(ASSET_URL + name, timeout=180) as resp:\n        cached.write_bytes(resp.read())\n    return cached\n\nreport = []                         # collects (check name, pass/fail) pairs\n\n\ndef check(name, ok):                # records and prints one verification\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-patches]** Cut the photograph into 32x32-pixel patches (76 m), select the patches that lie mostly on vineyard parcels, and take their positions in km as feature vectors."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "PATCH = 32\nWIDTH_KM = 7.31                     # the strip is 7.31 km wide\nphoto = imread(demo_asset(\"wachau_ortho.jpg\")) / 255.0\nlabels = np.asarray(imread(demo_asset(\"wachau_labels.png\")))\nif labels.ndim == 3:\n    labels = labels[:, :, 0]\nif labels.max() <= 1.0 and labels.dtype != np.uint8:\n    labels = np.rint(labels * 255).astype(np.uint8)\nrows = photo.shape[0] // PATCH\ncols = photo.shape[1] // PATCH\ntiles = photo[:rows * PATCH, :cols * PATCH].reshape(\n    rows, PATCH, cols, PATCH, 3).mean(axis=(1, 3))\nshare = (labels[:rows * PATCH, :cols * PATCH] == 1).reshape(\n    rows, PATCH, cols, PATCH).mean(axis=(1, 3))\nspacing = PATCH * WIDTH_KM / photo.shape[1]           # km between patches\ngrid_r, grid_c = np.divmod(np.arange(rows * cols), cols)\npositions = np.column_stack([grid_c * spacing, (rows - 1 - grid_r) * spacing])\nis_vine = share.ravel() > 0.5\nX = positions[is_vine]                                # the data points\nvine_r, vine_c = grid_r[is_vine], grid_c[is_vine]\nprint(f\"  {len(X)} vineyard patches of {rows * cols}, spaced {1000 * spacing:.0f} m\")\ncheck(\"[B-patches] every vineyard patch has a two-number feature vector\",\n      X.shape == (is_vine.sum(), 2) and 900 < len(X) < 1100)\ndist = np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(axis=2))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-dbscan]** DBSCAN with eps = 1.5 patch spacings and minPts = 4: core points, clusters as connected components of the eps-neighborhood graph on the core points, border points, noise. Check the connectivity of every cluster, the noise condition, and that the result is reached in one pass."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "def dbscan(dist, eps, min_pts):\n    \"\"\"DBSCAN: labels (-1 = noise) and the core-point indicator.\"\"\"\n    within = dist <= eps\n    core = within.sum(axis=1) >= min_pts           # counting the point itself\n    lab = -np.ones(len(core), dtype=int)\n    current = 0\n    for seed in range(len(core)):\n        if lab[seed] != -1 or not core[seed]:\n            continue\n        lab[seed] = current\n        stack = [seed]\n        while stack:\n            u = stack.pop()\n            if not core[u]:\n                continue                        # border points do not expand\n            for v in np.flatnonzero(within[u]):\n                if lab[v] == -1:\n                    lab[v] = current\n                    stack.append(v)\n        current += 1\n    return lab, core\n\n\ndef components(mask, adjacency):\n    \"\"\"Number of connected components of the subgraph induced by mask.\"\"\"\n    seen = np.zeros(len(mask), dtype=bool)\n    count = 0\n    for s in np.flatnonzero(mask):\n        if seen[s]:\n            continue\n        count += 1\n        stack = [s]\n        seen[s] = True\n        while stack:\n            u = stack.pop()\n            for v in np.flatnonzero(adjacency[u] & mask & ~seen):\n                seen[v] = True\n                stack.append(v)\n    return count\n\n\nEPS = 1.5 * spacing\nMIN_PTS = 4\nlab, core = dbscan(dist, EPS, MIN_PTS)\nwithin = dist <= EPS\nn_clusters = lab.max() + 1\nsizes = np.bincount(lab[lab >= 0])\norder = np.argsort(-sizes)                          # largest cluster first\nlab = np.where(lab >= 0, np.argsort(order)[np.maximum(lab, 0)], -1)\nsizes = sizes[order]\nareas = [c for c in range(n_clusters) if sizes[c] >= 20]\nborder = (lab >= 0) & ~core\nprint(f\"  eps = 1.5 spacings, minPts = {MIN_PTS}: {int(core.sum())} core points, \"\n      f\"{int(border.sum())} border points, {int((lab < 0).sum())} noise; \"\n      f\"{n_clusters} clusters of sizes {sizes.tolist()}; {len(areas)} with \"\n      f\"at least 20 patches\")\ncheck(\"[B-dbscan] every cluster is connected through core points at most \"\n      \"eps apart\",\n      all(components((lab == c) & core, within) == 1 for c in range(n_clusters)))\ncheck(\"[B-dbscan] every border point lies within eps of a core point of its \"\n      \"cluster\",\n      all(bool(np.any(within[i] & core & (lab == lab[i])))\n          for i in np.flatnonzero(border)))\ncheck(\"[B-dbscan] every noise patch has fewer than minPts patches within eps\",\n      bool(np.all(within[lab < 0].sum(axis=1) < MIN_PTS)))\n# one pass: rerunning on the clustered patches only reproduces the clusters\nlab_again, _ = dbscan(dist[lab >= 0][:, lab >= 0], EPS, MIN_PTS)\nsame = all(len(np.unique(lab_again[lab[lab >= 0] == c])) == 1\n           and np.all(lab_again[lab[lab >= 0] == c] >= 0) for c in range(n_clusters))\ncheck(\"[B-dbscan] a second pass over the clustered patches changes nothing\",\n      same and lab_again.max() + 1 == n_clusters)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-eps]** The same with eps = 1.1, 1.5 and 3.0 patch spacings: the number of clusters and the noise share as eps grows. Check that both fall."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "EPS_FACTORS = (1.1, 1.5, 3.0)\nsweep = []\nfor f in EPS_FACTORS:\n    lab_f, core_f = dbscan(dist, f * spacing, MIN_PTS)\n    n_f = lab_f.max() + 1\n    big_f = int((np.bincount(lab_f[lab_f >= 0]) >= 20).sum()) if n_f else 0\n    sweep.append((lab_f, n_f, big_f, float((lab_f < 0).mean())))\n    print(f\"  eps = {f:.1f} spacings: {n_f} clusters ({big_f} with at least 20 \"\n          f\"patches), {100 * sweep[-1][3]:.0f}% noise\")\ncheck(\"[B-eps] the number of clusters falls as eps grows\",\n      sweep[0][1] > sweep[1][1] > sweep[2][1])\ncheck(\"[B-eps] the noise share falls as eps grows\",\n      sweep[0][3] > sweep[1][3] > sweep[2][3])\ncheck(\"[B-eps] the largest eps joins areas that eps = 1.5 keeps apart\",\n      sweep[2][2] < len(areas))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-kmeans]** k-means with as many clusters as DBSCAN found areas of at least 20 patches: check that it splits at least one area and that one of its clusters joins two areas."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "def assign(A, cents):\n    return ((A[:, None, :] - cents) ** 2).sum(axis=2).argmin(axis=1)\n\n\ndef lloyd(A, cents):\n    lab_k = assign(A, cents)\n    for _ in range(300):\n        new = np.stack([A[lab_k == c].mean(axis=0) if (lab_k == c).any()\n                        else cents[c] for c in range(len(cents))])\n        new_lab = assign(A, new)\n        if np.array_equal(new_lab, lab_k) and np.allclose(new, cents):\n            return new_lab\n        lab_k, cents = new_lab, new\n    return lab_k\n\n\nNRCLUSTER = len(areas)\nparts = np.array_split(np.argsort(X[:, 0]), NRCLUSTER)\nlab_km = lloyd(X, np.stack([X[g].mean(axis=0) for g in parts]))\nsplit = sum(int((np.bincount(lab_km[lab == a], minlength=NRCLUSTER) >= 20).sum() >= 2)\n            for a in areas)\njoin = sum(int(sum(int(((lab_km == c) & (lab == a)).sum()) >= 20 for a in areas) >= 2)\n           for c in range(NRCLUSTER))\nprint(f\"  k-means with k = {NRCLUSTER}: splits {split} area(s), {join} cluster(s) \"\n      f\"join two areas\")\ncheck(\"[B-kmeans] k-means splits at least one wine-growing area\", split >= 1)\ncheck(\"[B-kmeans] at least one k-means cluster joins two areas\", join >= 1)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-images]** The photograph at patch resolution with the vineyard patches marked, and one painted copy per eps (noise in black)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "def save_image(arr, name, zoom=3):\n    img = np.clip(arr, 0.0, 1.0).repeat(zoom, axis=0).repeat(zoom, axis=1)\n    plt.imsave(OUT_DIR / name, img)\n\n\nPALETTE = np.array([[0.95, 0.75, 0.10], [0.15, 0.35, 0.85], [0.05, 0.75, 0.85],\n                    [0.60, 0.10, 0.10], [0.15, 0.65, 0.25], [0.95, 0.55, 0.75],\n                    [0.55, 0.30, 0.05], [0.45, 0.45, 0.45], [0.65, 0.15, 0.75],\n                    [0.55, 0.85, 0.30]])   # ordered by distinct brightness\ndimmed = 0.35 * tiles + 0.35\nmarked = dimmed.copy()\nmarked[vine_r, vine_c] = tiles[vine_r, vine_c]\nsave_image(marked, \"dbscan_wachau_vineyard.png\")\n\n\ndef paint(lab_p, name):\n    img = dimmed.copy()\n    for i, (r, c) in enumerate(zip(vine_r, vine_c)):\n        img[r, c] = PALETTE[lab_p[i] % len(PALETTE)] if lab_p[i] >= 0 else 0.0\n    save_image(img, name)\n    return img\n\n\npainted = []\nfor i, (lab_f, _, _, _) in enumerate(sweep, start=1):\n    sizes_f = np.bincount(lab_f[lab_f >= 0])\n    relabel = np.argsort(np.argsort(-sizes_f))     # largest cluster first\n    lab_f = np.where(lab_f >= 0, relabel[np.maximum(lab_f, 0)], -1)\n    painted.append(paint(lab_f, f\"dbscan_wachau_eps{i}.png\"))\ncheck(\"[B-images] one painted copy per eps\",\n      all((OUT_DIR / f\"dbscan_wachau_eps{i}.png\").exists() for i in (1, 2, 3)))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-plot]** Write the positions of the patches of each area, of the small clusters and of the noise for the entry's scatter, plus the preview."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "def write_points(name, sel):\n    with open(OUT_DIR / name, \"w\") as f:\n        f.write(\"x1,x2\\n\")\n        for a, b in X[sel]:\n            f.write(f\"{a:.4f},{b:.4f}\\n\")\n\n\nfor i, a in enumerate(areas, start=1):\n    write_points(f\"dbscan_points_area{i}.csv\", lab == a)\nwrite_points(\"dbscan_points_small.csv\", (lab >= 0) & ~np.isin(lab, areas))\nwrite_points(\"dbscan_points_noise.csv\", lab < 0)\n\nfig, axes = plt.subplots(1, 4, figsize=(16, 3.4))\nax = axes[0]\nmarkers = (\"o\", \"s\", \"^\", \"D\", \"v\", \"p\", \"h\")\nfor i, a in enumerate(areas):\n    ax.plot(X[lab == a, 0], X[lab == a, 1], markers[i], color=\"0.35\",\n            markersize=2.4, linestyle=\"none\", label=f\"area {i + 1}\")\nax.plot(X[lab < 0, 0], X[lab < 0, 1], \"x\", color=\"black\", markersize=4,\n        linestyle=\"none\", label=\"noise\")\nax.set_aspect(\"equal\")\nax.set_xlabel(\"easting (km)\")\nax.set_ylabel(\"northing (km)\")\nax.set_title(\"DBSCAN clusters of the vineyard patches\")\nax.legend(frameon=False, fontsize=7, loc=\"lower right\", ncol=2)\nfor ax, img, f in zip(axes[1:], painted, EPS_FACTORS):\n    ax.imshow(np.clip(img, 0, 1))\n    ax.set_title(f\"eps = {f:.1f} patch spacings\")\n    ax.set_xlabel(\"patch column\")\n    ax.set_ylabel(\"patch row\")\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"dbscan.png\", dpi=150)\nplt.close(fig)\ncheck(\"[B-plot] the scatter files were written\",\n      (OUT_DIR / \"dbscan_points_noise.csv\").exists()\n      and (OUT_DIR / f\"dbscan_points_area{len(areas)}.csv\").exists())\n\npassed = sum(1 for _, ok in report if ok)\nprint(f\"\\n{passed}/{len(report)} checks pass\")"
  }
 ]
}