查找集合是集合列表中的子集的次数

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)

获取值。

这个想法就像用当前行的元素对矩阵/df 进行切片，然后跨行求和。它与当前行的元素长度相同的情况是一个子集，因此对其进行计数。

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

现在的问题是，在对稀疏进行求和时，scipy 稀疏比在运行时间为密集时慢 4 倍

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

即使使用集合来解决问题也没有太大改善。

到目前为止，这是我的方法，我相信它具有 O(n2) 复杂度。有没有更好的算法/包来加快速度。

任何帮助表示赞赏。提前致谢。

Answer 1

由于 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，然后应用按位函数来获得所需的输出。应该通过不存储那些大的 onehot 来减少内存使用。