DBSCAN，英文全写为Density-based spatial clustering of applications with noise ，是在 1996 年由Martin Ester, Hans-Peter Kriegel, Jörg Sander 及 Xiaowei Xu 提出的聚类分析算法， 这个算法是以密度为本的：给定某空间里的一个点集合，这算法能把附近的点分成一组（有很多相邻点的点），并标记出位于低密度区域的局外点（最接近它的点也十分远），DBSCAN 是其中一个最常用的聚类分析算法，也是其中一个科学文章中最常引用的。

在 2014 年，这个算法在领头数据挖掘会议 KDD 上获颁发了 Test of Time award，该奖项是颁发给一些于理论及实际层面均获得持续性的关注的算法。

考虑在某空间里将被聚类的点集合，为了进行 DBSCAN 聚类，所有的点被分为、及，详请如下：

如果 p 是核心点，则它与所有由它可达的点(包括核心点和非核心点)形成一个聚类，每个聚类拥有最少一个核心点，非核心点也可以是聚类的一部分，但它是在聚类的“边缘”位置，因为它不能达至更多的点。

“可达性”（英文：Reachability ）不是一个对称关系，因为根据定义，没有点是由非核心点可达的，但非核心点可以是由其他点可达的。所以为了正式地界定 DBSCAN 找出的聚类，进一步定义两点之间的“连结性”（英文：Connectedness） ：如果存在一个点 使得点 和点 都是由 可达的，则点 和点 被称为(密度)连结的，而连结性是一个对称关系。

定义了连结性之后，每个聚类都符合两个性质：

DBSCAN 需要两个参数：ε (eps) 和形成高密度区域所需要的最少点数 (minPts)，它由一个任意未被访问的点开始，然后探索这个点的 ε-邻域，如果 ε-邻域里有足够的点，则建立一个新的聚类，否则这个点被标签为杂音。注意这个点之后可能被发现在其它点的 ε-邻域里，而该 ε-邻域可能有足够的点，届时这个点会被加入该聚类中。

如果一个点位于一个聚类的密集区域里，它的 ε-邻域里的点也属于该聚类，当这些新的点被加进聚类后，如果它(们)也在密集区域里，它(们)的 ε-邻域里的点也会被加进聚类里。这个过程将一直重复，直至不能再加进更多的点为止，这样，一个密度连结的聚类被完整地找出来。然后，一个未曾被访问的点将被探索，从而发现一个新的聚类或杂音。

算法可以以下伪代码表达，当中变数根据原本刊登时的命名：

DBSCAN(D, eps, MinPts) { C = 0 for each point P in dataset D { if P is visited continue next point mark P as visited NeighborPts = regionQuery(P, eps) if sizeof(NeighborPts) MinPts mark P as NOISE else { C = next cluster expandCluster(P, NeighborPts, C, eps, MinPts) } }}expandCluster(P, NeighborPts, C, eps, MinPts) { add P to cluster C for each point P' in NeighborPts { if P' is not visited { mark P' as visited NeighborPts' = regionQuery(P', eps) if sizeof(NeighborPts') = MinPts NeighborPts = NeighborPts joined with NeighborPts' } if P' is not yet member of any cluster add P' to cluster C }}regionQuery(P, eps) return all points within P's eps-neighborhood (including P)

注意这个算法可以以下方式简化：其一，"has been visited" 和 "belongs to cluster C" 可被结合起来，另外 "expandCluster" 副程式不必被抽出来，因为它只在一个位置被调用。以上算法没有以简化方式呈现，以反映原本出版的版本。另外，regionQuery 是否包含 P 并不重要，它等价于改变 MinPts 的值。

DBSCAN 对数据库里的每一点进行访问，可能多于一次（例如作为不同聚类的候选者），但在现实的考虑中，时间复杂度主要受regionQuery 的调用次数影响，DBSCAN 对每点都进行刚好一次调用，且如果使用了特别的编号结构，则总平均时间复杂度为 O(n log n) ，最差时间复杂度则为 O(n^2) 。可以使用 O(n^2) 空间复杂度的距离矩阵以避免重复计算距离，但若不使用距离矩阵，DBSCAN 的空间复杂度为 O(n)。