1.2 国内外研究现状

由于静态数据集和动态数据流的数据特征不同，从中挖掘频繁模式或高效用模式的算法也有所不同；但是静态数据集的挖掘算法是动态数据流中挖掘算法的基础，本节分别从静态数据集、动态数据流两方面介绍频繁模式和高效用模式挖掘算法的研究现状。

1.2.1 传统数据集中频繁模式挖掘算法的研究

1．静态数据集上频繁模式挖掘算法

Agrawal等[1,2]首先提出了频繁模式挖掘问题的原始算法，并给出了著名的Apriori算法。该算法的主要理论依据是频繁项集的两个基本性质：①频繁项集的所有非空子集都是频繁项集；②非频繁项集的超集都是非频繁项集。算法Apriori首先产生频繁1-项集L1，然后利用频繁1-项集产生频繁2-项集L2，直到有某个r值使得Lr为空为止。在第k次循环中，算法先产生候选k-项集的集合Ck, Ck中每一个项集是用两个只有一项不同的Lk-1中进行并集产生的。Ck中的项集是用来产生频繁k-项集的候选项集，即频繁项集Lk是Ck的一个子集。Ck中的每个项集需要统计在数据集中的个数，从而来决定其是否加入Lk，即需要扫描一遍数据集来计算Ck中的每个项集的支持度。

Apriori是首次提出采用逐层挖掘的算法，并且是逐层挖掘算法中的代表算法，之后的很多算法都是在此基础上进行改进，如算法DHP[3]采用Hash技术来优化Apriori算法中候选项集的产生过程。Cheung等[4]采用并行方式对Apriori算法进行改进，将数据集划分为多个小数据块，在每次迭代产生频繁项集过程中，首先并行计算所有候选项集在各个数据块的支持数，然后汇总每个候选项集的总支持数（即可从候选项集中找到频繁项集），最后再利用当前层产生的频繁项集来产生新的候选项集来进行下次的迭代。算法Apriori的主要缺点：①扫描数据集的次数至少等于最长的频繁项集的长度；②需要维护算法过程中产生的候选项集（中间结果）。

算法Apriori在挖掘过程中产生了大量的候选项集，并且需要反复扫描数据集，严重影响了算法效率。为此，Han等人提出了一种无须产生候选项集的算法FP-Growth[5]，该算法只需要扫描数据集两次：第一次扫描数据集得到频繁1-项集；第二次扫描数据集时，利用频繁1-项集来过滤数据集中的非频繁项，同时生成FP-Tree，然后在FP-Tree上执行递归算法，挖掘所有的频繁项集。实验分析表明FP-Growth算法比Apriori算法快一个数量级。

算法FP-Growth是采用模式增长的方式直接生成频繁模式，该算法是模式增长算法中的典型算法，同时也是第一个模式增长算法，之后提出的模式增长挖掘算法[6-18]都是在此基础上进行改进的，包括不确定数据集中频繁模式挖掘和高效用模式挖掘中的很多算法。

算法COFI[19]不需要递归的构建子树，该算法通过项集枚举的方法来挖掘频繁模式；在稀疏数据集上，该算法的时间和空间效率优于算法FP-Growth，但在处理稠密数据集或长事务数据集的时候，该算法的处理效率比较低。

之后提出了很多频繁项集挖掘算法[20-30]，包含完全频繁项集挖掘[5,19,21,22,24,26,31-35]、闭项集挖掘[20,28,36]和最大频繁项集挖掘[23,25,27,29,37]；其中国内在这领域研究也有较大的进展[7,38-74]，包括TOP-K频繁项集挖掘[75-77]、负关联规则挖掘算法[78,79]等。

2．数据流中频繁项集挖掘算法

和静态数据集相比，动态数据流上有更多的信息需要跟踪，如以前频繁模式后来变为非频繁项集，或以前非频繁模式后来变为频繁模式；另外，由于数据的流动性，当前内存中维护的数据要不断地调整。数据流中的频繁模式挖掘算法一般采用窗口方法获取当前用户关注的数据；然后基于已有的静态数据集上的频繁模式挖掘算法，提出可以挖掘数据流中被关注数据的算法。目前存在3种典型的窗口模型[80]：界标窗口模型（Landmark Window Model）、时间衰减窗口模型（Damped Window Model）和滑动窗口模型（Sliding Window Model）。

