k-means可能是最简单的一种聚类方法，它通常也被当作一种基准方法，用于比较其他聚类方法的性能。它的基本思想是假定数据分布为k个簇(cluster)；所以，先随机或者按照某种启发式方法选择k个质心(cluster centroids)作为起始簇，然后为每个数据点寻找距离最近的质心，并把它分配(assign)给该质心对应的簇，处理完所有数据点后，重新给这k个簇更新质心到该簇所有点的平均值；然后，不断迭代，直到质心稳定不变。
这里我们给定 $N$ 个样本 $\brace{x^1,\dots,x^N}$ ，算法步骤如下：
- 随机初始化 $K$ 个质心 $\mu_1,\dots,\mu_K \in \Re^n$ ；
-
重复下面的步骤，直到收敛。
(1) 对每个样本 $i$ ，计算其应该属于的类：
\[c^i := \operatorname*{arg\,min}_j \Abs{x^i - \mu_j}^2\](2) 对每个类 $j$ ，重新计算该类的质心：
\[\mu_j := {\sum_{i=1}^N \mathrm{sign}(c^i=j) x^i \over \sum_{i=1}^N \mathrm{sign}(c^i=j)}\]
其中， $K$ 是我们假定的簇数； $c^i \in \brace{1,\dots,K}$ 是样本 $i$ 距离最近的质心所属的簇；函数 $\mathrm{sign}(c^i=j)$ 中等式为真时为1，否则为0。
k-means算法一定能保证收敛吗？形式化定义distortion function：
\[J(c,\mu) = \sum_{i=1}^N \Abs{x^i - \mu_{c^i}}^2\]其中，函数 $J$ 表示每个样本 $x^i$ 到相应质心 $c^i$ 的平方和，k-means算法收敛即是最小化 $J$ 。其实，算法步骤2的每个循环内都是在最小化 $J$ ：先固定质心，取距离质心最近的点分配到该类，这会最小化 $J$ ；再固定分类，然后重新调整该类内的质心，这也在最小化 $J$ 。所以，每个循环都是 $J$ 单调递减的过程，即k-means算法会收敛。
k-means算法虽然能保证收敛，但有时也可能得不到全局最优解：
- 随机选择的 $K$ 个初始质心的位置，最终可能会收敛到一个不太满意的局部最优解。二分k-means算法可以解决这种问题，即每次只把样本划分成两个簇，然后选择其中一个簇继续二分，直到达到 $K$ 个簇；选择标准是挑选可以最大程度最小化 $J$ 值的那个簇继续二分。
- 初始的 $K$ 值选择，如果不是很了解样本的大致分布情况，就不太好确定 $K$ 的大小。有一种预处理方法canopy算法，可以用来估计初始质心的数量和位置。