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

      （英）Rakesh Agrawal    Ramakrishnan Srikant

IBM阿尔马丁研究中心

圣塔克莱拉市650亨利道 95120证

摘要：针对找出销售交易中大量数据库里项目之间的关联规则问题，我们提出两种与已知算法完全不同的新的算法来解决此问题. 观察数据表明：这两种算法在从小问题的三个到大问题的多个度量的因子上都优于先前的算法. 根据这两种算法的特点，我们还指出如何将它们合并才是一个最佳的混合算法，称为AprioriHybrid算法. 按比例增大实验证明AprioriHybrid算法是随着交易数量按线性比例递增的，且它在交易大小和数据库中的项目上也有良好的递推性.

1引言

条形码技术的广泛应用使得零售商在收集和存储大量商品的价格数据时十分方便，简称为货篮数据. 一条这样的数据记录通常都包括某个顾客的交易日期，交易中所购的物品项目. 成功的组织者视这种数据库为贸易市场基础结构的重要组成部分. 他们专注于研究用数据库技术来推动市场信息化过程，这样市场经营者就可以有能力发展及实施为顾客制定购买产品的方案和策略[6].

有关在货篮数据上挖掘关联规则的问题在[4]中已作介绍. 举个例子：可能有98%的顾客在购买轮胎和汽车配件的同时接受了有关汽车的服务. 找出所有这样的规则对于促进市场营销和提高顾客购买力是非常有价值的. 另外还有价目表设计，商品上架设计，进货安排，根据购买行为模式对顾客进行分类. 但这些应用中的数据库都是极其庞大的，因此，寻找一种快速的算法来完成此项任务是我们的当务之急.

以下是关于这个问题[4]的一个表述：令={}是个不同项目的集合，给定一个事务数据库,其中每一个事务是中一些项目的集合，且都与一个唯一的标识符相联. 如果对于中的一个子集,有,我们就说事务包含. 关联规则是形如的蕴含式，其中,且=. 如果事务数据库中有%的事务包含的同时也包含，则称关联规则的置信度为%. 如果事务数据库中，有%的事务包含了，则称关联规则具有支持度%. 这个规则在我们讨论多项集的问题时比[4]中的阐述要简单很多.

给定一个事务集，挖掘关联规则的问题就是产生支持度和置信度分别大于用户给定的最小支持度和最小置信度的关联规则. 我们对事务集的内容属性方面不加以讨论，比如说，可以是一份数据文件，也可以是一张关系表，或者是一个关联表达式的结果.

找出所有关联规则中的算法，我们称文章[4]提出的为AIS算法，文章[13]提出的为SETM算法. 在本文中，我们介绍两种新的算法：Apriori和AprioriTid算法，基本上与先前的算法不同. 我们将用实验结果证明这两种算法优于先前算法. 它们之间的差距主要体现在问题大小的增大及问题范围从小问题的三个到大问题的多个度量的因子上变化. 接着我们讨论由Apriori和AprioriTid算法合并而成的混合算法（AprioriHybrid算法）是如何的优异. 实验证明AprioriHybrid算法具有良好的递推性能，开启了挖掘关联规则在数据库中应用的可行性.

找出关联规则属于数据库挖掘范畴[3,12]，也称为数据库中的知识发现[21]. 类似地，但不直接可应用的工作还包括分类规则的介绍[8,11,22]，因果关联规则的发现[19]，学习逻辑定义[18]，函数的数据拟合[15]以及簇[9,10]. 非公开性的有关机器学习文献的作品是在[20]中的KID3算法. 如果应用在查找所有关联规则问题上，这个算法在与假定关联项的数目一样多的数据上进行运算时，运算量非常大. 最近在数据库上的研究工作是由数据出发来定义关联函数[16]. 函数关联规则需要十分严格的条件. 因此，定义一种函数规则为后,在[16]中描述的算法若从规则来考虑，就无法推出. 我们考虑的这些关联规则要符合实际性质. 规则的存在并不意味着也成立，因为后者可能不具备最小支持度. 同样的，规则和的存在也不意味着成立，因为后者可能也不具备最小置信度.

曾有一个关于测定“有用性”或“有趣性”规则的实验[20]. 无论是有用的还是有趣的，通常都是依赖于运用的. 它需要圈内人员去提供材料，让所有人知道规则的发现过程以及让规则清晰明了，如[7,14]. 在本文中，对这些观点我们不加以讨论，除了指出它们在规则发现体系中的必要特征，可以利用我们的算法作为发现过程中的引擎.