界标窗口模型中的窗口指特定一时间点（或数据流中一条特定的数据）到当前时间（或当前条数据）之间的数据，界标窗口模型如图1.1（a）所示，在C1、C2和C3时刻，窗口中的数据分别包含了从S点到C1点、C2点和C3点之间的数据。文献[81-85]中频繁项集挖掘算法都是基于界标窗口，文献[82]提出算法DSM-FI（Data Stream Mining for Frequent Itemsets）是基于界标窗口，它以数据开始点为界标点，该算法有三个重要特征：①整个挖掘过程只需要一遍数据集扫描；②扩展前缀树存储挖掘的模式；③自上而下的方式挖掘频繁项集。文献[83]提出一个基于界标窗口的频繁闭项集挖掘算法FP-CDS，该算法将一个界标窗口划分为多个基本窗口，每个基本窗口作为一个更新单元（每个基本窗口中的数据也可以称为一批数据）：首先从每个基本窗口中挖掘出潜在的频繁闭项集，同时存储在FP-CDS树上，最终从FP-CDS树上挖掘出所有的频繁闭项集。文献[84]提出一个近似算法Lossy Counting，该算法以批为处理单元，每来一批就更新一次已有频繁项集的支持数，频繁的项集被保留下来，不频繁的被删除，同时也将当前批中新的频繁项集保留下来。

时间衰减窗口模型和界标窗口模型所包含的数据是相同的，只是衰减窗口中的每条数据有不同的权重，距离当前时间越近，数据的权重越大，如图1.1（b）所示；实际上，时间衰减窗口模型是界标窗口模型的一个特例。文献[86-90]中算法都是基于时间衰减窗口模型。文献[86]提出一个基于衰减窗口模型的近似算法，该算法用一个树结构FP-stream来存储两类项集：频繁项集和潜在频繁项集。当新来一批数据的时候，更新树结构上这两类项集的支持数，如果更新后的项集既不是频繁项集，也不是潜在频繁项集，则将这类项集从树上删除；同时新来一批数据中新产生的频繁项集或潜在频繁项集也要存储在这个树结构上。文献[87]引入一个时间衰减的函数来计算项集支持数以及总的事务支持数。文献[88]采用固定的衰减值，当新来一个事务项集的时候，已有的频繁项集的支持数都乘以固定的衰减值，如果新来的事务包含某一频繁项集，则该项集的支持数再加上1。

滑动窗口模型中当前处理数据的个数固定，或者是当前处理数据的时间段长度固定，如图1.1（c）所示。基于滑动窗口模型的频繁项集挖掘算法研究比较多[91-100]。文献[92]提出一个挖掘算法DST，该算法指定一个窗口中有固定批的数据，并且每批数据中事务个数也是固定的，每新到一批数据就更新一次窗口；DST将窗口中事务数据保存到树DST-Tree上，DST-Tree的节点结构如图1.2（a）所示，节点上的P字段记录节点当前窗口中每批数据中的支持数，同时每个节点还用L字段记录更新该节点的最后批次；每新来一批数据，将新到的数据添加到树DST-Tree上，同时修改相应节点上的P值和L值。算法DST在挖掘窗口中频繁项集之前，先把树上不再有用的节点（垃圾节点）从树上删除，然后用算法FP-Growth挖掘每个窗口中的频繁项集。文献[92]的作者后来又提出一个算法DSP[93]，算法DSP和DST的主要区别是DSP采用COFI来挖掘窗口中的频繁项集，而DST是用FP-Growth挖掘窗口中的频繁项集；算法DSP存储事务项集的树结构和DST的相同。

文献[95]提出一个基于滑动窗口的频繁项集挖掘算法CPS，在算法CPS中，每个窗口是由固定批的数据组成，以批为单位更新窗口中数据，该算法将窗口中事务项集保存到一棵CPS-Tree树上，树CPS-Tree上有两类节点：正常节点（normal node）和尾节点（tail-node），正常节点上只记录该节点总的支持数S，如图1.2（b）所示；而尾节点要记录总的支持数S，同时还用一个数组P记录一个节点当前窗口中每批数据上的支持数，如图1.2（c）所示。每新来一批数据，该算法会将树中的垃圾节点删除，采用FP-Growth算法挖掘每个窗口中的频繁项集。

1.2.2 不确定数据集中的频繁模式挖掘算法的研究

