改进的多数据流协同频繁项集挖掘算法

王鑫 刘方爱

摘要：针对已有的多数据流协同频繁项集挖掘算法存在内存占用率高以及发现频繁项集效率低的问题，提出了改进的多数据流协同频繁项集挖掘（MCMDStream）算法。首先，该算法利用单遍扫描数据库的字节序列滑动窗口挖掘算法发现数据流中的潜在频繁项集和频繁项集；其次，构建类似频繁模式树（FPTree）的压缩频繁模式树（CPTree）存储已发现的潜在频繁项集和频繁项集，同时更新CPTree树中每个节点生成的对数倾斜时间表中的频繁项计数；最后，通过汇总分析得出在多条数据流中多次出现的且有价值的频繁项集，即协同频繁项集。相比AStream和HStream算法，MCMDStream算法不仅能够提高多数据流中协同频繁项集挖掘的效率，并且还降低了内存空间的使用率。实验结果表明MCMDStream算法能够有效地应用于多数据流的协同频繁项集挖掘。

关键词：

流数据挖掘；多数据流；滑动窗口；频繁项集；协同频繁项集

中图分类号： TP301.6 文献标志码：A

0引言

随着万维网技术的迅速发展，复杂多样的数据呈现爆炸式增长。数据流作为一种特殊形态的数据已在众多领域中广泛地应用，例如网络实时监控的数据[1]、传感器采集的数据[2]和金融市场的证券交易信息等。相对于传统静态数据而言，流数据具有实时、连续、大量、不确定和随时间变化的特点，因此，在不断变化的流数据上进行频繁项集挖掘更具有挑战性。

近年来，流数据频繁项集挖掘[3]成为研究的热点问题。1998年，Henzinger等[4]首次将流数据作为一种数据模型提出来。根据处理数据流时所采用的时序范围，将数据流模型划分为3个范畴：界标模型、快照模型和滑动窗口模型。以界标模型为基础，Manku等[5]提出了一种近似数据流频繁项集挖掘（Lossy Counting）算法，该算法能够有损耗地计算整个数据流中元素出现的近似频率，但因其效率不高、动态性不强；Yu等[6]提出了以假消极结果为导向在有限内存中挖掘数据流中频繁项集的流数据频繁模式挖掘（Frequent Data Stream Pattern Mining， FDPM）算法，但是Lossy Counting和FDPM算法只能得到近似的结果，因此，从流数据中获得当前准确频繁项集的科研成果随之涌现。Mozafari等[7]将滑动窗口引入数据流的传送中，并提出了一种新的技术概念Vertification，以此为基础设计了根据滑动窗口的大小调节性能和扩展性的滑动窗口增量挖掘（Sliding Window Incremental Miner， SWIM）算法。Leung等[8]构造了一种能够精确地挖掘数据流中频繁项集的新型树形索引结构（Data Stream Tree，请补充DSTree的英文全称。 DSTree）。以上算法只针对单数据流频繁项集的挖掘，但是结合当前的诸多应用，需要解决在多数据流环境[9-10]中频繁项集挖掘的问题，因此，Guo等[11]提出了HStream算法，目的是发现多数据流中的频繁项集问题。该算法以FPGrowth算法[12]为基础挖掘单条数据流中的频繁项集并将其频数存储于节点的自然倾斜时间窗口表中，通过汇总挖掘在多条数据流中多次出现的频繁项集。在此过程中需要多遍扫描数据库以及生成大量不必要的单位时间窗口，从而导致发现频繁项集时既耗时又浪费内存占用空间。

针对上述HStream算法低效、内存利用率不高的问题，本文提出了一种基于滑动窗口的多数据流协同频繁项集挖掘（Mining Collaborative Frequent Itemsets in Multiple Data Stream， MCMDStream）算法。该算法首先通过基于字节序列的滑动窗口挖掘（Ming Frequent Itemsets within a TimeInterval Sliding Window based on based on bitsequence， TISWMFI）算法发现数据流中的潜在频繁项集和频繁项集；然后构建CPTree用来存储多数据流中的频繁项集和潜在频繁项集，同时更新树节点中对数倾斜时间表中项集对应的频数；最后汇总分析得出多数据流中的协同频繁项集。与HStream算法中HTree的自然倾斜时间窗口表相比，MCMDStream算法中新引入的对数倾斜时间窗口表能够增量更新CPTree；同时还能够大量地减少节点总数，从而降低了算法的维护代价与空间复杂度；本文新引入的TISWMFI算法相比HStream中的FPGrowth而言，能够减少对数据库的遍历次数以及查询时间，因此，MCMDStream算法具有更强的适应性和扩展性。

