2024年1月14日发(作者：)

２０１３年９月　内蒙古科技大学学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｉｎｎｅｒ　Ｍｏｎｇｏｌｉａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｓｅｐｔｅｍｂｅｒ，２０１３　Ｖｏ１．３２，Ｎｏ．３　第３２卷３期　文章编号：２０９５—２２９５（２０１３）０３—０２７３—０５　基于ＭａｐＲｅｄｕｃｅ的并行遮盖文本聚类算法　张亚楠　，谭跃生　（１．内蒙古科技大学信息工程学院，内蒙古包头０１４０１０；２．内蒙古科技大学工程训练中心，内蒙古包头０１４０１０）　关键词：文本聚类；遮盖算法；Ｈａｄｏｏｐ；ＭａｐＲｅｄｕｃｅ　中图分类号：ＴＰ３９１．１　文献标识码：Ａ　摘要：通过研究Ｈａｄｏｏｐ平台和ＭａｐＲｅｄｕｃｅ编程框架，提出了一个基于ＭａｐＲｅｄｕｃｅ的并行遮盖文本聚类算法．遮　盖算法提出了两个距离阈值ｎ，　用来构建重叠子集，避免了传统聚类算法对噪声敏感的缺点．同时采用适当的　快速近似距离度量，大大加快了聚类速度．实验表明该算法在ＭａｐＲｅｄｕｃｅ框架下有良好的集群加速性能，适合处理　大规模的数据集．　Ｔｈｅ　ｐａｒａｌｌｅｌ　ｃａｎｏｐｙ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｅｘｔ　ｃｌｕｓｔｅｒｉｎｇ　ｂａｓｅｄ　ｏｎ　ＭａｐＲｅｄｕｃｅ　ＺＨＡＮＧ　Ｙａ．ｎａｎ　，ＴＡＮ　Ｙｕｅ．ｓｈｅｎｇ　（１．Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｓｃｈｏｏｌ，Ｉｎｎｅｒ　Ｍｏｎｇｏｌｉａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｂａｏｔｏｕ　０１４０１０，Ｃｈｉｎａ；２．Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ｔｒａｉｎｉｎｇ　Ｃｅｎｔｅｒ，Ｉｎｎｅｒ　Ｍｏｎｇｏｌｉａ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｙ，ｇＢａｏｔｏｕ　０１４０１０，Ｃｈｉｎａ）　Ｋｅｙ　ｗｏｒｄｓ：ｄｏｃｕｍｅｎｔ　ｃｌｕｓｔｅｒｉｎｇ；ｃａｎｏｐｙ　ａｌｇｏｒｉｔｈｍ；ｈａｄｏｏｐ；ｍａｐｒｅｄｕｃｅ　Ａｂｓｔｒａｃｔ：Ｂｙ　ｒｅｓｅａｒｃｈｉｎｇ　Ｈａｄｏｏｐ　ｐｌａｔｆｏｒｍ　ａｎｄ　ＭａｐＲｅｄｕｃｅ　ｐｒｏｇｒａｍｍｉｎｇ　ｆｒａｍｅｗｏｒｋ，ａ　ｃａｎｏｐｙ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｅｘｔ　ｃｌｕｓｔｅｒｉｎｇ　ｂａｓｅｄ　ｏｎ　ＭａｐＲｅｄｕｃｅ　ｗａｓ　ｐｒｅｓｅｎｔｅｄ．Ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｐｒｏｐｏｓｅｄ　ｔｗｏ　ｄｉｓｔａｎｃｅ　ｔｈｒｅｓｈｏｌｄ　Ｔ１　ａｎｄ　７２　ｔｏ　ｂｕｉｌｄ　ｏｖｅｒｌａｐｐｉｎｇ　ｓｕｂｓｅｔ．Ｉｔ　ｃａｎ　ａｖｏｉｄ　ｔｈｅ　ｓｈｏｒｔｃｏｍｉｎｇｓ　ｏｆ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｃｌｕｓｔｅｒｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｗｈｉｃｈ　ｉｓ　ｓｅｎｓｉｔｉｖｅ　ｔｏ　ｎｏｉｓｅ．Ａｔ　ｔｈｅ　ｓａｍｅ　ｔｉｍｅ，ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｕｓｅｓ　ａｎ　ａｐｐｒｏｐｒｉａｔｅ　ｆａｓｔ　ａｐｐｒｏｘｉｍａｔｅ　ｄｉｓｔａｎｃｅ　ｍｅｔｉｃｓ　ａｎｄ　ａｃｃｅｌｅｒａｔｒｅｓ　ｔｈｅ　ｃｌｕｓｔｅｒｉｎｇ　ｓｐｅｅｄ　ｇｒｅａｔｌｙ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｓｈｏｗ　ｔｈａｔ　ｉｔ　ｈａｓ　ａ　ｇｏｏｄ　ａｃｃｅｌｅｒａｔｉｏｎ　ｐｅｒｆｏｒｍ—　ａｎｃｅ　ｗｉｔｈ　ＭａｐＲｅｄｕｃｅ　ｆｒａｍｅｗｏｒｋ，ＳＯ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｓｕｉｔａｂｌｅ　ｆｏｒ　ｈａｎｄｌｉｎｇ　ｌａｒｇｅ　ｄａｔａ　ｓｅｔｓ．　文本聚类是文本挖掘的一个重要内容之一．文　特定的应用来决定．　本挖掘（Ｔｅｘｔ　Ｍｉｎｉｎｇ）是指从大量非结构化文本数据　中提取出事先未知的、可理解的、最终可用的、用户　感兴趣的信息或知识的过程．或者简单说来，当数据　挖掘的对象完全由文本数据类型组成时，这个过程　就被称为文本挖掘．　文本聚类并不是一项简单的工作，它所处理的　是非结构化或者半结构化的文本数据，这些数据大　多都是模糊的、缺乏确定的形式与结构．文本聚类的　基本过程包括对目标文本文档集进行文档预处理，　这个阶段包括分词、去除停留词、词干化等操作．接　下来抽取特征项、对特征项降维、选择文本表示方　法、构造特征空间、构造文档向量、选取距离和相似　文本聚类¨　可以对文本信息进行自动地组织、　摘要．实质是对文本根据其特征归类，即将给定的文　本集合分成若干个类或子集，使各个子集内部的文　度度量，最后进行文本聚类处理，得出聚类结果．可　见，能否对文本数据集进行充分有效的预处理决定　着聚类效果．　本相似，各子集之间的文本不相似．文本的特征项常　常根据应用的不同而各异，文本之间的相似性也由　收稿日期：２０１３—０５—２７　基金项目：内蒙古自然科学基金资助项目（２０１２ＭＳ０９１２）；内蒙古教育厅科研资助项目（Ｎｊｚｙｌ２１１０）　作者简介：张亚楠（１９８６一），男，河北石家庄人，内蒙古科技大学硕士研究生．　

