层次聚类通过对数据集在不同层次进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合（agglomerative）策略，也可采用“自顶向下”的分拆（divisive）策略。“自底而上”的算法开始时把每一个原始数据看作一个单一的聚类簇，然后不断聚合小的聚类簇成为大的聚类。“自顶向下”的算法开始把所有数据看作一个聚类，通过不断分割大的聚类直到每一个单一的数据都被划分。
根据聚类簇之间距离的计算方法的不同，层次聚类算法可以大致分为：单链接（Single-link）算法，全链接算法（complete-link）或均链接算法（average-link）。单链接算法用两个聚类簇中最近的样本距离作为两个簇之间的距离；而全链接使用计算两个聚类簇中最远的样本距离；均链接算法中两个聚类之间的距离由两个簇中所有的样本共同决定。
“自底向上”的聚合层次聚类算法
（1）计算任意两个数据之间的距离得到一个相似度矩阵（proximity matrix），并把每一个单一的数据看作是一个聚类；
（2）查找相似度矩阵中距离最小的两个聚类，把他们聚合为一个新的聚类，然后根据这个新的聚类重新计算相似度矩阵；
（3）重复（2）直到所有的数据都被归入到一个聚类中。
“自顶向下”的分拆（divisive）策略则与之相反。
可以使用单链接或者全链接的的方式来聚类簇之间的距离，会使得聚类的最终结果有所不同。
针对层次聚类不适于解决大量数据的问题，Zhang 等人提出了一种基于聚类特征树（Clustering Feature Tree）的层次聚类算法：BIRCH算法（Balanced Iterative Reducing and Clustering Using Hierarchies）。BIRCH算法实现了只需要一次对数据集的遍历就可以完成聚类。其聚类的主要过程就是将所有数据依次插入构建聚类特征树的过程，而树上的每一个节点所包含的数据构成了一个对应的聚类簇。同时对于包含数据极少的节点我们可以认为它是异常点从而进行去除。
层次聚类的另外一个变种算法是名为变色龙算法（Chameleon）。它是由George Karypis 教授提出的一种基于动态建模（Dynamic modeling）思想的层次聚类算法。该算法通过计算两个聚类簇之间的相似度和互连性从而克服CURE和ROCK等算法的缺点。变色龙算法首先将所有的数据根据他们之间的距离划分成众多的小的簇，通过计算相近簇之间的相似度和互连性不断合并形成大的聚类簇。
【描述来源：周志华. (2016). 机器学习: = Machine learning. 清华大学出版社.】
【描述来源：Data clustering: a review.描述来源URL：http://eprints.library.iisc.ernet.in/273/1/p264-jain.pdf .】
【描述来源：Jain, A. K., & Dubes, R. C. (1988). Algorithms for clustering data. Prentice Hall.描述来源URL：https://www.cse.msu.edu/~jain/Clustering_Jain_Dubes.pdf .】
【描述来源：Podani, J. (2000). Introduction to the exploration of multivariate biological data. Backhuys Publishers.描述来源URL：http://ramet.elte.hu/~podani/5-Hierarchical%20clustering.pdf】
【描述来源：Zhang, T., Ramakrishnan, R., & Livny, M. (1996, June). BIRCH: an efficient data clustering method for very large databases. In ACM Sigmod Record (Vol. 25, No. 2, pp. 103-114). ACM.描述来源URL：www.cs.sfu.ca/CourseCentral/459/han/papers/zhang96.pdf】
发展历史
层次聚类算法已经被使用和研究了几十年，自底而上的聚合算法比自顶向下的分裂算法应用更多。而目前大多数层次聚类的算法多是基于单链接，多链接的变种算法。早期对于单链接和全链接算法是参考1967由King或1973年Sneath等人书籍。Ward 在1963年根据方差分析提出了离差平方和的思想（Ward's method），在1967年形成另外一种层次聚类的算法。1996年，Tian Zhang提出了基于聚类特征树的层次聚类算法-BIRCH算法，为大量数据集的层次聚类提供了解决方案。在1999年，由Jain编著的书籍Data clustering: a review对聚类算法有了系统的解释和总结，到现在仍然被看作是非常优秀的关于聚类的综述文章。来自斯坦福的 Rob Tibshirani 教授将层次聚类应用于基因检测和癌症研究等医学方向，取得了相当不错的效果。而来自明尼苏达大学计算机科学和工程系的副教授 George Karypis 教授提出了一种基于动态建模（Dynamic modeling）的思想的层次聚类算法-变色龙算法，以及关于如何在文本数据上使用层次聚类。
主要事件
| 年份 | 事件 | 相关论文 |
| 1963 | Ward 提出离差平方和的思想 | Ward Jr, J. H. (1963). Hierarchical grouping to optimize an objective function. *Journal of the American statistical association*, *58*(301), 236-244. |
| 1967 | King 提出全链接算法 | King, B. (1967). Step-wise clustering procedures. *Journal of the American Statistical Association*, *62*(317), 86-101. |
| 1973 | Sneath 和 Sokal 提出单链接算法 | Sneath, P. H., & Sokal, R. R. (1973). *Numerical taxonomy. The principles and practice of numerical classification*. |
| 1996 | Zhang 等人提出BIRCH算法 | Zhang, T., Ramakrishnan, R., & Livny, M. (1996, June). BIRCH: an efficient data clustering method for very large databases. In ACM Sigmod Record (Vol. 25, No. 2, pp. 103-114). ACM. |
| 1999 | Jain编著关于聚类综述书籍 | Jain, A. K., Murty, M. N., & Flynn, P. J. (1999). Data clustering: a review. *ACM computing surveys (CSUR)*, *31*(3), 264-323. |
| 1999 | George Karypis教授提出使用动态建模的层次聚类 | Karypis, G., Han, E. H., & Kumar, V. (1999). Chameleon a hierarchical clustering algorithm using dynamic modeling. Computer, 32(8), 68-75. |
3. 发展分析
瓶颈
层次聚类的计算量非常的大，无论是单链接，全链接或者均链接算法或者其优化算法，时间和空间复杂度都至少在O(N^2)。所以对于大量的数据集的时候使用划分聚类（如EM算法和K-means算法）从而降低计算量。
尽管最近很多实验结果表明划分聚类好于层次聚类，但通常认为层次聚类算法产生的聚类结果是会优于划分聚类算法的。这是因为EM算法和K-means算法他们经常会收敛到一个较差的局部最优解，所以其产生的结果充满了不确定性，而层次聚类的结果更加的稳定。但同时不像K-Means和EM算法，大多数层次聚类算法并没有一个概率学的解释。
未来发展方向
在NIPS2017的一篇关于层次聚类的论文中，作者给出了一个分析架构从而更好的理解在实际观察到的结果。它是第一个对于自然目标功能的层次聚类建立了一种保障。所以未来的发展可能会专注于对于层次聚类理论的深入和可解释性的探究从而更好的优化算法。
Contributor: Chao Yang