有没有办法向量化计数项目在 pandas/numpy 中的共现？
Is there a way to vectorize counting items' co-occurences in pandas/numpy?
我经常需要根据列中项目的共现生成网络图。我从这样的事情开始：
letters
0 [b, a, e, f, c]
1 [a, c, d]
2 [c, b, j]
在下面的例子中，我想要一个table所有字母对，然后有一个"weight"列，它描述了每两个字母有多少次字母对一起出现在同一行（例如见底部）。
我目前正在使用 for 循环来完成它的大部分工作，我想知道是否有办法对其进行矢量化，因为我经常处理大量的数据集，这些数据集需要很长时间才能处理这边走。我还担心将事情保持在内存限制内。这是我现在的代码：
import pandas as pd
# Make some data
df = pd.DataFrame({'letters': [['b','a','e','f','c'],['a','c','d'],['c','b','j']]})
# I make a list of sets, which contain pairs of all the elements
# that co-occur in the data in the same list
sets = []
for lst in df['letters']:
for i, a in enumerate(lst):
for b in lst[i:]:
if not a == b:
sets.append({a, b})
# Sets now looks like:
# [{'a', 'b'},
# {'b', 'e'},
# {'b', 'f'},...
# Dataframe with one column containing the sets
df = pd.DataFrame({'weight': sets})
# We count how many times each pair occurs together
df = df['weight'].value_counts().reset_index()
# Split the sets into two seperate columns
split = pd.DataFrame(df['index'].values.tolist()) \
.rename(columns = lambda x: f'Node{x+1}') \
.fillna('-')
# Merge the 'weight' column back onto the dataframe
df = pd.concat([df['weight'], split], axis = 1)
print(df.head)
# Output:
weight Node1 Node2
0 2 c b
1 2 a c
2 1 f e
3 1 d c
4 1 j b
备注：
如其他答案中所建议，使用 collections.Counter 进行计数。由于它的行为类似于 dict，因此它需要可散列的类型。 {a,b} 不可散列，因为它是一个集合。将其替换为元组可以修复可散列性问题，但会引入可能的重复项（例如 ('a', 'b') 和 ('b', 'a')）。要解决此问题，只需对元组进行排序。
因为 sorted returns 一个 list，我们需要把它转回一个元组：tuple(sorted((a,b)))。有点麻烦，但与 Counter.
组合起来很方便
快速简单的加速：理解而不是循环
重新排列后，您的嵌套循环可以替换为以下理解：
sets = [ sorted((a,b)) for lst in df['letters'] for i,a in enumerate(lst) for b in lst[i:] if not a == b ]
Python 对理解执行进行了优化，因此这已经带来了一些加速。
好处：如果将它与 Counter 结合使用，您甚至不需要将结果作为列表，而是可以使用 生成器表达式 （几乎不需要使用额外的内存而不是存储所有对）：
Counter( tuple(sorted((a, b))) for lst in lists for i,a in enumerate(lst) for b in lst[i:] if not a == b ) # note the lack of [ ] around the comprehension
评估：什么是更快的方法？
像往常一样，在处理性能时，最终的答案必须来自测试不同的方法并选择最佳的方法。
在这里，我比较了@yatu 的（IMO 非常优雅和可读）基于 itertools 的方法，原始的嵌套 for 和理解。
所有测试 运行 都是在相同的样本数据上随机生成的，看起来像给定的例子。
from timeit import timeit
setup = '''
import numpy as np
import random
from collections import Counter
from itertools import combinations, chain
random.seed(42)
np.random.seed(42)
DF_SIZE = 50000 # make it big
MAX_LEN = 6
list_lengths = np.random.randint(1, 7, DF_SIZE)
letters = 'abcdefghijklmnopqrstuvwxyz'
lists = [ random.sample(letters, ln) for ln in list_lengths ] # roughly equivalent to df.letters.tolist()
'''
#################
comprehension = '''Counter( tuple(sorted((a, b))) for lst in lists for i,a in enumerate(lst) for b in lst[i:] if not a == b )'''
itertools = '''Counter(chain.from_iterable(combinations(sorted(i), r=2) for i in lists))'''
original_for_loop = '''
sets = []
for lst in lists:
for i, a in enumerate(lst):
for b in lst[i:]:
if not a == b:
sets.append(tuple(sorted((a, b))))
Counter(sets)
'''
print(f'Comprehension: {timeit(setup=setup, stmt=comprehension, number=10)}')
print(f'itertools: {timeit(setup=setup, stmt=itertools, number=10)}')
print(f'nested for: {timeit(setup=setup, stmt=original_for_loop, number=10)}')
运行 上面的代码在我的机器上 (python 3.7) 打印：
Comprehension: 1.6664735930098686
itertools: 0.5829475829959847
nested for: 1.751666523006861
因此，两种建议的方法都比嵌套 for 循环有所改进，但 itertools 在这种情况下确实更快。
为了提高性能，您可以使用 itertooos.combinations 从内部列表中获取所有长度的 2 组合，并使用 Counter 计算展平列表中的对。
请注意，除了从每个子列表中获取所有组合之外，排序是必要的步骤，因为它将确保所有的元组对以相同的顺序出现：
from itertools import combinations, chain
from collections import Counter
l = df.letters.tolist()
t = chain.from_iterable(combinations(sorted(i), r=2) for i in l)
print(Counter(t))
Counter({('a', 'b'): 1,
('a', 'c'): 2,
('a', 'e'): 1,
('a', 'f'): 1,
('b', 'c'): 2,
('b', 'e'): 1,
('b', 'f'): 1,
('c', 'e'): 1,
('c', 'f'): 1,
('e', 'f'): 1,
('a', 'd'): 1,
('c', 'd'): 1,
('b', 'j'): 1,
('c', 'j'): 1})
使用稀疏关联矩阵的 numpy/scipy 解决方案：
from itertools import chain
import numpy as np
from scipy import sparse
from simple_benchmark import BenchmarkBuilder, MultiArgument
B = BenchmarkBuilder()
@B.add_function()
def pp(L):
SZS = np.fromiter(chain((0,),map(len,L)),int,len(L)+1).cumsum()
unq,idx = np.unique(np.concatenate(L),return_inverse=True)
S = sparse.csr_matrix((np.ones(idx.size,int),idx,SZS),(len(L),len(unq)))
SS = (S.T@S).tocoo()
idx = (SS.col>SS.row).nonzero()
return unq[SS.row[idx]],unq[SS.col[idx]],SS.data[idx] # left, right, count
from collections import Counter
from itertools import combinations
@B.add_function()
def yatu(L):
return Counter(chain.from_iterable(combinations(sorted(i),r=2) for i in L))
@B.add_function()
def feature_engineer(L):
Counter((min(nodes), max(nodes))
for row in L for nodes in combinations(row, 2))
from string import ascii_lowercase as ltrs
ltrs = np.array([*ltrs])
@B.add_arguments('array size')
def argument_provider():
for exp in range(4, 30):
n = int(1.4**exp)
L = [ltrs[np.maximum(0,np.random.randint(-2,2,26)).astype(bool).tolist()] for _ in range(n)]
yield n,L
r = B.run()
r.plot()
我们看到此处介绍的方法 (pp) 具有典型的 numpy 常量开销，但从大约 100 个子列表开始它开始获胜。
OP 示例：
import pandas as pd
df = pd.DataFrame({'letters': [['b','a','e','f','c'],['a','c','d'],['c','b','j']]})
pd.DataFrame(dict(zip(["left", "right", "count"],pp(df['letters']))))
打印：
left right count
0 a b 1
1 a c 2
2 b c 2
3 c d 1
4 a d 1
5 c e 1
6 a e 1
7 b e 1
8 c f 1
9 e f 1
10 a f 1
11 b f 1
12 b j 1
13 c j 1
我经常需要根据列中项目的共现生成网络图。我从这样的事情开始：
letters
0 [b, a, e, f, c]
1 [a, c, d]
2 [c, b, j]
在下面的例子中，我想要一个table所有字母对，然后有一个"weight"列，它描述了每两个字母有多少次字母对一起出现在同一行（例如见底部）。
我目前正在使用 for 循环来完成它的大部分工作，我想知道是否有办法对其进行矢量化，因为我经常处理大量的数据集，这些数据集需要很长时间才能处理这边走。我还担心将事情保持在内存限制内。这是我现在的代码：
import pandas as pd
# Make some data
df = pd.DataFrame({'letters': [['b','a','e','f','c'],['a','c','d'],['c','b','j']]})
# I make a list of sets, which contain pairs of all the elements
# that co-occur in the data in the same list
sets = []
for lst in df['letters']:
for i, a in enumerate(lst):
for b in lst[i:]:
if not a == b:
sets.append({a, b})
# Sets now looks like:
# [{'a', 'b'},
# {'b', 'e'},
# {'b', 'f'},...
# Dataframe with one column containing the sets
df = pd.DataFrame({'weight': sets})
# We count how many times each pair occurs together
df = df['weight'].value_counts().reset_index()
# Split the sets into two seperate columns
split = pd.DataFrame(df['index'].values.tolist()) \
.rename(columns = lambda x: f'Node{x+1}') \
.fillna('-')
# Merge the 'weight' column back onto the dataframe
df = pd.concat([df['weight'], split], axis = 1)
print(df.head)
# Output:
weight Node1 Node2
0 2 c b
1 2 a c
2 1 f e
3 1 d c
4 1 j b
备注：
如其他答案中所建议，使用 collections.Counter 进行计数。由于它的行为类似于 dict，因此它需要可散列的类型。 {a,b} 不可散列，因为它是一个集合。将其替换为元组可以修复可散列性问题，但会引入可能的重复项（例如 ('a', 'b') 和 ('b', 'a')）。要解决此问题，只需对元组进行排序。
因为 sorted returns 一个 list，我们需要把它转回一个元组：tuple(sorted((a,b)))。有点麻烦，但与 Counter.
快速简单的加速：理解而不是循环
重新排列后，您的嵌套循环可以替换为以下理解：
sets = [ sorted((a,b)) for lst in df['letters'] for i,a in enumerate(lst) for b in lst[i:] if not a == b ]
Python 对理解执行进行了优化，因此这已经带来了一些加速。
好处：如果将它与 Counter 结合使用，您甚至不需要将结果作为列表，而是可以使用 生成器表达式 （几乎不需要使用额外的内存而不是存储所有对）：
Counter( tuple(sorted((a, b))) for lst in lists for i,a in enumerate(lst) for b in lst[i:] if not a == b ) # note the lack of [ ] around the comprehension
评估：什么是更快的方法？
像往常一样，在处理性能时，最终的答案必须来自测试不同的方法并选择最佳的方法。
在这里，我比较了@yatu 的（IMO 非常优雅和可读）基于 itertools 的方法，原始的嵌套 for 和理解。
所有测试 运行 都是在相同的样本数据上随机生成的，看起来像给定的例子。
from timeit import timeit
setup = '''
import numpy as np
import random
from collections import Counter
from itertools import combinations, chain
random.seed(42)
np.random.seed(42)
DF_SIZE = 50000 # make it big
MAX_LEN = 6
list_lengths = np.random.randint(1, 7, DF_SIZE)
letters = 'abcdefghijklmnopqrstuvwxyz'
lists = [ random.sample(letters, ln) for ln in list_lengths ] # roughly equivalent to df.letters.tolist()
'''
#################
comprehension = '''Counter( tuple(sorted((a, b))) for lst in lists for i,a in enumerate(lst) for b in lst[i:] if not a == b )'''
itertools = '''Counter(chain.from_iterable(combinations(sorted(i), r=2) for i in lists))'''
original_for_loop = '''
sets = []
for lst in lists:
for i, a in enumerate(lst):
for b in lst[i:]:
if not a == b:
sets.append(tuple(sorted((a, b))))
Counter(sets)
'''
print(f'Comprehension: {timeit(setup=setup, stmt=comprehension, number=10)}')
print(f'itertools: {timeit(setup=setup, stmt=itertools, number=10)}')
print(f'nested for: {timeit(setup=setup, stmt=original_for_loop, number=10)}')
运行 上面的代码在我的机器上 (python 3.7) 打印：
Comprehension: 1.6664735930098686
itertools: 0.5829475829959847
nested for: 1.751666523006861
因此，两种建议的方法都比嵌套 for 循环有所改进，但 itertools 在这种情况下确实更快。
为了提高性能，您可以使用 itertooos.combinations 从内部列表中获取所有长度的 2 组合，并使用 Counter 计算展平列表中的对。
请注意，除了从每个子列表中获取所有组合之外，排序是必要的步骤，因为它将确保所有的元组对以相同的顺序出现：
from itertools import combinations, chain
from collections import Counter
l = df.letters.tolist()
t = chain.from_iterable(combinations(sorted(i), r=2) for i in l)
print(Counter(t))
Counter({('a', 'b'): 1,
('a', 'c'): 2,
('a', 'e'): 1,
('a', 'f'): 1,
('b', 'c'): 2,
('b', 'e'): 1,
('b', 'f'): 1,
('c', 'e'): 1,
('c', 'f'): 1,
('e', 'f'): 1,
('a', 'd'): 1,
('c', 'd'): 1,
('b', 'j'): 1,
('c', 'j'): 1})
使用稀疏关联矩阵的 numpy/scipy 解决方案：
from itertools import chain
import numpy as np
from scipy import sparse
from simple_benchmark import BenchmarkBuilder, MultiArgument
B = BenchmarkBuilder()
@B.add_function()
def pp(L):
SZS = np.fromiter(chain((0,),map(len,L)),int,len(L)+1).cumsum()
unq,idx = np.unique(np.concatenate(L),return_inverse=True)
S = sparse.csr_matrix((np.ones(idx.size,int),idx,SZS),(len(L),len(unq)))
SS = (S.T@S).tocoo()
idx = (SS.col>SS.row).nonzero()
return unq[SS.row[idx]],unq[SS.col[idx]],SS.data[idx] # left, right, count
from collections import Counter
from itertools import combinations
@B.add_function()
def yatu(L):
return Counter(chain.from_iterable(combinations(sorted(i),r=2) for i in L))
@B.add_function()
def feature_engineer(L):
Counter((min(nodes), max(nodes))
for row in L for nodes in combinations(row, 2))
from string import ascii_lowercase as ltrs
ltrs = np.array([*ltrs])
@B.add_arguments('array size')
def argument_provider():
for exp in range(4, 30):
n = int(1.4**exp)
L = [ltrs[np.maximum(0,np.random.randint(-2,2,26)).astype(bool).tolist()] for _ in range(n)]
yield n,L
r = B.run()
r.plot()
我们看到此处介绍的方法 (pp) 具有典型的 numpy 常量开销，但从大约 100 个子列表开始它开始获胜。
OP 示例：
import pandas as pd
df = pd.DataFrame({'letters': [['b','a','e','f','c'],['a','c','d'],['c','b','j']]})
pd.DataFrame(dict(zip(["left", "right", "count"],pp(df['letters']))))
打印：
left right count
0 a b 1
1 a c 2
2 b c 2
3 c d 1
4 a d 1
5 c e 1
6 a e 1
7 b e 1
8 c f 1
9 e f 1
10 a f 1
11 b f 1
12 b j 1
13 c j 1