随着数据挖掘技术的广泛应用、数据采集中的不确定性和误差性等原因，现实中会产生很多不确定的数据，例如一个病人在问诊中，往往并不能根据病人的症状而被百分之百地确诊为某一病；通过RFID或者GPS获取的目标位置都有误差[101,102]；用商业网站或历史数据中挖掘到的购物习惯来预测某些顾客下一步购买的商品都存在一定的不确定性。表1.1是一个不确定数据集的例子，每个事务表示某一顾客最近要买哪些商品以及买这些商品的可能性（概率）。因此随着不确定数据在很多领域的产生，对该类数据进行挖掘分析又成为数据挖掘领域一个新的研究问题[103-124]。由于不确定数据集和传统数据集的数据结构不同，并且两类数据集上的频繁模式挖掘模型也不同，因此不能用传统数据集中的算法来挖掘不确定数据集中的频繁模式。本节根据数据集的静态和动态特性，分别描述不确定数据集上频繁模式挖掘算法的研究现状。

1．静态数据集

不确定事务数据集的频繁项集挖掘算法主要分为逐层挖掘（level-wise）和模式增长（pattern-growth）两种方法。逐层挖掘的算法基于算法Apriori，模式增长方式的算法则基于算法FP-Growth。表1.2列出了一些重要算法及其一些特征。

U-Apriori[121]是第一个不确定数据集上的频繁项集挖掘算法，该算法是基于Apriori提出的。该算法和Apriori的主要区别是前者扫描数据集是为了计算每个候选项集的期望支持数，而后者扫描数据集是为了计算候选项集的支持数。因此U-Apriori算法的缺陷同Apriori算法一样：产生候选项集，以及需要多遍扫描数据集来统计每层候选项集的期望支持数，如果最长的频繁项集长度是k，则最少需要扫描k次数据集。因此，如果数据集比较大、事务项集长度比较长或设定的最小期望支持数比较小，则U-Apriori的时间和空间性能都会受到很大的影响。

2011年，Wang等[115]提出一个不确定数据集的频繁项集挖掘算法MBP。该算法主要是对U-Apriori算法的改进，作者提出了两种策略来提高计算候选项集的期望支持数的效率：①在扫描数据集的过程中，如果一个候选项集提前被识别为非频繁项集，就停止计算该项集的实际期望支持数；②扫描数据集的过程中，如果一个候选项集的当前期望支持数已经大于预定义的最小期望支持数，就停止计算该项集的实际期望支持数。因此，算法MBP在时间和空间性能上得到了很大的提升。

2012年，Sun等[111]改善了算法MBP，基于MBP算法给出一个不确定数据集中频繁项集挖掘的近似算法IMBP。IMBP时间和空间性能优于MBP，然而，其准确性并不稳定，并且在稠密数据集中的精确度比较低。

2007年，Leung等[122]提出一个基于树的模式增长的算法UF-Growth，该算法中还提出一个新的树结构UF-Tree来存储不确定事务数据集，采用模式增长的方式从树上挖掘频繁项集。UF-Growth和FP-Growth的主要区别有两点：①UF-Tree树上每个节点除了保存和FP-Tree树上节点相同的信息外，还保存了每个节点的概率值，因此只有项相同，并且其相应的概率值相同的项才能共享同一个节点；而FP-Tree中，只要项相同就可以共享同一节点。②UF-Growth中计算频繁项集的时候都是统计项集的期望支持数，FP-Growth是计算项集的支持数。因此，UF-Tree树上的节点比较多，例如，对于两个不确定事务项集{a:0.50, b:0.70, c:0.23}和{a:0.55, b:0.80, c:0.23}，当按照字典顺序插入树中时，由于两个事务中项a的概率不相等，所以这两个项集不能共享同一个节点a，从而算法UF-Growth需要更多的空间和时间来处理UF-Tree。

Leung等[120]又改善UF-Growth以减小UF-Tree树的大小。改进算法的思想：先预定义一个k值，只考虑事务项集中概率值小数点之后的前k位数，如果两个概率的小数点之后的前k位数值都相同，则认为这两个概率值相同。例如，设定k值为1，当这两个事务项集{a∶0.50, b:0.70, c:0.23}和{a∶0.55, b∶0.80, c∶0.23}再按字典顺序添加到UF-Tree上时，则项a的概率均为0.5，则这两个项集可以共享同一个节点a；但若k设定为2，则项a概率分别为0.50和0.55，则这两个项集就不能共享同一个节点a。k值越小，改进后的算法消耗的内存越小，但改进后的算法仍然不能创建一棵与原始FP-Tree一样压缩率的UF-Tree，并且改进后的算法还可能会丢失一些频繁项集。

