针对多聚类中心大数据集的加速K-means聚类算法

Accelerate K-means for multi-center clustering of big datasets

随着数据量、数据维度呈指数发展以及实际应用中聚类中心个数的增多,传统的K-means聚类算法已经不能满足实际应用中的时间和内存要求。针对该问题提出了一种基于动态类中心调整和Elkan三角判定思想的加速K-means聚类算法。实验结果证明,当数据规模达到10万条,聚类个数达到20个以上时,本算法相比Elkan算法具有更快的收敛速度和更低的内存开销。

The K-means algorithm is the most popular cluster algorithm, but for big dataset clustering with many clusters, it will take a lot of time to find all the clusters. This paper proposed a new acceleration method based on the thought of dynamical and immediate adjustment of the center K-means with triangle inequality. The triangle inequality was used to avoid redundant distance computations; But unlike Elkan＇ s algorithm, the centers were divided into outer-centers and inner-centers for each data point in tl^e first place, and only the tracks of the lower bounds to inner-centers were kept; On the other hand, by adjus- ting the data points cluster by cluster and updating the cluster center immediately right after finishing each cluster＇ s adjust- ment, the number of iteration was effectively reduced. The experiment results show that this algorithm runs much faster than Elkan＇ s algorithm with much less memory consumption when the cluster center number is larger than 20 and the dataset re- cords number is greater than 10 million, and the speedup becomes better when the k increases.