""" 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: - https://en.wikipedia.org/wiki/DBSCAN - Ester, M., et al. "A density-based algorithm for discovering clusters." KDD 1996. https://dl.acm.org/doi/10.5555/3001460.3001507 """ def 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. """ if len(point_a) != len(point_b): raise ValueError("Both points must have the same number of dimensions.") return sum((a - b) ** 2 for a, b in zip(point_a, point_b)) ** 0.5 def 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] """ return [ index for index, point in enumerate(data) if euclidean_distance(data[point_index], point) <= epsilon ] def 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. """ if not data: raise ValueError("Data must not be empty.") if epsilon <= 0: raise ValueError("Epsilon must be greater than 0.") if min_points < 1: raise ValueError("min_points must be at least 1.") labels = [-1] * len(data) # all points start as noise current_cluster_id = 0 for point_index in range(len(data)): if labels[point_index] != -1: continue # already assigned neighbors = get_neighbors(data, point_index, epsilon) if len(neighbors) < min_points: continue # not a core point — remains noise for now # point_index is a core point — start a new cluster labels[point_index] = current_cluster_id seeds = [n for n in neighbors if n != point_index] while seeds: current_point = seeds.pop() # skip points already claimed by a different cluster if ( labels[current_point] != -1 and labels[current_point] != current_cluster_id ): continue # assign noise points and unvisited points to this cluster labels[current_point] = current_cluster_id current_neighbors = get_neighbors(data, current_point, epsilon) if len(current_neighbors) >= min_points: # current_point is also a core point — expand cluster for neighbor in current_neighbors: if labels[neighbor] == -1: seeds.append(neighbor) current_cluster_id += 1 return labels if __name__ == "__main__": import doctest doctest.testmod(verbose=True)