层次聚类，又称层次聚类分析（HCA），是数据挖掘和统计学中的一种聚类分析方法，旨在构建一个层次结构。与需要预先指定聚类数量的划分方法（如k均值）不同，层次聚类生成一个嵌套结构，可以在任意层级进行切割，从而获得不同数量的聚类。其结果通常以树状图呈现，这是一种树形图，用以说明合并或分裂的序列。该方法广泛应用于生物学、社会科学和机器学习等领域，用于探索性数据分析。
层次聚类的主要优势在于其灵活性：可以使用任何有效的距离度量，并且不要求必须提供原始观测数据，仅需距离矩阵即可。然而，除了单链接距离这一特殊情况外，没有任何算法能在不进行穷举搜索的情况下保证找到最优解，而穷举搜索的时间复杂度为O(2^n)。
凝聚与分裂策略
层次聚类的策略通常分为两类：凝聚和分裂。凝聚聚类，通常称为“自底向上”方法，开始时将每个数据点视为一个独立的聚类。在每一步中，算法根据选定的距离度量（如欧氏距离）和链接准则（如单链接、全链接）合并两个最相似的聚类。此过程持续进行，直到所有数据点合并为一个聚类或满足某个停止条件。凝聚方法因其简单性和对中小型数据集的计算效率而更为常用。
分裂聚类，称为“自顶向下”方法，开始时将所有数据点视为一个单一聚类，然后递归地将其分裂为更小的聚类。在每一步中，算法选择一个聚类，并根据诸如最大化聚类间距离等准则将其划分为两个或多个子集。分裂方法相对较少使用，但在目标是首先识别大型、明显不同的聚类时可能很有用。总的来说，合并或分裂的决定是以贪婪方式做出的，这意味着算法在每一步都做出局部最优选择，而不考虑全局结构。
复杂度与算法
标准层次凝聚聚类（HAC）算法的时间复杂度为O(n^3)，空间复杂度为Ω(n^2)，这使得它对于中等规模的数据集来说速度过慢。然而，在某些特殊情况下，存在时间复杂度为O(n^2)的最优高效凝聚方法：SLINK用于单链接，CLINK用于全链接。使用堆数据结构，一般情况下的运行时间可以降低到O(n^2 log n)，但代价是增加内存需求。在许多情况下，这种方法的内存开销过大，使其在实际应用中不可行。还有一些方法使用四叉树，可以在O(n)空间内实现O(n^2)的总运行时间。
分裂聚类若采用穷举搜索，其复杂度为O(2^n)，但通常使用更快的启发式方法来选择分裂方式，例如k均值。这些启发式方法在计算可行性上做出了权衡，牺牲了最优性，从而使得分裂方法能够应用于更大的数据集。
距离度量
链接准则决定了聚类间相异度的计算方式，而底层的距离度量则决定了单个观测值之间相异度的测量方式。由于层次聚类允许使用任何有效的距离度量，度量的选择受数据性质的指导，并会对最终的聚类结果产生显著影响。
欧氏距离是连续数值数据中最广泛使用的度量，它对应欧氏空间中两点间的直线距离，并且是大多数统计软件中的默认选择。曼哈顿距离（也称为城市街区距离或L1距离）计算各特征维度上绝对差值的总和。当特征具有不同量纲或数据包含离群值时，曼哈顿距离通常更受青睐，因为它对大幅偏差不如欧氏距离敏感。余弦距离用于度量两个非零向量之间的角度相异度，常用于文本分析和其他高维场景。
链接准则
链接准则决定了如何根据聚类内各个成员之间的距离来计算两个聚类之间的距离。单链接（或最近邻）使用两个聚类中任意两点之间的最小距离，这往往会产生长条状、链式的聚类。全链接（或最远邻）使用最大距离，倾向于产生紧凑、球形的聚类。平均链接使用所有点对之间的平均距离，是前两者之间的一种折中方案。沃德法（Ward's method）最小化聚类内总方差，因此对于连续数据很受欢迎。链接准则的选择会极大地改变最终树状图的形态和解释。
应用与局限性
层次聚类在许多领域都有应用。在生物学中，它常用于基于遗传相似性构建系统发育树。在市场营销中，它有助于根据行为相似性对客户进行细分。在图像分析中，它可以对像素或特征进行分组。在人工智能领域，层次聚类常作为一种无监督学习技术，用于探索性数据分析，或作为其他算法的预处理步骤。
尽管层次聚类具有诸多优点，但也存在局限性。算法的贪婪特性意味着一旦完成一次合并或分裂，就无法撤销，这可能导致次优的结果。标准算法的计算复杂度限制了其仅适用于中等规模的数据集，尽管针对特定链接准则已有优化实现。此外，树状图的解读可能带有主观性，并且距离度量和链接准则的选择需要领域知识。