什么是层次聚类？
层次聚类（Hierarchical Clustering） 是一种构建聚类层次结构的算法。
核心直觉：
- 开始时每个点是一个聚类
- 逐步合并最相似的聚类
- 最终形成一棵"树"（树状图 Dendrogram）
与 K-Means 对比：
- K-Means：需要预先指定聚类数 K
- 层次聚类：不需要指定 K，可以事后从树状图选择
适用场景
- 生物分类：物种分类、基因序列分析
- 文档层次结构：新闻主题层级、知识图谱构建
- 社交网络社区发现：用户群体层次分析
历史渊源
问题背景：生物学家在研究物种分类时，需要一种方法来展示物种之间的亲缘关系——不只是"分成几组"，而是展示"谁和谁更近"的层次结构。K-means 只能给出扁平的分组，无法表达这种层级关系。
关键突破：1967年，Stephen Johnson 系统性地描述了凝聚型层次聚类：从每个点自成一簇开始，每次合并最相似的两个簇，直到所有点合为一簇。整个过程形成一棵"树状图"（Dendrogram），在任意高度"切一刀"就能得到不同粒度的聚类结果。
深远影响：层次聚类的树状图成为了生物信息学的标准工具——基因表达分析、蛋白质家族分类、进化树构建都离不开它。"先看整体层次，再选择合适粒度"的分析思路影响了后来的多尺度数据分析方法。
趣闻："Dendrogram"（树状图）这个词来自希腊语 dendron（树）+ gramma（图画）。生物学家最早用它画进化树，后来被统计学家"借"来做聚类可视化——这大概是生物学对数据科学最优雅的贡献之一。
发展脉络
局限性
- O(n2) 复杂度：需要计算和存储所有点对之间的距离
- 无法撤销合并/分裂：一旦做出决策就无法回退
- 对噪声敏感：异常点会影响整个层次结构
这些局限催生了：BIRCH（大规模数据）、CURE（对异常值鲁棒）、谱聚类（结合图论）
工业界地位
层次聚类在小规模数据和需要层次结构的场景中被广泛使用：
- 搜索引擎：搜索结果分类展示
- 推荐系统：商品类目层次构建
- 生物信息学：基因表达分析、蛋白质分类
- 组织管理：部门架构、产品分类
何时选择层次聚类？当数据量较小（小于10万）、需要可视化层次结构、不确定聚类数时，层次聚类是最佳选择。树状图可以帮助直观地选择合适的聚类数！
交互式可视化
观察聚类如何逐步合并形成层次结构
- 观察树状图（dendrogram）：横线的高度表示合并时两个簇的距离——越高表示越不相似
- 调整「聚类数量」，相当于在树状图上画一条水平线——线以上的合并被「剪掉」
- 切换不同的「链接方式」（单链接/完全链接/平均链接），观察聚类结果如何变化
数据点
树状图 (Dendrogram)
聚类信息：
当前层级: 0
合并距离: 0
聚类数: 0
数学原理
直觉引入：想象一群人站在操场上——先让最近的两个人手拉手组成一组，然后让最近的两组合并……不断重复，最终所有人连成一棵"家谱树"（树状图）。在任意高度"切一刀"，就得到不同粒度的分组。
聚类间距离（链接方式）：
两个簇 $C_i$ 和 $C_j$ 之间的距离有多种定义，选择不同会得到不同形状的簇：
- 单链接（Single）——最近点距离，容易产生链式效应：
$$d(C_i, C_j) = \min_{p \in C_i, q \in C_j} d(p, q)$$
- 全链接（Complete）——最远点距离，倾向产生紧凑球形簇：
$$d(C_i, C_j) = \max_{p \in C_i, q \in C_j} d(p, q)$$
- 平均链接（Average）——所有点对的平均距离，折中方案：
$$d(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{p \in C_i} \sum_{q \in C_j} d(p, q)$$
- Ward 方法——合并后方差增量最小，最常用：
$$d(C_i, C_j) = \frac{|C_i||C_j|}{|C_i|+|C_j|} ||\mu_i - \mu_j||^2$$
观察树状图（Dendrogram），找最长的"竖线"（即两次合并之间距离跳跃最大的地方），在那里水平切割。跳跃越大，说明被合并的两个簇差异越大，不应该合并。