python - 元组是另一个元组的子集 - Apriori 算法

Question

我正在尝试实现先验算法。在最后步骤之一中，我从产品列表生成了两个元组数组。

>>> arr1 = array([(2421,), (35682,), (30690,), ..., (18622,), (18285,), (31269,)],
  dtype=object)

>>> arr2 = array([(2421, 35682), (2421, 30690), (2421, 24852), ..., (18622, 18285),
   (18622, 31269), (18285, 31269)], dtype=object))

我的想法是，我需要检查哪些 arr1 是 arr2 的子元组，即 (2421, ) 是 (2421, ) 的子元组 (2421, 30690)。

我试过了

>>> if (2421,) in (2421, 1231):
...    print('Yes')
... else:
...    print('No')

我得到否。我也尝试使用 .issubset 但我得到 AtributeError。

我想知道如何在不采用硬核方式的情况下做到这一点，

>>> print(len(arr1), len(arr2))
(9258, 263616)

我正在使用带有 Python 2 的 Jupyter 笔记本。仅使用 numpy、pandas 和 itertools。

所需的输出应采用以下形式；如果我有产品 1,2,3 但我只考虑元组 (1,) 和 (2,) 那么我需要 (1,2)，但不是所有 2 种产品组合中的 (1,3)。

Answer 1

如果您正在实现 Apriori 算法，您希望使用实际集而不是元组。 Python 有两种集合类型，set and frozenset ，其中后者是不可变的，因此可以存储在字典或其他集合中。您可能希望使用后者，以便可以将此类集合与支持分数相关联。

这当然是 apyori project implementation 所采用的方法。用途； apyory 是 Apriori 算法的纯 Python 库。

您可以使用元组进行子集测试，但对于大小为 N 和 M 的元组来说，这是一个缓慢的 O(NM) 操作:

def tuple_is_subset(ta, tb):
    return all(tav in tb for tav in ta)

这是对 ta 中 N 个项目的完整循环，并且每个 tav in tb 测试需要 M = len(tb) 步骤。

您可以将元组转换为集合，但这也需要 O(N) + O(M) 时间，之后子集测试需要 O(N) 时间。这使得整个过程需要线性时间，但对于小元组，我怀疑创建新对象的恒定成本将超过上面理论上成本更高的 O(NM) all() 测试。

要使用集合，您可以使用:

set(ta).issubset(tb)

其中 set.issubset() 接受任何非 set 可迭代对象，代码会为测试创建一个临时 set 对象。