1相关描述与问题定义

设S={S1，S2，…，Sn}为一组数据流集合，其中：Si表示一组大量的连续到达的流数据d1j，d2j，…，dij的数据序列，dij（i≥1，1≤j≤n）表示在第i时刻第j条数据流的值。

定义1项集I[5]。令I={i1，i2，…，im}为所有项的非空集合，其中m为项集的长度，包含k个项的项集称为k项集。例如项集{a，b}为2项集。

定义2事务数据流T[5]。表示一个连续的事务序列，即T=T1，T2，…，Tn，且TI。设Tid为事务数据流Ti的唯一标识符，TUid为时间单位标识符，事务T={TUid，Tid，Itemset}。

定义3滑动窗口SW[4]。指在单位时间内进行滑动的一个独立窗口，其中单位时刻TUi包含一个变量，即SW=[TUn-w+1，TUn-w+2，…，TUn]。其中：n-w+1表示当前滑动窗口单位时间标识号；w表示SW的总长度，且w=TUn-w+1+TUn-w+2+…+TUn。

定义4频繁项集（Frequent Itemset， FI）[4]。设项集X在滑动窗口SW中的支持度为Sup（X）SW，若Sup（X）SW≥θ·w，则称X为一个频繁项集（FI）。其中，θ（θ∈[0，1]）表示用户自定义的最小支持度阈值。

定义5协同频繁项集（Collaborative Frequent ItemsetCFI的英文全称补充得是否正确？请明确。， CFI）。设在给定数据流Si中的项集O，若tOSimax-tOSimin≤θ（tOSimax=max{t1，t2，…，tk}，tOSimin=min{t1，t2，…，tk}），则O是一个协同项集（Collaborative Itemset， CI）。若协同项集CI在随后给定的时间里以同样的方式在数据流集合Φ的数据流Si中频繁出现，则称CI为一个协同频繁项集。

定义6最大误差因子ε。令ε在系统允许范围内控制算法精度。若ε≤Sup（X）SW≤θ，则项集X为潜在频繁项集（Potential Frequent Itemset， PFI）；若Sup（X）SW≤ε，则项集X为非频繁项集（UnFrequent Itemset请补充PFI、UFI的英文全称。， UFI）。PFI、UFI都是针对特定时间段定义的。例如，在时间段t1内，项集X为FI；而在t2内，X可能为PFI或UFI。

2算法描述

在本文中，将多数据流协同频繁项集挖掘分为3步：

第1步利用新引入的TISWMFI算法从数据流中产生一组潜在频繁项集以及频繁项集；

第2步构建一棵基于字典序列的前缀树CPTree用来保存数据流中频繁项集动态的变化趋势，在此重新设计了CPTree结构，加入了对数倾斜时间窗口记录FI的频繁数；

第3步利用MCMDStream算法从潜在频繁项集中发现协同频繁项集。

2.1CPTree结构

结构上，CPTree由MTree、Header Table和Logarithmic Tilted Window三部分组成，该结构如图1所示。

1）MTree。记录频繁项集动态变化的一棵字典序列前缀树，用来存储数据流中频繁的和潜在频繁的项集。

2）Header Table。一个指向MTree中不同层中节点指针的数组。利用Header Table，能够高效地从MTree中挖掘出频繁的和潜在频繁的项集，减少更新树中频繁项集的时间，从而提高遍历树结构的效率。

3）Logarithmic Tilted Window。为了进一步地降低内存占用率以及算法的空间复杂度，新增加了对数倾斜时间窗口LW。滑动窗口SW由大小固定且连续的LW序列组成，记为{LW1，LW2，…，LWm}。在每个时间间隔内，LW为每个节点都创建了相对应的时间窗口表保留频繁项集的计数值。在n组数据流中，每个频繁项所需操作的数是对整个数据流数据进行操作的总数再除以N。

2.2TISWMFI算法

针对在有限的物理存储空间挖掘频繁项集会多次扫描数据库的问题，本文提出了一种新颖的单程扫描算法，即基于字节序列的滑动窗口挖掘（Ming Frequent Itemsets within a TimeInterval Sliding Window based on sequence of bytes， TISWMFI）算法，目的是挖掘给定时间t中SW内数据流Si的频繁项集。TISWMFI将SW内所有的数据项都以字节序列的形式表示，保证所有的项只被扫描一次，因此，该算法不仅能够提高内存利用率，而且还提高了动态存储事务的速度。

2.2.1字节序列表示法