２７４　内蒙古科技大学学报　２０１３年９月　第３２卷第３期　ＭａｐＲｅｄｕｃｅ　是Ｇｏｏｇｌｅ早在２００４年就提出来　的编程模型，它简化了开发并行程序的过程，推动了　并行计算的广泛应用．Ｇｏｏｇｌｅ的ＭａｐＲｅｄｕｃｅ是商业　系统，２００８年Ａｐａｃｈｅ　Ｈａｄｏｏｐ　开源云平台实现了　ＭａｐＲｅｄｕｃｅ编程模型，同时也实现了类似ＧＦＳ　（Ｇｏｏｇｌｅ　Ｆｉｌｅ　Ｓｙｓｔｅｍ，谷歌文件系统）的ＨＤＦＳ分布　式文件系统．在近几年中，随着Ｈａｄｏｏｐ开源云平台　的发展与广泛应用，使得大规模数据集的数据挖掘　变得更加大众化．因此，在文本聚类传统预处理的基　础之上，进一步引入了遮盖算法作为深层次的预处　理，经过这两步预处理后，再采用常见聚类算法进行　聚类．同时为了加快速度，将遮盖算法部署在Ｈａ—　ｄｏｏｐ平台上，进行ＭａｐＲｅｄｕｃｅ并行化．通过以上这　两个改进，使得面对大规模文本聚类时大大加快了　聚类处理速度和聚类精度．　１　遮盖算法介绍以及并行化分析　１．１遮盖算法介绍　遮盖算法　是一种简单、快速，但不太准确的　聚类方法，是专门应对高维海量数据源的一种新型　聚类算法．算法的思路是：首先在计算数据样本距离　时采用算法复杂度低的距离度量（ｍｅｔｉｒｃ　ｄｉｓｔａｎｃｅ），　把样本数据集划分为一些部分重叠的子集．然后，在　传统聚类中，比如ｋ均值，应用复杂度高的度量距　离，进一步计算，从而使得高维海量数据源聚类难题　易于实现．　一个典型的遮盖算法的流程图如图１所示．　图１遮盖算法流程图　Ｆｉｇ．１　Ｃａｎｏｐｙ　ａｌｇｏｒｉｔｈｍ　ｆｌｏｗｃｈａ￣　具体执行过程如下：　（１）确定两个距离阈值：Ｔ１和　，其中Ｔ１＞７２：　（２）从经过预处理的数据集中任取一点Ｐ，用　低计算成本方法快速计算点Ｐ与所有遮盖之间的距　离（如果当前不存在遮盖，则把点Ｐ作为一个遮　盖），如果点Ｐ与某个遮盖距离在　１以内，则将点Ｐ　加入到这个遮盖；　（３）如果点Ｐ曾经与某个遮盖的距离在　以　内，则需要把点Ｐ从数据集中删除，点Ｐ此时与这个　遮盖中心已经足够近，因此它不能再做其它遮盖的　中心了；　（４）重复步骤２，３，直到数据集为空结束．　１．２遮盖算法并行化　分析遮盖算法的流程，在Ｈａｄｏｏｐ平台上按照　ＭａｐＲｅｄｕｃｅ　编程模型进行并行化的策略如下：首　先，在各个从节点上分别使用遮盖算法处理本节点　存储的数据，将生成的遮盖中心集合汇总到主节点　上，这个过程需要使用一个映射（ｍａｐ）操作和一个　规约（ｒｅｄｕｃｅ）操作；其次，按照生成的遮盖中心集合　进行遮盖聚类，这个过程需要一个映射操作．　算法ＭａｐＲｅｄｕｃｅ并行化流程如图２所示．　图２遮盖算法并行化流程图　Ｆｉｇ．２　Ｐａｒａｌｌｅｌｉｚａｔｉｏｎ　ｃａｎｏｐｙ　ａｌｇｏｒｉｔｈｍ　ｆｌｏｗｃｈａｒｔ　具体实现过程中，最主要是实现两个映射类和　一个规约类：　（１）ＣａｎｏｐｙＤｒｉｖｅｒ　这是整个程序的入口，负责算法的整体运行．首　先，进行程序运行参数的初始化，将从命令行传人的　程序运行参数进行解析，主要的参数包括数据集输　

