基于闭项目集的Apriori算法改进.docx

1、基于闭项目集的Apriori算法改进基于闭项目集的Apriori算法改进首都师范大学信息工程学院2013-2014学年第二学期2013硕士研究生 计算机应用技术 专业期末考试试卷课程名称 数据挖掘 考试形式 撰写学术论文 考试时间 2014.4.21考试对象 2013级研究生 姓名 李燕 学号 2131002053任课教师利民 成绩基于闭项目集的Apriori算法李燕（首都师范大学信息工程学院，北京 100089）摘 要：本文针对Apriori算法中需要不断扫描原始事务项集问题，介绍了在某些情况下，可以大大减少扫描次数的close算法，同时对此算法给出了改进的想法和简单实现。关键字：关联规则

2、Apriori算法 频繁闭项集、close算法An improved Apriori algorithmAbstract: This article in view of the Apriori algorithm need to constantly scan the original transaction itemsets，Introduced 一条事务，或者说一条记录，是形如tid，X)的二元组，其中tid称为事务标识符，它唯一标识该条记录，X为项目集。要挖掘的数据集或者数据库D是N条事务的集合，一条事务也称为一条记录，N为数据集D的记录总数。若事务t包含项目集X中的所有项目，则称事务

3、t支持或包含项目集X。定义1.3：支持度计数和支持度数据库TDB中包含(支持)项集X的事务的数目称为项集X的支持度计数，记为count(X)， support(X)=count(X)N称为项集X的支持度，其中N为数据库中记录总数。定义1.3：支持度计数和支持度数据库TDB中包含(支持)项集X的事务的数目称为项集X的支持度计数，记为count(X)， support(X)=count(X)N称为项集X的支持度，其中N为数据库中记录总数。定义1.4：频繁项目集支持度不小于用户给定的最小支持度阈值(minsup)的项集称为频繁项目集，或者大项目集。所有的频繁1-项集记为Ll定义1.5：关联规则关联规

4、则是形如X=Y的蕴涵式，X称为关联规则的前件或前提，Y称为关联规则的后件或结论。项集XUY的支持度称为关联规则的支持度。定义1.6: 置信度关联规则X=Y的置信度。确定Y在包含X的事务中出现的频繁程度。confidence(X=Y)=支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。一般来说，只有支持度和置信度均较高的关联规则才可能是用户感兴趣、有用的关联规则。 Agrawal等人建立了用于事务数据库挖掘的项集格空间理论。这个理论核心的原理是：频繁项目集的子集是频繁项目集；非频繁项目集的超集是非频繁项集。这个原理一直作为

5、经典的数据挖掘理论被应用。定理1.1：如果项目集X是频繁项目集，那么它的所有非空子集都是频繁项目集。定理1.2：如果项目集X是非频繁项目集，那么它的所有超集都是非频繁项目集。关联规则发现：对于给定的事务集D，关联规则发现是指从D中挖掘出支持度和置信度分别大于等于minsup和minconf的所有规则，其中minsup和minconf是对应的支持度和置信度阈值。2 经典关联规则挖掘算法一种原始的关联规则挖掘方法是：计算所有规则的支持度和置信度，再删去支持度或置信度不满足阈值的规则。因为从数据集中提取的规则的数目是指数级，这种方法的计算任务繁重，过高的代价使得它在很多场合下变得不可行。研究者通过对

6、关联规则挖掘的研究发现，很多规则是没有必要计算的。只计算可能满足要求的规则，可以节省大量的时间。目前通常采用一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务：(1)生成频繁项集，其任务是生成所有满足最小支持度阈值的项集，这些项集被称作频繁项集(Frequent ltemset)；通常用格结构(Lattice structure)来表示所有可能的项集。一个包含k个项的项集最多可能产生(2。-1)个非空频繁项集。由于在许多实际应用中k的值可能非常大，需要查找的项集搜索空问可能是指数规模的。一种原始的频繁项集生成方法是确定格结构中每个候选项集(Candidate Itemset)的支持度计数

7、。为了完成这一任务，必须将每个候选项集与每个事务进行比较。如果候选项集包含在事务中，则给候选项集的支持度计数加1。这种方法的开销可能非常大。(2)生成规则，其任务是从上一步生成的频繁项集中提取所有高置信度的规则。频繁项集是满足支持度阈值的项集，对这些项集再增加置信度的要求，即可从数据集中挖掘出满足要求的关联规则。关联规则可以这样来从频繁项集中提取；将一个频繁项集Y划分成两个非空的子集X和Y-X，所有满足置信度阈值的规则X=Y-X即是所要生成的规则。因为这些规则都是由频繁项集产生的，所以它们必然满足支持度阈值。排除前件或后件为空集的规则，每个频繁k项集能够产生多达2k一1个关联规则。计算关联规则

