关联规则实验报告.docVIP

Apriori算法的设计与实现 1，实验要求 频繁项目集的计算 根据题目给定的原始事务记录和最小支持度，通过迭代的方法求出各项频繁项目集。 关联规则的产生 根据（1）中求得频繁项目集和给定的最小可信度，求出相关的关联规则。 2.1Apriori算法的原理 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。很多的的挖掘算法是在Apriori算法的基础上进行改进的，比如基于散列（Hash）的方法，基于数据分割（Partition）的方法以及不产生候选项集的FP-GROWTH方法等。因此要了解关联规则算法不得不先要了解Apriori算法。 Apriori算法使用一种称作逐层迭代的候选产生测试（candidate generation and test）的方法，k-项目集用于探索（k+1）-项目集。首先，找出频繁1-项目集的集合，该集合记作L 。L 用于找频繁2-向募集到集合L ，而L 用于找L ，如此下去，直到不能找到频繁k-项目集。找每一个L 均需要一次数据库的扫描。 Apriori性质：频繁项集的所有非空子集必须也是频繁的。Apriori性质基于如下观察：根据定义，如果项集I不满足最小支持度阈值，则I不是频繁的，即support(I)＜min-sup。如果项A添加到I，则结果项集（即IUA）不可能比I更频繁出现。因此，IUA也不是频繁的，即support(IUA)＜min-sup。 算法应用Apriori性质以LK-1来找LK，这一过程由连接和剪枝组成。 C ：Candidate itemset of size k，即k-候选项目集。 L ：frequent itemset of size k，即k-频繁项目集。 1、连接步：为找L ，通过L 与自己连接产生候选k-项集的集合。该候选项集记作C 。设 和 是L 中的项集。记 [j]表示 的第j项（例如， [k-2]表示的倒数第3项）。为方便计，假定事务或项集中的项按字典次序排列。执行LK-1与自身连接，其中，LK-1的元素是可连接的，如果（ [1]= [1]）∧（ [2]= [2]）∧…∧（ [k-2]= [k-2]）∧（ [k-1]＜ [k-1]）。条件（ [k-1]＜ [k-1]）是简单地保证不产生重复。连接 和 产生的结果项集是 [1] [2] … [k-1] [k-1]。 2、剪枝步：C 是L 的超集，即是，它的成员可以是频繁的也可以是不频繁的，但所有的频繁k-项集都包含在C 中。扫描数据库，确定C 中每个候选的计数，从而确定L （即根据定义，计数值不小于最小支持度计数的所有候选是频繁的，从而属于L ）。然而C 可能很大，这样所涉及的计算量就会很大。为压缩C ，可以用一下办法使用Apriori性质：任何非频繁的（k-1）－项集都不可能是频繁k-项集的子集。因此，如果一个候选k-项集的（k-1）子集不在L 中，则该候选也不可能是频繁的，从而可以由C 中删除。这种子集测试可以使用所有频繁项集的散列树快速完成。 算法首先扫描数据库，各数据项每出现一次，计数一次。由每个数据项的计数值可以算出其支持度。支持度超过阈值的1-itemset即为频繁1-itemset。产生所有单项频繁数据项集的集合L 。从L 出发，可以循环计算二项频繁项集L 、三项频繁项集L 、…L 、…。直到有某个r值使得L 为空，这时算法停止。这里在第k次循环中，即：从L 计算L 时，先用apriori_gen()函数从L 生成候选的k项数据项集的集合C ，C 中的每一个项集是对两个只有一个项不同的属于L 的频繁项集做一个（k-2）-连接来产生的。C 中的项集是用来产生和频集的候选集，最后的频集L 必须是C 的一个子集。C 中的每个元素需在交易数据库中进行验证来决定其是否加入L 。 L =Find_frequent_1_itemset(T){ //发现1_项集 for(k=2; L !=Φ;k++) begin C =apriori_gen(L ); // C =candidate generated from L for each transaction t∈database D //扫描D计数 begin C =subset(C ,t); //t中包含的候选频繁项集 for each candidates c∈C c.count++; //increment the count of all candidates end L ={c∈C |c.count=minsup} en