经典挖掘算法Apriori与关联规则

2023-06-16 理论教育版权反馈

【摘要】：Apriori算法[3]是单维、单层、布尔关联规则挖掘算法，是最简单形式的关联规则挖掘。该算法是挖掘产生布尔关联规则频繁项目集的经典算法，对关联规则挖掘研究有着重要影响。图2.3Apriori-gen算法Apriori算法调用Apriori-gen，生成所有频繁项集，如图2.4所示。Apriori算法假定数据库驻留在内存中。Apriori算法之后，学者们不断研究其改进算法及其他思想的关联规则挖掘算法，取得了很多成果。图2.4Apriori算法图2.5找出频繁项集L后生成关联规则算法

Apriori算法[3]是单维、单层、布尔关联规则挖掘算法，是最简单形式的关联规则挖掘。该算法是挖掘产生布尔关联规则频繁项目集的经典算法，对关联规则挖掘研究有着重要影响。首先，关联规则的挖掘被分为两个步骤：

（1）找出满足minsup的所有频繁项集。

（2）从频繁项集生成关联规则。

步骤（1）中，算法利用一个逐层搜索的迭代方法来完成频繁项目集的挖掘。具体的做法如下：首先访问一次数据库，找出频繁1-项集，记为L1；利用L1×L1生成频繁2-项集候选集C2；访问一次数据库筛掉C2中的非频繁项集，形成频繁2-项集L2；利用L2×L2生成3-项集，根据[性质2.1]和[性质2.2]去掉3-项集中不可能频繁的项集实现剪枝，留下的作为C3；访问一次数据库筛掉C3中的非频繁项集，形成频繁3-项集L3；如此不断地循环下去直至Ck或Lk空为止。

Apriori算法中将由Lk×Lk生成k+1-项目集，并剪枝形成Ck+1的过程分离出来称Apriori-gen算法，如图2.3所示。

pagenumber_ebook=13,pagenumber_book=8

图2.3　Apriori-gen算法

Apriori算法调用Apriori-gen，生成所有频繁项集，如图2.4所示。

Apriori算法假定数据库驻留在内存中。数据库扫描的最大趟数等于最大的频繁项目集的基数加1。生成了频繁项集L后，关联规则的生成变得非常直接。其算法命名为ARGen，如图2.5所示。

许多情况下，Apriori算法的产生——剪枝方法大幅度地压缩了候选项集的大小，具有较好的性能。但在数据库规模巨大、项目稠密的情况下，频繁1-项集很大和最终产生的频繁模式很长，Apriori算法就需要大量的剪枝运算和多次扫描数据库，算法的效率会大大降低。Apriori算法之后，学者们不断研究其改进算法及其他思想的关联规则挖掘算法，取得了很多成果。

pagenumber_ebook=14,pagenumber_book=9

图2.4　Apriori算法

pagenumber_ebook=14,pagenumber_book=9

图2.5　找出频繁项集L后生成关联规则算法

经典挖掘算法Apriori与关联规则

相关推荐