DBSCAN

DBSCAN is a density-based clustering algorithm first described in Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu (1996). "A density-based algorithm for discovering clusters in large spatial databases with noise". In Evangelos Simoudis, Jiawei Han, Usama M. Fayyad. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231 defines three types of points in a dataset. Core Points are points that have at least a minimum number of neighbors (MinPts) within a specified distance (eps). Border Points are points that are within eps of a core point, but have less than MinPts neighbors. Noise Points are neither core points nor border points.

Clusters are built by joining core points to one another. If a core point is within eps of another core point, they are termed directly density-reachable.) All points that are within eps of a core point are termed density-reachable and are considered to be part of a cluster. All others are considered to be noise.