一种聚类算法的行化研究.pdf

一种聚类算法的并行化研究 {ii 摘 要 随着计算机技术的飞速发展以及网络的普及，人们在应用过程中产生和收集的信息 在规模、范围和深度等方面不断扩大。这些海量的数据在组成和功能之间存在着丰富和 复杂的信息，因此人们希望能够对其进行更高层次的分析。 K均值算法是基于原型的聚类技术，具有简单、快速和有效处理大规模数据等诸多 优点，是应用最广泛的聚类方法之一。缺点是存在过度依赖初始条件，如初始聚类中心 的选取等都会影响聚类结果，制约了其应用范围。二分K均值聚类算法是K均值算法 的变种算法，通过使用基本K均值算法能够产生划分聚类算法或层次聚类算法，具有不 受初始质心选择影响的优点。 聚类实际应用处理对象多为海量数据和高维数据，具有很高的时间和空间复杂性。 在处理海量TB级文本数据时，利用多台主机组成的群集系统，具有强大的并行计算能 力。基于群集环境下的二分K均值聚类算法并行化研究，可以极大的提高工作效率，具 有一定的现实应用意义。 本文针对二分K均值聚类算法在二分聚类过程中初始质心选取速度方面存在的不 足，提出了以极大距离点作为二分聚类初始质心的思想，较好的改善了算法的运行速度。 深入研究和分析了如何在群集系统中进行快速聚类，根据二分K均值聚类算法的特性， 采用数据并行的思想和均匀划分策略，对算法进行了并行化。最后的实验结果表明，改 进后的算法获得了理想的加速比，提高了算法的使用效率。 关键词：数据挖掘；聚类；二分K均值；并行化；群集 一种聚类算法的并行化研究 Abstract the of scienceand With andthe of rapiddevelopmentcomputer technologypopularity the information andcollected hasbeen network，the generated bypeople continually inthe and vastamountsofdatacontainrichand expandingsize，scopedepth．The complex the and informationbetween function，SO to itfurther． composition peopleexpectanalyze TheK-Means thatisbasedonthe isthemost clusteringalgorithm prototypetechnology used itis andefficientfor dataset． widelyclusteringmethods，becausesimple，fast large—scale ButtheK-Means Call be inthelimitedas used it clusteringalgorithmonly rangeexcessively ontheinitial astheselectionofinitial depends condition，such