CFMoment:挖掘数据流频繁闭项集算法

王金伟， 吴少华， 瞿治国

南京信息工程大学计算机与软件学院，南京210044

近年来，随着大数据处理技术的快速发展，对数据流的模式挖掘已成为该领域的一个研究热点.但是数据流的数据量大且需要实时处理，使得数据流挖掘面临着一些固有的挑战[1-3]：1）每个数据元素流只能被处理一次；2）尽管数据元素是连续产生的，但是存储空间是有限的；3）数据元素的高速流动需求更加快捷地处理这些数据；4）数据流挖掘的准确度必须控制在允许的误差范围内.

近年来，研究者已提出多种挖掘数据流频繁项模式的算法.基于数据流处理所采用的不同的处理模型，数据流频繁项集挖掘算法大致可以分为3 类：界标窗口模型、滑动窗口模型、衰减窗口模型.在界标窗口模型中，用户将一个开始时间指定为界标，挖掘范围是从界标时间到当前时间的所有数据；在滑动窗口模型中，窗口大小由用户指定，并且挖掘范围是该窗口中最近的事务；在衰减模型中，根据流动顺序对每个事务执行递减授权，先前流动的事务权重较小，而最近流动的事务权重最大.文献[4]基于界标窗口模型提出了sticky-sampling 和lossy-counting 两种数据流频繁项集挖掘算法.其中，lossy-counting 算法能够基于3 个buffertrie-setgen 模型来挖掘离线数据流中的频繁项集.文献[5]提出的基于前缀树的DSM-FI（data stream mining for frequent itemsets）算法可以利用界标模型挖掘数据流中的频繁项集.文献[6]提出的DSM-MFI（data stream mining for maximal frequent itemset）算法能够挖掘数据流中最大的频繁项集.文献[7]提出的FDPM（frequent data stream pattern mining）算法使用界标窗口模型来挖掘高速事务数据流中的频繁项集.文献[8]提出了FP-CDS 算法，该算法使用了界标模式挖掘数据流中的频繁闭项集.

文献[9]提出了基于时间衰减模型的estDec 算法，该算法主要针对数据流中可能的频繁项集进行挖掘.文献[10]进一步提出了采用衰减窗口模型的estMax 算法，主要针对数据流中信息价值更大的最大频繁项集进行挖掘.文献[11]提出了与前缀树不同的数据结构CP-tree来挖掘数据流中的频繁项集.效率对比测试表明，具有CP-tree 结构的esDec 算法远高于原始的esDec 算法.随后文献[12]提出了一种利用滑动窗口挖掘在线数据流中的频繁项集算法.文献[13]则基于Apriori 算法[14]并结合滑动窗口模型进一步提出了基于事务滑动窗口的频繁项挖掘（mining frequent itemsets-transaction sliding window,MFI-TransSW）算法，该算法用于挖掘数据流中的频繁项集.文献[6]提出了基于DSM-MFI 的DSM-RMFI 算法，该算法利用滑动窗口模型来挖掘离线数据流中最大的频繁项集.文献[15]则利用滑动窗口模型提出了挖掘数据流中最大频繁项集的Max-FISM（maximal-frequent itemset mining）算法，当有新的事务更新进入到窗口时，代表新事务的最大项集被插入到最大集用来参与最大频繁项集的处理，从而提高了挖掘效率.文献[16]对数据库进行扫描将其转换为垂直数据格式，然后通过生成位表的形式来优化寻找频繁项集.文献[17]提出了一种改进的FP-growth 算法及分布式并行实现技术，该算法先对构造的完备模式树进行剪枝，然后采用频繁闭模式项集策略减少空间搜索，从而达到提高算法挖掘效率的目的.文献[18]基于集合枚举树排序提出了多最小支持度的频繁模式挖掘算法，引入集合枚举树结构并在枚举树中使用多最小支持度来解决挖掘过程中时间和内存消耗过大的问题.

