1

我已经实现了用于挖掘频繁项集的 apriori 算法，它对样本数据的工作正常，但是当我尝试为http://fimi.ua.ac.be/data/retail.dat提供的零售数据集执行它时，它大约是 3mb 数据88k 笔交易和 1600 件独特物品大约需要 29 小时。我搜索了性能下降的原因，发现生成候选项目集的算法需要很多时间。任何人都可以帮助我如何提高性能，或者这些是正常的算法行为。

4

3 回答 3

2

您正在使用什么算法，您的阈值是多少？

如果您有n满足最低支持的 1 项集，则 Apriori（和许多其他人）必须考虑n*(n-1)/22 项集。这当然会变得相当昂贵。在 Apriori 中，2 项集通常是最大和最昂贵的步骤（取决于您的设置，3 项集可能更糟，但通常您不会走那么远……）

根据您的数据特征，Eclat 的性能可能会更好，也可能更差。FP-growth 非常聪明，但似乎很难正确有效地实施。

还存在无数种变体，其中一些是概率性的，并且可能更快。

但本质上实现和数据集/参数设置很重要。在同一组数据上，一种方法可能优于另一种方法；并且实现可能很容易产生 10 倍的性能差异。尤其是对于 APRIORI，许多人并不完全了解所使用的修剪技巧，最终会做太多的工作。

对于您的示例数据集（不幸的是，如果没有解释数字的字典，这完全没有帮助），我的 APRIORI 在 minSupport=1000 的低端 Atom CPU 上大约 1 分钟内完成。找到的 4 个项目集是：

32, 38, 39, 48: 1236
32, 39, 41, 48: 1646
36, 38, 39, 48: 1080
38, 39, 41, 48: 1991
38, 39, 48, 110: 1031
38, 39, 48, 170: 1193

但如前所述，参数对 APRIORI很重要。APRIORI 在事务的数量上可以很好地扩展（可能超过主内存），但它会受到大量候选者的影响，因此您需要将 minSupport 设置得足够高。

使用 minSupport=1000：

1-frequentItemsets (56)
2-frequentItemsets (49)
3-frequentItemsets (24)
4-frequentItemsets (6)
APRIORI runtime: 55401 ms

使用 minSupport=500：

1-frequentItemsets (185)
2-frequentItemsets (191)
3-frequentItemsets (79)
4-frequentItemsets (13)
5-frequentItemsets (0)
APRIORI runtime: 136594 ms

如您所见，运行时间增加了一倍多。原因是 1 项集增长了，产生了更多的 2 项集候选者。在 3 项和 4 项集上，差异不再那么大。但总的来说，在一个非常低端的 CPU 上运行 2 分钟还不错。

将最低支持降至 250：

1-frequentItemsets (587)
2-frequentItemsets (640)
3-frequentItemsets (273)
4-frequentItemsets (54)
5-frequentItemsets (4)
APRIORI runtime: 954984 ms

现在运行时开始爆炸。几乎 16 分钟找到 5 项集：

32, 38, 39, 41, 48: 448
36, 38, 39, 41, 48: 334
38, 39, 41, 48, 110: 346
38, 39, 41, 48, 170: 413

如您所见，38, 39, 41, 484 项集在该数据集中起着关键作用（但我们在第一次运行时已经发现了这一点）。我们现在还可以给出 的置信度38, 39, 41, 48 -> 32，这将是涉及 5 个项目的最置信规则：大约22.5%涉及前四个的交易也涉及项目32。但是考虑到 AFAICT 这个数据集的数字的含义是未知的，我们不知道这个规则在实践中是否真的很有趣，或者只是一个玩具练习。

转到 minSupport=100，运行时间进一步增长：

1-frequentItemsets (1857)
2-frequentItemsets (2785)
3-frequentItemsets (1475)
4-frequentItemsets (306)
5-frequentItemsets (28)
6-frequentItemsets (0)
APRIORI runtime: 8256507 ms

即两个多小时。大部分时间都花在了 2 个项目集上：有 170 万个候选者，其中 2785 个是频繁的。对于 3 项集，可以粗略估计只有几千个候选者，但不再是几百万个。我有一些计划，通过根据候选者的数量在两个代码路径之间切换来进一步改进实现。（'''Update:''' 通过更简单的修改，我进一步将运行时间减少了 20 倍。所以，'''实现很重要'''，它可以轻松地将 100 到 1000 倍或更多 -例如，当 APRIORI 修剪没有完全实现时）

如果我有时间阅读 Eclat 算法并重新实现它，我可以用结果更新它。我相信这里会更快，FP-growth 也会更快。

于 2014-01-22T09:10:58.713 回答
1

Karp Papadimtrioue Shanke 提出了一种非常有效的算法，即在数据的单次遍历中找到候选者（它基本上是为流处理而设计的），以便找到频率至少theta为任何thetain 的项目(0,1)。

高级算法：

  • 将元素收集到 PF 中，计算它们的外观
  • 每当遇到 1/θ 不同的元素时，将所有计数器减 1，并从 PF 中删除那些计数器为零的元素
  • 输出 PF 中在此过程中幸存的元素

该算法产生 1/Theta（最多）候选，并且它没有假阴性（不会错过任何候选） - 但它确实有一些假阳性（一些候选不常见）。

为简单起见，假设 1/Theta 是整数。

伪代码：

PF = {} //empty dictionary
for each element e:
   if PF.contains(e):
       PF[e] = PF[e] + 1
   else:
       PF[e] = 1
       if PF.size() == 1/Theta:
             for each element k in PF:
                PF[k] = PF[k] - 1
                if PF[k] == 0:
                     remove k from PF
When done, all elements in PF are your candidates.
于 2014-01-21T16:11:38.820 回答
0

这取决于您的实施。在实现 Apriori 时可以进行许多优化。

首先，如果您阅读 Agrawal 和 Srikant 的原始 Apriori 论文，您会注意到他们建议使用特殊的哈希树来有效地计算候选人的支持度。如果您想了解这个实现是如何工作的，SPMF 开源数据挖掘库中有一个使用 HashTree 实现的 Apriori 版本。它被命名为 AprioriHT。

另一个避免多次扫描数据库的优化称为 AprioriTID。每个项目集都用包含它的事务 id 集（tid 集）进行注释。那么当通过组合A和B两个项目集生成候选时，不扫描数据库直接统计AUB的支持度，可以进行A和B的tid集的交集。为了进一步优化，可以实现tid sets位向量。此版本的 APriori 称为 AprioriTID。

在算法 Pascal 中提出了另一种优化。它是利用形式概念分析中的生成器项集的概念，在不扫描数据库的情况下，利用生成器的概念来推断某些项集的支持阈值。

另一个优化是按字典顺序对 Apriori 中每个级别的项集进行排序，并按字典顺序对每个项集中的所有项进行排序。然后，在生成候选者时，您可以使用此排序来避免将所有项集相互比较以生成更大的候选者。

还有其他优化。在 FIMI 网站上，有各种不同优化的实现。

如果您想查看优化版本，可以查看我在 Java中的SPMF 数据挖掘库中的实现。此外，在同一个网站上，您将获得更快算法的实现，例如 FPGrowth。

于 2014-02-26T15:49:58.553 回答