算法UH-Mine[125]也是一个模式增长的算法，它和UF-Growth算法的主要区别：UF-Growth算法采用FP-Tree保存事务项集，而UH-Mine采用非压缩的结构H-struct[26]来保存事务项集。在将事务项集存储到H-struct上时，没有任何的压缩，即任两个项集都不会共享任何节点。H-struct的创建也需要扫描数据集两遍：第一遍，创建一个有序的频繁1-项集头表；第二遍，将事务项集添加到H-struct中，同时按头表的顺序添加，并且删除事务项集中非频繁的项。头表中还保存有每个频繁项在树上的所有节点。该算法在较小的数据集上，能获得较好的效果，然而在大数据集上，因为H-struct需要较多的空间来存储，同时也需要较多的时间来处理H-struct上的所有节点。

文献[125]也将经典算法FP-Growth扩展到不确定事务数据集，扩展后的算法命名为UFP-Growth。UFP-Growth采用FP-Growth的方法创建了一棵同样压缩率的树，但是创建的树会丢失事务项集相应的概率信息，所以UFP-Growth只是先从树上产生候选项集，最后通过一遍原始数据集的扫描确认真正的频繁项集。

2011年，Lin等[109]提出一个新的不确定事务项集的频繁项集挖掘算法CUFP-Mine。该算法是将事务项集压缩到一个新的树结构CUFP-Tree上，一棵CUFP-Tree树的创建需要扫描两遍数据集：第一遍扫描是为创建一个有序的频繁1-项集头表；第二遍扫描中，将事务项集按头表排序，同时删除事务项集中的非频繁项。假设项集Z（{Z1, Z2, …, Zi, …, Zm}）是有序，并且所有项都是频繁的，则当任一项Zi被添加到树上时，在对应节点上需要将Zi的所有超集（超集是由项Z1, Z2, …, Zi中的任意项组合的）及每个超集对应的期望支持数保存到该节点上。

CUFP-Mine的主要思想：所有的事务项集压缩到树上后，再统计相同节点上所有超集的总的期望支持数，即可判断哪些超集是频繁的。CUFP-Mine的优点是不需要递归的挖掘频繁项集；在设定阈值较大的情况下，能够较快地发现频繁项集。该算法的主要缺点是需要较多的内存来保存事务项集；另外，随着数据集的变大和设定的最小期望支持数变小，该算法很容易发生内存溢出。

2．动态数据流

针对不确定数据流中频繁项集挖掘，已有的算法主要基于UF-Growth及滑动窗口技术或时间衰减窗口技术[112-114,116,119,124]。

Leung等[119]提出两个基于滑动窗口的算法UF-streaming和SUF-Growth，每个滑动窗口包含固定批数的数据，当一个窗口满了以后，每来一批数据，都会先从窗口中删除一批最老的数据，然后再将新来数据添加到窗口中。

算法UF-streaming采用FP-streaming[86]的方法，预定义两个最小期望支持数preMinsup和minSup（preMinsup<minSup）, UF-streaming挖掘的频繁项集的支持数大于等于minSup，而支持数介于preMinsup和minSup之间的项集称为潜在频繁项集，也会和频繁项集一起保存到一棵树UF-stream上。该算法利用UF-Growth挖掘每批数据中的支持数大于等于preMinsup的项集作为候选项集，然后将每批数据中的候选项集保存到一个树UF-stream上，UF-stream树上每个节点记录窗口中每批数据的支持数（假设一个窗口中包含w批数据，则每个节点上需要记录w个支持数）；当新来一批数据中的候选项集被添加到UF-stream树上之前，会将树上最老批次数据对应的候选项集从树上删除；当一个节点上总的支持数（所有批上的支持数的和）大于等于minSup，则该节点到根节点对应的项集就是一个频繁项集。该算法是一个近似的挖掘算法，会丢失一部分频繁项集。

SUF-Growth算法主要基于算法UF-Growth，该算法将每批数据添加到树UF-Tree的时候，节点分别记录每批数据的支持数（假设一个窗口中包含w批数据，则每个节点上需要记录w个支持数）；当新来一批数据的时候，会首先将树上最老批次的数据删除；最老批次数据删除之后，则将新来数据添加到树上；挖掘频繁项集的时候从该树上读取数据，采用模式增长的方式挖掘频繁项集。

