为一个小的数据关联规则矿实现一个玩具Apriori algorithm,我需要一个函数来返回所有子集。在
subsets的长度由参数i
给出。我需要将这个函数推广到任何i
。对于i
1或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
嵌套循环。任何提示或完整答案都将被视为非常棒的。在
那你就不是在做先验的。在
在Apriori中,除了k=1之外,您从不枚举k大小的所有子集。在
在任何更大的尺寸中,您都可以根据
Apriori-Gen
构造组合。在这样效率更高,实际上至少和手动构建所有组合一样简单。在
这里有一个例子。假设发现以下项集频繁出现:
那么apriori将只构造一个候选(根据前缀规则!)公司名称:
^{pr2}$然后它将检查其他子集是否也被发现是频繁的,即
因为所有这些都在上一轮中,所以这个候选者存活下来,并将在下一次对数据集的线性扫描中进行测试。在
Apriori是关于而不是必须检查k大小的所有子集,而只是那些有机会频繁的子集,前提是已知以前的知识。在
您在注释中提到代码here对您是不透明的。但这可能是实现您所要实现的
combinations
函数的最佳方法,而且它值得理解,所以我将尝试详细解释它。在其基本思想是,给定一个序列和多个可供选择的项,我们可以将每个组合表示为给定序列中的一系列索引。例如,假设我们有一个列表
['a', 'b', 'c', 'd', 'e']
,我们希望从该列表生成两个值的所有组合。在我们的第一个组合是这样的。。。在
…并由索引列表
^{pr2}$[0, 1]
表示。我们的下一个组合如下:并由索引列表
[0, 2]
表示。在我们继续向前移动第二个插入符号,将第一个插入符号保持在适当的位置,直到第二个插入符号到达末尾。然后我们将第一个插入符号移动到索引
1
,并通过将第二个插入符号移回索引2
来“重置”进程。在然后我们重复这个过程,向前移动第二个插入符号直到它到达结尾,然后将第一个向前移动一个并重置第二个。在
现在我们必须通过操纵索引列表来找出如何做到这一点。事实证明这很简单。最终组合如下:
它的索引表示是}是选择数(在本例中是
[3, 4]
。这些是索引的最大可能值,并且等于i + n - r
,其中i
是列表中的位置,n
是值的数目(在本例中是5
),而{2
)。因此,一旦某个特定的指数达到这个值,它就不能再高了,而且需要“重置”。在考虑到这一点,下面是对代码的一步一步的分析:
首先,给定基于上述示例的输入,
pool
将是我们上面转换成元组的字符列表,n
只是池中的项数。在在没有替换的情况下,我们不能从
n
项列表中选择超过n
个项目,因此在这种情况下我们只返回。在现在我们有了索引,初始化为第一个组合(
[0, 1]
)。所以我们放弃它:然后我们使用无限循环生成剩余的组合。在
在循环中,我们首先向后遍历索引列表,搜索尚未达到最大值的索引。我们使用上面描述的公式(
i + n - r
)来确定给定索引的最大值。如果我们发现一个索引没有达到它的最大值,那么我们就跳出循环。在如果我们找不到一个,那就意味着所有的索引都达到了它们的最大值,所以我们就完成了迭代。(这使用鲜为人知的
for-else
构造;只有当for
循环正常终止时,else
块才会执行。)现在我们知道索引
i
需要递增:另外,
i
之后的索引都处于最大值,因此需要重置。在现在我们有了下一组指数,所以我们得出另一个组合。在
这种方法有几种变体;在另一种方法中,不是向后遍历索引,而是向前一步,递增第一个索引,该索引与下一个索引之间存在“差距”,然后重置较低的索引。在
最后,您可以递归地定义它,尽管从实用的角度来看,递归定义可能没有那么有效。在
您可以使用^{} ,而不是推出自己的。在
相关问题 更多 >
编程相关推荐