层次聚类算法详解：构建嵌套层次结构与时间复杂度

层次聚类算法是一种在数据挖掘和机器学习中广泛应用的无监督聚类方法，其核心思想是构建一个层次结构，即层次树，来表示数据对象之间的相似性和关系。与顺序聚类不同，层次聚类不形成单一的簇，而是生成一个由越来越大的子集组成的树形结构，每个节点代表一个聚类，子节点包含在父节点中，形成嵌套关系。 层次聚类主要分为两种实现方式：合并（Agglomerative）和分裂（Divisive）。合并算法通常更常用，因为它直观易理解，通过不断合并相似度最高的聚类对，形成更大的聚类，直至所有数据点都属于同一个簇。初始时，每个对象作为一个单独的簇，然后每次迭代中，算法会选择两个最相似的簇进行合并，形成一个新的簇，并更新层次结构。 合并算法的关键在于计算相似度函数g(Ci, Cj)，这个函数衡量两个聚类Ci和Cj之间的相似度或凝聚度。通用的合并算法通常按照以下步骤进行： 1. 初始化：将所有对象分为单元素聚类（如{x1},…,{xN}），设t=0。 2. 重复直到所有数据点合并成一个大簇： a. t递增1。 b. 在当前层次t-1中找到两个最相似的聚类Ci和Cj。 c. 合并这两个聚类形成Cq，将结果添加到新的层次Ât中，同时移除Ci和Cj。 这个过程中的一个重要特点是“惰性”，一旦两个点合并，它们就会保持在一起，除非后续操作将其拆分开。然而，这也带来了一个缺点，即如果在算法初期就存在聚类错误，这些错误会随着层次的增加而累积，难以修正。层次聚类的时间复杂度较高，尤其是在大规模数据集上，因为每层都需要考虑所有可能的聚类对，导致总的时间复杂度为O(N^3)，其中N为数据点的数量。 例如，对于一组数据点X={x1, x2, x3, x4, x5}，初始时每个点都是独立的，随着迭代，数据点会根据相似度逐渐聚集到一起，直到形成最终的层次结构。在实际应用中，层次聚类常用于数据分析、图像分割、生物信息学等领域，因其能提供层次清晰的聚类视图。