层次聚类

层次聚类可以表示为树图的形式。

单/全连通聚类

寻找两个集合之间最相似样本之间的相似度。

算法过程：

初始每一个节点为一类，计算每两类中最近节点的距离，并选取距离最小的进行合并。

如图，第一回合聚类结果为{a, b}, {c, d}, {e, f}, {g, h}。第二回合聚类结果为{a, b, c, d}, {e, f, g, h}

但是a和d之间的距离实际上比a和e之间的距离要大，因此这种算法可能会导致拉长聚类区域。

全连通聚类

全连通聚类考虑的是最不相近样本之间的聚类，然后选取这些距离中最小的进行聚类。

平均连通聚类

平均连通聚类定义了一个相似度$S(Cj ) = \frac{1}{|c_j |(|c_j |-1)}\sum{\vec{x} \in cj}\sum{\vec{x} != \vec{y} \in c_j} sim(\vec{x}, \vec{y})$

我们需要计算S($c_u \cup c_j$)，并且合并结果最大的两个集合

非层次聚类

k-means算法