KdTree密度的聚类算法及优化

参考博客：https://www.cnblogs.com/zeze/p/7053395.html

 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

DBSCAN中的几个定义：

• Ε邻域：给定对象半径为Ε内的区域称为该对象的Ε邻域；


• 核心对象：如果给定对象Ε领域内的样本点数大于等于MinPts，则称该对象为核心对象；


• 直接密度可达：对于样本集合D，如果样本点q在p的Ε领域内，并且p为核心对象，那么对象q从对象p直接密度可达。


• 密度可达：对于样本集合D，给定一串样本点p1,p2….pn，p= p1,q= pn,假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达。


• 密度相连：存在样本集合D中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。

　　可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。密度相连是对称关系。DBSCAN目的是找到密度相连对象的最大集合。

Eg: 假设半径Ε=3，MinPts=3，点p的E领域中有点{m,p,p1,p2,o}, 点m的E领域中有点{m,q,p,m1,m2},点q的E领域中有点{q,m},点o的E领域中有点{o,p,s},点s的E领域中有点{o,s,s1}.

　　那么核心对象有p,m,o,s(q不是核心对象，因为它对应的E领域中点数量等于2，小于MinPts=3)；

　　点m从点p直接密度可达，因为m在p的E领域内，并且p为核心对象；

　　点q从点p密度可达，因为点q从点m直接密度可达，并且点m从点p直接密度可达；

　　点q到点s密度相连，因为点q从点p密度可达，并且s从点p密度可达。

二、算法优点：

1. 与K-means方法相比，DBSCAN不需要事先知道要形成的簇类的数量。

2. 与K-means方法相比，DBSCAN可以发现任意形状的簇类。

3. 同时，DBSCAN能够识别出噪声点。对离群点有较好的鲁棒性，甚至可以检测离群点。

4.DBSCAN对于数据库中样本的顺序不敏感，即Pattern的输入顺序对结果的影响不大。但是，对于处于簇类之间边界样本，可能会根据哪个簇类优先被探测到而其归属有所摆动。

5.DBSCAN被设计与数据库一同使用，可以加速区域的查询。例如 使用R*树

三、算法缺点：

1. DBScan不能很好反映高维数据。

2. DBScan不能很好反映数据集以变化的密度。

3.由于DBSCAN算法直接对整个数据集进行操作，并且在聚类之前需要建立相应的R*树，并绘制k-dist图，因此算法所需的内存空间和I/O消耗都相当可观。在计算资源有限而数据量又非常庞大的情况下，DBSCAN算法的效率将受到很大影响。（DBSCAN算法将区域查询得到的所有未被处理过的点都作为种子点，留待下一步扩展处理。对于大规模数据集中的较大类而言，这种策略会使种子点的数目不断膨胀，算法所需的内存空间也会快速增加。）

4.由于DBSCAN算法使用了全局性表征密度的参数，因此当各个类的密度不均匀，或类间的距离相差很大时，聚类的质量较差。(当各个类的密度不均匀、或类间的距离相差很大时，如果根据密度较高的类选取较小的Eps值，那么密度相对较低的类中的对象Eps 邻域中的点数将小Minpts，则这些点将会被错当成边界点，从而不被用于所在类的进一步扩展，因此导致密度较低的类被划分成多个性质相似的类。与此相反，如果根据密度较低的类来选取较大的Eps值，则会导致离得较近而密度较大的类被合并，而它们之间的差异被忽略。所以在上述情况下，很难选取一个合适的全局Eps值来获得比较准确的聚类结果。)

5.DBSCAN不是完全确定的，边界点从不同的簇中获得，可以使不同簇的一部分，取决于数据处理。

6.DBSCAN的质量取决于regionQuery(P,Eps)函数中距离的测量。最常用的距离度量是欧式距离，尤其是在高维数据中，由于所谓的维数灾难，这种度量基本上是无用的，很难为E找到一个恰当的值。虽然目前有一些基于欧式距离的算法，但是如果不能对数据和规模有很好的了解，也很难找一个有意义的距离阈值E。

7.当密度差异大时，由于选取的MinPts-Eps组合不能同时适合所有的簇，DBSACN不能很好的进行数据聚类。（缺点4）

8.输入参数敏感,确定参数Eps , MinPts困难 ,若选取不当 ,将造成聚类质量下降。

9.由于经典的DBSCAN算法中参数Eps和MinPts在聚类过程中是不变的，使得该算法难以适应密度不均匀的数据集．

四、算法改进：

　　1. 对缺点3的改进：通过选用核心点邻域中的部分点作为种子点来扩展类，从而大大减少区域查询的次数，降低I/O开销，实现快速聚类。

　　2.对缺点4的改进：为了解决上述问题，周水庚等人提出了PDBSCAN ( Partitioning-based DBSCAN)算法。该算法基于数据分区技术来扩展DBSCAN算法，它根据数据的分布特性，将整个数据空间划分为多个较小的分区，然后分别对这些局部分区进行聚类，最后将各个局部的聚类结果进行合并。 PDBSCAN 的算法思想是：首先，根据数据集在某一维或多个维上的分布特性，将整个数据空间划分为若干个局部区域，使得各局部区域内的数据尽可能分布均匀；然后依次绘制各个局部区域的k-dist图，并依次得到各个区域的Eps值，接着用 DBSCAN 算法对各个局部区域进行局部聚类；最后，将各个局部聚类的结果进行合并，从而完成整个数据集的聚类分析。由于每个局部区域都使用各自的局部Eps值来进行聚类，因此有效缓解了因使用全局Eps值而导致的聚类质量恶化的问题。

