数据流topK频繁模式挖掘算法研究

《数据流topK频繁模式挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、北京交通大学博士学位论文数据流top-K频繁模式挖掘算法研究姓名：杨蓓申请学位级别：博士专业：计算机应用技术指导教师：黄厚宽20090601取得均衡。3．有效挖掘数据流滑动窗口top-K闭合频繁模式。闭合频繁模式是频繁模式的精确简洁表示，能够唯一地确定所有的频繁模式及其支持度，并且在数目上往往比频繁模式小几个数量级。研究了一种有效挖掘数据流滑动窗12top．K闭合频繁模式的近似算法TCIS。设计了一种新的压缩前缀扩展树结构TCIS-Tree，该结构不仅存储当前滑动窗口的概要数据信息，而且还记录了业已发现的候选闭

2、合模式信息。在TCIS-Tree的更新和挖掘过程中，采用数据过滤、启发式动态调整剪枝阈值、挖掘阈值等若干优化措施，有效地提高算法的时空效率。结合TCIS-Tree采用一种二级哈希结构快速地进行模式的闭合性判别。有效地实现了滑动窗口top-K闭合模式的挖掘。4．数据流分位数查询。分位数是数据集合的一个重要统计量。设计了一个基于规范数直方图的概要结构——ⅣD耐，并在此基础上实现了数据流分位．Histogram数查询的单遍扫描近似算法NORMAL，其时问和空间复杂度均线性于概要结构中桶的个数，与数据流的长度无关，因而

3、具有很好的可伸缩性。该方法在均匀分布的数据上取得了优良性能。对算法精度与内存需求的关系进行了理论分析。针对上述研究，本文进行了一系列实验研究，对算法的时间消耗、空间需求以及精确性进行了测试，并和已有的有关算法进行了比较。实验表明，上述算法具有较高的时空效率和精确性能，有效地实现了相关的数据流挖掘任务。关键词：数据流；top-K频繁模式；滑动窗12；界标窗12；直方图；分位数分类号：TPl8ABSTRACTDatastre锄isanewdatamodelcomingupinrecentyears．Ithasbee

4、ncalledforinmanyapplicationsincludingwebclickstream，trafficmonitoringandmanagement，electricalpowermanagementandforecasting,sensornetworkdataanalysis，teleco眦lunicationmanagement，financialapplication,businesstradingandothers·Datastre锄modelisdifferentfromtradit

5、ionaldatabase．Ithasthecharacteristicsofrapidness，real．time，continuousnessandboundlessness．Therefore，thealgorithmsforminingdatastreamshavesubstantialdifferencefromthatoftraditionaldatabasemining．Theyareone-passalgorithms．Itisimpossibletomaimmnalltheelementsof

6、datastreamsforthelimitofcapacityofmainmemory．DesigningasynopstsdatastructurewithfarsmallsizecomparedwiththatofthedatastreamtosavethesummaryfeaturesofpasseddataandprovidinginformationforqueriesandanalysisOVerdatastreamISagoodidea．Thus．datastreamprocessingsacr

7、ificestheprecisionofitsminingresultsbyallowingsomeerrors．Consideringthespeedandcontinuousnessofstreamingdata,thealgorithmsforminingdatastreamshavetobeincrementalandefficientintimeandspace．Theexistingdatabasemanagementtechniquescanhardlybeappliedtoprocessdata

8、streamseffectively．Miningoverdynamicdatastreamsbringsumqueopportunitiesbutalsogreatchallenges．Weexploresomeprincipleproblemsofminingdatasteamsinthisdissertationandthecontributionsareasthefollowi