基于投影数据挖掘算法研究与实现

陕西理工学院毕业设计第1页共27页毕业论文﹙设计﹚题目基于投影数据挖掘算法研究与实现学生姓名郭凯学号041842020所在院(系)数学系专业班级信息与计算科学043班指导教师周涛完成地点数学系数据挖掘实验室2008年6月9日陕西理工学院毕业设计第2页共27页基于投影数据挖掘算法研究与实现作者：郭凯（陕西理工学院数学系信息与计算科学专业043班陕西723001）指导教师：周涛[摘要]：序列模式的发现是数据挖掘领域一个活跃的研究分支,即在序列数据库中找出所有的频繁子序列.本文先介绍序列模式挖掘中的一些基本概念,然后详细描述FreeSpan和PrefixSpan2个基于投影、分治的模式增长的重要算法。基于投影方法即序列数据库先被投影为很多小投影数据库,然后在小投影数据库中进行递归挖掘的典型算法.其中FreeSpan算法是将数据库分成若干个子空间，再每个子空间里进行递归的的投影，对于每一个项及其与前一项组合成的序列模式进行投影挖掘，最终得出频繁子序列。PrefixSpan算法则是先找出长度为1的序列模式，以此序列模式为前缀的投影，并在投影数据库里面继续递归的进行投影，最终得出频繁子序列。本文并以实例解析，更为详细清楚的描述了两种算法的过程。[关键词]:数据挖掘；FreeSpan算法；PrefixSpan算法；陕西理工学院毕业设计第3页共27页AccordingtocastshadowadatatoscoopoutcalculatewayresearchAuthor：GuoKai（Grade04,Class03,Informationandcalculationscience，DepartmentofMathematics，ShaanxiUniversityofTechnology，Hanzhong723000，Shaanxi）tutor::ZhouTaoAbstractSequencemodedataminingisthediscoveryofanactiveareaofresearchbranch,thatis,allsequencesinthedatabasetoidentifythefrequencyofsequence.Inthispaper,firstintroducedinthesequencepatternminingsomeofthebasicconcepts,andthendescribedindetailFreeSpanandPrefixSpan2basedprojection,thepartitionoftheimportantgrowthpatternalgorithm.Basedontheprojectionmethodthatsequencedatabasewasfirstprojectionforthemanysmallprojectiondatabase,andthenasmallprojectiondatabaseMiningtypicalrecursivealgorithm.WhichFreeSpanalgorithmisdividedintoseveralsub-databasespace,theneachoftherecursivespacefortheprojector,andforeachandeveryitemwithacombinationof10%oftheformermodelprojectionexcavationsequence,thefinalsequenceofdrawnfrequent.ThePrefixSpancalculatewaythenfindoutthelengthasonesequencemodefirst,takethissequencemodeascastshadowofex-Zhui,andcontinuetopasstoreturnintheprojectionthedatabaseofcarryoncastshadow,endgetmultifarioussub-sequence.Analysisandexamplesinthispaper,amoredetaileddescriptionofthetwoclearlyalgorithmprocess.KeywordsThedatascoopout;FreeSpanarithmetic;PrefixSpanarithmetic;陕西理工学院毕业设计第4页共27页目录一引言.......................................................................5二序列模式挖掘相关知识.......................................................52.1基本术语..................................................................52.2基本定义..................................................................5三序列模式简介...............................................................63.1问题描述..................................................错误!未定义书签。3.2系统规定..................................................错误!未定义书签。四模式增长方法...............................................................64.1freespan算法..............................................................64.1.1freespan算法的思想.....................................................64.1.2freespan算法执行过程的描述.............................错误!未定义书签。4.1.3freespan算法的分析.....................................................74.2prefixspan算法............................................................74.2.1prefixspan算法的提出...................................................74.2.2prefixspan算法的思想及描述.............................................74.2.3prefixspan算法的分析...................................................84.2.4prefixspan算法的主要改进...............................................84.2.5prefixspan算法和Aporiori算法的比较....................................8五实例解析...................................................................9I利用freespan算法解析.......................................错误!未定义书签。Ⅱ利用PrefixSpan算法解析....................................错误!未定义书签。六对prefixspan算法的VC程序的实现..........................................126.1prefixspan算法的流程图...................................................126.2算法的执行结果...........................................................136.3算法结果分析.............................................................14七结论与展望................................................................15八致谢......................................................................15九参考文献..................................................................16十附录......................................................................17陕西理工学院毕业设计第5页共27页一：引言：序列模式挖掘是数据挖掘研究的一个重要课题,而且具有非常广泛的应用，被应用在包括顾客购买行为的分析、网络访问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害的预测、DNA序列模式的分析等[1].目前对序列模式挖掘问题的研究主要集中在算法设计和实际应用，在理论方面研究还很罕见.序列模式挖掘是对关联规则挖掘的进一步推广,它挖掘出序列数据库中项集间的时序关联规则是数据挖掘研究的一个重要内容.早先的很多关联规则挖掘研究都有助于挖掘序列模式或者与时间相关的频繁模式.SRIKANT和AGRAWAL对序列规定了时间限制、滑动时间窗口和用户规定的分类,并总结了序列模式的定义,提出一种基于Apriori的改进算法GSP(generalizedsequentialpatterns)算法.以上这些都是基于Apriori的水平格式的序列模式挖掘或者与时间相关的频繁模式挖掘.后来,ZAKI提出了一种基于垂直格式存储的序列模式挖掘方法SPADE算法,该算法由基于垂直格式的频繁项挖掘演化而来.近几年,HAN等人又提出一种基于投影的模式增长算法——Freespan（FrequentPattern-pojectedSequentialPatternMining）算法[2],该算法改进后为PrefixSpan(Prefix-ProjectedSequentialPatternsMining)算法[3],性能进一步提高.MANNILA等人[4]提出的挖掘频繁序列片段问题,GAROFALAKIS等人提出的基于规则表达式约束的序列模式挖掘,还有关于序列模式挖研究的一些扩展,如序列模式闭项挖掘、并行挖掘、分布式挖掘、多维度序列模式挖掘和近似序列模式挖掘等,所有这些对后来研究序列模式挖掘都有一定的影响.本文重点对典型的序列模式挖掘算法FreeSpan和PrefixSpan两种典型算法进行详细的描述、分析和比较.二、序列模式挖掘的相关知识2.1基本术语设I={i1,i2,……,in}是一个项目集合,项目集或者项集(items)就是各种项目组成的集合,即I的所有子集.一个序列就是若干项集的有序列表,一个序列S可表示为〈s1,s2,……,sn〉,其中sj为项集,也称作S的元素.元素由不同的项组成,可表示为(x1,x2,……,xn).当元素只包含一项时,一般省去括号,如(x2)一般表示为x2.元素之间是有顺序的,但元素内的项是无序的,一般定义为词典序.序列包含项的个数称为序列的长度,长度为L的序列记为L-序列.序列数据库