　　3.缺点8改进：

　　DBSCAN 算法的改进，输入参数的处理：针对 DBSCAN算法对输入参数(聚类半径Eps , 聚类点数 MinPts) 敏感问题 ,作如下处理。由于参数的设置通常是依赖经验 , 当数据密度相差较大和类间距离分布不均匀时 ,很难选取一个合适的 Eps 值来进行聚类且得到比较准确的结果 . 因此 , 事先确定算法的参数值大小是不可取的 ,应在聚类过程中根据聚类结果的好坏对参数进行适当的调整。比如选择适当的评价函数作为评价聚类结果的尺度。反复调整算法的参数 ,重新聚类 ,直到聚类结果满足要求。尽管DBSCAN算法提供了利用绘制降序k-距离图的可视化方法来选择Eps ,选定的Eps值已经比较接近“理想”值 ; 但常有微小差距 , 最终造成聚类结果的相差很大。可以考虑采用如下方法来加以改善 :

　　（1）可以对所有聚类对象按照从一个簇到另一个簇 ,按簇边缘→簇核心→簇边缘的顺序排序。这样,该对象序列就可以反映出数据空间基于密度的簇结构信息。基于这些信息可以容易地确定合适的Eps值 ,并随之发现各个簇。

　　（2）不对原始数据集进行聚类 ,而是通过从数据集合中抽取高密度点生成新的数据集合,并修改密度参数 ,反复进行这一过程 , 直到生成的数据集合可以很容易地被聚类为止,然后以此结果为基础,再将其它点逐层地吸附到各个类中。这样,就避免了DBSCAN算法中输入参数对聚类结果的影响。

　　（3）采用核聚类的思想对样本集进行非线性变换，使样本集的分布尽可能地均匀，经过核函数的映射使原来没有显现的特征突现出来，然后再用全局参量Eps ,从而能够更好地聚类 , 得到较好的结果 .

　　（4）在绝大多数聚类结果不理想的情况下,是Eps值选择过小,导致本应为一个簇的对象集合被分析成了多个子簇。被分开的子簇共享一些对象 ,可以认为子簇通过这些共享的对象相互连接。而DBSCAN算法将子簇的连接信息简单地丢掉 。因此,可以通过记录下所有的簇连接信息,由用户根据实际的聚类结果和簇连接信息,将被错误分开的子簇合并。这样可以提高聚类的效果,而输入参数Eps的变化对聚类结果的影响,就被最后的合并过程屏蔽掉。可以考虑以下两种方式进行改进 :

　　　　1)并行化.

　　  从DBSCAN算法可以看出,全局变量Eps值影响了聚类质量,尤其是数据分布不均匀时.因此,考虑对数据进行划分,每一个划分中的数据分布相对较均匀 ,根据每个划分中数据的分布密集程度来选取Eps值.这样一方面降低了全局变量Eps值的影响,另一方面由于具有多个划分 ,因此考虑并行处理 ,从而提高聚类效率 ,也降低了DBSCAN算法对内存的较高要求

　　      .2)增量式处理。

　　当数据增加或者删除时 ,只考虑其增加或删除的数据所影响到的那些类 . 这种方法在处理大数据集时非常有效 ,不需要重新对数据库中的数据进行聚类 ,只需要对类进行渐进性地更新 , 修正和加强已发现的类 . 另外 ,由于高维数据的复杂性 , 使聚类分析的效率和实用性都很差。通过确定聚类空间中和聚类主题相关性较强的数据维,来降低聚类空间的维度。利用数据降维可以降低数据结构上的复杂性。目前,有多种降维技术均

可用于特征空间的削减。在方法的选择上应根据降维后,信息丢失率在可接收范围内 ,来选择一种合适的降维方法。

　　4.对缺点9改进：

　　　　2.1 自适应选择 Eps 参数

　　　　对于不均匀数据分布，各个数据与周围数据的相似程度不同，因此，针对每个点，将距离该点最近的多个点的距离平均值作为该点处的稠密程度的评判标准,即对任意一点P,根据距离矩阵,选取与P点最近的k个点,计算距离的平均值.此时,每个点都能够得出一个k最近点平均距离．

　　　　然后对所有点的一维k最近点平均距离数据进行DBSCAN聚类。再对聚类结果中每类 i找到其最大平均距离的点．最后将该点与它的第k点的距离作为该类的邻域阈值Eps_i ,并将其保存以备聚类.这种发现Eps的方法主要考虑到对于不同密度的数据集,应根据各个数据的稠密程度,分别选取合适的阈值进行聚类.由于聚类中所采用的参数Eps只能够确定聚类结果中同一类数据中的密度差别，所以，参数选取所引起的误差不会对聚类结果产生很大影响．

　　　　2.2 基于变参数的 DBSCAN 聚类

1)将2.1中得出的邻域阈值Eps_i按照由小到大的顺序排列，准备聚类;

2)选取最小的邻域阈值,MinPts可以不变,对数据进行DBSCAN聚类;

3)然后使用下一个邻域阈值和MinPts作为参数,对标注为噪声的数据再次进行 DBSCAN聚类;

4)不断循环,直到所有邻域阈值均使用完毕，聚类结束.

在多次聚类过程中，邻域阈值要由小到大进行聚类.使用较小阈值进行聚类时,距离较大的类中的数据由于不满足该阈值而不被处理到,所以较小的距离阈值只能处理密度较大的点,不会对小密度数据产生影响。