数据流中基于滑动窗口的效用频繁模式挖掘算法

《数据流中基于滑动窗口的效用频繁模式挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、合肥工业大学硕士学位论文数据流中基于滑动窗口的效用频繁模式挖掘算法姓名：孙英家申请学位级别：硕士专业：管理科学与工程指导教师：李锋刚201203数据流中基于滑动窗口的效用频繁模式挖掘算法摘要随着硬件技术的高速发展，人们收集数据的能力也在飞速的提高。越来越多的领域已不再满足于静态数据的处理和分析，数据挖掘的热点也逐渐转移到数据流上。区别于静态数据，数据流具有快速、多变、实时、海量等特点，这对数据挖掘工作带来了新的困难和挑战。在目前数据流挖掘的研究中，数据流中的每个项(item)被看成具有同等重要性，然而在实际应用中，每个项都有着

2、不同的重要性一一效用，这种挖掘手段称为效用频繁模式挖掘。然而引用效用概念后，一些定理和方法不再适用一一如向下闭合性，这给挖掘工作带来了很大困难。本文将频繁模式挖掘与效用结合，提出一个高效的基于滑动窗口的效用频繁模式挖掘算法UFPM(utilityfrequentpatternmining)。算法将位图结构与树结构相结合，只需一遍扫描，就能够快速、完整地存储和更新模式信息。算法中设计了一种新的树结构u．tree，按照文法顺序生成，方便模式的增量更新和用户读取。同时算法采用模式增长的挖掘方式，可以避免现有算法存在的逐级搜索产生大量

3、候选项集的问题。通过多个实验与前人算法进行测试和对比，结果表明该算法具有较高的效率和较好的可扩展性，优于现有的同类算法。关键词：数据流；效用频繁；滑动窗口；位图TheUtilityFrequentPatternMiningBasedonSlideWindowinDataStreamABSTRACTWiththehighdevelopfnen专ofhard、Vare，people’sabilityincollectingdataisaswellinfastimprovement．Moreandmoreneldscannomore

4、llleetthedemandsofproeessingandanalyzingthestaticdata，hence，thesearehinghotspotflordatanliningistransf色rringintodatastreams．Dif纯rftomthestaticdata，datastrealnhasthefast，multi．changing，livingandmagnanimitycharaeteristicswhichbfingthenewdimcultyandchallengef-ordataIni

5、ningwork。Inreeentresearchofdatastfeammining，eaehitemindatastrea搬isofequalimportance。HoweVer，in1)ractice，eachite娃lhasadif蟊efentsignificance—thatisutilitywhicht量lismethodiscalledfrequentpatternmining．However，sonletheoremandmethodsarenomoreinadaption，likedownwardcloses

6、pacewhiehbringahugediff{c试tyinminingtasks．下hispapereombinesf}equentminingitemsetswithutilityandproposesanef矗cientalgorithmforutilityfrequentpatternmining(UFPM)，：{tcombinesbitmapwithtreestructurethatcanstofeandupda专ethepatternofdatastreamquicklyandeompletelybyscannin

7、gonlyonee．Thealgofithmgeneratedbylexicographicorder，proposesanoveltreeU—treeandmakeseonvenieneefbrpatternupdatinganduse堇．reading．Withapatterngrowthapproachinmining，thealgorithmcaneff．ectiVelyavoidt量leproblelnofalnasscandidacygenerationby】eVel-wisesearching．Byworking

8、throughseVefalexperil弧entstoteslingandcontrastinginexistingalgorithms，wepr。Vethatouralgorithmisinhigheffieiencyandgoodscalabilityoutperfbr