在一个集合列表中，找出一个集合在其他集合中出现的次数

Question

我试图解决的问题是找到交易数据中每个项集的支持度。

例如，

transactions = [
    'b c d',
    'a g' ,
    'a c d e',
    'e f h',
    'a b c g h',
    'd' , 
    'a e g h',
    'b c d',
    'a b f g h',
    'a c d g',
]

将会有 [2, 5, 1, 1, 1, 5, 1, 2, 1, 1]

所以基本上对于第二次交易a，g，它是其他交易的子集，如'a g'、'a b c g h'、'a e g h'、'a b f g h'、'a c d g'，因此计数为5。

现在，最初，我正在使用mlxtend事务编码器将此数据集转换为一种热编码事务。 并使用类似于以下内容：

df.progress_apply(lambda x: (df.iloc[:, np.where(x==1)[0]].sum(1)==len(np.where(x==1)[0])).sum(), axis=1)

获取这些值的方法。

这个想法就像是使用当前行元素切片矩阵/数据框，然后沿着行求和。当它与当前行元素长度相同时，就是子集，因此要计算它。

然而，对于较小的数据集，这种方法效果良好，但当我遇到kosarak时，由于OOM错误，我无法使用密集表示。所以，我切换回countVectorizer并生成稀疏表示，然后使用类似于之前的逻辑。

现在的问题是，使用scipy sparse进行sum操作比dense慢4倍，运行时间为

164 ms ± 22.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

即使使用集合来解决问题，也没有什么改进。

目前我的做法是 O(n2) 的时间复杂度。是否有更好的算法/包能加速处理？

非常感谢任何帮助。

- lu5er

---

这个时间是为了例子而设定的吗？ - Dani Mesejo

所以我查看了kosarak数据集，我有一个问题： 每行交易的顺序是否重要？（例如，3、5等同于5、3）。从您使用集合的方式来看，我会说“不是”，但我不能确定。 - Shamis

还有一个问题 - 有些行会重复。对于重复的行应该采取什么方法？（忽略它们是完全可能的，我不确定是否值得额外比较来缓存/删除结果。） - Shamis

你能尝试一下分治法吗？按长度排序，计算重复项，仅检查较长的字符串，记忆结果（我的意思是，如果l9是l11的子集，则如果l5是l9的子集，则它也是l11的子集）。 - gboffi

Answer 1

你可以使用Numba来加速对密集数组的计算。从one-hot编码开始。

transactions = list(map(str.split, transactions))
# First compute indices for each element of transactions
indices = dict(item[::-1] for item in enumerate(set(x for t in transactions for x in t)))
# Make the matrix len(transactions)-by-len(indices)
A = np.zeros((len(transactions), len(indices)), bool)
# Fill in the matrix
for r, item in enumerate(transactions):
    A[r, [indices[t] for t in item]] = True

现在你可以通过A点乘A.T的每一行，对其进行阈值处理，并求出通过的元素之和：

@numba.njit
def check_subsets(A):
    output = np.empty(len(A), dtype=np.int_)
    for r, row in enumerate(A):
        output[r] = np.sum((A * row).sum(1) >= row.sum())
    return output

>>> check_subsets(A)
array([2, 5, 1, 1, 1, 5, 1, 2, 1, 1])

这确实可以加快您的原始数据集的处理速度：

%timeit check_subsets(A)
5.2 µs ± 343 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
%timeit (np.matmul(A, A.T, dtype=int) >= A.sum(1, keepdims=True)).sum(1)
7.86 µs ± 39 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

这种改进对于大型数据集并不适用，但内存占用更少。

np.random.seed(42)
B = np.random.randint(2, size=(10000, 26), dtype=bool)
%timeit check_subsets(B)
4.48 s ± 62.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit (np.matmul(B, B.T, dtype=int) >= B.sum(1, keepdims=True)).sum(1)
2.31 s ± 96.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

这两个基准测试是在numba的JIT编译器的初始编译阶段之后运行的。请注意，没有缓冲区的朴素实现比所示的实现慢约5%。

- Mad Physicist

Answer 2

由于2的26次方远低于32位整数的整数限制，您可以这样做：

