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