论文部分内容阅读
随着数据的爆炸式增长，单机聚类算法无论是存储能力还是处理能力都无法满足海量数据的聚类，必须寻求并行化的解决方案。Google提出的分布式编程模型MapReduce给并行聚类带来了新的希望，因此，论文提出了一种基于MapReduce的自适应密度聚类算法。论文首先针对DBSCAN无法处理变化密度的聚类和参数敏感的问题进行了改进，提出了一种自适应的密度聚类算法ADC。算法将一个点到其第k个最邻近邻居的距离定义为密度，使用密度变化率来识别簇边界，当且仅当一个点的最邻近邻居中至少有k个点的密度与该点的密度变化率小于用户给定的阈值，该点才为核点，并且阈值在运行时自动动态调整。其次，论文在ADC的基础上，提出了一种基于MapReduce的聚类算法MR-ADC，算法包括五个步骤：1）对数据进行归一化；2）将归一化后的数据均匀的划分为若干个块；3）在划分后的每一个块上分别应用改进的ADC算法进行聚类，并且将靠近划分边界的点写入HDFS；4）对划分边界的点进行分析，将局部簇合并为全局簇；5）根据局部簇与全局簇的映射关系，对局部聚类结果进行全局簇标号。论文在一个包含4个节点的Hadoop集群上对算法进行了实验分析，包括聚类的效果和算法的时间开销。实验结果表明，ADC算法可以处理任意大小、形状和密度的聚类，并且由于自适应，参数的设置更加容易，MR-ADC算法可以取得和单线程一样的效果，并且运行时间远远小于单线程算法，适合处理海量数据聚类。