Sandeep Bazar 365 Days of AI
Labs

Machine Learning › Unsupervised Learning › Day 184

Hands-on lab — Day 184: Hierarchical Clustering and DBSCAN

Commands

Setup

pip install -r requirements/requirements.txt

Run

python3 examples/hierarchical_clustering_and_dbscan_lib.py

Test

./tests/run_tests.sh

File tree

examples/hierarchical_clustering_and_dbscan_lib.py
examples/test_hierarchical_clustering_and_dbscan_lib.py
expected-output/examples-run.txt
expected-output/FIELDS.md
expected-output/measured-values.txt
expected-output/starter-run.txt
expected-output/test-run.txt
metadata.yml
README.md
requirements/requirements.txt
security.md
starter/hierarchical_clustering_and_dbscan_lib.py
starter/test_hierarchical_clustering_and_dbscan_lib.py
tests/run_tests.sh
tests/test_hierarchical_clustering_and_dbscan_lib.py
troubleshooting.md

Lab README

Lab: Day 184 -- Hierarchical Clustering and DBSCAN

Lesson

Day number: 184 of 365. Course: Course04-SS03 (Beyond Supervised Learning). Topic: Hierarchical Clustering and DBSCAN.

Purpose

Build a complete, pure NumPy implementation of the DBSCAN density clustering algorithm from scratch. You will implement epsilon-neighborhood range queries, core point identification, breadth-first density cluster expansion, and noise classification.

Learning objectives

  • Implement epsilon-radius Euclidean neighborhood queries.
  • Identify core, border, and noise observations.
  • Expand density clusters using iterative queue traversal.
  • Benchmark clustering performance on non-spherical datasets with noise.

Prerequisites

  • Linear algebra: Pairwise Euclidean distance matrices.
  • Data structures: Queue-based breadth-first traversal.
  • Python 3.11+ with NumPy.

Supported operating systems

  • macOS (Apple Silicon / Intel)
  • Linux (Ubuntu, Debian, Fedora, Arch)
  • Windows 11 / WSL2

Hardware requirements

  • 1+ CPU cores.
  • 512 MB RAM.
  • 50 MB disk space.

Required software

  • Python 3.11 or newer.
  • pip package manager.
  • virtualenv or venv module.

Free and open-source options

All tools used in this lab (Python, NumPy, pytest, scikit-learn) are free and open-source under BSD/MIT licenses.

Installation

python3 -m venv .venv
source .venv/bin/activate
pip install -r requirements/requirements.txt

File structure

  • starter/hierarchical_clustering_and_dbscan_lib.py: Student scaffold file.
  • examples/hierarchical_clustering_and_dbscan_lib.py: Complete reference implementation.
  • tests/test_hierarchical_clustering_and_dbscan_lib.py: Pytest automated validation suite.
  • expected-output/: Verified output logs and baseline values.

How to run

Execute the reference demonstration script:

python3 examples/hierarchical_clustering_and_dbscan_lib.py

What the commands do

  • Generates two Gaussian clusters with 100 points plus 3 isolated outlier noise points.
  • Runs DBSCANFromScratch with epsilon=0.8 and MinPts=5.
  • Logs the number of discovered clusters and verified noise points.

Expected output

DBSCAN Demo: Discovered 2 clusters with 3 noise points.

Validation steps

  1. Verify that all points in core neighborhoods are assigned to matching cluster IDs.
  2. Verify that isolated outliers receive label -1.
  3. Ensure all unit test assertions pass.

Tests

Run the test runner script:

./tests/run_tests.sh

Cleanup

find . -type d -name "__pycache__" -exec rm -rf {} +
find . -type d -name ".pytest_cache" -exec rm -rf {} +

Troubleshooting

  • All Points Noise: Epsilon radius is too small. Check scale of features.
  • Single Giant Cluster: Epsilon radius is too large, causing clusters to merge across noise.

Security notes

All computations run strictly on local CPU memory without network transmission.

Extension exercises

  1. Implement KD-Tree spatial indexing to optimize neighborhood range queries from O(N^2) to O(N log N).
  2. Implement Ward hierarchical clustering dendrogram tree building.

