K-平均算法的发明历史

K-means聚类是1956发明的。这种算法最常见的形式是称为劳埃德算法的迭代改进探索法。劳埃德算法首先将输入点分成k个初始化组，初始化组可以是随机的，也可以使用一些启发式数据。然后计算每组的中心点，根据中心点的位置将对象划分到最近的中心，重新定义分组。继续反复计算中心，重新分组，直到收敛，即对象不再改变分组(中心点的位置不再改变)。

劳埃德算法和K-average通常关系密切，但在实际应用中，劳埃德算法是解决K-average问题的启发式规则。对于起点和重心的某些组合，劳埃德算法实际上可能会收敛到错误的结果。(上述函数中有不同的最优解)

虽然有变化，劳埃德算法仍然流行，因为它在实践中收敛非常快。事实上，据观察，迭代次数远远小于点数。但最近David Arthur和Sergei Vassilvitskii提出，特定点集的存在使得K-average算法需要超多项式时间才能达到收敛。

设计了近似K-平均算法来计算原始数据子集。

从算法的性能来看，并不能保证得到全局最优解，最终解的质量很大程度上取决于初始化的分组。由于这种算法的速度很快，一种常用的方法是多次运行K-average算法，选择最优解。

K-average算法的一个缺点是数据包的数量K是一个输入参数，一个不合适的K可能会返回很差的结果。此外，该算法还假设均方误差是计算组离差的最佳参数。