8、的置信度并不需要再次扫描事务数据集。例如对于规则臼，A,B= C，它是由频繁项集x=A，B，C)产生的。该规则的置信度为Count fA，B，CCountA，B。因为A，B，C)是频繁的，项集A，B)也一定是频繁的。由于这两个项集的支持度计数已经在频繁项集产生时得到，因此不必再扫描整个数据集。相对频繁项集生成而言，规则的生成较为简单和直观。通常，生成频繁项集所需的计算开销远大于生成规则所需的计算开销。2.1 Apriori算法简介Apriori算法是现今研究关联规则中最具代表性的方法，虽然之后有许多算法被提出，但皆是依据此架构做改进或延伸，Apriori算法利用层次顺序搜索的循环方法(又称作逐

9、层搜索的迭代方法)来完成频繁项集的挖掘工作，同时利用Apriori定理来压缩搜索空间，提高频繁项集产生的效率。Apriori定理：频繁项集的所有非空子集也一定是频繁的。频繁项集也称作是向下封闭的，因为如果一个项集满足最小支持度的要求，其所有子集也满足这一要求。对于Apriori算法中的数据表示，采用水平数据表示法，在水平数据表示中，数据库的一条事务由事务标识符(TID)和项目组成。事务由TID唯一标识，一条事务可以包含一个项目或多个项目。图表1实例形象说明了这种表示方案。 图1：Apriori水平数据表示在该算法中支持度的计算是在扫描数据库的前提下，不断的计数进行的。扫描数据库一次，对每一条事

10、务，若事务包含项目，则该项目的支持度计数增l。2.2 Apriori算法原理Apriori算法的基本思想是先找出所有频繁1- 项集， 这些项集组成L1， 然后由L1 产生频繁2-项集L2， 然后用L2 求出L3， 以此类推直到没有新的频繁项集产生。从Lk- 1 到Lk 的实现， 首先把Lk- 1 与自身连接生成候选k-项集合， 记为Ck， 然后对中的数据项集频度进行统计， 丢弃低频度的数据项集。形成Lk 连接的过程: 从Lk- 1中取出l1， l2， l1j表示l1 的第j 项， 如果两者的前k- 2 项相同， 则进行链接形成k- 项候选项集l11l12l1k- 1l2k- 1， 加入到Ck

11、中， Ck 中的每个元素需在交易数据库中进行验证来决定其是否加入Lk， 这里的验证过程是影响算法性能的一个瓶颈。每求一个Lk 需要对数据库扫描一遍。为了提高生成频繁项集的效率， 用到了数据项集的一个基本性质。根据关联规则的性1以及推论可知， 一个项集是频繁项集当且仅当它的所有子集是频繁集， 那么如果Ck 中某个候选k- 项集有一个(k- 1)- 项子集不属于Lk-1， 则这个候选k-项集可以被修剪，不再被考虑，这个修剪过程可以降低计算候选集支持度的代价。具体算法，首先获得最小支持度，以及全体事务集。具体步骤如下:1扫描事务数据库TDB一次，找到Ll频繁1-项集的集合；2For(k=2；Lk-1

12、；k+)do(1)由Lk-l产生候选集Ck，即长度为k的所有候选项目集。当且仅当k项集X的所有的长度为(k1)的子集都包含在Lk1，它才应该被包含在Ck；(2)若Ck=。则转步骤3；(3)扫描事务数据库TDB一次，对Ck的每一个项集，计算其支持度；(4)Lk=X|(XCk)(sup(X) minsupp)；3Return 2.3 实例分析Apriori算法瓶颈基于频繁项集的Apriori算法采用了逐层搜索的迭代的方法，算法简单明了，没有复杂的理论推导，也易于实现。但是它存在一些难以克服的缺陷：(1)对数据库的扫描次数过多。在Apriori算法的扫描中，每生成一个候选项集，都要对数据库进行一次全

13、面的搜索。如果要生成最大长度为K的频繁项集，那么就要对数据库进行K次扫描。当数据库中存放大量的事务数据时，在有限的内存容量下，系统I0负载相当大，每次扫描数据库的时间就会很长，这样效率就非常低。(2)Apriori算法可能产生大量的候选项集。在规模较大的情况下，Apriori算法需要产生大量的候选项集。(3)在频繁项集长度变大的情况下，运算时问显著增加。当频繁项集长度变大时，支持该频繁项集的事务会减少，从理论上讲，计算其支持度所需要的时间不会明显增加，但Apriori算法仍然是在原来事务数据库中来计算频繁项集的支持度，由于每个频繁项集的项目变多了，所以在确定每个频繁项集是否被事务支持的开销也增

