基于云计算平台Hadoop的并行kmeans聚类算法设计研究_(1)1
需积分: 0 72 浏览量
2022-08-04
00:34:15
上传
评论
收藏 320KB PDF 举报
第３８卷第１０期
计算机科学
Ｖ０１．３８
Ｎｏ．１０
２０１１年１０月
Ｃｏｍｐｕｔｅｒ
Ｓｃｉｅｎｃｅ
Ｏｃｔ
２０１ｌ
基于云计算平台Ｈａｄｏｏｐ的并行ｋ－ｍｅａｎｓ
聚类算法设计研究
赵卫中１’４
马慧芳孔４
傅燕翔３ 史忠植４
（湘潭大学信息工程学院
湘潭４１１１０５）１
（西北师范大学数学与信息科学学院
兰州７３００７０）２
（湘潭大学机械工程学院
湘潭４１１１０５）３
（中国科学院计算技术研究所智能信息处理重点实验室北京１００１９０）４
摘要随着数据库技术的发展和Ｉｎｔｅｒｎｅｔ的迅速普及，实际应用中需要处理的数据量急剧地增长，致聚类研究面临
许多新的问题和挑战，如海量数据和新的计算环境等。深入研究了基于云计算平台Ｈａｄｏｏｐ的并行ｋ－ｍｅａｎｓ聚类算
法，给出了算法设计的方法和策略。在多个不同大小数据集上的实验表明，设计的并行聚类算法具有优良的加速比、
扩展率和数据伸缩率等性能，适合用于海量数据的分析和挖掘。
关键词云计算，Ｈａｄｏｏｐ平台，并行ｂｍｅａｎｓ，ＭａｐＲｅｄｕｃｅ
Ｒｅｓｅａｒｃｈ
ｏｎ
Ｐａｒａｌｌｅｌ
ｋ－ｍｅａｎｓ
Ａｌｇｏｒｉｔｈｍ
Ｄｅｓｉｇｎ
Ｂａｓｅｄ
ｏｎ
Ｈａｄｏｏｐ
Ｐｌａｔｆｏｒｍ
ＺＨＡＯ
Ｗｅｉ－ｚｈｏｎｇａ’４
ＭＡ
Ｈｕｉ—ｆａｎｇ’４
ＦＵ
Ｙａｎ－ｘｉａｎｇ
ＳＨＩ
Ｚｈｏｎｇ－ｚｈｉ４
（Ｃｏｌｌｅｇｅ
ｏｆ
Ｉｎｆｏｒｍａｔｉｏｎ
Ｅｎｇｉｎｅｅｒｉｎｇ。ｘｉａｎｇｔａｎ
Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｎｇｔａｎ
４１１１０５，Ｃｈｉｎａ）１
（Ｃｏｌｌｅｇｅ
ｏｆ
Ｍａｔｈｅｍａｔｉｃｓ
ａｎｄ
Ｉｎｆｏｒｍａｔｉｏｎ．Ｎｏｒｔｈｗｅｓｔ
Ｎｏｒｍａｌ
Ｕｎｉｖｅｒｓｉｔｙ。Ｌａｎｚｈｏｕ
７３００７０。Ｃｈｉｎａ）２
（Ｃｏｌｌｅｇｅ
ｏｆ
Ｍｅｃｈａｎｉｃａｌ
Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉａｎｇｔａｎ
Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｎｇｔａｎ
４１１１０５，Ｃｈｉｎａ）３
（Ｋｅｙ
Ｌａｂｏｒａｔｏｒｙ
ｏｆ
Ｉｎｔｅｌｌｉｇｅｎｔ
Ｉｎｆｏｒｍａｔｉｏｎ
Ｐｒｏｃｅｓｓｉｎｇ，Ｉｎｓｔｉｔｕｔｅ
ｏｆ
Ｃｏｍｐｕｔｉｎｇ
Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｉｎｅｓｅ
Ａｃａｄｅｍｙ
ｏｆ
Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ
１００１９０，Ｃｈｉｎａ）４
Ａｂｓｔｒａｃｔ
Ｉｎ
ｔｈｅ
ｐａｓｔ
ｄｅｃａｄｅｓ，ｄａｔａ
ｃｌｕｓｔｅｒｉｎｇ
ｈａｓ ｂｅｅｎ
Ｓｔｕｄｉｅｄ
ｅｘｔｅｎｓｉｖｅｌｙ
ａｎｄ
ａ
ＩＴｉａｓｓ
ｏｆ
ｍｅｔｈｏｄｓ
ａｎｄ
ｔｈｅｏｒｉｅｓ
ｈａｖｅ
ｂｅｅｎ
ａｃｈｉｅｖｅｄ．Ｈｏｗｅｖｅｒ，ｗｉｔｈ
ｔｈｅ
ｄｅｖｅｌｏｐｍｅｎｔ
ｏｆ
ｄａｔａｂａｓｅ
ａｎｄ
ｐｏｐｕｌａｒｉｔｙ
ｏｆ
Ｉｎｔｅｒａｃｔ，ａ ｌｏｔ
ｏｆ
ｎｅｗ
ｃｈａｌｌｅｎｇｅｓ
ｓｕｃｈ
ａｓ
ｍａｓｓｉｖｅ
ｄａｔａ
ａｎｄ
ｎｅｗ
ｃｏｍｐｕｔｉｎｇ
ｅｎｖｉｒｏｎｍｅｎｔ
ｌｉｅ
ｉｎ
ｔｈｅ
ｒｅｓｅａｒｃｈ
ｏｎ
ｄａｔａ
ｃｌｕｓｔｅｒｉｎｇ．Ｗｅ
ｃｏｎｄｕｃｔｅｄ
ａ
ｄｅｅｐ
ｒｅｓｅａｒｃｈ
ｏｎ
ｐａｒａｌｌｅｌ
ｋ－ｍｅａｎｓ
ａｌｇｏｒｉｔｈｍ
ｂａｓｅｄ
ｏｎ
Ｈａｄｏｏｐ．ｗｈｉｃｈ
ｉｓ
ａ
ｎｅｗ
ｃｌｏｕｄ
ｃｏｍｐｕｔｉｎｇ
ｐｌａｔｆｏｒｍ．Ｗｅ
ｓｈｏｗｅｄ
ｈｏｗ
ｔ０
ｄｅｓｉｇｎ
ｐａｒａｌ—
ｌｅｌ
ｋ－ｍｅａｎｓ
ａｌｇｏｒｉｔｈｍｓ
ｏｎ
Ｈａｄｏｏｐ．Ｅｘｐｅｒｉｍｅｎｔｓ
ｏｎ
ｄｉｆｆｅｒｅｎｔ
ｓｉｚｅ
ｏｆ
ｄａｔａｓｅｔｓ
ｄｅｍｏｎｓｔｒａｔｅ
ｔｈａｔ
ｏｕｒ
ｐｒｏｐｏｓｅｄ
ａｌｇｏｒｉｔｈｍ
ｓｈｏｗｓ
ｇｏｏｄ
ｐｅｒｆｏｒｍａｎｃｅ
ｏｎ
ｓｐｅｅｄｕｐ，ｓｃａｌｅｕｐ
ａｎｄ
ｓｉｚｅｕｐ．Ｔｈｕｓ
ｉｔ
ｆｉｔｓ
ｔＯ
ｄａｔａ
ｃｌｕｓｔｅｒｉｎｇ
ｏｎ
ｈｕｇｅ
ｄａｔａｓｅｔｓ．
Ｋ．鄂腻Ｃｌｏｕｄ
ｃｏｍｐｕｔｉｎｇ，Ｈａｄｏｏｐ，Ｐａｒａｌｌｅｌ
ｋ－ｍｅａｎｓ，ＭａｐＲｅｄｕｃｅ
１
引言
聚类是数据挖掘中重要的研究课题之一。所谓聚类。就
是将物理或抽象对象的集合组成为由类似的对象组成的多个
类或簇的过程。由聚类生成的簇是一组数据对象的集合，同
一簇中的对象尽可能相似，而不同簇中的对象尽可能相异［Ｊ］。
随着数据库技术的成熟和数据应用的普及，商业、企业、科研
机构或者政府部门都积累了大量的、以不同形式存储的数据。
如何存储、处理这些海量数据，以及迸一步从中挖掘出有用
的、可以指导应用的知识，成为～个棘手的问题。在面对海量
数据时，现有的聚类算法在时间复杂性和空间复杂性上遇到
了瓶颈，这也是聚类算法研究领域中亟需解决的问题之一。
解决该问题的一个思路就是将并行处理技术应用到聚类中，
设计出高效的并行聚类算法，来提高聚类算法处理海量数据
时的性能。
云计算作为一种新兴的商业计算模型得到了人们的广泛
关注［２－５］。Ｈａｄｏｏｐ是一个可以更容易开发和并行处理大规模
数据的云计算平台，它的主要特点包括扩容能力强、成本低、
效率高以及可靠性好等。Ｈａｄｏｏｐ平台由两部分组成：Ｈａ—
ｄｏｏｐ分布式文件系统（ＨＤＦｓ）［６ｊ和ＭａｐＲｅｄｕｃｅ计算模型”］。
ＨＤＦＳ采用Ｍ／Ｓ架构，一个ＨＤＦＳ集群是由一个管理节
点（Ｎａｍｅｎｏｄｅ）和一定数目的数据节点（Ｄａｔａｎｏｄｅ）组成，每个
节点均是一台普通ＰＣ。在使用上，ＨＤＦＳ与单机上的文件系
统非常类似，同样可以建目录，创建、复制、删除文件，查看文
件内容等。但其底层实现上是把文件切割成块，然后这些块
分散地存储于不同的数据节点上。每个块还可以复制若干
到稿日期：２０１０－１１－０１返修日期：２０１１－０３—２１
本文受国家自然科学基金（６０９３３００４，６０９７５０３９。６１０７２０８５）．国家９７３项目（２００７ＣＢ３１１００４），
西北师范大学青年教师科研能力提升计划骨干项目（ＮＷＮＵ—ＬＫＱＮ一１０－１），湘潭大学博士启动基金（１０ＱＤＺ４２），湖南省教育厅一般项目
（０９Ｃ９６７）资助．
赵卫中（１９８１－－），男．博士，讲师，主要研究领域为机器学习、数据挖掘、算法分析与设计。Ｅ－ｍａｉｌ：ｚｈａｏｗｅｉｚｈｏｎｇ＠ｇｎｍｉＬ
ｔｏｍ；马慧芳（１９８１一）。
女，博士，副教授，主要研究领域为机器学习、数据挖掘；傅燕ｍ（１９７９－），女，讲师，主要研究领域为人机界面交互；史蒯［（１９４１－－），男，研究员，
博士生导师，主要研究领域为人工智能、机器学习、神经计算、认知科学。
·
１６６·
万方数据
评论0
最新资源