python - 基于Apriori算法生成候选项集

Question

我正在尝试实现 Apriori 算法。为此，我需要从长度为 k 的项集(作为字典 L 给出)生成长度为 k+1 的项集。在生成组合时必须遵循 Apriori 原则。原理说明:只有当输入 L 中存在其所有子集时，才能生成长度为 k+1 的集合。
我有一本字典，我需要从中生成项目集。
我目前的尝试是这样的:

import itertools as it
def generateItemsets(Lk,k):

    comb = sum(Lk.keys(), tuple())
    Ck = set(it.combinations(comb, k))
    return Ck

但是该功能需要永远并且会因错误而中断:IOPub data rate exceeded。
示例 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: %s\n" % (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在控制台中，来自这篇文章:How to solve "IOPub data rate exceeded." in Jupyter Notebook
或此视频:https://www.youtube.com/watch?v=B_YlLf6fa5A