文献[113,114]中提出的算法采用的是时间衰减窗口模型，仍然采用UF-Tree来存储窗口中的事务项集。由于UF-Tree共享同一个节点时，不仅要求项相同，还要求项对应的概率值也相同，因此该树结构的存储需要大量的空间，同时也需要较多的处理时间。

1.2.3 高效用项集挖掘算法的研究

传统数据集中频繁模式挖掘仅仅考虑了一个项集在多少个事务中出现，并没有考虑项集中各项的重要度、利润、价格和数量等效用值相关的信息，而效用值可以度量项集的成本、利润值或其他重要度等信息。例如，在传统数据集的购物单中，只考虑一个购物单中包含了哪些商品，而没有考虑一个购物单中每个商品的数量、价格或利润，然而在现实的很多应用中，购物单中商品的数量以及每种商品的单位利润都是很重要的。表1.3和表1.4是一个具有效用信息的数据集，该类数据中的高效用模式可以用来最大化一个企业的商业利润，这里称此类数据为带有效用的数据集。其中表1.3的前两列是一个包含7个事务的事务数据集，表1.4是各事务项的单位利润（效用）值；表1.3中的第三列t u（Ti）给出了每个事务的总效用值，后面三列则分别是B、C、{BC}三个项集在每个事务上的效用值。下面给出静态和动态数据集上的高效用模式挖掘算法的研究现状。

1．静态数据集

表1.5列出了一些高效用模式挖掘的主要算法。2004年，Yao等[126]首先提出了高效用项集挖掘的相应定义和数学模型：数据集Dut上一个项集X的效用值 u（X），被 定 义 为 X 在 所 有 事 务 t 上 的 效 用 值 的 总 和，即，其中Dut是一个带有效用值的数据集、u（X, t）是项集X在事务t上的效用；它是一个项集的总的利润（总的效用值），例如：“牛奶”+“面包”组合为所有的购物记录中所产生的利润的总和。高效用项集挖掘的目标，就是找出效用值u（X）高出用户预先设定的最小效用值的所有项集。

在文献[126]中Yao等还提出一种挖掘算法，该算法首先估计项集效用的期望值，然后用估计的期望值来判断一个项集是否是一个候选项集。但是，当用户设定的最小效用值比较低的时候，或者事务中包含比较多的事务项集的时候，该方法产生的候选项集个数接近于所有项的组合数。针对上述算法中产生大量候选项集的问题，在2006年，他们又在文献[127]中提出了两个新的算法：UMining和UMining_H。UMining算法采用效用值上限的剪枝策略来降低候选项集个数，UMining_H算法采用启发式的策略来降低候选项集的个数；同时这两个算法会失去一些高效用项集，并且产生的候选项集个数还是比较多。

自Yao等提出高效用项集挖掘之后，高效用项集挖掘也成为一个研究热点[126-140]。2005年，Liu等[128]提出了一个典型算法Two-Phase，同时作者还提出一个twu（transaction-weighted-utilization）模型，即一个项集的twu值不小于用户设定的最小效用值，该项集就是一个候选项集。该模型同时也满足向下封闭属性，即如果一个项集的twu值不小于用户设定的最小效用值，则该项集的任何非空子集的twu值也不小于用户设定的最小效用值；如果一个项集的twu值小于用户设定的最小效用值，则该项集的任何超集的twu值也小于用户设定的最小效用值。Two-Phase算法主要分为两步来完成：首先利用twu模型和Apriori算法，挖掘出所有的候选项集；再扫描一遍数据集来确定哪些候选项集是高效用项集。Two-Phase算法确实优于文献[126]中的方法，但是该算法包含了Apriori算法需要扫描多遍数据集的缺点；同时该方法也是通过候选项集来产生高效用项集，其时间效率仍然不是很理想。

为了解决已存在算法的低效率问题，特别是挖掘稠密数据集时的低效率问题，2007年，Erwin等[137]提出了一个基于树结构的高效用项集挖掘算法CTU-Mine。然而，该算法只是在挖掘稠密数据集或用户设定的最小效用值比较低的时候，性能才优于Two-Phase算法。

