在聚类问题中，给定一个训练集，算法根据某种策略将训练集分成若干类。在监督式学习中，训练集中每一个数据都有一个标签，但是在如果分类问题中没有标签，我们可以将聚类算法称之为非监督式学习算法。这两种算法最大的区别还在于：监督式学习有标签，而非监督式学习没有标签。那么这里可以理解为标签实际上就是一种监督性质的分类，而无标签根据分布性质，那么我们称之为聚类。感兴趣同学可以查阅半监督学习。
算法的核心目标就是将给定的数据集分成 k 类，具体做法为：
1、随机选取k个簇中心（cluster centroids）记为μ1,μ2,...,μk∈Rn 2、重复下面过程直到收敛 { 对于每一个样例 i ，计算其应该属于的类 c(i)=arg minj∥x(i)−μj∥2 对于每一个类j，重新计算该类的质心 μj=∑mi=11{c(i)=j}x(i)∑mi=11{c(i)=j} }K 是我们事先给定的聚类数，c(i) 代表样本 i 与k个簇中距离最近的那个簇的下标， c(i) 的值是1到 k 中的一个。质心μj 代表我们对属于同一个类的样本中心点的猜测。程序就这样反复进行直到收敛或者簇中心基本不动。
算法过程可以如下图示意，其中k取2：
K-means面对的一个重要问题是如何保证收敛，前面的算法中强调结束条件就是收敛，可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性，我们定义畸变函数（distortion function）如下：
J(c,μ)=∑i=1m∥x(i)−μc(i)∥2
J 函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前 J 没有达到最小值，那么首先可以固定每个簇中心μj，调整每个样例的所属的类别 c(i) 来让 J 函数减少，同样，固定c(i) ，调整每个簇中心 μj 也可以使 J 减小。这两个过程就是内循环中使J单调递减的过程。当 J 递减到最小时，μ和c也同时收敛。（在理论上，可以有多组不同的 μ和c 值能够使得 J 取得最小值，但这种现象实际上很少见）。其实整体来看，这个算法就是坐标上升算法. 如果畸变函数J是非凸函数，意味着我们不能保证取得的最小值是全局最小值，也就是说k-means对簇中心初始位置的选取比较敏感，但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优，那么可以选取不同的初始值跑多遍k-means，然后取其中最小的 J 对应的μ和c输出。
K-Means聚类算法的优点主要集中在:
算法快速、简单; 对大数据集有较高的效率并且是可伸缩性的; 时间复杂度近于线性，而且适合挖掘大规模数据集。K-Means聚类算法的时间复杂度是 O(nkt) ,其中 n 代表数据集中对象的数量，t代表着算法迭代的次数， k 代表着簇的数目。k-means 算法缺点 1. 在 K-means 算法中K是事先给定的，这个 K <script type="math/tex" id="MathJax-Element-1216">K</script>值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 K-means 算法的一个不足。 2. 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 K-means算法的一个主要问题。对于该问题的解决，许多算法采用遗传算法（GA），例如文献中采用遗传算法（GA）进行初始化，以内部聚类准则作为评价指标。 3. 从 K-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。所以需要对算法的时间复杂度进行分析、改进，提高算法应用范围。在文献中从该算法的时间复杂度进行分析考虑，通过一定的相似性准则来去掉聚类中心的侯选集。而在文献中，使用的 K-means 算法是对样本数据进行聚类，无论是初始点的选择还是一次迭代完成时对数据的调整，都是建立在随机选取的样本数据的基础之上，这样可以提高算法的收敛速度。
参考文献： http://blog.csdn.net/xiaocainiaodeboke/article/details/50611890
