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

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

V A

一_技应】嚣术用【

基于滑动窗口的数据流频繁项集挖掘方法丁邦旭(铜陵学院数学与计算机科学系安徽铜陵 24 0 ) 4 0 0

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

中图分类号：T 3 3文献标识码：A文章编号：1 7 -7 9 2 1 )0 1 1 2 2 P1 1 1 6 1 5 7( 0 2 3 5—0 0

0引言

向量表示方法。 表 1数据流事务序列Tl D Ie t msf . 3 f 1f.5 j I h 4

数据流是指连续产生的、快速、实时变化的有序数据序列。为了及时

得到最有用的信息，很多领域中对于数据流的处理已经成为人们关注的热点，比如网络监控、商品销售分析、股票的交易数据分析等。由于数据流

的大量性和瞬时性的特点，数据流频繁项信息会随着新数据的到达而不断发生变化，在有限的内存中无法存储全部数据，对于它的挖掘和存储都有一

,I3 1,I . I 2I 4l I I l h 2 s

定的难度。 数据流的特点要求挖掘算法只能经过一次扫描获得挖掘结果，并且要死

求较低的空间复杂度。因此，数据流挖掘面临着重大的挑战。挖掘数据流的频繁模式是数据挖掘重要的研究领域，陆续提出了一系列的相关算法。 C a g e在B S法的基础上，提出了基于滑动窗口模型挖掘最近的频 h n与L e T算

l“l 2l sI . I 、1 s

繁项集算法 s M 1[] ak与 Mt a i出了基于界标窗口的数据流频 w[] 2;Mn u o w n提繁项的挖掘算法，该算法在扫描一次数据的基础上得到整个数据流频繁项

表 2事务数据二进制表示TI D, l I1 e " DS t,, Bv c o et r l0l01

集

[] in e l等人提出挖掘滑动窗口中的频繁集算法[] 3;G a n la 4;张月琴提出了一种改进的滑动窗口频繁项集挖掘方法 NW 7。 S[]很多时候，人们更需要关注近期数据流的频繁模式信息。因此，挖掘近期数据流的频繁模式成为数据挖掘中一项具有实际意义的工作。基于滑动窗口的数据流频繁项集挖掘满足了人们对最近的信息更感兴趣的需要。 本文提出了一种基于滑动窗口的数据流频繁项集挖掘新算法M I,它采用 FM一

丘 ,]厶

,, 死。 n,乃，,,

0101 1 1 011 l010 10 1O0 0 1

在初始状态下，每个项的二进制向量所有元素均为 0。事务数据流开

种新的结构来记录频繁项集的动态变化，有效地挖掘数据流频繁项集[] 8。

始，当滑动窗口未满时，则新来的事务中每一项都被表示成二进制位向量的形式，更新每个项的二进制向量。当前的事务数超过窗口大小时，窗口 开始滑动，将每个项的二进制位向量按位向左移动，这种按位运算，即可移除窗口中最旧的事务，从而大大提高窗口的滑动速度。如果新来的事务中包含对应的项，左移后低位补 1,否则补O。在频繁项集产生阶段，通过位运算得到项集的支持数，降低了挖掘的

1问墨定义和描述定义1:设 I I,I,…, I}一个给定的数据项全集，I为第 i=(l 2 n是 个项 (≤ i )。项集 X 1≤n是数据项全集 I的子集 ( I,含有 k x )个项的项集

成为k项集，数据项全集的一个子集称为模式。一定义 2:事务T一个项集，数据流 ( aa S em是 D t ta )可以看成是一个连续到达的事务序列 D={1 2…,T) T为第 j事务，是 I一个子 S T,T, N, j个的集。设 T是数据流中到来时间最久的事务，T是数据流中最新到来的事 l N务。D中所有包含项集x s的事务个数称为项集x的支持数，占所有事务数的百分比称为支持度，记为sp() u X。定义3:设给定的支持度的闽值为 s,对于项集x,如果项集 X的支持度 sp(),则称项集x频繁项集。如果某一

数据项集的数据项不频繁， u x≥s是 则该项集一定不频繁。 定义4:将数据流 D分段，每一个分段对应一个数据流子序列且事务 s数一定，这样的一个数据分段称为一个滑动窗口，记为 s,它的大小为每 w

时间复杂度。并且，在挖掘过程中只存储二进制数据，空间开销相对很小。因而，采用二进制的事务矩阵的方法，能获得较小的时间复杂度与空间复杂度。

22算法基本思想 .算法根据A r o i质产生频繁项集：频繁项集的所有非空子集都必 pir性

须是频繁的，任何非频繁的 ( - )一集都不可能是频繁 k项集的子集。 ki项一 利用卜项集和 ( - )一 k i项集的按位与运算产生k项集的方法挖掘事务矩阵一中的频繁项集，并且在产生k项集的过程中通过删除L中不在L—中出现的一 1 k i

项集。挖掘步骤为：1 )根据用户定义最小支持度产生频繁卜项集 L,即：求每个项的行

个窗口能容纳的事务个数，是用户预先设定的大小w。当窗口被事务填满时，每当有一个新事务到达窗口，最旧的事务被滑出窗口。

向量中 i的个数 sm(,若 sm I) u h) u (t不小于最小支持数，则该行的项为频繁项。

2算法描述 2 1数据结构定义 .数据流中的事务数据结构是将每个项由包含它的事务表示，如果该项包含在某个事务中，则对应的二进制位为 i,否则为0即每个项以二进制，

2 )各项的行向量进行按位与操作，获得的二进制向量中 i的个数就是

该项集的支持数，不小于最小支持度的项即为频繁项集的成员。3 )继续产生 L、 I… L,直至无新的候选 (+ )一集产生，L u 3 J k 4 k1项 l

L u…L,输出结果，算法结束。 2 k2 3 M I算法 F M M I算法采用二进制向量表示数据项，用事务矩阵存储窗口事务数 FM

向量表示，最终构成一个事务矩阵。将表示项的二进制向量的长度制定为滑动窗口的大小。表 l为前 7事务序列数据表示：表 2个为事务数据二进制

本文来源：https://www.bwwdw.com/article/oy9j.html