吴丹　刘贺

基金项目：长春理工大学经济管理学院大学生创新创业训练项目《可视化流数据挖掘的交互平台》;项目编号：201910186046。

摘要：近些年来，在数据流环境下进行数据挖掘已得到该领域的热点关注。数据流与静态数据有很大不同，它具有无限、连续、高速和实时等动态特征，这就使得以往传统的频繁项集挖掘算法不在适用数据流环境。因此，本文将针对数据流环境下的频繁项集挖掘进行研究，将其分为三个方面，分别对其代表算法进行详细分析，做出对比并进一步总结，为学者们呈现出数据流挖掘在过去十余年中的发展，同时总结现有研究中存在的不足，提出未来可能的研究方向。

关键词：数据流;频繁项集挖掘

中图分类号：TP18;O157.5文献标识码：A文章编号：1672-9129（2020）07-0060-02

Abstract：In recent years， data mining in the data flow environment has attracted much attention in this field. Data flow is very different from static data. It has such dynamic characteristics as infinite， continuous， high speed and real time， which makes the traditional frequent itemset mining algorithm not suitable for data flow environment. Therefore， this article will focus on data flow under the environment of frequent itemsets mining， which can be divided into three aspects， the detailed analysis of its representative algorithms respectively， make a comparison and summary， further present a data stream mining for scholars in the past more than ten years of development， summarizes the existing shortcomings in the course of study at the same time， the future research direction is put forward.

Key words：data flow;Frequent itemset mining

1數据流环境中的频繁项集挖掘概述

数据流环境下的频繁项集挖掘是一个重要的研究内容，当前的频繁项集挖掘研究中主要有3个分支：挖掘完全频繁项集、频繁闭项集与最大频繁项集。

1.1获得完全频繁项集的方法。完全频繁项集中包含的项集数量巨大，其经典算法是LossyCounting算法。为了体现不同时段数据的时效性，韩家炜等人于2003年首次将时间粒度的概念与窗口模型相结合提出了著名的FP-stream算法[1]。

（1） FP-stream算法。FP-stream算法在FP-growth算法的基础上，构建并维护一个嵌入倾斜时间窗口信息的Pattern-tree结构，存储和压缩频繁模式。核心步骤如下：

①倾斜窗口及其更新。倾斜时间窗口用来维护频繁模式信息，其对应的时间窗口时刻为t，t，2t，4t，…2nt。当一批新事务B抵达倾斜时间窗时，若时刻未达2nt，需引进中间缓冲窗口，到满后合并缓冲窗口并更新到下一窗口，直到更新完2nt的时间窗。

②频繁模式的更新及pattern-tree的建立。i=1，首批事务B1抵达，清空结构树。计算事务各项支持数，递减排序创建有序列表List，并按此顺序对数据项进行排序。当B1完全到达，按照List表顺序构建FP-tree，并删除所有支持度计数f<εB1的项。利用FP-growth算法对FP-tree挖掘所有的ε-频繁项集以创建pattern-tree，随后丢弃内存保留的批事务B1及FP-tree。

i>1，随后抵达的每个批事务，采用相同处理方式：清空FP-tree，将每个事务t按List顺序插入FP-tree。当前Bi处理完后，利用FP-growth算法挖掘出FP-tree树结构中的所有频繁项，并采用如下方法更新pattern-tree。

③Pattern-tree的更新。

1）查询I是否存在于pattern-tree中。如果存在，在i的倾斜时间窗口表中增加i的出现次数，同时对时间窗口表进行尾剪枝操作。如果更新后i的倾斜时间窗口表为空，算法将停止挖掘i的所有超集，并在深度扫描pattern-tree时删除项集i及其超集;否则，继续挖掘i的超集;如果不存在，但fi≥εBi，将I插入pattern-tree中。

2）借用深度优先搜索算法扫描pattern-tree，对于每一个未更新的项集在时间窗口中插入0，并进行尾减枝。扫描项集I和其超集及超集兄弟结点，判断对应的倾斜时间窗表是否为空，如果为空，删除对应的结点。

FP-stream算法存在许多问题：（1）构建FP-tree时需两次扫描数据库;（2）挖掘频繁模式时需大量动态的生成和释放FP-tree结构;（3）FP-stream采用自底向上遍历，查找和更新速度较慢。

