数据流中频繁闭项集的近似挖掘算法.pdf

《数据流中频繁闭项集的近似挖掘算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第5期电子学报Vol.35No.52007年5月ACTAELECTRONICASINICAMay2007数据流中频繁闭项集的近似挖掘算法刘旭，毛国君，孙岳，刘椿年（北京工业大学计算机学院，北京市多媒体与智能软件重点实验室，北京100022）摘要：在数据流中挖掘频繁项集得到了广泛的研究，传统的研究方法大多关注于在数据流中挖掘全部频繁项集.由于挖掘全部频繁项集存在数据和模式冗余问题，所以对算法的时间和空间效率都具有更大的挑战性.因此，近年来人们开始关注在数据流中挖掘频繁闭项集，其中一个典型的工作就是Moment算

2、法.本文提出了一种数据流中频繁闭项集的近似挖掘算法A-Moment.它采用衰减窗口机制、近似计数估计方法和分布式更新信息策略来解决Moment算法中过度依赖于窗口和执行效率低等问题.实验表明，该算法在保证挖掘精度的前提下，可以比Moment获得更好的效率.关键词：数据挖掘；数据流；频繁闭项集中图分类号：TP311文献标识码：A文章编号：0372-2112（2007）05-0900-06AnAlgorithmtoApproximatelyMineFrecuentClosedltemsetsfromDataStr

3、eamsLIUXu，MAOGuo-jun，SUNYue，LIUChun-Nian（BeijingMunicipalKeyLaboratoryofMultimediaandIntelligentSoftwareTechnology，SchoolofComputerScience，BeijingUniuersityofTechnology，Beijing100022，China）Abstract：Miningfreguentitemsetsfromdatastreamshasextensivelybeenstud

4、ied，andmostofthemfocusonfindingcompletesetoffreguentitemsetsinadatastream.Becauseofnumerousredundantdataandpatternsinmainmemory，theycannotgetverygoodperformanceintimeandspace.Therefore，miningfreguentcloseditemsetsindatastreamsbecomesanewimportantprobleminre

5、centyears，wherealgorithmMomentwasregardedasatypicalmethodofthem.Thispaperpres-entsanalgorithm，calledA-Moment，whichusesthedampedwindowtechnigue，approximatecountmethodanddistributedupdatingstrategytogethigherminingefficiency.Experimentalresultsshowthatouralgo

6、rithmperformsmuchbetterthanthepreviousapproaches.Keywords：datamining；datastream；freguentcloseditemset如，一个大型超市每天产生数百万甚至千万条购买记!"引言录、一个地球探测卫星每天要产生十亿字节的数据，并且这些数据随着时间还在不断地增长.尽管挖掘频繁项在关联规则、序列模式挖掘等研究领域，挖掘频繁集仍然是数据流中知识发现的一个基础性工作，但是在项集是最基础和最关键的步骤.挖掘频繁项集是数据挖这类大容量的动态变化的

7、数据流中进行频繁项集挖掘掘中一个活跃的研究领域.1994年，R.Agrawal提出了Apriori算法［1］，这是一个最有影响的挖掘布尔关联规则出现了新的具有挑战性的问题，因此近年来得到广泛关［7，9，11］注.挖掘数据流算法必须能在有限的内存空间和频繁项集的算法.但是，由于Apriori算法需要产生庞大的候选项集和多次扫描数据库［2，3］，因此导致较差的时限定的时间内快速形成模式的归纳，因此对时间和空间空效率.2000年，Han等提出了FP-Tree算法［2］，它不使效率的要求要比静态的数据库挖掘要高.本文

8、提出了一种在数据流中近似地挖掘频繁项集的算法A-Moment.用候选项集而是直接将数据库的扫描结果存放到紧缩［11］它以Moment算法的主要数据结构CET为基础，通过的频繁模式树中，是一个两次数据库扫描的频繁项集挖引进衰减窗口机制和近似估计方法等来减少内存使用掘算法.另一个有代表性的工作是频繁闭项集（Freguent规模和提高挖掘效率.ClosedItemset）的挖掘方法.1999年，Pasgu