基于动态窗口数据流频繁闭合模式挖掘算法

《基于动态窗口数据流频繁闭合模式挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、信息与电脑算法语言ChinaComputer&Communication2009年第10期基于动态窗口的数据流频繁闭合模式挖掘算法陆楠深圳大学计算机与软件学院，广东深圳518060李晓林深圳慧瑞信息系统有限公司，广东深圳518060摘要：本文根据数据流的特点，提出了一种基于动态窗口的频繁闭合模式的新方法DSFIS。它将滑动窗口分割成基本窗口作为更新单位，计算每个基本窗口的潜在频繁闭合项集，将它们存储到一种新的数据结构中，并进行增量更新，利用该数据结构可以快速地挖掘滑动窗口中的所有频繁闭合项集。通过实验验证了该算法在时间上和空间上的可行性和有效性。关键词：关联规则；数据挖掘；数据流；滑

2、动窗口；频繁闭合模式中图分类号：TP391文献标识码：A文章编号：1003-9767(2009)10-0100-03AMiningAlgorithmBasedOnDynamicWindowofFrequentClosedPatternsAboutDataStreamLuNanCollegeofComputer&SoftwareShenzhenUniversity518060LiXiaolinShenzhenPowerrichInformationSystemLitCo518060Abstract:Accordingtothecharacteristicsofthedatastream

3、,thispaperputsforwardanewmethod,DSFIS,basedondynamicwindowoffrequentclosedpatterns.Itdividestheslidingwindowintoseveralbasicwindows,eachasanewunitandcalculatespotentialfrequentcloseditemsetsofeachbasicwindow,andstorestheminanewdatastructurebytheincrementalupdating.Usingthedatastructurecanquickl

4、yminingallfrequentcloseditemsetsintheslidingwindow.Throughtheexperiment,Itvalidatesthealgorithm’sfeasibilityandavailabilityintimeandspace.KeyWord:Associationrules;Datamining;DataStream;Slidingwindow;frequentclosedpatterns1.引言记作，它所容纳的基本窗口的数目是一个定值数据流是潜在的、连续快速的、随时间不断变化的数据序列，由k，如图1所示

5、。于数据流的无限性和流动性，传统的数据挖掘算法在数据流中并不适随着新数据的到来，滑动窗口以基本窗口为单位不断更新，每进用，挖掘数据流中的频繁模式已成为数据挖掘的热点之一。近年来，入一个新的基本窗口，最旧的一个基本窗口被删除，滑动窗口随之更陆续提出了一些关于数据流频繁模式的挖掘算法。新一次，因此，滑动窗口中包含的数据不断变化和更新。在动态数据流环境下，基于窗口的数据流挖掘模型主要有三种：定义3：将所有包含项集X作为子集的事务的tidset记做t(X)，快照窗口（起始时间和结束时间都固定）、界标窗口（起始时间固将事务集Y中所共有的项集记做i(Y)，则X的闭合项集c(X)=i(t(X))。

6、定、结束时间变化）和滑动窗口（起始时间和结束时间均变化）。若X=c(X)，则称X为闭合项集。如果X的支持度大于最小支持度目前大多数频繁模式挖掘算法都是建立在快照窗口或界标窗口，minsup，那么X即为频繁闭合项集。而基于滑动窗口的挖掘算法相对较少，原因在于滑动窗口包含的数据一个闭合项集对应着一部分具有相同支持度的项集的集合，而且集既增又减，因此，其频繁模式的挖掘更为困难。Teng等人提出了滑这部分项集都是该闭合项集的子集。所有闭合项集唯一确定了所有项动窗口中的时态频繁模式挖掘方法，为每个频繁项集存储一个ATF压集。缩形式，利用ATF可以近似计算滑动窗口中的频繁项集，但是，当频定义4：

7、设给定支持度s和允许误差值ε，

8、N

9、表示窗口（基本窗口繁模式较长或窗口中频繁模式数量很大时，算法存在很大的模式延或滑动窗口）中的事务数，窗口中项目集X的支持数为sup(X)，如果迟。而且算法的精度与每个小分段数据是否满足线性关系直接相关。有sup(X)>(s-ε)

10、N

11、，则称X为窗口中的频繁项集；如果sup(X)>ε

12、N

13、，本文提出了一种动态窗口下数据流频繁闭合模式挖掘新算法，它则称为窗口中的潜在频繁项集；如果sup(X)≤ε

14、N

15、，则称为窗口中的采用一种