序列模式挖掘研究与发展(nxpowerlite)

《序列模式挖掘研究与发展(nxpowerlite)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据第36卷第12期计算机科学V01．36No．122009年12月ComputerScienceDec2009·-·__o·___·_·‘’__I一-1___I______■_o__-__··-___________o___________-__________●■●o·●____●。____-·_____________-。___。。。_。。。_-____·_·____--o一序列模式挖掘研究与发展王虎1丁世飞h2(中国矿业大学计算机科学与技术学院徐州221008)·(中国科学院计算技术研究所智能信息处理重点实验室北京100080)z摘要序

2、列模式挖掘是数据挖掘的一个重要研究课题，它在很多领域中都有着广泛的应用。首先讨论了序列模式挖掘的相关背景，然后对序列模式挖掘进行分类，并在此基础上对每一类序列模式挖掘算法的特点进行了介绍和比较；最后，对序列模式挖掘未来的研究重点进行展望，以便研究者对序列模式挖掘做进一步的研究。关键词数据挖掘，序列模式挖掘，闭合模式，增量式，多维模式ResearchandDevelopmentofSequentialPatternMining(SPM)WANIGHulDINGShi—feil．2(SchoolofComputerScienceandTechnolog

3、y，ChinaUniversityofMiningandTechnology，Xuzhou221008，China)1(KeyLaboratoryofIntelligentInformationProcessing，InstituteofComputingTechnology，ChineseAcademyofSciences。Beijing100080，China)2AbstractSequentialpatternmining(SPM)isanimportantresearchsubjectofdatamining，andusedwidelyin

4、manyapplicationfields．Thispaperfirstlydiscussedbackgroundofsequentialpatternminging，thenclassifiedit，andintro—ducedaswellascomparedthefeaturesofsequentialpatternmingingalgorithmsbasedontheclassification．Finally，dis—CUSSedthefutureresearchonthisfield80thatresearcherscandofurthe

5、rstudy,KeywordsDatamining，Sequentialpatternmining(SPM)，Closedpattem，Incrementalpattern，Muhi-dimentionalpat—tam1引言序列模式挖掘(Sequentialpatternmining，SPM)是指从序列数据库中寻找频繁子序列作为模式的知识发现过程，它是数据挖掘的一个重要研究课题，在很多领域都有实际的应用价值，如客户购买行为模式的分析、web访问模式的预测、疾病诊断、自然灾害预测、DNA序列分析等。通过对这些领域的数据运用序列模式挖掘技术，可以发现

6、隐藏的知识，从而帮助决策者做出更好的决策，以获得巨大的社会价值和经济价值。深入理解高效的序列模式挖掘方法对在大型数据库中高效挖掘频繁子树、格、子图以及其他结构模式等有着重要意义。序列模式挖掘最早是由RakeshAgrawal和Ramakrish—nanSrikant针对购物篮数据分析提出来的，经过多年的发展，对序列模式挖掘的研究取得了比较大的进步，研究者们提出了很多性能良好的算法。本文将对每类算法的特点进行评述并对未来的研究重点进行展望。2序列模式挖掘算法的分类及研究现状基本的序列模式挖掘的任务是找出序列数据库中满足用户定义的最小支持度阈值的所有序

7、列的集合。序列模式挖掘和关联规则挖掘有着紧密的联系：一方面，关联规则挖掘以发现事物的内部联系为主，序列模式挖掘以发现事物之间的联系为主；另一方面，很多对于关联规则挖掘的研究都进一步促进了序列模式挖掘研究的发展。2．1基本的序列模式挖掘(1)基于Apriori特性的算法早期的序列模式挖掘算法都是基于Apfiofi特性发展起来的。RakeshAgrawal和RamakrishnanSrikant在文献1-13中最早提出了序列模式挖掘的概念并且提出了3个基于Apriori特性的算法[1]：ApfiofiAll，ApfiofiSome，Dynamic—So

8、me。基于这一思想，研究者又提出了GSPc2]算法，它对AprioriAll算法的效率进行了改进并且加入了时间限制、放宽交