1

为小数据关联规则矿实现一个玩具Apriori 算法，我需要一个函数来返回所有子集。

子集的长度由参数给出i。我需要为任何i. 1 或 2的情况i是微不足道的，可以看到一般模式：一个长度的元组列表，i其中强加了顺序以防止重复。

def all_subsets(di,i):
        if i == 1:
                return di
        elif i == 2:
                return [(d1,d2) for d1 in di for d2 in di if d1 < d2]
        else:
                return [ ... ]

如何i以简洁的方式概括这种嵌套循环模式，比如使用列表推导、生成器或一些“函数式编程”概念？

我在考虑某种函数列表，但我真的不知道如何概括i嵌套循环。任何提示或完整答案都将被视为真棒。

4

4 回答 4

4

您可以使用itertools.combinations().

于 2013-03-02T13:09:11.517 回答
1

那么你不是在做 Apriori。

在 Apriori 中，您永远不会枚举大小为 k 的所有子集，除了 k=1。

在任何更大的尺寸中，您都可以根据构建Apriori-Gen组合。

这样效率更高，实际上至少与手动构建所有组合一样简单。

这是一个例子。假设以下项集被发现频繁：

 ABCD
 ABCF
 ABEF
 ABDF
 ACDF
 BCDF

然后 apriori 将只构造一个候选者（通过前缀规则！）：

 ABC + D   - ABC + D + F
 ABC + F   /

然后它会接下来检查其他子集是否也发现频繁，即

 BCDF
 ACDF
 ABDF

由于所有这些都在上一轮中，因此该候选者幸存下来，并将在数据集的下一次线性扫描中进行测试。

Apriori 就是不必检查所有大小为 k 的子集，而只检查那些有机会频繁出现的子集，给定先前的知识。

于 2013-03-02T14:59:50.223 回答
1

您在评论中提到这里的代码对您来说是不透明的。但这可能是实现combinations您所针对的功能的最佳方式，并且值得理解，因此我将尝试详细解释它。

基本思想是给定一个序列和许多可供选择的项目，我们可以将每个组合表示为给定序列的索引序列。例如，假设我们有一个 list ['a', 'b', 'c', 'd', 'e']，我们想从该列表中生成两个值的所有组合。

我们的第一个组合看起来像这样......

['a', 'b', 'c', 'd', 'e']
  ^    ^

...并由索引列表表示[0, 1]。我们的下一个组合如下所示：

['a', 'b', 'c', 'd', 'e']
  ^         ^

并由索引列表表示[0, 2]。

我们继续向前移动第二个插入符号，将第一个插入符号保持在原位，直到第二个插入符号到达末尾。然后我们将第一个插入符号移回 index1并通过将第二个插入符号移回 index 来“重置”该过程2。

['a', 'b', 'c', 'd', 'e']
       ^    ^

然后我们重复这个过程，将第二个插入符号向前移动直到它到达末尾，然后将第一个插入符号向前移动一个并重置第二个。

现在我们必须弄清楚如何通过操纵索引列表来做到这一点。事实证明，这很简单。最终组合将如下所示：

['a', 'b', 'c', 'd', 'e']
                 ^    ^

并且它的索引表示将是[3, 4]。这些是索引的最大可能值，等于i + n - r，其中i是列表中的位置，n是值的数量（5在这种情况下），并且r是选择的数量（2在这种情况下）。因此，一旦特定索引达到此值，它就不能再高了，需要“重置”。

因此，考虑到这一点，下面是对代码的逐步分析：

def combinations(iterable, r):
    pool = tuple(iterable)
    n = len(pool)

首先，给定基于上述示例的输入，pool将是我们上面转换为元组的字符列表，并且n只是池中的项目数。

if r > n:
    return

我们不能在不替换的情况下n从项目列表中选择多个项目，因此在这种情况下我们只需返回。n

indices = range(r)

现在我们有了索引，初始化为第一个组合 ( [0, 1])。所以我们产生它：

yield tuple(pool[i] for i in indices)

然后我们使用无限循环生成剩余的组合。

while True:

在循环内部，我们首先在索引列表中向后退一步，搜索尚未达到最大值的索引。我们使用上述公式 ( i + n - r) 来确定给定索引的最大值。如果我们发现一个索引没有达到它的最大值，那么我们就跳出循环。

    for i in reversed(range(r)):
        if indices[i] != i + n - r:
            break

如果我们没有找到一个，那么这意味着所有的索引都在它们的最大值，所以我们完成了迭代。（这使用了鲜为人知的for-else结构；仅当循环正常终止else时才执行该块。）for

    else:
        return

所以现在我们知道索引i需要增加：

    indices[i] += 1

另外，后面的索引i都是最大值，所以需要重新设置。

    for j in range(i+1, r):
        indices[j] = indices[j-1] + 1

现在我们有了下一组索引，所以我们产生了另一个组合。

    yield tuple(pool[i] for i in indices)

这种方法有几种变体；在另一种情况下，您不是在索引中倒退，而是向前迈进，增加第一个与下一个索引之间有“间隙”的索引，并重置较低的索引。

最后，您也可以递归地定义它，尽管从实用上讲，递归定义可能不会那么有效。

于 2013-03-02T15:00:10.497 回答
0

好的，这是我自己推出的版本：

def all_subsets(source,size):
        index = len(source)
        index_sets = [()]
        for sz in xrange(size):
                next_list = []
                for s in index_sets:
                        si = s[len(s)-1] if len(s) > 0 else -1
                        next_list += [s+(i,) for i in xrange(si+1,index)]
                index_sets = next_list
        subsets = []
        for index_set in index_sets:
                rev = [source[i] for i in index_set]
                subsets.append(rev)
        return subsets

产量：

>>> Apriori.all_subsets(['c','r','i','s'],2)
[['c', 'r'], ['c', 'i'], ['c', 's'], ['r', 'i'], ['r', 's'], ['i', 's']]
于 2013-03-02T14:44:06.083 回答