文献[19]首次提出了利用滑动窗口挖掘数据流中频繁闭项集的Moment 算法，在闭枚举树（closed enumeration tree,CET）数据结构中存储了4 种节点：非频繁节点、无望节点、中间节点和封闭节点.这4 种节点类型涵盖了窗口滑动过程中节点变化的所有类型，因此CET能够覆盖挖掘过程中的所有必要信息.当新的事务被添加到窗口或从当前窗口删除时，该算法遍历并更新CET 中的相应部分；当窗口尺寸设置得太小且概念漂移过于频繁时，项集添加到窗口或从窗口中移除均涉及到许多节点的更改.文献[20]使用直接更新（direct update,DIU）数据结构来存储频繁闭项集的数据流.文献[21]基于CET 数据结构提出了NewCET 数据结构，只保存可能的频繁闭项集，并进一步提出了NewMoment 算法，采用位操作技术来高效计算频繁闭项集的支持度.文献[22]提出了AFPCFI-DS 算法，根据每个窗口的FP-tree 检查频繁项集的频繁闭项集[23].当处理新窗口时，该算法首先检查头表，然后根据头表中项目的变化更新FP-树.文献[24]提出的TMmoment 算法挖掘滑动窗口中的频繁闭项集，并使用TCET 数据结构来存储事务和关闭窗口中的频繁项集.

本文提出了一种新型的用于挖掘数据流频繁闭项集的CFMoment 算法.该算法使用滑动窗口模型和滑动窗口的特征来挖掘窗口中的事务.实验结果证明，该算法比Moment 算法更有效，占用内存也较小.

1 预备知识

1.1 基础定义

假设I={i1,i2,··· ,im}是一个项目的集合，事务T=(tid,x1,x2,··· ,xn)，xi ∈I，是一个项集.其中，m表示项目的大小，n表示事务的大小，tid为事务的编号.大小为k的项集称为k-项集.TDS={T1,T2,··· ,Tn}是一个事务流，其中Tn为最新流入事务，编号为n.当前滑动窗口TSWn-w+1=[Tn-w+1,Tn-w+2,··· ,Tn]，其中w表示窗口的大小，n-w+1 是当前事务滑动窗口（transaction sliding window,TSW）的id 编号.在同一窗口中，top =Tn-w+1表示该窗口中存在的最陈旧事务，即在时间序列中最先进入窗口的事务；bottom=Tn则表示当前窗口所存在的最新事务，即在时间序列中最后进入窗口中的事务.假设下一个流入事务是bottom+1=Tn+1，则用bottom+1 来表示窗口滑动时下一个流入的事务.项集X的支持度表示为sup(X)，即项集X在TSW 中出现的次数.

定义1如果项集X满足条件sup(X) ≥s，那么称这个项集X为频繁项集.其中，s是用户自定义的最小支持度阈值.

定义2如果不存在具有与项集X相同的支持计数的超集，则X是一个封闭的项目集.

1.2 问题的提出

给定滑动窗口和最小支持度阈值s，研究如何在数据流最近的w个事务中挖掘频繁闭项集，如图1所示.

图1 滑动窗口Figure1 Sliding window

2 CFMoment 算法

为了提高窗口滑动时的挖掘速度，在算法CFMoment 中建立表rela_table 用于存储频繁非闭项集与频繁闭项集之间的关系.此外，算法还采用了基于前缀树的扩展闭环枚举树（extend closed enumeration tree,ECET）存储数据流中的w个交易的闭合频繁项目集和相关信息，进一步提高了挖掘效率，降低了内存消耗.

2.1 建立ECET树

ECET 树是一种基于前缀树的数据结构，由4 部分组成：

1）Fre_item_list：该表主要用于保存挖掘到的当前窗口中所有包含项数为1 的频繁1-项集；

2）代表项集的3 种类型节点：非频繁项集节点、频繁但非闭的项集节点和频繁闭项集节点；

3）Hash_table：该表主要用于检查所挖掘出的项集是否为闭项集，它保存并映射闭项集为某个具体值.其中，闭项集的频繁支持度sup、该闭项集的所有事务标识以及tid_sum 联合形成该节点的键值；

4）Rela_table：该表主要记录并保存ECET 树中频繁非闭项集与频繁闭项集之间的相互关系.

与prefix-tree 所用结构类似的是，ECET 树中的每个节点ni都代表了一个项集I，而子节点nj则是在项集I添加新的项集后得到的.

BuildTree 是一个深度优先程序，它通过项集的字典顺序来处理项集.在算法1 的第1～3行中，如果一个长度为1 的项集很频繁，则将该项集添加到fre_item_list 中.在第4～6 行中，如果发现ni因某些字典序列很小而没有通过封闭检查，则ni判定为无望节点，并且节点ni的项集I和使项集无法通过封闭检查的项集均存储在rela_table 中.函数leftcheck 使用ni的支持以及包括项集I和tid_sum 的事务标识作为散列键用于封闭检查.当一个节点是频繁的但没有无望节点时，BuildTree 将检查它的后代节点，如算法1 中的第8～12 行所示.然后通过程序中的第13～18 行可以判断节点ni是中间节点还是封闭节点.