14、大了，而且事务没有减少，因此频繁项集长度增加时，运算时间显著增加。以表1描述的原始项目集为例，TIDItemsT1I1,I3,I4T2I2,I3,I5T3I1,I2,I3,I5T4I2,I5表1：原始事务集现考虑生成频繁项的过程，首先搜索原始数据库，得到1-项集I1,I2,I3,I4,I5和支持度，修剪支持度小于最小支持度的项目，L1，如图2所示。图2：频繁项集L1 图3：频繁集L2有L1产生2-项集，继续计算支持度修剪产生图3描述的频繁2-项集，继续产生L3l1,l2,l3。这样频繁项集就产生了，后面可以计算关联规则了，这个部分就是简单的计算，这里就不介绍了。从中可见，总共执行三轮，数据库就

15、扫描了三次。对于数据量比较小来讲，这个时间可以忽略，但是对于大数据来件，就要尽可能考虑少扫描数据库。因此对频繁项目集的搜索次数的改进，有了不同的算法。3 基于闭项目集理论对Apriori算法的改进1999 年，Pasquier 等人提出闭合项目集挖掘理论，并给出了基于这种理论的Close 算法。他们给出了闭合项目集的概念，并讨论了这个闭合项目集格空间上的基本操作算子。3.1 项目集理论的基本概念闭项集Close算法改进基于的基本原理： 一个频繁闭合项目集的所有闭合子集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。先增加几个基本概念：定义3.1：子集和超集：对于两个集合A与B，

16、如果集合A的任何一个元素都是集合B的元素，而集合B中至少有一个元素不属于集合A，则称集合A是集合B的真子集，集合B为集合A的超集。定义3.2：最大频繁项集，如果频繁项集L 的所有超集都是非频繁项集, 那么称L 为最大频繁项集。定义3.3：闭项集和频繁闭项集，所谓闭项集，就是指一个项集X，它的直接超集的支持度计数都不等于它本身的支持度计数。如果闭项集同时是频繁的，也就是它的支持度大于等于最小支持度阈值，那它就称为频繁闭项集。例如，有交易数据库:TIDitem1abc2abcd3bce4acde5de表2：闭项集实例事务集 因为项集b,c出现在TID为1,2,3的事务中，所以b,c的支持度计数为3

17、。而b,c的直接超集： a,b,c,a,b,c,d的支持度计数分别为2,1，都不等于b,c的支持度计数3，所以b,c为闭项集，如果支持度阈值为40%，则b,c也为闭频繁项集。项集a,b出现在TID为1,2的事务中，其支持度计数为2。而它的直接超集a,b,c支持度计数也为2，所以a,b不是闭项集。3.2 close算法改进的过程Close 算法是对Apriori 的改进算法。在Close 算法中，也使用了迭代的方法：利用频繁闭合i- 项目集记为FCi，生成频繁闭合（i+1）- 项目集，记为FCi+1(i1)。首先找出候选1- 项目集，记为FCC1，通过扫描数据库找到它的闭合以及支持度，得到候选闭

18、合项目集。然后对其中的每个候选闭合项进行修剪，如果支持度不小于最小支持度，则加入到频繁闭合项目集FC1 中。再将它与自身连接，已得到候选频繁闭合2-项目集FCC2，再经过修剪得出FC2，再用FC2 推出FC3，如此继续下去，直到有某个值r 使得候选频繁闭合r- 项目集FCCr 为空，这时算法结束5。3.3 close算法实例分析 可见算法的具体实现步骤总结如下：（1）查找频繁闭项集 ；（2) 生成频繁项目集；（3）生成关联规则； 利用频繁闭合i-项集为FCi，生成闭合（i+1）-项集，也就是 FCi+1。基本过程大致描述为：首先找到候选1-项集，记为:FCC1，扫描数据库找到它的闭合以及sup

19、port，得到候选闭合项集，修剪以后，得到FC1，与自身连接以后，得到FCC2，继续得到FC2继续下去，知道FCCr为空，算法结束，得到频繁闭合项集。以图4标明的事务数据集为例：其中最小支持度设为minsupport=2，TIDItemset123456789A，B，EB，DB，CA，B，DA，CB，CA，CA，B，C，EA，B，C表3：闭项目事务数据集表（1）计算FCC1各个产生式的闭合与支持度。首先得到FCC1产生式：A、B、C、D、E。计算闭合集。首先计算A闭合集，具体过程，考虑A在事务集合中出现的项数为：1、4、5、7、8、9，因此考虑这些项闭合集的产生，步骤如下：1：ABE 和A的闭

