K-Means Algorithm

K-Means算法是一种聚类（Clustering）算法，属于非监督学习算法(Unserpvised Learning)的一种，它可以根据数据的分布特典自动对数据进行分类。应用的场景包括市场划分(Market Segmentation), 分割服务器集群，社交网络集群分割，等等。

算法步骤

K-Means的算法步骤可以如下图所列：

其中第一个for循环叫Cluster Assignment Step, 第二步叫Move Centroid Step。

优化目标

此算法的优化目标函数或者叫失真损失函数(Distrorion Cost Function)如下图所示：

在数学上可以证明，K-Means算法每次迭代，损失函数都会逐步减小。

证明如下：

通过第一个for循环可以计算出ci$c^i$，J可以重写为：

可以看出相对于μci${\mu }_{c^i}$每部分都是独立的，所以求J的最小值，就是求每部分的最小值，以J1=1N1∑N1i=1||xi−μc1||2$J_1=\frac{1}{N_1}\sum _{i=1}^{N_1}||x^i-{\mu }_{c^1}|{|}^2$为例:

令一阶导数等于0，可得μc1=1N1∑N1i=1xi${\mu }_{c^1}=\frac{1}{N_1}\sum _{i=1}^{N_1}{x}^i$，又因为∂2J1∂μ2c1=2>0$\frac{{\mathrm{\partial }}^2{J}_1}{\mathrm{\partial }{\mu }_{c^1}^2}=2>0$，所以为最小值。这正是算法第二步更新的值。

一点题外话：上一步的计算用到了矩阵微积分，其实J1$J_1$是标量，对向量μc1${\mu }_{c^1}$求导，其实就是对向量中的每个维度求导，结果还是一个向量，使用矩阵或者向量的形式来写，可以简化书面表达和计算。归根结底，矩阵微积分是属于多元微积分的范畴。

K值初始化

不难想象，不同K值初始化，算法的最终结果会有不同。

如上图所示，K值得选取可能会使算法收敛到局部极值。
有一种解决办法是，做多次随机初始化并运行算法，然后从中选出最优解。

在实际应用中，如果K的个数比较小，例如在2到10个之间，那么这个方法大概率会奏效。但是如果K的个数过于庞大，例如几百个，这个方法的结果大概率不尽人意。

K值个数的选取

有一种方法叫Elbow Method：

按K值从小到大，依次运行算法，比较损失函数的大小，然后进行如图中的选择。但是这个方法的缺点是，在实际应用中，K-J曲线一般比较平滑，这样对K的个数的选择就比较困难。

另外一种更为推荐的方法如下图所示：

通常运行K-Means算法是为了后面更进一步应用这个结果，所以K值个数应当由后续具体应用来决定。图中给了一个例子：例如想根据数据来决定生产T-shirt的大小，可以先考虑到底想生产出几种大小，这个时候可根据具体情况来决定(3种？5种？)。然后再根据算法来算出最佳各种大小的尺码。

以上截图均来自Coursera的ML.