张亚楠，等：基于ＭａｐＲｅｄｕｃｅ的并行遮盖文本聚类算法　人路径、聚类结果输出路径、Ｃｏｎｆｉｇｕｒａｔｉｏｎ配置类、距　离度量标准、距离阈值等等；对于没有指定值的参数　采用默认值；其次，最主要任务是定义和配置ｊｏｂ，组　织ｊ０ｂ的执行，在这个过程中指定了ＣａｎｏｐｙＭａｐｐｅｒ　类、ＣａｎｏｐｙＲｅｄｕｃｅｒ类和ＣｌｕｓｔｅｒＭａｐｐｅｒ类分别为第　一个映射阶段和规约阶段以及第二个映射阶段的具　体实现．第一个ｍａｐ阶段需要调用ｂｕｉｌｄＣｌｕｓｔｅｒｓ（）　方法在各个从节点上来构建ｃｌｕｓｔｅｒ，规约阶段与映　射阶段类似，在主节点调用ｂｕｉｌｄＣｌｕｓｔｅｒｓ（）将各个　从节点构建的ｃｌｕｓｔｅｒ汇总．第二个映射阶段则调用　ｃｌｕｓｔｅｒＤａｔａ（）方法来进行聚类，这些过程中都指定　了映射、规约阶段的输入输出＜ｋｅｙ，ｖａｌｕｅ＞值的数　据类型．　（２）ＣａｎｏｐｙＣｌｕｓｔｅｒｅｒ　这个类是实现遮盖算法的核心，其中包含２个　重要方法：　（￣）ａｄｄＰｏｉｎｔＴｏＣａｎｏｐｉｅｓ方法用来决定当前点应　该加人到哪个遮盖中，在ＣａｎｏｐｙＭａｐｐｅｒ和Ｃａｎｏｐｙ—　Ｒｅｄｕｃｅｒ中用到；　（￣）ｅｍｉｔＰｏｉｎｔＴｏＣｌｏｓｅｓｔＣａｎｏｐｙ方法查找与当前点　距离最近的遮盖，并将当前点（遮盖的标示符，用　Ｖｅｃｔｏｒ表示）输出，这个方法在聚类阶段ＣｌｕｓｔｅｒＭａｐ—　ｐｅｒ中用到．　（３）ＣａｎｏｐｙＭａｐｐｅｒ　这个类指定了映射阶段的具体实现过程，主要　任务是在各个从节点上构建ｃｌｕｓｔｅｒ．首先声明了一　个ＡｒｒａｙＬｉｓｔ类型的全局变量ｃａｎｏｐｉｅｓ，用来存储生　成的遮盖ｃｌｕｓｔｅｒ列表．ＣａｎｏｐｙＭａｐｐｅｒ类继承于　Ｍａｐｐｅｒ类，因此父类的三个方法ｓｅｔｕｐ（），ｍａｐ（），　ｃｌｅａｎｕｐ（）可以根据实际需要进行重写．ｓｅｔｕｐ方法　用于ｍａｐ方法之前，用于初始化数据．ｃｌｅａｎｕｐ方法　用于ｍａｐ方法之后，将中间结果写入上下文．这个　类的核心是ｍａｐ方法，每个从节点通过ｍａｐ方法来　处理各自被分配到的数据集，通过执行调用　ａｄｄＰｏｉｎｔＴｏＣａｎｏｐｉｅｓ方法来构建ｃｌｕｓｔｅｒ．　（４）ＣａｎｏｐｙＲｅｄｕｃｅｒ　这个类指定了规约阶段具体实现过程．主要任　务是在主节点上将各个从节点生成的遮盖用相同算　法汇总后得到最终的遮盖集合．ＣａｎｏｐｙＲｅｄｕｃｅｒ类里　面同样定义了一个遮盖集合，用来存储全局遮盖．特　别的，ｓｅｔｕｐ方法在规约阶段与映射阶段不同的地方　是可以对阈值ｎ，／２（Ｔ１＞　）重新设置（这里用　乃，　表示），也就是说映射阶段的阈值可以与规　２７５　约阶段的不同．ｒｅｄｕｃｅ方法最后更新各个全局遮盖　的信息，将＜遮盖标示符，遮盖对象＞键值对写入　上下文中．　（５）ＣｌｕｓｔｅｒＭａｐｐｅｒ　这个类用来进行最后聚类，比较简单，只有一个　ｍａｐ操作，以上一阶段输出的顺序文件为输入，ｓｅｔｕｐ　方法做一些初始化工作并从上一阶段输出目录读取　文件，重建遮盖集合信息并存储在一个遮盖集合中，　ｍａｐ操作就调用ＣａｎｏｐｙＣｌｕｓｔｅｒｅｒ的ｅｍｉｔＰｏｉｎｔＴｏＣｌｏｓ—　ｅｓｔＣａｎｏｐｙ方法实现聚类，将最终结果输出到一个顺　序文件中．　１．３　ｎ及　取值的讨论　引入遮盖算法后，ｋ均值中需要人工指定的参　数由ｋ变成了力及　，ｎ和　所起的作用是缺一　不可的．７１决定了每个聚类包含点的数目，这直接　影响了Ｃｌｕｓｔｅｒ的“重心”和“半径”；而　则决定了　聚类的数目，　太大会导致只有一个聚类，而太小　则会出现过多的聚类．实验表明，ｎ和　取值会严　重影响到算法的效果，如何确定ｎ和　，可以用　ＡＩＣ，ＢＩＣ或者交叉验证确定．　文档之间采用余弦相似度进行相似度测量，文　档之间的距离度量取值在０～１之间。０表示两个向　量是完全独立的，１表示两个向量方向完全相同．所　以ｎ，　这两个距离阈值取值范围也在０～１之间．　假设目标数据集要聚为ｋ类，且文档是分布理想的　１　情况下，每类文档的半径为　，考虑聚类有重叠部分，　‘　１　１　取ｎ＝　＋Ｏｄ，７２＝　一　是指定的经验值．　２实验测试和性能分析　２．１　实验环境　为了充分使用有限的硬件资源、提高工作效率，　实验平台基于免费版的ＶＭｗａｒｅ　ｖＳｐｈｅｒｅ　Ｈｙｐｅｒｖｉｓｏｒ　５搭建．在这个虚拟化平台上安装了９个Ｕｂｕｎｔｕ节　点，每个节点分配的硬件配置如下：内存１ＧＢ，硬盘　２０ＧＢ，ＣＰＵ　１ＧＨｚ．接着在这９个节点之上部署了一　个小型的Ｈａｄｏｏｐ集群环境，通过更改主节点的设　置，可以模拟单机模式（只有１个主节点的伪分布　模式）和多节点集群模式（１个主节点、多个从节　点）．最后在这个Ｈａｄｏｏｐ平台上运行ＭａｐＲｅｄｕｃｅ并　行化的ｋ均值和遮盖算法，进行对比实验．　整个实验环境的结构层次图如图３所示．　

