计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2013年
7期
76-82
,共7页
陈东明%刘健%王冬琦%徐晓伟
陳東明%劉健%王鼕琦%徐曉偉
진동명%류건%왕동기%서효위
聚类算法%分布式聚类%MapReduce编程模型%数据挖掘%社团结构
聚類算法%分佈式聚類%MapReduce編程模型%數據挖掘%社糰結構
취류산법%분포식취류%MapReduce편정모형%수거알굴%사단결구
clustering algorithm%distributed clustering%MapReduce programming model%data mining%community structure
时空复杂度较高以及物理机器内存不足,会导致传统聚类算法不能有效地分析处理大规模数据网络。针对该问题,在MapReduce分布式模型的基础上,提出一种网络数据分布式聚类算法。根据MRC理论设计有限MapReduce轮数,控制混洗过程所需时间,利用Map内合并技术对网络流量进行控制,在进行中间结果合并时仅对社团合并,而不考虑社团内部节点,以控制内存开销。使用模拟生成的数据在集群中进行实验,结果表明,当数据规模和集群规模增大时,该算法具有较好的加速比和扩展性。
時空複雜度較高以及物理機器內存不足,會導緻傳統聚類算法不能有效地分析處理大規模數據網絡。針對該問題,在MapReduce分佈式模型的基礎上,提齣一種網絡數據分佈式聚類算法。根據MRC理論設計有限MapReduce輪數,控製混洗過程所需時間,利用Map內閤併技術對網絡流量進行控製,在進行中間結果閤併時僅對社糰閤併,而不攷慮社糰內部節點,以控製內存開銷。使用模擬生成的數據在集群中進行實驗,結果錶明,噹數據規模和集群規模增大時,該算法具有較好的加速比和擴展性。
시공복잡도교고이급물리궤기내존불족,회도치전통취류산법불능유효지분석처리대규모수거망락。침대해문제,재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.