基于倾斜时间窗口的频繁项集挖掘算法研究

《基于倾斜时间窗口的频繁项集挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、●分类号：——UDC：密级：编号：工学硕士学位论文基于倾斜时间窗口的频繁项集挖掘算法研究硕士研究生：指导教师：学位级别：学科、专业：所在单位：论文提交日期：论文答辩日期：学位授予单位：徐艳红张健沛教授工学硕士计算机软件与理论计算机科学与技术学院2010年1月6日2010年3月12日哈尔滨工程大学}～oII，rI¨．八-ClassifiedIndex：曲U．D．C：■ADissertationfortheDegreeofM．EngAnResearchonMiningFrequentItemsetsAlgorithmBasedonTitled-·TimeWindow

2、Candidate：XuYanHongSupervisor：ZhangJianpeiAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：ComputerSoftwareandTheoryDateofSubmission：January，2010DateofOralExamination：March，2010University：HarbinEngineeringUniversity哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。有关观点、方法、数据和

3、文献的引用已在文中指出，并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者(签字)：行开够2日期：衣9加年罗月心日学位论文授权使用声明本人完全了解学校保护知识产权的有关规定，即研究生在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编

4、本学位论文，可以公布论文的全部内容。同时本人保证毕业后结合学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈尔滨工程大学。涉密学位论文待解密后适用本声明。本论文(口在授予学位后即可口在授予学位12个月后口解密后)由哈尔滨工程大学送交有关部门进行保存、汇编等。作者(签字)：孝寰j}鼋零≯日期：i∥印年多月世日导师c签字，爹坼醴咖年乡月店日哈尔滨T程大学硕十学位论文摘要当今的信息社会的中，人们每天都要处理各种各样的信息和数据。随着信息的爆炸式增长，许多应用中需要处理的数据规模也越来越大，这些数据以快速的、大量的、按时间顺序连续到达，这种数据模式就是数据流。由于

5、数据流的流动性和无限性的特点，原有频繁项集挖掘算法已很难完成基于数据流上的挖掘任务。这些挑战吸引了许多人对数据流中频繁项集挖掘进行了大量研究。现在，数据流中频繁项集挖掘已成为数据挖掘中的热点之一。FP．stream算法可以实现在线挖掘多时间粒度的频繁项集。作为一个经典的挖掘算法，FP．stream算法具有较好的时间效率。但它的不足之处在于：算法使用FP．growth算法来生成频繁项集和计算支持数，需要很大的内存开销和时间开销；整个挖掘过程中，所有的历史信息数据都存于内存中，随着时间的推移内存空间将急剧的膨胀。所以，内存开销巨大是FP．stream算法最大的缺点。

6、针对上述问题，本文将在原算法的基础之上，采用一种新的数据结构(LR．Tile树及树结点)来存储频繁项集及其对应的倾斜时间窗口。同时引入了垂直的二进制向量表示法存储事务数据以提高时空效率。由于构造了新的树结点结构，可以方便地完成LR．Tile树的线性存储和结点查询。另外将LR．Trie树分割为若干子树并以文件的形式存储，在内存中建立项和文件的索引表，按需调入文件，极大地减少了内存消耗。实验表明，改进后的算法在不明显降低原算法时间效率的前提下，提高了内存空间利用率。该算法适用于对时间要求不高，但对内存空间要求较高的应用。关键词：数据流：频繁项集：二进制向量；LR．T

7、ile树；内存开销k‘●、o‰IAbstractIIltheinformationsociety,peoplehavetoprocessvariousinformationanddatatoday．Astheexplosiveincreaseofinformation，thescaleofthedatatobepfocessedbecomeslargerandlargerinmanypracticalapplications．Thesedatacontinuallyarrivewithhighspeed，hugevolumeandintimeordenThisd

8、atamoduleisc