如何在Python中基于直接/间接连接高效聚类800万KV对？及相关数学问题

对应的数学模型 #

这个问题本质是无向图的连通分量求解问题，也属于等价类划分问题：

• 每个K对应图中的一个节点
• 若两个K共享任意一个V，则节点间存在边（直接关联）；通过V间接关联的K会被归为同一连通分量（等价类）
• 最终的聚类结果就是图中所有的连通分量

高效实现方案：并查集（Union-Find/DSU） #

针对800万条数据的规模，直接构建节点间的边会导致内存过载，因此采用反向映射+并查集的方式，以V为中间媒介合并关联K，步骤如下：

1. 数据预处理 #

将原始KV对转换为V到K的映射：键是V，值是该V关联的所有K的集合。比如示例数据处理后得到：

V1: {K1, K2, K5}
V2: {K1}
V3: {K1}
V4: {K2}
V5: {K3}
V6: {K4, K5}

2. 初始化并查集 #

为每个K创建独立集合，每个K的父节点初始化为自身，同时维护秩信息用于优化合并操作。

3. 合并关联K #

遍历每个V对应的K集合：

• 取集合中第一个K作为基准，将其余所有K与基准K执行合并操作
• 共享同一V的K会被归为同一集合，间接关联的K也会通过多轮合并最终归为同一集合

4. 生成聚类结果 #

遍历所有K，通过并查集的查询操作找到每个K的根节点，将同一根节点下的K归为一个聚类。

Python实现示例 #

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩优化
        return self.parent[x]
    
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        # 按秩合并优化
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

# 模拟800万条数据的输入结构（示例用小规模数据）
kv_data = {
    'K1': {'V1', 'V2', 'V3'},
    'K2': {'V1', 'V4'},
    'K3': {'V5'},
    'K4': {'V6'},
    'K5': {'V1', 'V6'}
}

# 构建V到K的映射
v_to_ks = {}
for k, vs in kv_data.items():
    for v in vs:
        v_to_ks.setdefault(v, []).append(k)

# 初始化并查集
uf = UnionFind()
for k in kv_data.keys():
    uf.parent[k] = k
    uf.rank[k] = 0

# 执行合并操作
for ks in v_to_ks.values():
    if len(ks) < 2:
        continue
    base_k = ks[0]
    for k in ks[1:]:
        uf.union(base_k, k)

# 生成最终聚类
clusters = {}
for k in kv_data.keys():
    root = uf.find(k)
    clusters.setdefault(root, set()).add(k)

# 输出结果
for idx, (_, ks) in enumerate(clusters.values(), 1):
    print(f"C{idx} = {ks}")

复杂度说明 #

• 时间复杂度：O(N α(N))，N为K的数量，α是阿克曼函数的反函数，增长极慢，几乎可视为常数
• 空间复杂度：O(N + M)，N为K的数量，M为V的数量，远低于直接构建节点边的方案

方案优势对比 #

临时聚类再合并的方式通常需要多次遍历和集合合并，时间复杂度可达O(N²)，完全无法处理800万级别的数据；而并查集的路径压缩+按秩合并优化，确保了近乎线性的时间复杂度，能高效支撑大规模数据处理。

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