2008年，Li等[135]针对Two-Phase算法中产生过多候选项集的问题，提出了降低候选项集的策略IIDS（Isolated Items Discarding Strategy），并将提出的策略应用到已存在的层次挖掘算法中，分别得到两个新的算法FUM和DCG+。这两个算法都优于它们原来的算法，但是这两个算法还是存在同样的问题：通过候选项集来挖掘高效用项集。2007年，Hu等[136]还提出一个近似的方法来挖掘高效用项集；2011年，Lin等[134]提出一个新算法HUP-Growth，该算法首先通过两遍数据集扫描，将事务项集维护在一棵类FP-Tree的树上，处理树上每一项的时候，需要产生包含该项的所有项集，同时需要计算这些项集的效用值，即可以从中确认真实的高效用项集；该算法的计算量比较大，但是该算法的时间效率优于算法Two-Phase。

以上提出的算法基本上都是通过多遍扫描数据集来产生候选项集；2009年，Ahmed等[132]提出一个不需要多次扫描数据集的算法IHUP。算法IHUP先将事务项集及效用信息存储在一棵IHUP-Tree上，这里以表1.3和表1.4的数据为例来描述算法IHUP，最小效用值（记为minUti）设为70。

该算法首先扫描一遍数据集，计算各项的twu值，删除twu值小于70的项，然后将剩余的项按twu值大小的逆序排序，如图1.3中左边的头表。创建好头表后，接下来就可以创建树，首先将事务项集按头表中项的顺序排序，同时删除不在头表中的项，计算修改后的事务项集的twu值，再将有序的项集添加到树上，同时将新计算到的twu值累加到该项集在树中的所有节点上。表1.3和表1.4中数据所对应的IHUP-Tree如图1.3所示。创建完树后，采用模式增长的方式从树上产生候选项集；最后再扫描一遍数据集从候选项集中识别出高效用项集。该算法的挖掘效率相对于已有的算法有很大的提高。

Tseng等在文献[130,131]中对算法IHUP进行改进，主要是针对建树方法的改进，进而得到算法UP-Growth。Tseng等考虑到处理树上每个节点的时候，子孙节点不再参与当前节点的处理过程，因此Tseng等人在将一个准备好的项集添加到树上，并在处理该项集中每一项的时候，只将该项及祖先项的效用值的和累加到该项在树上对应的节点上，如图1.4所示，当表1.3中第二个事务（B,2）（C,2）（E,1）（G,4）被添加到树上的时候，首先被处理的项集为“C:2, E:3, B:6”（其中的数值为各项在该事务中的效用值），当各项被添加到树上的时候，如项E对应的节点只将项C和E的效用值累加到该节点效用值上，项B对应的节点将这三项的效用值都累加到该节点效用值上，如图1.4的路径root-C-E-B所示。对比图1.3和图1.4，会发现后者树上很多节点的效用值降低了很多，从而在创建条件子树的时候，会有很多项排除在条件子树之外，即条件子树中节点也会减少，因此UP-Growth算法的效率比IHUP算法提高了很多。

算法D2HUP[141]采用项集枚举的方法挖掘高效用项集，该算法主要通过剪枝策略提高挖掘的时间效率，但是需要大量的空间来维护枚举树和事务项集。HUI-Miner[133]同Apriori算法采用层次方式产生高效用项集，每层中需要产生大量的项集，并计算每个项集的效用值；同时还需要维护每个项集所在事务ID、相应事务中的效用值和事务中其余项的效用值信息，因此该算法空间消耗较大。

2．动态数据流

Tseng等[138,139]提出了第一个数据流中高效用项集挖掘算法THUI，该算法整合了Two-Phase算法和滑动窗口的方式来挖掘数据流上的高效用项集，每个窗口中有固定批数的数据，每批数据又有固定个数的事务项集。该算法首先挖掘出窗口的第一批数据中的候选2项集，当第二批数据到来的时候，再挖掘出前二批数据中的候选2项集，依次挖掘出整个窗口中的候选2项集，用所有的候选2项集再产生全部的候选项集，最后还需要再扫描一遍数据集从候选项集中确认高效用项集。维护候选2项集的时候，还将每个候选项集产生的开始批次保存下来，当删除老数据的时候，只将候选项集的twu值减去该项集在最老批次数据中的twu值，同时将修改项集的开始批次增加1；当新来数据的时候，修改当前维护的候选项集的twu值，同时将新来批数据中新产生的候选项集添加到维护的候选项集集合中。该算法是一个近似算法，它的主要问题是需要产生并维护候选项集，并且还需要扫描数据集来统计每个候选项集的效用值，甚至有时候会产生大量的候选项集。

