聚类分析的并行化实现技术研究.pdf

第23卷第2期
电子设计工程
2015年1月
Vol 23
Electronic Design Engineering
fan.2015
聚类令折的开行化实规故术研究
齐浩,马力
(1.西安邮电大学计算机学院,陕西西安710121:2.西安邮电大学数宇艺术学院,陕西西安710061)
摘要;文中基于使传统聚类算法能够满足当前大敬据分析的对计算效卒的需求,采用将传统聚类算法分布式化的方
法提高传统聚类算法效率。结合近年来广泛使用的 Mapreduce分布式处理模型,对K- mcans、PAM、C.I.ARA3种算法
进行了分布式化实验,并从数据规模和节点效量两个方面考察、讨论了一些影响并行算法性能的因素。实验分析表
明,该方法能够有效地将聚类方法并行化,并可以应用在分布式系统当中。
关键词:数据挖掘;聚类; Mapreduce;并行化计算
中图分类号:INO2
文献标识码:A
文章编号:1674-6236(2015)02-0048-03
Parallel implementation of clustering analysis
QI liao', MA Li-
(1. School ofcomputer Science and Technology, Xi'an University of Post and Telecommunications, Xi an 710121
China; 2. School of Digita A s. i mn niers y of s and Telecommunication, Xi an 710061, Chino
Abstract: Based on the traditional clustering algorithms to meet the needs of todays big data analysis of computational
efliciency, distributed clustering algorithm of the traditional lo improve the efliciency of Iraditional clustering algorithm
inding the widely used in recent years distributed model Mapreduce, made three experiments using K-means, PAM and
C ARA to realize the parallel clustering Through changing the siz of data and the number of nodes to discuss the faetor
effected the parallel performance of the algorithm. The experiments show that Lhis method ean effectively parallelize the
clustering method. and can be used in which distributed svstems
Key words: dala mining: cluslering; Mapreduce; parallel compuling
根据美国风险基金KPCB( kleiner perkins caufield& Sanjay Ghemawat是出的一种分布式编程模型阳,起初的日标
byers)在2013年的《互联网趋势报告》中的统计和预测,互联是用于大于1TB的大規模数据集的计算。 Mapreduce解决了
网上的数据在过去五年间増长了9倍,在过去的8年中在分布式集群中进行并行计算、分发数据、处理失效的问题
(2005-2013),数据量几乎严格按照摩尔定律测的速度在不时所遇到的种种复杂问题。它将并行、容错、数据分布和负载
停的增长。2013年的全网数据量(包括文件、图片、视频等)将均衡等散乱的细节包含在个库里面,从而使程序员将注意
达到4ZB。在数据量急刷爆发的同时,如何能更高效、更深入力可以集中在如何表达所要执行的运算中,而无需考虑到运
地利用这些数据,是数据挖掘技术所而临的新一轮挑战。由此算过程中所涉及的每个细节。
也产生了许多并行编程语言及模型,如PARI.OG及信息传递
Mapreduee使用Map和 Rcducc两个函数来表达整个计
接口( Message Passing Interface,MPl)等,但这些方法并不能将算过程。
个特定的算法显式的表现出来。当前大部分的研究是对某
首先将用户将数据源中的记录(如数据库中的某条记
个特定的传统算法的发展和优化,这些技术已远远不能满足录)转为键值对的形式< in key, in value>,提交给目定义的
现实的数据挖掘要求及分布式技术的发展。2007年,ChuC等Map数,产生一组或多组中问键值对< out kev,
人提出了在多核处理器的讦算机上实现部分数挖掘算法的 intermediate_ value>。然后再把所有拥有相同键的中间键值对
方法四,为分布式系统中的数据挖掘奠定了基础。随着分布式汇总,产生中间键对列表,结束Mup作业,返回。
技术的不断发展、网络数据量爆发式的增长,如何更好地利用
在Map作业执行完毕之后, Reduce函数利用Map的输
分布式系统进行数据挖成了人们迫切的现实需求
出作为输入,把列表中键值对的 valuc值合并在.一起,构造
1分布式编程模型 Mapreduce
个拥有更小 value值的集合。一般情況下,每次调用 Reduce
函数会输出零或?个 value值。中间 value值通过·个迭代器
Mapreduce是在2004年由 Google的 Jeffrey Dean和提供给用户的 Reduee H函数,以避免因太大而无法迺应内存
收稿日期;2014-03-22
稿件编号:201403249
的 value值列表的出现
作者简介:齐浩(1988一),男,内蒙古赤峰人,硕士研究生。研究方向:计算机网络和多媒体通信。