Apriori算法实验报告

Apriori算法实验报告1背景关联规则挖掘的研究工作主要包括：Apriori算法的扩展、数量关联规则挖掘、关联规则增量式更新、无须生成候选项目集的关联规则挖掘、最大频繁项目集挖掘、约束性关联规则挖掘以及并行及分布关联规则挖掘算法等，其中快速挖掘与更新频繁项目集是关联规则挖掘研究的重点，也是多种数据挖掘应用中的技术关键，已用于分类规则挖掘和网络入侵检测等方面的研究。研究者还对数据挖掘的理论进行了有益的探索，将概念格和粗糙集应用于关联规则挖掘中，获得了显著的效果。到目前为止，关联规则的挖掘已经取得了令人瞩目的成绩，包括：单机环境下的关联规则挖掘算法；多值属性关联规则挖掘；关联规则更新算法；基于约束条件的关联规则挖掘；关联规则并行及分布挖掘算法等。2算法描述Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代：频繁 K项Lk集用于搜索频繁(K+1)项集Lk+1，如此下去，直到不能找到维度更高的频繁项集为止。这种方法依赖连接和剪枝这两步来实现。算法的第一次遍历仅仅计算每个项目的具体值的数量，以确定大型l项集。随后的遍历，第k次遍历，包括两个阶段。首先，使用在第(k-1)次遍历中找到的大项集Lk-1和用Aprioir-gen函数产生候选项集Ck。接着扫描数据库，计算Ck中候选的支持度。用Hash树可以有效地确定Ck中包含在一个给定的事务t中的候选。算法如下：L1={大项目集1项目集};for(k=2;Lk1!=空；k++)dobeginCk=apriori-gen(Lk-1); 〃新的候选集for所有事务t£DdobeginCt=subset(Ck，t); //t中所包含的候选for所有候选c£Ctdoc.count++;endLk={c£Ck|c.count^minsupp}endkey=ULk；Apriori-gen函数：Apriori候选产生函数Apriori-gen的参数Lk-1，即所有大型(k-1)项目集的集合。它返回所有大型k项目集的集合的一个超集(Superset)。首先，在Jion(连接)步骤，我们把Lk-1和Lk-1相连接以获得候选的最终集合的一个超集C:kinsertintoCkselectp[1],p[2], , p[k-1],q[k-1]⑶fromLk-1p,Lk-1q(4)wherep[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£Ckdofor所有c的(k-1)子集sdoif(s0Lk-1)then从Ck中删除c例如：L3为｛｛123｝，｛124｝，｛134｝，｛135｝，｛234｝｝。Jion步骤之后，C4为｛｛1234｝，(1345｝｝。Prune步骤将删除项集｛1345｝，因为项集｛145｝不在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算法的剪枝操作几乎不起任何作用。例如：1维高频数据项集L1的规模是O(n)，则2维候选数据项集的规模将达到O(n2)。如果我们考虑一般情况，即在没有支持度的情况下1维高频数据项集L1的规模是103，则2维候选数据项集的规模C2将达到C1000笃X105.这种空间复杂度以指数形式的增长，使得这个经

典的算法的执行效率很难让人满意.Apriori算法的两大缺点就是产生大量的候选集，以及需重复扫描数据库。3实验结果与分析实验测试用机为P41.49GHZ，内存256M。实验采用蘑菇数据库，项目数=15，共进行了6组实验，实验数据如下:表1、表2为时间性能表；表3为对于不同的记录数和最小支持度所测试到的频繁项目集的个数。记录数time(s)2001记录数time(s)2001500410005200014400049800090表1：最小支持度=0.7记录数time(s)200150021000420009400027800059表2:最小支持度=0.9表3：'频繁项目集记录数、Min_supL1L2L3L4L5L62000.791930251120.9910105105000.792030251120.9910930010000.7915102000.971000020000.78202718610.9710930040000.78222613200.985200080000.7918209100.9831000下图为对表1、表2中数据的绘制:

emirOOOOOOOOOOO09876543211—emirOOOOOOOOOOO09876543211—sup=0.7—sup=0.9从上图可以看出当增大数据库或者减少最小支持度时，都会增加计算的时间而且是成指数增加。因为算法在每次循环时都要重新扫描数据库来计算支持度，而增大数