Li等[129]提出两个基于滑动窗口的算法：MHUI-BIT和MHUI-TID，这两个算法都采用类Apriori算法的特点逐层产生所有的候选项集，然后再扫描数据集来统计候选项集的效用值。算法MHUI-BIT和MHUI-TID分别采用bit-vector和TID-lists两个结构来存储当前窗口中每批数据，利用这两个结构能检索到与候选项集相关的事务，从而可以快速地统计候选项集的效用值，实验结果也验证了这两个算法的时间效率优于算法THUI。

2010年，Ahmed等[140]提出一个仍然基于滑动窗口的算法HUPMS，该算法采用树结构来维护窗口中每批数据的事务项集，通过一遍数据集扫描，将窗口中的事务项集维护在一棵树上，当新来一批数据的时候，先将最老数据从树上删除，再将新的数据添加到树上；当需要挖掘窗口中的高效用项集的时候，采用模式增长的方式从树上挖掘出所有的候选项集；最后再扫描一次数据集来统计所有候选项集的效用值。该算法相对算法MHUI-BIT和MHUI-TID，可以有效地减少候选项集的个数，实验也验证了该算法有比较好的时间性能。

1.2.4 大数据集下的频繁模式挖掘研究

目前，针对大数据环境下的数据流频繁模式挖掘算法研究比较少，主要集中在静态的大数据中研究。PFP[142]是一个基于MapReduce的FP-Growth算法的实现，该算法需要两次MapReduce。首先，PFP算法利用MapReduce建立一个头表。第二次MapReduce，在Map过程中，每个事务项集都按头表的顺序排序，并且删除事务项集中不频繁的项，将有序事务项集中每项之前的项集（称为子事务项集）作为value值，该项作为key值输出，即如果一个事务项集中包含k项，则该事务项集会产生（k-1）个（key, value）键值对，即一个事务项集被分配给全局头表中多项来创建子树；在Reduce过程中，采用FP-Growth算法挖掘各项对应的子事务项集中的频繁项集。PFP算法的最大缺点是不能将数据均匀分配给各个节点，有的节点上数据量会很大，因此会影响到整体的时间效率。文献[143]针对云制造环境下数据挖掘的需求，提出了一种新的利用键值存储系统优化PFP-Growth算法。

Apriori算法的MapReduce实现的研究比较多，文献[144-151]中的算法都是基于MapReduce的Apriori实现的研究。已存在的基于Apriori的算法主要采用多次MapReduce来实现Apriori算法的并行算法，如果数据集中存在最大长度是k的频繁项集，则需要最少k次MapReduce。首先MapReduce一遍数据集产生频繁1-项集；然后用频繁1-项集组合产生候选2-项集，将候选2-项集分配到各个节点上，进行第二次MapReduce扫描数据集，统计各个候选项集在各个节点上支持数，在Reduce过程中再统计各个候选项集在全部数据集上的支持数，即可发现频繁2-项集；继续产生候选k-项集，进行k次MapReduce扫描数据集，从中发现频繁k项集（k≥3）。文献[151]中还提出三个算法FPC和DPC和SPC:FPC在每次迭代过程中，产生固定层次的候选项集，如产生k+1, k+2, …, k+l的候选项集（l为某一固定值）；而算法DPC是对FPC的一个改进，在每次的迭代过程中，将FPC中的l变为一动态值；算法SPC[151]是每次迭代中只产生一层候选项集。通过实验分析，发现算法SPC和FPC的时间性能比较好，并且两算法的时间性能也比较接近，但是算法FPC在每次迭代中会产生过多候选项集，内存需求会比较多。

文献[147]提出了基于MapReduce的Apriori算法近似频繁项集挖掘算法PSON，通过两次MapReduce（第一次是挖掘每个节点上的局部频繁项集，然后合并所有节点上的局部频繁项集作为候选项集；第二次MapReduce，再扫描一遍数据集统计所有候选项集的支持数），即可从候选项集中发现所有支持数大于等于设定的最小支持数的频繁项集。该算法的问题就是输出的是<key,1>键值对，并且该算法挖掘的结果中会丢失部分频繁项集。