k-means算法是机器学习中一种经典的被广泛应用的无监督学习算法。k-means算法在处理大规模聚类场景下的效率提升具有重要研究价值,本文为提升k-means算法在大数据场景下的效率提出了两种改进方案,第一种是基于粒球划分的精确kmeans加速算法,第二种是基于近邻信息的近似k-means加速算法。本文提出的第一种改进k-means算法称为Ball k-means,是一种精确加速算法,通过粒球模型来描述一个簇类。该算法主要通过减少数据点与聚类中心之间的不必要的距离计算从而达到降低运行时间来提高效率的目的。该算法中的近邻搜索方式可以准确地为每个粒球找到其近邻粒球,从而使得一个数据样本点仅仅需要计算到其相邻近的粒球的聚类中心的距离;此外,每个粒球还可以被划分为“稳定域”和“活动域”,而“活动域”可以进一步划分为许多“环形域”。“稳定域”中的数据点在当前迭代轮次中不会更改,而“环形域”中的点在当前迭代轮次中将在一些近邻粒球之间进行调整;另外,还设计了一种方法来降低每轮迭代中粒球球心之间的欧式距离计算;针对k-means算法在后期迭代过程中越来越多的粒球会逐渐趋于“不变”,本文提出了一种方法能够找到这些粒球,并证明了这些粒球不需要重新建立粒球,粒球里面的数据样本不需要参与本轮迭代中的分配步骤;最后,通过理论分析和在真实数据集以及人工合成的数据集上的实验结果表明,该算法的性能优于最新的精确加速k-means算法,尤其是在处理大k聚类问题时。Ball k-means算法设计简单、无需额外参数使其能够完全替代Lloyd k-means算法。在某些应用中,对于聚类结果的质量要求不高,即允许部分的聚类结果不准确,但需要快速得到聚类结果。因此,本文提出了第二种基于近邻信息的快速近似kmeans聚类算法。基于观察发现,在k-means迭代过程中,每个粒球中的数据样本只在其周围邻近的粒球范围之间调整。为此,本文通过一种局部化策略来将k-means算法的分配步骤中参与的粒球缩小到一个较小的范围;此外,为了维稳所提出算法的聚类质量,本文还提出了一种新的近邻更新方式,将近邻的近邻当作候选近邻,进而在后续迭代轮次中用候选近邻粒球来进行k-means算法的分配步骤,从而避免了维持最初的近邻关系导致最终聚类结果的质量损失。最后,在真实数据集中验证本算法的有效性,在多个数据集的时间性能上相对于Lloyd k-means算法达到了成百上千倍的加速,而平均仅有1.10%左右的聚类质量损失。本文提出了两种快速高效的k-means聚类方法,为大规模聚类场景下的快速聚类需求提供了两种不同的解决方案。