企业官网建设流程全解析

层次聚类（合并法）大概是所有聚类算法里最“反直觉”的一个：它不像 K-Means 那样要先回答“我要分几类”，而是先把每个样本都当成独立的一簇，然后一步一步把最近的两簇并在一起，直到最后只剩一个簇。你可以在任何阶段停下来，决定要几个簇。听起来很优雅，但真上手实现的时候，麻烦事全藏在这些“最近的两簇”里。

我第一次学这个算法时，直接调了现成库，三行代码出结果，聚类图也画得漂漂亮亮。直到有次项目中同事拿着我给的聚类结果追问：为什么这两组先合并？为什么换一种连接方式结果完全不一样？我当时含糊其辞，只能说是“算法决定的”。就是那次之后，我决定用纯 Python 不调任何机器学习包，把合并法层次聚类从零写一遍。这篇文章整理的就是完整实现过程、实测数据，以及我在手写过程中反复踩进去的四个坑。

1. 为什么还要手写合并法层次聚类

有人会问：现成库里的 AgglomerativeClustering 三行代码就能跑，手写一遍不是自找麻烦吗？我的观点是，手写不是为了“重复造轮子”，而是为了在必要时能修改轮子。

调包实现看起来快，但暴露出来的认知缺口很实际。比如你用现成库跑出一张树状图，但说不清这几个问题：

• 两个簇之间的距离到底是怎么从“点与点的距离”汇总出来的？
• 为什么有些数据跑出来是均匀的树状结构，有些是一串糖葫芦？
• 裁剪树状图的时候，阈值该看合并距离的哪个位置？
• 如果业务上要求自定义一种连接方式，现成库不支持怎么办？

这些问题的答案，只有真正从零实现一遍才能消化。很多做算法的人大概都有类似的经历：面试时能背出“单连接、全连接、平均连接”的定义，但真到了要为一个特殊业务定义“两个簇之间的距离是加权平均再乘以某个系数”时，才发现自己对数据结构的理解和算法细节的控制力完全不够。

手写实现还有一个作用：调试和比对。后来我再用现成库做层次聚类时，会顺手跑一下自己的纯 Python 版本，把合并顺序打出来对照。库升级、参数变化、异常数据导致的合并顺序异常，都能第一时间发现。这有点像老司机熟悉车辆原理，遇到仪表盘亮红灯时知道大概哪里出了问题，而不是只会把车开进修理厂。

这篇博文会用一组我自己构造的二维坐标数据作为实测样本，完整过一遍合并法层次聚类从距离矩阵到最终合并记录的过程，并对比三种常见连接方式在同样数据上的表现差异。

2. 合并法的最小完整框架：点间距离与类间距离

合并法层次聚类的基本流程非常朴素：一开始有 n 个样本，每个样本是独立一簇。每一轮找出“距离最近”的两簇，把它们合并成一簇，不断重复直到只剩一个簇。整个过程记录下来，就是一棵树状结构，每次合并的高度就是合并时那两簇间的距离。

这里有两个“距离”要区分清楚。

2.1 点与点的距离：三种常用度量

第一个是样本点之间的原始距离，这决定了“远近”的基本定义。实现时我不会限制死成一种，代码里做成了可插拔的度量函数。

我在实现里先写了这三个函数。欧氏距离用math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))一行搞定；曼哈顿距离把平方换成绝对值；余弦距离则需要先算点积和两个向量的模长，再返回1 - dot / (norm_a * norm_b)。这里有个容易忽略的边界情况：如果某个样本是零向量（全 0），模长为 0，直接除就会报错，所以我在余弦函数里加了检查，遇到零向量直接返回 1.0，表示方向完全未知、相似度最低。

2.2 类与类的距离：连接方式决定了聚类的“性格”

第二个距离是“簇与簇之间的距离”。两个簇内部可能有很多个点，点对点距离一大堆，怎么汇总成一个数？这就是连接方式（linkage）的职责。我实现了三种最常见的：

• 单连接（single）：取两个簇之间所有点对距离的最小值。可以理解成“只要两个簇里各有一个点靠得足够近，就算这两个簇很近”。
• 全连接（complete）：取两个簇之间所有点对距离的最大值。可以理解成“两个簇的所有点都足够近，才承认它们近”。
• 平均连接（average）：取所有点对距离的平均值。可以理解成“综合看两个簇的平均亲近程度”。

单连接像朋友圈社交：两个人只要有一个共同好友，就算认识，慢慢越串越远，容易串成一条链。全连接像团队评审：必须所有人都点头才算数，任何一个离群点都能把合并距离拉大。平均连接夹在中间，更像是“民意调查”。

