数据流上的频繁闭项集挖掘算法—49—数据流上的频繁闭项集挖掘算法陶克，王意洁(国防科技大学计算机学院并行与分布处理国家重点实验室，长沙410173)摘要：针对频繁闭项集挖掘算法中数据结构与处理机制复杂的问题，提出窗口快速滑动的数据流频繁闭项集挖掘算法——MFWSR。算法通过采用紧致的数据结构和简化的判断过程提高时空效率，支持响应不同用户支持度阈值的查询。实验结果表明，在保持已有算法精度的情况下，MFWSR具有更高的时空效率。关键词：数据流；数据挖掘；频繁闭项集AlgorithmofMiningFrequentClosedItemsetsonDataStreamsTAOKe,WANGYi-jie(NationalKeyLaboratoryforParallelandDistributedProcessing,SchoolofComputer,NationalUniversityofDefenseTechnology,Changsha410173,China)ThispaperproposesanalgorithmofMiningFrequentcloseditemsetswithWindowSlidingRapidly(MFWSR)againstthecomplexityofdatastructureandprocessfordetermination.Withthedatastreamrepresentedbycompactdatastructure,processfordeterminationsimplified,MFWSRimprovesthetemporalandspatialefficiencywhileitcanresponsetotherequestsofuser-specifiedsupportthreshold.Experimentalresultsshowthatcomparedwithexistingalgorithms,MFWSRachieveshighertemporaryandspatialefficiencywhiletheaccuracyremains.datastream;datamining;frequentcloseditemsets计算机工程ComputerEngineering第36卷第18期Vol.36No.182022年9月September2022·软件技术与数据库·文章编号：1010—3428(2022)18—0049—03文献标识码：A中图分类号：TP3111概述近年来，在商业等应用中，人们对数据流上的相联规则挖掘、频繁项集挖掘的时间、空间效率提出了新的要求。由于要考虑太多的备选项集(若有k个项，则需要考察2k个项集是否为频繁项集)，空间复杂度呈组合爆炸式的增长。另外，依据频繁闭项集挖掘结果可再现出所有频繁项集及其支持度。数据流D由无限到达的事务Ti组成，Ti由若干个项组成，事务与项集类似(特指那些在数据流中的组成单元)，k个项可以组成k项集。项集的支持度是指在其滑动窗口的所有事务中出现的比例。超过由用户指定比例的项集被称为频繁项集[1]。频繁闭项集是指不存在超项集与自身有相同支持度的频繁项集。数据流上的频繁项集挖掘成为近来研究的热点，文献[2]提出LossyCounting方法；Chang等提出的算法estDec采用一种将数据流随出现时间推移而降低其权重的方法；Giannella等提出的方法从另一个方面考虑了这个特性。以上的方法称全数据流方法。而另外一类算法采用了滑动窗口模型，这种模式仅在最近出现的一段数据流上挖掘频繁项集。对于数据流上的频繁闭项集挖掘方法有文献[3]提出的Moment以及文献[4]提出的CFI-Stream等。Moment的主要贡献在于提出了CET；缺陷在于对稍大的滑动窗口，CET消耗很大空间。CFI-Stream的主要缺点在于对新到达事务所包含的所有子集进行闭包判断，这样的分析方法大大降低了其算法效率。另外，文献[5]提出了NewMoment算法。本文以处理高速数据流为目的，提出数据流上频繁闭项集挖掘算法——MFWSR，提高了已有算法的时间、空间效率。2符号与函数的定义2.1符号定义符号定义如表1所示。表1符号定义符号定义W当前滑动窗口Wi,j从第i个事务开始的一个窗口，窗口大小为jsup(X)项集X的支持度str(X)项集X的字符串表示len(X)项集X所包含项的数目2.2函数定义定义1设在数据流D上，T为所有事务的子集，定义：(){|,}fTiItTiT=∈?∈∈定义2设在数据流D上，X为所有项的子集，定义：(){|,}gXtDiXit=∈?∈∈另外，设X为一个项集，若C(X)=f·g(X)=X，则X为闭项集。3MFWSR算法MFWSR算法通过位序列方式使得算法的空间效率得以显著提高，并采用散列表查询频繁闭项集支持度计数，提高查询速度。3.1位序列位序列是指用二进制位表示项集的支持度、在窗口中每个事务的出现情况。MFWSR算法存储所有1项集的位序列组成位矩阵，其中，每个位矩阵的子集的位序列都可以快速基金项目：国家自然科学基金资助项目(60873215,60621013)；国家“973”计划基金资助项目(2005CB321801)；高等学校博士学科点专项科研基金资助项目(20221011010003)；高等学校全国优秀博士学位论文作者专项基金资助项目(200141)作者简介：陶克(11018－)，男，硕士研究生，主研方向：数据流处理；王意洁，教授、博士生导师收稿日期：2022-04-16E-mail：andy.taoke@https://www.sodocs.net/doc/a83514968.html本文来源：网络收集与整理，如有侵权，请联系作者删除，谢谢！