K-means 的缺点，及后续的改进方案。
- 依赖初始化，不同的初始化对应结果可能不同——k-means++；
- 可能收敛局部最小——二分kmeans（或者多次运行，合并结果）
- 需要制定K值，即聚类中心的个数——iosdata；
- 异常值敏感——k-medium；
- 聚类结果为超球体——kernel、GMMs。
- 海量数据——minibachk-means
原始k-means
- 1 初始选择K个类别中心。
- 2 将每个样本标记为距离类别中心最近的那个类别。
- 3 将每个类别中心更新为隶属该类别所有点的中心。
- 4 重复2,3两步若干次直至终止条件（迭代步数，簇中心变化率，MSE等等）
k-means++
尝试解决初始化聚类中心的问题。
二分K-均值(bisecting K-means)
为了克服K-Means算法收敛于局部最小值的问题
算法的伪代码如下：
将所有的点看成是一个簇
当簇小于数目k时
对于每一个簇
计算总误差
在给定的簇上进行K-均值聚类,k值为2
计算将该簇划分成两个簇后总误差
选择使得误差最小的那个簇进行划分
注意：其中误差可以选择欧式距离等度量指标
IOSDATA
该算法能够在聚类过程中根据各个类所包含样本的实际情况动态调整聚类中心的数目。如果某个类中样本分散程度较大（通过方差进行衡量）并且样本数量较大，则对其进行分裂操作；如果某两个类别靠得比较近（通过聚类中心的距离衡量），则对它们进行合并操作。
该方法并不是真的不限制类别数，最终的类别数为输入类别数的1/2-2倍之间，而且该算法需要：预期的聚类中心数目Ko、每个类所要求的最少样本数目Nmin最大方差Sigma、两个类别对应聚类中心之间所允许最小距离dmin，四个参数，所以并不常用。
k-means,k-medians和k-medoids
区别在于如何计算一个中心点代表整个cluster（让N对N的计算变为N对1）：
k-means： 算中心点时，每个属性（attribute）单独算，距离函数是L2norm。每个属性可能是数据中没出现过的值。
k-medians： 算中心点时，每个属性单独算，距离函数是L1norm。每个属性是数据中出现过的值，但可能来至于不同数据点，所以中心点可能在数据中没出现过。这是attribute意义上的median。
k-medoids： 算中心点时，所有属性一起算，距离函数是自定。中心点在数据中出现过。这是数据点意义上的median。用处是处理非欧式空间的数据，比如分类问题。
Mini batch k-means
与K均值算法相比，数据的更新是在每一个小的样本集上。对于每一个小批量，通过计算平均值得到更新质心，并把小批量里的数据分配给该质心，随着迭代次数的增加，这些质心的变化是逐渐减小的，直到质心稳定或者达到指定的迭代次数，停止计算。
1：从数据集中随机抽取一些数据形成小批量，把他们分配给最近的质心
2：更新质心
Mini Batch K-Means比K-Means有更快的收敛速度，但同时也降低了聚类的效果，但是在实际项目中却表现得不明显。
（例子中时间并没有减少，待验证。）
一趟聚类（Onepass K-means）
简介
一趟聚类算法是由蒋盛益教授提出的无监督聚类算法，该算法具有高效，简单的特点。数据集只需要遍历一遍即可完成聚类。算法对超球状分布的数据有良好的识别，对凸型数据分布识别较差。 一趟聚类可以在大规模数据，或者二次聚类中，或者聚类与其他算法结合的情况下，发挥其高效，简单的特点；
算法流程
- 初始时从数据集读入一个新的对象
- 以这个对象构建一个新的簇
- 若达到数据集末尾,则转6,否则读入一个新的对象;计算它与每个已有簇之间的距离，并选择与它距离最小的簇
- 若最小距离超过给定的阈值r,转2
- 否则将对象并入该簇，并更新簇心，转3
- 结束
GMMs
使用 GMMs 有两个关键的优势。首先，GMMs 比 K-Means 在簇协方差方面更灵活；因为标准差参数，簇可以呈现任何椭圆形状，而不是被限制为圆形。K-Means 实际上是 GMM 的一个特殊情况，这种情况下每个簇的协方差在所有维度都接近 0。第二，因为 GMMs 使用概率，所以每个数据点可以有很多簇。因此如果一个数据点在两个重叠的簇的中间，我们可以简单地通过说它百分之 X 属于类 1，百分之 Y 属于类 2 来定义它的类。即 GMMs 支持混合资格。
EM法求解高斯混合模型参数：
1、初始化
2、估计步骤（E-step）
E就是Expectation的意思，就是假设模型参数已知的情况下，求隐含变量Z分别取z1,z2,...的期望，亦即Z分别取z1,z2,...的概率。在GMM中就是求数据点由各个 component生成的概率。
3、最大化步骤（M-step）
4、收敛条件
为了用可视化的方式解释它，我们可以看一下上面的图，特别是黄色的簇，我们以它来作为例子。分布在第一次迭代时随即开始，但是我们可以看到大部分的黄点都在分布的右侧。当我们计算一个概率加权和时，即使中心附近有一些点，但它们大部分都在右侧。因此，分布的均值自然会接近这些点。我们也可以看到大部分的点分布在「从右上到左下」。因此改变标准差来创建更适合这些点的椭圆，以便最大化概率加权和。
参考链接：
https://www.cnblogs.com/yixuan-xu/p/6272208.html
https://www.jianshu.com/p/d57060f29ff6
http://blog.pluskid.org/?p=40
https://www.jiqizhixin.com/articles/the-6-clustering-algorithms-data-scientists-need-to-know
https://blog.csdn.net/u011574296/article/details/52986943
http://hareric.com/2016/07/06/%E4%B8%80%E8%B6%9F%E8%81%9A%E7%B1%BB(One-Pass%20Cluster)%E5%8F%8Apython%E5%AE%9E%E7%8E%B0/