２７６　内蒙古科技大学学报　２０１３年９月　第３２卷第３期　图３实验结构层次图　Ｆｉｇ．３　Ｔｈｅ　ｈｉｅｒａｒｃｈｙ　ｏｆ　ｅｘｐｅｒｉｍｅｎｔ　由于没有文本聚类专用的数据集，目前一般采　用文本分类的数据集进行测试．实验数据集采用复　旦大学中文语料库　．复旦大学中文语料库由复旦　筮潮器　大学计算机信息与技术系国际数据库中心自然语言　７　６　５　４　３　２　ｌ　Ｏ　处理小组提供，包括测试语料，共９　８３３篇文档，训　练语料，共９　８０４篇文档．数据集分为航空、能源、电　力、通信、计算机、采掘、交通、环境、农业、经济、法　律、医药、军事、政治、运动、艺术、文化、教育、哲学和　历史，共二十个类别．实验中使用Ａｐａｃｈｅ提供的工　具完成对复旦语料库的初步预处理工作．处理本实　验数据集时取　＝２０，ＯＬ＝０．００５，则：　Ｔ１＝　Ｉ＋　＝０．０３，　１＝　一　＝０．０２．　２．２速度对比　首先，分别在２，４，６，８个节点上进行遮盖算法　的集群实验，比较遮盖算法处理不同大小的数据集　时的集群加速比．ＤＳ１／１６表示整个数据集的１／１６，　以下类同．经过５次实验，取平均值可得如图４所示　结果．图中横坐标为从节点个数，纵坐标为加速比．　加速比ｓ＝　，７１，为１个节点运行时间，　为凡个节　１　ｎ　点运行时间　．　从图４可以得出以下结论：（１）遮盖算法的加　速比表现良好，加速比随着数据集的增大更趋于线　性增长；（２）在数据集大小相同的情况下，由于节点　的增加会导致节点之间的通信开销也逐渐增大，因　此加速比的增长速度随着节点数目的增加而放慢．　其次，通过遮盖算法对数据集进行深层预处理之　后，再采用传统的聚类算法．实验中对比了有无遮盖算　法预处理　均值算法运行时间，其结果如图５所示．　节点个数　图４集群加速比　Ｆｉｇ．４　Ｔｈｅ　ｓｐｅｅｄｕｐ　ｏｆ　ｃｌｕｓｔｅｒ　从图５中可以看到：（１）数据集较小的时候，也　就是当处理ＤＳ１／１６到ＤＳ１／４这些数据集时，两种　算法在运行时间上的差距并不明显；（２）随着数据　集的成倍增长，也就是当处理ＤＳ１／４到ＤＳ１这些数　据集时，两种算法的运行时间都会有明显增长，并且　时间的增长速度要大于数据集的增长倍数；（３）无　预处理的　均值比有预处理的　均值算法的时间耗　费更明显．　：　３　迎２　喜：　藩：　数据集　图５　均值运行时间对比　Ｆｉｇ．５　Ｔｈｅ　ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ａｎｄ　ｍｅａｎｓ　ｒｕｎｔｉｍｅ　２．３效果评价　复旦大学中文语料库中文档分类多达２０种之　多，而且每一种的文档数量差距很大，有些文档的数　量达到１　０００篇以上，有的却不到１００篇．搜狗语料　库中有ｌ０种分类，且每一种分类的文档数据相同．　相比而言，复旦大学数据集可以比较良好地模拟现　实应用中的文档聚类情况．　文本聚类效果评价引入了查准率和查全率　两个指标，统计经过预处理的　均值的聚类结果，图　６为查准率和查全率．　