（2） PSW算法。黄威于2010年提出了基于滑动窗口的数据流频繁项集挖掘算法——PSW算法[2]。PSW算法提出PSW-tree，使频繁项集的挖掘和更新在PSW-tree中同时进行，较FP-stream算法在挖掘频繁模式时需要大量动态的生成和释放FP-tree结构有更好的时空效率。

核心步骤如下：

①PSW-tree的建立。PSW-tree是基于FP-tree的改进模式树，用child-link和brother-link链接节点，对数据项进行自顶向下索引，存储（临界）频繁模式。将基本窗口BW1挖掘得到的（临界）频繁模式加入到树中，为每一节点分配滑动窗口表，用来记录最近几个基本窗口计数，当新W1中事务到达完毕，将I-count插入到W1计数中。

②PSW-tree的更新。若事务t的滑动窗口表中非频繁，则其进行预剪枝，清空Wt，用于记录下一次新的基本窗口计数;如果Wt不为空，且t的孩子子树不为空，采用合并策略，把t的孩子子树的节点计数合并到其兄弟子树中;若孩子子树为空，进行尾剪枝。

随后，杜志刚于2012年提出MFIS-stream算法[3]，在黄威算法的基础上提出FIS-tree结构，添加信息窗口列表W于各项末节点，记录末节点的窗口位置和出现次数，通过该节点的位置信息可快速找到旧窗口中的事务，只需删除末节点列表中含i的项，就可快速更新数据。

1.2获得频繁闭项集的方法。在数据挖掘所生成的完全频繁项集中，有相当大一部分是冗余的信息，降低时间、空间效率。频繁闭项集可以在保证没有信息损失的基础上，减少冗余的频繁项集，其经典算法为Closet，但在数据流挖掘的情况下并不适用。

（1）Moment算法。Moment算法[4]用加入了交易表TID的FP-tree来存储窗口中的数据;用CET结构来挖掘FP-tree中的闭频闭繁项集和潜在闭频繁项集;利用哈希表（Hash Table）来维护CET中的闭频繁项集。

①创建CET。在FP-tree中判断节点类型，创建只含频繁闭项集及频繁闭项集和其余项集之间的边界项集的CET数据结构。对任一节点ni，查看哈希表，若节点ni既不是非频繁的也不是无希望的，则查看子节点，判断ni是一个中间节点还是闭合节点。

②CET的维护过程。当新事务被添加到窗口或删除时，从根节点开始递归进行检验所有相关节点的类型是否发生变化。新事务t可能导致ni更改其节点类型的情况如下：

1）ni为非频繁节点。若ni变得频繁，必须检查ni兄弟节点能否创建出包含ni的子节点，若创建成功，调用函数判断节点类型;

2）ni为无希望节点。若包含ni兄弟节点的子节点支持数小于ni的支持数，则ni将变为有希望节点，原来被修剪的分支需重新判断节点类型;

3）ni为闭合节点。假设添加事务t，ni将保持为一个闭合节点，但会更新其在哈希表中的条目数量;

4）ni为中间节点。当ni的一个子节点具有与它相同的支持数s时，其仍为中间节点;如果新添加的事务t包含ni，并且ni的子女中没有一个和它有相同的s時，ni变为闭合节点。

Moment算法的不足之处：（1）CET存在非闭项集，且判断结点类型将耗费大量时间;（2）算法运行完整的更新过程，当添加的新事务与删除的旧事务一致或存在共有项时，可能使内存中的数据结构出现大幅波动。

（2） CFMoment算法。针对Moment算法可能出现的数据颠簸问题，王金伟等人于2018年提出了一种高效的数据流频繁闭项挖掘算法CFMoment[5]。当项集被添加或删除时，并不直接修改CET树，而只确定CET树的哪些节点受新项集和旧项集的操作影响。

CFMoment算法对CET树更新的改进之处：

当窗口滑动时能对CET产生影响的有最旧事务top的删除和最新事务bottom+1的添加，此算法利用这一点，首先判断top和bottom+1事务是否相同，若相同，则不更新CET，反之，取两事务交集，记为i，将top-i的所有子集加入minus，将（bottom+1）-i的所有子集加入plus，调用函数对这两项集的单项集进行频繁性检查。若某单项由频繁变为非频繁，则原包含它的频繁闭项集都将被去除;反之，保持不变。

