算法首先声明每个点是自己的簇，然后合并两个最相似的簇，直到满足某种停止准则为停止。scikit-learn中实现的停止准则是簇的个数，当合并到剩下指定个数的簇为止。如何度量最相似的簇，scikit-learn提供了链接准则，有三类：

ward：默认选项，ward挑选两个簇来合并，使得所有簇中的方差增加最小。这通常会得到大小差不多相等的簇。

average：将簇中所有点之间平均距离最小的两个簇合并。

complete：将簇中点之间最大距离最小的两个簇合并。也称最大链接。

ward 适用于大多数数据集，在我们的例子中将使用它。如果簇中的成员个数非常不同（比如其中一个比其他所有都大得多），那么average 或complete 可能效果更好。

图3-33 给出了在一个二维数据集上的凝聚聚类过程，要寻找三个簇。

最开始，每个点自成一簇。然后在每一个步骤中，相距最近的两个簇被合并。在前四个步骤中，选出两个单点簇并将其合并成两点簇。在步骤5（Step 5）中，其中一个两点簇被扩展到三个点，以此类推。在步骤9（Step 9）中，只剩下3 个簇。由于我们指定寻找3 个簇，因此算法结束。

我们来看一下凝聚聚类对我们这里使用的简单三簇数据的效果如何。由于算法的工作原理，凝聚算法不能对新数据点做出预测。因此AgglomerativeClustering 没有predict 方法。为了构造模型并得到训练集上簇的成员关系，可以改用fit_predict 方法。结果如图3-34 所示。

正如所料，算法完美地完成了聚类。虽然凝聚聚类的scikit-learn 实现需要你指定希望算法找到的簇的个数，但凝聚聚类方法为选择正确的个数提供了一些帮助，我们将在下面讨论。

层次聚类与树状图

凝聚聚类是一种所谓的层次聚类（hierarchical clustering）。聚类过程迭代进行，每个点都从一个单点簇变为属于最终的某个簇。每个中间步骤都提供了数据的一种聚类（簇的个数也不相同）。有时候，同时查看所有可能的聚类是有帮助的。下一个例子（图3-35）叠加显示了图3-33 中所有可能的聚类，有助于深入了解每个簇如何分解为较小的簇：

虽然这种可视化为层次聚类提供了非常详细的视图，但它依赖于数据的二维性质，因此不能用于具有两个以上特征的数据集。但还有另一个将层次聚类可视化的工具，叫作树状图（dendrogram），它可以处理多维数据集。

目前scikit-learn 没有绘制树状图的功能，可以利用SciPy 轻松生成树状图。SciPy 的聚类算法接口与scikit-learn 的聚类算法稍有不同。SciPy 提供了一个函数，接受数据数组X 并计算出一个链接数组（linkage array），它对层次聚类的相似度进行编码。

然后我们可以将这个链接数组提供给scipy 的dendrogram 函数来绘制树状图（图3-36）。

树状图在底部显示数据点（编号从0 到11）。然后以这些点（表示单点簇）作为叶节点绘制一棵树，每合并两个簇就添加一个新的父节点。从下往上看，数据点1 和4 首先被合并（正如你在图3-33 中所见）。接下来，点6 和9 被合并为一个簇，以此类推。在顶层有两个分支，一个由点11、0、5、10、7、6 和9 组成，另一个由点1、4、3、2 和8 组成。这对应于图中左侧两个最大的簇。树状图的y 轴不仅说明凝聚算法中两个簇何时合并，每个分支的长度还表示被合并的簇之间的距离。在这张树状图中，最长的分支是用标记为“three clusters”（三个簇）的虚线表示的三条线。它们是最长的分支，这表示从三个簇到两个簇的过程中合并了一些距离非常远的点。我们在图像上方再次看到这一点，将剩下的两个簇合并为一个簇也需要跨越相对较大的距离。

把凝聚聚类算法应用在图3-27、图片-28、图3-29的数据集上发现，凝聚聚类仍然无法分离像拉长形、半月形等 数据集这样复杂的形状。对数据点密度不同的数据集的效果，请比较下列下图与图3-27。

后续我们要学习的下一个算法DBSCAN 可以解决复杂的形状的数据集聚类这个问题。