Apriori算法

先决条件—— 数据集中的频繁项集（关联规则挖掘） Apriori算法 由R.Agrawal和R.Srikant在1994年给出，用于在布尔关联规则的数据集中查找频繁项集。该算法的名称是Apriori，因为它使用了频繁项集属性的先验知识。我们采用迭代方法或逐级搜索，其中k频繁项集用于查找k+1项集。

为了提高按级别生成频繁项集的效率，使用了一个重要属性 先验性质 这有助于减少搜索空间。

先验属性—— 频繁项集的所有非空子集都必须是频繁的。Apriori算法的关键概念是支持度的反单调性。先验假设

频繁项集的所有子集都必须是频繁的（Apriori属性）。 如果一个项目集不频繁，那么它的所有超集都将不频繁。

在我们开始理解这个算法之前，先看一下我在前一篇文章中解释的一些定义。 考虑下面的数据集，我们会发现频繁项集，并为它们生成关联规则。

最低支持数为2 最低置信度为60%

第一步： K=1 （一） 创建一个表，其中包含数据集中存在的每个项目的支持计数，称为 C1（候选集）

（二） 将候选集项目的支持度计数与最小支持度计数进行比较（此处，最小支持度=2，如果候选集项目的支持度计数小于最小支持度，则删除这些项目）。这为我们提供了项目集L1。

第二步： K=2

• 使用L1生成候选集C2（这称为连接步骤）。加入L的条件 _k-1 我呢 _k-1 它应该有（K-2）个相同的元素。
• 如果不是频繁项集，则删除或删除所有频繁项集。（示例{I1，I2}的子集是{I1}，{I2}它们是频繁的。检查每个项目集）
• 现在通过在数据集中搜索来查找这些项集的支持计数。
  

  （二） 将候选项（C2）的支持度计数与最小支持度计数进行比较（这里的最小支持度=2，如果候选项集项目的支持度计数小于最小支持度，则删除这些项目），这将为我们提供项目集L2。

  

  第三步：

  • 使用L2生成候选集C3（连接步骤）。加入L的条件 _k-1 我呢 _k-1 它应该有（K-2）个相同的元素。所以这里，对于L2，第一个元素应该匹配。 所以通过连接L2生成的项集是{I1，I2，I3}{I1，I2，I5}{I1，I3，I5}{I2，I3，I4}{I2，I4，I5}{I2，I3，I5}
  • 检查这些项目集的所有子集是否频繁，如果不是，则删除该项目集。（这里，{I1，I2，I3}的子集是{I1，I2}，{I2，I3}，{I1，I3}的频繁子集。对于{I2，I3，I4}，子集{I3，I4}不频繁，所以删除它。同样地检查每个项目集）
  • 通过在数据集中搜索来查找这些剩余项集的支持计数。
  

  （二） 将候选项（C3）支持度计数与最小支持度计数进行比较（这里的最小支持度=2，如果候选项集项目的支持度计数小于最小支持度，则删除这些项目），这将为我们提供项目集L3。

  

  第4步：

  • 使用L3生成候选集C4（连接步骤）。加入L的条件 _k-1 我呢 _k-1 （K=4）就是说，它们应该有（K-2）个相同的元素。因此，对于L3，前两个元素（项）应该匹配。
  • 检查这些项目集的所有子集是否频繁（这里，通过连接L3形成的项目集是{I1，I2，I3，I5}，因此其子集包含{I1，I3，I5}，这是不频繁的）。所以C4中没有设置项目
  • 我们停在这里是因为没有找到更多的频繁项集

  ---

  因此，我们发现了所有的频繁项集。现在，强关联规则的生成就出现了。为此，我们需要计算每个规则的置信度。

  信心—— 60%的信心意味着60%购买牛奶和面包的顾客也会购买黄油。

  Confidence(A->B)=Support_count(A∪B)/Support_count(A)

  因此，在这里，我们将以任何频繁项集为例，展示规则生成。 项集{I1，I2，I3}//来自L3 所以规则可以是 [I1^I2]=>[I3]//置信度=sup（I1^I2^I3）/sup（I1^I2）=2/4*100=50% [I1^I3]=>[I2]//置信度=sup（I1^I2^I3）/sup（I1^I3）=2/4*100=50% [I2^I3]=>[I1]//置信度=sup（I1^I2^I3）/sup（I2^I3）=2/4*100=50% [I1]=>[I2^I3]//置信度=sup（I1^I2^I3）/sup（I1）=2/6*100=33% [I2]=>[I1^I3]//置信度=sup（I1^I2^I3）/sup（I2）=2/7*100=28% [I3]=>[I1^I2]//置信度=sup（I1^I2^I3）/sup（I3）=2/6*100=33%

  因此，如果最小置信度为50%，那么前3条规则可以被视为强关联规则。

  Apriori算法的局限性 Apriori算法可能很慢。主要限制是需要时间来保存大量的候选集，这些候选集具有频繁的项集、较低的最小支持度或较大的项集，即对于大量数据集来说，这不是一种有效的方法。例如，如果频繁的1项集中有10^4个候选项，则需要将超过10^7个候选项生成为2项长度，然后对其进行测试和累积。此外，为了检测大小为100的频繁模式，即v1、v2…v100，它必须生成2^100个候选项集，从而产生昂贵且浪费时间的候选项集。所以，它会检查候选项集中的多个集合，并且会多次重复扫描数据库以查找候选项集。当内存容量受限于大量事务时，Apriori将非常低且效率低下。[来源： https://arxiv.org/pdf/1403.3948.pdf ]