machine_learning.dbscan

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

A density-based clustering algorithm that groups together points that are closely packed together, while marking points in low-density regions as outliers.

Unlike K-Means, DBSCAN: - Does NOT require specifying the number of clusters in advance - Can find clusters of arbitrary shapes - Is robust to outliers (labels them as noise, cluster id = -1)

Key Parameters:

epsilon (eps): The maximum distance between two points to be considered neighbors min_points: Minimum number of points to form a dense region (core point)

Point Types:

  • Core point: Has at least min_points neighbors within epsilon distance

  • Border point: Within epsilon of a core point, but has fewer than

    min_points neighbors

  • Noise point: Neither core nor border — labeled as -1

Time Complexity: O(n²) with brute-force neighbor search Space Complexity: O(n)

References:

Functions

dbscan(→ list[int])

Perform DBSCAN clustering on a dataset.

euclidean_distance(→ float)

Compute the Euclidean distance between two points in n-dimensional space.

get_neighbors(→ list[int])

Return indices of all points within epsilon distance of data[point_index].

Module Contents

machine_learning.dbscan.dbscan(data: list[list[float]], epsilon: float, min_points: int) → list[int]

Perform DBSCAN clustering on a dataset.

Args:

data: List of n-dimensional data points, e.g. [[x1,y1], [x2,y2], …] epsilon: Maximum distance between two points to be considered neighbors.

Must be greater than 0.

min_points: Minimum number of neighbors (including self) to be a core point.

Must be at least 1.

Returns:

A list of integer cluster labels, one per input point. Noise points are labeled -1. Cluster IDs start from 0.

Raises:

ValueError: If data is empty. ValueError: If epsilon is not positive. ValueError: If min_points is less than 1.

Example — two well-separated clusters: >>> data = [ … [1.0, 1.0], [1.1, 1.0], [1.0, 1.1], … [9.0, 9.0], [9.1, 9.0], [9.0, 9.1], … ] >>> labels = dbscan(data, epsilon=0.5, min_points=2) >>> len(set(labels)) # two clusters 2 >>> labels[0] == labels[1] == labels[2] # first three in same cluster True >>> labels[3] == labels[4] == labels[5] # last three in same cluster True >>> labels[0] != labels[3] # different clusters True

Example — isolated noise point: >>> data = [[0.0, 0.0], [0.1, 0.0], [0.0, 0.1], [99.0, 99.0]] >>> labels = dbscan(data, epsilon=0.5, min_points=2) >>> labels[3] # noise -1 >>> labels[0] == labels[1] == labels[2] # one cluster True

Example — all points are noise (min_points too high): >>> data = [[0.0, 0.0], [5.0, 5.0]] >>> dbscan(data, epsilon=0.3, min_points=5) [-1, -1]

Example — single cluster (all points close together): >>> data = [[0.0, 0.0], [0.1, 0.0], [0.0, 0.1], [0.1, 0.1]] >>> labels = dbscan(data, epsilon=0.5, min_points=2) >>> len(set(labels)) 1 >>> -1 not in labels True

Example — invalid inputs: >>> dbscan([], epsilon=0.5, min_points=2) Traceback (most recent call last):

…

ValueError: Data must not be empty. >>> dbscan([[1.0, 2.0]], epsilon=0.0, min_points=2) Traceback (most recent call last):

…

ValueError: Epsilon must be greater than 0. >>> dbscan([[1.0, 2.0]], epsilon=0.5, min_points=0) Traceback (most recent call last):

…

ValueError: min_points must be at least 1.

machine_learning.dbscan.euclidean_distance(point_a: list[float], point_b: list[float]) → float

Compute the Euclidean distance between two points in n-dimensional space.

>>> euclidean_distance([0.0, 0.0], [3.0, 4.0])
5.0
>>> euclidean_distance([1.0, 2.0, 3.0], [1.0, 2.0, 3.0])
0.0
>>> euclidean_distance([0.0], [5.0])
5.0
>>> euclidean_distance([0.0, 0.0], [1.0])
Traceback (most recent call last):
    ...
ValueError: Both points must have the same number of dimensions.
machine_learning.dbscan.get_neighbors(data: list[list[float]], point_index: int, epsilon: float) → list[int]

Return indices of all points within epsilon distance of data[point_index].

>>> data = [[0.0, 0.0], [0.1, 0.1], [5.0, 5.0]]
>>> get_neighbors(data, 0, 0.5)
[0, 1]
>>> get_neighbors(data, 2, 0.5)
[2]
>>> get_neighbors(data, 0, 10.0)
[0, 1, 2]