基于改进Canopy-K-means算法的并行化研究

Research on Parallelization Based on Improved Canopy-K-means Algorithm

随着互联网数据的快速增长,原始的K-means算法已经不足以应对大规模数据的聚类需求;为此,提出一种改进的Canopy-K-means聚类算法;首先面对Canopy算法中心点随机选取的不足,引入“最大最小原则”优化Canopy中心点的选取;接着借助三角不等式定理对K-means算法进行优化,减少冗余的距离计算,加快算法的收敛速度;最后结合MapReduce框架并行化实现改进的Canopy-K-means算法;基于构建的微博数据集,对优化后的Canopy-K-means算法进行测试;试验结果表明:对不同数据规模的微博数据集,优化后算法的准确率较K-means算法提高了约15%,较原始的Canopy-K-means算法提高了约7%,算法的执行效率和扩展性也有较大提升。

With the rapid growth of Internet data,the original K-means algorithm is no longer sufficient to meet the clustering needs of large-scale data.To this end,an improved Canopy-K-means clustering algorithm is proposed.Faced with the shortcomings of the random selection of the center point of the Canopy algorithm,the“maximum and minimum principle”was introduced to optimize the selection of the Canopy center point;then the K-means algorithm was optimized with the help of the triangle inequality theorem to reduce redundant distance calculations and accelerate the convergence rate of the algorithm;finally combined with MapReduce framework parallelization to achieve improved Canopy-K-means algorithm.Based on the constructed Weibo dataset,the optimized Canopy-K-means algorithm is tested.The test results show that the accuracy of the optimized algorithm is about 15%higher than that of the K-means algorithm and about 7%higher than that of the original Canopy-K-means algorithm.The execution efficiency and scalability of the algorithm are also improved.Greatly improved.