第36卷第10期 北京科技大学学报 Vol.36 No.10 2014年10月 Journal of University of Science and Technology Beijing 0ct.2014 基于MapReduce的大规模文本聚类并行化 武森，冯小东，杨杰，张晓楠 北京科技大学东凌经济管理学院，北京100083 ☒通信作者，E-mail:wusen@manage.ustb.cdu.cn 摘要建立快速有效的针对大规模文本数据的聚类分析方法是当前数据挖掘研究和应用领域中的一个热点问题.为了同 时保证聚类效果和提高聚类效率，提出基于“互为最小相似度文本对”搜索的文本聚类算法及分布式并行计算模型.首先利 用向量空间模型提出一种文本相似度计算方法：其次，基于“互为最小相似度文本对”搜索选择二分簇中心，提出通过一次划 分实现簇质心寻优的二分K-means聚类算法；最后，基于MapReduce框架设计面向云计算应用的大规模文本并行聚类模型. 在Hadoop平台上运用真实文本数据的实验表明：提出的聚类算法与原始二分K-means相比，在获得相当聚类效果的同时，具 有明显效率优势：并行聚类模型在不同数据规模和计算节点数目上具有良好的扩展性. 关键词云计算：文本：聚类；相似度 分类号TP391 Parallel clustering of very large document datasets with MapReduce WU Sen,FENG Xiao-dong,YANG Jie,ZHANG Xiao-nan Dongling School of Economics and Management,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:usen@manage.ustb.edu.cn ABSTRACT To develop fast and efficient methods to cluster mass document data is one of the hot issues of current data mining research and applications.In order to ensure the clustering result and simultaneously improve the clustering efficiency,a document clustering algorithm was proposed based on searching a document pair with minimum similarity for each other and its distributed parallel computing models were provided.Firstly a document similarity measure was presented using a vector space model (VSM);then bisec- ting clustering was raised combining the bisecting K-means and the proposed initial cluster center selection approach to find the optimized cluster centroids by once partitioning:finally a distributed parallel document clustering model was designed for cloud compu- ting based on MapReduce framework.Experiments on Hadoop platform,using real document datasets,showed the obvious efficiency advantages of the novel document clustering algorithm compared to the original bisecting K-means with an equivalent clustering result, and the scalability of parallel clustering with different data sizes and different computation node numbers was also evaluated. KEY WORDS cloud computing:documents:clustering:similarity 文本挖掘是数据挖掘在文本类型数据上扩展的 数据的快速增长和商业分析的迫切需求，使得文本 研究，是以文本数据作为研究对象，利用数据挖掘相 挖掘的重要性和紧迫性也日益增强，其中在不需要 关方法，从中寻找文本信息的结构、模型、模式等隐 训练集和预定义类别的情况下，从给定的文本集合 含的具有潜在价值的知识的过程，结合了数据挖掘、 中找到合理的文本簇划分的文本聚类研究是文本挖 机器学习、自然语言处理、信息检索和知识管理等不 掘领域的一个重要研究方向 同领域的研究成果口.以互联网应用为载体的文本 随着互联网各种应用（微博、电子商务和搜索 收稿日期：201309-30 基金项目：国家自然科学基金资助项目(71271027)：高等学校博士学科点专项科研基金资助项目(20120006110037)：中央高校基本科研业务 费专项资金资助项目(FRF-TP-10-OO6B) DOI:10.13374/j.issn1001-053x.2014.10.019:http://journals.ustb.edu.cn第 36 卷 第 10 期 2014 年 10 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 10 Oct． 2014 基于 MapＲeduce 的大规模文本聚类并行化 武 森，冯小东，杨 杰，张晓楠 北京科技大学东凌经济管理学院，北京 100083  通信作者，E-mail: wusen@ manage． ustb． edu． cn 摘 要 建立快速有效的针对大规模文本数据的聚类分析方法是当前数据挖掘研究和应用领域中的一个热点问题． 为了同 时保证聚类效果和提高聚类效率，提出基于“互为最小相似度文本对”搜索的文本聚类算法及分布式并行计算模型． 首先利 用向量空间模型提出一种文本相似度计算方法; 其次，基于“互为最小相似度文本对”搜索选择二分簇中心，提出通过一次划 分实现簇质心寻优的二分 K-means 聚类算法; 最后，基于 MapＲeduce 框架设计面向云计算应用的大规模文本并行聚类模型． 在 Hadoop 平台上运用真实文本数据的实验表明: 提出的聚类算法与原始二分 K-means 相比，在获得相当聚类效果的同时，具 有明显效率优势; 并行聚类模型在不同数据规模和计算节点数目上具有良好的扩展性． 关键词 云计算; 文本; 聚类; 相似度 分类号 TP 391 Parallel clustering of very large document datasets with MapＲeduce WU Sen ，FENG Xiao-dong，YANG Jie，ZHANG Xiao-nan Dongling School of Economics and Management，University of Science and Technology Beijing，Beijing 100083，China  Corresponding author，E-mail: usen@ manage． ustb． edu． cn ABSTＲACT To develop fast and efficient methods to cluster mass document data is one of the hot issues of current data mining research and applications． In order to ensure the clustering result and simultaneously improve the clustering efficiency，a document clustering algorithm was proposed based on searching a document pair with minimum similarity for each other and its distributed parallel computing models were provided． Firstly a document similarity measure was presented using a vector space model ( VSM) ; then bisec￾ting clustering was raised combining the bisecting K-means and the proposed initial cluster center selection approach to find the optimized cluster centroids by once partitioning; finally a distributed parallel document clustering model was designed for cloud compu￾ting based on MapＲeduce framework． Experiments on Hadoop platform，using real document datasets，showed the obvious efficiency advantages of the novel document clustering algorithm compared to the original bisecting K-means with an equivalent clustering result， and the scalability of parallel clustering with different data sizes and different computation node numbers was also evaluated． KEY WOＲDS cloud computing; documents; clustering; similarity 收稿日期: 2013--09--30 基金项目: 国家自然科学基金资助项目( 71271027) ; 高等学校博士学科点专项科研基金资助项目( 20120006110037) ; 中央高校基本科研业务 费专项资金资助项目( FＲF--TP--10--006B) DOI: 10． 13374 /j． issn1001--053x． 2014． 10． 019; http: / /journals． ustb． edu． cn 文本挖掘是数据挖掘在文本类型数据上扩展的 研究，是以文本数据作为研究对象，利用数据挖掘相 关方法，从中寻找文本信息的结构、模型、模式等隐 含的具有潜在价值的知识的过程，结合了数据挖掘、 机器学习、自然语言处理、信息检索和知识管理等不 同领域的研究成果［1］． 以互联网应用为载体的文本 数据的快速增长和商业分析的迫切需求，使得文本 挖掘的重要性和紧迫性也日益增强，其中在不需要 训练集和预定义类别的情况下，从给定的文本集合 中找到合理的文本簇划分的文本聚类研究是文本挖 掘领域的一个重要研究方向． 随着互联网各种应用( 微博、电子商务和搜索