1.3 获得最大频繁项集的方法。挖掘最大频繁模式的算法时空效率比其他两种更高，其经典算法是Chang等提出的estDec+算法，采用时间衰减机制降低历史数据的支持度作用。

（1） BFPM-Stream算法。在现实中，数据流速非恒定是很常见的，它会导致待处理数据不稳定的现象。针对此问题，陈艳于2010年提出BFPM-Stream算法[6]，借助将时间和事务相融合的滑动窗口，用位对象表示数据和位频繁模式树BFP-Tree进行数据存储，解决了数据流的流速不确定性问题。

基本思想如下：

①事务和时间相结合的滑动窗口。非恒定流速的数据流挖掘，需先设置一批事务数阈值N和时间阈值T。满足任何一个参数，便可将其作为当前滑动窗口，将其所包含的事务集作为等待挖掘的项集。

②带权的位对象数据格式。将滑动窗口中的事务用带权的位对象表示，即用固定长度的二进制位表示模式的一个位串，窗口W内的模式x的二进制位记为T（x），若x在W内的第i个事务中存在时T（x）的第i位为1，反之为0。

③位频繁模式树的建立

扫描滑动窗口中的事务，得到所有频繁模式及其支持数，按支持度降序排序，得到频繁项目头表List和项目位权表;将中值为1的位所对应的位权逐个插入到模式树中。

（2）MMFI-DS算法。挖掘最大频繁项集需不断计算数量庞大的项集支持数，比较耗时。毛伊敏于2011年提出了最大频繁项集挖掘算法MMFI-DS[7]。SEFI-tree结构采用自底向上和自顶向下策略，存储最大频繁项集的有关信息，删除过长的最大频繁项集的子集和非频繁项集的超集，减少计算项集支持度所消耗的时间。

主要内容如下：

①SEFI-tree的构造和维护。将数据流中每个项插入到SEFI-tree中，将每个事务的子集插入到存储结构OFI-list中。读完一个基本窗口的数据，删除FI-list指向EIS-tree具有相同的I-item所有不频繁的结点的所有信息。

②最大频繁项集的挖掘。FI-list中各节点对应的OFI-list中的各项通过组合产生项目集与该节点合并，得到最大频繁候选集。将该最大频繁候选集平分到项集E1、E2里。对E1自顶向下搜索，将频繁项集放入MFI项集中，并删除E2中该项的子集;对E2自底向上搜索，若频繁项集不是MFI的子集，则将其频繁项集放入MFI中，否则从E1中减去含有E2的超集。

2结语

本文着重对关联规则挖掘中的完全频繁模式、频繁闭模式和最大频繁模式的代表算法进行了分析，并进行对比总结。但各种算法的性能对于不同数据集产生不同作用，没有一种算法能够适应所有的数据集满足所有的需求。目前，随数据流越来越多，模式数量巨大，如何在满足用户不同需求的同時尽可能的使模式压缩;如何结合近几年的云计算发展来提高数据挖掘效率等成为研究者进一步的研究方向。

参考文献：

[1]Giannella G Hanj.Yup.Mining Frequent Pattern sin Data Stream sat Multiple Time Granularities.Data Mining：Next Generation Challenges and Future Directions.2004.191-212.

[2]黄威.数据流的频繁模式挖掘算法研究[D].西安科技大学，2010.

[3]杜志刚.基于数据流的挖掘算法研究[D].西安科技大学，2012.

[4]Chi Y，Wang H，Yu P.Catch the moment：maintaining closed frequent itemsets over a data stream sliding window.Knowledge and Information Systems，2006，10（3）：265-294.

[5]王金伟，吴少华，瞿治国.CFMoment：挖掘数据流频繁闭项集算法[J].应用科学学报，2019，37（3）：389-397.

[6]陈艳.数据流的最大频繁模式挖掘研究[D].西安科技大学，2010.

[7]毛伊敏.数据流频繁模式挖掘关键算法及其应用研究[D].中南大学，2011.

作者简介：吴丹（1999-），女，汉族，河北唐山市人，本科生，单位：长春理工大学经济管理学院信息管理与信息系统专业，研究方向：大数据研究。