如何对重叠列表类型的Destination字段进行聚类分组

问题背景 #

给定包含列表类型字段的Pandas DataFrame：

import pandas as pd
df = pd.DataFrame({
    'ID': ['A','B','C','D','E','F'],
    'Destination': [['x','y'],['m','n'],['x','k'],['x','k','y'],['m'],['p','h']]
})

对应表格：

需要将Destination字段中存在重叠元素的行聚类分组，得到合并后的目标元素集合与对应ID列表，期望输出：

要求避免迭代方法，适配大数据量场景。

解决方案：基于图论连通分量 #

这类问题本质是识别共享元素的连通组，使用图论算法可高效处理，无需提前指定分组数。以下是实现步骤：

步骤1：构建关联图 #

以ID为节点，通过共享的目标元素建立连接（用元素作为中间节点，自动连通所有包含该元素的ID）。

步骤2：提取连通分量 #

识别图中所有独立的ID连通组。

步骤3：生成结果 #

对每个连通组，合并所有目标元素并去重，收集对应ID列表。

代码实现 #

import pandas as pd
import networkx as nx
from itertools import chain

# 初始化数据
df = pd.DataFrame({
    'ID': ['A','B','C','D','E','F'],
    'Destination': [['x','y'],['m','n'],['x','k'],['x','k','y'],['m'],['p','h']]
})

# 构建图：用目标元素作为中间节点，连接所有包含该元素的ID
G = nx.Graph()
for _, row in df.iterrows():
    current_id = row['ID']
    G.add_node(current_id)
    # 给当前ID和每个目标元素连边，自动连通共享元素的ID
    for elem in row['Destination']:
        G.add_edge(current_id, elem)

# 提取仅包含ID的连通分量（过滤元素节点，这里假设ID为大写字母，元素为小写）
connected_id_groups = []
for component in nx.connected_components(G):
    id_group = [node for node in component if node.isupper()]
    if id_group:
        connected_id_groups.append(id_group)

# 生成结果DataFrame
result = []
for group in connected_id_groups:
    # 合并该组所有目标元素并去重
    all_elements = set(chain.from_iterable(df[df['ID'].isin(group)]['Destination']))
    result.append({
        'Destination_Group': sorted(all_elements),
        'ID_Group': sorted(group)
    })

result_df = pd.DataFrame(result)
print(result_df)

输出结果 #

Destination_Group ID_Group
0           [k, x, y]  [A, C, D]
1           [m, n]     [B, E]
2           [h, p]     [F]

方法优势 #

• 无嵌套迭代，networkx的连通分量算法时间复杂度接近线性，适合大数据量。
• 自动识别所有独立分组，无需提前定义分组数量。
• 若ID与目标元素命名冲突，可给元素节点加前缀（如elem_）区分，避免混淆。

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