挖掘关联规则的快速算法(apriori算法 外文翻译)

挖掘关联规则的快速算法（英）RakeshAgrawalRamakrishnanSrikantIBM阿尔马丁研究中心圣塔克莱拉市650亨利道95120证摘要：针对找出销售交易中大量数据库里项目之间的关联规则问题，我们提出两种与已知算法完全不同的新的算法来解决此问题.观察数据表明：这两种算法在从小问题的三个到大问题的多个度量的因子上都优于先前的算法.根据这两种算法的特点，我们还指出如何将它们合并才是一个最佳的混合算法，称为AprioriHybrid算法.按比例增大实验证明AprioriHybrid算法是随着交易数量按线性比例递增的，且它在交易大小和数据库中的项目上也有良好的递推性.1引言条形码技术的广泛应用使得零售商在收集和存储大量商品的价格数据时十分方便，简称为货篮数据.一条这样的数据记录通常都包括某个顾客的交易日期，交易中所购的物品项目.成功的组织者视这种数据库为贸易市场基础结构的重要组成部分.他们专注于研究用数据库技术来推动市场信息化过程，这样市场经营者就可以有能力发展及实施为顾客制定购买产品的方案和策略[6].有关在货篮数据上挖掘关联规则的问题在[4]中已作介绍.举个例子：可能有98%的顾客在购买轮胎和汽车配件的同时接受了有关汽车的服务.找出所有这样的规则对于促进市场营销和提高顾客购买力是非常有价值的.另外还有价目表设计，商品上架设计，进货安排，根据购买行为模式对顾客进行分类.但这些应用中的数据库都是极其庞大的，因此，寻找一种快速的算法来完成此项任务是我们的当务之急.以下是关于这个问题[4]的一个表述：令I={12,,,miii}是m个不同项目的集合，给定一个事务数据库D,其中每一个事务T是I中一些项目的集合，且都与一个唯一的标识符TID相联.如果对于I中的一个子集X,有XT,我们就说事务T包含X.关联规则是形如威斯康辛大学，计算机系，麦迪逊全部或部分材料允许被免费拷贝，这些拷贝不是为直接的商业优势而制作的，VLDB的拷贝权是由VLDBE授予的.另外，拷贝或重新出版还需要金额和VLDBE的允许.第20届极大数据库程序会议智利圣地亚哥，19941YX的蕴含式，其中IYX,,且YX=.如果事务数据库D中有c%的事务包含X的同时也包含Y，则称关联规则YX的置信度为c%.如果事务数据库D中，有s%的事务包含了YX，则称关联规则YX具有支持度s%.这个规则在我们讨论多项集的问题时比[4]中的阐述要简单很多.给定一个事务集D，挖掘关联规则的问题就是产生支持度和置信度分别大于用户给定的最小支持度和最小置信度的关联规则.我们对事务集D的内容属性方面不加以讨论，比如说，D可以是一份数据文件，也可以是一张关系表，或者是一个关联表达式的结果.找出所有关联规则中的算法，我们称文章[4]提出的为AIS算法，文章[13]提出的为SETM算法.在本文中，我们介绍两种新的算法：Apriori和AprioriTid算法，基本上与先前的算法不同.我们将用实验结果证明这两种算法优于先前算法.它们之间的差距主要体现在问题大小的增大及问题范围从小问题的三个到大问题的多个度量的因子上变化.接着我们讨论由Apriori和AprioriTid算法合并而成的混合算法（AprioriHybrid算法）是如何的优异.实验证明AprioriHybrid算法具有良好的递推性能，开启了挖掘关联规则在数据库中应用的可行性.找出关联规则属于数据库挖掘范畴[3,12]，也称为数据库中的知识发现[21].类似地，但不直接可应用的工作还包括分类规则的介绍[8,11,22]，因果关联规则的发现[19]，学习逻辑定义[18]，函数的数据拟合[15]以及簇[9,10].非公开性的有关机器学习文献的作品是在[20]中的KID3算法.如果应用在查找所有关联规则问题上，这个算法在与假定关联项的数目一样多的数据上进行运算时，运算量非常大.最近在数据库上的研究工作是由数据出发来定义关联函数[16].函数关联规则需要十分严格的条件.因此，定义一种函数规则为AX后,在[16]中描述的算法若从规则AYX来考虑，就无法推出.我们考虑的这些关联规则要符合实际性质.规则AX的存在并不意味着AYX也成立，因为后者可能不具备最小支持度.同样的，规则YX和ZY的存在也不意味着ZX成立，因为后者可能也不具备最小置信度.曾有一个关于测定“有用性”或“有趣性”规则的实验[20].无论是有用的还是有趣的，通常都是依赖于运用的.它需要圈内人员去提供材料，让所有人知道规则的发现过程以及让规则清晰明了，如[7,14].在本文中，对这些观点我们不加以讨论，除了指出它们在规则发现体系中的必要特征，可以利用我们的算法作为发现过程中的引擎.1.1问题剖析和论文概要找出所有关联规则的问题可分解为以下两个小问题：21.找出事务中所有满足用户指定最小支持度的项集，每个项集的支持度就是包含项集的事务数.具有最小支持度的项集称为频繁项集，否则称为非频繁项集.在第二章，我们给出新的算法:Apriori和AprioriTid算法来解决这个问题.2.利用频繁项集来产生所需要的规则，这里有一种直接的算法.对于每个频繁项集l，找出l中所有非空子集a，如果la支持度最小置信度支持度就生成关联规则a(l-a).我们需要考虑所有l的子集产生的多种规则的结果.由于篇幅关系，这里对此问题不做深入探讨，但读者可通过阅读[5]来获取一种快速算法.第三章，我们就提出的Apriori和AprioriTid算法与AIS算法[4]和SETM算法[13]作出比较.为了使论文更完善，在这个章节中还对AIS和SETM算法做了简要介绍.同时我们还阐述了Apriori和AprioriTid算法如何合并形成AprioriHybrid算法，并且演示了这种算法的递推性.在第四章，我们总结指出许多相关联的开放性问题.2产生频繁项集产生频繁项集需要在数据上作多步运算.第一步，需要计算出每个项目的支持度，从而确定哪些是频繁的，换言之，就是具有最小支持度.在后续的步骤中，都以前一步生成的频繁项集为基础，产生新的候选项集，即潜在的频繁项集，再扫描数据库计算候选项集的支持度，最后确定哪个些候选项集能真正成为频繁项集.重复上述过程，直到没有新的频繁项集产生为止.Apriori和AprioriTid算法与AIS算法[4]和SETM算法[13]完全不同之处就在于候选项集的产生方面，前者一步到位而后者在数据扫描时临时产生.在AIS和SETM算法中，扫描一个数据时候选项集呈飞过式产生.特别地，浏览一个事务之后，事务中哪一个是前一步生成的频繁项集是确定的.新的候选项集是将事务中原有的项扩展到这些频繁项集中产生的.然而，就我们看来，明显的缺陷就是这个结果不一定会产生，而且对候选项集计算的次数太多导致效率低下.而Apriori和AprioriTid算法只需通过先前事务中前一步找出的频繁项集来产生候选项集，而无需考虑数据库中所有事务.其基本的思想是任何频繁项集的子集也一定是频繁项集.因此，就可以通过链接频繁(k-1)-项集，删除其中含有非频繁子集的项集来产生候选k-项集.这个过程使得更少的候选项集产生.此外，AprioriTid算法还有自己的特点，数据库仅在第一次统计候选项集的支持度时被扫描一次.更确切地说，把前一步中得到的候选项集的代码用到这个项目中，在接下来的步骤3中，代码的大小会变得比数据库小，因此，节省了很多扫描过程.在描述此算法时我们会对细节的关键点作出具体解释.符号表示假设每个事务中项目都按字典序排列，那么就可以直接采用这些算法来保持数据库D中的运算正常化，且数据库中每条记录显示为TID，项目，其中TID是事务的标志符.我们把一个项集中所含项的个数称为项集的长度，长度为k的项集称为k-项集.项集中各项按字典序排列，我们用符号c[1]·c[2]·…·c[k]表示一个k-项集，其中c包含项目c[1],c[2],…,c[k]，且c[1]＜c[2]＜…＜c[k].如果cXY，且Y为m-项集，则Y为X的m-项扩展集.关联每个项集的是一个用来储存这个项集支持度的计算领域，其初始值为0.对算法中使用的符号，我们在表1中作了总结.集合kC在AprioriTid算法中会应用到，我们在描述这个算法时再对它作进一步的探讨.表1：符号k-项集含有k个项的项集kL频繁k-项集（具有最小支持度）集合中的每个元素含有两个计算域：i)项集的计算；ii)支持度的计算kC候选k-项集（潜在的频繁项集）集合中的每个元素含有两个计算域：i)项集的计算；ii)支持度的计算kC当生成的事务TID与候选集保持关联时的候选k-项集2.1Apriori算法图1给出了Apriori算法的详细过程.算法的第一步就是简单地计算出决定生成频繁1-项集的项目.接下来直到第k步，可分成两个阶段：首先，在第k-1步中产生频繁项集1kL，通过调用Apriori-gen函数产生候选项集kC；其次，对数据库进行扫描并计算候选项集kC的支持度.为了使计算更快速，我们需要确定候选项集kC包含于给定的事务t中.2.1.2章节描述的Subset函数就运用于这个目的.参考[5]中讨论的缓冲管理.1）1L{large1-itemsets};2)for(k2;1kL;k)dobegin3)kCapriori-gen(1kL);//新的候选项集44）foralltransactionst∈Ddobegin5)tCsubset(kC,t);//所有t包含的候选项集6）forallcandidatesc∈tCdo7)c.count;8)end9)kL{c∈kC∣c.countminsup}10)end11)AnswerkkL图1：Apriori算法2.1.1Apriori候选集的产生求得所有频繁(k-1)-项集1kL是通过函数Apriori-gen实现的，该函数返回的是所有频繁k-项集的超集，其计算过程如下：第一步，链接，把1kL与自己链接：insertintokCselect1.pitem,2.pitem,…,1.kpitem,1.kqitemfrom1kLp,1kLqWhere1.pitem=1.qitem,…,2.kpitem=2.kqitem,1.kpitem1.kqitem;第二步，剪枝，如果项集kcC但c中的(k-1)-项子集不属于1kL，则c:forallitemsetsc∈kCdoforall(k-1)-subsetssofcdoif(s1kL)thendeletecfromkC;举例：令3L={{123}，{124}，{134}，{135}，{234}}.通过链接步，4C={{1234}，{1345}}，剪枝步会删除{1345}，因为{145}不属于3L，所以最后4C={1234}.把这里产生候选集的方法与AIS和SETM算法的相比较,方法的第k步都是扫描数据库t，5从而确定1kL中的哪个频繁项集当前属于t.这里的每个频繁项集l是由t中原有频繁的项一起扩展而成的，且这些项目在按字典序排列后会排在l中原有的项目之后.继续上面的例子，考虑事务{12345}，第四步，AIS和SETM算法会通过扩展频繁项集{123}来产生两个候选集{1234}，{1235}.类似地，另外的三个候选项集会通过扩展3L中的其他频繁项集来生成，导致第四步需要考虑5个候选项集.另一方面，Apriori算法只产生并计算一个项集{1345}，因为它包括一个Apriori，其余合并的项集不可能具有最小支持度.验证：我们需要证明kkCL.显然，任意频繁项集的子集都具有最小支持度，因此，如果把所有可能的项目扩展到1kL中的每个项集内，删除其中(k-1)-子集不属于1kL的项集，就得到kL中项集的超集.链接等同于用数据库中的每个项扩展1kL，再删除那些第(k-1)项不属于1kL的项集，得到(k-1)-项集.条件11..kkpitemqitem明确不产生重复项.因此，在链接步后就有kkCL.