Expected output

FIELDS.md

# Expected Output Fields: Day 184

- `Discovered Clusters`: Integer count of non-noise clusters.
- `Noise Points`: Integer count of points assigned label -1.
- `Labels`: Array of cluster indices of shape (N,).

examples-run.txt

DBSCAN Demo: Discovered 2 clusters with 3 noise points.

measured-values.txt

Discovered Clusters: 2
Noise Points: 3
Total Samples: 103

starter-run.txt

Starter scaffold executed. Ready for student implementation.

test-run.txt

============================= test session starts ==============================
collected 2 items

tests/test_hierarchical_clustering_and_dbscan_lib.py::test_dbscan_cluster_discovery PASSED [ 50%]
tests/test_hierarchical_clustering_and_dbscan_lib.py::test_dbscan_noise_filtering PASSED [100%]

============================== 2 passed in 0.08s ===============================

Source files

examples/hierarchical_clustering_and_dbscan_lib.py (1889 bytes) 
import numpy as np

class DBSCANFromScratch:
    def __init__(self, eps=0.5, min_samples=5):
        self.eps = eps
        self.min_samples = min_samples
        self.labels_ = None

    def fit(self, X):
        n_samples = len(X)
        self.labels_ = np.full(n_samples, -1)
        cluster_id = 0

        dists = np.linalg.norm(X[:, np.newaxis, :] - X[np.newaxis, :, :], axis=2)

        for i in range(n_samples):
            if self.labels_[i] != -1:
                continue

            neighbors = np.where(dists[i] <= self.eps)[0]
            if len(neighbors) < self.min_samples:
                continue

            self.labels_[i] = cluster_id
            queue = list(neighbors[neighbors != i])

            while queue:
                current_point = queue.pop(0)
                if self.labels_[current_point] == -1:
                    self.labels_[current_point] = cluster_id

                curr_neighbors = np.where(dists[current_point] <= self.eps)[0]
                if len(curr_neighbors) >= self.min_samples:
                    for n in curr_neighbors:
                        if self.labels_[n] == -1:
                            self.labels_[n] = cluster_id
                            queue.append(n)

            cluster_id += 1

        return self

def run_dbscan_demo():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-3.0, 0.0], scale=0.3, size=(50, 2))
    c2 = np.random.normal(loc=[3.0, 0.0], scale=0.3, size=(50, 2))
    noise = np.array([[10.0, 10.0], [-10.0, 10.0], [0.0, -10.0]])
    X = np.vstack([c1, c2, noise])

    db = DBSCANFromScratch(eps=0.8, min_samples=5).fit(X)
    n_clusters = len(set(db.labels_) - {-1})
    n_noise = int(np.sum(db.labels_ == -1))
    print(f"DBSCAN Demo: Discovered {n_clusters} clusters with {n_noise} noise points.")
    return db, n_clusters, n_noise

if __name__ == "__main__":
    run_dbscan_demo()
examples/test_hierarchical_clustering_and_dbscan_lib.py (879 bytes) 
import pytest
import numpy as np
from examples.hierarchical_clustering_and_dbscan_lib import DBSCANFromScratch

def test_dbscan_cluster_discovery():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-4.0, 0.0], scale=0.2, size=(40, 2))
    c2 = np.random.normal(loc=[4.0, 0.0], scale=0.2, size=(40, 2))
    X = np.vstack([c1, c2])

    db = DBSCANFromScratch(eps=0.8, min_samples=4).fit(X)
    unique_labels = set(db.labels_) - {-1}
    assert len(unique_labels) == 2
    assert db.labels_[0] != db.labels_[45]

def test_dbscan_noise_filtering():
    np.random.seed(42)
    c1 = np.random.normal(loc=[0.0, 0.0], scale=0.2, size=(30, 2))
    noise = np.array([[15.0, 15.0], [-15.0, -15.0]])
    X = np.vstack([c1, noise])

    db = DBSCANFromScratch(eps=0.8, min_samples=4).fit(X)
    assert db.labels_[-1] == -1
    assert db.labels_[-2] == -1
    assert db.labels_[0] != -1
