一、原型聚类和层次聚类

原型聚类也称基于原型的聚类(prototype-based clustering)，这类算法假设聚类结构能够通过一组原型刻画，先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，产生不同的算法。常用的原型聚类算法有k-means算法。

层次聚类(hierarchical clustering)是一种基于原型的聚类算法，试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用"自底向上"的聚合策略，也可以采用"自顶向下"的分拆策略。层次聚类算法的优势在于，可以通过绘制树状图(dendrogram)，帮助我们使用可视化的方式来解释聚类结果。层次聚类的另一个优点就是，它不需要事先指定簇的数量。

二、凝聚层次聚类

层次聚类可以分为凝聚(agglomerative)层次聚类和分裂(divsive)层次聚类。分裂层次聚类采用的就是"自顶而下"的思想，先将所有的样本都看作是同一个簇，然后通过迭代将簇划分为更小的簇，直到每个簇中只有一个样本为止。凝聚层次聚类采用的是"自底向上"的思想，先将每一个样本都看成是一个不同的簇，通过重复将最近的一对簇进行合并，直到最后所有的样本都属于同一个簇为止。

在凝聚层次聚类中，判定簇间距离的两个标准方法就是单连接(single linkage)和全连接(complete linkage)。单连接，是计算每一对簇中最相似两个样本的距离，并合并距离最近的两个样本所属簇。全连接，通过比较找到分布于两个簇中最不相似的样本(距离最远)，从而来完成簇的合并。

凝聚层次聚类除了通过单连接和全连接来判断两个簇之间的距离之外，还可以通过平均连接(average linkage)和ward连接。使用平均连接时，合并两个簇所有成员间平均距离最小的两个簇。使用ward连接，合并的是使得SSE增量最小的两个簇。

三、全连接的凝聚层次聚类

基于全连接的凝聚层次聚类主要包括下面几个步骤：

1、获取所有样本的距离矩阵

2、将每个数据点作为一个单独的簇

3、基于最不相似(距离最远)样本的距离，合并两个最接近的簇

4、更新样本的距离矩阵

5、重复2到4，直到所有样本都属于同一个簇为止。

下面通过代表来实现基于全连接的凝聚层次聚类

1、获取样本

随机产生5个样本，每个样本包含3个特征(x、y、z)

2、获取所有样本的距离矩阵

通过SciPy来计算距离矩阵，计算每个样本间两两的欧式距离，将矩阵矩阵用一个DataFrame进行保存，方便查看

3、获取全连接矩阵的关联矩阵

通过scipy的linkage函数，获取一个以全连接作为距离判定标准的关联矩阵(linkage matrix)。

第一列表的是簇的编号，第二列和第三列表示的是簇中最不相似(距离最远)的编号，第四列表示的是样本的欧式距离，最后一列表示的是簇中样本的数量。

4、通过关联矩阵绘制树状图

使用scipy的dendrogram来绘制树状图

通过上面的树状图，可以直观的发现。首先是s1和s5合并，s2和s3合并，然后s2、s3、s4合并，最后再和s1、s5合并。

5、结合树状图和热度图

在实际应用中，可以将树状图和热力图结合使用，通过不同的颜色来代表样本矩阵中的独立值。

通过热力图与树状图结合，能够更加直观的发现特征对于簇划分的影响，不同颜色代表欧式距离的大小。

6、使用sklearn实现凝聚聚类

使用sklearn的AgglomerativeClustering可以很容易的实现凝聚聚类，需要设置返回簇的数量。