字节序列表示法是指用二进制位（0或1）表示在SW内数据流Si的事务Ti中项X的支持度计数Sup（X）和出现的频数fx，项X的字节序列表示为Bit（X）。设在当前SW中项X存在于Ti中，则项X的第i位记为1，即Bit（X）=1；否则记为0，即Bit（X）=0。随着窗口的不断滑动，需要维护项的字节序列，因此，在计算Sup（X）时，2个k项集的字节序列进行“按位与”操作，便得到（k+1）项集（k≥0）的字节序列；而在进行删除操作时只需将原有的字节序列按位左移一位。该方法能够使窗口快速地滑动而且还能用较小的存储空间保存所有项集出现的情况。

在滑动窗口SW1和SW2中的事务数据流的项集字节序列为例。在表1中，SW1由〈T1，（abc）〉、〈T2，（bce）〉和〈T3，（abce）〉三条事务组成，并且项a在SW1的T1和T3中存在，因此Bit（a）=101、Bit（b）=111、Bit（c）=111、Bit（d）=000和Bit（e）=011。

2.2.2TISWMFI算法描述

TISWMFI算法由窗口初始化、窗口滑动和频繁项集生成3个阶段组成。具体过程如下。

步骤1滑动窗口初始化阶段。当SW=Null时，将单位时间TUi内事务Ti中所有项按照字节序列表示法将其转变为相对应的字节序列，直到SW=Full时结束。

步骤2窗口滑动阶段。在步骤1的基础上，将项X的字节序列“按位左移”即可将当前SW中失效事务中的项集移除。若Sup（X）SW=0，则可删除项X。

步骤3频繁项集产生阶段。即已知的频繁（K-1）项集以逐层迭代的方式构成候选K项集，并将相应的字节序列作“按位与”操作计算频繁项集的支持度，即Bit（X）中字节1的总数。主要子步骤如下：

1）单遍扫描数据流Si，计算每个项的支持度，删除支持度小于θ的项，构成频繁1项集FI1；

2）将两个FI1以自连接的方式构成包含候选2项集，保留支持度大于θ的项，形成频繁2项集FI2；

3）以此类推，逐层迭代，直到没有新的频繁项集产生为止。

滑动窗口SW1和SW2四条事务数据流中的频繁项集如表2所示，SW2由事务T2、T3和T4组成，现以SW2中频繁项集生成过程为例。设θ=0.6，w=3，Sup（X）SW2=0.6×3=1.8。由此可得，Sup（b）=111、Sup（b）=3>1.8，Bit（c）=110、Sup（c）=2>1.8和Bit（e）=110、Sup（e）=2>1.8，即（b）、（c）和（e）构成FI1；利用FI1执行“按位与”操作，得到FI2，Bit（bc）=Bit（b） & Bit（c）=110、Sup（bc）=2，同理，Sup（be）=2、Sup（ce）=2；利用FI2执行“按位与”操作，得到FI3，Bit（bce）=Bit（bc） & Bit（be） & Bit（ce），Sup（bce）=2>1.8，因此，FI3为（bce）。

2.3MCMDStream算法

MCMDStream算法将TISWMFI算法中发现的频繁项集保存在CPTree中，由θ控制FI的数量，ε控制CPTree剪枝率；其次，通过插入新的FI、PFI和删除UFI持续更新CPTree；最后，深度优先遍历CPTree发现多条数据流中的协同频繁项集。假设n条数据流Si的集合Φ以批处理的方式挖掘，其中在时间间隔ti（i≥1）产生的第j（1≤j≤n）条数据流被标记为dij，遍历自定义数据结构中的频繁项集。多数据流协同频繁项集挖掘算法伪代码如下。

有序号的程序——————————Shift+Alt+Y

程序前

输入：用户自定义的最小支持度阈值θ；n条数据流集合S；最大误差率ε；协同频繁项集集合α。

输出：协同频繁项集。

//步骤1：Construct CPTree

1）

FI=Null， PFI=Null， i=1；

2）

for j=1 to n do

3）

FI= FI∪TISWMFI（dij，θ）；

PFI=CI∪TISWMFI（dij，θ，ε）；

4）

end for

5）

MTree=Initialize_MTree（FI，PFI）

//步骤2：Update CPTree

6）

While S≠Null do

7）

I=Null，i=i+1；

8）

Ci1，Ci2，…，Cin=Preprocessing（di1，di2，…，din，MTree，θ，ε）

9）

for j=1 to n do

10）

I=I∪TISWMFI（Cij）；

11）

end for

12）

MTree=Insert_CPTree（I），MTree=Prune_CPTree（MTree，θ，ε）；

