论文部分内容阅读
聚类分析是数据挖掘中的核心技术之一。随着互联网的发展,现实世界中的数据量呈现爆炸式地增长,这导致传统的集中式聚类技术在面对大数据时无法有效地处理。随着MapReduce框架的出现与流行,利用该框架进行分布式并行的聚类成为目前的一大研究方向。如何在MapReduce框架下对大规模数据集进行高效并行的聚类是本文要解决的问题。本论文的研究内容包括并行K-means聚类、并行CLARANS聚类、基于CHSMST算法的并行聚类、并行层次搜索网页聚类PHSPC。主要做出了如下创新性工作:
●提出了面向Hbase数据库、基于MapReduce框架下的并行K-means聚类算法。该算法首先利用蓄水池抽样原理从全体数据集中等概率地选出样本点作为初始的聚类中心。然后启动MapReduceJob迭代地对聚类中心进行求精。该算法具有近似线性的加速比、良好的可扩展性、较高的结果一致性和并行正确率。最后比较了面向HDFS和Hbase的并行K-means聚类算法。
●提出了基于MapReduce框架下的并行CLARANS聚类算法。该算法以样本为聚类中心来聚类所有数据。首先修改了原有的CLARANS算法使得其更加适合于在MapReduce框架下高效执行,然后分三步对其进行了并行化。最后的实验结果显示,该算法具有良好的加速比和可扩展性、极高的结果一致性和并行正确率。与并行K-means算法相比,聚类结果更加稳定。
●提出了在MapReduce框架下的基于超曲面和K均值的并行聚类算法CHSK-means。首先介绍了超曲面分类及其并行化的内容。接着我们将CHS聚类的过程进行了并行化,并分析了在MapReduce框架下并行化MST的低效性,然后给出了一个替代的解决方案CHSK-means。实验结果表明,对于相同的数据量和计算资源,该算法的运行时间与并行K-means和并行CLARANS相比最短,且具有非常优异的加速比和可扩展性,极高的结果一致性,但在并行正确率上对实验数据集的测试偏低,原因是我们给出的对MST的替代方案在这些数据集中不能较好地分割局部密集区域。
●提出了基于MapReduce框架下的并行层次搜索网页聚类算法PHSPC。算法首先分析了目前的搜索引擎对网页结果展示的一些不足,给出了对用户而言比较友好的浏览方式。然后提出了对搜索网页进行层次聚类的算法,并在MapReduce框架下进行了并行化。通过实验分析了各个参数对聚类结果的影响,最后展示了一种对聚类结果进行浏览的层次方法,大大方便了用户的使用。