第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 bisecting 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 computing 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］． 以互联网应用为载体的文本 数据的快速增长和商业分析的迫切需求，使得文本 挖掘的重要性和紧迫性也日益增强，其中在不需要 训练集和预定义类别的情况下，从给定的文本集合 中找到合理的文本簇划分的文本聚类研究是文本挖 掘领域的一个重要研究方向． 随着互联网各种应用( 微博、电子商务和搜索
·1412 北京科技大学学报 第36卷 引擎)的大规模发展，如何快速有效地挖掘应用产 目前的文本聚类算法主要扩展传统的聚类算法，根 生的大规模文本己成为数据挖掘研究和应用领域所 据采用的聚类算法的不同可分为划分文本聚类算法 面临的一个巨大挑战.分布式并行计算在面对大规 和层次文本聚类算法.其中，最常用划分聚类算法 模数据时计算能力强大且实现简单方便，因此将分 是基于余弦相似度扩展经典K-means聚类算法n 布式并行计算引入文本挖掘领域所产生的分布式文 (称为球面K-means聚类，Spherical K-means)).在此 本挖掘技术是近年来的研究热点.云计算的兴起为 基础上，为了克服K-means算法本身局限的文本聚 分布式并行计算提供了更多的框架，其中Google提 类研究有：K-means++d通过一个特定的基于概 出的MapReduce框架回允许用户通过定义Map和 率的中心点初始化选择策略，能以(ogk)的算法复 Reduce任务将大规模数据计算任务分配到多个计 杂性，取得与经过优化的K-means接近的聚类结果； 算节点上而获得计算效率的提高，面向云计算的开 基于文本最小相似度的中心选取方法的选择相似 源Hadoop平台的出现更是为基于MapReduce的分 度最小的两个文本分别作为初始的两个中心，然后 布式并行计算模型实现提供了便利，并且有学者开 依次选择到已知中心相似度最小的样本作为其他类 发了针对机器学习和数据挖掘算法的Mahout类库. 的中心：在线球面K-means通过使用竞争学习技 本文面向云计算平台上的大规模文本挖掘应 术加速聚类算法的速度，获得与球面K-means接近 用，研究文本聚类方法及其并行化计算模型，提出了 甚至更好的结果：对于线性不可分数据，基于该方法 高效的文本聚类算法，并针对该算法设计了在 的K-means算法m利用该函数将原始的特征空间 MapReduce框架下的分布式并行计算模型，运用 映射到一个高维的线性可分空间进行聚类：基于自 Hadoop平台实现并行聚类框架并验证算法的性能. 组织映射的文本聚类算法阁将文本映射到二维的 平面上，以图的方式展示不同文本之间的关系.受 相关研究分析 划分聚类算法本身限制，该类文本聚类方法产生的 文本聚类指根据文本内容的相关性对整个文本 聚类结果不稳定且受噪声数据影响较大. 集合进行簇划分的过程，其中的重要问题包括文本 在层次文本聚类研究方面，文献9]最早在文 表示模型建立、文本相似度衡量及文本聚类过程. 本聚类中利用凝聚层次聚类方法，然而不同的凝聚 首先，文本挖掘算法不能直接对原始文本形式 层次聚类在计算类别间相似度时采用不同的策略， 进行处理，需要将非结构化文本信息转化为计算机 代表性的算法有单连通，完全连通，类间平均连通 识别的结构化模型，即建立文本结构表示模型.文 等，其中UPGMA20)(unweighted pair grouping method 本挖掘中常用文本表示模型包括向量空间模型 wit山h arithmetic-mean)被认为是效果比较好的层次聚 (vector space model,VSM))、语义模型(semantic 类算法.此后有不同学者四对比研究了不同层次 indexing)、本体模型(ontology model)B-6和后缀 聚类方法在文本聚类中的表现，均表明UPGMA层 树模型(suffix tree model).其中，向量空间模 次聚类算法可得到相对较好的文本聚类效果.但 型圆是当前信息检索领域最常用的文本特征表示 是，单独的层次聚类算法在进行文本合并或分裂之 模型，广泛应用在以商业搜索引擎领域为代表的文 后，无法进行调整，使两个较相似的文档容易被划分 本挖掘研究和应，用中 到不同的文本簇中，结合划分聚类多次迭代寻优和 在文本表示模型基础上，聚类算法根据文本对 层次聚类结果稳定的特点，二分K-means聚类 象之间的相似性将文本聚集成簇，因此文本之间的 (bisecting K-means))不断分裂一个选定的簇直到 相似程度的衡量是文本聚类研究的关键内容.目 簇的数目达到指定的数目，然后将每个簇的质心作 前，文本聚类中普遍采用的相似性衡量方法包括基 为K-means算法的初始类中心再次进行聚类，获得 于向量空间的相似度计算回（欧式距离、曼哈顿距 了比K-means、UPGMA及其他凝聚层次聚类更好的 离、明考斯基距离、余弦相似度等)、基于短语的相 文本聚类效果，是目前较可靠的文本聚类算法.但 似度计算@和基于本体的相似度计算.其中，源 是，二分K-means聚类方法由于随机选择初始二分 于几何空间中的向量内积思想的余弦相似度方 簇中心，因此需要多次迭代划分寻找最优簇质心 法☒计算效率较高，且能较准确地衡量文本之间的 (簇质心和二分簇中心分别表示簇本身的平均文本 相似程度，广泛应用在各种文本聚类及其他文本挖 中心及对该簇进行二分K-means聚类时的初始聚类 掘过程中 中心)，增加了计算时间复杂度.因此，可以考虑如 文本聚类算法是形成文本簇划分的重要步骤， 何通过一次迭代划分提高二分K-means的聚类
北 京 科 技 大 学 学 报 第 36 卷 引擎) 的大规模发展，如何快速有效地挖掘应用产 生的大规模文本已成为数据挖掘研究和应用领域所 面临的一个巨大挑战． 分布式并行计算在面对大规 模数据时计算能力强大且实现简单方便，因此将分 布式并行计算引入文本挖掘领域所产生的分布式文 本挖掘技术是近年来的研究热点． 云计算的兴起为 分布式并行计算提供了更多的框架，其中 Google 提 出的 MapＲeduce 框架［2］允许用户通过定义 Map 和 Ｒeduce 任务将大规模数据计算任务分配到多个计 算节点上而获得计算效率的提高，面向云计算的开 源 Hadoop 平台的出现更是为基于 MapＲeduce 的分 布式并行计算模型实现提供了便利，并且有学者开 发了针对机器学习和数据挖掘算法的 Mahout 类库． 本文面向云计算平台上的大规模文本挖掘应 用，研究文本聚类方法及其并行化计算模型，提出了 高效的文本聚类算法，并针对该算法设计了在 MapＲeduce框架下的分布式并行计算模型，运 用 Hadoop平台实现并行聚类框架并验证算法的性能． 1 相关研究分析 文本聚类指根据文本内容的相关性对整个文本 集合进行簇划分的过程，其中的重要问题包括文本 表示模型建立、文本相似度衡量及文本聚类过程． 首先，文本挖掘算法不能直接对原始文本形式 进行处理，需要将非结构化文本信息转化为计算机 识别的结构化模型，即建立文本结构表示模型． 文 本挖掘中常用文本表示模型包括向量空间模型 ( vector space model，VSM) ［3］、语义模型( semantic indexing) ［4］、本体模型( ontology model) ［5--6］和后缀 树模 型［7］ ( suffix tree model) ． 其 中，向 量 空 间 模 型［8］是当前信息检索领域最常用的文本特征表示 模型，广泛应用在以商业搜索引擎领域为代表的文 本挖掘研究和应用中． 在文本表示模型基础上，聚类算法根据文本对 象之间的相似性将文本聚集成簇，因此文本之间的 相似程度的衡量是文本聚类研究的关键内容． 目 前，文本聚类中普遍采用的相似性衡量方法包括基 于向量空间的相似度计算［9］( 欧式距离、曼哈顿距 离、明考斯基距离、余弦相似度等) 、基于短语的相 似度计算［10］和基于本体的相似度计算［11］． 其中，源 于几何空间中的向量内积思想的余弦相似度方 法［12］计算效率较高，且能较准确地衡量文本之间的 相似程度，广泛应用在各种文本聚类及其他文本挖 掘过程中． 文本聚类算法是形成文本簇划分的重要步骤， 目前的文本聚类算法主要扩展传统的聚类算法，根 据采用的聚类算法的不同可分为划分文本聚类算法 和层次文本聚类算法． 其中，最常用划分聚类算法 是基于余弦相似度扩展经典 K-means 聚类算法［13］ ( 称为球面 K-means 聚类，Spherical K-means) ． 在此 基础上，为了克服 K-means 算法本身局限的文本聚 类研究有: K-means + +［14］通过一个特定的基于概 率的中心点初始化选择策略，能以( logk) 的算法复 杂性，取得与经过优化的 K-means 接近的聚类结果; 基于文本最小相似度的中心选取方法［15］选择相似 度最小的两个文本分别作为初始的两个中心，然后 依次选择到已知中心相似度最小的样本作为其他类 的中心; 在线球面 K-means［16］通过使用竞争学习技 术加速聚类算法的速度，获得与球面 K-means 接近 甚至更好的结果; 对于线性不可分数据，基于该方法 的 K-means 算法［17］利用该函数将原始的特征空间 映射到一个高维的线性可分空间进行聚类; 基于自 组织映射的文本聚类算法［18］将文本映射到二维的 平面上，以图的方式展示不同文本之间的关系． 受 划分聚类算法本身限制，该类文本聚类方法产生的 聚类结果不稳定且受噪声数据影响较大． 在层次文本聚类研究方面，文献［19］最早在文 本聚类中利用凝聚层次聚类方法，然而不同的凝聚 层次聚类在计算类别间相似度时采用不同的策略， 代表性的算法有单连通，完全连通，类间平均连通 等，其中 UPGMA［20］( unweighted pair grouping method with arithmetic-mean) 被认为是效果比较好的层次聚 类算法． 此后有不同学者［21］对比研究了不同层次 聚类方法在文本聚类中的表现，均表明 UPGMA 层 次聚类算法可得到相对较好的文本聚类效果． 但 是，单独的层次聚类算法在进行文本合并或分裂之 后，无法进行调整，使两个较相似的文档容易被划分 到不同的文本簇中． 结合划分聚类多次迭代寻优和 层次 聚 类 结 果 稳 定 的 特 点，二 分 K-means 聚 类 ( bisecting K-means) ［22］不断分裂一个选定的簇直到 簇的数目达到指定的数目，然后将每个簇的质心作 为 K-means 算法的初始类中心再次进行聚类，获得 了比 K-means、UPGMA 及其他凝聚层次聚类更好的 文本聚类效果，是目前较可靠的文本聚类算法． 但 是，二分 K-means 聚类方法由于随机选择初始二分 簇中心，因此需要多次迭代划分寻找最优簇质心 ( 簇质心和二分簇中心分别表示簇本身的平均文本 中心及对该簇进行二分 K-means 聚类时的初始聚类 中心) ，增加了计算时间复杂度． 因此，可以考虑如 何通过 一 次 迭 代 划 分 提 高 二 分 K-means 的 聚 类 · 2141 ·
第10期 武森等：基于MapReduce的大规模文本聚类并行化 ·1413· 效率. 在并行聚类研究方面，MapReduce框架的出现 ",=〔×i通=lg(++1 (1) ni 使得大规模文本数据的并行聚类研究逐渐发展，研 式中，f,指特征词t在文本d,中出现的频率，ng为文 究者基于MapReduce框架进行的并行聚类研究包 本d:中特征词t出现的次数，n:为文本d,含有的所有 括：基于MapReduce的并行K-means聚类；基于 特征词出现的总数：id出指特征词t在整个文本集中 MapReduce的快速K-center和K-median聚类：基 的逆向文档频率，用来衡量特征词的出现范围，N为 于MapReduce的大规模多维数据聚类：基于 文本集合中总文本数量，V表示含有特征词t,的不 MapReduce的分布式文本聚类Pa.这些研究针对不 同文本数量.显然，某个特征词在特定的文档中出 同的聚类算法，通过定义不同的Ma即和Reduce任 现的频率越高，该特征词在区分该文本内容属性方 务实现大规模数据的并行聚类，获得了大规模数据 面的能力越强(T℉)；在文本集中出现的范围越广， 聚类挖掘效率的提高及良好的扩展性 其区分文本内容的属性越低(DF). 本文针对目前具有较好文本聚类效果的二分 定义2文本相似度.给定文本d,d,TA(d:, K-means算法的不足，在保证文本聚类效果的前提 d）={t1,t2,…,tu,…,th}表示d,d所含特征 下，从如何提高二分K-means聚类效率及大规模文 词的并集，h为并集中特征词的数目；TS(d:,d,)= 本挖掘问题入手，对文本聚类算法及其并行化进行 {t1,ta,…,t…,tu}表示d,d所含特征词的交 了研究.首先，利用向量空间模型提出一种文本相 集，l为交集中特征词的数目.文本d,d,在TS中的 似度计算方法.其次，提出了基于“互为最小相似度 每个特征词t4上的相似度sim(d:,d,t)定义为 文本对”搜索算法的初始二分聚类簇中心选择方 sim(dd)=min() (2) 法，并对算法搜索的收敛性进行了证明.然后，结合 max (w,) 二分K-means算法的步骤和思想，给出一次划分实 文本d,d的相似度SM(d,d)定义为 现簇中心寻优的高效二分聚类过程及完整的文本聚 ∑sim(d:,d,tt) 类算法.此外，在针对提高大规模文本聚类的效率 SIM(d.,d)= 一，(3) I TA(d,d)I 方面，本文借鉴基于MapReduce的并行聚类研 即两文本在所有共同特征词上的相似度之和与两文 究-，利用MapReduce框架设计了面向云计算应 本包含的所有特征词的个数之比.式(3)与经典的 用的分布式并行二分K-means文本聚类模型.最 余弦相似度(W:·W/(IW:1*1W1)计算方法相 后，在Hadoop平台的真实数据实验验证了算法在保 比，都首先利用了两个文本所包含的共同特征词计 证聚类效果的前提下相比原始二分K-means算法的 算公式的分子项，其次分母项均利用了除了共同特 效率优势及并行聚类在不同数据规模和计算节点上 征之外其余各自本文的特征词.不同的是，本文提 的扩展性 出的式(3)分别精确地计算了每个共同特征词的相 似程度，而不是在夹角余弦中直接通过向量内积计 2基于初始簇中心的文本聚类算法 算总体相似度. 本文首先采用文本特征表示模型提出了文本相 定义3文本簇相似度均方.包括c个文本的 似度计算模型，并提出了基于“互为最小相似度文 文本簇C={d,d2,…,d,…,d}的簇相似度均方 本对”搜索的初始二分簇中心选择方法，在此基础 MS(C)定义为所有文本与簇质心相似度平方的 上给出结合二分K-means的文本聚类算法 均值： 2.1文本特征表示及相似度模型 ∑sIM(d,d.)2 定义1文本特征表示模型.给定文本集合 MS(C)= (4) nc D={d,d2,,d,…,dw},d代表每个文本向量， 其中，d为簇质心文本特征向量，即d。=(〈t1,w）, 采用向量空间模型可表示为d:=（l1,wa),〈2， 〈t2,02）,…,〈t,0g）,…,〈tm,0em>）, 02〉，…，〈，0g〉，…，〈tm,0m）.其中：T={t1, 2,…,,…,tm}表示文本集中所有文本包含的所 有特征词的集合，W:=(wa,02,…,0…,0m）表 We (5) nc 示文本d,在所有特征词上对应的权重向量.采用 2.2初始二分簇中心选择方法 TFDF计算方法网： 原始的二分K-means方法在选择一个簇进行分
第 10 期 武 森等: 基于 MapＲeduce 的大规模文本聚类并行化 效率． 在并行聚类研究方面，MapＲeduce 框架的出现 使得大规模文本数据的并行聚类研究逐渐发展，研 究者基于 MapＲeduce 框架进行的并行聚类研究包 括: 基于 MapＲeduce 的并行 K-means 聚类［23］; 基于 MapＲeduce 的快速 K-center 和 K-median 聚类［24］; 基 于 MapＲeduce 的 大规模多维数据聚类［25］; 基 于 MapＲeduce的分布式文本聚类［26］． 这些研究针对不 同的聚类算法，通过定义不同的 Map 和 Ｒeduce 任 务实现大规模数据的并行聚类，获得了大规模数据 聚类挖掘效率的提高及良好的扩展性． 本文针对目前具有较好文本聚类效果的二分 K-means 算法的不足，在保证文本聚类效果的前提 下，从如何提高二分 K-means 聚类效率及大规模文 本挖掘问题入手，对文本聚类算法及其并行化进行 了研究． 首先，利用向量空间模型提出一种文本相 似度计算方法． 其次，提出了基于“互为最小相似度 文本对”搜索算法的初始二分聚类簇中心选择方 法，并对算法搜索的收敛性进行了证明． 然后，结合 二分 K-means 算法的步骤和思想，给出一次划分实 现簇中心寻优的高效二分聚类过程及完整的文本聚 类算法． 此外，在针对提高大规模文本聚类的效率 方面，本 文 借 鉴 基 于 MapＲeduce 的 并 行 聚 类 研 究［23--25］，利用 MapＲeduce 框架设计了面向云计算应 用的分布式并行二分 K-means 文本聚类模型． 最 后，在 Hadoop 平台的真实数据实验验证了算法在保 证聚类效果的前提下相比原始二分 K-means 算法的 效率优势及并行聚类在不同数据规模和计算节点上 的扩展性． 2 基于初始簇中心的文本聚类算法 本文首先采用文本特征表示模型提出了文本相 似度计算模型，并提出了基于“互为最小相似度文 本对”搜索的初始二分簇中心选择方法，在此基础 上给出结合二分 K-means 的文本聚类算法． 2. 1 文本特征表示及相似度模型 定义 1 文本特征表示模型． 给定文本集合 D = { d1，d2，…，di，…，dN} ，di代表每个文本向量， 采用向量空间模型可表示为 di = ( ? t1，wi1 ?，? t2， wi2 ?，…，?tj ，wij ?，…，? tm，wim ?) ． 其中: T = { t1， t2，…，tj ，…，tm } 表示文本集中所有文本包含的所 有特征词的集合，Wi = ( wi1，wi2，…，wij，…，wim ) 表 示文本 di 在所有特征词上对应的权重向量． 采用 TF-IDF 计算方法［8］: wij = tfi × idfj = nij ni ·log2 ( N Nj + 1 + 1 ) ． ( 1) 式中，tfij指特征词 tj在文本 di中出现的频率，nij为文 本 di中特征词 tj出现的次数，ni为文本 di含有的所有 特征词出现的总数; idfj指特征词 tj在整个文本集中 的逆向文档频率，用来衡量特征词的出现范围，N 为 文本集合中总文本数量，Nj表示含有特征词 tj的不 同文本数量． 显然，某个特征词在特定的文档中出 现的频率越高，该特征词在区分该文本内容属性方 面的能力越强( TF) ; 在文本集中出现的范围越广， 其区分文本内容的属性越低( IDF) ． 定义 2 文本相似度． 给定文本 di，dj ，TA( di， dj ) = { ta1，ta2，…，tat，…，tah } 表示 di，dj所含特征 词的并集，h 为并集中特征词的数目; TS( di，dj) = { ts1，ts2，…，tsk，…，tsl} 表示 di，dj所含特征词的交 集，l 为交集中特征词的数目． 文本 di，dj在 TS 中的 每个特征词 tsk上的相似度 sim( di，dj ，tsk ) 定义为 sim( di，dj ，tsk ) = min( wisk，wjsk ) max( wisk，wjsk ) ， ( 2) 文本 di，dj的相似度 SIM( di，dj ) 定义为 SIM( di，dj ) = t ∑sk∈TS( di ，dj ) sim( di，dj ，tsk ) | TA( di，dj ) | ， ( 3) 即两文本在所有共同特征词上的相似度之和与两文 本包含的所有特征词的个数之比． 式( 3) 与经典的 余弦相似度( Wi ·Wj / ( | Wi | * | Wj | ) ) 计算方法相 比，都首先利用了两个文本所包含的共同特征词计 算公式的分子项，其次分母项均利用了除了共同特 征之外其余各自本文的特征词． 不同的是，本文提 出的式( 3) 分别精确地计算了每个共同特征词的相 似程度，而不是在夹角余弦中直接通过向量内积计 算总体相似度． 定义 3 文本簇相似度均方． 包括 nC个文本的 文本簇 C = { d1，d2，…，di，…，dnC } 的簇相似度均方 MS( C) 定义为所有文本与簇质心相似度平方的 均值: MS( C) = ∑di∈C SIM( di，de ) 2 nC ． ( 4) 其中，de为簇质心文本特征向量，即 de = ( ?t1，we1 ?， ?t2，we2 ?，…，?tj ，wej ?，…，?tm，wem ?) ， wej = ∑ n i = 1 wij nC ． ( 5) 2. 2 初始二分簇中心选择方法 原始的二分 K-means 方法在选择一个簇进行分 · 3141 ·
·1414 北京科技大学学报 第36卷 裂后，利用K-means思想随机选取初始簇中心进行 文本对” 二分聚类并多次迭代寻找最优划分.本文提出通过 证明：设算法在n步搜索过程中得到的互不相 搜索簇的“互为最小相似度文本对”选择二分聚类 同的文本组成的序列DSd,d2,,d,…,dn〉 的初始二分簇中心，其中簇的“互为最小相似度文 (n≥3)，即d:+1是文本簇C中与d,相似度最小的 本对”定义如下 文本： 定义4互为最小相似度文本对.文本簇C= SIM (d;,d)min (SIM(d,d)}, {d,d2,…,d,…,d}的“互为最小相似度文本 i=1,2,…,n1, 对”定义为簇C中满足如下条件的两个文本d:,d: 相应的相似度值序列记为SS〈31，s2…,s。-1), SIM (d,,d,)min (SIM(d,,d))= 其中s:=SIM(d:,d:+i). min (SIM (d;,d), (6) 因为 即d是文本簇中与d相似度最小的文本，同时d是 SIM (d;,di)min (SIM(d,,d)}, 该簇中与d相似度最小的文本. SIM(dd)=min(sIM(dd)) 本文提出根据搜索簇的“互为最小相似度文本 i=1,2,…,n-2, 对”确定初始二分簇中心，但根据定义4，显然一个 所以SIM(d,d+1)≥SIM(d+1,d+2）,s:≥s+1,即 文本簇中可能含有多于一对满足式(6)的“互为最 S1≥S2≥≥S:≥Si+1≥"≥$m-1 小相似度文本对”.因此，给出簇的“互为最小相似 (1)由算法终止条件知：若3i=1,2,…,n-2, 度文本”搜索的贪心算法如下 使得s:=s:+1,则算法满足终止条件，停止搜索，输出 算法1“互为最小相似度文本对”搜索算法. “互为最小相似度文本对”d,d 输入：文本簇C={d1,d2,…,d,…,dn},nc为 (2)若i=1,2,…,n-2,s:>5+1即s1>52> 文本簇C中文本的数量. …>S:>S:+1>…>5n-2>Sn-1,算法继续第n+1步 输出：“互为最小相似度文本对”d,d 搜索，设搜索到文本簇C中与dn相似度最小的文本 算法步骤： 为d,则SIM(dn-1'dn）≥SlM(dn,d),即sn-1≥sn 步骤1在文本簇C中随机选取文本d,赋给 ①若SIM(dn-1,dn）=SIM(dn,d),算法满足 d,d←d 终止条件，停止搜索，输出“互为最小相似度文本 步骤2在文本簇C中搜索与文本d,相似度最 对”dn-'dn 小的文本d,即 ②若SM(dn-,dn)>SIM(dn,d),则i=1, SIM(dd,)=min (SIM (dd)) 2,…,n,d4≠d.因为： 步骤3在文本簇C中搜索与文本d,相似度最 首先，若3i=1,2,…,n-2,使得d=d,则 小的文本d,即 s:>s-1>SIM (d,,d)=SIM (d;,di)>SIM(d, SIM (d,,d)min {SIM (d,,d,)}. d)SIM(d:,d+i）>SIM(dn,d:),这与“sIM(d:, d:ec 步骤4判断以下两个条件： d:+i)=min{SlM(d,d,)}(d,1是文本簇C中与d 4.1若d4=d或SM(d,d,)=SM(d,d,), 相似度最小的文本)”矛盾： 则算法结束，输出d,d,为“互为最小相似度文本 其次，显然有d≠dn,dn-1… 对”，即文本簇C的初始簇中心； 即d与DS中所有文本均不相同，因此不存在 4.2若d≠d且SIM(d,d,)≠SM(d,d,), 因出现文本序列循环回路而无法终止算法的情况， 则赋值d←d,d,←d,返回步骤3重新搜索 可将新搜索的文本d,加入DS后继续搜索 步骤5结束. 由①和②知在算法第n+1步搜索中，新搜索到 由算法1的步骤可知，搜索文本的过程中可能 的文本d或满足终止条件①，算法搜索结束：或与 会出现循环，即无法收敛得到“互为最小相似度文 已搜索到的长度为n的互不相同文本序列DS中所 本对”的结果.下面通过定理证明算法1的收敛性. 有文本均不为同一文本，可添加到DS中形成长度 定理1算法1的收敛性.经过有限步骤，算法 为n+1的互不相同文本序列继续搜索；最坏的情 1必收敛，即对于任意文本簇C={d,d2,…,d,…, 况，当DS长度达到nc时，由于不存在与DS中所有 dnc},nc≥2，在有限的n步(n≤nc,nc为文本簇C 文本均互不相同的文本，无法满足②，此时必满足终 中文本的数量)之内，总能寻找到“互为最小相似度 止条件①，算法搜索结束
北 京 科 技 大 学 学 报 第 36 卷 裂后，利用 K-means 思想随机选取初始簇中心进行 二分聚类并多次迭代寻找最优划分． 本文提出通过 搜索簇的“互为最小相似度文本对”选择二分聚类 的初始二分簇中心，其中簇的“互为最小相似度文 本对”定义如下． 定义 4 互为最小相似度文本对． 文本簇 C = { d1，d2，…，di，…，dnC } 的“互为最小相似度文本 对”定义为簇 C 中满足如下条件的两个文本 di，dj : SIM( di，dj ) = min dk∈C { SIM( di，dk ) } = min dk∈C { SIM( dj ，dk ) } ， ( 6) 即 di是文本簇中与 dj相似度最小的文本，同时 dj是 该簇中与 di相似度最小的文本． 本文提出根据搜索簇的“互为最小相似度文本 对”确定初始二分簇中心，但根据定义 4，显然一个 文本簇中可能含有多于一对满足式( 6) 的“互为最 小相似度文本对”． 因此，给出簇的“互为最小相似 度文本”搜索的贪心算法如下． 算法 1 “互为最小相似度文本对”搜索算法． 输入: 文本簇 C = { d1，d2，…，di，…，dnC } ，nC为 文本簇 C 中文本的数量． 输出: “互为最小相似度文本对”dx，dy ． 算法步骤: 步骤 1 在文本簇 C 中随机选取文本 di 赋给 dx，dx←di ． 步骤 2 在文本簇 C 中搜索与文本 dx相似度最 小的文本 dy，即 SIM( dx，dy ) = min dj ∈C { SIM( dx，dj ) } ． 步骤 3 在文本簇 C 中搜索与文本 dy相似度最 小的文本 dk，即 SIM( dy，dk ) = min dj ∈C { SIM( dy，dj ) } ． 步骤 4 判断以下两个条件: 4. 1 若 dk = dx或 SIM( dx，dy ) = SIM( dk，dy ) ， 则算法结束，输出 dx，dy 为“互为最小相似度文本 对”，即文本簇 C 的初始簇中心; 4. 2 若 dk≠dx且 SIM( dx，dy ) ≠SIM( dk，dy ) ， 则赋值 dx←dy，dy←dk，返回步骤 3 重新搜索． 步骤 5 结束． 由算法 1 的步骤可知，搜索文本的过程中可能 会出现循环，即无法收敛得到“互为最小相似度文 本对”的结果． 下面通过定理证明算法 1 的收敛性． 定理 1 算法 1 的收敛性． 经过有限步骤，算法 1 必收敛，即对于任意文本簇 C = { d1，d2，…，di，…， dnC } ，nC≥2，在有限的 n 步( n≤nC，nC为文本簇 C 中文本的数量) 之内，总能寻找到“互为最小相似度 文本对”． 证明: 设算法在 n 步搜索过程中得到的互不相 同的文本组成的序列 DS =? d1，d2，…，di，…，dn ? ( n≥3) ，即 di + 1 是文本簇 C 中与 di 相似度最小的 文本: SIM( di，di + 1 ) = min dj ∈C { SIM( dj ，di ) } ， i = 1，2，…，n ’1， 相应的相似度值序列记为 SS =? s1，s2 … ，sn － 1 ?， 其中 si = SIM( di，di + 1 ) ． 因为 SIM( di，di + 1 ) = min dj ∈C { SIM( dj ，di ) } ， SIM( di，di + 2 ) = min dj ∈C { SIM( dj ，di + 1 ) } ， i = 1，2，…，n － 2， 所以 SIM( di，di + 1 ) ≥SIM( di + 1，di + 2 ) ，si≥si + 1，即 s1≥s2≥…≥si≥si + 1≥…≥sn － 1 ． ( 1) 由算法终止条件知: 若i = 1，2，…，n － 2， 使得 si = si + 1，则算法满足终止条件，停止搜索，输出 “互为最小相似度文本对”ds，ds + 1 ． ( 2) 若i = 1，2，…，n － 2，si ＞ si + 1，即 s1 ＞ s2 ＞ … ＞ si ＞ si + 1 ＞ … ＞ sn － 2 ＞ sn － 1，算法继续第 n + 1 步 搜索，设搜索到文本簇 C 中与 dn相似度最小的文本 为 dk，则 SIM( dn － 1，dn ) ≥SIM( dn，dk ) ，即 sn － 1≥sn ． ① 若 SIM( dn － 1，dn ) = SIM( dn，dk ) ，算法满足 终止条件，停止搜索，输出“互为最小相似度文本 对”dn － 1，dn ; ② 若 SIM( dn － 1，dn ) ＞ SIM( dn，dk ) ，则i = 1， 2，…，n，dk≠di ． 因为: 首先，若i = 1，2，…，n － 2，使得 dk = di，则 si ＞ sn － 1 ＞ SIM( dn，dk ) SIM( di，di + 1 ) ＞ SIM( dn， dk ) SIM( di，di + 1 ) ＞ SIM( dn，di ) ，这与“SIM( di， di + 1 ) = min dj ∈C { SIM( dj ，di ) } ( di + 1 是文本簇 C 中与 di 相似度最小的文本) ”矛盾; 其次，显然有 dk≠dn，dn － 1 ． 即 dk与 DS 中所有文本均不相同，因此不存在 因出现文本序列循环回路而无法终止算法的情况， 可将新搜索的文本 dk加入 DS 后继续搜索． 由①和②知在算法第 n + 1 步搜索中，新搜索到 的文本 dk或满足终止条件①，算法搜索结束; 或与 已搜索到的长度为 n 的互不相同文本序列 DS 中所 有文本均不为同一文本，可添加到 DS 中形成长度 为 n + 1 的互不相同文本序列继续搜索; 最坏的情 况，当 DS 长度达到 nC时，由于不存在与 DS 中所有 文本均互不相同的文本，无法满足②，此时必满足终 止条件①，算法搜索结束． · 4141 ·
第10期 武森等：基于MapReduce的大规模文本聚类并行化 ·1415· 综上，算法必在有限的n步(n≤nc,nc为文本 循环需要计算新分裂的两个簇包含的所有文本与相 簇C中文本的数量)之内收敛. 应簇中心的相似度平方，假设每一步划分均匀，则复 证毕 杂度为O(N2):第三步对第一步产生的另一簇分 2.3基于“互为最小相似度文本对”搜索的文本聚 割，复杂度为O(N2),直到第K-1步为(N/2-1) 类算法 或(N2-2).因此，总体复杂度T,≤0(K-1)N), 根据提出的初始簇中心选择方法，结合二分 K为类个数 K-means.算法思想，给出文本聚类算法步骤如下. (2)步骤3中，最差的情况下需要计算任意两 算法2基于“互为最小相似度文本对”搜索的 个文本的相似度，即时间复杂度T2=O(Nm)≤ 文本聚类算法 O(NW),m为搜索次数. 输入：文本集合D={d,d2,…,d,…,d}. (3)步骤4的时间复杂和步骤2类似，需要计 参数：聚类的簇数K 算每次分割簇中所有文本与两个簇中心的相似度， 输出：文本集合D的簇划分S={S1,S2,…, 时间复杂度T3≤0(2(K-1)N),并且步骤4和步骤 S4,…,Sx}; 2都需计算分割簇中所有文本与簇中心的相似度， 算法步骤： 因此只需计算一次存储即可，步骤2和步骤4的总 步骤1初始化.将所有文本组成的集合D作 体时间复杂度T,+T3=T3≤0(2(K-1)N). 为初始簇：S={S,},S。←-D (4)步骤6为标准的K-Means算法，复杂度 步骤2根据式(4)从S中选择文本相似度均 T,=O(tKN),t为迭代次数 方MS最小的簇S作为待分裂簇. 因此整个算法的时间复杂度T≤O(NW)+ 步骤3运用提出的算法1寻找待分裂簇S的 O(2(K-1)N)+O(tKN)≈O(NW),聚类个数K和 初始二分簇中心文本对d,d 迭代次数t均远小于文本总数N.与原始的二分 步骤4将待分类簇的所有文本S.={d1, K-means:算法相比，本文的算法主要通过步骤4提高 dn2,…,d,…,dnm}按照相似度最大原则分配到簇 了效率，原始的算法需要多次迭代进行文本划分，时 S和S中： 间复杂度为T:≤O(2t(K-1)N) rdnm∈Sx,SlM(dm,d）≥sim(dm,d,）; 值得一提的是，文献5]提出的基于最小相似 dS,,SIM (dd)<sim(d'd,) 度的文本聚类中心选取方法和本文提出的根据“互 将S,和S,添加到簇划分S中，并将S.从S中 为最小相似度文本对”选择初始二分聚类簇中心的 删除 过程并不相同.首先，从概念定义上，文献5]定义 步骤5如果S中文本簇个数小于K,返回步骤 的“最小相似度文本”指整个数据中相似度最小的 2:如果S中文本簇个数等于K,转向步骤6 两个文本，本文提出的“互为最小相似度文本对”指 步骤6以S中K个簇的质心为初始簇中心对 某个己经形成的文本簇中互为对方最小相似度的文 所有文本利用球面K-means聚类得到文本簇划分 本对，即文献5]中寻找“最小相似度文本”对应的 S,其中聚类过程中采用定义2的文本相似度计算 文本相似度为整个数据集中任意两个文本相似度的 方法. 最小值：本文中，簇的“互为最小相似度文本”对应 步骤7结束 的相似度不一定是为任意两个文本相似度的最小 由算法2过程可知，本文提出的文本聚类算法 值，即前者为全局最小值，后者为局部极小值.因此 在搜索到初始二分簇中心后一次分配所有对象（步 从搜索的时间复杂度上看，文献5]搜索“最小相 骤4)，得到簇的划分，并无原始二分K-means算法 似度文本”时间复杂度为O(NW)(全局最小，N为文 中重复的迭代寻优过程，因此将有可能提高文本聚 本数)：本文的时间复杂度O(Nm)≤O(NW),m为 类的效率 搜索次数，最差为O(NW).其次，从确定类中心过 2.4算法分析比较 程上，文献15]针对K-means划分聚类寻找初始簇 首先，分析算法2的时间复杂度.具体地，各步 中心的问题，选择相似度最小的两个文本作为其中 的时间复杂度如下 两个初始中心，然后将这两个文本从文本集合中删 (1)步骤2中首先计算每个簇的相似度均方. 除，根据与己确定类中心之间相似度和最小的原则 第一次循环中需计算每个文本与相应簇中心的相似 从其余文本中选择其他类的中心，直到选出指定类 度平方，因此复杂度为O(N),N为文本数：第二次 别数目的中心点个数为止：本文提出的方法是针对
第 10 期 武 森等: 基于 MapＲeduce 的大规模文本聚类并行化 综上，算法必在有限的 n 步( n≤nC，nC为文本 簇 C 中文本的数量) 之内收敛． 证毕． 2. 3 基于“互为最小相似度文本对”搜索的文本聚 类算法 根据提出的初始簇中心选择方法，结合二分 K-means算法思想，给出文本聚类算法步骤如下． 算法 2 基于“互为最小相似度文本对”搜索的 文本聚类算法． 输入: 文本集合 D = { d1，d2，…，di，…，dN} ． 参数: 聚类的簇数 K． 输出: 文本集合 D 的簇划分 S = { S1，S2，…， Sk，…，SK } ; 算法步骤: 步骤 1 初始化． 将所有文本组成的集合 D 作 为初始簇: S = { S0 } ，S0←D． 步骤 2 根据式( 4) 从 S 中选择文本相似度均 方 MS 最小的簇 Sm作为待分裂簇． 步骤 3 运用提出的算法 1 寻找待分裂簇 Sm的 初始二分簇中心文本对 dx，dy ． 步骤 4 将待分类簇的所有文本 Sm = { dm1， dm2，…，dmi，…，dmn } 按照相似度最大原则分配到簇 Sx和 Sy中: dmi∈Sx，SIM( dmi，dx ) ≥sim( dmi，dy ) ; dmi∈Sy，SIM( dmi，dx ) ＜ sim( dmi，dy { ) ． 将 Sx和 Sy 添加到簇划分 S 中，并将 Sm从 S 中 删除． 步骤 5 如果 S 中文本簇个数小于 K，返回步骤 2; 如果 S 中文本簇个数等于 K，转向步骤 6． 步骤 6 以 S 中 K 个簇的质心为初始簇中心对 所有文本利用球面 K-means 聚类得到文本簇划分 S，其中聚类过程中采用定义 2 的文本相似度计算 方法． 步骤 7 结束． 由算法 2 过程可知，本文提出的文本聚类算法 在搜索到初始二分簇中心后一次分配所有对象( 步 骤 4) ，得到簇的划分，并无原始二分 K-means 算法 中重复的迭代寻优过程，因此将有可能提高文本聚 类的效率． 2. 4 算法分析比较 首先，分析算法 2 的时间复杂度． 具体地，各步 的时间复杂度如下． ( 1) 步骤 2 中首先计算每个簇的相似度均方． 第一次循环中需计算每个文本与相应簇中心的相似 度平方，因此复杂度为 O( N) ，N 为文本数; 第二次 循环需要计算新分裂的两个簇包含的所有文本与相 应簇中心的相似度平方，假设每一步划分均匀，则复 杂度为 O( N /2) ; 第三步对第一步产生的另一簇分 割，复杂度为 O( N /2) ，直到第 K － 1 步为( N /2K － 1 ) 或( N /2K － 2 ) ． 因此，总体复杂度 T1≤O( ( K － 1) N) ， K 为类个数． ( 2) 步骤 3 中，最差的情况下需要计算任意两 个文本的 相 似 度，即 时 间 复 杂 度 T2 = O ( Nm) ≤ O( NN) ，m 为搜索次数． ( 3) 步骤 4 的时间复杂和步骤 2 类似，需要计 算每次分割簇中所有文本与两个簇中心的相似度， 时间复杂度 T3≤O( 2( K － 1) N) ，并且步骤 4 和步骤 2 都需计算分割簇中所有文本与簇中心的相似度， 因此只需计算一次存储即可，步骤 2 和步骤 4 的总 体时间复杂度 T1 + T3 = T3≤O( 2( K － 1) N) ． ( 4) 步骤 6 为标准的 K-Means 算法，复杂度 T4 = O( tKN) ，t 为迭代次数． 因此整个算法的时间复杂度 T≤O( NN) + O( 2( K － 1) N) + O( tKN) ≈O( NN) ，聚类个数 K 和 迭代次数 t 均远小于文本总数 N． 与原始的二分 K-means算法相比，本文的算法主要通过步骤 4 提高 了效率，原始的算法需要多次迭代进行文本划分，时 间复杂度为 T'3≤O( 2t( K － 1) N) ． 值得一提的是，文献［15］提出的基于最小相似 度的文本聚类中心选取方法和本文提出的根据“互 为最小相似度文本对”选择初始二分聚类簇中心的 过程并不相同． 首先，从概念定义上，文献［15］定义 的“最小相似度文本”指整个数据中相似度最小的 两个文本，本文提出的“互为最小相似度文本对”指 某个已经形成的文本簇中互为对方最小相似度的文 本对，即文献［15］中寻找“最小相似度文本”对应的 文本相似度为整个数据集中任意两个文本相似度的 最小值; 本文中，簇的“互为最小相似度文本”对应 的相似度不一定是为任意两个文本相似度的最小 值，即前者为全局最小值，后者为局部极小值． 因此 从搜索的时间复杂度上看，文献［15］搜索“最小相 似度文本”时间复杂度为 O( NN) ( 全局最小，N 为文 本数) ; 本文的时间复杂度 O( Nm) ≤O( NN) ，m 为 搜索次数，最差为 O( NN) ． 其次，从确定类中心过 程上，文献［15］针对 K-means 划分聚类寻找初始簇 中心的问题，选择相似度最小的两个文本作为其中 两个初始中心，然后将这两个文本从文本集合中删 除，根据与已确定类中心之间相似度和最小的原则 从其余文本中选择其他类的中心，直到选出指定类 别数目的中心点个数为止; 本文提出的方法是针对 · 5141 ·
·1416· 北京科技大学学报 第36卷 二分K-means随机选择二分簇中心的问题，提出用 Ma即：〈t@d,f〉→t,〈d,tf》 “互为最小相似度文本”作为二分簇中心，因此本文 Reduce:〈t,count(Kd:,f))→〈t,V>, 和文献5]是分别针对不同的聚类策略研究如何 〈@d,f〉→t@d,wg〉 选择初始簇中心的问题 (4)整理获取每个文本的特征表示.以获取的 每个文本d:含有的每个特征词t的TFDF权值 3基于MapReduce的并行文本聚类模型 〈，@d,心；)作为该任务的输入，Ma即将其转换成 尽管改进的算法相比原始二分聚类有可能提高 〈d,〈，w》;Reduce将每个文本d:的所有特征词 聚类效率，但是通过聚类算法本身的改进获得的计 及其权重合并一起，即→(d:,〈，0g》 中的MapReduce框架对文本聚类过程进行并行化 Reduce:〈d:,〈马，wg》→(d,Lit,og》 处理，将进一步大幅提高文本聚类效率 其中，上述四个MapReduce任务中：count表示 在文本聚类过程中，两个重要的步骤分别是文 计数，sum表示求和，Li⊕表示含有某种元素的集 本特征提取和聚类过程.因此，本文分别针对这两 合，下文同理 个步骤设计了并行化的MapReduce任务框架. 3.2基于MapReduce任务的并行文本聚类过程 3.1基于MapReduce任务的并行文本特征提取 在文本聚类过程中，本文设计三个MapReduce 可以通过以下四个MapReduce任务提取每个 任务进行分布式并行计算，负责搜索“互为最小相 文本的特征，即获取每个文本包括的所有特征词及 似度文本对”、分配文本到两个簇及最终的K-means 对应的TFDF权值. 文本聚类过程. (1)统计每个文本中每个特征词出现的次数. (1)根据“互为最小相似度文本对”寻找初始 Map对含有具体内容的每个文本〈d,contedt进行 文本簇中心.Ma即选取一个文本d,根据定义2计 预处理，输出每个文本d,中的每个特征词，且标记 算选定的簇S中其余文本与d的相似度，并搜索与 次数为1，即.MapReduce过程可表示为： d,重新利用Map搜索d的最小相似度文本，直到 Map:〈d,contedt→Kt,@d:,2 找到“互为最小相似度文本对”〈d,d,）,由定理1 Reduce:〈t,@d:,count(1))→Kt@d:,ng〉 可知该过程收敛.MapReduce过程可表示为： (2)统计每个文本中含有的所有特征词的总 Map:〈d.,Lif,og》,〈Snm,List d》→ 数.Map将输入〈t@d,ng)中的文本和特征词分 离，以文本d:为key转换成〈d:,〈t,ng》:Reduce Repeat 统计具有相同key值(d:)的value(ng)进行统计求 Map:〈d,Lift,0,》,〈Sm,Li4dm》→ 和，得到每个文本d:所有特征词出现的总数n:,即 〈d,&d,SM(d,d）〉 〈d,n:》:并根据上一个过程的结果计算每个文本 Reduce:drd,d,←dk d:含有的每个特征词t的频率〈t@d:,ng/n:),即 End until d =dg or SIM (d,d,)=SIM(d,,d,) (t@d,圹).MapReduce过程可表示为： (2)分配待分裂簇中所有文本到两个簇中 Map:〈t@d,ng)→(d:,〈t,ng》 Ma即根据搜索的初始簇中心d,d,按照定义2计 Reduce:〈d:,sum(Kt,ng)))→(d:,n:）, 算簇S中所有文本与簇中心d,d,的相似度，并按 〈t@d,n〉→Kt@d,tf〉 相似度最大原则分配到两个簇S,和S,中，〈S,List (3)统计每个特征词在不同文本中出现的次 〈d:,Litt,w:》(Sk=S或S,).Reduce按照定 数.Map将输入〈t,@d:,f:)中的文本和特征词分 义3计算两个簇的质心向量d和文本相似度均方 离，以特征词t为key转换成，〈d,f》:Reduce MS(S),即.MapReduce过程可 统计每一个特征词在不同文本中出现的总次数 表示为： N,即〈t,N),再读取总文本数V根据式(1)计算每 Map:〈Sm,List d〉，d.,d,〉→Sk,Litd:》 个文本d:含有的每个特征词的TFDF权值0，即 Reduce:〈Sk,Litd:》→(Sk,d4,MS(S)> 〈t,@d,w,>.MapReduce过程可表示为： 上述两个MapReduce任务将重复进行直到簇
北 京 科 技 大 学 学 报 第 36 卷 二分 K-means 随机选择二分簇中心的问题，提出用 “互为最小相似度文本”作为二分簇中心，因此本文 和文献［15］是分别针对不同的聚类策略研究如何 选择初始簇中心的问题． 3 基于 MapＲeduce 的并行文本聚类模型 尽管改进的算法相比原始二分聚类有可能提高 聚类效率，但是通过聚类算法本身的改进获得的计 算效率的提高远无法适应面向云计算实际应用中大 规模海量文本聚类挖掘需要，因此利用云计算环境 中的 MapＲeduce 框架对文本聚类过程进行并行化 处理，将进一步大幅提高文本聚类效率． 在文本聚类过程中，两个重要的步骤分别是文 本特征提取和聚类过程． 因此，本文分别针对这两 个步骤设计了并行化的 MapＲeduce 任务框架． 3. 1 基于 MapＲeduce 任务的并行文本特征提取 可以通过以下四个 MapＲeduce 任务提取每个 文本的特征，即获取每个文本包括的所有特征词及 对应的 TF-IDF 权值． ( 1) 统计每个文本中每个特征词出现的次数． Map 对含有具体内容的每个文本? di，content? 进行 预处理，输出每个文本 di中的每个特征词 tj ，且标记 次数为 1，即?tj @ di，1? ; Ｒeduce 对具有相同 key( 同 一文本 di中的同一特征词 tj : tj@ di ) 的 value 进行统 计求和，即?tj @ di，nij?． MapＲeduce 过程可表示为: Map: ?di，content ? →?tj @ di，1? Ｒeduce: ?tj @ di，count( 1) ?→?tj @ di，nij? ( 2) 统计每个文本中含有的所有特征词的总 数． Map 将输入? tj @ di，nij ? 中的文本和特征词分 离，以文本 di为 key 转换成? di，? tj ，nij ?? ; Ｒeduce 统计具有相同 key 值( di ) 的 value( nij) 进行统计求 和，得到每个文本 di所有特征词出现的总数 ni，即 ?di，ni?; 并根据上一个过程的结果计算每个文本 di含有的每个特征词 tj 的频率? tj @ di，nij / ni ?，即 ?tj @ di，tfij?． MapＲeduce 过程可表示为: Map: ?tj @ di，nij?→?di，?tj ，nij?? Ｒeduce: ? di，sum ( ? tj ，nij ?) ? → ? di，ni ?， ?tj @ di，nij?→?tj @ di，tfij? ( 3) 统计每个特征词在不同文本中出现的次 数． Map 将输入? tj @ di，tfij? 中的文本和特征词分 离，以特征词 tj为 key 转换成?tj ，?di，tfij?? ; Ｒeduce 统计每一个特征词 tj 在不同文本中出现的总次数 Nj ，即?tj ，Nj ?，再读取总文本数 N 根据式( 1) 计算每 个文本 di含有的每个特征词 tj的 TF-IDF 权值 wij，即 ?tj @ di，wij?． MapＲeduce 过程可表示为: Map: ?tj @ di，tfij?→?tj ，?di，tfij?? Ｒeduce: ? tj ，count ( ? di，tfij ?) ? → ? tj ，Nj ?， ?tj @ di，tfij?→?tj @ di，wij? ( 4) 整理获取每个文本的特征表示． 以获取的 每个文本 di 含有的每个特征词 tj 的 TF-IDF 权值 ?tj @ di，wij?作为该任务的输入，Map 将其转换成 ?di，?tj ，wij?? ; Ｒeduce 将每个文本 di的所有特征词 及其权重合并一起，即? di，List? tj ，wij ?? ． MapＲeduce 过程可表示为: Map: ?tj @ di，wij?→?di，?tj ，wij?? Ｒeduce: ?di，?tj ，wij?? →?di，List ? tj ，wij?? 其中，上述四个 MapＲeduce 任务中: count 表示 计数，sum 表示求和，List ?? 表示含有某种元素的集 合，下文同理． 3. 2 基于 MapＲeduce 任务的并行文本聚类过程 在文本聚类过程中，本文设计三个 MapＲeduce 任务进行分布式并行计算，负责搜索“互为最小相 似度文本对”、分配文本到两个簇及最终的 K-means 文本聚类过程． ( 1) 根据“互为最小相似度文本对”寻找初始 文本簇中心． Map 选取一个文本 dx，根据定义 2 计 算选定的簇 Sm中其余文本与 dx的相似度，并搜索与 dx具有最小相似度的文本 dy，并搜索与 dy具有最小 相似度的文本 dk ; Ｒeduce 将 dy赋值给 dx，dk赋值给 dy，重新利用 Map 搜索 dy的最小相似度文本，直到 找到“互为最小相似度文本对”? dx，dy?，由定理 1 可知该过程收敛． MapＲeduce 过程可表示为: Map: ? dx，List? tj ，wxj ?? ，? Sm，List? dmi ?? → ?dx＆dy，SIM( dx，dy ) ? Ｒepeat Map: ?dy，List? tj ，wyj ?? ，? Sm，List? dmi ?? → ?dy＆dk，SIM( dk，dy ) ? Ｒeduce: dx←dy，dy←dk End until dk = dk or SIM( dk，dy ) = SIM( dx，dy ) ( 2) 分配待分裂簇中所有文本到两个簇中． Map 根据搜索的初始簇中心 dx，dy，按照定义 2 计 算簇 Sm中所有文本与簇中心 dx，dy的相似度，并按 相似度最大原则分配到两个簇 Sx和 Sy中，? Sk，List ?di，List ? tj ，wij??? ( Sk = Sx或 Sy ) ． Ｒeduce 按照定 义 3 计算两个簇的质心向量 dek和文本相似度均方 MS( Sk ) ，即?Sk，dek，MS( Sk ) ?． MapＲeduce 过程可 表示为: Map: ?Sm，List ? dmi?，dx，dy?→?Sk，List ? di?? Ｒeduce: ?Sk，List ? di?? →?Sk，dek，MS( Sk ) ? 上述两个 MapＲeduce 任务将重复进行直到簇 · 6141 ·
第10期 武森等：基于MapReduce的大规模文本聚类并行化 ·1417· 的数目为指定的K 20),采用F-measure(F-measure值越高表示聚类 (3)根据K个簇的质心进行K-means聚类. 效果越好)作为文本聚类算法的效果评价指标，并 Map读入所有文本集合D和K个簇的质心向量dt 比较其运行时间，结果如表1所示.本节实验（及后 进行K-means聚类，形成文本簇划分，即〈Sk,List 面的实验)均在Hadoop平台上进行，本实验的聚类 〈da》,该过程需要类似上一个MapReduce任务的 算法均在1个计算节点上运行，其中“二分寻优次 文本分配过程： 数”指BKM算法在每次二分聚类过程中迭代划分 Repeat: 寻优质心的次数，运行时间和F-measure均为10次 Map:D,Litd〉→KS4,Litd》 随机试验的平均值，BKM算法中的文本相似度采用 Reduce:〈S,Litd:》→KS,d,MS(Se)) 经典的余弦相似度方法 Until簇划分不再变化. 表1原始二分K-means和本文提出的算法实验结果对比 4 算法分析 Table 1 Comparison between experiment results of BKM and the pro- posed algorithm 针对提出的文本聚类算法及其并行计算模型， 算法名称 二分寻优次数运行时间/ms F-measure 应用真实的20 newsgroup新闻文本数据集和维基百 5 17801 0.67 科词条数据集在Hadoop平台下进行实验，以验证算 BKM 10 33235 0.74 法的文本聚类性能及并行聚类的扩展性. 15 46393 0.74 4.1实验数据及文本预处理 本文算法 1 1187 0.73 在实验中选取以下两个数据集作为聚类对象： (1)20 newsgroup文本数据集①，该数据集由6个大 从表1可以看出：(1)BKM算法在迭代5次寻 类、20个小类共约20000个新闻文本组成，被广泛 找簇中心时，在计算时间是本文改进算法约15倍的 用于文本挖掘研究中.(2)维基百科词条数据集，采 情况下，F-measure值明显低于本文提出的算法； 集2012年4月10日的包括约400万个英文词条的 (2)迭代次数从5次增长到10次时，BKM算法的聚 数据备份，数据大小约为32GB. 类效果随着迭代次数的增加会获得提高，但从10次 首先，对于上述两个数据集，通过预处理过程将 增长到15次时，并无显著提高，存在聚类效果的瓶 非结构化的文本信息转换成为结构化的文本表示模 颈；(3)本文的改进算法在获得和BKM算法相当 型，实验分析中进行的数据预处理有：(1)提取特征 (略低0.01)的F-measure值的情况下，运行时间远 词，将空格作为特征分割符提取特征词，并删除空格 小于BKM算法.可见，本文提出的文本聚类算法通 紧随的标点，即如果标点后有空格，则删除，标点后 过搜索“互为最小相似度文本对”确定分裂中心后， 无空格，则保留，例如保留www.ustb.edu.cn和 只进行1次划分的过程，减少了重复计算的次数，在 UserlName(@gmail.com中的标点；(2)规范化，将所 运行时间上比原BKM算法具有相对较大优势，并在 有的字母进行小写格式化：(3)长度处理，删除长度 保持与原BKM算法基本相当的聚类效果情况下，大 大于50的生僻词或小于2的无意义特征词：(4)消 大提高了计算效率. 除停用词，按照Google提供的英文停词表，继续删 4.3并行聚类扩展性分析 除对文本挖掘没有意义的特征词：(5)消除数字，删 将提出的基于MapReduce的并行文本聚类模 除文本中的只包含单独数字的词汇特征，而保留部 型应用到维基百科数据集中，分析并行文本聚类算 分含有数字的特征词：(6)提取词干，利用 法的扩展性能.将维基百科数据集切分为1、2、8和 PorterStemmeri词根提取算法m提取特征词的主干； 32GB四个不同大小的数据集进行文本预处理，为 (7)同义词替换，利用WordNet②提供的同义词列表 了分析并行文本聚类算法在不同数据规模和计算节 对同义词进行替换. 点上的扩展性，设计了以下两个实验 4.2文本聚类算法性能分析 实验1选择2、8和32GB三个数据集，在1到 选择20 newsgroup新闻文本数据集验证提出的 文本聚类算法性能，即如何在保证聚类效果的前提 ①数据集可从以下网站下载：htp://people.csail.mit.cdu 下大幅度提高计算效率。对预处理后的 jrennie/20Newsgroups/ 20 newsgroup数据集分别应用二分K-means算法P] ②相关内容数据从以下网站下载：http://wordnet.prince- (记为BKM)和本文提出的改进文本聚类算法(K= ton.edu/wordnet/
第 10 期 武 森等: 基于 MapＲeduce 的大规模文本聚类并行化 的数目为指定的 K． ( 3) 根据 K 个簇的质心进行 K-means 聚类． Map 读入所有文本集合 D 和 K 个簇的质心向量 dek 进行 K-means 聚类，形成文本簇划分，即? Sk，List ?dki?? ，该过程需要类似上一个 MapＲeduce 任务的 文本分配过程: Ｒepeat: Map: D，List ? dek?→?Sk，List ? dki?? Ｒeduce: ?Sk，List ? di?? →?Sk，dek，MS( Sk ) ? Until 簇划分不再变化． 4 算法分析 针对提出的文本聚类算法及其并行计算模型， 应用真实的 20newsgroup 新闻文本数据集和维基百 科词条数据集在 Hadoop 平台下进行实验，以验证算 法的文本聚类性能及并行聚类的扩展性． 4. 1 实验数据及文本预处理 在实验中选取以下两个数据集作为聚类对象: ( 1) 20newsgroup 文本数据集①，该数据集由 6 个大 类、20 个小类共约 20000 个新闻文本组成，被广泛 用于文本挖掘研究中． ( 2) 维基百科词条数据集，采 集 2012 年 4 月 10 日的包括约 400 万个英文词条的 数据备份，数据大小约为 32 GB． 首先，对于上述两个数据集，通过预处理过程将 非结构化的文本信息转换成为结构化的文本表示模 型，实验分析中进行的数据预处理有: ( 1) 提取特征 词，将空格作为特征分割符提取特征词，并删除空格 紧随的标点，即如果标点后有空格，则删除，标点后 无空 格，则 保 留，例 如 保 留 www． ustb． edu． cn 和 UserlName@ gmail． com中的标点; ( 2) 规范化，将所 有的字母进行小写格式化; ( 3) 长度处理，删除长度 大于 50 的生僻词或小于 2 的无意义特征词; ( 4) 消 除停用词，按照 Google 提供的英文停词表，继续删 除对文本挖掘没有意义的特征词; ( 5) 消除数字，删 除文本中的只包含单独数字的词汇特征，而保留部 分含 有 数 字 的 特 征 词; ( 6 ) 提 取 词 干，利 用 PorterStemmer词根提取算法［27］提取特征词的主干; ( 7) 同义词替换，利用 WordNet② 提供的同义词列表 对同义词进行替换． 4. 2 文本聚类算法性能分析 选择 20newsgroup 新闻文本数据集验证提出的 文本聚类算法性能，即如何在保证聚类效果的前提 下大幅度提高计算效率． 对 预 处 理 后 的 20newsgroup 数据集分别应用二分 K-means 算法［21］ ( 记为 BKM) 和本文提出的改进文本聚类算法( K = 20) ，采用 F-measure［28］( F-measure 值越高表示聚类 效果越好) 作为文本聚类算法的效果评价指标，并 比较其运行时间，结果如表 1 所示． 本节实验( 及后 面的实验) 均在 Hadoop 平台上进行，本实验的聚类 算法均在 1 个计算节点上运行，其中“二分寻优次 数”指 BKM 算法在每次二分聚类过程中迭代划分 寻优质心的次数，运行时间和 F-measure 均为 10 次 随机试验的平均值，BKM 算法中的文本相似度采用 经典的余弦相似度方法． 表 1 原始二分 K-means 和本文提出的算法实验结果对比 Table 1 Comparison between experiment results of BKM and the proposed algorithm 算法名称 二分寻优次数 运行时间/ms F-measure 5 17801 0. 67 BKM 10 33235 0. 74 15 46393 0. 74 本文算法 1 1187 0. 73 从表 1 可以看出: ( 1) BKM 算法在迭代 5 次寻 找簇中心时，在计算时间是本文改进算法约 15 倍的 情况下，F-measure 值明显低于本文提出的算法; ( 2) 迭代次数从 5 次增长到 10 次时，BKM 算法的聚 类效果随着迭代次数的增加会获得提高，但从 10 次 增长到 15 次时，并无显著提高，存在聚类效果的瓶 颈; ( 3) 本文的改进算法在获得和 BKM 算法相当 ( 略低 0. 01) 的 F-measure 值的情况下，运行时间远 小于 BKM 算法． 可见，本文提出的文本聚类算法通 过搜索“互为最小相似度文本对”确定分裂中心后， 只进行 1 次划分的过程，减少了重复计算的次数，在 运行时间上比原 BKM 算法具有相对较大优势，并在 保持与原 BKM 算法基本相当的聚类效果情况下，大 大提高了计算效率． 4. 3 并行聚类扩展性分析 将提出的基于 MapＲeduce 的并行文本聚类模 型应用到维基百科数据集中，分析并行文本聚类算 法的扩展性能． 将维基百科数据集切分为 1、2、8 和 32 GB 四个不同大小的数据集进行文本预处理，为 了分析并行文本聚类算法在不同数据规模和计算节 点上的扩展性，设计了以下两个实验． 实验 1 选择 2、8 和 32 GB 三个数据集，在 1 到 · 7141 · ① ② 数据集可从以下网站下载: http: / / people． csail． mit． edu / jrennie /20Newsgroups/ 相关内容数据从以下网站下载: http: / /wordnet． princeton． edu /wordnet /
·1418 北京科技大学学报 第36卷 10个计算节点上分别应用提出的并行文本聚类模 表2不同大小数据集的并行聚类时间对比 型(K=10000),得到并行算法的加速比，如图1所 Table 2 Time comparison of parallel clustering on different sizes of da- tabases 示（其中加速比定义为算法在1个计算节点上运算 时间与使用多个计算节点的并行计算时间之比，图 计算 运行时间/ms 时间比值 中的理想加速比为忽略通信时间的理想线性加 节点数 1GB数据 32GB数据 速比) 1 217048 2824201 13.0119 2 125530 1569016 12.4991 11 10 3 91404 1046031 11.4440 9 4 76824 855821 11.1400 8 5 61512 688833 11.1984 6 49332 543115 11.0094 6 以 7 43185 470722 10.9001 8 39465 421529 10.6811 3 -2GB -8GB 9 35579 376568 10.5840 2 -e-32 GB 10 34452 344415 9.9970 ◆理想加速化 3 4567891011 计算节点数 5 结论 图1并行算法在不同数据规模和计算节点数上的加速比 Fig.I Speed-up ratio of the parallel algorithm on different data 针对面向云计算应用的大规模文本数据聚类挖 scales and node numbers 掘问题，本文在提出高效的文本聚类算法基础上，设 计了基于MapReduce框架的并行文本聚类模型.以 由图1可以看出：随着数据集规模的增加，由于 二分K-means算法为基础，在保证二分K-means本 并行聚类的通信时间在总时间开销中所占的比重大 身较好的文本聚类效果的前提下，试图提高文本聚 大降低，并行算法获得的加速比更加接近线性理想 类效率：提出了基于初始簇中心选择的文本聚类算 加速比；随着节点数的增加，每个计算节点的Ma即 法.算法基于提出并证明收敛的“互为最小相似度 或Reduce计算任务越来越少，通信时间在总时间开 文本对”搜索算法选择初始二分聚类簇中心，克服 销中所占比重增加，使算法执行时间下降减缓并且 了原始二分K-means随机选择初始簇中心导致的需 加速比增长速度逐步放缓.图1通过计算本文提出 要多次迭代寻找最优簇质心带来的计算效率较低问 的基于MapReduce的并行文本聚类算法在不同数 题；并且基于MapReduce框架设计了面向云计算应 据规模和节点数上的加速比反映出了算法的良好扩 用的分布式并行聚类模型.Hadoop平台上运用真 展性，其可运用于大规模数据聚类，通过增加计算节 实应用中的20 newsgroup文本数据集的实验表明， 点数目可以有效地提高文本聚类效率 提出的算法在保证聚类效果的前提下，相比原始二 实验2选择1GB和32GB大小的两个数据 分K-means算法具有效率优势，应用不同规模的维 集，在1到10个计算节点上分别应用提出的并行文 基百科数据集及在不同计算节点数目上的实验验证 本聚类模型(K=10000),得到并行算法的运行时 了基于MapReduce并行聚类算法的良好扩展性.未 间，如表2所示 来的研究可能包括降低聚类中的K-means步骤可能 表2的实验结果表明：随着计算节点数的增 带来的噪声数据对文本聚类结果的影响以及其他大 加，本文提出的基于MapReduce的并行文本算法 规模文本挖掘的并行化问题 在32GB数据集上的运行时间与1GB数据集上的 运行时间比从约13倍不断下降到约10倍，即算法 考文献 处理大数据集的效率随着计算节点的增加越来越 高，因此该并行算法更适合于大规模文本数据的 ] Guan R C,Pei ZL,Shi X H,et al.Weight affinity propagation 并行聚类 and its application to text clustering.J Comput Res Der,2010,47 (10):1733 实验1和实验2共同验证了本文的并行文本聚 (管仁初，裴志利，时小虎，等。权吸引子传播算法及其在文 类算法在大规模数据集和更多计算节点上的扩 本聚类中的应用.计算机研究与发展，2010,47(10)：1733) 展性 Jeffrey D,Sanjay G.MapReduce:simplified data processing on
北 京 科 技 大 学 学 报 第 36 卷 10 个计算节点上分别应用提出的并行文本聚类模 型( K = 10000) ，得到并行算法的加速比，如图 1 所 示( 其中加速比定义为算法在 1 个计算节点上运算 时间与使用多个计算节点的并行计算时间之比，图 中的理想加速比为忽略通信时间的理想线性加 速比) ． 图 1 并行算法在不同数据规模和计算节点数上的加速比 Fig． 1 Speed-up ratio of the parallel algorithm on different data scales and node numbers 由图 1 可以看出: 随着数据集规模的增加，由于 并行聚类的通信时间在总时间开销中所占的比重大 大降低，并行算法获得的加速比更加接近线性理想 加速比; 随着节点数的增加，每个计算节点的 Map 或 Ｒeduce 计算任务越来越少，通信时间在总时间开 销中所占比重增加，使算法执行时间下降减缓并且 加速比增长速度逐步放缓． 图 1 通过计算本文提出 的基于 MapＲeduce 的并行文本聚类算法在不同数 据规模和节点数上的加速比反映出了算法的良好扩 展性，其可运用于大规模数据聚类，通过增加计算节 点数目可以有效地提高文本聚类效率． 实验 2 选择 1 GB 和 32 GB 大小的两个数据 集，在 1 到 10 个计算节点上分别应用提出的并行文 本聚类模型( K = 10000) ，得到并行算法的运行时 间，如表 2 所示． 表 2 的实验结果表明: 随着计算节点数的增 加，本文提出的基于 MapＲeduce 的并行文本算法 在 32 GB 数据集上的运行时间与 1 GB 数据集上的 运行时间比从约 13 倍不断下降到约 10 倍，即算法 处理大数据集的效率随着计算节点的增加越来越 高，因此该并行算法更适合于大规模文本数据的 并行聚类． 实验 1 和实验 2 共同验证了本文的并行文本聚 类算法在大规模数据集和更多计算节点上的扩 展性． 表 2 不同大小数据集的并行聚类时间对比 Table 2 Time comparison of parallel clustering on different sizes of databases 计算 节点数 运行时间/ms 1 GB 数据 32 GB 数据 时间比值 1 217048 2824201 13. 0119 2 125530 1569016 12. 4991 3 91404 1046031 11. 4440 4 76824 855821 11. 1400 5 61512 688833 11. 1984 6 49332 543115 11. 0094 7 43185 470722 10. 9001 8 39465 421529 10. 6811 9 35579 376568 10. 5840 10 34452 344415 9. 9970 5 结论 针对面向云计算应用的大规模文本数据聚类挖 掘问题，本文在提出高效的文本聚类算法基础上，设 计了基于 MapＲeduce 框架的并行文本聚类模型． 以 二分 K-means 算法为基础，在保证二分 K-means 本 身较好的文本聚类效果的前提下，试图提高文本聚 类效率; 提出了基于初始簇中心选择的文本聚类算 法． 算法基于提出并证明收敛的“互为最小相似度 文本对”搜索算法选择初始二分聚类簇中心，克服 了原始二分 K-means 随机选择初始簇中心导致的需 要多次迭代寻找最优簇质心带来的计算效率较低问 题; 并且基于 MapＲeduce 框架设计了面向云计算应 用的分布式并行聚类模型． Hadoop 平台上运用真 实应用中的 20newsgroup 文本数据集的实验表明， 提出的算法在保证聚类效果的前提下，相比原始二 分 K-means 算法具有效率优势，应用不同规模的维 基百科数据集及在不同计算节点数目上的实验验证 了基于 MapＲeduce 并行聚类算法的良好扩展性． 未 来的研究可能包括降低聚类中的 K-means 步骤可能 带来的噪声数据对文本聚类结果的影响以及其他大 规模文本挖掘的并行化问题． 参 考 文 献 ［1］ Guan Ｒ C，Pei Z L，Shi X H，et al． Weight affinity propagation and its application to text clustering． J Comput Ｒes Dev，2010，47 ( 10) : 1733 ( 管仁初，裴志利，时小虎，等． 权吸引子传播算法及其在文 本聚类中的应用． 计算机研究与发展，2010，47( 10) : 1733) ［2］ Jeffrey D，Sanjay G． MapＲeduce: simplified data processing on · 8141 ·
第10期 武森等：基于MapReduce的大规模文本聚类并行化 ·1419· large clusters /Proceedings of the 6th Symposium on Operating [15]Zheng W,Ji D,Cai D F,et al.An approach to center selection Systems Design.San Francisco,2004:137 based on minimal similarity among texts.J Guangxi Norm Univ B]Yao Q Y,Liu G S,L X.VSM-based text clustering algorithm. Nat Sci Ed,.2008,26(3):198 Comput Eng,2008,34(18):39 (郑伟，季铎，蔡东风，等.基于文本互为最小相似度的中心 (姚清耘，刘功申，李翔.基于向量空间模型的文本聚类算 选取方法.广西师范大学学报：自然科学版，2008,26(3)： 法.计算机工程，2008,34(18)：39) 198) 4]Zhang X D,Zhou X H,Hu X H.Semantic smoothing for model- [16]Zhong S.Efficient online spherical K-means clustering /Pro- based document clustering /Proceedings of the Sixth International ceedings of 2005 IEEE International Joint Conference on Neural Conference on Data Mining.Washington:IEEE Computer Society, Neticorks.IEEE,2005:3180 2006:1193 [17]Scholkopf B,Weston J,Eskin E,et al.A kernel approach for Bharathi C.Venkatesan D.Study of ontology or thesaurus based leaming from almost orthogonal pattems.Lect Notes Comput Sci, document clustering and information retrieval.I Theor Appl Inf 2002,2431:494 Technol,.2012,40(1):55 [18]Ding Y,Fu X.The research of text mining based on selforgani- [6]Ma J,Xu W,Sun Y,et al.An ontology-based text-mining method zing maps.Procedia Eng,2012,29:537 to cluster proposals for research project selection.IEEE Trans Syst 9]Ceema I,Kavitha M.RenukadeviG,et al.Clustering web docu- Man Cybern Part A,2012,42(3):784 ments using hierarchical method for efficient cluster formation. 7]Shi Q W,Zhao Z,Zhao K.Hierarchical clustering of Chinese web Int J Sci Eng Technol Res,2012,1(5):127 pages on suffix tree.J Liaoning Tech Univ,2006,25(6):890 20] Gronau I,Moran S.Optimal implementations of UPGMA and (史庆伟，赵政，朝何.一种基于后缀树的中文网页层次聚类 other common clustering algorithms.Inf Process Lett,2007,104 方法.辽宁工程技术大学学报，2006,25(6)：890) (6):205 [8]Aswani Kumar C,Radvansky M,Annapuma J.Analysis of a vee- 1]Zhao Y,Karypis C,Fayyad U.Hierarchical clustering algorithms tor space model,latent semantic indexing and formal concept anal- for document datasets.Data Min Knowl Discor,2005,10 (2): ysis for information retrieval.Cybern Inf Technol,2012,12(1): 141 34 22]Yin Y,Wei C,Zhang G,et al.Implementation of space opti- Wu S H,Cheng Y,Zheng Y N,et al.A survey on text represen- mized bisecting K-means (BKM)based on Hadoop /Proceed- tation and similarity calculation in text clustering.Inf Sci,2012, ings9th Web Information Systems and Applications Conference, 30(4):622 W1S42012:170 (吴夙慧，成颖，郑彦宁，等.文本聚类中文本表示和相似度 [23]Zhao W Z,Ma H F,He Q.Parallel K-means clustering based on 计算研究综述.情报科学，2012,30(4)：622) MapReduce.Lect Notes Comput Sci,2009,5931:674 [10]Hammouda K M,Kamel M S.Efficient phrase-based document 24]Alina E,Sungjin I,Benjamin M.Fast clustering using MapRe- indexing for web document clustering.IEEE Trans Knowl Data duce /Proceedings of the 17th ACM SIGKDD International Con- Eng,2004,16(10):1279 ference on Knowcledge Discovery and Data Mining.New York: [11]Logeswari S,Premalatha K.Biomedical document clustering ACM,2011:681 using ontology based concept weight /2013 International Con- [25]Robson L F,Caetano T J,Agma J M,et al.Clustering very large ference on Computer Communication and Informatics (ICCCI). multi-dimensional datasets with MapReduce /Proceedings of the IEEE,2013:1 17th ACM SIGKDD International Conference on Knowledge Discov- [12]Zhu K B,Tang J,Yang B R.Web text mining system and clus- ery and Data Mining.New York:ACM,2011:690 tering analysis algorithm.Comput Eng,2004,30(13):138 [26]Wan J,Yu W M,Xu X H.Design and implement of distributed (朱克斌，唐菁，杨炳儒.Wb文本挖掘系统及聚类分析算 document clustering based on MapReduce /Proceedings of the 法.计算机工程，2004,30(13)：138) Second Symposium International Computer Science and Computa- [13]Dhillon I S,Modha D S.Concept decompositions for large sparse tional Technology.Huangshanr,2009:278 text data using clustering.Mach Learn,2001,42(1):143 27]Jones K S,Willet P.Readings in Information Retrieval.San [14]Arthur D,Vassilvitskii S.K-means++:the advantages of care Francisco:Morgan Kaufmann Publishers Inc,1997 ful seeding /Proceedings of the 8th Annual ACM-Siam Symposi- 8]Yang Y M.An evaluation of statistical approaches to text catego- um on Discrete Algorithms.Philadelphia,2007:1027 rization.Inf Retr,1999,1(1/2):69
第 10 期 武 森等: 基于 MapＲeduce 的大规模文本聚类并行化 large clusters / / Proceedings of the 6th Symposium on Operating Systems Design． San Francisco，2004: 137 ［3］ Yao Q Y，Liu G S，L X． VSM-based text clustering algorithm． Comput Eng，2008，34( 18) : 39 ( 姚清耘，刘功申，李翔． 基于向量空间模型的文本聚类算 法． 计算机工程，2008，34( 18) : 39) ［4］ Zhang X D，Zhou X H，Hu X H． Semantic smoothing for modelbased document clustering / / Proceedings of the Sixth International Conference on Data Mining． Washington: IEEE Computer Society， 2006: 1193 ［5］ Bharathi G，Venkatesan D． Study of ontology or thesaurus based document clustering and information retrieval． J Theor Appl Inf Technol，2012，40( 1) : 55 ［6］ Ma J，Xu W，Sun Y，et al． An ontology-based text-mining method to cluster proposals for research project selection． IEEE Trans Syst Man Cybern Part A，2012，42( 3) : 784 ［7］ Shi Q W，Zhao Z，Zhao K． Hierarchical clustering of Chinese web pages on suffix tree． J Liaoning Tech Univ，2006，25( 6) : 890 ( 史庆伟，赵政，朝柯． 一种基于后缀树的中文网页层次聚类 方法． 辽宁工程技术大学学报，2006，25( 6) : 890) ［8］ Aswani Kumar C，Ｒadvansky M，Annapurna J． Analysis of a vector space model，latent semantic indexing and formal concept analysis for information retrieval． Cybern Inf Technol，2012，12( 1) : 34 ［9］ Wu S H，Cheng Y，Zheng Y N，et al． A survey on text representation and similarity calculation in text clustering． Inf Sci，2012， 30( 4) : 622 ( 吴夙慧，成颖，郑彦宁，等． 文本聚类中文本表示和相似度 计算研究综述． 情报科学，2012，30( 4) : 622) ［10］ Hammouda K M，Kamel M S． Efficient phrase-based document indexing for web document clustering． IEEE Trans Knowl Data Eng，2004，16( 10) : 1279 ［11］ Logeswari S，Premalatha K． Biomedical document clustering using ontology based concept weight / / 2013 International Conference on Computer Communication and Informatics ( ICCCI) ． IEEE，2013: 1 ［12］ Zhu K B，Tang J，Yang B Ｒ． Web text mining system and clustering analysis algorithm． Comput Eng，2004，30( 13) : 138 ( 朱克斌，唐菁，杨炳儒． Web 文本挖掘系统及聚类分析算 法． 计算机工程，2004，30( 13) : 138) ［13］ Dhillon I S，Modha D S． Concept decompositions for large sparse text data using clustering． Mach Learn，2001，42( 1) : 143 ［14］ Arthur D，Vassilvitskii S． K-means + + : the advantages of careful seeding / / Proceedings of the 8th Annual ACM-Siam Symposium on Discrete Algorithms． Philadelphia，2007: 1027 ［15］ Zheng W，Ji D，Cai D F，et al． An approach to center selection based on minimal similarity among texts． J Guangxi Norm Univ Nat Sci Ed，2008，26( 3) : 198 ( 郑伟，季铎，蔡东风，等． 基于文本互为最小相似度的中心 选取方法． 广西师范大学学报: 自然科学版，2008，26( 3) : 198) ［16］ Zhong S． Efficient online spherical K-means clustering / / Proceedings of 2005 IEEE International Joint Conference on Neural Networks． IEEE，2005: 3180 ［17］ Schlkopf B，Weston J，Eskin E，et al． A kernel approach for learning from almost orthogonal patterns． Lect Notes Comput Sci， 2002，2431: 494 ［18］ Ding Y，Fu X． The research of text mining based on self-organizing maps． Procedia Eng，2012，29: 537 ［19］ Ceema I，Kavitha M，Ｒenukadevi G，et al． Clustering web documents using hierarchical method for efficient cluster formation． Int J Sci Eng Technol Ｒes，2012，1( 5) : 127 ［20］ Gronau I，Moran S． Optimal implementations of UPGMA and other common clustering algorithms． Inf Process Lett，2007，104 ( 6) : 205 ［21］ Zhao Y，Karypis G，Fayyad U． Hierarchical clustering algorithms for document datasets． Data Min Knowl Discov，2005，10( 2) : 141 ［22］ Yin Y，Wei C，Zhang G，et al． Implementation of space optimized bisecting K-means ( BKM) based on Hadoop / / Proceedings-9th Web Information Systems and Applications Conference， WISA 2012: 170 ［23］ Zhao W Z，Ma H F，He Q． Parallel K-means clustering based on MapＲeduce． Lect Notes Comput Sci，2009，5931: 674 ［24］ Alina E，Sungjin I，Benjamin M． Fast clustering using MapＲeduce / / Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining． New York: ACM，2011: 681 ［25］ Ｒobson L F，Caetano T J，Agma J M，et al． Clustering very large multi-dimensional datasets with MapＲeduce / / Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining． New York: ACM，2011: 690 ［26］ Wan J，Yu W M，Xu X H． Design and implement of distributed document clustering based on MapＲeduce / / Proceedings of the Second Symposium International Computer Science and Computational Technology． Huangshanr，2009: 278 ［27］ Jones K S，Willet P． Ｒeadings in Information Ｒetrieval． San Francisco: Morgan Kaufmann Publishers Inc，1997 ［28］ Yang Y M． An evaluation of statistical approaches to text categorization． Inf Ｒetr，1999，1( 1 /2) : 69 · 9141 ·