13）

end while

//步骤3：Mining collaborative Frequent Itemsets across //Multiple Streams（在多数据流中挖掘协同频繁项集）

14）

CFI=Collaboration_Mining（α）

15）

Output CFI

程序后

具体算法步骤如下。

步骤1利用TISWMFI算法从第一批数据流dij中提取FI和PFI。

步骤2构造CPTree，并初始化CPTree的MTree、Header Table和Logarithmic Tilted Window。计算各项集在指定时间窗口内的平均频数并降序排列。将所有数据项E∈{FI∪PFI}插入到MTree中；同时将所有数据流中数据项E的频繁项计数写入每个节点相对应的对数时间窗口表中。根据频繁计数对数据项E分类，同时，在Header Table增加一个指针指向MTree每一层首节点。

步骤3利用最新的数据流更新MTree。该过程有如下4个子步骤：

1）预处理最新的数据流，删除dij中的UFI。

2）查找项集I，在每一条被预处理的数据流中查找未被剪枝的项集。

3）将数据项集I插入MTree中，若I已插入树中，则仅更新窗口表中相对应数据项的计数值；否则，将在MTree插入I，同时更新CPTree的三部分。

4）调用末端剪枝函数Prune_CPTree（）删除窗口末端的UFI。

步骤4当所有的数据流更新完成后，深度优先遍历MTree，在多数据流集合Φ中挖掘协同频繁项集CFI。

2.4算法性能分析

3实验结果与分析

实验环境配置为：Windows 7 Professional操作系统，Intel Core CPU i33220 @2.93GHz，1TB RAM。使用Microsoft Visual C++ Version 6.0实现算法以及数据流模拟生成模块。模拟实验主要从存储代价、算法响应时间、查准率和查全率4个方面分别对AStream、HStream和MCMDStream算法进行对比分析。其中AStream算法是基于Aprior算法的挖掘频繁项集的算法，通过对数据流进行多次扫描、自底向上的宽度优先搜索得到协同频繁项集的一种算法。测试数据集是由IBM Quest MarketBasket合成数据生成器产生的6条数据流。每条数据流中包含2000个事务，其中：TLen表示每个事务的平均长度，NItems表示每个事务中每个项集的平均长度，如表3所示。

3.1存储代价

内存使用量影响着算法的可扩展性，将MCMDStream与另外两个多数据流频繁项集挖掘算法AStream和HStream进行对比。假定在已处理的数据规模不变的情况下，测试IBM合成6条数据流分批到达构建CPTree树结构时所产生的节点的总数。在最小支持度阈值和最大误差率不变的前提下，分批处理事务数据流长度为5～30，步长为5。当所有的数据项插入CPTree后，各算法生成树节点的总数如图2所示。

从图2可得，MCMDStream算法中树结构生成的节点数量与AStream和HStream相比最少，因此所占用的内存空间最小，算法的存储空间最低，即MCMDStream算法的空间复杂度较小。这是因为AStream算法仅用ε控制树的剪枝率，因此包含了大量的潜在频繁项集，HStream使用θ与ε同时控制剪枝率，而MCMDStream算法在使用θ与ε控制CPTree剪枝率的基础上采用对数倾斜时间窗口，减少了每个节点中时间窗口的数量，便于冗余剪枝。最终减小了树结构的内存使用率，从而降低了存储代价。

3.2算法响应时间

该算法根据不同的支持度阈值产生不同的响应时间。测试各算法在IBM合成的6条数据流的响应时间。设在IBM数据集的支持度阈值变化范围为1～5，步长为1。实验结果分别如图3所示。

从图3中得出，HStream算法具有较高的事务敏感性。当事务数据量逐渐增大时，该算法因受剪枝策略的影响会产生较冗余的分支。HStream算法是在FPGrowth算法的基础上进行频繁项集挖掘，不仅需要扫描两遍数据库，而且还会产生大量的候选频繁项集，因此在进行挖掘过程中消耗大量的时间。MCMDStream算法是基于字节序列的滑动窗口的频繁项集挖掘，其在查询过程中，只需建立一棵频繁模式树且只扫描一遍数据库，因此节省了查询响应时间，从而降低了MCMDStream算法的时间复杂度，查询效率高于HStream和AStream。

3.3查准率和查全率

最大误差值ε是算法中一项重要的剪枝参数，查准率是指算法发现的实际协同频繁项集数与算法发现输出数量的百分比，而查全率则为算法发现的实际协同频繁项集数与真实数量的百分比。挖掘数据集的协同频繁项集以最大误差值ε作为剪枝参数，在更新树结构时能够影响算法的查准、查全率。图4～5分别评估了在IBM合成的6条数据流中不同误差值对算法查准、查全率的影响。假定误差值ε分别为0.0002，0.0008，0.0014和0.002时IBM合成数据流中S1、S2和S3三条数据流的查准率和查全率。

