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

Research on Distributed Clustering over Data Stream Using Hadoop MapReduce

作　　者：蔡斌雷[1] 任家东[2] 朱世伟[1] 郭芹[3] 

机构地区：[1]山东省科学院情报研究所,山东济南250014 [2]燕山大学信息科学与工程学院,河北秦皇岛066004 [3]济南大学泉城学院,山东烟台265600

出　　处：《信息工程大学学报》2014年第4期472-478,共7页Journal of Information Engineering University

基　　金：国家自然科学基金资助项目(61170190);国家青年基金资助项目(61004115)

摘　　要：随着数据流规模的持续增大,现有基于网格的聚类算法对数据流的聚类效果不好,不能实时发现任意形状的簇,也不能及时删除数据流中的噪声点。文章提出了一种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.

关 键 词：数据挖掘 聚类 数据流聚类 分布式聚类 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]