8.3凝聚层次聚类

有两种产生层次聚类的基本方法

凝聚的：从点作为个体簇开始，每一步合并两个最接近的簇。这需要定义簇的邻近性概念。

分裂的：从包含所有点的某个簇开始，每一步分裂一个簇，知道仅剩下单点簇。在这种情况下， 我们需要确定每一步分裂哪个簇，以及如何分类。

凝聚层次聚类技术最为常见，我们先关注这类方法。

层次聚类常常使用树状图的类似于树的图显示。该图显示簇——子簇练习和簇合并（凝聚）或分裂的次序。

基本凝聚层次聚类算法

从个体点作为簇开始，相继合并两个最接近的簇，只到只剩下一个簇

1：如果需要，计算邻近度矩阵

2：repeat

3：合并最接近的两个簇

4：更新邻近性矩阵，以反映新的簇与原来的簇之间的邻近性

5：until 仅剩下一个簇

1.定义簇之间的邻近性

算法的关键操作是计算两个簇之间的邻近度，并且正是簇的邻近性定义区分了我们将讨论的各种凝聚层次技术。簇的邻近性通常用特定的簇类型定义：在基于邻近的簇中，每个对象到该簇某个对象的距离比到不同簇中任意点的距离更近。

许多凝聚层次聚类技术，MIN——定义簇的邻近度为不同簇的两个最近的点之间的邻近度；MAX——取不同簇中两个最远的点之间的邻近度作为簇的邻近度；组平均——定义簇邻近度取自不同簇的所有点对邻近度的平均值（平均边长）

也可以取基于原型的观点，簇用质心代表，定义为簇质心之间的邻近度。

另一种方法——Ward，簇使用质心代表，使用合并两个簇导致的SSE增加来度量两个簇之间的邻近性。Ward与K-means一样视图最小化点到簇质心的距离平方和。