聚类具有任何列中的匹配元素值的行

Question

我正在尝试对行进行标记和聚类，其中 link 匹配任何列下的值。

row	id1	id2	id3
0	a	b	c
1	a	d	f
2	d	g	h
3	b	g	l
4	c	e	c

在上面的示例中，我们可以看到第 0 行和第 1 行在 id1 中与 'a' 匹配。但是 0 和 4 在 id3 中也与 'c' 匹配。因此第 0、1 和 4 行被分组在一个簇下。 2 和 3 在 id2 下匹配，因此它们被分组在另一个单独的集群中。它们将被标记为 cluster_id。

无论有多少行和额外的 id 列 n，我如何使用 pandas 自动执行此操作？我们可以假设没有重复行，并且它需要至少处理一百万条记录。

Answer 1

如评论所述，这是一个 networkx 问题。首先，我们需要构建邻接矩阵：

import networkx as nx

s = df.filter(like='id').values
G = nx.from_numpy_matrix((s == s[:,None]).any(axis=-1))

cluster = dict(enumerate(nx.connected_components(G)))
# {0: {0, 1, 4}, 1: {2, 3}}

请注意，我们使用广播来构造相邻矩阵，因此这种方法可能不适用于许多行。我会说它在 5k rows x 10 ids 左右（广播时大约 250M）

工作正常

另请注意，每个集群内的节点代表数据帧的 范围索引 ，而不是 row 列中的值。因此，如果您想知道集群 0 中的节点名称，您需要：

df['row'].iloc[list(cluster[0])]

更新：我们可以使用 melt 和 merge 来构建邻接关系，这对于长数据帧可能更好：

s = df.melt('row')
G = nx.from_pandas_edgelist(s.merge(s, on=['value','variable']), 
                            source='row_x', 
                            target='row_y')

这种方法会更好，因为节点名称取自列 row 中的值而不是索引。

聚类具有任何列中的匹配元素值的行

Clustering rows with matching element values in any column

python

networkx

pandas