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

1、灰曲理N号彷毕业论文（设计）题目基于投影数据挖掘算法研究与实现学生姓名郭凯学号041842020院（系）学系专业班级信息与计算科学043班指导教师痛流完成地点数学系数据挖掘实验室2008年6月9日基于投影数据挖掘算法研究与实现作者：郭凯（陕西理工学院数学系信息与计算科学专业043班陕西723001）指导教师：周涛摘要：序列模式的发现是数据挖掘领域一个活跃的研究分支，即在序列数据库中找出所有的频繁子序列.本文先介绍序列模式挖掘中的一些基本概念，然后详细描述FreeSpan和PrefixSpan2个基于投影、分治的模式增长的重要算法。基于投影方法即序列数据库先被投影为很多小投影数据库，然后在小投影

2、数据库中进行递归挖掘的典型算法.其中FreeSpan算法是将数据库分成若干个子空间，再每个子空间里进行递归的的投影，对于每一个项及其与前一项组合成的序列模式进行投影挖掘，最终得出频繁子序列。PrefixSpan算法则是先找出长度为1的序列模式，以此序列模式为前缀的投影，并在投影数据库里面继续递归的进行投影，最终得出频繁子序列。本文并以实例解析，更为详细清楚的描述了两种算法的过程。关键词:数据挖掘；FreeSpan算法；PrefixSpan算法;AccordingtocastshadowadatatoscoopoutcalculatewayresearchAuthor:GuoKai(Grade0

3、4,Class03,Informationandcalculationscience,DepartmentofMathematics,ShaanxiUniversityofTechnology,Hanzhong723000,Shaanxi)tutor:ZhouTaoAbstractSequencemodedataminingisthediscoveryofanactiveareaofresearchbranch,thatis,allsequencesinthedatabasetoidentifythefrequencyofsequence.Inthispaper,firstintroduced

4、inthesequencepatternminingsomeofthebasicconcepts,andthendescribedindetailFreeSpanandPrefixSpan2basedprojection,thepartitionoftheimportantgrowthpatternalgorithm.Basedontheprojectionmethodthatsequencedatabasewasfirstprojectionforthemanysmallprojectiondatabase,andthenasmallprojectiondatabaseMiningtypic

5、alrecursivealgorithm.WhichFreeSpanalgorithmisdividedintoseveralsub-databasespace,theneachoftherecursivespacefortheprojector,andforeachandeveryitemwithacombinationof10%oftheformermodelprojectionexcavationsequence,thefinalsequenceofdrawnfrequent.ThePrefixSpancalculatewaythenfindoutthelengthasonesequen

6、cemodefirst,takethissequencemodeascastshadowofex-Zhui,andcontinuetopasstoreturnintheprojectionthedatabaseofcarryoncastshadow,endgetmultifarioussub-sequence.Analysisandexamplesinthispaper,amoredetaileddescriptionofthetwoclearlyalgorithmprocess.KeywordsThedatascoopout;FreeSpanarithmetic;PrefixSpanarit

7、hmetic;目录一引言5二序列模式挖掘相关知识52.1 基本术语52.2 基本定义5三序列模式简介62.1 问题描述错误！未定义书签。2.2 系统规定错误！未定义书签。四模式增长方法61 freespan算法61.4 freespan算法的思想61.4 freespan算法执行过程的描述错误！未定义书签。1.4 freespan算法的分析71 prefixspan算法71.5 prefixspan算法的提出71.5 prefixspan算法的思想及描述71.5 prefixspan算法的分析81.5 prefixspan算法的主要改进81.5 prefixspan算法和Aporiori算法的

8、比较8五实例解析9I利用freespan算法解析错误！未定义书签。n利用PrefixSpan算法解析错误！未定义书签。六对prefixspan算法的VC®序的实现12(1) prefixspan算法的流程图12(1) 算法的执行结果13(1) 算法结果分析14七结论与展望15八致谢15九参考文献16十附录17序列模式挖掘是数据挖掘研究的一个重要课题，而且具有非常广泛的应用，被应用在包括顾客购买行为的分析、网络访问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害的预测、DNA序列模式的分析等1.目前对序列模式挖掘问题的研究主要集中在算法设计和实际应用，在理论方面研究还很罕见.序列

