层次聚类是什么？和 K-means 有什么区别？

简化版

层次聚类把样本组织成嵌套簇的树。凝聚式从单点簇开始反复合并，分裂式从全体开始拆分；single、complete、average、Ward 等 linkage 定义不同的合并代价。它不必在建树前指定 K，但交付平坦簇时仍要选择切割高度。凝聚算法通常没有随机中心初始化，不过并列距离、输入顺序和 tie-breaking 仍可能改变树的细节，不能无条件称结果绝对确定；主要代价是二次级存储、较高时间成本和贪心合并不可逆。

详细版

两种方向：

方向	做法	常用性
凝聚式（自底向上）	每点一簇 → 不断合并最近的两簇	最常用
分裂式（自顶向下）	全部一簇 → 不断拆分	少用、更慢

簇间距离（linkage）：

方法	定义	特点
单连接 Single	两簇最近点对的距离	易形成链状、对噪声敏感
全连接 Complete	两簇最远点对的距离	倾向紧凑球形簇
平均连接 Average	两簇所有点对平均距离	折中
Ward	合并后簇内平方和增量最小	常用、倾向等大球形簇

层次聚类 vs K-means：

	层次聚类	K-means
需指定 K	否（事后切树）	是
输出	树状图（层次结构）	平坦的 K 个簇
随机性	通常无随机初始化；并列处理可能影响细节	常依赖初始化与随机种子
复杂度	高 O(n²~n³)	低 O(nKd·迭代)
大数据	不适合	适合

完整版教学

一、层次聚类的核心思想：建一棵簇的树

K-means 直接把数据切成 K 个平坦的簇。层次聚类不同——它构建一棵嵌套的层次结构（树）：小簇一层层合并成大簇（或大簇一层层拆成小簇），最终形成一棵叫 树状图（dendrogram） 的树。这棵树展示了「在不同粒度下数据怎么分组」：树越往下簇越细、越往上簇越粗。

好处是不用预先决定分几类——先建好整棵树，之后想要几个簇，就在对应高度横切一刀。这让层次聚类特别适合探索数据的层次结构（如生物物种分类、文档主题层次）。

二、两种方向：凝聚 vs 分裂

凝聚式（Agglomerative，自底向上）——最常用：

1. 每个样本各自成一个簇（n 个簇）
2. 重复：找出「距离最近的两个簇」，合并成一个
3. 直到所有点合成一个大簇
记录每次合并 → 得到树状图

分裂式（Divisive，自顶向下）：

1. 所有样本在一个大簇里
2. 重复：把某个簇拆成两个（拆得最"该拆"的）
3. 直到每个点各自成簇

分裂式每步要决定「怎么拆」，选择空间更大、计算更贵，实践中很少用，主流是凝聚式。

三、关键：怎么衡量「两个簇的距离」（linkage）

凝聚式每步要合并「最近的两个簇」，但簇里有多个点，「簇间距离」怎么定？这就是 linkage（连接准则），不同选择会得到很不同的聚类：

单连接（Single Linkage）：两簇最近的一对点的距离。倾向把「链条状」连起来（能发现细长簇），但对噪声敏感、易产生链式效应（一串点被拉成一簇）。
全连接（Complete Linkage）：两簇最远的一对点的距离。倾向形成紧凑的球形簇，对噪声较鲁棒，但可能拆散大簇。
平均连接（Average Linkage）：两簇所有点对距离的平均。是单连接和全连接的折中。
Ward 连接：合并后簇内平方和（方差）增量最小的两簇优先合并。倾向生成大小相近的球形簇，是最常用、通常效果最好的选择。

四、树状图与「切一刀定簇数」

层次聚类的输出是树状图（dendrogram）：横轴是样本，纵轴是合并时的簇间距离（高度）。两个簇在越高处合并，说明它们越不相似。

距离
 │        ┌──────┐         ← 在这个高度横切 → 2 个簇
 │      ┌─┘    ┌─┘
 │    ┌─┘    ┌─┘┌──┐       ← 切低一点 → 更多簇
 │   A  B   C  D  E

要几个簇，就在树状图的相应高度横切一刀——切线穿过几条竖线，就得到几个簇。切得越低簇越多越细，越高簇越少越粗。这样就把「选簇数」从「聚类前的猜测」变成了「聚类后的观察」，还能看到不同粒度的结构，很直观。

