k均值是人工智能领域最常用的快速基础算法之一，广泛应用于聚类、数据预分析和其他机器学习算法的改进等。 为了进一步提高k均值算法的效率，许多优秀的k均值算法通过保持每个样本上下边界来减少样本距离计算次数，达到加速目的。 第一个Elkan以及在此基础上发展起来的harmly、ann、exp、yingyang等。 由重庆邮电大学迷路路灯与精心草丛共同提出的多粒度粒球计算理论(Xia S，Liu Y，Ding X，wangge tal.granularballcomputingclassifiersforefficient， 使用salableandrobustlearning [ j ].information sciences，2019，48:136-152.)、使用球体来划分度量空间簇，提出了一种简单、高效的Ball-k-means算法。超球体量化空间簇3358 www.Sina.com/: https://www.researchgate.net/publication/342914449 _ a _ fast _ adaptive _ k-means _ wit tttt
原文链接：定义1 (集群) )。
这个概念是多粒度-粒球计算理论(Xia S，Liu Y，Ding X，wangggetal.granularballcomputingclassifiersforefficient，salableandrobustlearning [ j 48:136-152.)可以通过用称为超球体的最简单模型(无论数据的维度如何，只有半径和中心两个参数)量化和表示簇来获得簇
定义2 (邻近集群) )
可下载链接:其距离计算范围从所有点限制在其邻近球内部。 一个集群的点在下一次迭代中只在其相邻集群中进行调整，不需要计算该集群中点到所有其他点的距离，计算次数减少）。
邻近球的关系示意图如图1所示。 因为C1和C2是C3的邻居，而C4不是C3的邻居，所以C3的点被分配给C1和C2，并且可能不被分配给C4。
图1 .邻居集群关系示意图
省略证明过程，具体证明过程为一、核心基本概念
二、使用近邻球簇可大大缩减了一个球簇内的点在下一次的迭代中的距离计算范围各集群内部进一步分为稳定区和活动区，具体定义如下3。该特性由定理1保证
如图2所示，球C1有两个邻近簇C2和C3，其稳定区由C2确定，是被绿色虚线包围的区域。
图2 .邻居集群关系示意图
省略证明过程，具体证明过程为可参见原文
三. 3358www.Sina.com/活动区域分成环后(具体定义见定义4 )，球簇内部量化，进一步加速图2所示，第一层环(绿色虚线和蓝色虚线之间)内的点稳定域中的点不需要在下一次迭代中进行调整，因此这些点在下一次迭代中的距离计算次数为零，该特性由定理2保证。
省略证明过程，具体证明过程为可参见原文
四.为了降低求近邻集群过程中集群与集群中心的距离计算次数，降低近邻集群的距离计算次数，如图球簇活动域划分为环，进一步加速图3所示，Cj不能通过以下迭代成为Ci的近邻球。
因此下一次迭代中不需要计算两者之间的距离。证明过程省略，具体可参见原文。
图 3. Cj在下一次迭代中不可能成为Ci的近邻球
五、稳定簇这是最终的加速过程。对于某个球簇，如果一个簇中的点没有发生任何变化，我们称之是稳定的。如果一个簇的近邻簇在上一代都是稳定簇，那么该簇在当前迭代过程中不需要参与任何计算。该特性由定理5保证。随着迭代过程的推进，稳定簇会越来越多，基于稳定簇的算法加速作用也会越来越明显。
证明过程省略，具体可参见原文。
六、时间复杂度分析以下是与其他算法的时间复杂度分析对比，具体请参见原文。
结论Ball k-means 突破了现有大多数优秀精确k-means算法基于单一样本上下界约束调整的思路，消除了单一样本需要维护的上下界，实现个一个更加精确、简单和自适应的计算过程。整体算法简单、高效。
本文的c语言源代码，以及python调用版本可从以下链接下载（包含单精度和双精度两种版本），执行速度远高于sklearn中的k-means算法。欢迎大家使用（请引用原文：S. Xia et al., "A Fast Adaptive k-means with No Bounds," in IEEE Transactions on Pattern Analysis and Machine Intelligence, doi: 10.1109/TPAMI.2020.3008694.）并提出宝贵意见：
https://github.com/syxiaa/ball-k-means；
http://www.cquptshuyinxia.com/ball-k-means.html.
欢迎大家多多交流，多提宝贵意见：xiasy@cqupt.edu.cn；380835019@qq.com.