Python:DIY将这个“all_subsets”函数推广到任何大小的子集

2024-03-28 14:26:12 发布

您现在位置:Python中文网/ 问答频道 /正文

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

subsets的长度由参数i给出。我需要将这个函数推广到任何i对于i1或2的情况是微不足道的,并且可以看到一般的模式:长度为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嵌套循环。任何提示或完整答案都将被视为非常棒的。在


Tags: 数据函数in列表forreturnif规则
3条回答

那你就不是在做先验的。在

在Apriori中,除了k=1之外,您从不枚举k大小的所有子集。在

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

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

这里有一个例子。假设发现以下项集频繁出现:

 ABCD
 ABCF
 ABEF
 ABDF
 ACDF
 BCDF

那么apriori将只构造一个候选(根据前缀规则!)公司名称:

^{pr2}$

然后它将检查其他子集是否也被发现是频繁的,即

 BCDF
 ACDF
 ABDF

因为所有这些都在上一轮中,所以这个候选者存活下来,并将在下一次对数据集的线性扫描中进行测试。在

Apriori是关于而不是必须检查k大小的所有子集,而只是那些有机会频繁的子集,前提是已知以前的知识。在

您在注释中提到代码here对您是不透明的。但这可能是实现您所要实现的combinations函数的最佳方法,而且它值得理解,所以我将尝试详细解释它。在

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

我们的第一个组合是这样的。。。在

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

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

^{pr2}$

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

我们继续向前移动第二个插入符号,将第一个插入符号保持在适当的位置,直到第二个插入符号到达末尾。然后我们将第一个插入符号移动到索引1,并通过将第二个插入符号移回索引2来“重置”进程。在

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

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

现在我们必须通过操纵索引列表来找出如何做到这一点。事实证明这很简单。最终组合如下:

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

它的索引表示是[3, 4]。这些是索引的最大可能值,并且等于i + n - r,其中i是列表中的位置,n是值的数目(在本例中是5),而{}是选择数(在本例中是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构造;只有当for循环正常终止时,else块才会执行。)

    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)

这种方法有几种变体;在另一种方法中,不是向后遍历索引,而是向前一步,递增第一个索引,该索引与下一个索引之间存在“差距”,然后重置较低的索引。在

最后,您可以递归地定义它,尽管从实用的角度来看,递归定义可能没有那么有效。在

您可以使用^{},而不是推出自己的。在

相关问题 更多 >