层次聚类合并法大概是所有聚类算法里最“反直觉”的一个它不像 K-Means 那样要先回答“我要分几类”而是先把每个样本都当成独立的一簇然后一步一步把最近的两簇并在一起直到最后只剩一个簇。你可以在任何阶段停下来决定要几个簇。听起来很优雅但真上手实现的时候麻烦事全藏在这些“最近的两簇”里。我第一次学这个算法时直接调了现成库三行代码出结果聚类图也画得漂漂亮亮。直到有次项目中同事拿着我给的聚类结果追问为什么这两组先合并为什么换一种连接方式结果完全不一样我当时含糊其辞只能说是“算法决定的”。就是那次之后我决定用纯 Python 不调任何机器学习包把合并法层次聚类从零写一遍。这篇文章整理的就是完整实现过程、实测数据以及我在手写过程中反复踩进去的四个坑。1. 为什么还要手写合并法层次聚类有人会问现成库里的 AgglomerativeClustering 三行代码就能跑手写一遍不是自找麻烦吗我的观点是手写不是为了“重复造轮子”而是为了在必要时能修改轮子。调包实现看起来快但暴露出来的认知缺口很实际。比如你用现成库跑出一张树状图但说不清这几个问题两个簇之间的距离到底是怎么从“点与点的距离”汇总出来的为什么有些数据跑出来是均匀的树状结构有些是一串糖葫芦裁剪树状图的时候阈值该看合并距离的哪个位置如果业务上要求自定义一种连接方式现成库不支持怎么办这些问题的答案只有真正从零实现一遍才能消化。很多做算法的人大概都有类似的经历面试时能背出“单连接、全连接、平均连接”的定义但真到了要为一个特殊业务定义“两个簇之间的距离是加权平均再乘以某个系数”时才发现自己对数据结构的理解和算法细节的控制力完全不够。手写实现还有一个作用调试和比对。后来我再用现成库做层次聚类时会顺手跑一下自己的纯 Python 版本把合并顺序打出来对照。库升级、参数变化、异常数据导致的合并顺序异常都能第一时间发现。这有点像老司机熟悉车辆原理遇到仪表盘亮红灯时知道大概哪里出了问题而不是只会把车开进修理厂。这篇博文会用一组我自己构造的二维坐标数据作为实测样本完整过一遍合并法层次聚类从距离矩阵到最终合并记录的过程并对比三种常见连接方式在同样数据上的表现差异。2. 合并法的最小完整框架点间距离与类间距离合并法层次聚类的基本流程非常朴素一开始有 n 个样本每个样本是独立一簇。每一轮找出“距离最近”的两簇把它们合并成一簇不断重复直到只剩一个簇。整个过程记录下来就是一棵树状结构每次合并的高度就是合并时那两簇间的距离。这里有两个“距离”要区分清楚。2.1 点与点的距离三种常用度量第一个是样本点之间的原始距离这决定了“远近”的基本定义。实现时我不会限制死成一种代码里做成了可插拔的度量函数。度量方式公式适合场景欧氏距离坐标差平方和开根号特征量纲一致、空间结构明显时最常用曼哈顿距离坐标差的绝对值之和高维稀疏数据或希望降低离群值影响时余弦距离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_nameeuclidean): 构建对称距离矩阵。矩阵会被后续每次找最近簇时反复复用。 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, methodsingle, dist_nameeuclidean): 合并法层次聚类主流程。 返回 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) 组成第三簇。合并次序单连接全连接平均连接1[6] 与 [8]0.5000[6] 与 [8]0.5000[6] 与 [8]0.50002[0] 与 [1]0.7071[0] 与 [1]0.7071[0] 与 [1]0.70713[0,1] 与 [2]0.7071[3] 与 [4]0.7071[3] 与 [4]0.70714[3] 与 [4]0.7071[0,1] 与 [2]1.0000[0,1] 与 [2]0.85365[3,4] 与 [5]0.7071[3,4] 与 [5]1.0000[3,4] 与 [5]0.85366[6,8] 与 [7]0.7071[6,8] 与 [7]1.1180[6,8] 与 [7]0.91267[0,1,2] 与 [3,4,5]4.2426[0,1,2] 与 [3,4,5]5.7009[0,1,2] 与 [3,4,5]4.97808全部与 [6,7,8]4.6098全部与 [6,7,8]11.3360全部与 [6,7,8]7.7919这张表的信息量很大。先看单连接。它的前六次合并距离全部是 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)|不同连接方式对应的系数如下连接方式α_Aα_Bβγ单连接0.50.50−0.5全连接0.50.500.5平均连接n_A / (n_A n_B)n_B / (n_A n_B)00Ward(n_A n_C) / (n_A n_B n_C)(n_B n_C) / (n_A n_B n_C)−n_C / (n_A n_B n_C)0其中 n_A、n_B、n_C 分别表示三个簇的样本数。值得一提单连接和全连接作为“最值”操作居然能用线性组合和绝对值项表达出来这一点我刚看到的时候也挺意外。它的本质是数学上的恒等变形但对实现者来说意义重大——这意味着你可以用一套统一的递推框架同时支持多种连接方式。有了 Lance-Williams 递推每轮合并之后更新簇间距离矩阵只需要 O(1) 时间不需要再回扫原始点对。配合每轮维护一个堆优先队列来快速取最小距离可以把整体复杂度降到接近 O(n² log n)。不过堆方案有个麻烦合并后所有涉及到旧簇的距离项都要在堆里作废重建惰性删除是常用手段。如果你只是在业务里跑几百上千个样本我这份朴素实现完全够用运行时间可能也就几百毫秒。如果数据量到几十万级别我强烈建议直接使用成熟的库自己维护堆、索引、失效标记这些细节成本极高而且还容易踩到前面说的那些坑。手写版本最大的价值是让你彻底弄清算法内部发生了什么而不是让你用它去替代工业级实现。最后分享一点我的使用习惯把纯 Python 版层次聚类写完之后我再也没删过它反而成了工具箱里的常驻工具。现在做数据分析时我会先用这个小实现跑一遍平均连接看看合并距离有没有明显断层判断数据是否真的有聚类结构再用单连接跑一遍检查是否存在链式效应如果单连接的树状图把很多本应不同的样本串在一起说明数据可能有连续性分布或者离群点问题。还有一个小技巧升级现成库的版本之后我会用这版纯 Python 实现的合并顺序去对比新旧库的输出。如果合并历史完全一致说明库的默认行为没有变如果不一致多半是平局策略、浮点精度或者默认参数有调整而不是我的数据出了问题。这个习惯帮我避免了好几次被“库更新导致结果变化”搞到怀疑人生的尴尬处境。
