7

问题：

我有数百万笔交易的清单。每个事务都包含项目（例如“胡萝卜”、“苹果”），目标是生成在单个事务中经常一起出现的一对项目的列表。据我所知，进行详尽的搜索是不可行的。

解决方案尝试：

到目前为止，我有两个想法。1）随机抽取一些适当的交易部分，只检查那些或 2）计算每个元素出现的频率，使用该数据计算元素应该偶然出现的频率，并使用它来修改从 1 开始的估计。

非常感谢任何提示、替代方法、现成的解决方案或一般的阅读建议。

编辑：

评论中的一些附加信息

不同项目的数量：1,000 到 100,000

内存限制：最多几个小时的几场公羊。

使用频率：或多或少一次。

可用资源：20-100 小时的新手程序员时间。

所需的结果列表格式：一对项目和一些衡量它们出现的频率，对于 n 个最频繁的对。

每笔交易的物品分配：目前未知。

4

2 回答 2

7

设事务n数为，项目数为，事务k的平均大小为d。

天真的方法（检查所有记录中的对）将为您提供O(k^2 * n * d)解决方案，但确实不是非常理想。但是我们可以将其改进为O(k*n*d)，并且如果我们假设项目的均匀分布（即每个项目平均重复O(n*d/k)次数） - 我们可能能够将其改进为O(d^2 * n + k^2)（这要好得多，因为很可能是d << k）。

这可以通过构建交易的倒排索引来完成，这意味着 - 创建从项目到包含它们的交易的映射（创建索引是O(nd + k)）。

例如，如果您有交易

transaction1 = ('apple','grape')
transaction2 = ('apple','banana','mango')
transaction3 = ('grape','mango')

倒排索引将是：

'apple' -> [1,2]
'grape' -> [1,3]
'banana' -> [2]
'mango' -> [2,3]

因此，在了解什么是倒排索引之后 -以下是解决方案的指南：

  1. 为您的数据构建倒排索引
  2. 对于每个项目 x，迭代它出现的所有文档，并为所有与共同出现的对构建直方图。(x,y)yx
  3. 完成后，您将获得一个包含 k^2 个项目的直方图，您需要对其进行处理。这个问题讨论了如何从未排序的列表中获取前 k 个元素。

复杂性分析：

  1. 建立倒排索引是O(nd+k)
  2. 假设每个元素在O(nd/k)事务中重复，每次迭代都需要O(nd/k * d)时间，而且你k在这一步有迭代，所以你得到O(nd^2 + k)了这一步。
  3. 如果您想要完全排序，或者如果您只想打印前 X 个元素，可以在 O(k^2logk) 中完成处理列表，它可以在O(k^2).

总计O(nd^2 + k^2)解决方案以获得 top-X 元素，这比天真的方法要好得多，假设d << k.

此外，请注意，如果需要，可以在线程之间有效地并行化和分布瓶颈（步骤 2）。

于 2013-01-04T16:13:25.610 回答
0

如果一次购买中订购的商品数量很少（<10），请执行以下操作：
拥有地图地图（字典词典）：第一个地图中的键是项目，
第一个地图中的值是地图，其键是第二个项目，值用第一个键计算它在购买中出现的次数。

因此，请检查每个订单和每对更新地图。最后通过地图地图并在“第二值”中寻找“大值”

注意：根据输入数据的大小和“分布”，您可能最终没有足够的内存

于 2013-01-04T16:36:05.277 回答