《《基于投影数据挖掘算法的研究与实现》-公开DOC·毕业论文》由会员分享，可在线阅读，更多相关《《基于投影数据挖掘算法的研究与实现》-公开DOC·毕业论文（27页珍藏版）》请在金锄头文库上搜索。
1、陕西理工学院毕业设计 毕业论文设计题 目 基于投影数据挖掘算法研究与实现 学生姓名 郭凯 学号 041842020 所在院(系) 数学系 专业班级 信息与计算科学043班 指导教师 周涛 完成地点 数学系数据挖掘实验室 2008年 6 月 9 日基于投影数据挖掘算法研究与实现作者：郭凯（陕西理工学院 数学系信息与计算科学专业043班 陕西 723001）指导教师：周涛摘要：序列模式的发现是数据挖掘领域一个活跃的研究分支,即在序列数据库中找出所有的频繁子序列.本文先介绍序列模式挖掘中的一些基本概念,然后详细描述FreeSpan和PrefixSpan2个基于投影、分治的模式增长的重要算法。基于投影
2、方法即序列数据库先被投影为很多小投影数据库, 然后在小投影数据库中进行递归挖掘的典型算法.其中FreeSpan算法是将数据库分成若干个子空间，再每个子空间里进行递归的的投影，对于每一个项及其与前一项组合成的序列模式进行投影挖掘，最终得出频繁子序列。PrefixSpan算法则是先找出长度为1的序列模式，以此序列模式为前缀的投影，并在投影数据库里面继续递归的进行投影，最终得出频繁子序列。本文并以实例解析，更为详细清楚的描述了两种算法的过程。关键词:数据挖掘； FreeSpan算法；PrefixSpan算法；According to cast shadow a data toscoop out ca
3、lculate way researchAuthor：GuoKai（Grade04,Class03, Information and calculation science，Department of Mathematics，Shaanxi University of Technology，Hanzhong 723000，Shaanxi）tutor: ZhouTaoAbstract Sequence mode data mining is the discovery of an active area of research branch, that is, all sequences in
4、the database to identify the frequency of sequence. In this paper, first introduced in the sequence pattern mining some of the basic concepts, and then described in detail FreeSpan and PrefixSpan2 based projection, the partition of the important growth pattern algorithm. Based on the projection meth
5、od that sequence database was first projection for the many small projection database, and then a small projection database Mining typical recursive algorithm. Which FreeSpan algorithm is divided into several sub-database space, then each of the recursive space for the projector, and for each and ev
6、ery item with a combination of 10% of the former model projection excavation sequence, the final sequence of drawn frequent. The PrefixSpan calculate way then find out the length as one sequence mode first, take this sequence mode as cast shadow of ex- Zhui, and continue to pass to return in the pro
7、jection the database of carry on cast shadow, end get multifarious sub- sequence. Analysis and examples in this paper, a more detailed description of the two clearly algorithm process.Keywords The data scoop out;FreeSpan arithmetic; PrefixSpan arithmetic;目 录一 引言5二 序列模式挖掘相关知识52.1 基本术语52.2 基本定义5三 序列模式
8、简介63.1 问题描述63.2 系统规定6四 模式增长方法64.1 freespan算法6 4.1.1 freespan算法的思想6 4.1.2 freespan算法执行过程的描述7 4.1.3 freespan算法的分析74.2 prefixspan算法7 4.2.1 prefixspan算法的提出7 4.2.2 prefixspan算法的思想及描述7 4.2.3 prefixspan算法的分析8 4.2.4 prefixspan算法的主要改进8 4.2.5 prefixspan算法和Aporiori算法的比较8五 实例解析9I 利用freespan算法解析9 利用PrefixSpan算法解
9、析10六 对prefixspan算法的VC程序的实现126.1 prefixspan算法的流程图126.2 算法的执行结果136.3 算法结果分析14七 结论与展望15八 致谢15九 参考文献16十 附录17一：引言：序列模式挖掘是数据挖掘研究的一个重要课题, 而且具有非常广泛的应用，被应用在包括顾客购买行为的分析、网络访问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害的预测、DNA 序列模式的分析等1.目前对序列模式挖掘问题的研究主要集中在算法设计和实际应用，在理论方面研究还很罕见.序列模式挖掘是对关联规则挖掘的进一步推广, 它挖掘出序列数据库中项集间的时序关联规则是数据挖掘研究的一
10、个重要内容. 早先的很多关联规则挖掘研究都有助于挖掘序列模式或者与时间相关的频繁模式. SRIKANT和AGRAWAL对序列规定了时间限制、滑动时间窗口和用户规定的分类, 并总结了序列模式的定义, 提出一种基于Apriori 的改进算法GSP(generalized sequential patterns)算法. 以上这些都是基于Apriori的水平格式的序列模式挖掘或者与时间相关的频繁模式挖掘. 后来, ZAKI提出了一种基于垂直格式存储的序列模式挖掘方法SPADE算法, 该算法由基于垂直格式的频繁项挖掘演化而来. 近几年, HAN等人又提出一种基于投影的模式增长算法Freespan（Fre
11、quent Pattern-pojected Sequential Pattern Mining）算法2 , 该算法改进后为PrefixSpan(Prefix-Projected Sequential Patterns Mining)算法3 , 性能进一步提高. MANNILA等人4提出的挖掘频繁序列片段问题,GAROFALAKIS等人提出的基于规则表达式约束的序列模式挖掘, 还有关于序列模式挖研究的一些扩展, 如序列模式闭项挖掘、并行挖掘、分布式挖掘、多维度序列模式挖掘和近似序列模式挖掘等, 所有这些对后来研究序列模式挖掘都有一定的影响. 本文重点对典型的序列模式挖掘算法FreeSpan和P
12、refixSpan两种典型算法进行详细的描述、分析和比较.二、序列模式挖掘的相关知识2.1 基本术语设I= i1, i2, in是一个项目集合, 项目集或者项集(items) 就是各种项目组成的集合, 即I 的所有子集. 一个序列就是若干项集的有序列表, 一个序列S可表示为s1,s2, , sn, 其中sj为项集, 也称作S的元素. 元素由不同的项组成, 可表示为(x1, x2, , xn). 当元素只包含一项时, 一般省去括号, 如(x2)一般表示为x2. 元素之间是有顺序的, 但元素内的项是无序的, 一般定义为词典序. 序列包含项的个数称为序列的长度, 长度为L的序列记为L- 序列. 序列
13、数据库就是元组(tuples)sid, s 的集合, 其中s是序列, sid 是该序列的序列号, 元组的个数称为序列数据库的大小, 记作|SDB|.2.2 基本定义5定义1 序列模式：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值.定义2子序列和超序列：对于序列A=a1, a2, , an和B=b1, b2, , bm , 当且仅当1j1 j2 jm m 且a1j1 , a2j2 , , anjn时, 称序列B
14、为序列A的超序列, 序列A为序列B的子序列, 又称序列B包含序列A, 记作AB. 例如在表1中a(abc)(cf) bd这个序列, 其中(abc),a(abc) (cf)都是a(abc)(cf)bd的子序列, a(abc)(cf)bd是(abc),a(abc)(cf)的超序列.定义3 支持数：序列数据库D是元组sid, S的集合, sid为序列标识号. 如果序列T是S的子序列(即TS) , 称元组sid, S包含序列T , 则序列T 在序列数据库D中的支持数是数据库中包含T的元组数, 即support D(T) = |sid, S|sid, SDTS | , 记作support(T).定义4频繁序列模式：给定一个最小支持度阈值minsup , 如果序列s的支持度不小于minsup , 则称序列s为频繁序列模式, 所有的频繁序列模式集合记作FS. 例如在表1中(ac)这个序列分别在10和40序列出现2次, 所以其支持数为2. 假设用户规定min sup 为2, 可知(ac)序列是频繁序列模式.定义5 前缀( Prefix) :设每个元素中的所有项目按照字