1.1问题剖析和论文概要

找出所有关联规则的问题可分解为以下两个小问题：

1.找出事务中所有满足用户指定最小支持度的项集，每个项集的支持度就是包含项集的事务数. 具有最小支持度的项集称为频繁项集，否则称为非频繁项集. 在第二章，我们给出新的算法:Apriori和AprioriTid算法来解决这个问题.

2.利用频繁项集来产生所需要的规则，这里有一种直接的算法. 对于每个频繁项集，找出中所有非空子集，如果就生成关联规则 (-). 我们需要考虑所有的子集产生的多种规则的结果. 由于篇幅关系，这里对此问题不做深入探讨，但读者可通过阅读[5]来获取一种快速算法.

第三章，我们就提出的Apriori和AprioriTid算法与AIS算法[4]和SETM算法[13]作出比较. 为了使论文更完善，在这个章节中还对AIS和SETM算法做了简要介绍. 同时我们还阐述了Apriori和AprioriTid算法如何合并形成AprioriHybrid算法，并且演示了这种算法的递推性. 在第四章，我们总结指出许多相关联的开放性问题.

2产生频繁项集

产生频繁项集需要在数据上作多步运算. 第一步，需要计算出每个项目的支持度，从而确定哪些是频繁的，换言之，就是具有最小支持度. 在后续的步骤中，都以前一步生成的频繁项集为基础，产生新的候选项集，即潜在的频繁项集，再扫描数据库计算候选项集的支持度，最后确定哪个些候选项集能真正成为频繁项集. 重复上述过程，直到没有新的频繁项集产生为止.

Apriori和AprioriTid算法与AIS算法[4]和SETM算法[13]完全不同之处就在于候选项集的产生方面，前者一步到位而后者在数据扫描时临时产生. 在AIS和SETM算法中，扫描一个数据时候选项集呈飞过式产生. 特别地，浏览一个事务之后，事务中哪一个是前一步生成的频繁项集是确定的. 新的候选项集是将事务中原有的项扩展到这些频繁项集中产生的. 然而，就我们看来，明显的缺陷就是这个结果不一定会产生，而且对候选项集计算的次数太多导致效率低下.

而Apriori和AprioriTid算法只需通过先前事务中前一步找出的频繁项集来产生候选项集，而无需考虑数据库中所有事务. 其基本的思想是任何频繁项集的子集也一定是频繁项集. 因此，就可以通过链接频繁(-1)-项集，删除其中含有非频繁子集的项集来产生候选-项集. 这个过程使得更少的候选项集产生.

此外，AprioriTid算法还有自己的特点，数据库仅在第一次统计候选项集的支持度时被扫描一次. 更确切地说，把前一步中得到的候选项集的代码用到这个项目中，在接下来的步骤中，代码的大小会变得比数据库小，因此，节省了很多扫描过程. 在描述此算法时我们会对细节的关键点作出具体解释.

符号表示 假设每个事务中项目都按字典序排列，那么就可以直接采用这些算法来保持数据库中的运算正常化，且数据库中每条记录显示为<，项目>，其中是事务的标志符.

我们把一个项集中所含项的个数称为项集的长度，长度为的项集称为-项集. 项集中各项按字典序排列，我们用符号[1]·[2]·…·[]表示一个-项集，其中包含项目[1], [2],…, []，且[1]＜[2]＜…＜[]. 如果，且为-项集，则为的-项扩展集. 关联每个项集的是一个用来储存这个项集支持度的计算领域，其初始值为0.

对算法中使用的符号，我们在表1中作了总结. 集合在AprioriTid算法中会应用到，我们在描述这个算法时再对它作进一步的探讨.

表1：符号

图1给出了Apriori算法的详细过程. 算法的第一步就是简单地计算出决定生成频繁1-项集的项目. 接下来直到第步，可分成两个阶段：首先，在第-1步中产生频繁项集，通过调用Apriori-gen函数产生候选项集；其次，对数据库进行扫描并计算候选项集的支持度. 为了使计算更快速，我们需要确定候选项集包含于给定的事务中. 2.1.2章节描述的Subset函数就运用于这个目的. 参考[5]中讨论的缓冲管理.

1）{large 1-itemsets};

2)  for (2; ;) do begin

3)   apriori-gen();//新的候选项集

4）  forall transactions∈do begin 

5)      subset(,);//所有包含的候选项集

