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

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

作　　者：张顺龙[1,2] 库涛[1,2] 周浩 

机构地区：[1]中国科学院沈阳自动化研究所,沈阳110016 [2]中国科学院大学,北京100043 [3]吉化集团吉林市软信技术有限公司,吉林吉林132021

出　　处：《计算机应用研究》2016年第2期413-416,共4页Application Research of Computers

基　　金：国家科技支持计划资助项目(2012BAH15F05);吉林省科技型中小企业技术创新基金资助项目(12C26212201399);国家自然科学基金资助项目(612033161;51205389)

摘　　要：随着数据量、数据维度呈指数发展以及实际应用中聚类中心个数的增多,传统的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.

关 键 词：DIACK 加速K-means 聚类 三角定理 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]