基于滑动窗口的数据流频繁项集挖掘方法

摘 要： 数据流的特点要求挖掘算法只能经过一次扫描获得挖掘结果，并且要求较低的空间复杂度。结合数据流的特点，提出一种基于滑动窗口的数据流频繁项集挖掘新算法MFIM。该算法采用二进制向量矩阵表示滑动窗口中的事务序列，以这种新的结构来记录频繁项集的动态变化，有效地挖掘数据流频繁项集。理论分析与实验结果表明该算法能获得较好的时间复杂度与空间复杂度。

关键词： 数据流；数据挖掘；频繁项集；滑动窗口；二进制向量

中图分类号：TP311.13 文献标识码：A 文章编号：1671－7597（2012）0310152－020 引言

数据流是指连续产生的、快速、实时变化的有序数据序列。为了及时得到最有用的信息，很多领域中对于数据流的处理已经成为人们关注的热点，比如网络监控、商品销售分析、股票的交易数据分析等。由于数据流的大量性和瞬时性的特点，数据流频繁项信息会随着新数据的到达而不断发生变化，在有限的内存中无法存储全部数据，对于它的挖掘和存储都有一定的难度。

数据流的特点要求挖掘算法只能经过一次扫描获得挖掘结果，并且要求较低的空间复杂度。因此，数据流挖掘面临着重大的挑战。挖掘数据流的频繁模式是数据挖掘重要的研究领域，陆续提出了一系列的相关算法。Chang与Lee在BTS算法的基础上，提出了基于滑动窗口模型挖掘最近的频繁项集算法SWM[1][2]；Manku与Motwani提出了基于界标窗口的数据流频繁项的挖掘算法，该算法在扫描一次数据的基础上得到整个数据流频繁项集[3]；Giannella等人提出挖掘滑动窗口中的频繁集算法[4]；张月琴提出了一种改进的滑动窗口频繁项集挖掘方法NSW[7]。

很多时候，人们更需要关注近期数据流的频繁模式信息。因此，挖掘近期数据流的频繁模式成为数据挖掘中一项具有实际意义的工作。基于滑动窗口的数据流频繁项集挖掘满足了人们对最近的信息更感兴趣的需要。本文提出了一种基于滑动窗口的数据流频繁项集挖掘新算法MFIM，它采用一种新的结构来记录频繁项集的动态变化，有效地挖掘数据流频繁项集[8]。

1 问题定义和描述

定义1：设I={I1，I2，…，In}是一个给定的数据项全集，Ii为第i个项（1≤i≤n）。项集X是数据项全集I的子集（X I），含有k个项的项集成为k-项集，数据项全集的一个子集称为模式。

定义2：事务T是一个项集，数据流（Data Steam）可以看成是一个连续到达的事务序列DS={T1，T2，…，TN}，Tj为第j个事务，是I的一个子集。设T1是数据流中到来时间最久的事务，TN是数据流中最新到来的事务。DS中所有包含项集X的事务个数称为项集X的支持数，占所有事务数的百分比称为支持度，记为sup(X)。

定义3：设给定的支持度的阈值为s，对于项集X，如果项集X的支持度sup(X) s，则称项集X是频繁项集。如果某一数据项集的数据项不频繁，则该项集一定不频繁。

定义4：将数据流DS分段，每一个分段对应一个数据流子序列且事务数一定，这样的一个数据分段称为一个滑动窗口，记为SW，它的大小为每个窗口能容纳的事务个数，是用户预先设定的大小w。当窗口被事务填满时，每当有一个新事务到达窗口，最旧的事务被滑出窗口。

2 算法描述

2.1 数据结构定义

数据流中的事务数据结构是将每个项由包含它的事务表示，如果该项包含在某个事务中，则对应的二进制位为1，否则为0，即每个项以二进制向量表示，最终构成一个事务矩阵。将表示项的二进制向量的长度制定为滑动窗口的大小。表1为前7个事务序列数据表示；表2为事务数据二进制向量表示方法。

在初始状态下，每个项的二进制向量所有元素均为0。事务数据流开始，当滑动窗口未满时，则新来的事务中每一项都被表示成二进制位向量的形式，更新每个项的二进制向量。当前的事务数超过窗口大小时，窗口开始滑动，将每个项的二进制位向量按位向左移动，这种按位运算，即可移除窗口中最旧的事务，从而大大提高窗口的滑动速度。如果新来的事务中包含对应的项，左移后低位补1，否则补0。

在频繁项集产生阶段，通过位运算得到项集的支持数，降低了挖掘的时间复杂度。并且，在挖掘过程中只存储二进制数据，空间开销相对很小。因而，采用二进制的事务矩阵的方法，能获得较小的时间复杂度与空间复杂度。

2.2 算法基本思想

