·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 da￾tabases 计算 节点数 运行时间/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 ·