9、模式挖掘是对关联规则挖掘的进一步推广，它挖掘出序列数据库中项集间的时序关联规则是数据挖掘研究的一个重要内容.早先的很多关联规则挖掘研究都有助于挖掘序列模式或者与时间相关的频繁模式.SRIKANTAGRAWAL序列规定了时间限制、滑动时间窗口和用户规定的分类，并总结了序列模式的定义，提出一种基于Apriori的改进算法GSP(generalizedsequentialpatterns)算法.以上这些都是基于Apriori的水平格式的序列模式挖掘或者与时间相关的频繁模式挖掘.后来，ZAKI提出了一种基于垂直格式存储的序列模式挖掘方法SPAD算法，该算法由基于垂直格式的频繁项挖掘演化而来.近几年，H

10、AN人又提出一种基于投影的模式增长算法Freespan(FrequentPattern-pojectedSequentialPatternMining)算法，该算法改进后为Pre巾xSpan(Prefix-ProjectedSequentialPatternsMining)算法网，性能进一步提高.MANNILA等人4提出的挖掘频繁序列片段问题，GAROFALAKI等人提出的基于规则表达式约束的序列模式挖掘，还有关于序列模式挖研究的一些扩展，如序列模式闭项挖掘、并行挖掘、分布式挖掘、多维度序列模式挖掘和近似序列模式挖掘等，所有这些对后来研究序列模式挖掘都有一定的影响.本文重点对典型的序列模式挖掘

11、算法FreeSpan和PrefixSpan两种典型算法进行详细的描述、分析和比较二、序列模式挖掘的相关知识基本术语设I=i1,i2,in是一个项目集合，项目集或者项集(items)就是各种项目组成的集合，即I的所有子集.一个序列就是若干项集的有序列表，一个序列S可表示为s1,s2,sn>,其中sj为项集，也称作S勺元素.元素由不同的项组成，可表示为(x1,x2,xn).当元素只包含一项时，一般省去括号，如(x2)一般表示为x2.元素之间是有顺序的，但元素内的项是无序的，一般定义为词典序.序列包含项的个数称为序列的长度，长度为L的序列记为L-序列.序列数据库就是元组(tuples)sid,

12、s>的集合，其中s是序列，sid是该序列的序列号，元组的个数称为序列数据库的大小，记作|SDB|.基本定义定义1序列模式：给定一个由不同序列组成的集合，其中，每个序列由不同的元素按顺序有序排列，每个元素由不同项目组成，同时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列，即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值定义2子序列和超序列：对于序列A=a1,a2,an>和B=b1,b2,bm>,当且仅当1Wj1<j2V,<jm<m且a1?j1,a2?j2,an?jn时，称序列B为序列A的超序列，序列A为序列B的子序列，又称序

13、列B包含序列A,记作A?B.例如在表1中a(abc)(cf)bd>这个序列，其中(abc)>,a(abc)(cf)>者B是a(abc)(cf)bd>的子序列，a(abc)(cf)bd>是(abc)>,a(abc)(cf)>的超序列.定义3支持数：序列数据库比元组sid,S>的集合，sid为序列标识号.如果序列T是S勺子序列(即T?S),称元组sid,S>包含序列T,则序列T在序列数据库D43的支持数是数据库中包含T的元组数，即supportD(T)=|sid,S>|sid,S>CDAT?S|,记作support(T).定义4频繁

14、序列模式：给定一个最小支持度阈值minsup,如果序列s的支持度不小于minsup,则称序列s为频繁序列模式，所有的频繁序列模式集合记作FS.例如在表1中(ac)>这个序列分别在10和40序列出现2次，所以其支持数为2.假设用户规定minsup为2,可知(ac)序列是频繁序列模式.定义5前缀(Pre巾x):设每个元素中的所有项目按照字典序排列.给定序列“=<ele2,""en>,3=<el'e2',em'>(m<n),如果ei'=ei(i<m-1),em'?em,并且(em-em')中

