用于查找在大数据集中经常出现的元素的启发式算法

Question

问题:

我有数百万笔交易的清单.每个交易都包含项目(例如"胡萝卜","苹果"),目标是生成在个别交易中经常出现的一对项目列表.据我所知,进行详尽的搜索是不可行的.

解决方案尝试

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

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

编辑:

评论中的一些其他信息

不同项目数量:1,000到100,000

记忆约束:最多只有几个小时的公羊.

使用频率:或多或少一次性使用.

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

期望的结果列表格式:对于n个最频繁的对,项目对和一些测量它们出现的频率.

每笔交易的物品分配:截至目前未知.

Answer 1

让交易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)这样y共同occures用x.
3. 完成后,您有一个包含k ^ 2项的直方图,您需要处理这些项目.这个问题讨论了如何从未排序的列表中获取top-k元素.

复杂性分析:

1. 构建倒排索引是 O(nd+k)
2. 假设每个元素在O(nd/k)事务中重复,每次迭代都需要O(nd/k * d)时间,并且您k在此步骤中进行了迭代,因此您可以O(nd^2 + k)执行此步骤.
3. 如果您想要完整排序,可以在O(k ^ 2logk)中完成列表的处理,或者如果您只想打印前X个元素,则可以在其中完成O(k^2).

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

另外,请注意,如果需要,瓶颈(步骤2)可以有效地并行化并在线程之间分配.