算法1BuildTree(nI,w,s)

图2是BuildTree 运行后建立的ECET 树.在图2中，虚线圆圈表示不频繁的网关节点，如节点D.虚线矩形代表无望的网关节点，如B.图中的A 和AB 是中间节点.实线矩形表示封闭的节点，如ABC 和AC.

图2 TSW1 的ECET 树Figure2 TSW1's ECET tree

2.2 窗口滑动过程

由于滑动窗口大小事先确定并保持不变，当窗口滑动时，能够对ECET 结构产生影响的过程有最旧事务top 的删除操作以及在窗口中引入最新事务bottom+1 的添加操作.因此，本文的CFMoment 算法充分利用这一特点，通过一致的集合运算高效地更新ECET 在窗口滑动时产生的变化.

算法2Sliding(top,bottom+1)

算法2 给出了Sliding 算法的具体执行步骤.从算法中可知，Sliding 算法主要有两个参数，即top 和bottom+1，分别表示滑动窗口最旧事务的删除操作，以及滑动窗口中添加新事务操作.在Sliding 算法的第1～2 行中，如果新添加的项集与待移除的项集相等，则新窗口中的ECET 树不必进行更新而保持不变.在Sliding 算法的3～4 行中，当top∩bottom+1 ={x1,x2,··· ,xm}（{x1,x2,··· ,xm}可以为空集）时，将top-{x1,x2,··· ,xm}的所有子集加入sup_minus，将bottom+1-{x1,x2,··· ,xm}的所有子集加入sup_plus.当执行到Sliding算法第6～9 行时，调用函数itemcheck 分别对sup_minus 和sup_plus 中的1-项集进行检查更新.引入itemcheck 的目的是对1-项集进行基础频繁性检查，从而有效提高对sup_minus和sup_plus 中是否包含对应频繁和非频繁性质发生转换的1-项集的检查效率.具体来说，如果sup_minus 中某个单项在频繁次数减少后由频繁单项变为非频繁单项，则原所有包含它的频繁闭项集都将在新的频繁闭项集合中被去除；反之则原所有包含它的频繁闭项集不会因窗口滑动而在新的频繁闭项集合中发生变化.同理，如果sup_minus 中某个单项在频繁次数增加后由非频繁单项变为频繁单项，则可能存在新的包含该单项的频繁闭项集出现；反之则原所有包含它的频繁闭项集不会因窗口滑动而在新的频繁闭项集合中发生变化.在该算法的第10 行中，将sup_minus 和sup_plus 的剩余项集添加到服从字典顺序和长度的递减顺序的candidate_set 中.算法的第11～17 行是对candidate_set 的项集进行逐一检查.如果项集运行函数supcheck=false，则该项集false 和candidate_set 将作为函数relacheck 的参数进行运算.简单理解如下：supcheck 函数是为了检查相应参数项集是否频繁，而relacheck 的功能是查找rela_table 中的项集记录作为参数，在rela_table 中确定它的类别并以此进行不同的处理，加速找出封闭节点.relacheck 函数的伪代码如下：

算法3relacheck(I,Boolean,SupSet)

2.3 算法示例

为了便于理解本文所提的相关算法，本文结合图1中所给出的具体示例进一步演示CFMoment 算法的执行过程.

根据图1可知，窗口TSW1的初始条件为top=T1，而相对应的是bottom+1 代表即将进入滑动窗口的最新事务，即bottom+1 =T5.在这一初始条件下，当窗口进行滑动时，将自动调用Sliding 算法.此时，因为top=T1=CD 且top+1=T5=CD，即退出窗口的旧事务与加入窗口的新事务相等，则不执行算法的更新操作，运行结束.此时窗口从TSW1滑动到TSW2，ECET 不变，TSW2的闭项集与TSW1的闭项集相同.

在窗口TSW2中，top =T2，bottom+1 =T6.当窗口从TSW2滑到TSW3时，调用Sliding 算法.此时top =T1= AC，bottom+1 = BD.CFMoment 算法的第4～5 行是在sup_minus 中加入项集A、C 和AC，在sup_plus 中加入项集D 和BD.第6～7 行是在sup_minus 中的1-项集调用itemcheck 函数，此时A 和C 的频繁次数为sup=sup-1，但它们仍然满足频繁条件且为单个频繁项集，继续存储在sup_minus 中.第8～9 行是在sup_plus 中的1-项集调用了函数itemcheck，运行后sup_plus 中还剩B 和D.将sup_minus 和sup_plus合并形成candidate_set，此时candidate_set={AC,A,B,C,D}.在算法的第11～17 行中，分开执行candidate_set 中的所有项目集.因为supercheck(AC)=true，所以对于AC 则执行relacheck(AC,true,candidate,set).