15、的项目均在em'中项目的后面，则称3是a的前缀；定义6后缀(Suffix):序列a关于子序列3=<e1e2,em-1em'>的投影为J=<e1en>,其中enf=(eme2,en>(n>m),则序列a关于子序列3的后缀为<enVem+1,定义7投影：给定序列a和3,如果3是a的子序列，则a关于3的投影a'必须满足:a'的前缀，a'是a的满足上述条件的最大子序列.定定义8投影数据库：设值为序列数据库什的一个序列模式，则3的投影数据库为S中所有以口为前缀的序列相对于a的后缀，记为S|o(.例：在表1中9>一投影

16、数据库由3个后缀序列组成：<(abc)(cf)bd>,<bc(ce)>,<(_c)bg(cf)f>,<(ab)>投影数据库<(_c)(cf)bd>.定义9投影数据库中的支持数：设”为序列数据库S中的一个序列模式，序列3以a为前缀，则3在a的投影数据库S|a中的支持数为S|a中满足条件3?a.丫的序列丫的个数.表1序列数据库Sid序列10a(abc)(cf)bd20eabc(ce)30cghd40(ac)bg(cf)f三、序列模式简介问题描述：给定序列数据库和最小支持度阈值，序列模式挖掘就是要找出序列数据库中所有的序列模式.系统规定：由

17、于同一个元素中的项目之间排列没有顺序，为了表达的唯一性，我们将同一个元素内部的不同项目按照字典顺序排列四、模式增长方法这类算法是一种基于投影的、分治的模式增长的方法，即序列数据库先被投影为很多小投影数据库，然后在小投影数据库中进行递归挖掘.1FreeSpan算法FreeSpan算法思想FreeSpan,即频繁模式投影的序列模式挖掘，其基本思想为：利用频繁项递归地将序列数据库投影到更小的投影数据库集中，在每个投影数据库中生成子序列片段.这一过程对数据和待检验陕西理工学院毕业设计的频繁模式集进行了分割，并且将每一次检验限制在与其相符合的更小的投影数据库中.FreeSpan算法执行过程的描述：(1)

18、首先给定序列数据库S及最小支持度阈值8.2)扫描序列数据库S,找到S中的频繁项集，并以降序排列生成f_list列表。执行下面步骤：a.根据生成的f_list列表把数据库分成几个不相交的子集。1)只包含第一个项。2)包含第二个项，但不包含以后的项。3)包含第N®,但不包含NH后的项。4)只包含最后一项。b.第一遍扫描数据库S,找出每个项及其与前一项组成的项在序列数据库中的频度，删除小于最小支持度的项。d.对生成的大于最小支持度的项递归的挖掘出更长频度的序列。直至最后的投影数据库都是最大的频繁子集。4.1.3FreeSpan算法分析：它将频繁序列和频繁模式的挖掘统一起来，把挖掘工作限制在

19、投影数据库中，还能限制序列分片的增长.它能有效地发现完整的序列模式，同时大大减少产生候选序列所需的开销，比基于Apriori的GSPT法快很多.不足之处，它可能会产生许多投影数据库，如果一个模式在数据库中的每个序列中出现，该模式的投影数据库将不会缩减；另外，一个长度为k的序列可能在任何位置增长，那么长度为k+1的候选序列必须对每个可能的组合情况进行考察，这样所需的开销是比较大的.又FreeSpan中频繁项矩阵F占用存储空间的定量分析如下：设序列数据库中有m频繁项，频繁项矩阵共需要|M|=m+32X(m-1)x(m-2)个计数单元。例如，m=1000,|M|=1.5x106=3Mb(假设每个计数

20、单元占用2b的空间)，目前一般的计算机就很容易满足这个要求4。4.2PrefixSpan算法PrefixSpan算法的提出在许多应用中，如DN刚析和股市序列分析等，数据库常包含大量的序列模式，而且许多模式很长，此时有必要重新审视序列模式挖掘问题，以探索一些更加有效、易于扩展的方法.通过观察发现，基于Apriori算法的瓶颈在于每一步的候选集生成和测试，能否找到一种方法，既能吸取Apriori的灵魂又能避免或者充分减少昂贵的候选集生成和测试.顺着这个思路，PeiJian,HanJiawei及WangJianyong等人基于分治和模式扩展的原理提出了模式扩展方法，代表性的算法有FreeSpan和P

