如何用Python对成对组合中的相似值进行聚类分组

嗨，我来帮你搞定这个相似值聚类的问题！其实你选NetworkX的思路完全没问题，大概率是没找对正确的方法～ 下面我给你两种可行的方案，一种用NetworkX（帮你把之前的坑填上），另一种纯Python实现（不用任何第三方库），你可以按需选择：

方法一：用NetworkX快速实现 #

你的成对组合正好对应图里的「边」，每个值就是「节点」，而你要的聚类就是图里的连通分量——也就是所有能通过边连在一起的节点集合。NetworkX里有现成的方法直接提取这些分量，来看看具体代码：

import networkx as nx

col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'), 
             ('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'), 
             ('j','k')]

# 创建一个无向图对象
G = nx.Graph()
# 把所有成对组合作为边添加到图里
G.add_edges_from(col_combi)

# 提取所有连通分量，转成你需要的字符串格式
clusters = []
for component in nx.connected_components(G):
    # 这里用sorted是为了让结果更整齐，你也可以去掉sorted用任意顺序
    cluster_str = '-'.join(sorted(component))
    clusters.append(cluster_str)

# 输出结果
for cluster in clusters:
    print(cluster)

运行这段代码后，你会得到：

a-b-c-g
d-e-m-p-z
j-k-l-n-t

和你要的结果几乎一致，只是节点顺序略有不同（因为连通分量是无序集合），如果不需要严格和例子里的顺序一致，这个方法完全够用，而且代码超简洁。

方法二：纯Python并查集实现（无第三方依赖） #

如果你不想依赖任何外部库，那用经典的**并查集（Union-Find）**数据结构是最优解，这是处理这类连通性聚类问题的标准算法，效率也很高。直接上代码：

col_combi = [('a','b'), ('b','c'), ('d','e'), ('l','j'), ('c','g'), 
             ('e','m'), ('m','z'), ('z','p'), ('t','k'), ('k', 'n'), 
             ('j','k')]

# 实现并查集类
class UnionFind:
    def __init__(self):
        self.parent = {}
    
    def find(self, x):
        # 查找节点x的根节点，同时做路径压缩优化
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # 合并x和y所在的集合
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            self.parent[y_root] = x_root

# 初始化并查集，先把所有节点加进去
uf = UnionFind()
all_nodes = set()
for u, v in col_combi:
    all_nodes.add(u)
    all_nodes.add(v)
for node in all_nodes:
    uf.parent[node] = node

# 把每一对相似值合并到同一个集合
for u, v in col_combi:
    uf.union(u, v)

# 按根节点分组，转成需要的字符串格式
groups = {}
for node in all_nodes:
    root = uf.find(node)
    if root not in groups:
        groups[root] = []
    groups[root].append(node)

# 生成最终聚类结果，同样可以选择是否排序
clusters = ['-'.join(sorted(group)) for group in groups.values()]

# 输出结果
for cluster in clusters:
    print(cluster)

这个方法完全不依赖任何第三方库，而且处理大量数据时性能更优，适合需要轻量实现的场景。

备注：内容来源于stack exchange，提问作者Ömer Faruk Güllüoğlu