当执行relacheck(AC,true,candidate,set)时，由于ABC 是包含AC 的超集，且其自身是闭项集，所以AC 不是闭项集.但是可以发现，AC 同时存在于rela_table 和close_node中，A 也同时存在于no_closed_node 和candidate_set 中，由于AC 是闭项集，则A 也不是闭项集.当AC 和A 从candidate_set 中被移除时，candidate_set={B,C,D}.进而检查B则有supercheck(B)=true，在rela_table 的closed_node 中没有记录B，所以B 为闭项集，将B 插入hash_table 中.同理可求得C 与D 也为闭项集.

图3 TSW3 的ECET 树Figure3 TSW3's ECET tree

3 实验分析

本节主要分析算法CFMoment 和Moment 的执行效率.测试数据来自IBM 数据生成器，其中所包含的事务总数由参数H表示，每个事务的平均长度由T表示，最大潜在的频繁项集平均长度则为I，商品类别为N.这里利用生成的数据和T10.I10.N1000.D200K 数据进行实验来比较两种算法的效率.

本实验使用的硬件平台是Intel Pentium G60 处理器2.6 GHz，4 G 内存，采用Windows 7操作系统.算法由Java 实现，编译器为Oracle JDK 7.0.

在这个实验中，支持阈值可以在[0.05,1.00]范围内变化，并且窗口大小的变化规则是从20 kB 变化到100 kB.图4显示了这两种算法随窗口大小变化的操作时间图，当窗口设置为20 kB 时，算法Moment 和CFMoment 的操作时间分别为285 ms 和98 ms.随着窗口的扩大，Moment 和CFMoment 的操作时间不断增加.当窗口大小达到100 kB 时，Moment 算法和CFMoment 算法的操作时间分别为476 ms 和412 ms.可以看出，当窗口大小设置为20 kB 时，CFMoment 算法的执行速度明显快于Moment 算法，这是因为当项集被添加或取消时，CFMoment 算法并不修改ECET 树，而只是确定ECET 树的哪些节点将受到最新项集和最旧项集的交操作影响，从而完成对ECET 树的一次修改.而对于Moment 算法，只要有新的项集添加进来，CET 树就会被修改.当树被修改时，执行删除最旧项集的操作.因此，这种方式会导致窗口滑动时算法Moment 会连续修改CET 树，从而大大降低算法的效率.从图4还可以看出，当窗口接近最大值100 kB 时，这两种算法的运行速度几乎相同，这是因为当窗口大小为100 kB 时，两种算法几乎只要构建一次树结构就可以完成闭合频繁项集的挖掘.由于没有滑动过程，CFMoment 算法和Moment 算法的执行速度几乎相同.

图5显示了这两种算法在具有不同支持度阈值时的内存消耗，当支持度阈值为0.05时，CFMoment 算法和Moment 算法的内存消耗分别为88 MB 和277 MB.当支持度阈值接近1 时，两种算法的内存消耗均较低，但CFMoment 算法的整体内存不会有太大变化，这是因为当支持度阈值变小时会有更多的频繁闭项集.当Moment 算法寻找频繁闭项集时，必须连续修改CET 树.CET 树修改越频繁，内存消耗就越多.在CFMoment 算法中，虽然在支持度阈值较低的情况下可以挖掘相同数量的频繁闭项集，但在窗口滑动期间不必经常改变ECET 树，因此内存消耗很小.然而，当支持度阈值增加时，频繁闭项集的数量也减少，但此时Moment 仍然需要连续修改CET 树，因此其内存消耗必然大于CFMoment 算法.

图4 执行时间Figure4 Running time

图5 内存消耗Figure5 Memory consumption

4 结 语

本文提出的CFMoment 算法可以有效挖掘数据流中的频繁闭项集.在该算法中，ECET树用于记录当前窗口中的频繁闭项集，同时通过分析最新项目集和最旧项目集之间的关系来快速确定受影响项集的位置，并有效修改ECET 树.实验比较证明，CFMoment 算法的运行速度比Moment 更快，并且在数据流中挖掘频繁闭项集时所占用的内存资源更少.