元组是另一个元组的子集 - 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, 30690) 的子元组。

我试过了

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

我得到 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() 接受任何非集合的可迭代对象，代码会为测试创建一个临时集合对象。

Answer 2

欢迎2pac,

初始化

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

所以如果你想问 (2421,) 它是 arr2 的子集吗仅当 arr2 包含大小为 1 的元组并包含值 2421 时，才会 return True 。

因为这不是您预期的行为，您必须遍历 arr1 的每个 i 项并检查是否所有 i[j] 项都是 arr2[k][= 的一部分25=]

快速概览

>>> arr1[0]
array([2421], dtype=object)
>>> arr1[0] in arr2
True
>>> arr1[0] in arr2[0]
True

这可以给这个功能

def is_a_subset( tuple_i, primary_tuple ):
  return all( k in primary_tuple for k in tuple_i)

for tuple_i in arr1:
  is_a_subset( tuple_i , arr2)

但是我会建议使用 set 如果你一步一步地构建你的集合 frozenset 如果它是一个不可变的集合（即 set and frozenset）

编辑：同理回答

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

Tuple is subset of another tuple - Apriori algortihm

python

tuples

subset

apriori

jupyter-notebook