algorithm - 先验算法

Question

我以前多次听说过 Apriori 算法，但一直没有时间或机会深入研究它，谁能用简单的方式向我解释一下这个算法的工作原理？另外，一个基本的例子会让我更容易理解。

Answer 1

先验算法

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

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

Apriori Property - 一个给定的 (k+1)-itemset 是一个候选 (k+1)-itemset 只有当每个人它的 k-itemset 子集是频繁的。

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

1. 最初，扫描数据库/数据集一次以获得频繁的1-itemset。
2. 从长度为 k 的频繁项集中生成 长度为 k+1 的候选 项集。
3. 根据数据库/数据集测试候选人。
4. 当无法生成频繁集或候选集时终止。

解决的例子

假设有一个交易数据库如下，有4笔交易，包括他们的交易ID和购买的元素。假设最小支持度 - min_sup 为 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} 不满足 2 的 min_sup >。因此，它不会包含在频繁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} 和 {A,E} 项集不满足 的 min_sup 2 因此它们不会包含在频繁的2-itemset, L_2

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

现在让我们对数据库进行第 3 次扫描并获取候选 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} code> 不满足 2 的 min_sup。因此它们不会被包含在频繁的3-itemset中，L_3如下。

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

现在，最后，我们可以计算出关联/关联规则可以由项集{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