21、re巾xSpan，其中PrefixSpan改进法采用了伪投影技术，性能比FreeSpan好.下面描述并分析PrefixSpan算法.PrefixSpan算法思想及描述该算法就是通过前缀投影来挖掘序列模式，进行投影时，并不考虑所有出现的频繁子序列，而是找出前缀序列，把相应的后缀投影成为一系列的投影数据库.对于每一个投影数据库，只须找出局部频繁模式，且不产生候选码，它的主要步骤如下：扫描数据库一次，找出频繁L2序列，假设为k个；划分研究空间：把完整的序列模式划分为k个研究空间，分别以频繁L2序列为前缀；构造相应的数据库，也就是对应前缀的后缀集合；在这些后缀集合中递归地发现频繁模式的子集算法形式化描

22、述如下：输入：序列数据库S和最小支持度minsup.输出：所有的序列模式.方法：调用子程序PrefixSpan(<>,0,S)其中子程序PrefixSpan(a,L,S|a)描述如下：(1)扫描S|a,找到满足下述要求的长度为1的序列模式b:b可以添加到a的最后一个元素中并为序列模式；<b>可以作为a的最后一个元素并为序列模式.(2)对每个生成白序列模式b，将b添加到a形成序列模式a',并输出a'；(3)对每个a',构造a'的投影数据库S|a'，并调用子程序PrefixSpan(a',L+1,S|a').子程序参数

23、说明：a为一个序列模式；L为序列模式a的长度；S|a为a的投影数据库(当a为空时，S|a就是S).PrefixSpan算法分析：(1)PrefixSpan算法不需要产生候选序列模式，从而大大缩减了检索空间(2)相对于原始的序列数据库而言，投影数据库的规模不断减小(3)PrefixSpan算法的主要开销在于投影数据库的构造.PrefixSpan算法的主要改进：(1)逐层投影：使用隔层投影代替逐层投影，从而可以有效减小投影数据库的个数(2)伪投影：当序列数据库可以直接放入内存时，可以使用伪投影操作代替实际的投影数据库，从而可以有效减少构造投影数据库的开销.其主要思想就是用指针指向对应序列，用偏移量

24、表示后缀起始位置，这样就可用指针和偏移量代替真实投影，从而在投影数据库中不重复出现后缀，节省不少的空间.例如：序列数据库只有序列a(abc)(ac)d(cf)>,关于ab的投影数据库为(-c)(ac)d(cf)>,这时可以用(e,4)代替S|<ab>,指针指向对应的序列，而4表示后缀从第4位置开始，即从字符c开始.可见利用虚拟投影节省了空间，进一步提高了该类算法的性能.PrefixSpan算法与Apriori算法的比较经过测试比较，PrefixSpan算法性能比基于Apriori的算法(GSP和SPADE)明显要好，原因在于：1)模式扩展方式不生成候选序列。Prefix

25、Span是一个基于模式扩展的方法，就象FP-growth一样。用传统的候选集生成-测试方法来处理一个比较小的数据库(例如只有10k的序列)，需要相当多的时间来生成和测试大量的候选序列模式。2)基于投影的分治是数据缩减(reduction)的有效方法。序列模式”的投影数据库包含且仅包含用来挖掘那些由a扩展得到的模式的必需信息，投影数据库的大小随着挖掘过程向更长第8页共27页的序列模式进行而迅速缩减。3)PrefixSpan需要的内存空间相对稳定。原因在于它采用分治的方法,不生成候选集。而GSP和SPADE，当支持度阈值(supportthreshold)降低时，由于需要容纳大量候选序列，需要相当