6）     forall candidates∈do

7)          .count;

8)      end

9)      {∈∣.countminsup}

10)   end

11)Answer

图1：Apriori算法

2.1.1Apriori候选集的产生

求得所有频繁(-1)-项集是通过函数Apriori-gen实现的，该函数返回的是所有频繁-项集的超集，其计算过程如下：第一步，链接，把与自己链接：

insert  into 

select, ,…, , 

from ,  

Where =,…, =, <;

第二步，剪枝，如果项集但中的(-1)-项子集不属于，则:

forall itemsets∈do

 forall (-1)-subsets  of  do

   if () then

     delete  from;

举例：令={{1 2 3}，{1 2 4}，{1 3 4}，{1 3 5}，{2 3 4}}. 通过链接步， ={{1 2 3 4}，{1 3 4 5}}，剪枝步会删除{1 3 4 5}，因为{1 4 5}不属于，所以最后={1 2 3 4}.

把这里产生候选集的方法与AIS和SETM算法的相比较,方法的第步都是扫描数据库，从而确定中的哪个频繁项集当前属于. 这里的每个频繁项集是由中原有频繁的项一起扩展而成的，且这些项目在按字典序排列后会排在中原有的项目之后. 继续上面的例子，考虑事务{1 2 3 4 5}，第四步，AIS和SETM算法会通过扩展频繁项集{1 2 3}来产生两个候选集{1 2 3 4}，{1 2 3 5}. 类似地，另外的三个候选项集会通过扩展中的其他频繁项集来生成，导致第四步需要考虑5个候选项集. 另一方面，Apriori算法只产生并计算一个项集{1 3 4 5}，因为它包括一个Apriori，其余合并的项集不可能具有最小支持度.

验证：我们需要证明. 显然，任意频繁项集的子集都具有最小支持度，因此，如果把所有可能的项目扩展到中的每个项集内，删除其中(-1)-子集不属于的项集，就得到中项集的超集.

链接等同于用数据库中的每个项扩展，再删除那些第(-1)项不属于的项集，得到(-1)-项集. 条件明确不产生重复项. 因此，在链接步后就有.同理，虽然删除所有(-1)-项子集不属于的项集，但不会删除内的任何项集.

变形：在同一步中计算多种长度的候选集 在第步不仅能计算长度为的候选集，还能计算由产生的候选集等，这里由产生且. 当计算和保存额外的候选集到存储器上所花的时间比扫描数据库少时，这个变形就可在后续步骤中得到应用.

2.1.2Subset 函数

候选项集存储于hash-树中，hash-树的一个结点包含的不是一列项集（叶子结点）就是一个hash-表（内部结点）. 在内部结点中，hash-表的每个桶指向另一个结点. 规定hash-树树根的深度为1，深度为的内部结点指向深度为的结点，项集都存储在叶子结点中，当存储一个项集时，我们从树根出发，沿着树直到叶子. 在深度为的内部结点处确定沿着哪条树枝以运用hash-函数到达项集的第项. 所有的结点最初都是由叶子结点生成的，当叶子结点上项集的数目超出一个特定的范围时，叶子结点就转化为内部结点.

从根结点出发，运用Subset函数找出事务中所有的候选集. 如果在一个叶子结点中找到属于的项集，那么对他们在问题集中添加附注；如果通过对项进行hash后到达一个内部结点，那么对中之后的所有项进行hash，并用这个程序对桶内相对应的结点进行递归；此外，对于根结点中每个属于的项都要进行hash.

究竟为什么Subset函数会返回附注的所需集合呢，这里就要考虑根结点发生了什么变化. 对于事务中的任意项集，中的第一个项目肯定属于，在根部，通过对中的每个项目进行hash后，确定不是以中的项目为开始的项集. 同样对深度较低的结点运用这个结论，唯一附加的因素是，只要每个项集中的项目都按字典序排列着，如果仅对项进行hash后就到达当前的结点，那么只需考虑中排在之后的项.

2.2AprioriTid 算法

