DBSCAN算法原理

DBSCAN(Density-Based Spatial Clustering of Applications with Noise，基于密度的噪声空间聚类)。大概思想：给定一组空间中的点，它会将紧密挨在一起的点（或者说有很多邻居的点）划分为同一个簇，这些点聚集在一起形成一个高密度的区域；将低密度区域的点标记为异常点，这些点邻居很少。

定义：

• 样本集为 D = ( X 1 , … , X N ) D=(X_1,…,X_N) D=(X1​,…,XN​)
• ϵ ϵ ϵ：邻域距离阈值（为其中一个输入参数），当样本 X i X_i Xi​与 X j X_j Xj​的距离小于 ϵ ϵ ϵ时，则 X i X_i Xi​是 X j X_j Xj​的邻居， X j X_j Xj​也是 X i X_i Xi​的邻居
• ϵ − ϵ- ϵ−邻域 N ϵ ( i ) N_ϵ (i) Nϵ​(i)，对于 D D D中的一个样本 X i X_i Xi​，其 ϵ − ϵ- ϵ−邻域为 N ϵ ( i ) = { X j ∈ D ∣ d ( i , j ) ≤ ϵ } N_ϵ (i)=\{X_j∈D|d(i,j)≤ϵ\} Nϵ​(i)={Xj​∈D∣d(i,j)≤ϵ}，基数为 ∣ N ϵ ( i ) ∣ |N_ϵ (i)| ∣Nϵ​(i)∣， d ( i , j ) d(i,j) d(i,j)为样本 i i i, j j j间的距离函数，如欧式距离
• 核心点：如果样本 X i X_i Xi​的 ϵ − ϵ- ϵ−邻域个数 ∣ N ϵ ( i ) ∣ ≥ m i n p t s |N_ϵ (i)|≥minpts ∣Nϵ​(i)∣≥minpts（为另一个输入参数），即 X i X_i Xi​至少有 m i n p t s minpts minpts个邻居，则样本 X i X_i Xi​称为一个核心点
• 密度直达：如果 X j X_j Xj​是 X i X_i Xi​的邻居且 X i X_i Xi​是核心点，则称 X j X_j Xj​到 X i X_i Xi​密度直达，这种关系不是对称的， X i X_i Xi​到 X j X_j Xj​不一定是密度直达的，除非 X j X_j Xj​也是核心点
• 密度可达：如果存在样本序列 p 1 p 2 … p ( T − 1 ) p T p_1 p_2…p_{(T-1)} p_T p1​p2​…p(T−1)​pT​，且 p ( t + 1 ) p_(t+1) p(​t+1)到 p t p_t pt​密度直达（也就是说 p 1 … p ( T − 1 ) p_1…p_{(T-1)} p1​…p(T−1)​都是核心点），则称 p T p_T pT​到 p 1 p_1 p1​密度可达
• 密度相连： 对于样本 X i X_i Xi​和 X j X_j Xj​，如果存在核心点 X k X_k Xk​使得 X i X_i Xi​和 X j X_j Xj​到 X k X_k Xk​都是密度可达的，则 X i X_i Xi​和 X j X_j Xj​是密度相连的， X k X_k Xk​相当于一座桥梁，这种关系是对称的。
• 异常点：所有不能从其他点可达的点都是异常点

DBSCAN将所有点标记为核心点、边界点或异常点。需要确定的两个参数为 ϵ , m i n p t s ϵ,minpts ϵ,minpts。如下图(来自维基百科)， m i n p t s = 4 minpts=4 minpts=4，红色点是核心点（其邻居个数都大于4），黄色点B、C不是核心点，因为它们的邻居个数小于4，但它们到至少一个核心点密度直达，且点B和C是密度相连的，因为点B和C到核心点A是密度可达的。蓝色点N不到任一点可达所以是异常点。

通过以上分析可知：DBSCAN将任意两个距离小于 ϵ ϵ ϵ的核心点归为同一个簇（上图中所有红色点），任何与核心点足够近的边界点也放到与之相同的簇中。所以上图所有红色和黄色点为一个簇。
DBSCAN是基于密度聚类的，本身就有发现异常点的功能，算法发现的异常点恰好是我们所需要的。
DBSCAN参数设置：如果 ϵ ϵ ϵ设置过大，则所有的点都会归为一个簇，如果设置过小，那么簇的数目会过多。如果 m i n p t s minpts minpts设置过大的话，很多点将被视为噪声点，但也会找到更多异常点。

ϵ ϵ ϵ的选取方法可参考这篇论文：Determination of Optimal Epsilon (Eps) Value on DBSCAN Algorithm to Clustering Data on Peatland Hotspots in Sumatra，或是博客，思想很简单，就是对距离排序然后画图找到拐点位置对应的距离就是最优 ϵ ϵ ϵ。