除了这三种，还有著名的 Ward 法，合并准则不是最小化簇间距离，而是最小化合并后类内离差平方和的增量。它需要用到每个簇的质心和样本数，不能只靠点对距离矩阵直接算出来，所以我在这版纯 Python 实现里先不展开，后面在扩展部分再讨论。

理解了这两个距离，合并法层次聚类的框架就完整了：重复计算所有活跃簇之间的类间距离，找到最小值，合并它们。难点全在“不要弄丢哪些簇还在活跃、哪些已经失效”这一类状态管理问题上。

3. 纯 Python 实现：三个核心函数搞定合并过程

先把代码贴出来，再解释每一步为什么这么设计。这段实现不依赖任何第三方库，只用了标准库里的math。

import math def euclidean(a, b): """欧氏距离：最常见的直线距离。""" return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b))) def manhattan(a, b): """曼哈顿距离：坐标差的绝对值之和。""" return sum(abs(x - y) for x, y in zip(a, b)) def cosine(a, b): """余弦相似度取反：数值越小表示方向越接近。""" dot = sum(x * y for x, y in zip(a, b)) norm_a = math.sqrt(sum(x * x for x in a)) norm_b = math.sqrt(sum(y * y for y in b)) if norm_a == 0 or norm_b == 0: return 1.0 return 1.0 - dot / (norm_a * norm_b) DISTANCE_FUNCTIONS = { "euclidean": euclidean, "manhattan": manhattan, "cosine": cosine, } def build_distance_matrix(points, dist_name="euclidean"): """构建对称距离矩阵。矩阵会被后续每次找最近簇时反复复用。""" n = len(points) dist = [[0.0] * n for _ in range(n)] fn = DISTANCE_FUNCTIONS[dist_name] for i in range(n): for j in range(i + 1, n): d = fn(points[i], points[j]) dist[i][j] = d dist[j][i] = d return dist def linkage_distance(dist, cluster_a, cluster_b, method): """根据连接方式，把两个簇之间的所有点对距离归纳成一个标量。""" values = [dist[i][j] for i in cluster_a for j in cluster_b] if method == "single": return min(values) if method == "complete": return max(values) if method == "average": return sum(values) / len(values) raise ValueError(f"未知的连接方式: {method}") def agglomerative(points, method="single", dist_name="euclidean"): """ 合并法层次聚类主流程。 返回 merges 列表，每个元素是 (left_points, right_points, merge_distance)。 """ n = len(points) dist = build_distance_matrix(points, dist_name) # 每个簇用 frozenset 保存它包含的原始样本下标 clusters = [frozenset([i]) for i in range(n)] active = [True] * n merges = [] num_active = n while num_active > 1: best_d = float("inf") best_i = best_j = -1 # 扫描所有活跃簇的两两组合，找距离最小的那一对 for i in range(n): if not active[i]: continue for j in range(i + 1, n): if not active[j]: continue d = linkage_distance(dist, clusters[i], clusters[j], method) if d < best_d: best_d = d best_i, best_j = i, j # 记录合并信息，然后把旧簇合并进 best_i，标记 best_j 失效 left = clusters[best_i] right = clusters[best_j] merges.append((sorted(left), sorted(right), best_d)) clusters[best_i] = left | right clusters[best_j] = frozenset() active[best_j] = False num_active -= 1 return merges

三个关键设计需要说明一下。

第一，为什么先算完整的点间距离矩阵，而不是每轮现算？因为合并过程中要找最近簇，会反复访问各簇内点对的距离。如果每轮都从原始坐标重新计算，大量距离会被重复算很多遍。距离矩阵是 O(n²) 的存储代价，换取的是每轮 O(1) 的距离取值。这是以空间换时间的典型取舍。

第二，为什么簇要用 frozenset 存原始下标？因为距离矩阵是按原始样本下标组织的，簇里只有装上原始下标，才能去矩阵里找点对距离。用不可变的 frozenset 而不是 list，是为了防止在合并过程中意外修改某个内部集合。合并时left | right直接生成新集合，旧集合保持原样，逻辑上更安全。

第三，为什么每次合并都从头扫描所有活跃簇，而不是维护一个递增更新的候选表？因为这是最朴素、最不容易写错的版本。每一轮扫描 O(n²) 个簇对，对小规模数据完全够用，而且代码的可读性非常高。性能优化我会在第六节专门讲，这里先把正确性和逻辑结构放到第一位。

用我构造的九点数据跑一遍平均连接，输出长这样：

第 1 次合并: [6] 与 [8], 距离 = 0.5000 第 2 次合并: [0] 与 [1], 距离 = 0.7071 第 3 次合并: [3] 与 [4], 距离 = 0.7071 第 4 次合并: [0, 1] 与 [2], 距离 = 0.8536 第 5 次合并: [3, 4] 与 [5], 距离 = 0.8536 第 6 次合并: [6, 8] 与 [7], 距离 = 0.9126 第 7 次合并: [0, 1, 2] 与 [3, 4, 5], 距离 = 4.9780 第 8 次合并: [0, 1, 2, 3, 4, 5] 与 [6, 7, 8], 距离 = 7.7919

