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

首都师范大学信息工程学院2013-2014学年第二学期2013硕士研究生 计算机应用技术 专业期末考试试卷课程名称 数据挖掘 考试形式 撰写学术论文 考试时间 2014.4.21考试对象 2013级研究生 姓名 李燕 学号 2131002053任课教师利民 成绩基于闭项目集的Apriori算法李燕（首都师范大学信息工程学院，北京 100089）摘 要：本文针对Apriori算法中需要不断扫描原始事务项集问题，介绍了在某些情况下，可以大大减少扫描次数的close算法，同时对此算法给出了改进的想法和简单实现。关键字：关联规则 Apriori算法 频繁闭项集、close算法An improved Apriori algorithmAbstract: This article in view of the Apriori algorithm need to constantly scan the original transaction itemsets，Introduced in some cases, can greatly reduce the number of scanning the close of the algorithm, at the same time, this algorithm gives the improvement ideas and simple implementation.Keywords: Association Rules Apriori Algorithm Frequent Closed Item Set close Algorithm0前言 信息技术的不断推广应用，将企业带入了一个信息爆炸的时代。如何充分利用这些数据信息为企业决策者提供决策支持成为一个十分迫切的又棘手的问题，人们除了利用现有的关系数据库标准查询语句得到一般的直观的信息以外，必须挖掘其内含的、未知的却又实际存在的数据关系。著名的Apriori算法是一种挖掘关联规则的算法。本文利用事务集闭项集来在一定程度上减少数据事务集的扫描次数来减少Apriori算法的瓶颈。这有利于提高挖掘的速度和减少数据库的I/O操作时间的开销。1 关联规则挖掘理论和基本概念 数据挖掘(Data Mining)利用统计与人工智能的算法,从庞大的企业历史资料中,找出隐藏的规律并建立准确的模型,用以预测未来。其中关联规则(Association Rules) 的挖掘是数据挖掘中的一个重要问题。关联规则(Assocation Rule)最由Agarwal等提出，用于交易数据库。关联规则是数据挖掘领域的一个热点，它发现交易数据库中不同商品(项)之间的联系，即关联规则。关联规则一般用以发现交易数据库中不同商品(项)之间的联系,用这些规则找出顾客的购买行为模式,比如购买了某一种商品对购买其他商品的影响,这种规则可以应用于超市商品货架设计、货物摆放以及根据购买模式对用户进行分类等。进而引伸至寻找一个变量间不同选择之间的关系,或寻找不同变量间的关系。关联规则中的基本概念主要包括：定义1.1：k-项集一个商品或者一个属性称为一个项目。多个项目的集合称为项集。设i为数据库D中全体项目的集合，集合x=il， i2， ， ik(xi且IXI=k)，称为k-项集。定义1.2：事务一条事务，或者说一条记录，是形如tid，X)的二元组，其中tid称为事务标识符，它唯一标识该条记录，X为项目集。要挖掘的数据集或者数据库D是N条事务的集合，一条事务也称为一条记录，N为数据集D的记录总数。若事务t包含项目集X中的所有项目，则称事务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：关联规则关联规则是形如X=Y的蕴涵式，X称为关联规则的前件或前提，Y称为关联规则的后件或结论。项集XUY的支持度称为关联规则的支持度。定义1.6: 置信度关联规则X=Y的置信度。确定Y在包含X的事务中出现的频繁程度。confidence(X=Y)=support(XY)support(X)100%支持度和置信度是描述关联规则的两个重要概念，前者用于衡量关联规则在整个数据集中的统计重要性，后者用于衡量关联规则的可信程度。一般来说，只有支持度和置信度均较高的关联规则才可能是用户感兴趣、有用的关联规则。Agrawal等人建立了用于事务数据库挖掘的项集格空间理论。这个理论核心的原理是：频繁项目集的子集是频繁项目集；非频繁项目集的超集是非频繁项集。这个原理一直作为经典的数据挖掘理论被应用。定理1.1：如果项目集X是频繁项目集，那么它的所有非空子集都是频繁项目集。定理1.2：如果项目集X是非频繁项目集，那么它的所有超集都是非频繁项目集。关联规则发现：对于给定的事务集D，关联规则发现是指从D中挖掘出支持度和置信度分别大于等于minsup和minconf的所有规则，其中minsup和minconf是对应的支持度和置信度阈值。2 经典关联规则挖掘算法一种原始的关联规则挖掘方法是：计算所有规则的支持度和置信度，再删去支持度或置信度不满足阈值的规则。因为从数据集中提取的规则的数目是指数级，这种方法的计算任务繁重，过高的代价使得它在很多场合下变得不可行。研究者通过对关联规则挖掘的研究发现，很多规则是没有必要计算的。只计算可能满足要求的规则，可以节省大量的时间。目前通常采用一种策略是，将关联规则挖掘任务分解为如下两个主要的子任务：(1)生成频繁项集，其任务是生成所有满足最小支持度阈值的项集，这些项集被称作频繁项集(Frequent ltemset)；通常用格结构(Lattice structure)来表示所有可能的项集。一个包含k个项的项集最多可能产生(2。-1)个非空频繁项集。由于在许多实际应用中k的值可能非常大，需要查找的项集搜索空问可能是指数规模的。一种原始的频繁项集生成方法是确定格结构中每个候选项集(Candidate Itemset)的支持度计数。为了完成这一任务，必须将每个候选项集与每个事务进行比较。如果候选项集包含在事务中，则给候选项集的支持度计数加1。这种方法的开销可能非常大。(2)生成规则，其任务是从上一步生成的频繁项集中提取所有高置信度的规则。频繁项集是满足支持度阈值的项集，对这些项集再增加置信度的要求，即可从数据集中挖掘出满足要求的关联规则。关联规则可以这样来从频繁项集中提取；将一个频繁项集Y划分成两个非空的子集X和Y-X，所有满足置信度阈值的规则X=Y-X即是所要生成的规则。因为这些规则都是由频繁项集产生的，所以它们必然满足支持度阈值。排除前件或后件为空集的规则，每个频繁k项集能够产生多达2k一1个关联规则。计算关联规则的置信度并不需要再次扫描事务数据集。例如对于规则臼，A,B= C，它是由频繁项集x=A，B，C)产生的。该规则的置信度为Count fA，B，CCountA，B。因为A，B，C)是频繁的，项集A，B)也一定是频繁的。由于这两个项集的支持度计数已经在频繁项集产生时得到，因此不必再扫描整个数据集。相对频繁项集生成而言，规则的生成较为简单和直观。通常，生成频繁项集所需的计算开销远大于生成规则所需的计算开销。2.1 Apriori算法简介Apriori算法是现今研究关联规则中最具代表性的方法，虽然之后有许多算法被提出，但皆是依据此架构做改进或延伸，Apriori算法利用层次顺序搜索的循环方法(又称作逐层搜索的迭代方法)来完成频繁项集的挖掘工作，同时利用Apriori定理来压缩搜索空间，提高频繁项集产生的效率。Apriori定理：频繁项集的所有非空子集也一定是频繁的。频繁项集也称作是向下封闭的，因为如果一个项集满足最小支持度的要求，其所有子集也满足这一要求。对于Apriori算法中的数据表示，采用水平数据表示法，在水平数据表示中，数据库的一条事务由事务标识符(TID)和项目组成。事务由TID唯一标识，一条事务可以包含一个项目或多个项目。图表1实例形象说明了这种表示方案。 图1：Apriori水平数据表示在该算法中支持度的计算是在扫描数据库的前提下，不断的计数进行的。扫描数据库一次，对每一条事务，若事务包含项目，则该项目的支持度计数增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 中， Ck 中的每个元素需在交易数据库中进行验证来决定其是否加入Lk， 这里的验证过程是影响算法性能的一个瓶颈。每求一个Lk 需要对数据库扫描一遍。为了提高生成频繁项集的效率， 用到了数据项集的一个基本性质。根据关联规则的性1以及推论可知， 一个项集是频繁项集当且仅当它的所有子集是频繁集， 那么如果Ck 中某个候选k- 项集有一个(k- 1)- 项子集不属于Lk-1， 则这个候选k-项集可以被修剪，不再被考虑，这个修剪过程可以降低计算候选集支持度的代价。具体算法，首先获得最小支持度，以及全体事务集。具体步骤如下:1扫描事务数据库TDB一次，找到Ll频繁1-项集的集合；2For(k=2；Lk-1；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 L1 L2 Lk2.3 实例分析Apriori算法瓶颈基于频繁项集的Apriori算法采用了逐层搜索的迭代的方法，算法简单明了，没有复杂的理论推导，也易于实现。但是它存在一些难以克服的缺陷：(1)对数据库的扫描次数过多。在Apriori算法的扫描中，每生成一个候选项集，都要对数据库进行一次全面的搜索。如果要生成最大长度为K的频繁项集，那么就要对数据库进行K次扫描。当数据库中存放大量的事务数据时，在有限的内存容量下，系统I0负载相当大，每次扫描数据库的时间就会很长，这样效率就非常低。(2)Apriori算法可能产生大量的候选项集。在规模较大的情况下，Apriori算法需要产生大量的候选项集。(3)在频繁项集长度变大的情况下，运算时问显著增加。当频繁项集长度变大时，支持该频繁项集的事务会减少，从理论上讲，计算其支持度所需要的时间不会明显增加，但Apriori算法仍然是在原来事务数据库中来计算频繁项集的支持度，由于每个频繁项集的项目变多了，所以在确定每个频繁项集是否被事务支持的开销也增大了，而且事务没有减少，因此频繁项集长度增加时，运算时间显著增加。以表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。这样频繁项集就产生了，后面可以计算关联规则了，这个部分就是简单的计算，这里就不介绍了。从中可见，总共执行三轮，数据库就扫描了三次。对于数据量比较小来讲，这个时间可以忽略，但是对于大数据来件，就要尽可能考虑少扫描数据库。因此对频繁项目集的搜索次数的改进，有了不同的算法。3 基于闭项目集理论对Apriori算法的改进1999 年，Pasquier 等人提出闭合项目集挖掘理论，并给出了基于这种理论的Close 算法。他们给出了闭合项目集的概念，并讨论了这个闭合项目集格空间上的基本操作算子。3.1 项目集理论的基本概念闭项集Close算法改进基于的基本原理：一个频繁闭合项目集的所有闭合子集一定是频繁的；一个非频繁闭合项目集的所有闭合超集一定是非频繁的。先增加几个基本概念：定义3.1：子集和超集：对于两个集合A与B，如果集合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。而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，通过扫描数据库找到它的闭合以及支持度，得到候选闭合项目集。然后对其中的每个候选闭合项进行修剪，如果支持度不小于最小支持度，则加入到频繁闭合项目集FC1 中。再将它与自身连接，已得到候选频繁闭合2-项目集FCC2，再经过修剪得出FC2，再用FC2 推出FC3，如此继续下去，直到有某个值r 使得候选频繁闭合r- 项目集FCCr 为空，这时算法结束5。3.3 close算法实例分析可见算法的具体实现步骤总结如下：（1）查找频繁闭项集；（2) 生成频繁项目集；（3）生成关联规则；利用频繁闭合i-项集为FCi，生成闭合（i+1）-项集，也就是 FCi+1。基本过程大致描述为：首先找到候选1-项集，记为:FCC1，扫描数据库找到它的闭合以及support，得到候选闭合项集，修剪以后，得到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的闭合为：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的某个候选项选择出来，记为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,将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 负载。虽然之后的算法进行了优化，但是，如果数据库很大，算法的效率还是很低的。因此采用闭合的方法，可以在一定程度