K-means clustering algorithm
在聚类的问题中，我们得到了一组训练样本集 
%7D%2C…%2Cx%5E%7B(m)%7D%5C%7D#card=math&code=%5C%7Bx%5E%7B%281%29%7D%2C…%2Cx%5E%7B%28m%29%7D%5C%7D&height=19&width=90)，然后想要把这些样本划分成若干个相关的“类群（clusters）”。其中的 
%7D%5Cin%20R%5En#card=math&code=x%5E%7B%28i%29%7D%5Cin%20R%5En&height=16&width=53)，而并未给出分类标签 
%7D#card=math&code=y%5E%7B%28i%29%7D&height=18&width=18) 。所以这就是一个无监督学习的问题了。
均值聚类算法如下所示：
- 随机初始化（initialize）聚类重心（cluster centroids）
。 - 重复下列过程直到收敛（convergence）: {
对每个 
，设
%7D%3A%3Darg%5Cmin_j%7C%7Cx%5E%7B(i)%7D-%5Cmu_j%7C%7C%5E2%0A#card=math&code=c%5E%7B%28i%29%7D%3A%3Darg%5Cmin_j%7C%7Cx%5E%7B%28i%29%7D-%5Cmu_j%7C%7C%5E2%0A&height=28&width=157)
对每个 
，设
%7D%3Dj%5C%7Dx%5E%7B(i)%7D%7D%7B%5Csum%7Bi%3D1%7D%5Em1%5C%7Bc%5E%7B(i)%7D%3Dj%5C%7D%7D%0A#card=math&code=%5Cmu_j%3A%3D%5Cfrac%7B%5Csum%7Bi%3D1%7D%5Em1%5C%7Bc%5E%7B%28i%29%7D%3Dj%5C%7Dx%5E%7B%28i%29%7D%7D%7B%5Csum_%7Bi%3D1%7D%5Em1%5C%7Bc%5E%7B%28i%29%7D%3Dj%5C%7D%7D%0A&height=41&width=155)
}
在上面的算法中，
是我们这个算法的一个参数，也就是我们要分出来的群组个数（number of clusters）；而聚类重心 
表示的是我们对各个聚类的中心位置的当前猜测。在上面算法的第一步当中，需要初始化（initialize）聚类重心（cluster centroids），可以这样实现：随机选择 个训练样本，然后设置聚类重心等于这 个样本 各自的值。（当然也还有其他的初始化方法。）
算法的第二步当中，循环体内重复执行两个步骤：（i）将每个训练样本%7D#card=math&code=x%5E%7B%28i%29%7D&height=16&width=20) “分配（assigning）”给距离最近的聚类重心；（ii）把每个聚类重心 移动到所分配的样本点的均值位置。下面的 图1 就展示了运行 均值聚类算法的过程。
图1： 均值聚类算法。图中的圆形点表示的是训练样本，交叉符号表示的是聚类重心。(a) 原始训练样本数据集。 (b) 随机初始化的聚类重心（这里的初始化方法就跟我们上面说的不一样，并没有从训练样本中选择两个点）。(c-f) 运行 均值聚类算法中的两步迭代的示意图。在每一次迭代中，我们把每个训练样本分配给距其最近的聚类重心（用同样颜色标识出），然后把聚类重心移动到所分配的样本的均值位置。（用颜色区分效果最好了。）图片引用自 Michael Jordan。
均值聚类算法能保证收敛性么？可以的，至少在一定意义上能这么说。尤其是我们可以定义一个下面这样的函数作为失真函数（distortion function）：
%3D%5Csum%7Bi%3D1%7D%5Em%20%7C%7Cx%5E%7B(i)%7D-%5Cmu%7Bc%5E%7B(i)%7D%7D%7C%7C%5E2%0A#card=math&code=J%28c%2C%5Cmu%29%3D%5Csum%7Bi%3D1%7D%5Em%20%7C%7Cx%5E%7B%28i%29%7D-%5Cmu%7Bc%5E%7B%28i%29%7D%7D%7C%7C%5E2%0A&height=40&width=160)
这样就可以用 
来衡量每个样本 %7D#card=math&code=x%5E%7B%28i%29%7D&height=16&width=20) 和对应的聚类重心
%7D%7D#card=math&code=%5Cmu_%7Bc%5E%7B%28i%29%7D%7D&height=13&width=23)之间距离的平方和。很明显能看出 均值聚类算法正好就是对 的坐标下降过程。尤其是内部的循环体中， 均值聚类算法重复对 进行最小化，当 
固定的时候用 
来最小化 ，当 固定的时候则用 最小化 。这样就保证了 是单调降低的（monotonically decrease），它的值也就必然收敛（converge）。（通常这也表明了 和 也收敛。在理论上来讲，均值 可能会在几种不同的聚类之间摆动(oscillate)，也就是说某些组不同值的 和/或 对应有完全相同的 值，不过在实践中这种情况几乎不会遇到。）
失真函数 ，是一个非凸函数（non-convex function），所以对 进行坐标下降（coordinate descent）并不一定能够收敛到全局最小值（global minimum）。也就是说， 均值聚类算法可能只是局部最优的（local optima）。通常除了这个问题之外， 均值聚类效果都不错，能给出很好的聚类。如果你担心陷入到某些比较差的局部最小值，通常可以多次运行 均值距离（使用不同的随机值进行来对聚类重心 进行初始化）。然后从所有的不同聚类方案（clusterings）中，选择能提供最小失真（distortion） #card=math&code=J%28c%2C%5Cmu%29&height=16&width=39) 的。
