大数据挖掘Apriori算法.doc

《大数据挖掘Apriori算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告实验课程名称：数据挖掘实验项目名称：Apriori算法理学院实验时间：2014年11月11日学生所在学院：理学院专业：统计学班级：姓名学号实验组实验时间指导教师成绩实验项目名称Apriori算法实验目的及要求：1.加强对Apriori算法的理解2.锻炼分析问题、解决问题以及动手能力3.编程实现Apriori算法实验（或算法）原理：Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代：频繁K项Lk集用于搜索频繁(K+1)项集Lk+1，如此下去，直到不能找到维度更高的频繁项集为止。这种方法依赖连接和剪枝这两步来实现。

2、算法的第一次遍历仅仅计算每个项目的具体值的数量，以确定大型l项集。随后的遍历，第k次遍历，包括两个阶段。首先，使用在第(k-1)次遍历中找到的大项集Lk-1和用Aprioir-gen函数产生候选项集Ck。接着扫描数据库，计算Ck中候选的支持度。用Hash树可以有效地确定Ck中包含在一个给定的事务t中的候选。算法如下：(1) L1 = {大项目集1项目集};(2) for  (k = 2; Lk-1 != 空; k++)  do  begin(3) Ck = apriori-gen(Lk-1);      //新的候选集(4)for  所有事务

3、 t ∈D  do  begin(5)     Ct = subset ( Ck，t);     //t中所包含的候选 (6) for  所有候选 c ∈Ct  do (7)c.count++;(8)end(9)Lk = {c ∈Ck 

4、 c.count ≥ minsupp}(10) end(11) key = ∪Lk；Apriori-gen函数：1]Apriori候选产生函数Apriori-gen的参数Lk-1，即所有大型(k-1)项目集的集合。它返回所有大型k项目集的集合的一个超集(Superset)。首先，在Jion(连接)步骤，我们把

5、Lk-1和Lk-1相连接以获得候选的最终集合的一个超集Ck：(1) insert  into  Ck(2) select  p[1]，p[2]，……，p[k-1]，q[k-1](3) from  Lk-1p，Lk-1q(4) where  p[1] = q[1]，……，p[k-2] = q[k-2]，p[k-1] < q[k-接着，在Prune(修剪)步骤，我们将删除所有的项目集 c∈Ck，如果c的一些k-1子集不在Lk-1中，为了说明这个产生过程为什么能保持完全性，要注意对于Lk中的任何有最小支持度的项目集，任何大小为k-1的子集也必须有最

6、小支持度。因此，如果我们用所有可能的项目扩充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中的项目集。(1) for  所有项目集c ∈Ck  do(2)

7、 for  所有c的 (k-1) 子集 s  do (3)if (s￠Lk-1)  then(4)从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都指向另一

8、个节点。Hash树的根的深度定义为1。在深度d的一个节点指向深度d+1的节点。项目集存储在叶子中。要加载一个项目集c时，从根开始向下直到一个叶子。在深度为d的一个节点上，要决定选取哪个分枝，可以对此项目集的第d个项目使用一个Hash函数，然后跟随相应Bucket中的指针。所有的节点最初都创建成叶节点。当一个叶节点中项集数量超过某个指定的阈值时，此叶节点就转为一个节点。从根节点开始，Subset函数寻找所有包含在某个事务t中的候选，方法如下：若处于一个叶子，就寻找此叶子中的哪些项目集是包括在t中的，并对它们附加引用指向答案集合。若处于一个节点，

9、而且是通过Hash项目i从而到达此节点的，那么就对t中i之后的每个项目进行Hash，并对相应Bucket中的节点递归地应用这个过程。对于根节点，就对t中的每个项目进