先验算法

我之前曾多次听说过 Apriori 算法，但从未有时间或机会深入研究它，有人可以用简单的方式向我解释该算法的工作原理吗？另外，一个基本的例子会让我更容易理解。

先验算法

它是一种用于数据集中频繁模式挖掘的候选生成和测试方法。有两件事你必须记住。

Apriori 剪枝原理 -如果任何项集不常见，则不应生成/测试其超集。

阿普里财产 -给定的(k+1)-itemset是候选人(k+1)-itemset只有当它的每个人k-itemset子集是频繁的。

现在，这是分 4 个步骤的先验算法。

1. 最初，扫描数据库/数据集一次以获取频繁的1-itemset.
2. Generate length k+1 候选人长度项集k频繁项集。
3. Test针对数据库/数据集的候选人。
4. 当无法生成频繁集或候选集时终止。

解决的例子

假设有一个交易数据库如下，有 4 笔交易，包括交易 ID 和购买的商品。假设最小支持 -min_sup is 2。术语“支持”是指存在/包含某个项目集的事务数量。

交易数据库

tid  | items
-------------
10   | A,C,D
20   | B,C,E
30   | A,B,C,E
40   | B,E

现在，让我们创建候选人1-itemsets通过数据库的第一次扫描。它被简单地称为C_1如下。

itemset | sup
-------------
  {A}   |  2
  {B}   |  3
  {C}   |  3
  {D}   |  1
  {E}   |  3

如果我们测试这个min_sup， 我们可以看到{D}不满足min_sup of 2。所以，它不会被包含在频繁的1-itemset，我们简称为集合L_1如下。

itemset | sup
-------------
  {A}   |  2
  {B}   |  3
  {C}   |  3
  {E}   |  3

现在，让我们第二次扫描数据库，并生成候选2-itemsets，我们简称为集合C_2如下。

itemset | sup
-------------
  {A,B} |  1
  {A,C} |  2
  {A,E} |  1
  {B,C} |  2
  {B,E} |  3
  {C,E} |  2

如你看到的，{A,B} and {A,E}项集不满足min_sup of 2因此它们不会被包含在频繁的2-itemset, L_2

itemset | sup
-------------
  {A,C} |  2
  {B,C} |  2
  {B,E} |  3
  {C,E} |  2

现在让我们对数据库进行第三次扫描并获取候选者3-itemsets, C_3如下。

itemset  | sup
-------------
 {A,B,C} |  1
 {A,B,E} |  1
 {A,C,E} |  1
 {B,C,E} |  2

你可以看到，{A,B,C}, {A,B,E} and {A,C,E}不满足min_sup of 2。所以他们不会被频繁列入3-itemset, L_3如下。

itemset  | sup
-------------
 {B,C,E} |  2

现在，我们终于可以计算出support (supp), confidence (conf) and lift (interestingness value)的价值观关联/相关规则可以由项集生成{B,C,E}如下。

         Rule       | supp  |  conf   |  lift
    -------------------------------------------
     B ->  C & E    |  50%  |  66.67% |  1.33
     E ->  B & C    |  50%  |  66.67% |  1.33
     C ->  E & B    |  50%  |  66.67% |  1.77
     B & C ->  E    |  50%  |  100%   |  1.33
     E & B ->  C    |  50%  |  66.67% |  1.77
     C & E ->  B    |  50%  |  100%   |  1.33