可以看到，前六次合并基本发生在三个局部密集的小组内部，后两次才把三个小组两两合并。树状图里如果在 1.0 的位置横切一刀，恰好得到三类，和数据的直观分布完全一致。

4. 同一份数据，三种连接方式的走位差异

为了看清楚连接方式的影响，我把同样九点数据分别用单连接、全连接、平均连接跑了一遍，合并轨迹对比如下。九点的原始坐标是：(1,1)、(1.5,1.5)、(2,1) 组成第一簇，(5,5)、(5.5,4.5)、(5,4) 组成第二簇，(9,8)、(9.5,8.5)、(8.5,8) 组成第三簇。

这张表的信息量很大。

先看单连接。它的前六次合并距离全部是 0.7071，说明它通过“最近的一对点”就把三个小组内部各自粘起来了。第七次合并跳到 4.2426，第八次到 4.6098，也就是说真正把三大簇分开的距离阈值很清楚：取 1 到 4 之间任意高度切一刀，都是三簇；取 4.2 到 4.6 之间切，是两簇。这个“合并距离的间隙”非常干净，说明数据本身就适合做层次聚类。

再看全连接。前六次合并的距离从 0.5 一路涨到 1.1180，没有像单连接那样整齐地挤在同一个高度。原因是全连接要求“全部点都近”才合并，第三组里有一个点与另外两个点的距离达到 1.1180，所以这一组的合并硬生生被拉到更晚。更夸张的是最后一步，全连接把所有点合并成一个簇时距离是 11.3360，相比之下单连接只要 4.6098。这说明全连接对“最远的点”非常敏感，数据里只要有相对远的离群点，树状图的高度会被整体拉高。

平均连接则介于两者之间，前六次合并距离在 0.5 到 0.9126 之间，后两次分别在 4.9780 和 7.7919。它的合并高度也呈现明显的两组分层，聚类结果稳定，这也是为什么平均连接在实际应用中往往是默认选择之一。

从这张表还能推出一条实践经验：如果单连接和平均连接的树状图合并距离分层都很清晰，说明数据中存在自然的簇结构；如果合并高度近似均匀递增、没有明显断层，那数据大概率是均匀分布的，任何聚类方法都难有稳定结果。判断办法很简单，把合并距离列出来看有没有明显“台阶”，比看树状图本身更直观。

单连接的缺点是“链式效应”，它在某些场景会表现得非常明显。设想一堆点沿一条弧线分布，单连接会因为“相邻点很近”而把整个弧线串成一长条，而不是形成紧实的球形簇。全连接恰好相反，它更倾向于找凸的、紧凑的簇，但容易被离群点干扰。平均连接受到的单点影响最小，但计算量也最大，因为每次都要汇总所有点对的距离。

5. 手写版本最容易翻车的四个细节

实现本身不难，但我在调试过程中踩过的坑不少。这些问题在调库时几乎不会被看见，因为库已经帮你处理好了。自己做一遍，这些细节才真正暴露出来。

5.1 相等的距离与合并顺序的“玄学”

第一坑：多对簇的距离同时达到最小值时，合并哪一对？我在代码里用的是if d < best_d，也就是说只有严格小于才更新当前最优解，遇到相等就保留先扫到的。这个看似无关紧要的选择，会直接影响合并轨迹。

以单连接为例，第 2 到第 6 次合并的距离都是 0.7071，满足条件的候选对不止一对。我的扫描顺序是按下标从小到大，所以先扫到的 [0] 与 [1] 会被合并，而不是其他等距离候选。如果你把<改成<=，合并顺序可能变成先合并 [6,8] 与 [7]，后续结果看起来完全不同。

这不是 bug，但很容易被误判成 bug。尤其是你拿自己的结果和现成库对比时，发现合并顺序不一样，第一反应往往是代码写错了。实际上只差在平局处理策略。解决方法是明确把平局规则写进注释，或者统一成一种确定性规则，比如所有候选按左簇最小下标排序再选第一个。

5.2 距离矩阵的对称性隐患

第二个坑：距离矩阵是对称矩阵，dist[i][j]和dist[j][i]必须相等。我的实现里构建矩阵时同时填两个位置，天然保证对称。但如果你试图边合并边更新距离矩阵来优化性能，很容易只更新了上三角忘了下三角，导致后续取距离时出现非对称的脏数据。

我在这版实现里绕开了这个问题：两个簇之间的距离永远从原始点间距离矩阵里现算，而不是维护一个簇间距离矩阵。这样做每一步要多花一点时间，但彻底避免了更新时一手抖改错位置的问题。如果你的目标是性能，必须改用 Lance-Williams 递推公式，那时候对称性就是你需要重点盯着验证的地方。

