本文介绍了一种无参的密度聚类算法-DBSCAN。首先介绍了DBSCAN的类表示为一簇密度可达的样本点,相似性度量为密度可达。然后介绍了DBSCAN中几个基本定义: -邻域,核心对象,密度可达,密度直达,噪声点,基于此绍了DBSCAN算法的实现流程。最后介绍了算法的特点,能发现任意簇,抗噪性强,聚类时间长,存在维度灾难问题。
作者 | 文杰
编辑 | yuquanle
DBSCAN的类表示是一簇密度可达的样本,相似性度量定义为密度可达,密度可达即为一类,属于硬划分。
密度聚类是一种基于密度的聚类,其根据样本的空间分布关系进行聚类。一般来讲,用带参的模型来定义样本的分布可以看作是带参的密度估计,比如高斯混合模型,高斯判别分析;用无参的模型来描述样本的分布称为无参密度估计,比如直方图,核密度估计,山峰聚类,DBSCAN,meanshift。
假设样本集是,在DBSCAN中为了描述样本分布的关系,定义了如下几个概念:
1) -邻域:对于,其-邻域包含样本集中与的距离不大于的子样本集,即 这个子样本集的个数记为。
2)核心对象:对于任一样本,如果其-邻域对应的 至少包含个样本,即如果,则是核心对象。
3)密度直达:如果位于的-邻域中,且是核心对象,则称由密度直达。注意反之不一定成立,即此时不能说由密度直达, 除非且也是核心对象。
4)密度可达:如果由密度直达,且由密度直达,那么由密度可达。密度可达满足封闭性。
其中密度可达是相似性度量,由于密度可达具有封闭性,所以簇内的所有点与簇内的核心均密度可达,否则即不是一个簇,所以密度可达可以对样本进行聚类,其中密度可达涉及的参数有和和距离度量。
5)噪声点:对于非核心点和不能由核心点密度可达的点即为噪声点。
输入:样本集,邻域参数, 样本距离度量方式
输出:簇划分
1)初始化核心对象为,簇划分,未访问样本集合。
2)变量所有样本点,找出的核心对象并入核心对象。
3)如果核心对象,算法结束,否则从核心对象集中随机选择一个核心对象,初始化当前簇,当前核心对象集为,循环:
a)从当前的核心对象集中选择,循环:
aa)找出密度直达的未访问的点加入到,把其中未访问的核心对象加入到
ab)更新当前核心对象集
ac)更新核心对象集,更新未访问样本集
b)如果当前核心对象集,结束内部循环
4)输出簇划分。
可以看出,外层循环为簇的个数,内层循环是构建一个密度可达的簇。当算的执行完,对应既不是核心点,也不是密度可达的点我们称为异常点或者噪声点。
DBSCAN的特点:
1)由于密度可达的定义,DBSCAN具有发现任意形状的簇划分。
2)聚类的同时可发现异常点,抗噪性强。
3)不需要预先指点类数,但和的直观性不强,参数选择麻烦。
4)样本集较大时,聚类收敛时间较长,密度估计存在维度灾难问题。
5)如果样本集的密度不均匀、聚类间距差差别很大时,聚类质量较差,这时用DBSCAN聚类一般不适合。
The End