论文部分内容阅读
大数据时代的到来,对人们的生产、生活以及工作和思维都产生着巨大的影响。在海量数据面前,如何将其转换为有价值的信息和知识,是当前一个十分重要且有意义的课题。通过对数据转换,数据处理和分析,数据挖掘在各个领域的数据分析和知识发现中发挥着重要的作用。聚类分析作为数据挖掘中的一个重要技术手段,它已被广泛的应用于各种数据分析场合。聚类分析通过发现数据集中对象的相关和分布模式,从而将数据集中的对象分组为不同的簇,每个簇中的对象类似。由于聚类分析在数据挖掘的应用范围内使用广泛,所以,提高聚类算法的效果很有必要。基于密度的聚类算法是著名的一类聚类算法,它基于密度扩展,可以从有噪声的数据集中发现各种形状的簇。但是,现在随着信息的爆炸式增长,形成的数据中包含着各种各样形式复杂的数据类型。所以,如何提高基于密度的聚类结果的准确程度和算法的自适应能力是一项值得研究的课题和挑战。作为聚类算法的一种,DBSCAN算法是经典的基于密度的一种聚类算法。它能够通过密度扩展来进行聚类。DBSCAN算法可以在包含有噪声和边界点的数据集中发现任意形状的簇,同时具有很好的抗噪声的能力。但是,DBSCAN算法有以下几个缺点。首先,它需要用户输入特定的参数,增加了对不同领域知识的依赖性;然后,由于使用了固定的全局参数的缘故,它不能很好的对非均匀数据集进行聚类;最后,算法的计算成本和I/O消耗比较大。针对以上问题的前两个缺点,本文提出了基于密度层次划分的自适应DBSCAN算法,SADBSCAN-DLP((A self-adaptive multi-density DBSCAN based on Density Levels Partitioning)。算法的思路如下:计算出数据集中各个对象的k近邻距离并排序,同时得到KNN矩阵,根据KNN矩阵中每一列数据对象间密度分布情况计算密度层次跳变阈值,通过该阈值来划分不同密度层次的数据代表集,根据聚类效果指数CEI(Clustering effect index)的值来自动得到Min Pts参数,并对每个代表集的Eps参数进行估计,最后,在每个代表集上用参数Min Pts和相应的Eps参数进行局部聚类,再将得到的各个局部聚类的结果逐一进行合并。实验结果表明,改进算法在参数自适应能力和针对非均匀数据集的聚类结果的质量上要优于传统的DBSCAN算法。