k 均值聚类算法的工作流程是这样的：首先选取 k 个点，作为初始 k 个簇的中心（这个 k 是人为设定的超参数），然后将其余的数据对象分配到距离自己最近的簇中心所在的簇中。假设样本集中有 l 个样本，每个样本都是一个具备 n 个特征，用向量 xi 表示第 i 个样本。现在我们假设要把所有样本划分为 k 个簇，即：
S={S1, S2, ......, SK}
这里 Sl(1≤l≤k) 表示第 l 个簇，S 是由若干簇构成的簇集合。
那么，最优的分配方案就是优化如下目标函数的解：
其中，μi 簇中的均值向量，有的文献也称之为质心（centroid），共有 k 个，因此这个算法叫作 k 均值聚类算法。由于以上公式所示的组合优化问题是一个 NP 难题，通常难以求得最优解，只能求得近似解。因此在实现过程中，通常采用循环迭代的方式，逐步收敛到局部最优解处。
当所有的点均被划分到某一个簇后，要再对各个簇中心（μi）进行更新。更新的依据是，根据每个聚类对象的均值，计算每个对象到簇中心的距离最小值，直到满足一定的条件才停止计算。这个条件一般为函数收敛（比如前后两次迭代的簇中心足够接近）或计算达到一定的迭代次数。
k 均值聚类算法的过程如图 1 所示。
图 1：k 均值聚类算法的过程
在 k 均值聚类算法中，我们主要需要考虑两个关键问题：初始簇中心（也称质心）的选取及距离的度量。常见的选取初始簇中心的方法是随机挑选 k 个点，但这样形成的簇质量往往很差。
因此，我们采用其他常用方法挑选初始簇中心，具体如下：
- 多次运行调优。每次使用一组不同的随机初始簇中心，最后从中选取具有最小平方误差的簇集。这种方法简单，但效果难料，主要取决于数据集的大小和簇的个数k；
- 根据先验知识（即历史经验）来决定 k 值。
对于另一个因素—如何确定对象之间的距离，根据问题场景不同，度量方式也是不同的。在欧式空间中，我们可以通过欧氏距离来度量两个样本之间的距离，而对于非欧式空间，可以选择 Jaccard 距离、Cosine 距离或 Edit 距离等度量方式。