五、相比 K-means 的优缺点

优点：

不需要预先指定 K：建好树后切一刀即可，还能看不同 K 的结果。
输出层次结构：树状图展示数据的嵌套组织，信息比平坦的 K 个簇丰富。
通常更易复现：凝聚式没有随机中心初始化；但并列距离、输入顺序、浮点误差和库的 tie-breaking 仍可能影响合并细节。
可用各种距离/linkage，灵活适配不同簇形状。

缺点：

计算复杂度高：一般 O(n²) 空间、O(n²logn)~O(n³) 时间，不适合大数据集（K-means 是 O(nKd) 线性，扩展性好得多）。
合并不可逆（贪心）：一旦合并了就不能撤销，早期的错误合并会一直影响后面。
对噪声和距离度量敏感（尤其单连接）。

六、怎么选——层次聚类 vs K-means vs DBSCAN

数据小、想看层次结构、不知簇数、要确定性结果 → 层次聚类
数据大、簇近球形、已知/能估 K、追求效率 → K-means
任意形状、有噪声、不知簇数、密度均匀 → DBSCAN

三者互补：层次聚类给结构和确定性，K-means 给效率，DBSCAN 给任意形状 + 噪声识别。

七、常见追问

凝聚式和分裂式哪个常用？ 凝聚式（自底向上），分裂式太贵少用。
Ward linkage 有什么特点？ 合并后簇内方差增量最小，倾向等大球形簇，最常用、效果通常好。
怎么定簇数？ 看树状图，在「合并距离突然变大」的高度横切（类似肘部思想）。
为什么不适合大数据？ O(n²) 以上的复杂度，n 大就算不动。
单连接的链式效应是什么？ 单连接用最近点对距离，一串挨着的点会被逐个连成一条长链，形成不理想的细长簇。

八、用四个一维点还原凝聚过程

设四个一维点 A=0,B=1,C=5,D=6，用欧氏距离和 single linkage。第一轮最近距离为 1，A-B 与 C-D 都并列；若实现先合并 A、B，下一轮仍会合并 C、D，最后两个簇在距离 4 处合并。树状图记录的是每次合并高度，而不是预先给出的类别编号。

当前簇	候选距离	选择
{A},{B},{C},{D}	d(A,B)=1，d(C,D)=1	按确定的 tie 规则选一对
{AB},{C},{D}	d(C,D)=1，d(AB,C)=4	合并 {C,D}
{AB},{CD}	d(AB,CD)=4	合成根节点

高度 4          ┌─────────┐
             ┌──┘         └──┐
高度 1      A──B             C──D
切在 1 与 4 之间 → {A,B}、{C,D} 两簇

Ward 准则比较的是合并造成的簇内平方和增量，其标准推导与欧氏几何配套，不能随意换成任意距离。凝聚过程没有随机中心初始化，但并列距离、输入顺序和库的 tie-breaking 仍可能让树的细节不同。

易错点：“不用先给 K”只表示先建树后切树；最终交付平坦簇时仍要选择切割高度或簇数。

九、常见误区与追问

误区：层次聚类的结果在任何情况下都绝对唯一。 并列距离和实现的破同分规则可能改变合并顺序。
误区：Ward linkage 可以配任意距离。 经典 Ward 最小化平方误差增量，通常要求欧氏距离。
追问：为什么合并不可逆？ 凝聚算法只维护当前簇，不回溯拆开早期合并，因此是贪心过程。
追问：树状图纵轴一定是原始点距离吗？ 它表示所用 linkage 的合并代价，不同准则的数值含义不同。
追问：大样本如何扩展？ 可先抽样或用快速聚类形成微簇，再对代表点做层次聚类。

十、加强记忆

层次聚类输出可在不同高度切割的嵌套树：single 看最近点、complete 看最远点、average 看平均点对距离，Ward 最小化平方误差增量且通常配欧氏距离。它无需在建树前给 K，但最终平坦分群仍要选切割高度。凝聚过程通常无随机初始化，却可能受并列距离和实现规则影响；同时有二次级存储、较高时间成本与不可逆合并。选型应依据样本规模、距离语义、簇形状和是否需要层次解释，而不是机械套“层次/K-means/DBSCAN”口诀。

简化版

详细版