基于Apriori算法生成候选项集

Question

我正在尝试实现Apriori算法。为此，我需要从长度为k的项目集(以字典L的形式给出)生成长度为k+1的项目集。在生成组合时必须遵循Apriori原则。该原则指出:长度为k+1的集合只能在其所有子集都出现在输入l中才能生成

我有一个字典，我需要从中生成项集。

我当前的尝试是:

import itertools as it
def generateItemsets(Lk,k):
comb = sum(Lk.keys(), tuple())
Ck = set(it.combinations(comb, k))
return Ck

但是这个函数永远运行并且在错误时中断:IOPub数据速率超过。

示例1:

Input (dictionary): {(150,): 2, (160,): 3, (170,): 3, (180,): 3}
Output (set): {(150, 160), (150, 170), (150, 180), (160, 170), (160, 180), (170, 180)}

更新1

数据集包含近16000个事务。它看起来像这样:

[![数据集][1]][1]

唯一项范围为0-999

正如你所看到的，这个函数将得到一个输入L_k，它应该输出C_k+1。输入的L_k是一个字典，例如({(301,350):46，(966,970):612，(310,350):216，(548,550):457})，而输出的C_k+1应该是一个集合(例如:{(250,350)，(360,370)，(380,390)，…}

Answer 1

我不确定你到底想要什么输入，因为不清楚你发布的列表是如何符合Apriori算法输入的定义的。
输入应该是一个交易列表，这些交易中的一个项目和一个数字，该数字表示在同一交易中与指定项目一起出现的某些项目的计数。
输出是已与指定商品一起售出所需次数的商品列表。有几个库可以解决这类问题。用户null已经指出了一个不错的:https://github.com/tommyod/Efficient-Apriori。还有Apyori: https://github.com/ymoch/apyori.
这是一个简单的解决Apriori算法的尝试。它可以复制到一个文件中，然后用Python执行:

# list of transactions
sales = [
('eggs', 'bacon', 'soup'),
('eggs', 'bacon', 'apple'),
('soup', 'bacon', 'banana'),
]
# generate match dictionary of type {item: {count: {item, ...}, ...}, ...}
matches = {
i: { 
sum((i in z and j in z) for z in sales): set(
k for t in sales for k in t
if i!=k and
sum((i in z and j in z) for z in sales) == sum((i in z and k in z) for z in sales)
)
for t in sales for j in t if i in t and j!=i
}
for t in sales for i in t
}
#print ( "match counts: %sn" % (matches) )
print ( "best match(es) for eggs:", matches['eggs'][len(matches['eggs'])] )
# output: {'bacon'}
print ( "best match(es) for bacon:", matches['bacon'][len(matches['bacon'])] )
# output: {'eggs', 'soup'}
basket = ('soup', 'apple', 'banana') # consumer basket
# calculate a list of best matches for new sales
best = set(sum([ list(matches[i][len(matches[i])]) for i in basket ], [])) - set(basket)
print ( "basket: %s, best matches: %s" % ( basket, best ) )
# output: {'bacon', 'eggs'}

上面的代码生成一个项目字典，其中包含包含两个项目的事务中某些项目的特定计数列表。这个字典的生成对于庞大的交易列表来说可能很慢。但您不必为每个新交易计算这个。相反，我会每天时不时地重新计算比赛次数。
项目名称可以替换为项目索引来处理项目数据集。在这个例子中，字符串比数字更清晰。
一般来说，将慢函数转换为数据集的嵌套字典是一个提高代码速度的好主意。类型为:

的慢函数

result = function ( parameter, parameter, ... )

可以转换为一个嵌套字典和一个在较长时间后重新计算字典的函数:

if time < refresh:
dictionary = precalc ( )
refresh = time + rate
...
result = dictionary [ parameter ] [ parameter ] [ ... ]

这个解决方案当然需要更多内存。

为了得到可靠的答案，你不应该否定帖子，而是提供一个更大的代码块，可以复制到一个文件并执行。您还应该为函数提供清晰的输入值。Lk和k是什么?根据你的问题，我假设以下程序不输出你发布的错误:

import itertools as it
def generateItemsets(Lk,k):
comb = sum(Lk.keys(), tuple())
Ck = set(it.combinations(comb, k))
return Ck
# input of apriori algorithm should be a list of transactions, wtf is this ?!
Lk = {(150,): 2, (160,): 3, (170,): 3, (180,): 3}
missing_input_value = 1234567890
print ( generateItemsets ( Lk, missing_input_value ) )
# output: set()
for i in range(0,999999):
generateItemsets ( Lk, i )   # does not error out

所以你要么搞砸了你的Python版本，要么我误解了你的问题，要么你提供的输入没有涵盖你的程序的错误情况。
我建议你用更大的代码更新你的问题，而不仅仅是三行没有任何工作输入的函数。
当您使用Jupyter笔记本时，您得到的错误可能与您的输出数据速率有关。尝试执行jupyter notebook --NotebookApp.iopub_data_rate_limit=1.0e10如何解决"ipub数据速率超过"的问题?在Jupyter Notebook
或本视频:https://www.youtube.com/watch?v=B_YlLf6fa5A