26、数量的内存。基于模式扩展的方法，可以应用到多层次、多维数的序列模式中，也可以挖掘其他结构化的模式。五、实例解析:例给定如下表所示的序列数据库，分别用FreeSpan和PrefixSpan算法进行计算，设最小支持度为2,并给出详细过程.TABLE2Sequence_idSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>I、禾1J用FreeSpan算法解析：1.(1)找到频繁项集：频繁项按支持度降序排列形成频繁项列表f_List=<a:4,b:4

27、,c:4,d:3,f:3,e:2>(注意：由于g:1<2,所以剪去。)根据f_List,序列模式集被分为不相交的六个子集：只包含项<a>.含项<b>,但不包括<b>以后的项。如<ab>正确，但<bc>错误。含项<c>,但不包括<c>以后的项。)含项<d>,但不包括<d>以后的项)含项<f>,但不包括<f>以后的项包含项<e>.分而自治策略。如序列模式<a>的投影数据库是含有<a>的序列集的子序列，非频繁项及a后的项也

28、被删除。在数据库中含<a>的项<aaa><aa><a><a>，但只有<aa>:2被保留，其余全部删除。又如序列模式<c>的投影数据库是含有<c>的序列子集的子序列。其中包括与<c>以前的项所一起组成的子序列。挖掘以<C>影的数据<a(abc)(ac)c>,<ac(bc)a>,<(ab)cb>,<acbc>.再次扫猫数据库，挖掘出长度为2的序列，如<ac>:4,<(bc)>2,<bc>:3,&l

29、t;cc>:3,<ca>:2,<cb>:3,接下来我们再次扫猫以<ac>为前缀的投影数据库，包括<a(abc)(ac)c>,<ac(bc)a>,<acbc>,并以此生成长度为3的序列模式，即有<acb>:3,<acc>:3,<(ab)c>:2,<aca>:2.对于<acb>挖掘数据库如下<ac(bc)a>,<(ab)cb>,<acbc>,此时我们发现找不到长度为4的序列模式。则此时<acb>就到此结束，<

30、acb>即为一个频繁序列子集。相似的，对于其他的序列模式我们也如此的进行递归的投影。最终得到的频繁序列子集如下表。n、利用PrefixSpan算法解析：.查找长度为1的序列模式<a>:4,<b>:4,<c>:4,<d>:3,<e>:3,<f>:3.分割搜索空间序列模式集可按6个前缀被划分为六个子集：1)包含前缀<a>的子集；2)包含前缀<b>的子集；3)包含前缀<c>的子集；4)包含前缀<d>的子集；5)包含前缀<e>的子集；6)包含前缀<f>的

31、子集。.寻找序列模式的子集。构建并递归挖掘投影数据库。(1)寻找具有前缀<a>的序列模式。<a>一投影数据库，由4个后缀序列组成：<(abc)(ac)d(cf)>,<(_d)c(bc)(ae)>,<(_b)(df)cb>,<(_f)cbc>。(3)扫描<a>投影数据库一遍，找到含有前缀<a>的长度为2的序列模式，包括：<aa>:<ab>:4,<(ab)>:2,<ac>:4,<ad>:2,<af>:2。(4)递归，所有具有前缀&l

32、t;a>的序列划分为6个子集：1)包含前缀<aa>的子集；,；6)包含前缀<af>的子集<aa>一投影数据库：<(_bc)(ac)d(cf)>。不产生任何频繁子序列，结束。<(ab)>一投影数据库：<(_c)(ac)d(cf)>,<(df)cb>,包含前缀<(ab)>的序列模式有：<c>,<d>,<f>,<dc>。即<(ab)c>,<(ab)d>,<(ab)f>,<(ab)dc><ab>

33、一投影数据库：<(_c)(ac)d(cf)>,<(_c)a>,<c>。序列模式：<(_c)>,<(_c)a>,<a>,<c>,即<a(bc)>,<a(bc)a>,<aba>,<abc>。,直到<af>都投完。然后继续以没有结束的3-序列模式继续投影，如<(ab)d>一投影数据库：<(cf)>,<(_f)cb>包含前缀<(ab)d>的序列模式有：<c>,找到含有前缀<(ab)d>的序

