![](https://csdnimg.cn/release/download_crawler_static/18270299/bg1.jpg)
收稿日期:20190106;修回日期:20190318 基金项目:国家重点研发计划重点专项资助项目(2017YFC0803700)
作者简介:吉小洪(1994),男,硕士,主要研究方向为数据挖掘、大数据分析;徐爱萍,女(通信作者),教授,博导,主要研究方向为文本分析、大
数据分析(xuaiping@whu.edu.cn).
基于 triemerging机制数据流滑动
窗口模型的频繁树模式挖掘
吉小洪,徐爱萍
(武汉大学 计算机学院,武汉 430072)
摘 要:因树型结构的良好表达能力,在互联网中传输的信息流越来越多以树型结构形式存储。但由于流式数
据的时效性,隐含在数据流中的知识会随着时间的推移发生改变。针对数据流场景下挖掘最近时间段内的频繁
子树模式的问题,提出了一种滑动窗口模型下挖掘频繁子树模式算法———SWMiner算法,用于挖掘数据流下任
意时刻窗口所有的频繁子树模式。SWMiner算法使用基于前缀树的结构来压缩存储生成的树模式,并且使用
triemerging机制有效地更新子树模式的支持度。实验结果表明,SWMiner算法在滑动窗口模型中的性能优于目
前现有的常用算法,能有效地挖掘最近时间段内的频繁树模式。
关键词:trie树;数据流;滑动窗口;频繁树模式
中图分类号:TP391 文献标志码:A 文章编号:10013695(2020)07015199306
doi:10.19734/j.issn.10013695.2019.01.0006
Triemergingapproachforminingfrequenttreepatternover
datastreamslidingwindow
JiXiaohong,XuAiping
(SchoolofComputer,WuhanUniversity,Wuhan430072,China)
Abstract:Duetothegoodexpressingpowerofthetreestructureddataformat,thedatastreamtransmittedontheInternetis
preferredstoredinatreestructure.However,knowledgeembeddedinadatastreamismorelikelytobechangedovertime,
consideringtheproblemoffindingrecentfrequenttreepatternsoveradatastreamslidingwindow,thispaperproposedame
thodSWMinerwhichusedtominerecentfrequenttreepatternsoverslidingwindow
,itusedtominedtherecentfrequenttree
patternatanytimestep.SWMinerusedatriebasedstructuretocompactlystorethetreepatternsandtriemergingapproachto
supportupdatingsupportofpatternefficiently.Itconductedextensiveexperimentsonseveralsyntheticandrealdatasets.The
resultsofexperimentshowthatSWMinerperformsmuchbetterthanthewellknownexistingalgorithmandcanfindtherecent
frequenttreepatternefficiently.
Keywords:trietree;datastream;slidingwindow;frequenttreepattern
0 引言
传统研究中,数据挖掘往往处理的是结构规整的数据,例
如,事务数据库或关系数据库,其数据是以表格结构的形式排
列的。相反,存在于互联网中的
XML、JSON和 ProtocolBuffer
等都是树型结构数据。与传统的关系数据模型相比,树型结构
数据格式能够表达更复杂的数据类型,包括数据的嵌套、重复
和缺失值
[1]
。随着这些树型结构数据的数量不断增长,它们
很快将成为人类知识的主要表现形式之一。因此,挖掘树型结
构数据正在成为数据挖掘领域中重要的研究方向。
过去的十年中,在大型静态数据库中挖掘频繁模式已被广
泛研究
[2~9]
。如今,数据往往是顺序到达的而并不能从一开始
就获取整个数据集,并且数据集的大小随着时间的推移迅速增
加,因此,传统的应用在静态数据库上的挖掘算法便不再适用。
这种现象广泛存在于互联网应用中,例如,
Twitter数据流,其携
带实时 Web应用程序的信息,这些信息大多以 Json格式存储,
且只要人们在网上冲浪,则数据在不断产生;在线数据服务,如
雅虎、
IMDB和新浪微博等,这些服务商提供的 RestfulAPI为
用户和开发者提供数据接口,这里面传输的数据也是以 Json
的格式在网络中传输,且每天都有成千上万的用户在请求和接
收数据。从这几个案例中可以发现,它们都有一些共同特征:
a)连续性,数据源源不断地到来;b)到期性,数据智能读取一
次;c)无限性,数据产生的总量往往是无限的
[10]
。具有这些
特征的环境(系统)称为数据流或流数据。数据流是在“数据
爆炸”的时代背景下的产物,许多公司和组织每天都将产生以
百万数量级增长的记录,且随时间而变化的数据,生成和存储
速度比以往任何时候都要快。因其动态改变、高速到达、无限
增长的特性,以及内存的有限性,快速识别数据流中最近时间
内的数据信息能为数据流的分析提供更有价值的信息
[11]
。
本文的研究基于上述两个研究热点进行,讨论的是基于滑
动窗口模型的数据流中频繁树模式挖掘问题,旨在挖掘数据流
中最近时间段内的频繁树模式。本文将树事务数据流建模为
无限的树事务序列,而每个树事务是由树的深度优先扫描生成
的节点序列表示,如图 1所示,大小为 W的数据流滑动窗口由
W个最近的树事务组成,即当新的树事务到达而最旧的树事
务必须从窗口中删除。对于基于滑动窗口模型,朴素方法是每
当新事务进入或最旧事务离开窗口时,从整个窗口重新生成频
繁树模式,这种策略效率低下,需要多次重复扫描树事务。因
第 37卷第 7期
2020年 7月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol.37No.7
Jul.2020