AprioriTid算法的过程如图2所示，同样在计算过程之前运用apriori-gen函数（2.1.1章节已给出）确定候选项集. 这个算法有意思的地方就是数据在第一步被扫描之后就不必再去计算它的支持度，而是被集合所取代. 集合中的每个元素都以<>形式存在，代表事务中潜在的频繁-项集，用表示整个集合. 当=1时，对应数据库，虽然概念上是每个项目被项集所取代；当>1时，由算法（第10步）产生，其中的元素与事务相对应，表示为<>. 如果一个事务不包含候选-项集，则不会含有这个事务的入口记录. 因此，中入口记录的数目可能会少于数据库中事务的数目，尤其对于数值较大的. 另外，对于数值较大的，每条入口记录可能会比相对应的事务要小，因为可能只有少数候选集属于事务. 然而对于数值较小的，每条入口记录可能会比相对应的事务要大，因为中的一条入口记录包括事务中所有的候选-项集.

在2.2.1章节，我们给出了数据结构用来运行这个算法. 参考[5]可得这个验证的证明过程以及对商业中缓冲管理的讨论.

1) {large 1-itemsets};

2) database;

3) for (2; ; ++) do begin

4)     apriori-gen();//新的候选项集

5)    ;

6)     forall entries  do begin

7)         //确定中的候选项集   //在事务中定义

           {set-of-itemsets

set-of-itemsets};

8)         forall candidates  do

9)              .coumt;

10)        if  then <, >

11)     end

12)     {countminsup}

13) end

14)  Answer

图2：AprioriTid算法

举例：考虑图3所示的数据库，假设事务的最小支持度为2，在第4步时对运用apriori-gen函数得到候选项集，从第6步到第10步，通过扫描的入口记录来计算中候选集的支持度并产生.中的第一条入口记录是{{1}{3}{4}}，与事务100相对应. 第7步中对应中的入口记录为{{1 3}}，因为{1 3}是的一个元素，且{{1 3}-{1}}与{{1 3}-{3}}都是set_of_itemsets中的元素.

对运用apriori-gen函数得到，对与作进一步计算得到，发现中缺少事务100和400的两条入口记录，因为他们不包含中的任何项集. 于是中的候选项集{2 3 5}就证明是最大的，且是唯一的元素. 当用生成时，结果为空，那么计算结束.

2.2.1数据结构

我们给每个候选项集分配一个唯一的号码，称为. 每个候选项集都按队列保存，则指针可通过来查找项集.中的每个元素都以形式存在且每个都存储在连续的结构中.

通过链接两个频繁(-1)-项集并运用Apriori-gen函数来产生一个候选-项集，我们为每个候选项集设定两个附加域：i)初始域；ii)扩展域. 初始域存储着产生的两个频繁(-1)-项集的，而扩展域存储着所有由的扩展而成的(+1)-项候选集的. 因此，如果候选集是由和产生的，那么初始域中存储着和的，同时，把的添加到的扩展域中.

图3：举例

现在我们来描述图2中的第7步在上述数据结构中是如何运用的. 调回中入口记录对应的set_of_itemsets域，给所有属于事务的(-1)-候选集，记这种候选集的扩展域为，所有候选-项集的集合构成扩展集,对每个中的，初始域给出产生的两个项集的. 如果这些项集目前有set_of_itemsets的入口记录，那么可以总结出在事务中，且把加入中.

3运行

为了评估这个方法在产生频繁项集时的有关运行情况，我们在IBM RS/6000 530H工作站作了几个关于测试CPU在33MHZ，MB的存储器和AIX3.2的操作系统下运行效率的实验. 数据存于AIX文档程序中，并保存在“2GB SCSI3.5”的驱动器上，计算测得连续流量的速度大约为2MB/s.

我们首先给出AIS和SETM算法的概要，再针对其算法，把Apriori和AprioriTid算法的运行过程与之相比较. 接着阐述如何对虚拟数据库进行求值，并且给出运算结果. 最后来总结把Apriori和AprioriTid算法合并形成AprioriHybrid算法在运行上的优点所在，并证明它的递推性.

3.1AIS算法

当扫描数据库时，生成候选项集且被快速统计；浏览一个事务后，确定前一步找出的哪个频繁项集包含于此事务中，新的候选项集可通过把事务中的项扩展到这些频繁项集中生成. 频繁项集仅由频繁的项目扩展而成，且这些项目在按字典序排列后会排在中原有的项目之后. 候选集由事务生成并加入到候选项集中继续下一步的运行，否则对应入口记录的条数将会增大，如果他们是之前的事务产生的话. 参考[4]可对AIS算法的细节有更深入的了解.

3.2SETM算法

SETM算法是在使用SQL时需要计算频繁项集的背景驱动下研究出来的. 与AIS算法一样，SETM算法也是快速扫描数据库中的事务产生候选项集，计算每个候选项集时也一致. 但是，使用标准的SQL语句运行此算法产生候选集时，把产生候选集与计算分离开来了. 它保存候选项集的复本并与连续结构中的事务相连接. 过程的最后一步，候选项集的支持度被确定下来并保存和收集在这个连续结构中.

