一、经典DBSCAN的不足
1.由于“维度灾难”问题,应用高维数据效果不佳
2.运行时间在寻找每个点的最近邻和密度计算,复杂度是O(n2)。当d>=3时,由于BCP等数学问题出现,时间复杂度会急剧上升到Ω(n的四分之三次方)。
二、DBSCAN在高维数据的改进
目前的研究有Grid-based和approx等方向,基于Grid-based结构的有Fast-DBSCAN,时间复杂度最坏是O(n*log(n)),但只使用于二维数据空间。ρ-approximate DBSCAN使用四叉树分级结构,在d(维度)相对较小时,运行时间呈线性O(n),d较高时,运行时间是O(n2)。
三、NQ-DBSCAN
NQ-DBSCAN即在ρ-approx DBSCAN的基础上,对高维数据聚类时,采用剪枝操作,减少不必要的距离计算。它的平均时间复杂度是O(n*log(n)),索引结构也是四叉树分级结构最优时间复杂度是O(n)。
3.1 NQ-DBSCAN的假设与结论
NQ-DBSCAN即使用三角不等式的性质,通过一个点的NBHD,不必计算所有区域,只要计算小面积的点,就可以找到其临近点的NBHD,即剪枝。
假设:当点p和q距离很近时,他们的ε-NBHD也很近(近邻区域,不了解的朋友可以看上一篇博客)。给定ε,两点距离越近,NBHD越相似。如图:
结论1:当p的l-nbhd=minPts,其中l>ε,点p是非核心点时,则与点p距离不超过l-ε的点为非核心点。
结论2:p,q,m都是数据集P中的点,
(1)如果d(p,m)<ε-d(p,q),则m属于q所在的聚类。
(2)如果d(p,m)>ε+d(p,q),则m不属于q所在的聚类。
(3)对于下图所示,已知点p的2ε范围内的点,点q的ε范围内点只需查找圈2和圈4之间的点(蓝色圈)。其中圈4内的点必定为聚类点,圈1和圈2内的点必定为非聚类点(由结论1和2得出)。
3.2 NQ-DBSCAN算法分析
3.3 NQ-DBSCAN的构造+查询
NQ-DBSCAN是在ρ-approx的基础上进行剪枝,则使用和ρ-approx一样的四叉树分级结构,同理查询算法一致。
构造过程这里比较麻烦,在文末有详细的ppt还有原始论文,感兴趣的朋友可以下载。
查询算法:
给定参数q,ε,ρ,初始化ans=0,取一个非空第i层单元c,c和查询点q有以下三种情况:
1.如果c和B(q,ε)完全不相交,则不考虑该单元。
2.如果c完全处于B(q,ε(1+ρ))中,则ans=ans+cnt©
3.不符合1和2的情况,c是叶子单元,当c与B(q,ε)相交时,ans=ans+cnt©。c不是叶子单元,递归遍历c的子单元,重复该过程。
对于第二层单元,即SW(5)和NE(4)来说,SW(5)与查询点q完全不相交,则跳过。NE(4)被点q的B(q,ε(1+ρ))覆盖,则ans=4,不必遍历子单元。
四、总结
基于密度聚类算法是聚类中一个很重要的方式,但它应用于高维数据时,时间复杂度较高。所有的密度聚类算法都面临着同样的问题:如何尽可能的将ε半径缩小,且ε-nbhd中点数达到最多?这对于ANN(近邻最近搜索)十分重要,因此,还需结合密度聚类的特点,应用在实际场景中。
五、下载
源论文下载
https://pan.baidu.com/s/11sTXuZIZ1anCxcKbdptRKA
ppt(内含详细总结)下载
https://pan.baidu.com/s/1HDkKnv6PEpKiQ21Q1Fl23g
基于密度的研究算法暂时告一段落了,这种方法在ANN上应用不多,确切的说,在大数据范围内,没有广泛应用,这在最新成果上数据的维数和数据量大小可以判断出来。但目前已经有在人脸识别、年龄预测等领域上应用。感兴趣的朋友欢迎留言讨论~