digitize = lambda x: np.in1d(list(string.ascii_lowercase), x.split()) @ 2 ** np.arange(26)

digitize函数将每组字母转换为一个唯一的位整数。由于数据是按位比较的，因此可以使用位运算进行比较。

trans = np.array([digitize(t) for t in transactions])

Out[]: array([ 14,  65,  29, 176, 199,   8, 209,  14, 227,  77], dtype=int32)

(np.bitwise_and.outer(tr, tr) == tr).sum(0)  #bitwise definition of subset, summed over entries

Out[]: array([2, 5, 1, 1, 1, 5, 1, 2, 1, 1])

你可以轻松地创建一个trans列，然后应用位函数以获得所需的输出。这样做可以通过不存储那些大型onehots来减少内存使用。

- Daniel F

---

facepalm 问题出在 np.bitwise_and.outer(tr, tr) 会导致结果非常大。不过，我还是先放着吧。 - Daniel F

Answer 3

如果可能的话，Python的集合运算通常相当不错，不涉及任何复杂的二进制逻辑，这显然更难阅读/理解。

建议基础上构建：

transactions = [
    'b c d',
    'a g' ,
    'a c d e',
    'e f h',
    'a b c g h',
    'd', 
    'a e g h',
    'b c d',
    'a b f g h',
    'a c d g',
]
transactions = list(map(lambda x: x.replace(' ', ''), transactions))
print(transactions) # ['bcd', 'ag', 'acde', 'efh', 'abcgh', 'd', 'aegh', 'bcd', 'abfgh', 'acdg']

transactions_set = list(map(set, transactions))
counts = [sum(set(elem).issubset(s) for s in transactions_set) for elem in transactions]
print(counts) # [2, 5, 1, 1, 1, 5, 1, 2, 1, 1]

- Stefan B

Answer 4

我的小尝试

如果你当前的方法每个循环大约需要164毫秒，那么这个方法可以提高8倍的效率。不幸的是，我不能声称自己有什么天才想法，而且我担心这个方法还是太慢了。我只是预先构建了所有的集合，然后以最直接的方式运行，使用issubset函数，就像@solid.py一样。在构建集合之前和使用for循环而不是函数调用的区别是6倍。

目前检查一个集合所需的时间为~22ms +-2ms或类似的时间。我一直在kosarak数据集上进行测试，所以我希望只有一个名为kosarak的数据集。

我尝试了一些更“聪明”的方法来消除不可能的选项，但不幸的是，它们都比这个“愚蠢”和直接的方法更慢。

以下是几种可能真正有用的方法：

• 按大小排序集合，然后仅使用长度>=的匹配项。长度检查是.issubset中的第一个检查。由于前30,000个集合只有一次交易，另外35,000个集合包含两次交易，这可能意味着可以减少计算量约30％。也许更多，因为少数交易集可以缓存以进一步提高性能。

• 这导致结果的缓存-至少是短期的。创建1：{2：{}}结构相当便宜，它允许您重复使用结果。即使在未排序的值上使用它，性能也会增加〜1.5ms左右。虽然不多，但通过排序可能会更多。当集合变得更大（因此具有缓存结果的概率变得更小）时，也可以切断此缓存。
  通常有几个交易重复了几百甚至几千次。这将有助于削减它们，从而进一步减少O（n ^ 2）中的n。不幸的是，我没有任何东西可以单独降低复杂度。

• 扩展缓存-事先对集合进行排序和计数也可用于将每个集合替换为元组（集合，计数）。这将消除对缓存的需求，并消除大部分不必要的计算。

   import csv
   import time
  
   reader = csv.reader(open('kosarak.csv'), delimiter=' ')
   dataLines = []
   for line in reader:
       dataLines.append(set(map(int, line)))
  
   results = []
   count = 0
   totalTime = 0
   for line1 in dataLines:
       r1 = 0
       t1 = time.time_ns()
       for line2 in dataLines:
           if line1.issubset(line2):
               r1 += 1
  
       t2 = time.time_ns()
       results.append(r1)
       totalTime += (t2 - t1) / 1000000
       count += 1
       if (count % 100) == 0:
           print("$$$$$$$$$$$$$")
           print(totalTime)
           print(totalTime / count)
           print(count)
  

- Shamis