34、列模式，包括：第10页共27页<(ab)dc>。最终序列模式如下图所示:前缀投影（后缀）数据库序列模式<a><(abc)(ac)d(cf)>,<(_d)c(bc)(ae)>,<(_b)(df)cb>,<(_f)cbc><a>,<aa>,<ab>,<a(bc)>,<a(bc)a>,<aba>,<abc>,<(ab)>,<(ab)c>,<(ab)d>,<(ab)f>,<(ab)dc>,

35、<ac>,<aca>,<acb>,<acc>,<ad>,<adc>,<af><b><(_c)(ac)d(cf)>,<(_c)(ae)>,<(df)cb>,<c><b>,<ba>,<bc>,<(bc)>,<(bc)a>,<bd>,<bdc>,<bf><c><(ac)d(cf)>,<(bc)(ae)>,<b>,&l

36、t;bc><c>,<ca>,<cb>,<cc><d><(cf)>,<c(bc)(ae)>,<(_f)cb><d>,<db><dc>,<dcb><e><(_f)(ab)(df)cb>,<(af)cbc><e>,<ea>,<eab>,<eac>,<eacb>,<eb>,<ebc>,<ec>,<ecb>,<

37、;ef>,<efb>,<efc>,<efcb><f><(ab)(df)cb>,<cbc><f>,<fb>,<fbc>,<fc>,<fcb>六：Mprefixspan算法的Vd序的实现prefixspan算法的流程图分割搜索空间序列模式集可按6个前缀被划分为六个子集1）包含前缀a的子集；，；6）包含前缀f的子集算法执行结果prefixspan算法的本算法只是针对给定的特定的数据库序列数据进行挖掘，结合对理解的基础上，对prefixspan实现了简单的编程，在V

38、C勺编程环境下，利用控制台程序来实现对算法的运行。算法的运行结果基本和上述算法的结果吻合。实验结果会在Debug文件下生成一个output.txt文档。Hicrosoftilindo忖零XPl版本5.L.26阙】<C>版权所有198S-2001NicrosoFtCorp.一.I:C：XDocumiits«ndSettingsfkdninistrator>cdC;XJDociirwnts<ndSettingsXftdRijnlstrat口DociinntsXgkPi*efixspanDehugrC-XltocurnntsandSnttingsMHdRiniiit

39、ratdrMlyDocuMntskXPTvfixBjMfiXllebug>prefi翼匕pan_testa.txt-f0>.2DeciiiwntsandSettIngsNAldpilnistratorMlyDocumentsgJ«Pre£ix&p4nxDebuig>结果保存在output.txt文件中de|be|cbb|cb|c|dfbc|df|efb|c|eFb|dfb|df|eFbeFbecc|dfc|dfefcef结果分析通过对算法的结果来看，比较更加容易的理解算法的基本性能，但是对于其他数据来说仍然比较吃力。七、结论与展望序列模式挖掘是当前

40、数据挖掘领域中一个较新而且非常活跃的研究分支，有着广泛的应用价值。文章在介绍了序列模式挖掘的相关概念后，对一类序列模式挖掘的2个经典的算法进行了描述和分析，不难发现，基于模式扩展的方法是个前途很好的发展方向。模式扩展方法还有很多工作要做，如闭合集挖掘、在特定领域的针对性研究等等。通过文章我们了解到FreeSpan和PrefixSpan属于模式增长方法，它们采用分而治之的方法，大大提高了算法的效率。但在实际应用中，在挖掘过程的不同阶段，数据集白特点，数据规模等因素可能不同，如果根据各阶段的特点，选择与之相应的算法，则序列模式挖掘能达到更好的效果。面对一个具体的实例，例如股票序列分析中，如何根据不

