DBScan class

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) is a clustering algorithm designed to discover clusters of arbitrary shape in spatial data.

Key concepts:

  • Core points: Points with at least minPoints neighbors within eps distance.
  • Border points: Points within eps distance of a core point but with fewer neighbors than minPoints.
  • Noise points: Points that are neither core nor border points

The algorithm works by:

  1. Building an optimized KD-Tree for O(log n) range queries.
  2. Finding all core points and their neighborhoods using spatial indexing.
  3. Connecting core points that are within eps distance of each other.
  4. Forming clusters using efficient queue-based seed expansion.
  5. Labeling remaining points as noise.

Performance Characteristics:

  • Time Complexity: O(n log n) average case with KD-Tree optimization
  • Space Complexity: O(n) for the spatial index and clustering state
  • Tree Construction: O(n log n) using Floyd-Rivest quickselect
  • Range Queries: O(log n + k) where k is the number of neighbors found

DBSCAN is particularly useful for:

  • Spatial data analysis (GIS, location clustering).
  • Outlier detection.
  • Clustering without specifying the number of clusters in advance.
  • Datasets with clusters of varying shapes and densities.

Unlike k-means, DBSCAN:

  • Doesn't require specifying the number of clusters.
  • Can find arbitrarily shaped clusters.
  • Can identify noise points.
  • Is less sensitive to outliers.

Constructors

DBScan.new({required double eps, required int minPoints})
Creates a new DBScan instance with the specified parameters.
const

Properties

eps → double
The maximum distance between two points to be considered neighbors.
final
hashCode → int
The hash code for this object.
no setterinherited
minPoints → int
The minimum number of points required to form a dense region.
final
runtimeType → Type
A representation of the runtime type of the object.
no setterinherited

Methods

noSuchMethod(Invocation invocation) → dynamic
Invoked when a nonexistent method or property is accessed.
inherited
run({required List<SpatialPoint> points}) → ClusteringResult
Performs DBSCAN clustering on a set of points.
runInIsolate({required List<SpatialPoint> points}) → Future<ClusteringResult>
Performs DBSCAN clustering in a separate isolate for CPU-intensive tasks.
toString() → String
A string representation of this object.
inherited

Operators

operator ==(Object other) → bool
The equality operator.
inherited