k-means算法被誉为十大经典数据挖掘算法之一,自被提出以来就因其高效的特性而被广泛应用于各个领域。但是,随着互联网的深入发展,网络上的数据呈爆发式增长,使得k-means算法的效率在大数据场景中面临挑战。为了进一步提升k-means算法的效率,本文分别针对精确k-means算法和近似k-means算法各提出了一种加速策略。本文的具体工作如下:1.本文针对精确k-means算法提出了一种基于多粒度的近邻球框架。该框架借用了Ball k-means算法提出的近邻球的概念,针对目前部分快速精确k-means算法上下界宽松,约束力不强的问题,提出在近邻球的基础之上来更新上下界。该框架从两个方面实现了加速:首先,该框架通过使用近邻球的概念,缩小了样本点的搜索范围;其次,该框架可以让每个样本点获得约束力更强的上界和下界。为了验证该框架的有效性,文章对应用框架后的代表算法与部分精确k-means算法进行了时间复杂度分析,还将这些算法在真实数据集上进行了效率对比,实验结果表明,使用近邻球框架之后的算法在大部分数据集上比其他快速精确kmeans算法的效率更高。2.本文提出了一种基于多粒度的快速近似k-means算法。该算法从两个不同的角度实现了加速:首先,该算法直接利用上一轮迭代过程中的信息来为每个簇寻找近邻簇,进而快速缩小样本点的搜索范围;其次,该算法利用上下界的条件快速减少了需要参与分配过程的样本点的数量。为了验证该算法的有效性,本文在不同规模和不同维度的真实数据集上进行了实验。实验结果表明,该算法在平均聚类质量损失约为2%左右的情况下可以使得算法的效率比Lloyd算法快几十到几百倍。