摘要：
1.算法概述
2.算法推导
3.算法特性及优缺点
4.注意事项
5.实现和具体例子
6.适用场合
内容：
1.算法概述
k-means算法是一种得到最广泛使用的聚类算法。 它是将各个聚类子集内的所有数据样本的均值作为该聚类的代表点。
2.算法推导
2.1 k-means 计算过程：
深入：如何验证收敛：
我们定义畸变函数（distortion function）如下：
J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当前J没有达到最小值，那么首先可以固定每个类的质心
，调整每个样例的所属的类别
来让J函数减少，同样，固定
，调整每个类的质心
也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时，
和c也同时收敛。
2.3 期望最大化（EM）：
EM算法（Expectation Maximization）是在含有隐变量（latent variable）的模型下计算最大似然的一种算法
其中Z是隐变量，theta是待定参数;
E-step是固定参数theta,求Z的期望;M-step是theta的极大似然估计
引申：使用EM算法推导K-means:
k-means算法是高斯混合聚类在混合成分方差相等，且每个样本仅指派一个混合成分时候的特例。k-means中每个样本所属的类就可以看成是一个隐变量，在E步中，我们固定每个类的中心，通过对每一个样本选择最近的类优化目标函数，在M步，重新更新每个类的中心点，该步骤可以通过对目标函数求导实现，最终可得新的类中心就是类中样本的均值。
深入：EM的收敛性证明
3.算法特性及优缺点
特性：本算法确定的k个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。
优点：
（1）原理简单，实现容易；
（2）对于处理大数据集，这个算法是相对可伸缩和高效的
（3）当簇近似为高斯分布时，它的效果较好
缺点：
（1）在簇的平均值可被定义的情况下才能使用，可能不适用某些应用
（2）初始聚类中心的选择比较敏感，可能只能收敛到局部最优解（改进：选取距离尽可能远的点作为初始聚类 实现kmeans++）
（3）必须事先确定K的个数 （根据什么指标确定K）
（4）算法复杂度高O(nkt)
（5）不能发现非凸形状的簇，或大小差别很大的簇
（6）对噪声和孤立点数据敏感
4.注意事项
归一化：基于距离的算法都需要进行无量纲化，防止样本在某些维度上过大导致距离计算失效
后处理：具有最大SSE值的簇划分为两个簇，具体实现只要将属于最大簇的数据点用K-均值聚类，设定簇数k=2即可。
为了保证簇总数不变，可以合并最近的质心，或者合并两个使得SSE值增幅最小的质心。
5.实现和具体例子
《机器学习实战》中的k-mean和二分k-means以及基于地点坐标的聚类
spark mllib的kmeans实现;spark mllib的二分k-means(BisectingKMeans)--有时间研究下
互联网防刷（反作弊）-- 近期计划
6.适用场合
支持大规模数据
特征维度
是否有 Online 算法:有，spark mllib的流式k均值
特征处理：支持数值型数据，类别型类型需要进行0-1编码
原文：http://www.cnblogs.com/arachis/p/KMeans.html