互联网文本数据量的激增使得对其作聚类运算的处理时间显著加长,虽有研究者利用Hadoop架构进行了k-means并行化研究,但由于很难有效满足k-means需要频繁迭代的特点,因此执行效率仍然不能让人满意。该文研究提出了基于新一代并行计算系统Spark的k-means文本聚类并行化算法,利用RDD编程模型充分满足了k-means频繁迭代运算的需求。实验结果表明,针对同一聚类文本大数据集和同样的计算环境,基于Spark的k-means文本聚类并行算法在加速比、扩展性等主要性能指标上明显优于基于Hadoop的实现,因此能更好地满足大规模文本数据挖掘算法的需求。
Abstract
Due to sharp increase of internet texts, the processing of k-means on such data is incredibly lengthened. Some classic parallel architectures, such as Hadoop, have not improved the execution efficiency of K-means, because the frequent iteration in such algorithms is hard to be efficiently handled. This paper proposed a parallelization algorithm of k-means based on Spark. It makes full use of in-memory-computing RDD model of Spark so as to well meet the frequent iteration requirement of k-means. Experimental results show that k-means executes much more efficiently in Spark than in Hadoop on the same datasets and the same computing environments.
关键词
k-means /
并行化 /
文本聚类 /
Spark /
RDD /
Hadoop /
MapReduce
{{custom_keyword}} /
Key words
k-means /
parallelization /
text clustering /
Spark /
RDD /
Hadoop /
MapReduce
{{custom_keyword}} /
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] 何婷婷,戴文华,焦翠珍.基于混合并行遗传算法的文本聚类研究[J].中文信息学报, 2007,21(4): 55-60.
[2] 陈德华, 韩忠明, 乐嘉锦.基于XML文档相似性的构件聚类分析[J].计算机工程与设计, 2009,30(2): 507-510.
[3] 袁冬.基于海量文本的语义构建方法研究[D].中国海洋大学博士学位论文,2012.
[4] 石晶,胡明, 戴国忠.基于小世界模型的中文文本主题分析[J].中文信息学报,2007,21(3): 69-74.
[5] Quinn M J, 奎因, 文光, 等. MPI与OpenMP并行程序设计: C语言版[M]. 清华大学出版社, 2004.
[6] 赵念强, 鞠时光. 网格计算及网格体系结构研究综述[J]. 计算机工程与设计, 2006, 27(5): 728-730.
[7] 陈康, 郑纬民. 云计算: 系统实例与研究现状[J]. Journal of Software, 2009, 20(5): 1337-1348.
[8] Dean J, Ghemawat S. MapReduce: simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.
[9] 王凯. MapReduce集群多用户作业调度方法的研究与实现 [D]. 国防科学技术大学硕士学位论文, 2010.
[10] 刘鹏. 实战 Hadoop: 开启通向云计算的捷径[M]. 北京: 电子工业出版社, 2011.
[11] 李建江, 崔健, 王聃, 等. MapReduce并行编程模型研究综述[J]. 电子学报, 2012, 39(11): 2635-2642.
[12] Srirama S N, Batrashev O, Jakovits P, et al. Scalability of parallel scientific applications on the cloud[J]. Scientific Programming, 2011, 19(2): 91-105.
[13] Fox G C. Data intensive applications on clouds[C]//Proceedings of the 2nd International Workshop on Data Intensive Computing in the Clouds. ACM, 2011: 1-2.
[14] Zaharia M, Chowdhury M, Franklin M J, et al. Spark: cluster computing with working sets[C]//Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing.2010: 10-10.
[15] 黄昌宁, 赵海.中文分词十年回顾[J].中文信息学报, 2007,21(3): 8-19.
[16] G. Salton, et al.. Vector-space model for automatic indexing [J]. Communications of the Acm, 1975(18): 613-620.
[17] 徐建民,王金化,马伟瑜.利用本体关联度改进的TF-IDF特征词提取方法[J].情报科学,2011,29(2): 279-283.
[18] 黄承慧,印鉴,侯昉. 一种结合词项语义信息和TF-IDF方法的文本相似度量方法[J].计算机学报,2011,34(5): 856-864.
[19] 韩晓红, 胡彧. K-means 聚类算法的研究[J]. 太原理工大学学报, 2009,(3): 236-239.
[20] 江小平, 李成华, 向文, 等. K-means聚类算法的MapReduce并行化实现[J]. 华中科技大学学报(自然科学版), 2011, 39(1): 120-124.
[21] 滕家雨. 云框架下的文本挖掘算法并行化研究[D].中国矿业大学硕士学位论文, 2015.
[22] Zaharia M, Chowdhury M, Das T, et al. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[C]//Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation. USENIX Association, 2012: 2-2.
[23] Apache Spark. Spark [EB/OL]. http://spark.incubator.apache.org.html,2014-02-10.
[24] Scala programming language [EB/OL]. http://www.scala-lang.org, 2014.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(41302203)
{{custom_fund}}
PDF(3722 KB)