SETM算法记录事务及其候选项集，为了避免需要运行子集，就利用这个信息确定事务中的频繁项集，是删除不具有最小支持度的候选集后得到的. 假设数据库保存在列表中，SETM算法在通过把存储在上，就能很容易找出事务中的频繁项集. 实际上，只需要在列表上对进行扫描一次就够了，产生候选集可通过有关合并-链接操作来完成.

这个方法的主要缺点是候选集的长度问题. 对于每个候选项集，候选集的入口记录与包含候选项集的事务数目一样多. 此外，当我们在最后一步决定计算候选项集的支持度时，处在错误的位置，且需要保存在项集上. 在计算与删除不具有最小支持度的非频繁候选项集后，在下一步被用于产生候选集之前需要在上作另外保存.

3.3构造虚拟数据

我们构造虚拟事务去评价算法在大量数据中的运行情况. 这些事务都是模仿零售商情况，模型即顾客趋向于购买的商品的集合. 每个集合都包含有潜在的频繁项集，比如一个集合包括床单、枕套、羊毛围巾和花边，有些人可能会购买其中的某几项如床单和枕套，有些人会只购买一项如床单. 一个事务也可包含一个或多个频繁项集，比如一个顾客在写下一件裙子和一件夹克衫订单的同时，又预订了床单和枕套. 这里裙子和夹克衫的组合构成另一个频繁项集. 事务的大小通常会蕴含着某种意义，且只有少数事务含有许多项；频繁项集的大小通常也会蕴含着某种含义，且只有少数频繁项集含有许多项.

建立一个数据集，构造数据过程中使用的参数如表2所示：

表2：参数

接着给事务分配项目，每个事务会分配到一个连续的潜在频繁项集. 如果当前的频繁项集不能放入事务中，就先置于一旁，当分配结束时再移入下一事务中.

频繁项集中的项是从中提取出来的，中项集的数目记为，它与潜在频繁项集的平均支持度的关系相反.中的项集由Poisson分布令平均数=计算项集的长度生成. 第一个项集内的项是随机提取产生的，为了模仿各频繁项集间常含有相同项目的现象，项集内的部分项取自连续着的前一项集. 我们用指数分布随机抽取平均数等于关联度的项，从而确定每个项集的重复部分，其余部分的项随机提取. 实验中的数据集，关联度为0.5；当在现实生活中运行多种实验，把关联度设为0.25或0.75时，对结果都不会造成影响.

中的每一个项都有自己的权值，与这个项集被选取的可能性相对应. 这个重量由指数分布通过单位计算所得并使之标准化，所以中所有项集的权值之和为1. 随后加入事务的项集是通过投一枚带权值的面硬币，权值偏向的一边就有可能被提取相关项集.

为了模仿频繁项集中的所有项不总是被一起购买现象，我们给中的每个项集一个误差度. 当事务中加入一个项集时，只要同样分布的任意数字（0~10）比小，就从项集中去掉一个项. 所以对一个长度为的项集，在事务中加入项需要次， -1项需要次， -2项需要次等. 一个项集的误差度是固定的，且由平均数为0.5，方差为0.1的正态分布取得.

我们构造数据集时，令=1000， =2000；给取3个数值分别为5，10，20；给取3个数值分别为2，4，6；事务的大小设为100,000，因为在3.4章节中，将证明STEM算法不能运行较大的数值. 但是对于按比例增大实验，我们可以构造大小为10,000,000的事务（838MB,T20）的数据集. 表3对数据集合中的参数设置作了概括，并给出和的数值，对于不同数值的，数据集合的长度都以Mb为单位且大致相等.

表3：参数设置

3.4对比运行情况

表3给出的6个虚拟数据集的运行时间如图4所示. 当最小支持度降低时，候选项集和频繁项集的数目都增多，因此所有算法的运行时间都延长.

观察图4可发现，对于SETM算法，我们只描绘出他对数据集T15.I2.D100K的运行时间曲线图，而对两个平均大小为10的事务的运行时间如表4所示. 不能描绘出与表4相对应的曲线图是因为它的运行时间跟其他算法的相比太长了；而对于另外3个大小为20的事务的数据集，它的运行时间太长而不得不对此运行宣告失败，虽然它的算法是正确的. 很明显，Apriori算法在大小确定的大数据集上运行比SETM算法优异.