从图4和图5中可以看出，对于不同的误差值，MCMDStream算法的查准率和查全率高于其他算法。当误差值增大时，频繁项集的数量减少，因此用户指定的误差值越大，频繁项集数量越少，挖掘多条数据流中的协同频繁项集时的准确率和查全率就会越高。

4结语

本文提出了一种能够高效地挖掘多数据流协同频繁项集的MCMDStream算法。该算法不仅能够减小内存利用率、缩短挖掘的查询响应时间，而且还可以提高算法的查准率和查全率。模拟实验利用IBM合成数据集验证了该算法的性能优于AStream和HStream算法，能够很好地应用于多数据流协同频繁项集的挖掘，但是本文只考虑了单机上的多数据流频繁项集挖掘问题，在今后的研究中，将采用分布式集群这一有效的途径，实现大规模多数据流中协同频繁项集发现问题。

参考文献：

[1]

BHATTACHARYA S， MOON S. Network performance monitoring and measurement： techniques and experience [M]// Universal Access in HumanComputer Interaction. Access to Interaction. Berlin： Springer， 2015： 528-537.

[2]

王爽，王国仁.面向不确定感知数据的频繁项查询算法[J].计算机学报，2013，36（3）：571-581.（WANG S， WANG G R. Frequent items query algorithm for uncertain sensing data [J]. Chinese Journal of Computers， 2013， 36（3）： 571-581.）

[3]

金澈清，钱卫宁，周傲英.流数据分析与管理综述[J].软件学报，2004，15（8）：1172-1181.（JIN C Q， QIAN W N， ZHOU A Y. Analysis and management of streaming data [J]. Journal of Software， 2004， 15（8）： 1172-1181.

[4]

HENZINGER M R， RAGHAVAN P， RAJAGOPALAN S. Computing on data streams [C]// Proceedings of the 1999 External Memory Algorithms： DIMACS Workshop External Memory and Visualization. Boston： American Mathematical Society， 1999： 107-118.

[5]

MANKU G， MOTWANI R. Approximate frequency counts over data streams [C]// Proceedings of the 28th International Conference on Very Large Data Bases. [S.l.]： VLDB Endowment， 2002： 346-357.

[6]

YU J， CHONG Z， LU H， et al. False positive or false negative： mining frequent itemsets from high speed transactional data streams [C]// Proceedings of the Thirtieth International Conference on Very Large Data Bases. [S.l.]： VLDB Endowment， 2004： 204-215.

[7]

MOZAFARI B， THANKKAR H， ZANIOLO C. Verifying and mining frequent patterns from large windows over data streams [C]// ICDE 2008： Proceedings of the IEEE 24th International Conference on Data Engineering. Piscataway， NJ： IEEE， 2008： 179-188.

[8]

LEUNG C K S， KHAN Q. DSTree： a tree structure for the mining of frequent sets from data streams [C]// ICDM06： Proceedings of the 2006 Sixth International Conference on Data Mining. Piscataway， NJ： IEEE， 2006： 928-932.

[9]

HRISTIDIS V， VALDIVIA O， VLACHOS M， et al. Information discovery across multiple streams [J]. Information Sciences， 2009， 179（19）： 3268-3285.

[10]

YEH M Y， DAI B R， CHEN M S. Clustering over multiple evolving streams by events and correlations [J]. IEEE Transactions on Knowledge and Data Engineering， 2007， 19（10）： 1349-1362.

[11]

GUO J， ZHANG P， TAN J， et al. Mining frequent patterns across multiple data streams [C]// Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 2325-2328.

[12]

HAN J， PEI J， YIN Y， et al. Mining frequent patterns without candidate generation： a frequentpattern tree approach [J]. Data Mining and Knowledge Discovery， 2004， 8（1）： 53-87.

[13]

CHANG J H， LEE W S. Finding recent frequent itemsets adaptively over online data streams [C]// Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2003： 487-492.

[14]

AGRAWAL R， SRIKANT R. Privacypreserving data mining [C]// Proceedings of the 2009 ACM SIGMOD Record. New York： ACM， 2000， 29（2）： 439-450.

[15]

BERNECKER T， CHENG R， CHEUNG D W， et al. Modelbased probabilistic frequent itemset mining [J]. Knowledge and Information Systems， 2013， 37（1）： 181-217.