我以前多次听说过 Apriori 算法,但一直没有时间或机会深入研究它,谁能用简单的方式向我解释一下这个算法的工作原理?另外,一个基本的例子会让我更容易理解。
最佳答案
先验算法
这是一种用于数据集中频繁模式挖掘的候选生成和测试方法。您必须记住两件事。
Apriori 剪枝原则 -如果任何项集不频繁,则不应生成/测试其超集。
Apriori Property - 一个给定的 (k+1)-itemset
是一个候选 (k+1)-itemset
只有当每个人它的 k-itemset
子集是频繁的。
现在,这是分 4 个步骤的先验算法。
- 最初,扫描数据库/数据集一次以获得频繁的
1-itemset
。 - 从长度为
k
的频繁项集中生成 长度为k+1
的候选 项集。 - 根据数据库/数据集测试候选人。
- 当无法生成频繁集或候选集时终止。
解决的例子
假设有一个交易数据库如下,有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
22-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
关于algorithm - 先验算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1248373/