基本工作原理
给定要聚类的N的对象以及N*N的距离矩阵(或者是相似性矩阵), 层次式聚类方法的基本步骤(参看S.C. Johnson in 1967)如下:
1. 将每个对象归为一类, 共得到N类, 每类仅包含一个对象. 类与类之间的距离就是它们所包含的对象之间的距离.
2. 找到最接近的两个类并合并成一类, 于是总的类数少了一个.
3. 重新计算新的类与所有旧类之间的距离.
4. 重复第2步和第3步, 直到最后合并成一个类为止(此类包含了N个对象).
根据步骤3的不同, 可将层次式聚类方法分为几类: single-linkage, complete-linkage 以及 average-linkage 聚类方法等.
single-linkage 聚类法(也称 connectedness 或 minimum 方法): 类间距离等于两类对象之间的最小距离，若用相似度衡量，则是一各类中的任一对象与另一类中任一对象的最大相似度
complete-linkage 聚类法 (也称 diameter 或 maximum 方法): 组间距离等于两组对象之间的最大距离。
average-linkage 聚类法: 组间距离等于两组对象之间的平均距离。average-link 聚类的一个变种是R. D'Andrade (1978) 的UCLUS方法, 它使用的是median距离, 在受异常数据对象的影响方面, 它要比平均距离表现更佳一些.
这种层次聚类称为“凝聚"法，由于它迭代合并所有分类。也有一种“划分”层次聚类法，与“凝聚”相反，它先将所有对象放在同一类中，并不断划分成更小的类，划分法一般很少使用。
(*) 当然，将所有n个对象都放在同一类中纯属扯淡，根本没用。实际上，一旦你得到了完整的层次树，如果你想进行k分类，需要做的仅仅是剪枝。
以下我们以single-linkage聚类算法为例说明Johnson算法的原理。
single-linkage算法一种agglomerative机制，即每次将两个旧类合并成一个新类，直到最终合并成一个类为止。每合并一次，则在距离矩阵中删除相对应的行与列。
先介绍一些符号：将待聚类的N个对象分别标号为0,1,......, (n-1),，D = [d(i,j)]表示对应的N*N距离矩阵。记号L(k)表示第k个类所处的层次，由对象m构成的类记为(m)，类(r)与类(s)的距离记为d [(r),(s)]。
single-linkage聚类算法过程如下：1. 初始时共有N个类，每个类由一个对象类成。令顺序号m = 0, L(m) = 0.
2. 在D中寻找最小距离d[(r),(s)] = min d[(i),(j)].
3. 将两个类(r)和(s)合并成一个新类(r,s);令m = m +1, L(m) = d[(r),(s)]
4. 更新距离矩阵D: 将表示类(r)和类(s)的行列删除，同时加入表示新类(r,s)的行列；同时定义新类(r,s)与各旧类(k)的距离为 d[(k), (r,s)] = min d[(k),(r)], d[(k),(s)]
5. 反复步骤2-4，直到所有对象合并成一个类为止。
问题
该算法主要的缺点在于：
- 不是scable，至少 O(n2),复杂性，n是对象总数 ;
- 不能取消之前已经做完的工作.
Bibliography
