创建对称矩阵的有效方法，计算两个字符串属于同一列表的频率

Question

假设我有一个如下所示的数据框：

df = pd.DataFrame(columns = ["ID", "GROUP"])
df["ID"] = ["a1", "a2", "a3", "a4", "a5", "a6"]
df["GROUP"] = [ ["g1", "g3"], ["g2", "g3", "g5"], ["g3", "g5"], ["g2"] , ["g1", "g5"], ["g3"]]

给出：

df

      ID         GROUP
0     a1      [g1, g3]
1     a2  [g2, g3, g5]
2     a3      [g3, g5]
3     a4          [g2]
4     a5      [g1, g5]
5     a6          [g3]

和如下组列表：

GROUPS = ["g1", "g2", "g3", "g4", "g5", "g6"]

这里是我想得到的：

groups_df

   g1 g2 g3 g4 g5 g6
g1  2  0  1  0  1  0
g2  0  2  1  0  1  0
g3  1  1  4  0  2  0
g4  0  0  0  0  0  0
g5  1  1  2  0  3  0
g6  0  0  0  0  0  0

计算两个组出现在同一个列表中的次数（或两个组中存在多少个 ID）。

我的代码看起来像这样：

groups_df = pd.DataFrame(columns = GROUPS, index = GROUPS)

for group1 in GROUPS:

    for group2 in GROUPS:

        groups_df.loc[group1, group2] = df[(df.GROUP.map(set) & {group1}) & (df.GROUP.map(set) & {group2})].shape[0]

它有效，但是我的实际数据非常慢，其中包含 df 中的大约 200000 行和 GROUPS 中的大约 760 个不同的组，我想我的解决方案不是很干净。

最终目标是将 groups_df 与 NetworkX 结合使用。

你能想出更好的方法来实现这个目标吗？

非常感谢您阅读本文并提供任何帮助！

编辑 1：

根据@gboffi () 的建议，我运行以下内容：

data = np.array(df.GROUP)
items = GROUPS
sc = np.vectorize(list.__contains__)
t = sc(data[:, None], items)
groups_array = np.array([np.sum(t[t[:,i]], axis=0) for i in range(len(GROUPS))])
groups_df = pd.DataFrame(groups_array, columns = GROUPS, index = GROUPS)

实际数据的速度快得令人难以置信：仅 33 秒！非常感谢您的帮助。

不过，我会很乐意尝试其他比较建议。

Answer 1

下面是一个基于简单哈希图计数器的解决方案：

counter = defaultdict(int)

for group in df['GROUP']:
    for i in xrange(len(group)):
        for j in xrange(i, len(group)):
            counter[(group[i], group[j]) if group[i] <= group[j] else (group[j], group[i])] += 1

然后你可以将这个 hashmap 转换成你的目标数据帧：

data = {group: [counter.get((group, group2) if group <= group2 else (group2, group), 0) for group2 in GROUPS] for group in GROUPS}
groups_df = pd.DataFrame(data, columns=GROUPS)

但我确信应该有一些优雅的方法可以使用 pandas 数据帧功能来做到这一点。

Answer 2

结合使用正则表达式和数据框值过滤器怎么样？再次！可能还有一些其他的优化方式！只是其中之一，您可以使用您的数据集对代码段进行基准测试。

for row, series in groups_df.iterrows():  
  for column,d in series.items():
    pattern = row if row == column else r'%s.*%s|%s.*%s' % (row, column, column, row)
    regex = re.compile(pattern)
    groups_df[row][column] = len(filter(regex.search, df.GROUP.values))

Answer 3

我有这种间接的方法来解决你的问题，它有明显的好处在 Python 中成为 O(1)，因为其他循环（必要的）由 Numpy

执行

让我们从一些假数据（没有数据帧，只有 ndarrays）开始，根据 10 行集合数组，随机长度，包含从 0 到 4 的整数（含 0 到 4）

In [82]: import numpy as np
In [83]: import random
In [84]: items = np.arange(5)
In [85]: items
Out[85]: array([0, 1, 2, 3, 4])
In [86]: data = np.array([set(np.random.choice(items, random.randint(1, 5), False)) for _ in range(10)], dtype=set)
In [87]: data
Out[87]: array([{0, 2, 3}, {0, 1}, {2, 4}, {3, 4}, {3, 4}, {3, 4}, {0, 1, 2, 3, 4}, {3}, {2, 3, 4}, {1}], dtype=object)

接下来，我将这个相当紧凑的数据转换为布尔数组

In [88]: sc = np.vectorize(set.__contains__)
In [89]: t = sc(data[:, None], items)
In [90]: t
Out[90]: 
array([[ True, False,  True,  True, False],
       [ True,  True, False, False, False],
       [False, False,  True, False,  True],
       [False, False, False,  True,  True],
       [False, False, False,  True,  True],
       [False, False, False,  True,  True],
       [ True,  True,  True,  True,  True],
       [False, False, False,  True, False],
       [False, False,  True,  True,  True],
       [False,  True, False, False, False]], dtype=bool)

据我所知，如果您的数据稀疏，这可能需要大量额外内存，但这可以简化下一步

In [91]: np.array([np.sum(t[t[:,i]], axis=0) for i in items])
Out[91]: 
array([[3, 2, 2, 2, 1],
       [2, 3, 1, 1, 1],
       [2, 1, 4, 3, 3],
       [2, 1, 3, 7, 5],
       [1, 1, 3, 5, 6]])

这里我们对 t 的列（对应于不同的项目）求和，只选择项目所在的行。

两个备注

我认为这应该比 Python 中的两个显式循环更快，但我没有基准，至少目前没有...
我曾尝试使用广播对最后一个循环进行矢量化但无济于事，如果有人从我的回答开始要删除最后一个循环，如果他们 post自己回答。

创建对称矩阵的有效方法，计算两个字符串属于同一列表的频率

Efficient way to create a symmetric matrix counting how often two strings belong to the same list

python

performance

matrix

networkx

coding-efficiency