层次聚类是什么？像画家谱树一样逐步合并或拆分数据

层次聚类（Hierarchical Clustering）是一种通过构建一棵层层嵌套的“簇的树”来对数据进行聚类的方法。与 K 均值聚类需要事先指定簇的数量不同，层次聚类会生成一个从“每个样本自成一簇”到“所有样本合为一簇”的完整层次结构，人们可以根据需要，在这个结构的任意一层上选取聚类的结果。

两种方式

凝聚式层次聚类：采用自底向上的策略，是最常用的方式。一开始，把每个样本都看作一个单独的簇；然后找出距离最近的两个簇，把它们合并成一个新的簇；接着在新的一组簇中，再找出最近的两个合并；如此反复，每一步都减少一个簇，直到所有的样本都合并成一个大簇为止。分裂式层次聚类：采用自顶向下的策略。一开始，把所有的样本都看作一个大簇；然后选择一个簇，把它分裂成两个更小的簇；如此反复，直到每个样本都自成一簇，或者满足某个停止的条件。分裂式的计算通常更加复杂，使用得相对较少。

树状图

层次聚类的结果通常用一种叫树状图的图形来展示，它看起来很像一棵家谱树或者生物的进化树。树状图的底部是所有单独的样本，每当两个簇合并，就用一根横线把它们连接起来，横线的高度表示合并时两个簇之间的距离。越早合并的簇，连接线越低，说明它们越相似。通过在树状图上某个高度画一条水平线“切一刀”，与这条线相交的竖线数量，就是得到的簇的数量。切得越高，簇的数量越少、每个簇越大；切得越低，簇越多、越精细。如果树状图中某一段的竖线特别长，说明在这里两个簇之间的差距很大，在这附近切分往往是一个自然的选择。

如何衡量两个簇之间的距离

在合并的过程中，需要计算两个簇之间的距离，而簇是由多个样本组成的，有多种不同的定义方式，会得到不同的聚类结果。单链接：两个簇中距离最近的那一对样本之间的距离。它能够发现细长的、形状不规则的簇，但容易出现“链式效应”，把两个本该分开的簇因为中间几个相邻的点而连在一起。全链接：两个簇中距离最远的那一对样本之间的距离。它倾向于产生紧凑的、大小相近的簇，但对异常值比较敏感。平均链接：两个簇中所有样本两两之间距离的平均值，是一种折中的方式。Ward 法：选择合并后让簇内的平方误差增加最少的那两个簇，倾向于产生大小相近、形状较为紧凑的簇，在实践中效果通常较好，也是很多工具中的默认选项。

优缺点和应用

层次聚类的优点是：不需要事先指定簇的数量；能够展示数据在不同尺度上的层次结构，信息丰富；树状图直观，便于理解和解释。它的缺点是：计算量大，标准的凝聚式算法需要计算和存储所有样本两两之间的距离，时间和空间开销随样本数量快速增长，难以处理大规模的数据；合并或分裂一旦完成就无法撤销，前面的错误会一直影响后面的结果；对噪声和异常值比较敏感。层次聚类在生物学中应用非常广泛，比如根据基因序列构建物种的进化树、对基因表达数据进行聚类分析；它还被用于文档的层次分类、社会网络分析、客户的细分，以及图像分割等领域。