第28卷 第2期2006年2月武 汉 理 工 大 学 学 报
JOURNALOFWUHANUNIVERSITYOFTECHNOLOGYVol.28 No.2
Feb.2006
4种序列模式挖掘算法的特性研究吕 锋,张炜玮(武汉理工大学信息工程学院,武汉430070)
摘 要: 序列模式挖掘是数据挖掘中的一个重要研究方向,对序列模式挖掘中的4种算法(AprioriAll、GSP、FreeSpan、Prefixspan)的执行过程及其特点进行了研究,并对这几种算法的时空执行效率进行了定性和定量的分析比较,指出了4种算法各自的适用范围,得出的结果对序列模式挖掘系统的设计具有一定的参考价值。关键词: 序列模式挖掘; AprioriAll; GSP; FreeSpan; Prefixspan
中图分类号: TP301.6文献标志码: A文章编号:167124431(2006)0220057204
ResearchontheCharactersofFourSequentialPatternsMiningAlgorithms
LUFeng,ZHANGWei2wei(SchoolofInformationEngineering,WuhanUniversityofTechnology,Wuhan430070,China)
Abstract:
Sequentialpatternsminingwasaveryimportantdata2miningproblemwithboardapplication.Weresearchedfour
sequentialpatternsminingalgorithmsnamelyAprioriAll,GSP,FreeSpan,Prefixspan,andstudiedtheircharacters.Aqualita2tiveanalysishadalsobeenmadeonthealgorithm’stimeandspaceefficiency.Wealsopointedouttheconditionsinwhicheachalgorithmwasapplied.Theconclusionoftheresearchwouldbebeneficialtothedesignofdataminingsystem.Keywords:
sequentialpatternsmining; aprioriAll; GSP; freespan; prefixspan
收稿日期:2005209202.
基金项目:教育部重点实验室开放研究基金(TKLJ0203)1作者简介:吕 锋(19572),男,教授.E2mail:lufengwut@163.com
序列模式挖掘即从序列数据库中发现频繁子序列以作为模式,它是一类重要的数据挖掘问题,有着非常广泛的应用前景,被应用在包括顾客购买行为的分析、网络访问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害的预测、DNA序列的破译等方面。序列模式首先是由AgrawalR和SrikantR提出的[1,2],此后,许多这方面的研究都将注意力放在如何提
高序列模式挖掘的效率上。但是到目前为止,大多数挖掘序列模式的方法都是Apriori类方法的改进。下面就对序列模式挖掘中的4种算法进行分析和比较。
1 序列模式挖掘中的4种算法及其特点1.1 AprioriAll算法AprioriAll[1]算法为Apriori类算法,主要思想为:在每一次扫描(pass)数据库时,利用上一次扫描时产生
的大序列生成候选序列,并在扫描的同时计算它们的支持度(support),满足支持度的候选序列作为下次扫描的大序列。第1次扫描时,长度为1的频繁序列模式作为初始的大1—序列。AprioriAll算法的不足:1)容易生成庞大众多的候选序列;2)需要多次扫描数据库。候选序列的长度增
加1,就需要扫描1次数据库;3)不易发现长序列模式,因为随着需要挖掘的序列模式长度的增加,侯选序列的数量会成指数级增长;4)在发现序列模式的过程中,每次扫描数据库都要在数据转换中产生很大的开销。1.2 GSP算法GSP[2]算法是AprioriAll算法的扩展算法,其算法的执行过程和AprioriAll类似,最大的不同就在于,
GSP引入了时间约束、滑动时间窗和分类层次技术,增加了扫描的约束条件,有效地减少了需要扫描的候选序列的数量,同时还克服了基本序列模型的局限性,更切合实际,减少多余的无用模式的产生。另外GSP利用哈希树来存储候选序列,减小了需要扫描的序列数量,同时对数据序列的表示方法进行转换,这样就可以有效地发现一个侯选项是否是数据序列的子序列。GSP算法也是一个Apriori类算法,它存在的主要问题和AprioriAll算法相似。1.3 FreeSpan算法FreeSpan[3],即频繁模式投影的序列模式挖掘,其基本思想为:利用频繁项递归地将序列数据库投影到更小的投影数据库集中,在每个投影数据库中生成子序列片段。这一过程对数据和待检验的频繁模式集进行了分割,并且将每一次检验限制在与其相符合的更小的投影数据库中[4]。FreeSpan算法执行的过程可以描述为:1)首先给定序列数据库S及最小支持度阈值ζ。扫描S,找到S中的频繁项集,并以降序排列生成flist列表。2)执行下面步骤:(1)第1遍扫描S,构造频繁项矩阵;(2)生成长度为2的序列模式,循环项模式的标记和投影数据库的标记;(3)再次扫描S,生成循环项模式和投影数据;(4)对生成的投影数据库递归调用矩阵投影挖掘算法挖掘更长的候选模式。FreeSpan算法分析:它将频繁序列和频繁模式的挖掘统一起来,把挖掘工作限制在投影数据库中,还能限制序列分片的增长。它能有效地发现完整的序列模式,同时大大减少产生候选序列所需的开销,比基于Apriori的GSP算法快很多。不足之处,它可能会产生许多投影数据库,如果一个模式在数据库中的每个序列中出现,该模式的投影数据库将不会缩减;另外,一个长度为k的序列可能在任何位置增长,那么长度为k+1的候选序列必须对每个可能的组合情况进行考察,这样所需的开销是比较大的。1.4 Prefixspan算法Prefixspan[5]是FreeSpan的改进算法,即通过前缀投影挖掘序列模式。其基本思想为:序列数据库投影
时,并不考虑所有可能出现的频繁子序列,而只检验前缀序列,然后把相应的后缀序列投影成投影数据库。每个投影数据库中,只检查局部频繁模式,在整个过程中不需要生成候选序列。Prefixspan算法的执行过程可以描述为[6]:1)对交易数据库扫描一次得到全部频繁项目n,它们同时也是频繁1—序列。2)将序列模式完整的集合分为n个具有不同前缀的序列模式的子集。3)通过构造相应的投影库并在其中递归地挖掘发现序列模式的子集。PrefixSpan算法分析:1)不需要产生候选序列模式,大大缩减了检索空间;2)与原始的序列数据库相比,投影数据库的规模不断减小;3)算法的主要开销在于投影数据库的构造,如果存在大量的序列模式,并且需要为每一个序列模式建立一个投影数据库,那么开销就比较大。
2 算法的特性分析对Apriori类方法的改进研究,主要集中在如何提高算法的效率上。所有的Apriori类算法无论在处理细节上采用何种改进技术,都不可避免地在候选序列的生成、检验和支持度的计算方面产生开销。另外一种思路就是引入FP2growth的思想,在获得的子序列基础上,将需要挖掘的序列模式进行分类,并且按照这些分类将序列数据库进行投影,这种方法就是模式增量的序列模式挖掘。2.1 4种算法的定性比较归纳起来改进的方法主要体现在候选序列的产生,数据存储的结构,对原始数据的扫描次数等(见表1)。
在挖掘序列模式的过程中,AprioriAll和GSP产生大量的候选序列,FreeSpan和PrefixSpan不产生候选序列。采用合适的数据结构存储频繁序列可以提高算法执行的效率,可以看到前3种算法都采用Hash
tree。AprioriAll和GSP没有对原始数据库进行分割,每次扫描都是在整个原始数据库上进行的,候选序列
85 武 汉 理 工 大 学 学 报 2006年2月的长度每增加1就需要扫描1次数据库,在发现频繁序列的过程中,需要对原始数据库进行反复多次的扫描。FreeSpan和PrefixSpan将原始数据库分割,并将其投影到较小的投影数据库中,对频繁序列的挖掘只局限在投影数据库中,从表1中也可以看到,后二者对原始数据库的扫描次数不超过3次。此外,AprioriAll和GSP用循环的方法挖掘频繁序列,FreeSpan和PrefixSpan用递归的方法进行挖掘。
表1 算法的分类比较属性Apriori类算法AprioriAllGSP模式增量算法FreeSpanPrefixSpan候选序列产生产生不产生不产生数据结构HashtreeHashtreeHashtreeWAPtree
数据库分割否否是是对原始数据库的扫描次数反复多次反复多次3次2次
算法执行循环循环递归递归
2.2 算法的时间和空间执行效率比较AprioriAll算法和GSP算法都属于Apriori类算法,都要产生大量的候选序列,需要有足够的存贮空间。这类算法还需要对原始数据进行反复多次的扫描来计算支持度,需要占用很多的运行时间。当支持度下降的时候,频繁序列的数量成指数上升,这样一来所花费的扫描时间也会成指数级上升,并且候选序列的数量也会随着待挖掘序列的长度呈指数增长关系,算法的执行效率将会大大下降。相对于AprioriAll,GSP由于采用了约束条件,减小了候选序列的数量,其执行效率比前者要高,但同时由于约束条件的使用,相应会使算法复杂一些,也会以相应的开销为代价,但总体来说效率比AprioriAll高2～20倍。FreeSpan算法和PrefixSpan算法属于模式增长方法,它们的查找更加集中和有效。算法不生成大量的候选序列,而是以某种压缩的形式保留了原数据库基本的数据分组。算法每一次迭代不是扫描完整的原数据库来匹配相应的全部候选序列,而是限定在投影数据库中,大大节省了算法执行时间。在所需存贮空间上,FreeSpan在主存中只存储了频繁项矩阵F,然后可以逐个对投影数据库进行计算,这样就比对原始数据库进行计算所需要的存贮空间少得多。基于序列数据库投影的算法比常用的基于Apriori的算法要快且有效得多,特别是在支持度比较低的情况下更是明显。FreeSpan基于任何频繁子序列对序列数据库投影,并在子序列的任何位置上增长;PrefixSpan仅仅基于频繁前缀子序列投影,并通过在其后添加后缀来实现序列的增长,在时间和空间上的执行性能比前者更优。2.3 Apriori类算法和Freespan算法的定量分析Apriori类算法会产生大量的候选序列,而且要反复多次的扫描数据库来计算支持度,这已经成为Apri2ori类算法的瓶颈。一般来说,Apriori类算法发现一个长度为l的序列模式,至少需要扫描数据库l次。例如,如果要发现{(abc)(adc)(edf)(fgd)(cfd)}这一序列模式,需要扫描数据库至少15次。从理论上来讲,