图4：运行时间

表4：SETM算法的运行时间（s）

Apriori算法在不确定大小的问题上运行比AIS算法也优异，因素范围可从以2为最大的最小支持度到为低水平的支持度规定的大小要大的最小支持度. 但AIS算法比SETM算法相对来说要好. 在数据较小的问题上，AprioriTid算法与Apriori算法相当，可在数据较大的问题上，前者的运行速度要降低一半.

3.5分析对比运行情况

为了分析这些算法的运行过程，在数据集T10.I4.D100K中，令最小支持度为0.75%，在不同算法中，频繁及候选项集的数目在运算过程中的变化情况如图5所示，注意图中y轴的刻度标记.

图5：频繁及候选集的大小(T10.I4.D100K)

SETM算法的根本性问题就在于集合的长度问题，回顾的长度，它是由计算得到的. 因此，如果是候选项集支持度的平均数，则集合大约比对应集合大倍，除非问题的大小非常小，否则不得不被写入磁盘，且被存储两次，从而导致STEM算法运行缓慢，这也就解释了为什么表4中当大小为10的事务中数据集的最小支持度从1.5%变到1.0%时，SETM算法运行时间就剧增. 在[13]中为SETM算法设计的最大数据集递推性实验，数据仍然太小以致可以放入内存中，在运行时间上没有发生这种剧增情况. 值得注意的是，对于相同大小的最小支持度，候选项集的支持度根据事务的数目呈线性增长. 因此，当事务的数目增大时和的数值也在增大，即使的长度没有改变，的长度也呈线性增长. 故对于多个事务的数据集，SETM算法与其他算法的运行效率相比差距会更大.

AIS算法的问题在于它在过程中生成太多的候选集，但计算结果的数目却很小，导致计算效率低下. 虽然Apriori算法在第二步也计算出很多小集合（是的中间产物），但这些中间产物从第三步开始就明显减少了（如图5所示），之后计算得到的候选项集几乎都是频繁的.

AprioriTid算法与SETM算法具有相同的问题就是不能太大. 但最后AprioriTid得出的中的项目要比SETM算法的少很多；且它能利用单独的存储一个候选集，而无需与候选集中项的数目相等的来存储. 另外，与SETM算法不同的是，它不需要存储，因此就不会遭受SETM算法保存后的麻烦.

AprioriTid算法还有个很好的特点就是它利用来代替原始数据集，故在的大小变得比数据集小之后，运行效率非常高. 当可以放入内存中但频繁项集的分布队列很长时，我们会发现AprioriTid算法比Apriori算法的性能好；但当不能放入内存时，AprioriTid算法在运行时间就会剧增，像表4中大小为10的事务中数据库的最小支持度从0.75%到0.5%的时间变化，这时，它就不如Apriori算法了.

3.6AprioriHybrid算法

不一定在所有的数据上只能用同一种方法来计算，图6描绘的是在数据集T10.I4.D100K上，过程中使用AprioriTid和Apriori算法的运行时间情况. 在最初扫描时，Apriori算法比AprioriTid好，而后期扫描时，情况相反. 我们在其他数据库中也观察到类似情形，其主要原因如下：二者的候选集产生过程和要计算的项集是相同的；而后期过程中，候选项集的数目在减少（观察图5中两种算法的的大小），但Apriori算法始终要扫描整个数据库，而AprioriTid只需通过扫描来获得支持度数据，并且的大小会变得比数据库小. 当可以放入内存时，我们就不会遭遇它被写入磁盘的窘境.

图6：Apriori和AprioriTid算法每一步的运行时间

（T10.I4.D100K,最小支持度=0.75%）

基于这些观察，我们提出一种混合算法：在最初的数据读取中使用Apriori算法，当可以放入内存中时，就切换成AprioriTid，称这种算法为AprioriHybrid算法. 这里需要估计的大小. 在一次数据库扫描结束时，就可以得到中候选项集的数值. 当已经产生，则可以根据这来估计它的大小，为. 如果在本次扫描中小的可以放入内存，且频繁项集的数目比前期少，就转向为AprioriTid. 增加后面的条件是为了避免本次扫描的可以放入内存而下一次扫描的不能.

