第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 pro￾posed 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． prince￾ton． edu /wordnet /