1. Intro
聚类算法中最经典的要算是 K-means 了。其中 K 代表划分的 cluster 的 数目，而 means 则是算法的核心概念——centroid（质心）
2. Basic K-means
K-means 是一个迭代算法，以最终 converge 为终止条件。
pseudo code：
SELECT K INITIAL CENTROIDS;
while(true)
foreach point:
Compute the distance to every centroid;
Label this point as the cluster corresponding to the nearest centroid;
re-calculate K centroids;
if (all centroids no longer change)
break;
1. 初始选取K 个 centroid；
2. 以 centroid 代表 cluster。计算每个点距离哪个 centroid 最近，
将该点标记为属于最近 centroid 对应的 cluster。然后计算每一个 cluster 的新的 centroid。
3. 重复2直到所有 centroid 不再改变
(对于欧氏空间？) 衡量聚类效果的好坏以平方误差和（sum of the square error, SSE）作为目标函数:
Paste_Image.png
可以将第一个求和号右边部分视为求每一个簇的簇SSE, 对所有的簇SSE求和，就得到总 SSE。
3. k-means存在缺点：
k-means是局部最优的，容易受到初始质心的影响；比如在下图中，因选择初始质心不恰当而造成次优的聚类结果（SSE较大）：
另外 basic K-means 容易形成 empty cluster
Paste_Image.png
4. 优化
对于empty cluster 我们的策略是当选取 initial centroid 的时候，随机选取真实的点作为initial centroid，这样就有效避免出现某个 cluster 里面没有点。
对于收敛于局部最优的缺点，我们通过 bisecting K-means 来解决。其基本思想是：
初始只有一个cluster包含所有样本点；
repeat for (K-1) times: //(k-1)次后就得到 k 个 clusters
从待分裂的clusters中选择一个进行二元分裂，所选的cluster是具有最大的 簇SSE 的簇；
这里选取待分裂簇的判断标准我不同意http://www.cnblogs.com/en-heng/p/5173704.html 这篇博客里面的说法，所选的 cluster 应使得 SSE 最小，这样的说法太过于笼统。
直接参考《数据挖掘导论》316页结论就好：分裂一个簇通常选取 SSE 最大的簇。因为一个簇的 簇SSE 越大，说明这个簇越离散，需要进一步分解。
