论文部分内容阅读
文本聚类是一项具有重要应用价值的研究,在一些应用领域中,文本聚类需要处理的数据规模正在以非常快的速度增大。处理大规模数据需要采用高效的大规模数据分析技术,传统的串行编程模型在可扩展性上存在严重不足,无法满足大规模数据处理对计算资源和存储资源的需求。以MapReduce为代表的分布式计算技术具备了良好的扩展性,能够极大地提高数据密集型算法的执行效率、充分发挥基于普通硬件的计算集群的计算能力。MapReduce分布式计算框架的出现极大地降低了并行计算的门槛,同时MapReduce编程模型又以自身优秀的架构设计成为大数据处理技术的不二选择。为了利用MapReduce分布式计算框架解决传统的层次聚类算法在处理大规模语料数据时可扩展性不足的问题,本文提出基于MapReduce编程模型的并行文本层次聚类算法。传统的层次聚类算法针对串行编程模型进行设计,因此将层次聚类算法并行化时,需要考量串行编程模型与分布式编程模型之间的差异,充分利用分布式计算平台的特性来设计并行层次聚类算法,以下是本文主要研究内容的简单概括:1)对MapReduce分布式计算框架进行深入的研究,包括MapReduce的数据分发策略、排序特性、将传统的串行算法移植到MapReduce编程模型的必要条件。针对MapReduce最重要的开源实现Hadoop中的关键模块进行了详细的分析。2)对文本聚类过程中涉及到的关键技术的MapReduce并行化进行深入分析,重新设计包括文本分词、特征选择、特征权重计算在内的文本向量化关键步骤,为整个文本聚类过程的MapReduce并行化奠定基础。3)针对文本层次聚类算法很难实现计算并行的问题,提出基于数据划分的并行文本层次聚类算法,解决了文本层次聚类算法的并行化。并行文本层次聚类将数据划分引入传统的层次聚类算法,合理地利用了MapReduce编程模型的排序特性及二次排序技术来高效地选取合并点。数据划分算法采用基于文本向量分量组特征统计的垂直划分算法,该算法简单高效,可以有效地进行大规模数据的快速划分。4)编程实现这些关键步骤的相关算法,并针对两个不同的数据集进行实验。为了进行实验,搭建一个小型的Hadoop集群,然后通过五个主要实验来验证算法的聚类精度及并行性能,并探讨了一些重要参数的配置及数据集的输入方式对算法的影响。实验结果表明,基于MapReduce的并行文本聚类算法可以有效地进行大规模文本的聚类,同时又具有良好的可扩展性。