论文部分内容阅读
高性能计算技术在全世界范围内受到了高度重视,在众多高新科技领域中的应用都取得了巨大的成就。集群系统的出现更给高性能计算的研究增添了一个极具吸引力的生力军,它以无可替代的优势和可深挖掘的潜在性能,成为了当前并行处理的热点和主流。
BIRCH是数据挖掘领域中层次聚类的经典算法之一,它特别适合于大数据集,单遍的扫描数据集就可以产生较好的聚类。然而,随着其应用范围的日益广泛,有些问题需要处理的数据量非常之大,有些则要求有极快的运行速度,目前的计算速度达不到实际要求。
基于此,本文对如何在集群系统中采用BIRCH进行快速聚类以及如何取得更好的聚类结果进行了深入的研究和分析。
首先,本文对BIRCH算法进行了深入研究,编写了其串行算法,针对算法中存在的局限性,提出了CF-树中不同的簇应使用不同阀值的思想,极好地改善了对体积相差悬殊的簇不能很好聚类的不足。随后,搭建了基于Windows和MPI、Linux和MPI的两个集群系统。在此基础上,以主从模式作为并行程序的模型,对BIRCH的并行化进行了重点分析和研究,并提出了一些创新:认为在集群环境下,BIRCH算法的并行化应采用数据并行的思想;为达到计算与通信的最大重叠,各从节点之间应该选用增量递增的非均匀数据划分策略;从该思想出发推导出各节点的基本数据区块的计算公式;并利用该公式对原有的数据选段方式进行了改进;此外,给出了提高聚类质量的方案。
其次,本文利用自建的两个实验平台,对并行算法进行了测试,比较了串行与并行BIRCH算法之间以及在不同平台之间的运算时耗的差异。根据理论研究和实际测试结果,表明利用集群系统进行BIRCH并行聚类能有效地提高效率是可行的,并得出Linux集群的性能较优。
本文的研究结果对聚类算法在相关领域的实际应用有着一定的参考价值。