算法根据Apriori性质产生频繁项集：频繁项集的所有非空子集都必须是频繁的，任何非频繁的（k-1）-项集都不可能是频繁k-项集的子集。利用1-项集和（k-1）-项集的按位与运算产生k-项集的方法挖掘事务矩阵中的频繁项集，并且在产生k-项集的过程中通过删除L1中不在Lk-1中出现的项集。挖掘步骤为：

1）根据用户定义最小支持度产生频繁1-项集L1，即：求每个项的行向量中1的个数sum(Ii)，若sum(Ii)不小于最小支持数，则该行的项为频繁项。

2）各项的行向量进行按位与操作，获得的二进制向量中1的个数就是该项集的支持数，不小于最小支持度的项即为频繁项集的成员。

3）继续产生L3、L4…Lk，直至无新的候选（k+1）-项集产生，L1∪L2∪…Lk，输出结果，算法结束。

2.3 MFIM算法

MFIM算法采用二进制向量表示数据项，用事务矩阵存储窗口事务数据，利用事务矩阵的行向量与运算产生频繁模式。

算法：MFIM

输入：事务数据流DS，最小支持度s，滑动窗口大小w，SW=NULL

输出：窗口中频繁项集

Ti流入窗口SW

for Ti in SW｛//滑动窗口中每个事务

If(i≥1 && i≤w)

{ //窗口初始化阶段

将新事务Ti用二进制位向量的形式表示；

AddTrans(事务矩阵第i列，Ti)；

}

else

{ //窗口滑动阶段

各项对应的行向量按位左移；

AddTrans(事务矩阵第w列，Tn)；

由s产生L1={频繁1-项集}；

//产生k-项集Lk(k≥2)，矩阵运算

for项m in L1

for 项n in Lk-1

{

if（m与n的某一子集相同）

continue；

事务矩阵第m行向量和第n行向量按位与操作，得值sum；

//sum即为对应项集的支持数

if(sum≥s・w)

频繁项(m，n) Lk

if(项m not in Lk-1)

Delete(L1，项m)；

}

if(Lk+1 is NULL)

break;

}

MFIM_Output( )；

3 实验分析

图2 算法MFIM与MAFIA内存消耗比较

MFIM的算法采用C++语言实现，实验所需的数据采用IBM人工数据生成器GenData产生数据集T10I4D1000K，其中|T|表示数据集中事务的平均长度，|I|表示候选频繁项集的平均长度，|D|表示数据流中的事务总数。实验参数设定最小支持度阈值s=0.005，窗口大小w=10000，对MFIM算法和MAFIA算法进行了性能比较：图1是在窗口大小w=10000，挖掘事务数大小为1000000的前提下，MFIM算法和MAFIA算法随事务数变化运行时间比较，图2是内存空间消耗结果的比较。从实验数据对比可知，MFIM算法具有较好的性能。

4 结束语

本文提出了一种基于滑动窗口的数据流频繁项集挖掘的MFIM算法，能快速地在滑动窗口中挖掘频繁项集。滑动窗口中的事务序列采用二进制向量的事务矩阵表示，行向量按位与操作计算相应项集的支持度，能有效地提高算法的效率，通过直接删除最老的事务，压缩L1项集，直接得到相应k-项集，减少了算法的空间开销。实验证明，MFIM算法具有较小的时间和空间复杂度。

基金项目：铜陵学院自然科学基金（No. 2009tlxy28）

参考文献：

[1]Chang J H,Lee W S.A sliding window method for finding recently frequent itemsets over online data streams[J].Journal of Information Science and Engineering,2004，20（4）:753-762.

[2]Change J H,Lee W S.Online data stream mining of recent frequent itemsets by sliding window method[J].Journal of Information Science,2005,31(2):76-90.

[3]Manku G S,Motwani R. Approximate frequency counts over datastreams[C].//Proceedings of the 28th International Conference on VeryLarge Databases,2002:346-357.

[4]Giannella C,Han J,Pei J,et al. Mining frequent patterns in data streams at multiple time granularities[M].Data Mining Next Generation Challenges and Future Directions，Cambridge,Mass:MIT Press,2004:191-212.

[5]刘学军、徐宏炳、董逸生等，基于滑动窗口的数据流闭合频繁模式的挖掘[J].计算机研究与发展，2006，43（10）：1738-1743.

[6]李国徽、陈辉，挖掘数据流任意滑动时间窗口内频繁模式[J].软件学报，2008，19（10）：2585-2596.

[7]张月琴，滑动窗口中数据流频繁项集挖掘方法[J].计算机工程与应用，2010，46（16）：132-134.

[8]王磊、黄志球、朱小栋等，数据流中基于矩阵的频繁项集挖掘[J].计算机科学与探索，2008，2（3）：330-336.

作者简介：

丁邦旭（1977-），男，铜陵学院讲师，研究方向：人工智能，数据挖掘。