1. 没有k-means算法。K-means是问题所在。它的算法包括 MacQueen、Lloyd/Forgy、Hartigan/Wong 等等。

2. 大多数这些算法（我猜几乎是详尽的搜索）只会找到局部最优，而不是全局最优。它们是启发式的。快速启发式...

3. 事实证明，如果集群大小变化很大，通常的最近中心启发式有时甚至会错过局部最优值。不是很多。但极少情况下，不应将点分配到最近的中心。

4. 全局最优搜索是 IIRC NP-hard，所以你不想使用完美的算法，除非你假设 P=NP。

K-means 聚类并不能保证您的全局最优（尽管我不会将 K-means 称为“启发式”技术）。但是您可以这样做：运行 K-means 多次，每次使用不同的随机初始中心种子，每次都获得一组最终聚类中心。如果这些集合看起来足够相似——从某种意义上说，你可以很容易地在运行中识别“相同”的最终中心——那么你肯定接近全局最优值。然后在运行中平均那些相应的最终中心，并将获得的平均中心作为最终运行的初始中心输入。那次运行几乎肯定会为您提供全局最优解。

另一个与此类似的获得“好的”初始中心的技巧是将总样本随机分成子样本并在每个子样本上执行 K-means，然后再次对最终中心进行平均并对总样本进行聚类。还有一种获得“好的”初始中心的方法是首先运行 Ward 层次聚类并获得 K 个集群，并将它们的中心用作 K-means 的输入。阅读有关K-means 初始化的一些变体。

在以下条件（或“假设”）下，您更有可能在 K-means 聚类中获得全局最优解：

• 数据中存在簇结构，即数据不是单簇的；
• 您的 K（簇数规范）是正确的；
• 变量的数量不是很大：K-means 对“维度灾难”很敏感，变量很多，初步的 PCA 是个好主意；
• 数据中的簇或多或少呈球形，中间紧凑（如正态分布）；集群中的方差大致相等。

K-means 在每次迭代时将每个对象分配给最近的聚类中心。如此分配所有对象后，更新 K 个中心。因此，一个中心似乎进一步朝着已经是“它的”对象的对象集移动。这就是为什么每次迭代都是一种改进，并且达到了最优——局部或全局，取决于初始中心的选择。优化后的函数是合并的簇内平方和（因为均值是与其最小 SS 偏差的轨迹），这相当于最小化由相应数归一化的成对平方欧几里德距离的合并簇内总和 -集群中的对象。

您实际上可以证明它收敛到局部最小值，并且实际上，您正在对量化误差函数执行牛顿最小化。所有细节都在 Léon Bottou 和 Yoshua Bengio 的论文“Convergence Properties of the K-Means Algorithms”中

这种类型的聚类的目标函数是以最小化到质心的平方距离之和的方式将点分配给聚类。然而，使用K-Means我们（大约）解决了一个不同的问题，它与我们的原始问题具有相同的最优解：

$$\begin{align} &\min_{x} \sum_{i=1}^n \sum_{j=1}^k x_{ij} || p_i - y_j||^2\\ &\text{subject to:} \\ &\sum_{j=1}^k x_{ij} = 1 \quad \forall i\\ &x_{ij} \in \{0,1\} \quad \forall i, j \\ &y_j \in \mathbb{R}^d \quad \forall j \end{align}$$

我们不是最小化到质心的距离，而是最小化到任何一组点的距离，这将提供更好的解决方案。事实证明，这些点正是质心。

在这篇文章中，我已经详细解释了 K-Means 的两个步骤是如何近似解决这个优化问题的。