metadata.yml (447 bytes) 
lesson_id: D184
day: 184
kind: lab
languages:
  - python
setup_commands:
  - 'pip install -r requirements/requirements.txt'
run_commands:
  - 'python3 examples/hierarchical_clustering_and_dbscan_lib.py'
test_commands:
  - './tests/run_tests.sh'
cleanup_commands:
  - 'find . -type d -name "__pycache__" -exec rm -rf {} +'
requires_network: false
requires_api_key: false
estimated_minutes: 45
last_executed: '2026-08-29'
executed_on: 'macos-arm64'
requirements/requirements.txt (62 bytes) 
numpy>=1.26.0
scikit-learn>=1.4.0
pytest>=8.0.0
scipy>=1.12.0
starter/hierarchical_clustering_and_dbscan_lib.py (295 bytes) 
import numpy as np

class DBSCANFromScratch:
    def __init__(self, eps=0.5, min_samples=5):
        self.eps = eps
        self.min_samples = min_samples
        self.labels_ = None

    def fit(self, X):
        # TODO: Implement DBSCAN density reachability and cluster expansion
        pass
starter/test_hierarchical_clustering_and_dbscan_lib.py (879 bytes) 
import pytest
import numpy as np
from examples.hierarchical_clustering_and_dbscan_lib import DBSCANFromScratch

def test_dbscan_cluster_discovery():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-4.0, 0.0], scale=0.2, size=(40, 2))
    c2 = np.random.normal(loc=[4.0, 0.0], scale=0.2, size=(40, 2))
    X = np.vstack([c1, c2])

    db = DBSCANFromScratch(eps=0.8, min_samples=4).fit(X)
    unique_labels = set(db.labels_) - {-1}
    assert len(unique_labels) == 2
    assert db.labels_[0] != db.labels_[45]

def test_dbscan_noise_filtering():
    np.random.seed(42)
    c1 = np.random.normal(loc=[0.0, 0.0], scale=0.2, size=(30, 2))
    noise = np.array([[15.0, 15.0], [-15.0, -15.0]])
    X = np.vstack([c1, noise])

    db = DBSCANFromScratch(eps=0.8, min_samples=4).fit(X)
    assert db.labels_[-1] == -1
    assert db.labels_[-2] == -1
    assert db.labels_[0] != -1
tests/run_tests.sh (227 bytes) 
#!/usr/bin/env bash
set -euo pipefail
echo "========================================"
echo "Running Day 184 Lab Test Suite"
echo "========================================"
pytest tests/ -v
echo "All tests passed successfully."
tests/test_hierarchical_clustering_and_dbscan_lib.py (879 bytes) 
import pytest
import numpy as np
from examples.hierarchical_clustering_and_dbscan_lib import DBSCANFromScratch

def test_dbscan_cluster_discovery():
    np.random.seed(42)
    c1 = np.random.normal(loc=[-4.0, 0.0], scale=0.2, size=(40, 2))
    c2 = np.random.normal(loc=[4.0, 0.0], scale=0.2, size=(40, 2))
    X = np.vstack([c1, c2])

    db = DBSCANFromScratch(eps=0.8, min_samples=4).fit(X)
    unique_labels = set(db.labels_) - {-1}
    assert len(unique_labels) == 2
    assert db.labels_[0] != db.labels_[45]

def test_dbscan_noise_filtering():
    np.random.seed(42)
    c1 = np.random.normal(loc=[0.0, 0.0], scale=0.2, size=(30, 2))
    noise = np.array([[15.0, 15.0], [-15.0, -15.0]])
    X = np.vstack([c1, noise])

    db = DBSCANFromScratch(eps=0.8, min_samples=4).fit(X)
    assert db.labels_[-1] == -1
    assert db.labels_[-2] == -1
    assert db.labels_[0] != -1

Troubleshooting

Troubleshooting: Day 184 - Hierarchical Clustering and DBSCAN

Common Issues

  1. Queue Infinite Loop:
    • Ensure points already added to cluster labels are not re-enqueued redundantly.

Security notes

Security & Privacy: Day 184 - Hierarchical Clustering and DBSCAN

Security Guidance

  • All clustering calculations execute locally without network transmission.