数据流频繁项挖掘算法的研究和应用

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

1、大连理工大学硕士学位论文摘要数据流是按时间顺序到达的一个连续数据组成的一个序列。近年来，挖掘数据流的应用越来越广泛。在动态数据集上挖掘频繁项是一项困难的任务，也是一个热点。流数据频繁项挖掘是数据流挖掘中的重要组成部分。目前数据流频繁项挖掘算法的研究成果主要有基于Hash的和基于抽样的。本文首先对这两类的经典算法的主要思想进行了探讨，对这些算法在误差范围、空间复杂度和单项处理的时间复杂度等方面重点进行了比较。接着，本文重点对数据流频繁项挖掘的EC算法进行了研究探讨。虽然该算法在误差范围、空间复杂度和处理单项数据

2、项的时间复杂度方面是目前进行频繁项挖掘中的较好算法，但该算法在最坏时间复杂度方面没有给出最坏保证，在精度方面还可以进一步提高。然后，本文给出了基于计数和局部性原理的频繁项挖掘算法。一方面，改进EC算法维护样本集合的方法，将数据流每个数据项的最坏处理时间控制在0(8-1)；另一方面，根据局部性原理可知，如果一个数据项被访问，则该项可能很快被再次访问。因此，利用增加历史样本集，暂存历史流数据的概要信息，通过动态维护样本集和历史样本集来进一步降低输出频率值的误差，用一定的空间换取一定的精度。通过理论分析和实验验证，

3、通常情况，改进算法的误差更小。而且，最坏时间复杂度可以得到保证。最后，在公安局的点击流频繁项挖掘系统中该算法得到具体应用。访问者点击网页时形成连续的、数据量巨大的点击流信息，保存所有数据是不现实的。当点击流信息产生时，首先，数据流处理模块负责接收数据、流量控制等。然后，通过数据流频繁项挖掘模块快速、有效地近似统计出点击量最大的网页，将该信息保存在概要数据结构中。当查询时，从概要结构中快速返回感兴趣的网页。关键词：数据流；数据挖掘；￡一近似；频繁项大连理工大学硕士学位论文ResearchandApplicati

4、onofMiningFrequentItemsAlgorithminDataStreamsAbstractAdamstreamisallorderedsequenceofitemsthatarrivesintimelyorder．Recently．theapplicationofdatastreamrnjniugiswidely-nsed．ItischallengeandhottomaintainfrequentitemsoveradynamicaldataStl'eanl．Datastreamfrequen

5、titemsminingisanimportantcomponentofdatastreammining．Researchresultsofdatastreamminillgalgorithmsmostlyincludehashalgorithmsandsamplingalgorithms．Firstly，thesetwotypesofclassicalalgorithmforthemainideaarediscnssed．Focusinthisarticleisonthedifferenceoffreque

6、nterrorbound、sparerequirementandtimeforper-itemofalgorithms．Secondly,ECalgorithmofmaintalningdatastreamfrequentitemsisresearchedanditisdiscussed．Frequenterrorbound、spacerequirementandtimeforper-itemofECalgorithmisbetternow,buttheWOl-St-ea．站eomplexityisnotco

7、nsideredandthefrequencyerrorboundoftheresultsCanbesmall．Thirdly,thispaperproposedanimprovedalgorithmforminingfrequentitembasedoncounterandlocalizedprinciple．Ontheonehand,themethodhowtoupdatethesamplesetofECalgorithmischangedbyacounter．Theworst-casecomplexit

8、yisO(8_1)byit．Ontheotherhand,ifaitemisarrived,itisprobablyarrivedrecently．So，thesynopsisinformationissavedwithhistorysampleset．ThefrequentGⅡ"l-orboundislowerbydynamicallyupdatesamplesetandhistorysample