Apriori算法

我之前已经多次听说过Apriori算法,但从来没有时间或机会深入研究它,有人能用一种简单的方法向我解释这个算法的工作原理吗？另外,一个基本的例子可以让我更容易理解.

Apriori算法

它是数据集中频繁模式挖掘的候选生成和测试方法.你必须要记住两件事.

Apriori修剪原则 -如果任何项目集很少,则不应生成/测试其超集.

Apriori属性 -只有当每个子集的频繁出现时,给定的(k+1)-itemset是候选者.(k+1)-itemsetk-itemset

现在,这是4步骤的apriori算法.

最初,扫描数据库/数据集一次以获得频繁1-itemset.

从长度频繁项集生成长度k+1 候选项k集.

根据数据库/数据集测试候选项.

当不能生成频繁或候选集时终止.

解决了例子

假设有一个交易数据库如下,包含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通过DB的第一次扫描创建候选者.它被简单地称为如下的集合C_1.

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

如果我们测试这与min_sup,我们可以看到{D}不满足min_sup的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}而{A,E}项集不满足min_sup的2,因此他们将不会被列入频繁2-itemset,L_2

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

现在让我们对DB进行第三次扫描并获得候选者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}和{A,C,E}不满足min_sup的2.所以它们不会频繁包括在内3-itemset,L_3如下所示.

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

现在,终于,我们可以计算出support (supp),confidence (conf)并且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

请参阅数据挖掘(免费访问)中的前10个算法或数据挖掘中的前10个算法.后者给出了算法的详细描述,以及如何获得优化实现的细节.