机器学习之聚类算法

聚类是一种非监督式学习算法，它不要求源数据集有标签，一般应用于做数据探索性分析，聚类算法的结果是将不同的数据集按照各自的典型特征分成不同类别，不同人对聚类的结果解读可能不同。
总体上来说，聚类算法分为层次聚类(Hierachical Methods)和划分聚类(Partitioning Methods)。

一、层次聚类

层次聚类不需要指定类数，按策略不同可分为自底向上的聚类方法(agglomerative hierarchical clustering),比如AGNES和自上向下的聚类方法(divisive hierarchical clustering)，比如DIANA。

1、自底向上的聚类方法
算法思想：
将每个点都看成一个簇；
将两个最近的簇合并为一个簇；
不断重复上述过程，直到达到预期簇或簇之间的距离满足要求为止。

2、自上向下的聚类方法
算法思想：
将样本的每个点都看成一个簇；
然后找出簇中距离最远的两个簇进行分裂；
不断重复到预期簇或者满足终止条件为止。

如何判断两个簇之间的距离
有三种不同的计算形式：
①、单链接聚类：
一个簇的所有成员到另一个簇的所有成员之间的最短两点之间的距离。
②、全连接聚类：
两个簇中最远的两个点之间的距离。
③、平均连接聚类：
两个簇中的点两两距离求平均值。

层次聚类如下图所示：

二、划分聚类
划分聚类的方法有很多，主要有K-Means、K-Means++、Mini Batch K-Means。
1、K-Means算法
该算法需要事先指定类数，算法的思想是初始随机给K个簇中心，按照距离最近原则把待分类的样本点分到各个簇，然后按平均法重新计算各个簇的质心，从而确定新的簇心，迭代计算，直到簇心的移动距离小于某个给定的误差值。具体有三个步骤：
①、任意选择K个点作为初始聚类中心；
②、计算每个样本点到各个聚类中心的距离，将每个样本点划分到离该点最近的聚类中去；
③、计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心。
反复执行②③，直到聚类中心的移动小于某误差值或者聚类次数达到要求为止。

计算点与点之间距离的方法通常是计算欧式距离：

聚类结束后判断聚类的好坏程度——损失函数：每一次选好新的中心点，我们就要计算一下当前选好的中心点的损失为多少，这个损失代表着偏移量，越大说明当前聚类的效果越差，计算公式为：

K-Means算法的缺陷：
①、K值需要预先给定，属于预先知识，很多情况下K值的估计是非常困难的；
②、K-means算法对初始选取的聚类中心点是敏感的，不同的随机种子点得到的聚类结果完全不同。

2、K-Means++算法
K-Means算法解决了K-Means算法的第二个缺陷，它在选取初始聚类中心点的方法上与K-Means算法不同，其中心思想是：初始的聚类中心点之间的相互距离要尽可能远。算法步骤如下：
①、随机挑选一个点作为第一个聚类中心点；
②、计算每一个点到最近的一个聚类中心点的距离D(x)，将所有的距离求和得到Sum(D(x))；
③、以正比于D(x)的概率随机选择一个中心点为新的中心点（即每个点的距离D(x)/距离和Sum(D(x))作为该点为下一个中心点的概率）。
重复②和③，直到K个聚类中心点全被选出来，再利用这K个初始聚类中心进行K-Means算法。
如下图所示：

K-Means++算法依旧需要预先给定K值，没有解决K-Means的第一个缺陷。

3、Mini Batch K-Means算法

适用于数据样本较大的情况下，使用Mini Batch（分批处理）的方法对数据之间的距离进行计算。
MiniBatch的好处：不必使用所有的数据样本，而是从不同类别的样本中取出一部分样本来代表各自类型进行计算。由于计算样本量少，所以会相应的减少运行时间，但另一方面抽样也必然会带来准确度的下降。

在3万样本点的基础上，使用 K-Means算法和Mini Batch K-Means算法聚类进行比较：

可以看出，二者的运行时间相差2倍多，但聚类结果差异却很小（右侧粉红色的错误点）。