张亚楠，等：基于ＭａｐＲｅｄｕｃｅ的并行遮盖文本聚类算法　分析图６：（１）经过遮盖聚类预处理之后得到的　结果，查准率多在８０％以上，这说明聚类的准确度　比较理想；（２）相比而言，对于查全率指标，则会差　异较大，对于文档数量较多的分类，则会被聚到多个　类之中，导致查全率下降，因为有些文档涉及到了多　个领域，分类并不唯一；（３）对于文档数目较少的原　始分类，如能源、电力、通信、交通、医药、文化等类　别，查准率和查全率指标会很低，因为文档数目较　少，提取出有效的特征值较少，该类别会被遮盖算法　认为是噪声而忽略掉．　１ＯＯ　ｇ５　９０　８５　丑８０　盍７５　７Ｏ　６五　６０　运动　经济计算机环境　艺术　政治　农业　觏空　类别　图６聚类的查准率和查全率统计　Ｆｉｇ．６　Ｔｈｅ　ｓｔａｔｉｓｔｉｃｓ　ｏｆ　ｃｌｕｓｔｅｒｉｎｇ　ｐｒｅｃｉｓｉｏｎ　ａｎｄ　ｒｅｃａｌｌ　３　结论　通过引入遮盖算法，对传统聚类算法进行深入　的预处理优化，由于减少了计算距离的空间复杂度，　算法时间得到大大的提高．经过集群上进行对比实　２７７　验统计算法加速比并行算法的指标等参数，验证了　经过遮盖算法预处理之后，弥补了传统聚类算法处　理大数据集的时间瓶颈．但是实验中，数据集预处理　效果对实验结果影响较大．下一步工作是进一步改　进算法，做好数据集的预处理，进行不同数据集的相　关实验，不断完善算法性能和集群配置，提高海量数　据的挖掘能力，同时优化文档分类，提高查准率和查　全率．　参考文献：　［１］朱明．数据挖掘导论［Ｍ］．合肥：中国科学技术大学　出版社，２０１２：２１５－２２５．　１－２］Ｄｅａｎ　Ｊ，Ｇｈｅｍａｗａｔ　ｓ．ＭａｐＲｅｄｕｃｅ：ｓｉｍｐｌｉｆｉｅｄ　ｄａｔａ　ｐｒｏｃｅｓｓ—　ｉｎｇ　ｏｎ　ｌａｒｇｅ　ｃｌｕｓｔｅｒｓ［Ｊ］．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，　２００８，５１（１）：１０７—１１３．　［３］Ｈａｄｏｏｐ　Ｗ　Ｔ．Ｔｈｅ　ｄｅｆｉｎｉｔｉｖｅ　ｇｕｉｄｅ［Ｍ］．Ｓｅｂａｓｔｏｐｏｌ：　Ｏ’Ｒｅｉｌｌｙ　Ｍｅｄｉａ，Ｉｎｃ．，２０１２．　１－４］　ＭｃＣａｌｌｕｍ　Ａ，Ｎｉｇａｍ　Ｋ，Ｕｎｇａｒ　Ｌ　Ｈ．Ｅｆｉｆｃｉｅｎｔ　ｃｌｕｓｔｅｒｉｎｇ　ｏｆ　ｈｉｇｈ—ｄｉｍｅｎｓｉｏｎａｌ　ｄａｔａ　ｓｅｔｓ　ｗｉｔｈ　ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　ｒｅｆｅｒｅｎｃｅ　ｍａｔｃｈｉｎｇ［Ａ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　ｓｉｘｔｈ　ＡＣＭ　ＳＩＧＫＤＤ　ｉｎ—　ｔｅｒｎａｔｉｏｎａｌ　ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ｋｎｏｗｌｅｄｇｅ　ｄｉｓｃｏｖｅｒｙ　ａｎｄ　ｄａｔａ　ｍｉｎｉｎｇＥ　ｃ］．ＵＳＡ：ＡＣＭ，２０００：１６９—１７８．　［５］Ｄｅａｎ　Ｊ，Ｇｈｅｍａｗａｔ　ｓ．ＭａｐＲｅｄｕｃｅ：ｓｉｍｐｌｉｉｆｅｄ　ｄａｔａ　ｐｒｏｃｅｓｓ—　ｉｎｇ　ｏｎ　ｌａｒｇｅ　ｃｌｕｓｔｅｒｓ［Ｊ］．Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　ｏｆ　ｔｈｅ　ＡＣＭ，　２００８，５１（１）：１０７—１１３．　［６３复旦大学中文语料库［ＥＢ／ＯＬ３．ｈｔｔｐ：／／ｗｗｗ．ｎｌｖ．ｏｒｇ．　ｃｎ，２００８—０６—２１．　［７］陈国良．并行计算——结构・算法・编程，第三版　［Ｍ］．北京：高等教育出版社，２０１１：１１８．　［８］　周昭涛．文本聚类分析效果评价及文本表示研究［Ｄ］．　北京：中国科学院研究生院，２００５．