20、合为：ABE4：现有A的闭合ABE和ABD取交集得到A闭合：AB；5：现有A的闭合AB和AC取交集得到A的闭合：A；7：现有A的闭合A和AC取交集得到A的闭合：A；8：现有A的闭合A和ABCE取交集得到A的闭合：A；9：现有A的闭合A和ABC取交集得到A的闭合：A。和分析A的闭合一样，同理分析B，C,D,E的闭合，分析以后的闭合集见表4。产生项闭合集支持度AA9BB7CC6DBD2EABE2表4：闭合集（2）进行修剪，减掉支持度小于2的，得到FC1，本例和FCC1相同。（3）利用FC1 的产生项生成FCC2。生成2-项目集，和apriori算法一样，然后将FC1中是FCC2的某个候选项选择出来

21、，记为Sp，如果FCC1的这一项是Sp字母的闭合项则删除，得到FCC2 = AB,AC,AD,BC,BD,CD,CE,DE。（4）计算各式闭合度同时修剪，得到FC2= =AB,AC,BC,BD(5)继续产生FCC3=ABC，支持度为2.修剪以后得到FC3=ABC. (6)生成FCC4，为空算法结束。得到所有不重复的闭合FC。FC=A,B,ABE,BD,C,AB,AC,BC,ABC. (7)所有闭合集统计：L3=ABC,ABE,L2=AB,AC,BC,BD,L1=A,B,C。最多的个数为3。L3频繁项分解， 先分解ABC为AB,AC,BC全部在FC中，不用添加。然后分解ABE为AB,AE,BE,

22、将AE,BE加入L2。得到L2为=BD,AB,AC,BC,AE,BEL2项分解：A,B,C,D,E，加入L1。得到的L1为=A,B,C,D,E,最终L3=ABC,ABE;3.4 close算法和Apriori算法比较在Apriori 算法中，Ck 中的每个元素需要在事务数据库中进行验证（计算支持度）来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的事务数据库，即如果频繁项目集最多包含c 个项，那么就需要扫描事务数据库c+1 遍，这需要很大的I/O 负载。虽然之后的算法进行了优化，但是，如果数据库很大，算法的效率还是很低的。因此采用闭合的方法，可以在一定程度

23、上减少数据库扫描的次数。使用频繁闭合项目集发现频繁集，可以提高发现关联规则的效率。实际上既是频繁的又是闭合的项目集的比例比频繁项目集的比例要小的多，而且随着数据库事务数的增加和项的大小的增加，项目集格增长很快。使用闭合项目集格可以通过减少查找空间、减少了数据库扫描次数，来改进Apriori 方法。5 结束语Apriori算法采用自底向上的、宽度搜索的方式，它枚举出所有的频集。当事务数据库比较稀疏时(例如购物篮数据)，由这类数据得到的频集模式通常较短，Apriori算法以及类似算法都能获得良好的性能。但是，当这一类算法遇到稠密数据(例如电信、人口普查等等)，由于大量长模式的出现，这类算法的性能急

24、剧下降。Close算法与传统的Apriori 算法相比，不同点在于该算法不仅生成了频繁项集，同时也生成了频繁闭包项集。而闭包项集是去掉冗余规则，生成关联规则最小覆盖的一个基础，是今后研究生成无冗余有效规则的良好开端。加速了频繁项目集的生成，减少了数据库的扫描次数。参考文献1李新征，一种新的高效Apriori算法微计算机信息，2006(09)：193-1942徐勇，周森鑫一种改进的关联规则挖掘方法研究计算机技术与发展，2006，03：77-793 毛国君段立娟王实石云，数据挖掘原理与算法M. 北京：清华大学出版社，2005，64- 109.4 杨红菊，梁吉业.一种挖掘频繁项集和频繁闭包项集的算法J.计算机工程与应用，2004，(13):176- 178.6 卿家康.制定期刊市场规则 整顿期刊市场秩序J.编辑学刊，1997，(2):21- 25.7 李力，翟东海，靳蕃.基于图的频繁闭项集挖掘算法J.西南交通大学学报，2004，(3):385- 389.8 邵峰晶，于忠清.数据挖掘原理与算法M. 北京：中国水利出版社，2003，91- 126.9 骆嘉伟，彭蔓蔓，陈景燕，王思玮.基于消费行为的 Apriori 算法研究J.计算机工程，2003，（5）：72- 73.