5

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

4

4 回答 4

11

先验算法

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

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

Apriori 属性——一个给定的只有当它的每个子集都是频繁的时(k+1)-itemset才是候选者。(k+1)-itemsetk-itemset

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

  1. 最初，扫描数据库/数据集一次以获取频繁的1-itemset.
  2. 从长度频繁项集生成长度k+1 候选项集。k
  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}不满足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

现在让我们对数据库进行第 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}和{A,C,E}不满足min_sup。2所以它们不会被包含在frequent3-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
于 2017-04-13T05:40:02.690 回答
6

请参阅数据挖掘中的十大算法（免费访问）或数据挖掘中的十大算法。后者给出了算法的详细描述，以及如何获得优化实现的细节。

于 2010-02-05T17:58:30.177 回答
4

好吧，我假设你已经阅读了维基百科条目，但你说“一个基本的例子会让我更容易理解”。维基百科就是这样，所以我假设您还没有阅读它并建议您阅读。

阅读维基百科文章。

于 2009-08-08T08:50:55.963 回答
2

Apriori 的最佳介绍可以从这本书下载：

http://www-users.cs.umn.edu/~kumar/dmbook/index.php

您可以免费下载第 6 章，其中非常清楚地解释了 Apriori。

另外，如果想下载Java版的Apriori等频繁项集挖掘算法，可以查看我的网站：

http://www.philippe-fournier-viger.com/spmf/

于 2011-10-22T18:29:10.540 回答