基于MapReduce的分布式网络数据聚类算法  

Distributed Clustering Algorithm for Network Data Based on MapReduce

作　　者：陈东明[1] 刘健[1] 王冬琦[1] 徐晓伟[2] 

机构地区：[1]东北大学软件学院,沈阳110819 [2]阿肯色大学小石城分校信息科学系,美国小石城72204

出　　处：《计算机工程》2013年第7期76-82,共7页Computer Engineering

基　　金：辽宁省自然科学基金资助项目(20102059)

摘　　要：时空复杂度较高以及物理机器内存不足,会导致传统聚类算法不能有效地分析处理大规模数据网络。针对该问题,在MapReduce分布式模型的基础上,提出一种网络数据分布式聚类算法。根据MRC理论设计有限MapReduce轮数,控制混洗过程所需时间,利用Map内合并技术对网络流量进行控制,在进行中间结果合并时仅对社团合并,而不考虑社团内部节点,以控制内存开销。使用模拟生成的数据在集群中进行实验,结果表明,当数据规模和集群规模增大时,该算法具有较好的加速比和扩展性。Due to the high time and space complexity and physical machines out of memory, traditional clustering algorithms usually can not effectively analyze and deal with large data network. To solve this problem, this paper proposes a distributed clustering algorithm for network data based on MapReduce model. It adopts the theory of MRC theory to design limited round number of MapReduce to control the time in shuffle stage, and utilizes the Map inner merging technology to control network flow. It proposes an idea that if merge the intermediate results, only merge clusters and do not consider the internal nodes, which can control memory overhead. It utilizes the data sets generated by simulation to do experiment. Experimental results show that when the data size and cluster scale increases, the CAMR algorithm has good speedup ratio and scalability.

关 键 词：聚类算法 分布式聚类 MapReduce编程模型 数据挖掘 社团结构 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]