41、同阶段的数据集的特点选择合适的算法，这些数据挖掘算法的结论信息又如何链接、传输、共享和兼容等，这些问题都是我们今后工作的研究内容。八、致谢九、参考文献吕锋，张炜伟。4种序列模式挖掘算法的特性研究，武汉理工大学学报。2006年2月第28卷第2期。HANJia-wei,PEIJian.Freespan:frequentpattern-projectedsequentialpatternminingC/Procofthe2000InternalionalConferenceonKnowledgeDiscoveryandDataMining(KDD).NewYork:ACMPress,2000:355

42、2-359.PEIJian,HANJia-wei,PINTOH,etal.PrefixSpan:miningsequentialpatternsefficientlybyprefix-projectedpatterngrowthC/Proc2001IntConfDataEngin(ICDE01).LosAlamitos:IEEEComputerSocietyPress,2001:2152224.MANNILAH,TOIVONENH,VERKAMOAI.DiscoveryoffrequentepisodesineventsequencesJ.DataMin&KnowlDiscovery,

43、1996,1(3):2582289.5张大海，胡孔法，陈凌。序列模式算法综述。扬州大学学报(自然科学版)，2007年2月第10卷第1期。6夏明，王晓川，孙永强，金士尧。序列模式挖掘算法研究。11算机技术与发展。2006年第16卷第4期。十、附录算法实现的主要程序如下：一：prefixspan.cpp#pragmawarning(disable:4786)#include<iostream>#include<fstream>#include<string>#include<vector>#include<list>#include<

44、;set>#include<map>#include<math.h>#includealgorithm#include"prefixspan.h"usingnamespacestd;#defineSAME_SET"_"#defineMAX_FR_SIZE(unsignedint)32768/输出帮助信息voidshow_help()(std:cout<<"n"<<"Prefixspantestscriptn"<<"nn"<&

45、lt;"Usage:'tprefixspan_testINPUT_NAMEsMIN_SUPPOUTPUT_NAMEorn<<"'tprefixspan_testINPUT_NAME-fMIN_FROUTPUT_NAMEnn"<<"Defaultoutputnameis'output.txt'nn")/读取输入数据文件到内存intread_input(INFILE&f,sequence_database&db)(sequencecurrent_row;itemcurrent_

