一、工作流程
首先，随机确定k个初始点作为质心。然后为数据集里的每个点找到与它距离最近的质心，将其分配到该质心所对应的簇。这一步完成后，每个簇的质心都更新为该簇所有点的平均值。伪代码如下：
创建k个点作为起始质心 当任意一个点的簇分配结果发生改变时 对数据集中的每个数据点 对每个质心 计算质心与数据点之间的距离 将数据点分配到距其最近的簇 对每一个簇，计算簇中所有点的均值并将均值作为质心
二、改进
一种用于度量聚类效果的指标是SSE(Sum of Squared Error,误差平方和)，所谓的误差是指一个点到它所在的簇的质心的距离。SSE值越小，标示数据点越接近它们的质心，聚类效果也越好。可以将最大的簇划分为两个簇，再把别的两个簇进行合并来实现这一目标（合并最近的质心，或者合并两个使得SSE增幅最小的质心）。为了克服K-均值算法收敛于局部最小值的问题，有人提出了一个称为二分K-均值算法的方案。该算法首先将所有点作为一个簇，然后将该簇一份为二，之后选择其中一个簇继续进行划分，选择哪一个簇进行划分取决于对其划分是否可以最大程度降低SSE的值。上述基于SSE的划分过程不断重复，直到得到用户指定的簇数目为止。