从Apriori到AprioriTid算法的转换也会有代价. 假设在第步结束时决定转换算法，那么在第（+1）步找到事务中的候选项集后，还要将它们的加入中（参考2.2章节描述的AprioriTid算法），因此在这步中与仅调用Apriori相比就多了一个额外的步骤，只有在第（+2）步才真正调用AprioriTid. 假如不存在频繁(+1)-项集或(+2)-候选集的话，将会花费了时间去转换却没有得到调用AprioriTid的任何好处.

图7所描绘的是对三个数据集合采用AprioriHybrid算法的运行情况. 几乎所有的例子都显示出AprioriHybrid优于Apriori算法，只有对于支持度为1.5%的数据集T10.I2.D100K，AprioriHybrid稍微逊色一些，由于算法的转换过程发生在最后一步，没有显出它的优势所致. 通常AprioriHybrid是否优于Apriori算法，主要依靠后期过程中的大小来决定. 若一直保持增大，直到快结束时才变小，则算法转换后仅在短时间内调用AprioriTid，速度还是会突然下降，所以AprioriHybrid算法就不能显示出它的优势. 这也是数据集T20.I6.D100K发生那种情况的原因. 但如果的大小在逐渐减小，AprioriTid算法在转换后还能运行一段时间的话，运行效率就会获得显著提高.

图7：AprioriHybrid的运行时间

3.7按比例增大实验

图8描绘的是随着事务大小从100,000增大到10,000,000时，AprioriHybrid算法的运行时间变化情况，联立(T5.I2)，(T10.I4)和(T20.I6)，分别取事务及项集大小的平均数，所有其他参数值同表3，大小为10,000,000的事务中数据集大小分别为239MB，439MB和838MB，设最小支持度为0.75%. 运行时间的规格主要体现在以下两个方面：第一幅图中大小为100,000的事务中数据集的运行时间和第二副图中大小为1,000,000的事务中数据集的运行时间. 如图所示，运行时间近似于线性增长.

图8：增大事务数目

接下来，我们来探究AprioriHybrid是如何随着项目的数量增多而按比例增长的. 把三个参数设置为T5.I2.D100K，T10.I4.D100K和T20.I6.D100K的数据集中项目的数量从1000增到10,000，其余参数值同表3，设最小支持度为0.75%. 运行实验后，得到的结果如图9所示，当项目的数量增多，项目的平均支持度下降，从而运行时间也减少. 把这个结果运用到稍微大点的项集时，运行的效率更高了.

最后，我们来研究当增大事务的平均大小时的按比例递增情况. 实验的目的是为了观察数据结构是如何随着事务大小改变的，不依赖于其他任何因素，如数据库本身大小，频繁项集的数目. 通过保持事务的平均大小及数目的结果不变从而保持数据库的本身大小基本不变，事务的数目范围而从平均大小为5的事务中含200,000个数据库到平均大小为50的事务中含20,000个数据库，固定最小支持度不变，随着事务大小的扩大，频繁项集的数目也按比例增长，只要事务中的项集存在的概率与事务大小大致成比例. 为此，以事务的数目固定项的最小支持度水平，结果如图10所示，图中的数字（如500）代表最小支持度. 由图可得，运行时间随着事务大小的增大而逐步地延长. 延长的主要原因是频繁项集的数目在随着事务大小增大而增大，尽管以事务的数目设定了项的最小支持度. 另外，在当前事务中找出候选集需要花一定的时间.

图9：增大项的数目                          图10：增大事务大小

4总结与工作前景

在本文中我们提出了两种新的算法：Apriori和AprioriTid算法，用于在事务中大量数据库的项目内找出所有有意义的关联规则；并且把这两种算法与先前已知的AIS和STEM算法进行比较，用实验结果证明这两种算法总是优于AIS和STEM算法. 它们之间的差距还会随着问题范围大小的增大而增大.

同时我们还展现了把这两种算法合并形成一种混合算法—AprioriHybrid算法的优点，在以后将会成为求解问题的精选算法. 按比例增大证明了AprioriHybrid随着事务数目的增长呈线性增长，另外，运行时间也会随着数据库中项目数量的增多而缩短. 如果事务大小的平均数在增大（保持数据库大小不变），运行时间也逐步地延长. 这些实验还证明了在实际应用程序中，对引入的大数据库采用AprioriHybrid算法的可行性.

本文中提到的算法已经在多个数据仓库中得到实行，包括AIX文本系统，DB2/MVS，及DB2/6000. 我们还把测试算法的结果与真实的顾客数据相比较. 具体过程可参考[5]. 以后，我们计划在以下范围内扩展对此算法的运用：

