FPGrowth是否仍在频繁的模式开采中被视为“最新技术”？

Question

据我所知，算法的开发解决了频繁的模式挖掘（FPM）问题，改进的道路具有一些主要检查站。首先， Apriori 算法是在1993年提出的 Agrawal等。, ，以及问题的形式化。该算法能够 剥离 来自 2^n - 1 通过使用晶格维护数据来设置（PowerSet）。该方法的缺点是需要重新阅读数据库以计算每个集合的频率扩展。

后来，1997年， 扎基等。 提出了算法 eclat, ， 哪个 插入 晶格内每个集合的结果频率。这是通过在晶格的每个节点上添加的，即从根到引用节点的项目的集合。主要的贡献是，不必重新阅读整个数据集即可了解每个集合的频率，但是保留此类数据结构所需的内存可能会超过数据集本身的大小。

在2000年， Han等。 提出了一种名称的算法 fpgrowth, ，以及名为FPTREE的前缀-Tree数据结构。该算法能够提供重大的数据压缩，同时还要授予仅产生频繁的项目集（没有候选项目集生成）。这主要是通过按降顺序对每个交易的项目进行排序，以便最常见的项目是树数据结构中重复最少的项目。由于频率仅在深入遍历树时仅下降，因此该算法能够 剥离 非频繁的项目集。

编辑:

据我所知，这可能被认为是一种最先进的算法，但我想了解其他提议的解决方案。 FPM的其他哪些算法被认为是“最先进的”？是什么 直觉/主要贡献 这种算法？

FPGrowth算法是否仍在频繁的模式开采中被视为“最新技术状态”？如果没有，哪种算法可以更有效地从大型数据集中提取频繁的项目集？

Answer 1

如下所述的最新技术：在实践中使用还是在理论上工作？

除了开发新的频繁项目集算法外，APRIORI无处不在。它易于实现，并且易于在非常不同的域中重复使用。您会发现数百种质量的APRIORI实现。实际上，很容易弄错Apriori。

FP Growth难以实施，但更有趣。因此，从学术的角度来看，每个人都试图改善fprowth-到现在基于Apriori的工作将非常困难。

如果您的实施良好，则每种算法都很好，我认为这是不良情况。良好的APRIORI实施将 只要 需要扫描数据库 k 找到所有长度的频繁项目集 k. 。特别是，如果您的数据适合主内存，这很便宜。可以杀死Apriori的2个项目太多（特别是当您不使用Trie和类似的加速技术等时）。它在大数据上最有效，频繁项目集数量较低。

Eclat在列上工作；但是它需要更频繁地阅读每一列。在差异方面有一些工作以减少这项工作。如果您的数据不适合主内存，则ECLAT可能会遭受APRIORI的痛苦。首先，通过深度进行深度，它还可以比Apriori早得多返回一个有趣的结果，您可以使用这些结果来调整参数。因此，您需要更少的迭代才能找到好的参数。但是，通过设计，它不能像Apriori那样整洁地进行修剪。

fprowth将数据设置压入树中。当您有很多重复记录时，这最有效。如果您可以预设数据并将重复的重复载体合并为加权矢量，那么您也可能会为Apriori和Eclat获得很多收益。 fprowth在极端层面上做到这一点。缺点是实施更加困难。而且，一旦这棵树不再适合内存，就会变得一团糟。

至于性能结果和基准 - 不要信任它们。有很多事情要错误地实施。尝试10种不同的实现，您将获得10个截然不同的性能结果。特别是对于Apriori，我的印象是，大多数实现都因为缺少Apriori的某些主要贡献而破坏了……而在这些部分正确的情况下，优化的质量差异很大。

实际上，甚至还有关于如何有效实施这些算法的论文：

Apriori和Eclat的有效实施。
克里斯蒂安·博格尔特（Christian Borgelt）
频繁的商品集挖掘实施研讨会（FIMI 2003，美国墨尔本，美国）。

您可能还想阅读有关此领域的这些调查：

• 戈特尔，巴特。 “关于频繁采矿的调查。”大学。赫尔辛基（2003）。

• Ferenc Bodon，一项关于频繁项目集采矿的调查，技术报告，布达佩斯技术与经济大学，2006年，2006年，

• 频繁的物品集开采
  克里斯蒂安·博格尔特（Christian Borgelt）
  Wiley跨学科评论：数据挖掘和知识发现2（6）：437-456。 2012

Answer 2

我在文献中看到的大多数近期频繁模式方法都是基于优化FP Growth的。我不得不承认，多年来，FPM的文献中没有看到很多发展。

这个Wikibook 突出显示了FPGrowth上的许多变体。