层次聚类 在数据挖掘和统计学中层次聚类英語Hierarchical clustering是一种旨在建立聚类的层次结构的聚类分析方法层次聚类的策略通常有两种 凝聚Agglomerative clustering一种自底向上方法从小集群开始逐渐将其合并形成更大的集群 分裂Divisive clustering一种自顶向下方法从单个集群开始递归地将其拆分成更小的集群 凝聚和分离的操作通常用贪心算法实现结果通常用树状图展示 标准的凝聚层次聚类Hierarchical agglomerative clusteringHAC算法的时间复杂度为 O  n   displaystyle mathcal On 空间复杂度为 Ω  n   displaystyle Omega n 这使它甚至难以应用于中等规模的数据集中对于一些特殊情况效率最优的算法复杂度为 O  n   displaystyle mathcal On 包括SLINK用于单连接聚类Singlelinkage clustering和CLINK用于全连接聚类Completelinkage clustering当使用堆Heap时一般情况下的时间复杂度降至 O  n  log  n  displaystyle mathcal Onlog n 该改进以更多的内存需求为代价这种改进方法的内存开销很多时候大到难以实际使用 除了单连接聚类的特殊情况除了穷举算法复杂度 O   n  displaystyle mathcal On 外没有算法可以保证找到最优解 使用穷举算法的分裂方法的复杂度为 O   n  displaystyle mathcal On 不过可以通过更快的启发式方法例如k均值算法进行分裂 层次聚类的优点是可以采用任何有效的距离测量当给定距离矩阵时观测本身是没有必要的