·项目的多重分类（组合）. 如洗碗机是一种厨房器具，又是一种电子设备等. 我们就可以根据这样的组合来找出关联规则.

·我们从未考虑进入事务的项目数量，而这个在很多应用程序上是十分有用的. 找出这样的规则就需要我们以后的工作发展.

本文中所得出的成果已经成为IBM Almaden Research Center的研究课题，主要探索数据库挖掘的多方面问题. 除了找出关联规则问题之外，还要调查在时间顺序上根据不同疑问和类似疑问来提高数据库的容量等. 我们相信数据库挖掘是数据库上的一块新的重要的应用领域，可以激起人们的好奇心结合商业利益来研究问题.

致谢：我们十分感谢Mike Carey具有洞察力的评论与建议.

参考文献：

[1]R. Agrawal, C. Faloutsos, and A. Swami. Efficient similarity search in sequence databases. In Proc. of the Fourth International Conference on Foundations of Data Organization and Algorithms, Chicago, October 1993.

[2]R. Agrawal, S. Ghosh, T. Imielinski, B. Iyer, and A. Swami. An interval classier for database mining applications. In    Proc. of the VLDB Conference, pages 560-573, Vancouver, British Columbia Canada, 1992.

[3]R. Agrawal, T. Imielinski, and A. Swami. Database mining: A performance perspective. IEEE Transactions on Knowledge and Data Engineering, 56:914-925, December 1993. Special Issue on Learning and Discovery in Knowledge-Based Databases.

[4]R. Agrawal, T. Imielinski, and A. Swami. Mining association rules between sets of items in large databases. In Proc. of the ACM SIGMOD Conference on Management of   Data, Wanshington, D.C., May 1993.

[5]R. Agrawal and R. Srikant.  Fast algorithms for mining association rules in large databases. Research Report RJ 9839, IBM Almaden Research Center, San Jose, California, June 1994.

[6]D. S. Associates. The new direct marketing. Business One Irwin, Illinois, 1990.

[7]R. Brachman et al. Integrated support for data archeology. In AAAI-93 Workshop on Knowledge Discovery in Databases, July 1993.

[8]L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone. Classification and Regression Trees. Wadsworth, Belmont, 1984.

[9]P. Cheeseman et al. Autoclass: A Bayesian classification system. In 5th Int’l Conf. on Machine Learning. Morgan Kaufman, June 1988.

[10]D. H. Fisher. Knowledge acquisition via incremental conceptual clustering. Machine Learning, 2(2), 1987.

[11]J. Han, Y. Cai, and N. Cercone. Knowledge discovery in databases: An attribute oriented approach. In Proc. of the VLDB Conference, pages 547-559, Vancouver, British Columbia, Canada, 1992.

[12]M. Holsheimer and A. Siebes. Data mining: The search for knowledge in databases. Technical Report CS-R9406, CWI, Netherlands, 1994.

[13]M. Houtsma and A. Swami. Set-oriented mining of association rules. Research Report RJ 9567, IBM Almaden Research Center, San Jose, California, October 1993.

[14]R. Krishnamurthy and T. Imielinski. Practitioner problems in need of database research: Re search directions in knowledge discovery.    SIGMOD RECORD, 20(3):76-78, September 1991.

[15]P. Langley, H. Simon, G. Bradshaw, and J. Zytkow.    Scientific Discovery: Computational Exploration of the Creative Process. MIT Press, 1987.

[16]H. Mannila and K.-J. Raiha. Dependency inference. In    Proc. of the VLDB Conference, pages 155-158, Brighton, England, 1987.

[17]H. Mannila, H. Toivonen, and A. I. Verkamo. Ecient algorithms for discovering association rules. In KDD-94: AAAI Workshop on Knowledge Discovery in Databases, July 1994.

[18]S. Muggleton and C. Feng. Efficient induction of logic programs. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, 1992.

[19]J. Pearl. Probabilistic reasoning in intelligent systems: Networks of plausible inference, 1992.

[20]G. Piatestsky-Shapiro. Discovery, analysis, and presentation of strong rules. In G. Piatestsky-Shapiro, editor, Knowledge Discovery in Databases. AAAI/MIT Press, 1991.

[21]G. Piatestsky-Shapiro, editor.    Knowledge Discovery in Databases. AAAI/MIT Press, 1991.

[22]J. R. Quinlan.C4.5: Programs for Machine Learning. Morgan Kaufman, 1993.