DBSCAN全称Density-based spatial clustering of applications with noise，即带噪声的基于密度的空间聚类。主要思想就是把空间中密度较大，每个点之间有多个邻近点的部分聚为一类，而把密度较低的部分作为离群值（outlier）对待。
DBSCAN需要设置两个参数，minPts和 ϵ ，这两个参数主要用于定义以下概念。
根据密度可达（reachable）的定义，我们可以发现，reachable并不是对称的， p 密度可达q，但如果 q 不是核心点，那么q并不密度可达 p 。因此，引入密度相连的概念。定义如下： 已知有点p， q ，如果另存在点o且 o 既密度可达p也密度可达 q ，则陈p和 q 密度相连（Density-Connected）。
有了密度相连的定义，簇的定义随即产生。在dbscan中，所有密度相连的点构成的集合为一个簇（cluster）。具体请见下例（来自wikipedia）。
上图为R2中各点，设minPts = 4，各圆的半径为 ϵ 。则各红点为核心点，因为空间中距离它们 ϵ 的点至少有4个（包括自己）。另外，红点和黄点密度相连，它们共同形成了一个簇。最后，蓝色点N是离群点，因为没有任何点可达它。
我们可以观察到上图中的B点和C点虽然不是核心点，但是它们与红色点密度相连，因此也被归到和红色点一起的簇中。只不过作为非核心点，它们没法再向外拓展其他它们直接可达的点。因而可以把这些点理解为这个簇的边界点。
D: total points set 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)通过上式可以看到，一个cluster的扩张，全是通过核心点来做的。
由于要比较每个点之间的距离来判断点与点之间是否“直接密度可达”，因此在这里算法复杂度为 O(n2) 。
优点：DBSCAN算法最大的优点是它不需要像kmeans一样事先明确具体的簇的数量；且DBSCAN面向的的数据集簇的形状可以是非凸的，这是因为某点是否属于一个簇是由这个簇中做靠近它的核心点决定的，也就是说这个簇的局部来决定，而不是像kmeans一样一个点代表了整个簇；另外，由于DBSCAN有离群点的概念，模型健壮性更强；最后，在具体领域中，如果模型使用者对数据认识非常到位，可以把minPts和 ϵ 两个参数定的比较合适，有时候这两个参数或许是可以由对应实际学科中的某概念来解释。 缺点： DBSCAN中，部分在簇边界上的点可能可以被分到多个簇中，具体被分到哪个取决于遍历时的顺序，不过这个并不会影响到核心点和离群点的定义，以及核心点之间的聚类；由于需要计算距离（通常用欧氏距离），一旦数据的维数较高，计算量会很大，而且此时定义一个合适的 ϵ 难度也会比较大；另外，数据集中每个簇自己的密度可能会有点不同，此时唯一的minPts- ϵ 组合并不能很好的描述这个场景。
通过上文，其实可以发现DBSCAN中很关键的一个部分是决定数据集中每个点是否是核心点。传统DBSCAN做法是计算每个点之间的距离，并以此判断各点的邻近点数量，算法复杂度是 O(n2) 。事实上，决定一个点是否为核心点，只需要参考这个点与“周围”的点的距离即可，并不需要计算这个点和其余所有点之间的距离。也就是说，如果我们能保证在这个“周围”之外的点的距离一定大于 ϵ ，且让这个“周围”尽可能的大或者可以提供其他一些方面计算的便利，我们就可以省去很多计算。那么，到底如何合理地定义这个”周围“呢？ 有一个思路是将数据集划成一个个的小格，每个小格就是一个“周围”，在这个小格中的各点之间可以由一定的关系，且各小格之间也有一些关系来简化一些计算。详细思路请见下文。
为便于说明和理解，下文中的说明都将以 R2 中数据集为例。
将 R2 划分成各个以 ϵ/2√ 为边长的正方形小格（下文有时称grid），则每个点唯一对应的grid也可以确定下来，具体为各点坐标除以grid的边长，取下界整数。此处算法复杂度为 O(n) 。
这么定义grid有如下好处： 1. 首先，每个小格的对角线长度为 ϵ ，是每个小格内的最长距离。换句话说，每个小格内的各点之间的距离不会超过 ϵ ，因此，如果在同一个小格中的点数量超过了参数minPts，那么不需要计算这些点的邻近点数量，就可以直接判断这些点为核心点； 2. 对那些包含点数量没超过minPts的小格，也不需要讲其中的点和数据集中其他所有点计算距离。一来对于小格中的点，小格中已包含了一部分它的邻近点，其次，我们只需要去邻近的小格中找点即可，如下图中，对最中心的grid，只需要找其周围的21个grid（包括自己）中的点几个。
本图来自参考文献3. 因为每个grid内点与点之间的距离不大于 ϵ ，因此同一个grid的点互相密度相连。所以，如果两个来自不同grid的核心点之间可以确定密度相连，那么，这两个grid中所有点都密度相连。换句话说，我们就不需要再确定每个点之间是否相连，而只需要确定grid与grid之间是否相连即可，这里“grid密度相连”的定义为：如果 p1 是来自 grid1 的核心点， p2 是来自 grid2 的核心点，且 p1,p2 密度相连，则 grid1,grid2 密度相连。
D: total points set eps: ϵ ，用于定义核心点的半径 MinPts: 用于定义核心点的邻近点数量
G = set_grid(); // 分配所有点到对应的grid，得到grid的全集G find_core_point(); merged_G = merge_grid(); // 将grid合并，merged_G可以看成一个二维数组，所有互相连接的grid存在同一个数组中 class_point(); find_core_point() { for grid in G size = grid.pt_set.size(); if (size > minPts) 每个grid.pt_set中的点均为核心点； else for pt in grid.pt_set if (pt与grid.neigh_grid_set中超过(minPts - size)个点距离小于eps) pt是核心点; } merge_grid() { for grid in G for neigh_grid in grid.neigh_grid_set check grid与neigh_grid是否相连 merge_connected_grid(); } class_point() { for cluster in merged_G 所有clster.grid.pt记为一个簇 for grid in G if grid not in merged_G // 这些grid中没有core_point for neigh_grid in grid.neigh_grid.set if neigh_grid中有core_point与grid中点相连 neigh_grid中各点分到core_point的簇中 break； grid中所有点为NOISE； }根据参考文献中描述，加入grid索引之后，算法复杂度可以降到 O(nlog(n)) ，且在计算中略去了不少不必要的点与点之间的计算。但是这个方法仍不能解决在数据特征维数变高后带来的计算问题，而且，当数据特征维数变多之后，寻找grid的neighbour grid的难度也会变大。
当特征维数变多之后，寻找grid的邻近grid难度较大。Brute force的方法是直接找包含从grid各边向外延伸一个 ϵ 的最小正方体，但一旦维数变多，这个超正方体会包含很多非邻近grid的grid。
