基于余弦相似度的K簇聚类：Kruskal算法在完全图上的MST应用困惑

嘿，这个问题其实戳中了MST聚类的核心逻辑——哪怕是连通的完全图，我们也不需要构建完整的生成树，而是利用Kruskal的合并过程提前终止，就能得到想要的k个簇。我给你一步步理清楚：

核心思路本质 #

我们的目标是把相似度越高（余弦相似度越大）的单词优先归为一类，而Kruskal算法的并查集（Union-Find）机制刚好能帮我们高效管理连通分量的合并。这里要注意：我们需要的是最大生成树（而非常规的最小生成树），因为边权是余弦相似度，权值越大代表两个单词越相似，要优先合并。

具体步骤拆解 #

• 第一步：预处理所有边
  因为是完全图，任意两个单词之间都有一条边，边权是它们的余弦相似度。把所有边按照余弦相似度从高到低排序——这一步是关键，确保我们先处理最相似的单词对。

• 第二步：初始化并查集
  给每个单词单独创建一个连通分量，此时总连通分量数等于单词总数n。并查集的作用就是快速判断两个单词是否已经在同一簇，以及合并不同的簇。

• 第三步：遍历边并合并分量，直到得到k个簇
  依次遍历排序后的每条边：

  1. 检查这条边连接的两个单词是否属于同一个连通分量（用并查集的find操作）。
  2. 如果不属于同一分量，就把这两个分量合并（用并查集的union操作），同时总连通分量数减1。
  3. 当总连通分量数恰好等于给定的k时，立刻停止遍历——不需要处理剩下的边了。

• 第四步：确定最终簇
  此时每个连通分量就是一个独立的簇：同一簇内的单词都是通过高相似度的边连接起来的，而不同簇之间还没被合并的边都是相似度较低的，完美符合聚类的需求。

为什么完全图也能这么做？ #

你困惑的点在于完全图是连通的，但MST聚类的核心根本不是要生成完整的生成树。我们只是借用Kruskal算法“按权值优先级合并连通分量”的过程，通过控制连通分量的数量，在达到k个的时候就停止，自然就得到了k个簇。

举个简单例子：假设你有5个单词，k=2。初始是5个独立分量，先合并相似度最高的两对，分量数降到3；再合并下一个最高的，分量数降到2，这时候就停手，剩下的两个分量就是你要的两个簇。

注意事项 #

• 一定要用最大生成树的逻辑（边按权值从大到小排序），如果搞成最小生成树（按权值从小到大），那就是优先合并最不相似的单词，完全违背聚类的初衷。
• 并查集一定要实现路径压缩和按秩合并，不然面对完全图的海量边（n*(n-1)/2条），效率会很低。

内容的提问来源于stack exchange，提问作者Habil Ganbarli