在本节，我们将学习另一种基于原型的聚类：层次聚类（hierarchical clustering）。层次聚类算法的一个优势在于：它能够使我们绘制出树状图（dendrogram，基于二叉层次聚类的可视化），这有助于我们使用有意义的分类法解释聚类结果。层次聚类的另一优势在于我们无需事先指定簇数量。
层次聚类有两种主要方法：凝聚（agglomerative）层次聚类和分裂（pisive）层次聚类。在分裂层次聚类中，我们首先把所有样本看作是在同一个簇中，然后迭代地将簇划分为更小的簇，直到每个簇只包含一个样本。本节我们将主要介绍凝聚层次聚类，它与分裂层次聚类相反，最初我们把每个样本都看作是一个单独的簇，重复地将最近的一对簇进行合并，直到所有的样本都在一个簇中为止。
在凝聚层次聚类中，判定簇间距离的两个标准方法分别是单连接（single linkage）和全连接（complete linkage）。我们可以使用单连接方法计算每一对簇中最相似两个样本的距离，并合并距离最近的两个样本所属簇。与之相反，全连接的方法是通过比较找到分布于两个簇中最不相似的样本（距离最远的样本），进而完成簇的合并。如下图所示：
凝聚层次聚类中其他常用的算法还有平均连接（average linkage）和ward连接（Ward抯linkage）。使用平均连接时，合并两个簇间所有成员间平均距离最小的两个簇。当使用ward连接时，被合并的是使得SSE增量最小的两个簇。
在本节，我们将重点关注基于全连接方法的凝聚层次聚类，其迭代过程可总结如下：
1）计算得到所有样本间的距离矩阵。
2）将每个数据点看作是一个单独的簇。
3）基于最不相似（距离最远）样本的距离，合并两个最接近的簇。
4）更新相似矩阵（样本间距离矩阵）。
5）重复步骤2到4，直到所有样本都合并到一个簇为止。
现在我们来讨论一下如何计算距离矩阵（步骤1）。在此之前，需要先随机生成一些样本数据用于计算。其中行代表不同的样本（ID值从0到4），列代表样本的不同特征（X，Y，Z）。
执行上述代码后，可以得到如下距离矩阵：