引言

其实对于所有的聚类问题，都有一个核心点，那就是以什么样的规则来划分两个点是不是同一类。密度聚类，本质上就是基于一种密度的概念来进行聚类。而密度的定义本质上也是来自于两点的距离，所以其实对于聚类的算法来看，大家本质上都差不多，谁也别笑话谁。下面我们来总结介绍一种叫做DBSCAN的密度算法。

DBSCAN

DBSCAN 的全称是 Density-Based Spatial Clustering of Applications with Noise
单词里面有个noise,这就说明我们的算法是能抗噪声的，并且我们的算法是可以在空间中聚类为任意形状的聚类的，这点是一些其他的聚类算法不具备的性质，如下所示：

具有这样的性能，就是因为我们的算法引入了“邻域”（其参数为(ε,MinPts)$(\epsilon ,MinPts)$）的概念来刻画样本的紧密程度的算法。

下面我们来介绍一下这个算法，在具体算法之前，我们先看几个定义，非常简单，但是可能比较绕，懂了这几个定义，下面的算法就是小菜一碟了。

基于密度的几个概念

ε−$\epsilon -$邻域：

对xj∈D$x_j\in D$，其ε−$\epsilon -$邻域是指样本集D$D$中与xj$x_j$距离不大于ε$\epsilon$的样本，即Nε(xj)={xj∈D|dist(xi,xj)≤ε}$N_{\epsilon }(x_j)=\left\{x_j\in D|dist(x_i,x_j)\le \epsilon \right\}$

核心对象：

对象xj$x_j$的ε−$\epsilon -$邻域中至少包含MinPts$MinPts$个样本，即Nε(xj)≥MinPts$N_{\epsilon }(x_j)\ge MinPts$，则称xj$x_j$为核心对象。

密度直达：

若xj$x_j$位于xi$x_i$的ε−$\epsilon -$邻域中，且xi$x_i$是核心对象，则称xj$x_j$由xi$x_i$密度直达。

密度可达：

对xj$x_j$与xi$x_i$，存在样本序列p1,p2,...,pn$p_1,p_2,...,p_n$且p1=xj,pn=xi$p_1=x_j,p_n=x_i$ 且pi+1$p_{i+1}$由pi$p_i$密度直达，则称xj$x_j$由xi$x_i$密度可达。

其实这个概念本质上要求p2,...,pn$p_2,...,p_n$都是核心对象

密度相连：

对xj$x_j$与xi$x_i$，若存在xk$x_k$使得xj$x_j$与xi$x_i$均由xk$x_k$密度可达，则称xj$x_j$由xi$x_i$密度相连。

下图直观的表示了这几个概念

基于上面的概念，可以定义DBSCAN算法里面的簇的定义

簇： 由密度可达关系导出的最大的密度相连的样本集合。

因此实际上簇C⊆D$C\subseteq D$满足下面的两个条件：

连接性：xi∈C,xj∈C⇒$x_i\in C,x_j\in C\Rightarrow$ xi$x_i$与xj$x_j$密度相连

最大性：xi∈C$x_i\in C$ 且xj$x_j$由xi$x_i$密度可达 ⇒xj∈C$\Rightarrow x_j\in C$

实际上就是核心对象以及与其密度可达的所有的点的集合

本质上相当于一些核心对象以及边界点组成了簇，簇中核心的点就是核心对象。

具体算法描述

实际上就是核心对象以及与其密度可达的所有的点的集合

输入

• 样本集 D={x1,...,xN}$D=\left\{x_1,...,x_N\right\}$
• 邻域参数(ε,MinPts)$(\epsilon ,MinPts)$

算法流程

• 找出所有的核心对象，放入集合中 Ω$\mathrm{\Omega }$
• 初始化未访问的样本集合：Γ=D$\mathrm{\Gamma }=D$
• while(Ω≠∅)$while(\mathrm{\Omega }\ne \varnothing )$
  

• Γold=D${\mathrm{\Gamma }}_{old}=D$
  
• 随机选取一个核心对象o∈Ω$o\in \mathrm{\Omega }$，初始化Q=<o>$Q=<o>$
  
• Γ=Γ∖{o}$\mathrm{\Gamma }=\mathrm{\Gamma }\setminus \left\{o\right\}$
  
• while(Q≠∅)$while(Q\ne \varnothing )$
  

• 从 Q$Q$中取出样本q$q$
  
• if(q$if(q$是核心对象)$)$
  

• 另Δ=Nε(q)∩Γ$\mathrm{\Delta }=N_{\epsilon }(q)\cap \mathrm{\Gamma }$， 即获取核心对象q$q$邻域内的点
  
• 将Δ$\mathrm{\Delta }$内的点加入到Q$Q$中
  
• Γ=Γ∖Δ$\mathrm{\Gamma }=\mathrm{\Gamma }\setminus \mathrm{\Delta }$
  
• endif$endif$
  
• endwhile$endwhile$
  
• k=k+1$k=k+1$,并且生成聚类簇Ck=Γold∖Γ$C_k={\mathrm{\Gamma }}_{old}\setminus \mathrm{\Gamma }$
  
• Ω=Ω∖Ck$\mathrm{\Omega }=\mathrm{\Omega }\setminus C_k$
• endwhile$endwhile$

输出

簇划分C={C1,...,CK}$C=\left\{C_1,...,C_K\right\}$

算法的优缺点

优点：

• 算法不需要指定聚类的数目，但是算法实际上需要另外两个参数(ε,MinPts)$(\epsilon ,MinPts)$，所以这个优点也是勉强。
• 可以聚成任意形状的类，就像开始的图所示
• 能够识别出噪声点

缺点：

• 对高维数据效果不算好
• 如果样本的密度不均， 效果会不理想