最近在整理一批文档向量需要按相似度把样本逐步归堆我顺手用C完整实现了一遍AGNES层次聚类。AGNES全称是Agglomerative Nesting是层次聚类里最经典的自底向上方法整个过程像“先找最近的两个人再找最近的两个圈子最后合并成一个大团体”。这篇文章把我实现过程中的核心思路、数据结构选型、代码细节和踩坑记录都拆开讲一遍适合刚接触聚类算法、或者想在C工程里不依赖外部库直接内嵌一个聚类模块的同学参考。代码量不大但里面的细节足够你写一个能输出合并历史的可靠实现。1. 项目概述与整体思路拆解1.1 AGNES要解决的问题把数据逐步“合并成伙”AGNES的核心逻辑用一个词概括就是“贪心合并”。初始状态下每个样本点单独作为一个簇然后每一轮都从所有簇对中找出距离最小的两个簇合并成一个新簇接着更新新簇和其他簇之间的距离继续重复直到达到你设定的目标簇数或者只剩一个簇为止。这个“谁跟谁走得近就先合并”的序列会形成一棵聚类树也就是树状图。树状图的好处是可以随时从不同高度切开得到不同粒度的聚类结果。举个例子如果从靠近根部的地方切高度阈值大簇数少、颗粒粗糙如果在靠近叶子的地方切簇数就多、划分更细。这类算法的优势在于不需要预先设定初始中心点。K-Means对初始中心敏感还经常需要反复跑几轮选随机种子AGNES在这方面省心得多。而且它天然支持非凸簇形状尤其是配合单链接时可以发现细长的、带流形结构的数据分布。实际使用场景包括文档语义归类、用户行为分群、图片颜色量化以及任何“结果需要带层级关系”的分析任务。1.2 为什么我选择用C手写而不是直接调库很多人一开始会问Python里有现成的层次聚类库或者C里也有不少开源库为什么还要自己实现一遍我个人的习惯是学习算法最有效的方式就是把它从零写一遍。调库的时候你面对的是一个黑盒传个参数等结果一旦数据形状怪异你想看一眼中间过程都无从下手。手写AGNES之后你才能真正理解“簇间距离”的几种定义、优先队列里失效项怎么处理、并查集是怎么跟簇ID配合的。另外如果你需要在C服务里嵌入一个聚类模块引入一个庞大的第三方库是很重的负担。AGNES本身原理不复杂自己写一个核心实现不到一千行可控性好也方便按业务需求定制距离函数。我这次就自定义了一个带权重的欧氏距离改起来非常方便。还有一个原因是性能可控。通用库为了适配各种场景会做很多抽象内存分配和虚函数调用开销都不小。自己实现可以直接控制数据结构比如提前reserve好内存、避免频繁拷贝、用数组而不是指针堆等。在小规模数据集上差别不明显但在某些嵌入式服务里这种控制力很重要。1.3 整体设计从距离矩阵到合并历史整个实现我拆成了几个相对独立的模块数据层样本点数组每个点包含一个特征向量和一个原始索引。距离矩阵所有样本两两之间的距离因为是对称矩阵我只保存上三角。优先队列最小堆维护所有“簇对距离”的候选项。并查集维护每个样本当前属于哪个根簇用于合并和最终输出标签。合并历史记录每次合并的两个簇ID、合并距离、合并后规模供后续画树状图或调整簇数。核心循环一句话就能说清楚从最小堆里取出距离最小的簇对检查两个簇是否还活跃如果有效就合并然后把新簇与所有其他活跃簇的距离重新压入堆。听起来很顺但真正的坑全在“检查有效”和“重新压堆”这两步里。别急下面逐个展开。2. 核心细节解析与数据结构选型2.1 样本表示与距离矩阵别把对称矩阵的索引写错我在代码里直接用std::vectorstd::vectordouble来存样本每个内层向量是一个样本的特征向量。这个容器的好处是访问简单缺点是内层向量可能分散在内存里缓存不友好。对于十万级以下的数据集性能完全够用就没必要上自定义连续内存结构了。距离矩阵有两种存法完整二维数组包括对角线和对称位置或者只存上三角。我选择只存上三角因为能省大约一半内存。代价就是访问的时候要小心dist[i][j]必须先判断i和j的大小保证i j。这个「交换下标」的操作被很多人忽略一旦写错初始化堆的时候就会出现重复项或者直接漏项。// 只保存上三角距离矩阵 double getDist(const vectorvectordouble dist, int i, int j) { if (i j) return 0.0; if (i j) std::swap(i, j); return dist[i][j]; }决定每个样本内部维度的标准化工作也应该在算距离之前做好否则量纲差异会直接影响欧氏距离的结果。这一点我会在后面的常见问题里专门讲因为它真的是最容易犯的错误之一。2.2 簇间距离的三种定义单链接、全链接、平均链接怎么选AGNES的“合并依据”有几种常见定义。所谓簇A和簇B的距离并不是两个“整体”的简单点距而是基于A、B中所有样本点对的距离再聚合。单链接Single Linkage取的是两个簇之间所有样本点对距离的最小值。它相当于只要两个圈子之间有一个人认识对方就认为两个圈子很近。单链接可以处理细长条、流形状的数据簇但也很容易产生“链式效应”中间经过一连串样本点把两个本来差距很大的簇最终连在一起这在噪声较多的数据里是个大问题。全链接Complete Linkage取的是所有点对距离的最大值相当于两个圈子必须“所有人都觉得近”才合并。它倾向于生成紧凑的球形簇对噪声相对稳定但如果真实数据是细长条或带环状的用全链接会把它们硬拆成好几块。平均链接Average Linkage取所有点对距离的平均值是介于两者之间的折中。实际项目里如果拿不准通常默认先试平均链接。缺点是计算量最大因为每次合并都要重新遍历两个簇的所有点对。如果数据量上去了建议换用基于簇中心的“中心链接”来做近似后面会提到。从实现角度看这三种距离都只需要写一个clusterDist()函数根据链接类型走不同分支即可。我习惯把这个函数独立出来只改一个函数就可以切换策略方便做对比实验。2.3 优先队列并查集懒删除方案才是核心AGNES实现里最考验代码功底的就是优先队列和并查集的配合。std::priority_queue不支持任意元素的删除和修改。每次合并两个簇之后所有涉及旧簇的距离项都失效了你又不能把它们从堆里抠掉。这时有两种思路一种是换成std::set或手动维护索引实现真正的动态更新另一种就是“懒删除”法——把失效项留在堆里取堆顶时检查涉及的簇是否还活跃不活跃就丢掉继续取直到找到有效项。懒删除的实现最简单代价是堆里会堆积大量历史失效项。以我的实测数据来说样本量在一千左右时堆里虽然垃圾项不少但影响不大样本量到五千以上堆的内存和时间开销就开始上升。到那个规模我会考虑改用Lance-Williams递推公式维护动态距离矩阵这个留在后面单独说。并查集这边我用它来维护样本之间的连通关系。初始时每个样本自成一个集合合并两个簇时把两个集合的根union到一起。但是并查集查找的结果是“根样本的索引”而不是“簇ID”。所以我额外维护了一个rootToClusterId映射把每个并查集根的样本索引映射到当前最新的簇ID。最终输出标签时对每个样本做一次find再查表就能稳定得到它所属的簇不需要在每个样本上反复更新字段。2.4 进阶Lance-Williams递推公式能省多少计算如果你只是跑通小规模Demo懒删除堆的方案已经够了。但如果你要把样本量撑到上万我就建议了解一下Lance-Williams递推公式。这个公式的作用是只用旧的簇间距离就能O(1)算出合并后的新簇到其他任意簇的距离而不用重新遍历点对。具体公式看起来有点抽象以合并簇A和B形成新簇T、计算T到簇C的距离为例通用形式如下d(T, C) α_A·d(A, C) α_B·d(B, C) β·d(A, B) γ·|d(A, C) - d(B, C)|其中 α、β、γ 取决于你选择的链接准则。比如单链接时α_A α_B 0.5β 0γ -0.5它会退化成min(d(A,C), d(B,C))。平均链接和全链接也有对应的系数组合。这个公式的好处是你可以在代码里维护一个活跃簇集合配合一个动态更新的距离矩阵每次合并只需要更新一行和一列。相比每次全量扫点对复杂度能降一个量级。我当时是在n3000左右的数据上做对比用朴素的平均链接跑了将近两分钟用LW公式版本几秒就出结果了。如果你打算把AGNES用到生产环境这个优化很值得做。3. 实操过程C实现的关键环节3.1 数据加载先标准化再算距离我这次的输入文件是文本格式每行一个样本列之间用空格或逗号分隔最后一列可以带样本名。加载函数就是很朴素的行读取加字符串流解析不依赖任何外部库。数据解析完紧接着做一次z-score标准化。标准化这一步很多人图省事会跳过但如果你不想让某个高数值维度直接把其他特征压死这一步必须做。标准化的方式很简单对每个特征列先求均值和标准差然后每个值变成(x - mean) / std。需要注意标准差为0的情况比如某列全是同一个值这种列直接跳过因为它对距离没有任何区分力。void standardize(vectorvectordouble data) { size_t dims data[0].size(); for (size_t j 0; j dims; j) { double mean 0.0; for (size_t i 0; i data.size(); i) mean data[i][j]; mean / data.size(); double var 0.0; for (size_t i 0; i data.size(); i) { var (data[i][j] - mean) * (data[i][j] - mean); } var / data.size(); double std sqrt(var 1e-12); // 防止除零 for (size_t i 0; i data.size(); i) { data[i][j] (data[i][j] - mean) / std; } } }我加了一个1e-12的平滑项纯粹是防守避免某列方差为0时除零崩溃。这个细节虽小但在真实脏数据上很管用。3.2 堆的初始化所有点对入优先队列初始化时每个样本本身就是一个簇。样本i的簇ID就是i样本j的簇ID就是j。我把所有满足i j的样本对距离都计算出来然后压入优先队列。这样堆里一开始就有n * (n - 1) / 2个候选项。优先队列的元素我定义成一个结构体包含距离和两个簇ID再写一个比较器让它变成小顶堆struct HeapItem { double dist; int c1, c2; }; struct HeapCompare { bool operator()(const HeapItem a, const HeapItem b) const { if (a.dist ! b.dist) return a.dist b.dist; // 小顶堆 if (a.c1 ! b.c1) return a.c1 b.c1; return a.c2 b.c2; } };这里在距离相等时比较簇ID是为了让算法结果可复现。如果不加这个稳定排序两个距离完全相等的候选谁能先被取出来不确定虽然最终聚类结果不一定受影响但调试的时候会非常难受。堆初始化的时间复杂度是O(n^2 log n)。要注意的是如果n到5000堆里候选项大约1250万个内存占用和插入耗时都会明显增长。这也是为什么我说AGNES更适合中小规模数据。3.3 主循环合并、更新、记录合并历史主循环是整个算法的心脏。我直接贴核心代码再逐段说明。while (activeCnt targetK) { bool found false; while (!pq.empty()) { HeapItem item pq.top(); pq.pop(); if (!alive[item.c1] || !alive[item.c2]) continue; // 失效项 if (item.c1 item.c2) continue; Cluster c1 clusters[item.c1]; Cluster c2 clusters[item.c2]; int newId idCounter; Cluster nc; nc.id newId; nc.active true; nc.memberIdx c1.memberIdx; nc.memberIdx.insert(nc.memberIdx.end(), c2.memberIdx.begin(), c2.memberIdx.end()); alive[item.c1] alive[item.c2] false; activeCnt--; // 合并并查集 int r1 uf.find(c1.repSample); int r2 uf.find(c2.repSample); int newRoot uf.unite(r1, r2); rootToClusterId[newRoot] newId; mergeHistory.push_back({item.c1, item.c2, item.dist, (int)nc.memberIdx.size()}); // 新簇与所有活跃旧簇之间的距离入堆 for (int other 0; other idCounter; other) { if (!alive[other] || other newId) continue; double d clusterDist(nc, clusters[other], linkType); pq.push({d, newId, other}); } clusters.push_back(std::move(nc)); found true; break; } if (!found) break; // 堆清完仍没有有效项 }这里的第一个关键点是alive数组。我最初用固定大小的vectorbool后来发现簇ID会一直增长旧簇还要保留Cluster结构供clusterDist用所以干脆用vectorchar并随idCounter动态扩容。Cluster里的memberIdx保存了这个簇包含的原始样本索引。合并时直接把两个成员索引列表拼接而不是重新创建一个新的大数组再拷贝这样能省不少内存。第二个关键点是并查集合并。每个Cluster里我存了一个repSample它是该簇在并查集里的代表性样本。合并时找到两个簇的根union之后新的根样本就是新簇的代表。把这个做法跟“直接遍历样本更新簇ID”相比省去了每次合并都要扫描成员数组的开销最终输出标签也更可靠。第三个关键点是新簇距离计算。合并完新簇理论上跟所有旧簇都可能产生新距离所以要遍历活跃簇列表重新算一遍并压入堆。这里的复杂度是O(n)次距离计算每次平均链接要遍历两个簇的成员点对所以整体开销比较高。如果你用的是单链接或全链接可以只更新距离矩阵如果用平均链接建议拆成“先算点对和再加总”的优化形式或者接受小规模数据的开销。3.4 结果输出并查集标签与合并树导出算法结束后我通常不会直接输出一个固定的簇标签就算了而是同时输出两个东西一是每个样本的所属簇ID二是完整的合并历史。簇ID的输出利用并查集逻辑非常干净for (int i 0; i n; i) { int root uf.find(i); int clusterId rootToClusterId[root]; cout 样本 i - 簇 clusterId endl; }find会返回该样本在并查集里的根样本索引再由rootToClusterId映射到最新的簇ID。这样就不需要维护sampleClusterId数组也避免了合并时大量更新操作。合并历史我建议输出成简单的JSON格式每一条记录包含两个子簇ID、合并时距离、合并后规模。后续不管是检查算法行为还是外部脚本画树状图都直接可用。{type: merge, cluster_id: 18, children: [7, 11], height: 1.24, size: 15}如果你一开始不知道目标簇数我的建议是不要急着设targetK先合并到只剩1个簇把整棵聚类树保留下来再结合业务需要去树状图上选一个断开高度。这样的用法更灵活。4. 常见问题与排查技巧实录4.1 失效堆顶导致死循环我第一次写主循环时犯的错误是从堆里取出失效项后用continue继续取但外层循环没有正确判断“是否找到了有效项”。结果当堆里全是失效项时外层while (activeCnt targetK)会一直运行内层却一直在空转最后直接死循环。解决办法就是我前面代码里写的内层while里一旦找到有效项就found true; break;如果循环结束后found仍为false就说明堆已经扫空或者没有可合并的簇了直接跳出外层。这个found标记看起来简单但它是防止死循环的关键。4.2 平均链接性能爆炸平均链接的计算量是最大的。初始堆里倒还好因为每个簇只有一个点两两距离直接查矩阵即可。麻烦的是合并之后每次计算新簇到其他簇的距离都要遍历新簇的所有成员和其他簇的所有成员。如果你用的是朴素三层循环数据量稍微上来就会卡到怀疑人生。我自己的经验边界大致是这样样本量小于500随便写都能跑1000到3000需要做一点优化5000以上平均链接就不太现实了要么换中心链接要么上Lance-Williams。另外平均链接其实可以写成“维护每个簇的成员点算距离时先求点对和再加总平均”比反复调用euclidean()要快不少。4.3 标签输出错位另一个很常见的坑是最终标签输出错误。有些人会在合并时直接遍历memberIdx把所有成员的“当前簇ID”改成新簇ID。听起来没问题但实际运行时某个成员的“当前簇ID”可能早就不是直接可用的簇ID了。因为排序问题或者多次合并后旧簇ID可能已经失效你再往回查就查到一个错误的簇。我最后采用的方式是彻底放弃“给每个样本存簇ID”的思路统一用并查集查根再映射到最新簇ID。实践证明这种方式最稳不会因为中间状态混乱而输出错位标签。4.4 欧氏距离的陷阱没标准化结果完全不同这个坑太经典了。假设有两个人身高精确到米大约1.7体重精确到公斤大约60如果直接算欧氏距离体重那一维几乎主导了整个距离身高维的作用可以忽略。这样聚类出来的结果基本等于“只按体重分”。我在做文档向量时没踩这个坑因为词频已经做过归一化。但一旦换成用户画像、传感器信号等混合量纲数据漏做标准化几乎必然翻车。标准化方式我用的是z-score也就是每个维度减均值再除标准差。如果你希望所有维度都落在相似范围也可以用min-max归一化区别不大关键是别不做。4.5 距离为零的重复样本要不要处理当数据里有完全重复的样本堆里会出现大量dist 0的候选。这些项会优先被取出合并顺序明确最终聚类结果一般不会出错但是会非常消耗计算资源。我在跑一份清洗不彻底的业务数据时堆里几乎全是0距离项瞬间觉得算法“卡死”了其实只是在疯狂合并重复点。如果你的数据里确实存在重复样本建议一开始就去重把特征完全相同的点合并成一个记录重复次数。聚类结束后给每个簇加权即可。这不仅能加快计算还能减少堆里零距离项的干扰。4.6 其他参数建议与实测心得最后整理一份参数速查表方便你复现时参考参数/选择建议原因目标簇数无先验时先合并到1再从树状图选高度保留完整层级信息更灵活链接准则默认平均链接细长簇用单链接紧凑球簇用全链接不同准则对应不同数据形态欧氏距离先做z-score标准化避免量纲差异主导距离距离矩阵只存上三角访问时交换下标省内存实现也简单线程/内存n 5000 时内存可控n 10000 时距离矩阵会超过几百MB优先队列懒删除配合found标记避免死循环实现最省事我在实际跑这个实现时最深的体会是AGNES的代码框架不难难的是把“合并后状态”维护清楚。你只要处理好了失效堆顶、并查集映射、距离更新这三件事整个算法就稳了大半。最后再分享一个小技巧不管项目多小都坚持输出合并历史。哪怕只是每轮一行log记录“谁和谁合并了、合并距离多少、活跃簇还剩几个”调试的时候你会发现自己能清楚地看到算法每一步在想什么。这比事后追着bug猜来猜去要高效得多。