文档介绍：Apriori算法实验报告
1背景
关联规则挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增量 式更新、无须生成候选项目集的关联规则挖掘、最大频繁项目集挖掘、约束性关联规则挖掘以及 并行及分布关联规则挖掘算: k
insert into Ck
select p[1], p[2], , p[k-1], q[k-1]
⑶ from Lk-1p, Lk-1q
(4) where p[1] = q[1] , , p[k-2] = q[k-2] , p[k-1] < q[k-1]
接着，在Prune(修剪)步骤，我们将删除所有的项目集c^Ck，如果c的一些k-1子集不在Lk-1 中，为了说明这个产生过程为什么能保持完全性，要注意对于Lk中的任何有最小支持度的项目集， 任何大小为k-1的子集也必须有最小支持度。因此，如果我们用所有可能的项目扩充Lk-1中的每个 项目集，然后删除所有k-1子集不在Lk-1中的项目集，那么我们就能得到Lk中项目集的一个超集。
上面的合并运算相当于用数据库中所有项目来扩展Lk-1 ；如果删除扩展项目集的第k-1个项目 后得到的k-1项目集不在Lk-1中，则删除该扩展项目集。条件p[k-1] < q[k-1]保证不会出现相同的 扩展项。因此，经过合并运算，Ck>Lk。类似原因在删除运算中，删除Ck中其k-1子项目集不在 Lk-1中的项目集，同样没有删除包含在Lk中的项目集。
for所有项目集c £Ck do
for 所有c的(k-1)子集s do
if (s 0 Lk-1) then
从Ck中删除c
例如：L3 为｛｛1 2 3｝，｛1 2 4｝，｛1 3 4｝，｛1 3 5｝，｛2 3 4｝｝。Jion 步骤之后，C4 为｛｛1 2 3 4｝， (1 3 4 5｝｝。Prune步骤将删除项集｛1 3 4 5｝，因为项集｛1 4 5｝不在L3中。
Subset 函数：
候选项目集Ck存储在一棵Hash树中。Hash树的一个节点包含了项集的一个链表(一个叶节点) 或包含了一个Hash表(一个内节点)。在内节点中，Hash表的每个Bucket都指向另一个节点。Hash 树的根的深度定义为1。在深度d的一个内节点指向深度d+1的节点。项目集存储在叶子中。要 加载一个项目集c时，从根开始向下直到一个叶子。在深度为d的一个内节点上，要决定选取哪 个分枝，可以对此项目集的第d个项目使用一个Hash函数，然后跟随相应Bucket中的指针。所 有的节点最初都创建成叶节点。当一个叶节点中项集数量超过某个指定的阈值时，此叶节点就转 为一个内节点。
从根节点开始，Subset函数寻找所有包含在某个事务t中的候选，方法如下：若处于一个叶子， 就寻找此叶子中的哪些项目集是包括在t中的，并对它们附加引用指向答案集合。若处于一个内节 点，而且是通过Hash项目i从而到达此节点的，那么就对t中i之后的每个项目进行Hash，并对 相应Bucket中的节点递归地应用这个过程。对于根节点，就对t中的每个项目进行Hash。
尽管Apriori算法已经可以压缩候选数据项集Ck，但是对于频繁项集尤其是2维的候选数据项 集产生仍然需要大量的存储空间。也就是说对于2维的候选数据项集，Apriori算法的剪枝操作几 乎