龚运鸿，周新志，雷印杰

(四川大学 电子信息学院，成都 610065 )

0 引言

随着程序需要处理的数据量越来越庞大，现如今以GB或TB为单位的数据集已经十分普遍了，数据挖掘中必须重视的一个问题就是如何高效得处理如此庞大的数据。即使算法的复杂程度是线性增长的，时间和空间的消耗也不容忽视。K均值聚类算法由Stuart Lloyd等人在1957年第一次提出[1]，K均值聚类算法源于信号处理的一种矢量量化方法，由于其概念简单、收敛速度快、易于实现等特点，现如今在数据挖掘领域聚类分析中十分流行。然而K均值聚类算法的复杂度比较高，如何高效进行算法计算是一个急切的研究方向。目前，陶冶[2]等人证明并实现了并行K均值聚类算法。喻金平[3]等人提出一种改进的人工蜂群算法，解决了K均值算法的搜索能力差的问题。霍莹秋[4]等人提出分块、并行的K均值聚算法，采用“合并访问”、“多级规约求和”和“负载均衡”等优化策略优化并行算法，提高了算法的运行速度。对于K均值聚类并行计算的研究还存在许多缺陷，比如没有针对CUDA并行计算平台进行优化，也没有针对中心点更新效率问题提出解释等。根据以上研究的缺陷，本文利用NVIDIA的CUDA并行平台，在传统K均值算法基础上，采用了一种滑动门并行计算中心点算法优化K均值算法更新中心点的耗时问题。通过与规约法计算中心点算法相比，获得了很好的加速比。

1 CUDA并行计算平台

随着社会的发展，CPU逐渐达到了速度极限并且购置成本也在急速上升。……