(最新)序列模式的增量式挖掘算法研究

《(最新)序列模式的增量式挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、硕士学位论文MASTER’STHESIS摘要随着信息技术的发展，许多领域积累了大量的数据，迫切需要一种技术从中及时发现有用的知识，提高信息利用率，KDD技术应运而生。通常KDD包括数据准备、数据挖掘、解释与评价等步骤。其中数据挖掘是KDD的核心环节。目前，数据挖掘的研究主要集中在分类、关联规则、序列模式挖掘等方面。序列模式挖掘作为数据挖掘领域的研究热点之一，其任务是从序列数据库中挖掘出最大频繁序列供决策者做出决策。目前的挖掘算法主要分为两种，即一般的挖掘算法和增量式的挖掘算法。一般的挖掘算法如AprioriAll等以关联规则挖

2、掘的相关算法为基础，当大型数据库需要加入新的数据时需要重新挖掘，降低了挖掘的效率，不能满足要求。于是序列模式的增量式挖掘算法被提出，现有的算法有MFS、ISM、ISE、IUS等，它们在原有数据库挖掘结果的基础上，往往只需遍历新增加的数据，或者只需较少次数的遍历原有数据库就能挖掘出新的序列模式，提高了挖掘的效率，其中IUS算法是最为先进的算法。本文通过对IUS及其它算法的研究，发现这些算法往往都只考虑了向数据库中增加数据的情况，而很少有考虑大型数据库也有删除数据的情况，这是问题一。而且，这些算法都是基于“数据库的更新”，没有考虑

3、到增量式挖掘的另一情况“算法参数的改变”，这是问题二。本文首先改正了IUS算法中的错误之处，然后分别针对这两个问题，结合序列模式的增量式挖掘算法的设计原则，以IUS算法为基础，提出了一种序列模式的更新式算法USP(UpdmingSequentialPattems)用来解决问题一。该算法以原数据库的挖掘结果为基础，同时考虑添加和删除数据两种情况，选出其中符合条件的序列作为新数据库中的频繁序列和负边界序列，并在原频繁序列和加入数据库的频繁序列中产生新的序列，作为下一次的候选序列。提出CMS算法解决问题二，在不同的条件下，利用前次挖

4、掘的结果加速本次挖掘过程。最后本文通过对这斜改进算法的分析，指出了它们不同于其它各种算法，以及比其它算法更完善和有效之处。关键词：KDD数据挖掘序列模式增量式挖掘IUS算法硕士学位论文MASTER’STHESISAbstractWiththerapiddevelopmentofimformationtechnology．1argeamountsofdatahavebeenaccumulatedinmanyfields．Ithasbecomemoreandmoreurgenttomineusefulimformationandk

5、nowledgefromsuchhugedata．ThetechnologyofKnowledgeDiscoveryinDatabase(KDD、hasemerged．ThestepsofKDDincludedatapreparing，datamining，explainingandevaluation，etc．OfthesestepsDataMining(DM)isthemostimportant．TheminingofsequentialpatternsisoneofthehottestspotsinthefieldofD

6、M．Thepurposeofsequentialpatternsminingistofindthefrequentsequencesintransactiondatabasesandthenusethesepatternstohelpdecision-makers．Theminingalgorithmsarcdevidedintotwotypes：thenormalonesandtheincrementalones．ThenormalalgorithmsofsequentialpatternsminingsuchasAprio

7、riAllassumethedatabaseisstaticandevenasmallchangeinthedatabasewillrequirethealgorithmtorunagaincompletelytogettheupdatedfrequentsequences．Inpractice，thecontentofadatabasechangescontinuously,anddatamininghastObeperformedrepeatedly．Ifeachtimetheminingalgorithmsmustber

8、erunfromscratch，itwillbeveryinefficientandtime—consuming．However,theincrementalalgorithmsaredifferent．Byusingtheresultsofpreviousminingand