algorithm - 如何计算a列中每对值之间b列中共享值的数量？

Question

我有一个包含 2 列“la”和“lb”的数据框。我想计算每对“la”值之间的共享 lb 值的数量，条件不在相同的“la”值之间计算并且不计算一对无序两次，例如，不计算 (1, 1)，不计算 ( 2, 1) 如果计算 (1, 2)。您可以将其视为在“la”节点之间构建一个无向的、非自循环的加权图。

d = pd.DataFrame([[1, 0], [2, 0], [1, 1], [2, 1]], columns=['la', 'lb'])
d
Out[26]: 
   la  lb
0   1   0
1   2   0
2   1   1
3   2   1

# The final result I want:
   la_x  la_y  count_shared_lb
0     1     2   2
1   ...   ... ...
.
.
.

目前我正在做一个合并，然后是 groupby 和计数。

dd= d.merge(d, left_on='lb', right_on='lb')
dd
Out[27]: 
   la_x  lb  la_y
0     1   0     1
1     1   0     2
2     2   0     1
3     2   0     2
4     1   1     1
5     1   1     2
6     2   1     1
7     2   1     2

dd.groupby(['la_x', 'la_y'], sort=False).size().reset_index(name='count_shared_lb')
Out[30]: 
   la_x  la_y  count_shared_lb
0     1     1                2
1     1     2                2
2     2     1                2
3     2     2                2

但我被困在这里，因为我无法过滤掉不需要的行。更重要的是，数据框太大以至于合并耗尽了内存。

所以我有 2 个问题:有没有一种方法可以在不使用合并的情况下完成结果？如果没有，有没有办法过滤掉不需要的行(在首选合并之前)？

谢谢。

Answer 1

至于两个，您可以通过删除所有具有lb 唯一值的行来提前缩小d。这不会解决合并问题，但应该会稍微缩小初始占用空间。

counts = d.lb.value_counts()
uniq_lbs = set(counts[counts < 2].index)
d = d[~d.lb.isin(uniq_lbs)]

至于一个，最简单的答案是只删除 la_x >= la_y 的所有行，因为这应该涵盖所有冗余计数。也就是说，如果您改为通过 for 循环而不是一次大合并进行许多较小的合并，然后连接您的结果，那么效率可能会高得多。这应该让您首先跳过两次匹配。

la_vals = sorted(df.la.unique())
d_list = []
for i in range(len(la_vals)-1):
    left_d = d.loc[d.la == la_vals[i], :]
    right_d = d.loc[d.la.isin(la_vals[i:]), :]
    d_list.append(left_d.\
                         merge(right_d, left_on = 'lb', right_on = 'lb').\
                         loc[:, ['la_x', 'la_y']])

final_d = pd.concat(d_list)

您应该能够毫不费力地将上述内容并行化，因为 d 中的任何内容都没有被更改。如果这样做，请考虑在每个进程中进行计数，然后在最后使用总和聚合所有 la_x, la_y, count 三元组。

也就是说，根据您案例的具体情况，这里最大的问题是您将进行很多最坏情况下的相似性匹配——检查没有任何共同点的值。您可能想看看一些图形库，例如 networkx或 igraph看看图形算法是否对您有所帮助。