基于MapReduce的大规模文本聚类并行化

第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］． 以互联网应用为载体的文本 数据的快速增长和商业分析的迫切需求，使得文本 挖掘的重要性和紧迫性也日益增强，其中在不需要 训练集和预定义类别的情况下，从给定的文本集合 中找到合理的文本簇划分的文本聚类研究是文本挖 掘领域的一个重要研究方向． 随着互联网各种应用( 微博、电子商务和搜索

·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 ·