46、item;itemsetcurrent_set;std:stringbuff;std:getline(f,buff);while(!f.eof()(current_item.erase();current_set.clear();current_row.clear();for(unsignedinti=0;i<buff.size();+i)(if('|'=buffi)/thismeansthatwe'reattheendofanitemcurrent_set.push_back(current_item);current_item.erase();)elseif(

47、''=buffi|'t'=buffi)/正处在项集第1项(if(0<current_item.size()/跳过多个空格(current_set.push_back(current_item);current_item.erase();current_set.sort();/排序项目当前"设置"current_row.push_back(current_set);current_set.clear();)else(current_item+=buffi;/处在项目的中间，必须扩大)current_set.push_back(curren

48、t_item);current_set.sort();current_row.push_back(current_set);db.push_back(current_row);std:getline(f,buff);/读取一行)return0;)/输出一个序列std:ostream&print_sequence(std:ostream&f,constsequence&s)for(sequence:const_iteratorit=s.begin();it!=s.end();+it)(itemset:const_iteratoris_it=it->begin();f

49、<<(*is_it);for(+is_it;is_it!=it->end();+is_it)f<<"|"<<(*is_it);)f<<"")returnf;)/输出一个数据库std:ostream&print_database(std:ostream&f,constsequence_database&db)for(sequence_database:const_iteratorit=db.begin();it!=db.end();+it)print_sequence(f,(*i

50、t);f<<std:endl;)returnf;)/输出序列列表std:ostream&print_list(std:ostream&f,constsequence_listl)(intk=0;for(sequence_list:const_iteratorit=l.begin();it!=l.end();+it)(if(k%2=0)print_sequence(f,(*it);f<<"n"+k;)returnf;)/c计算最小支持度unsignedintcalc_min_supp(constsequence_database&

51、;db,floatmin_freq)(return(unsignedint)ceil(float)db.size()*min_freq);)/计算支持计数voidcount_frequencies(constsequence_database&db,frequency_counter&fc)(for(sequence_database:const_iteratorrow_it=db.begin();row_it!=db.end();+row_it)(set_of_itemsitems_in_the_row;for(sequence:const_iteratorseq_it=ro

52、w_it->begin();seq_it!=row_it->end();+seq_it)(for(itemset:const_iteratorset_it=seq_it->begin();set_it!=seq_it->end();+set_it)/puttingtheitemsinaset=>eachwilloccuronceitems_in_the_row.insert(*set_it);)/在每个项目该行时增加支持度for(set_of_items:iteratoritems_it=items_in_the_row.begin();items_it!=ite

53、ms_in_the_row.end();+items_it)+fc(*items_it);)/序列扩展voidextend_prefix_sequence(constsequence&old_prefix,constitem&alfa,sequence&new_prefix)new_prefix=old_prefix;itemsettmp_set;tmp_set.push_back(alfa);new_prefix.push_back(tmp_set);/项集扩展voidextend_prefix_itemset(constsequence&old_prefix

54、,constitem&beta,sequence&new_prefix)new_prefix=old_prefix;itemset&tmp_set=new_prefix.back();tmp_set.push_back(beta);/剪切序列前缀voidcut_sequence(sequence&s,sequence:iterator&seq_it,itemset:iterator&item_pos)seq_it->erase(seq_it->begin(),+item_pos);if(seq_it->empty()+seq_i

55、t;elseseq_it->push_front(SAME_SET);s.erase(s.begin(),seq_it);/构造序列数据库voidproject_database_sequence(constsequence_database&db,constitem&alfa,sequence_database&projected_db)projected_db.clear();for(sequence_database:const_iteratorrow_it=db.begin();row_it!=db.end();+row_it)sequencecurren

56、t_row=(*row_it);booldone=false;for(sequence:iteratorseq_it=current_row.begin();!done&&seq_it!=current_row.end();+seq_it)itemset:iteratoralfa_pos=find(seq_it->begin(),seq_it->end(),alfa);陕西理工学院毕业设计itemset:iteratorindicator_pos=find(seq_it->begin(),seq_it->end(),SAME_SET);/wehaveav

57、alidsuffix,ifthenewitemalfaisin/anitemsetthatdoesn'tcontainthejokerch.if(seq_it->end()!=alfa_pos&&seq_it->end()=indicator_pos)done=true;cut_sequence(current_row,seq_it,alfa_pos);projected_db.push_back(current_row);/检查序列的最后一个项集是否在给定的项集中boolis_full_prefix_included(itemset&current

58、_set,constitemset&prefix_end,constitem&beta,itemset:iterator&beta_pos)boolprefix_found=true;itemset:iteratoritem_pos=current_set.begin();for(itemset:const_iteratorit=prefix_end.begin();prefix_found&&it!=prefix_end.end();+it)/it'senoughtocheckfromthelastfoundposition,/sincethe

59、listsareordereditem_pos=find(item_pos,current_set.end(),(*it);prefix_found=(current_set.end()!=item_pos);if(prefix_found)beta_pos=find(current_set.begin(),current_set.end(),beta);prefix_found=(current_set.end()!=beta_pos);returnprefix_found;/根据项集扩展来构造数据库voidproject_database_itemset(constsequence_dat

60、abase&db,constsequence&prefix,constitem&beta,sequence_database&projected_db)projected_db.clear();itemsetlast_set;if(!prefix.empty()last_set=prefix.back();for(sequence_database:const_iteratorrow_it=db.begin();row_it!=db.end();+row_it)(sequencecurrent_row=(*row_it);booldone=false;for(sequence:iteratorseq_it=current_row.begin();!done&&seq_it!=current_row.end();+seq_it)(itemset:iteratorindicator_pos=find(seq_it->begin(),seq_it->end(),SAME_SET);if(seq_it->end()!=indicator_pos)itemset:iteratorbeta_pos=find(seq_it->begin(),seq_it->end(),bet