先验算法

好吧,我假设你读过维基百科的词条,但你说“一个基本的例子会让我更容易理解”。维基百科就是这样的,所以我假设你没有读过它,并建议你读。

阅读 wikipedia 文章。

见 Top 10 algorithms in data mining (免费访问)或 The Top Ten Algorithms in Data Mining . 后者给出了算法的详细描述,以及如何获得优化实现的详细信息。

先验算法

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

先验剪枝原理- 如果不经常出现任何项集,则不应生成/测试它的超集。

先验财产- 给定的 (k+1)-itemset 是候选人 (k+1)-项集 只有当它的每个人 k-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

如果我们用 小苏普 我们可以看到 {D} 不满足 小苏普 属于 二 . 因此,它将不包括在 1-项集 我们称之为 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} 项集不满足 小苏普 属于 二 因此,它们将不包括在 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} 和 {A,C,E} 不满足 小苏普 属于 二 . 所以他们不会经常被列入 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

Apriori的最佳介绍可从本书下载:

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

你可以免费下载第6章,其中解释得很清楚。

此外,如果您想下载Apriori的Java版本和其他频繁项集挖掘算法,您可以查看我的网站:

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