基于Hadoop MapReduce的分布式数据流聚类算法研究

Research on Distributed Clustering over Data Stream Using Hadoop MapReduce

随着数据流规模的持续增大,现有基于网格的聚类算法对数据流的聚类效果不好,不能实时发现任意形状的簇,也不能及时删除数据流中的噪声点。文章提出了一种Hadoop平台环境下基于网格密度的分布式数据流聚类算法(PGDC-Stream),利于基于Hadoop的MapReduce框架对数据流进行阶段化的并行聚类分析,实时发现数据流中任意形状的簇,定义检测周期和密度阈值函数并及时删除数据流中的噪声点。算法基于网格密度对数据流初始聚类后,随着新数据的到来,使用基于密度阈值函数的噪声点处理策略,周期性检测和删除噪声点,使用基于Hadoop MapReduce框架的并行分析模型周期性地调整已经生成的簇。实验结果表明,PGDC-Stream对大规模数据流的聚类质量、可伸缩性和实时性都好于CluStream。

With continuous increase in data stream scale, most existing grid-based clustering algorithms are incompetent to find clusters of arbitrary shape in real-time, and the noise points could not be removed timely. To address these issues, this paper proposes PGDC-Stream, a novel grid-based algorithm for clustering data streams using Hadoop MapReduce. The algorithm adopts a parallel cluste- ring model based on Hadoop Mapreduce to find clusters in real-time. Exploiting a new time-based density threshold function and detecting cycle, the proposed algorithm could remove noise points time- ly. Firstly,PGDC-Stream clusters the data stream using grid density, with the new data records continuously arriving, a novel pruning strategy is used to inspect and remove the noise points periodically. Simultaneously, based on the parallel clustering model, the generated clusters are dynamically adjusted to capture the evolution of the data stream. The experimental results show that PGDC-Stream has superior efficiency, and its clustering quality and scalability are better than CluStream.