《毕业设计（论文）基于投影数据挖掘算法研究与实现.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）基于投影数据挖掘算法研究与实现.doc（27页珍藏版）》请在三一办公上搜索。
1、 毕业论文设计题 目 基于投影数据挖掘算法研究与实现 学生姓名 学号 041842020 所在院(系) 数学系 专业班级 信息与计算科学043班 指导教师 完成地点 数学系数据挖掘实验室 2008年 6 月 9 日基于投影数据挖掘算法研究与实现作者：（陕西理工学院 数学系信息与计算科学专业 陕西 723001）指导教师：摘要：序列模式的发现是数据挖掘领域一个活跃的研究分支,即在序列数据库中找出所有的频繁子序列.本文先介绍序列模式挖掘中的一些基本概念,然后详细描述FreeSpan和PrefixSpan2个基于投影、分治的模式增长的重要算法。基于投影方法即序列数据库先被投影为很多小投影数据库, 然
2、后在小投影数据库中进行递归挖掘的典型算法.其中FreeSpan算法是将数据库分成若干个子空间，再每个子空间里进行递归的的投影，对于每一个项及其与前一项组合成的序列模式进行投影挖掘，最终得出频繁子序列。PrefixSpan算法则是先找出长度为1的序列模式，以此序列模式为前缀的投影，并在投影数据库里面继续递归的进行投影，最终得出频繁子序列。本文并以实例解析，更为详细清楚的描述了两种算法的过程。关键词:数据挖掘； FreeSpan算法；PrefixSpan算法；According to cast shadow a data toscoop out calculate way researchAuth
3、or：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 the database to identify
4、 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 method that sequence databas
5、e 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 every item with a combinat
6、ion 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 projection the database of
7、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三 序列模式简介63.1 问题描述63.2 系统规定6四 模
8、式增长方法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算法解析10六 对prefixspan算法的VC程序的
9、实现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（Frequent Pattern-pojected S
11、equential Pattern Mining）算法2 , 该算法改进后为PrefixSpan(Prefix-Projected Sequential Patterns Mining)算法3 , 性能进一步提高. MANNILA等人4提出的挖掘频繁序列片段问题,GAROFALAKIS等人提出的基于规则表达式约束的序列模式挖掘, 还有关于序列模式挖研究的一些扩展, 如序列模式闭项挖掘、并行挖掘、分布式挖掘、多维度序列模式挖掘和近似序列模式挖掘等, 所有这些对后来研究序列模式挖掘都有一定的影响. 本文重点对典型的序列模式挖掘算法FreeSpan和PrefixSpan两种典型算法进行详细的描述、分
12、析和比较.二、序列模式挖掘的相关知识2.1 基本术语设I= i1, i2, in是一个项目集合, 项目集或者项集(items) 就是各种项目组成的集合, 即I 的所有子集. 一个序列就是若干项集的有序列表, 一个序列S可表示为s1,s2, , sn, 其中sj为项集, 也称作S的元素. 元素由不同的项组成, 可表示为(x1, x2, , xn). 当元素只包含一项时, 一般省去括号, 如(x2)一般表示为x2. 元素之间是有顺序的, 但元素内的项是无序的, 一般定义为词典序. 序列包含项的个数称为序列的长度, 长度为L的序列记为L- 序列. 序列数据库就是元组(tuples)sid, s 的集
13、合, 其中s是序列, sid 是该序列的序列号, 元组的个数称为序列数据库的大小, 记作|SDB|.2.2 基本定义5定义1 序列模式：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值.定义2子序列和超序列：对于序列A=a1, a2, , an和B=b1, b2, , bm , 当且仅当1j1 j2 jm m 且a1j1 , a2j2 , , anjn时, 称序列B为序列A的超序列, 序列A为序列B的子序列, 又
14、称序列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
15、, 如果序列s的支持度不小于minsup , 则称序列s为频繁序列模式, 所有的频繁序列模式集合记作FS. 例如在表1中(ac)这个序列分别在10和40序列出现2次, 所以其支持数为2. 假设用户规定min sup 为2, 可知(ac)序列是频繁序列模式.定义5 前缀( Prefix) :设每个元素中的所有项目按照字典序排列.给定序列 = ,=( m n) ,如果ei= ei ( i m - 1) , em em ,并且(em- em) 中的项目均在em中项目的后面, 则称是的前缀;定义6 后缀(Suffix) : 序列关于子序列= 的投影为= ( n m) ,则序列关于子序列的后缀为 , 其
16、中em= ( em - em) ;定义7 投影：给定序列和，如果是的子序列，则关于的投影必须满足：是的前缀，是的满足上述条件的最大子序列.定义8投影数据库：设a为序列数据库S中的一个序列模式，则a的投影数据库为S中所有以a为前缀的序列相对于a的后缀，记为S|a.例：在表1中投影数据库由3个后缀序列组成：，,， 投影数据库.定义9 投影数据库中的支持数:设为序列数据库S 中的一个序列模式,序列以为前缀,则在的投影数据库S|中的支持数为S|中满足条件.的序列的个数. 表1 序列数据库Sid序列10a（abc）(cf)bd20eabc(ce)30cghd40(ac)bg(cf)f 三、序列模式简介3
17、.1 问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式.3.2 系统规定：由于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列.四、模式增长方法这类算法是一种基于投影的、分治的模式增长的方法, 即序列数据库先被投影为很多小投影数据库, 然后在小投影数据库中进行递归挖掘.4.1 FreeSpan 算法 4.1.1 FreeSpan算法思想FreeSpan ,即频繁模式投影的序列模式挖掘,其基本思想为:利用频繁项递归地将序列数据库投影到更小的投影数据库集中,在每个投影数据库中生成子序列片段.这一过程对数据
18、和待检验的频繁模式集进行了分割,并且将每一次检验限制在与其相符合的更小的投影数据库中.4.1.2 FreeSpan 算法执行过程的描述:(1) 首先给定序列数据库S 及最小支持度阈值.(2) 扫描序列数据库S，找到S中的频繁项集，并以降序排列生成f_list列表。 执行下面步骤：a. 根据生成的f_list列表把数据库分成几个不相交的子集。1） 只包含第一个项。2） 包含第二个项，但不包含以后的项。3） 包含第N项，但不包含N以后的项。4） 只包含最后一项。b.第一遍扫描数据库S，找出每个项及其与前一项组成的项在序列数据库中的频度，删除小于最小支持度的项。d.对生成的大于最小支持度的项递归的挖
19、掘出更长频度的序列。直至最后的投影数据库都是最大的频繁子集。4.1.3 FreeSpan 算法分析:它将频繁序列和频繁模式的挖掘统一起来,把挖掘工作限制在投影数据库中,还能限制序列分片的增长.它能有效地发现完整的序列模式,同时大大减少产生候选序列所需的开销,比基于Apriori 的GSP算法快很多.不足之处,它可能会产生许多投影数据库,如果一个模式在数据库中的每个序列中出现,该模式的投影数据库将不会缩减;另外,一个长度为k 的序列可能在任何位置增长,那么长度为k + 1的候选序列必须对每个可能的组合情况进行考察,这样所需的开销是比较大的. 对FreeSpan 中频繁项矩阵F占用存储空间的定量分
20、析如下:设序列数据库中有m个频繁项,频繁项矩阵共需要|M|= m +32(m-1)(m-2) 个计数单元。例如, m=1000 ,|M|=1.5106=3Mb(假设每个计数单元占用2b 的空间) ,目前一般的计算机就很容易满足这个要求4。4.2PrefixSpan 算法4.2.1 PrefixSpan算法的提出在许多应用中,如DNA分析和股市序列分析等,数据库常包含大量的序列模式,而且许多模式很长,此时有必要重新审视序列模式挖掘问题,以探索一些更加有效、易于扩展的方法.通过观察发现,基于Apriori算法的瓶颈在于每一步的候选集生成和测试,能否找到一种方法,既能吸取Apriori的灵魂又能避免
21、或者充分减少昂贵的候选集生成和测试.顺着这个思路, PeiJian ,Han Jiawei 及Wang Jianyong 等人基于分治和模式扩展的原理提出了模式扩展方法,代表性的算法有FreeSpan 和PrefixSpan ,其中PrefixSpan改进法采用了伪投影技术,性能比FreeSpan 好.下面描述并分析PrefixSpan 算法.4.2.2 PrefixSpan 算法思想及描述该算法就是通过前缀投影来挖掘序列模式, 进行投影时, 并不考虑所有出现的频繁子序列, 而是找出前缀序列, 把相应的后缀投影成为一系列的投影数据库. 对于每一个投影数据库, 只须找出局部频繁模式, 且不产生候
22、选码, 它的主要步骤如下: 扫描数据库一次, 找出频繁L2序列, 假设为k个; 划分研究空间: 把完整的序列模式划分为k个研究空间, 分别以频繁L2序列为前缀; 构造相应的数据库,也就是对应前缀的后缀集合; 在这些后缀集合中递归地发现频繁模式的子集.算法形式化描述如下:输入: 序列数据库S 和最小支持度min sup.输出: 所有的序列模式.方法:调用子程序PrefixSpan( , 0 , S )其中子程序PrefixSpan( , L , S|) 描述如下:(1) 扫描S|,找到满足下述要求的长度为1 的序列模式b :1) b 可以添加到的最后一个元素中并为序列模式;2) 可以作为的最后一
23、个元素并为序列模式.(2) 对每个生成的序列模式b ,将b 添加到形成序列模式,并输出;(3) 对每个,构造的投影数据库S|,并调用子程序PrefixSpan (,L + 1,S|) .子程序参数说明:为一个序列模式; L 为序列模式的长度; S|为的投影数据库(当为空时, S|就是S) .4.2.3 PrefixSpan算法分析：(1)PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间.(2)相对于原始的序列数据库而言，投影数据库的规模不断减小.(3)PrefixSpan算法的主要开销在于投影数据库的构造.4.2.4 PrefixSpan算法的主要改进：(1)逐层投影：使
24、用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数.(2)伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销. 其主要思想就是用指针指向对应序列, 用偏移量表示后缀起始位置, 这样就可用指针和偏移量代替真实投影, 从而在投影数据库中不重复出现后缀, 节省不少的空间. 例如: 序列数据库只有序列a(abc)(ac)d (cf) , 关于ab的投影数据库为(- c)(ac) d (cf) , 这时可以用(e ,4) 代替S |ab, 指针指向对应的序列, 而4表示后缀从第4 位置开始, 即从字符c 开始. 可见利用虚拟投影节省
25、了空间, 进一步提高了该类算法的性能6.4.2.5 PrefixSpan 算法与Apriori算法的比较经过测试比较,PrefixSpan 算法性能比基于Apriori的算法(GSP 和SPADE) 明显要好,原因在于:1) 模式扩展方式不生成候选序列。PrefixSpan 是一个基于模式扩展的方法,就象FP - growth 一样。用传统的候选集生成- 测试方法来处理一个比较小的数据库(例如只有10k 的序列) ,需要相当多的时间来生成和测试大量的候选序列模式。2) 基于投影的分治是数据缩减( reduction) 的有效方法。序列模式的投影数据库包含且仅包含用来挖掘那些由扩展得到的模式的必
26、需信息, 投影数据库的大小随着挖掘过程向更长的序列模式进行而迅速缩减。3) PrefixSpan 需要的内存空间相对稳定。原因在于它采用分治的方法,不生成候选集。而GSP 和SPADE ,当支持度阈值(support threshold) 降低时,由于需要容纳大量候选序列,需要相当数量的内存。基于模式扩展的方法,可以应用到多层次、多维数的序列模式中,也可以挖掘其他结构化的模式。五、实例解析：例 给定如下表所示的序列数据库，分别用FreeSpan和PrefixSpan算法进行计算，设最小支持度为2，并给出详细过程.TABLE 2Sequence_idSequence10203040、利用Free
27、Span算法解析：1. (1)找到频繁项集：频繁项按支持度降序排列形成频繁项列表f_List= (注意：由于g：12,所以剪去。) (2)根据f_List，序列模式集被分为不相交的六个子集： 1)只包含项. 2)含项,但不包括以后的项。如正确，但错误。 3)含项,但不包括以后的项。 4）含项,但不包括以后的项 5）含项,但不包括以后的项 6)包含项. (3)分而自治策略。如序列模式 的投影数据库是含有的序列集的子序列，非频繁项及a后的项也被删除。在数据库中含的项，但只有:2被保留，其余全部删除。又如序列模式的投影数据库是含有的序列子集的子序列。其中包括与以前的项所一起组成的子序列。挖掘以投影的
28、数据,. 再次扫猫数据库，挖掘出长度为2的序列，如:4,2,:3,:3,:2,:3,接下来我们再次扫猫以为前缀的投影数据库，包括,并以此生成长度为3的序列模式，即有:3,:3,:2,:2.对于挖掘数据库如下,此时我们发现找不到长度为4的序列模式。则此时就到此结束，即为一个频繁序列子集。相似的，对于其他的序列模式我们也如此的进行递归的投影。最终得到的频繁序列子集如下表。 、利用PrefixSpan算法解析：1.查找长度为1的序列模式 :4,:4,:4,:3,:3,:32.分割搜索空间序列模式集可按6个前缀被划分为六个子集：1）包含前缀的子集；2）包含前缀的子集；3）包含前缀的子集；4）包含前缀的
29、子集；5）包含前缀的子集；6）包含前缀的子集。3.寻找序列模式的子集。构建并递归挖掘投影数据库。 (1) 寻找具有前缀的序列模式。 (2) 投影数据库，由4个后缀序列组成：，。 (3) 扫描投影数据库一遍，找到含有前缀的长度为2的序列模式，包括：2，：4，：2，：4，：2，：2。(4) 递归，所有具有前缀的序列划分为6个子集：1）包含前缀的子集；6）包含前缀的子集(5) 投影数据库：。不产生任何频繁子序列，结束。投影数据库：，包含前缀的序列模式有：,。即,投影数据库：，。序列模式：， 即，。直到都投完。然后继续以没有结束的3-序列模式继续投影，如投影数据库：，包含前缀的序列模式有：，找到含有前
30、缀的序列模式，包括：。最终序列模式如下图所示： 前缀投影（后缀）数据库序列模式, ,六：对prefixspan算法的VC程序的实现 6.1 prefixspan算法的流程图类似投影的方法对其他进行投影投影数据库，由4个后缀序列组成：，。寻找具有前缀的序列模式寻找具有前缀的序列模式第一次扫描数据库S，查找长度为1的序列模式:4,:4,:4,:3,:3,:3开始给定序列数据库S 及最小持度阈值分割搜索空间序列模式集可按6个前缀被划分为六个子集1）包含前缀的子集；6)包含前缀的子集寻找序列模式的子集。构建并递归挖掘投影数据库寻找序列模式的子集。构建并递归挖掘投影数据库(5) 投影数据库：。不产生任何
31、频繁子序列，结束。投影数据库：，包含前缀的序列模式有：,。即,投影数据库：，。序列模式：， 即，。直到都投完。扫描投影数据库一遍，找到含有前缀的长度为2的序列模式，包括：2，：4，：2，：4，：2，：2。 递归，所有具有前缀的序列划分为6个子集1）包含前缀的子集；6）包含前缀的子集结束所有的序列模式6.2 算法执行结果本算法只是针对给定的特定的数据库序列数据进行挖掘，结合对prefixspan算法的理解的基础上，对prefixspan实现了简单的编程，在VC的编程环境下，利用控制台程序来实现对算法的运行。算法的运行结果基本和上述算法的结果吻合。实验结果会在Debug文件下生成一个output.
32、txt文档。结果保存在output.txt文件中6.3 结果分析通过对算法的结果来看，比较更加容易的理解算法的基本性能，但是对于其他数据来说仍然比较吃力。七、结论与展望序列模式挖掘是当前数据挖掘领域中一个较新而且非常活跃的研究分支,有着广泛的应用价值。文章在介绍了序列模式挖掘的相关概念后,对一类序列模式挖掘的2个经典的算法进行了描述和分析,不难发现,基于模式扩展的方法是个前途很好的发展方向。模式扩展方法还有很多工作要做,如闭合集挖掘、在特定领域的针对性研究等等。通过文章我们了解到FreeSpan 和PrefixSpan 属于模式增长方法,它们采用分而治之的方法,大大提高了算法的效率。但在实际应
33、用中,在挖掘过程的不同阶段,数据集的特点,数据规模等因素可能不同,如果根据各阶段的特点,选择与之相应的算法,则序列模式挖掘能达到更好的效果。面对一个具体的实例,例如股票序列分析中,如何根据不同阶段的数据集的特点选择合适的算法,这些数据挖掘算法的结论信息又如何链接、传输、共享和兼容等,这些问题都是我们今后工作的研究内容。八、致谢 九、参考文献 1吕锋，张炜伟。4 种序列模式挖掘算法的特性研究，武汉理工大学学报。2006年2月第28卷第2期。2 HAN J ia-wei, PE I J ian. Freespan: frequent pattern -p ro jected sequential
34、pattern mining C /Proc of the 2000Internat ional Conference on Know ledge D iscovery and DataM ining (KDD). New York: ACM Press, 2000: 3552-359.3 PE I J ian, HAN Jia-wei, PINTOH, etal. PrefixSpan: mining sequential patterns efficiently by prefix-projectedpattern growth C /Proc 2001 Int Conf Data Eng
35、in ( ICDE01). Los A lam ito s: IEEE Computer Society Press,2001: 2152224.4 MANNILAH, TO IVON EN H, V ERKAMO A I. D iscovery of frequent ep isodes in event sequences J . DataM in & Know lD iscovery, 1996, 1 (3) : 2582289.5 张大海，胡孔法，陈凌。序列模式算法综述。扬州大学学报（自然科学版），2007年2月第10卷第1期。6 夏明，王晓川，孙永强，金士尧。 序列模式挖掘算法研究。
36、计算机技术与发展。2006年第16卷第4期。十、附录算法实现的主要程序如下：一：prefixspan.cpp#pragma warning(disable: 4786)#include #include #include #include #include #include #include #include #include #include prefixspan.husing namespace std;#define SAME_SET_#define MAX_FR_SIZE(unsigned int)32768/输出帮助信息void show_help()std:cout -n Pref
37、ix span test scriptn -nn Usage: tprefixspan_test INPUT_NAME -sMIN_SUPP OUTPUT_NAME or n tprefixspan_test INPUT_NAME -fMIN_FR OUTPUT_NAMEnn Default output name is output.txtnn; /读取输入数据文件到内存int read_input(INFILE &f, sequence_database &db)sequence current_row;item current_item;itemset current_set;std:s
38、tring buff;std:getline( f, buff);while ( !f.eof()current_item.erase();current_set.clear();current_row.clear();for ( unsigned int i = 0; i buff.size(); +i)if ( | = buffi)/ this means that were at the end of an itemcurrent_set.push_back( current_item);current_item.erase();else if ( = buffi | t = buffi)/ 正处在项集第1项if ( 0
