聚类算法之DBSCAN算法之二：高维数据剪枝应用NQ-DBSCAN

一、经典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上应用不多，确切的说，在大数据范围内，没有广泛应用，这在最新成果上数据的维数和数据量大小可以判断出来。但目前已经有在人脸识别、年龄预测等领域上应用。感兴趣的朋友欢迎留言讨论~