5.3 失效簇的处理与防御性检查

第三个坑：合并之后，旧的簇必须立刻标记为失效，否则下一轮扫描会把同一个簇计算进去，甚至出现自我合并或合并空簇的荒唐结果。

我的做法是：合并时把 right 对应的簇置为frozenset()，并把active[right]设为False。同时用一个独立的num_active计数器控制循环终止条件，而不是每次去数 True 的数量。这样即使活跃标记出错，循环次数也不会失控。

调试时还有个小技巧：每轮循环开头加一条防御性断言，assert best_d < float("inf")，确保这一轮确实找到了有效合并。如果活跃簇管理出错，这条断言会立刻暴露问题，而不是让程序带着错误状态继续跑出离谱结果。

5.4 特征缩放与零向量边界

第四个坑不在算法本身，而在数据预处理。如果特征量纲差异很大，比如一个维度取值范围是 0 到 100，另一个是 0 到 0.01，欧氏距离会被大尺度维度完全主导，算法实际只“看”到了第一个维度的差异。手写实现时这个问题会变得特别刺眼，因为你能清楚看到距离矩阵里的数值几乎全部由单一维度贡献。

常规做法是聚类前做标准化，让每个特征均值为 0、方差为 1。调包时这一步经常被忽略，因为库不会提醒你；手写时你会被迫注意到距离数字的构成，这反而是一件好事。

另外，如果使用余弦距离，还要处理零向量。我写余弦函数时特意加了模长为 0 的保护，返回 1.0。你可以根据业务需要决定这个返回值，但绝不能让它抛异常，否则一个全零样本就能搞崩整个聚类流程。

6. 从 O(n³) 到实用：性能分析与 Lance-Williams 更新

我这份实现的复杂度是偏高的。距离矩阵构建是 O(n²)，每一次合并要扫描所有活跃簇对，也就是 O(n²) 个候选，而每个候选的计算量取决于两个簇内部的点对数量，最坏情况接近 O(n)。整体跑下来，最坏时间复杂度大约在 O(n³) 到 O(n⁴) 之间。对于九点测试数据毫无压力，但放到几千个样本上就会明显卡顿。

正规实现一般会引入 Lance-Williams 递推公式，它的核心思想是：合并簇 A 和 B 形成新簇 AB 之后，新簇与任意其他簇 C 的距离，可以直接从老的距离值递推出来，不需要再回到原始点对距离计算。

Lance-Williams 递推公式可以写成：

d(AB, C) = α_A × d(A, C) + α_B × d(B, C) + β × d(A, B) + γ × |d(A, C) − d(B, C)|

不同连接方式对应的系数如下：

其中 n_A、n_B、n_C 分别表示三个簇的样本数。

值得一提：单连接和全连接作为“最值”操作，居然能用线性组合和绝对值项表达出来，这一点我刚看到的时候也挺意外。它的本质是数学上的恒等变形，但对实现者来说意义重大——这意味着你可以用一套统一的递推框架，同时支持多种连接方式。

有了 Lance-Williams 递推，每轮合并之后更新簇间距离矩阵只需要 O(1) 时间，不需要再回扫原始点对。配合每轮维护一个堆（优先队列）来快速取最小距离，可以把整体复杂度降到接近 O(n² log n)。不过，堆方案有个麻烦：合并后，所有涉及到旧簇的距离项都要在堆里作废重建，惰性删除是常用手段。

如果你只是在业务里跑几百上千个样本，我这份朴素实现完全够用，运行时间可能也就几百毫秒。如果数据量到几十万级别，我强烈建议直接使用成熟的库，自己维护堆、索引、失效标记这些细节，成本极高，而且还容易踩到前面说的那些坑。手写版本最大的价值，是让你彻底弄清算法内部发生了什么，而不是让你用它去替代工业级实现。

最后分享一点我的使用习惯

把纯 Python 版层次聚类写完之后，我再也没删过它，反而成了工具箱里的常驻工具。现在做数据分析时，我会先用这个小实现跑一遍平均连接，看看合并距离有没有明显断层，判断数据是否真的有聚类结构；再用单连接跑一遍，检查是否存在链式效应，如果单连接的树状图把很多本应不同的样本串在一起，说明数据可能有连续性分布或者离群点问题。

还有一个小技巧：升级现成库的版本之后，我会用这版纯 Python 实现的合并顺序去对比新旧库的输出。如果合并历史完全一致，说明库的默认行为没有变；如果不一致，多半是平局策略、浮点精度或者默认参数有调整，而不是我的数据出了问题。这个习惯帮我避免了好几次被“库更新导致结果变化”搞到怀疑人生的尴尬处境。