4种序列模式挖掘算法的特性研究

格式：pdf
大小：126.93 KB
文档页数：4

下载文档原格式

基于Markov链的Web访问序列挖掘算法研究及性能分析

ｃｎｉｐｏｅｃａｓｃｌｓｑｅｃｎｎｇｒｔｍｓｔａｕｌｖｕｈｔｅａｄｓａｅｃｍｐｅｉｒｐｒｉｓＰｅｆｒａｃａｒｖｌｓｉａｅｕｎｅｍｉｉｇａｏｉｍｌｈｈｔｕｓａｌｈａｅｍｃｉｐｃｏｙｍｎｌｘｔｐｏｅｔ．ｒｏｍｎｅｙｅｓｗｓｔａｅｐｏｏｅｎｅＣｅｒａｅｔｍｅａｄｓａｅｏｅｈａｌｅｃｉｇｆｒＷｅｃｅｓｎｅｕｎｅｐａｔｒｈｏｔｒｐｓｄｏａｄｃｅｓｈｔｈｎｉｎｐｃｖｒｅｄｗｈｉｓａｈｎｏｂａｃｓｉｇｓｑｅｃｔｎｗｈｅｅｒｅｎ
导致经典算法在效率和及时性上都达不到要求。
目前，对于Ｗｅ访问序列模式挖掘的研究大多集中ｂ
在对挖掘算法本身的改进上。本文提出了一种基于
Ｍａｋｖ和改进Ｐｅｘｐｎ序列模式挖掘算法的新算ｒｏ链ｒｆＳａｉ法。该算法通过Ｍａｋｖ的一步正向、逆向转移概率矩ｒｏ阵来构造序列数据库，并通过隔层投影和伪投影相结合的Ｐｅｘｐ算法对此数据库进行挖掘，从而以较小ｒｆＳａｉｎ的时间和空间复杂度获得较为准确的结果。
ｃｍｐｅｔｌｓｉａｌｏｔｍ．ｏｒａｄｗｉｃａｓｃａｇｒｈｈｌｉ
Ｋｅｙｗｏｒｓ：ｄｔｎｎｄａａｍｉｇ；Ｗｅｃｅｓｎｉｂａｃｓｉｇ；ＭａｋｖＳｃａｎ；ｓｑｅｅｐｔｅｎｒｏ’ ｈｉｅｕｎｃａｔｒ

一种基于MDL的日志序列模式挖掘算法

第47卷第2期Vol.47No.2计算机工程Computer Engineering2021年2月February2021一种基于MDL的日志序列模式挖掘算法杜诗晴1，王鹏2，汪卫2（1.复旦大学软件学院，上海201203；2.复旦大学计算机科学技术学院，上海201203）摘要：日志数据是互联网系统产生的过程性事件记录数据，从日志数据中挖掘出高质量序列模式可帮助工程师高效开展系统运维工作。

针对传统模式挖掘算法结果冗余的问题，提出一种从时序日志序列中挖掘序列模式（DTS）的算法。

DTS采用启发式思路挖掘能充分代表原序列中事件关系和时序规律的模式集合，并将最小描述长度准则应用于模式挖掘，设计一种考虑事件关系和时序关系的编码方案，以解决模式规模爆炸问题。

在真实日志数据集上的实验结果表明，与SQS、CSC与ISM等序列模式挖掘算法相比，该算法能高效挖掘出含义丰富且冗余度低的序列模式。

关键词：数据挖掘；日志分析；事件关系；最小描述长度准则；序列模式开放科学（资源服务）标志码（OSID）：中文引用格式：杜诗晴，王鹏，汪卫.一种基于MDL的日志序列模式挖掘算法［J］.计算机工程，2021，47（2）：118-125.英文引用格式：DU Shiqing，WANG Peng，WANG Wei.A MDL-based pattern mining algorithm for log sequences［J］. Computer Engineering，2021，47（2）：118-125.A MDL-based Pattern Mining Algorithm for Log SequencesDU Shiqing1，WANG Peng2，WANG Wei2（1.Software School，Fudan University，Shanghai201203，China；2.School of Computer Science，Fudan University，Shanghai201203，China）【Abstract】Logs contain rich information about procedural events generated in Internet systems，and the mining of high-quality sequence modes from log data can improve the efficiency of system operation and maintenance.To address the problem of redundant results of traditional pattern mining algorithms，this paper proposes a Discovering sequential patterns from Temporal log Sequences（DTS）algorithm.DTS heuristically discovers the set of patterns that can best represent the event relationships and temporal regularities in the original sequence.At the same time，DTS applies the Minimum Description Length（MDL）principle to pattern mining，and proposes an encoding scheme that considers event relationships as well as temporal relationships to solve pattern explosion.Experimental results on real log datasets show that compared with SQS，CSC，ISM and other sequential pattern mining algorithms，the proposed algorithm is capable of efficiently mining meaningful sequential patterns with low redundancy.【Key words】data mining；log analysis；event relationships；Minimum Description Length（MDL）principle；sequential patterns DOI：10.19678/j.issn.1000-3428.00571810概述日志数据记录了互联网系统运行时的状态以及任务的开始与结束等重要事件，其易于获取且含有丰富的信息，已经成为系统运维领域的重要数据源。

数据挖掘_国防科技大学中国大学mooc课后章节答案期末考试题库2023年

数据挖掘_国防科技大学中国大学mooc课后章节答案期末考试题库2023年1.某超市研究销售纪录数据后发现，买啤酒的人很大概率也会购买尿布，这种属于数据挖掘的哪类问题？()答案:关联规则发现2.下列有关SVM说法不正确的是（）答案:SVM因为使用了核函数，因此它没有过拟合的风险3.影响聚类算法效果的主要原因有：（）答案:特征选取_聚类准则_模式相似性测度4.7、朴素贝叶斯分类器不存在数据平滑问题。

( )答案:错误5.决策树中包含一下哪些结点答案:内部结点（internal node）_叶结点（leaf node）_根结点（root node) 6.标称类型数据的可以利用的数学计算为：众数7.一般，k-NN最近邻方法在( )的情况下效果较好答案:样本较少但典型性好8.考虑两队之间的足球比赛：队0和队1。

假设65%的比赛队0胜出、P(Y=0)=0.65。

剩余的比赛队1胜出、P(Y=1)=0.35。

队0获胜的比赛中只有30%在队1的主场、P(X=1|Y=0)=0.3，而队1获胜的比赛中75%是主场获胜、P(X=1|Y=1)=0.75。

则队1在主场获胜的概率即P(Y=1|X=1)为：（）答案:0.579.一组数据的最小值为12,000，最大值为98,000，利用最小最大规范化将数据规范到[0,1]，则73,000规范化的值为：（）答案:0.71610.以下哪个分类方法可以较好地避免样本的不平衡问题：（）答案:KNN11.简单地将数据对象集划分成不重叠的子集，使得每个数据对象恰在一个子集中，下列哪些不属于这种聚类类型层次聚类_模糊聚类_非互斥聚类12.数据点密度分布不均会影响K-means聚类的效果。

答案:正确13.数据集成需要解决模式集成、实体识别、数据冲突检测等问题答案:正确14.决策树模型中应处理连续型属性数据的方法之一为：根据信息增益选择阈值进行离散化。

答案:正确15.数据库中某属性缺失值比较多时，数据清理可以采用忽略元组的方法。

在频繁序列模式中挖掘并发序列模式

（）２
设ＳＢ＝｛。，， …，是一个序列数ＤＳ，Ｓ，Ｓ｝
据库，与为在某一最小支持度ｍｉｓｐ下序ｎｕ列模式挖掘结果，ｏ与Ｊ且ｌＢ互不包含．定义１若（）＾（）则在序列Ｓａ１３，
对挖掘结果进行大幅精简，使得挖掘更有实际意义．
关键词：并发关系；并发度；并发序列模式；并发序列模式挖掘
中图分类号：１１；Ｔ３１］８ＰＰ１文献标识码：Ａ
翌翌雯
序列模式挖掘是数据挖掘的一个重要研究
内容，能够发现隐藏在大规模数据中的具有顺序关系的模式．结构关系模式挖掘是一种建立在序
列模式挖掘基础上的新的挖掘任务，旨在寻找隐藏在序列模式后面的新的结构关系模式．结构关
系模式￣和序列模式一样在实际应用中也有２
序挖掘和结构关系模式挖掘更为相似，构关系结可以看作是偏序关系的限定和扩展．结构关系中的并发关系、互斥关系和顺序关系可以看作是偏序关系的限定，们简化了挖掘过程和挖掘结他果．而结构关系中的重复关系、联关系则不属关于偏序关系，这使得结构关系模式挖掘在实际应用中更有价值．经过几年的研究，本课题组建立了相对完整
重要的研究价值．构关系模式和序列模式之间结
的关系如图１所示．

一种面向金融时间序列的趋势特征挖掘算法研究

一谭华嘉兴学院经济学院
算法如下：
给定时间序列０（）＂，则平滑过程为式（：１】
Ⅳ一１
由于股票时间序列含有很多噪声，两个极值点之间往往离的很
浙江省教育厅项目（２００５Ｙ０８５１）７
［摘要］时序数据相似性挖掘是数据挖掘中的重要研究内容。本文根据金融事件序列自身特点，将股票中的时间序列转换为以价格变动率为变量的时间序列，对趋势特征提取、聚类算法进行
其中％是原始数据，０是清洗后的数据，ｃＯ是含Ｎ（）（，（维系数的向量，Ｎ根据具体数据来定，ｃ是设计ＦＲ（）Ｉ的重点。由脉宽和精度来确定，可用Ｍａｌ信号处理工具箱中有关函数得到。ｔｂａ１．趋势特征抽取算法时问模式挖掘是在空间中寻找能表征和预测事件的区域，如果预测点之前的时间模式包含在这些区域当中，则预测该事件点的发生提供了一种决策方法。时间序列数据的特征提取是模式发现的前提条件。分段线性法是目前应用最为广泛的时间序列特征提取方法之一。该方法具有较高的滤除噪声和数据抽象能力，可以根据需要获得时间序列数据不同精度的抽象表示。由于以近似误差为目标
财经论坛
一
种面向金融时间序列的趋势近，有时只有２时间单位，因此在进行特征提取前必须进行平滑个处理，去除噪声，然后寻找转折点来对时间序列分段线性化。平滑特征挖掘算法研究处理技术很多，本文采用采用最简单的有限脉；响应法（Ｉ）中ＦＲ，具体

基因序列相似度 r语言

基因序列相似度 r语言基因序列相似度是比较两个基因序列之间的相似性的指标。

基因序列可以通过比较其碱基组成和序列排列的相似度来确定它们的相似程度。

在研究基因组学、进化生物学、系统生物学等领域，基因序列相似度是一个重要的指标，可以用来解决诸如亲缘关系研究、物种分型、标记辅助选择等问题。

在R语言中，有很多方法可以计算基因序列的相似度，下面将介绍几种常用的方法。

1. 碱基组成分析方法碱基组成分析方法是通过比较两个基因序列中各个碱基的比例来计算相似度。

常见的方法包括计算相同碱基的数量、计算核苷酸比例或频率、计算G+C含量等。

这些方法都可以通过R语言中的字符串处理函数和统计函数来实现。

2. 序列比对方法序列比对是通过比较两个基因序列的对应位置上的碱基是否相同来计算相似度。

常见的序列比对算法包括全局比对算法和局部比对算法。

全局比对算法可以比较整个序列的相似性，常用的方法有Needleman-Wunsch算法和Smith-Waterman算法。

局部比对算法可以比较序列中的相似片段，常用的方法有BLAST算法和FASTA算法。

在R语言中，可以使用biopython包和Bioconductor包中的函数来实现序列比对计算。

3. 序列相似性矩阵方法序列相似性矩阵是用来表示两个序列之间的相似度的矩阵。

在矩阵中，矩阵的每一个元素表示两个碱基之间的相似度。

可以通过比较两个序列中的每对碱基来计算相似度矩阵。

常见的相似性矩阵包括PAM矩阵和BLOSUM矩阵。

在R语言中，可以使用Bioconductor包中的函数来计算序列相似性矩阵。

4. 序列挖掘方法序列挖掘方法是一种通过比较两个序列中的模式来计算相似度的方法。

可以通过比较序列中的重复片段或者特定的结构域来计算相似度。

常见的序列挖掘方法有RepeatsMasker和RepeatFinder等。

在R语言中，可以使用Bioconductor包中的函数来实现序列挖掘计算。

综上所述，基因序列的相似度可以通过多种不同的方法来计算，每种方法都有其适用的场景和算法。

基于分布式概念格的序列模式挖掘

进行序列模式的挖掘，并后得到整个数据库的序列模式．合关键词：布式；念格；列模式分概序
中图分类号：Ｐ０．Ｔ３１６
文献标识码：Ａ

文章编号：６３—１２２０）４— ０５— ６１７６Ｘ（０７００３０
定义３序列模式发现）模式给定交易数据Ｄ（Ｂ和用户指定的最小支持度ｓ序列模式发现就是找出，
ＤＢ中所有满足Ｓ的子序列，每一个这样的子序列代表了一个频繁序列模式（ｅｕｎｉｌａｅｎ．ａｓｑｅｔｔｒ）ａｐｔ
不断推广和深入，如何有效地处理分布式环境下的序列模式发现问题，为当前研究中亟待解决的问题．成文献［］出了基于树投影技术的两种不同的并行算法，决分布内存并行计算机的序列模式发现问题．４提解文献［］出了共享内存计算机上的序列模式发现问题的处理办法．翔等提出分布式环境下序列模５提邹式挖掘算法ＦＭＳＦｓＤｓｂｔｎｎｆＳｑｅｔｌａｅｎ）算法采用前缀投影技术生成全局序列ＤＰ（ａｔｉｒｕｅＭｉｉｏｅｕｎｉｔｒｓ，ｔｉｄｇａＰｔ模式．文提出算法ＤＭＳ（ｉｒｕｅ１ａｅｎｎｅｕｎｉｌａｅｎ）目的是解决以子全概念格作本ＣＰＤｓｂｔｄＣ．ｓｄＭｉｉｇＳｑｅｔｔｒｓ，ｔｉｂａＰｔ

基于改进的AprioriAll算法的Web序列模式挖掘研究

（华大学计算机与信息管理中心，北京１０８）清００４
摘要：了减少ＡｐｏＡｌ为ｉｉｆｆｌ算法挖掘过程中候选序列的生成以及对序列数据库的扫描次数，高算法的挖掘效率，出了提提
一
种基于改进的Ａｐｉｒｌ算法的ｗｅ序列模式挖掘方法。首先对数据进行预处理，然后利用经过改进的Ａｐｉｉｌ算法进ｒｉｌｏＡｂｒｒｌｏＡ
计算机工程与设计ＣｍｕｒｎｉｅｎｄｅｇｏｐｔＥｇｅｉａＤｓｎｅｎｒｇｎｉ
・信息化技术・
２１，５００１（９１３）２

基于改进的Ａｒｒｌ算法的Ｗｅ序列模式挖掘研究ｐｉｉｌｏＡｂ
吴海燕，朱靖君，高国柱，程志锐
（ｏｕｒｎｆｒｔｎＭａａｅｎｅｔ，Ｔｉｇｕｉｅｉ，Ｂｅｉｇ１０８，ＣｉａＣｍｐｔｄｎｏｍａｏｎｇｍｅｔｎｅｅａＩｉＣｒｓｈａｖｒｔｎＵｎｓｙｉｎ００４ｈ）ｊｎ
ＡｂｔａｔＴｄｃｅｇｎｒｔｎｏｃｎｉａｅｓｑｅｃｓｎｅｓａｓｔｅｕｎｅｄｔｂｓｏｒｒｌｌｏｉｍ，ａｆｃｅｔｅｓｒｃ：ｏｒｕｅｈｅｅａｉｆａｄｄｔｅｕｎｅｄｔｃｎｓｑｅｃａａａｅｒｅｔｏａｈｏｆＡｐｉｉｇｒｈｏＡｌａｔｎｅｉｎ－ｉｓｑｅｔｌａｔｒｎｎｔｏａｅｎｉｒｖｄＡｐｉｒｌｌｏｔｍｒｓｎｅ．Ｆｒｔ，ｄｔｅｐｅｒｃｓｅ．ＴｅｅｅｕｎｉｌｕｎｉｔｎｍｉｉｇｍｅｈｄｂｓｄｏａｐｅｍｐｏｅｒｉｇｒｈｉｐｅｅｔｄｏＡｌａｉｓｉｓｌｙａａｒｒｐｏｅｓｄａｈｎｔｑｅｔｈｓａｐｔｒｎｎｓｎｓｅｙｉｒｖｄＡｐｉｒＡｌａｇｒｈ．ＴｈａｅｎｍｉｉｇｉｉｈｄｂｉｆｍｐｏｅｒｏｉｌｌｏｉｍｔｅｉｒｖｍｅｔｆｒｏｉｌｌｏｔｍｒｉｌｏｎｓｏｅｉｍｐｏｅｎｓｏｉｒＡｐＡｌａｇｒｈａｅｍａｎｙｔｐｉｔ：ｎｉｗｏｓｔｈｎｅｈｏｎｃｉｎｏｃｎｉａｅｓｑｅｃｓｏｒｄｃｅｇｎｒｔｎｏｃｎｉａｅｓｑｅｃｓｔｅｏｈｒｓｏｒｄｃｅｎｅｌｓａ — ｏｃａｇｅｃｎｅｔｆａｄｄｔｅｕｎｅｕｅｔｅｅａｉｆａｄｄｔｕｎｅ；ｈｔｅｅｕｅｈｅｄｅｓｄｔｔｏｔｅｈｏｅｉｔｔａｂｓｃｎａｅｓａｓｔｉｒｖｅｅｃｅｃｆｌｏｉｍ．Ｆｎｌ，ｔｅｅｃｅｃｎａｉｉｆｍｐｏｅｒｏｉｌｌｏｔｍａｉａｅｙｏｍｐｏｅｔｆｉｎｙｏｇｒｔｈｉａｈｉａｌｙｈｆｉｎｙａｄｖｌｔｏｒｖｄＡｐｉｒｉｄｙｉＡｌａｇｒｈｉｖｌｔｄｂｉｓｄｅｐｒｎｓｘｅｍｅｔ．ｉＫｅｒｓＡｐｉｒｌａｇｒｔｍ；ｓｑｅｔｌａｅｎｗｅｇｍｉｉｇｔａｓｃｉｎｍａｉｌｏｗａｄｐｔｙｗｏｄ：ｒｉｌｌｏｈｏＡｉｅｕｎｉ￣ｒ；ａｐｂｌｎｎ；ｒｎａｔ；ｏｏｘｍａｒｒａｈｆ

SPADE算法介绍

水平垂直数据库区别在于数据库中存储数据的结构不一样，因此扫描数据库的效率不一样。
A
算法 lgorithm
主要特色
水平数据格式序列 <1,(1,2,3),(1,3),4,(3,6)> <(1,4),3,(2,3),(1,5)> <(5,6),(1,2),(4,6),3,2> <5,7,(1,6),3,2,3>
挖掘模式
Apriori系列算法 SPADE GSP
挖掘模式
分类模式关联模式
算法
关联模式
聚类模式
序列模式
序列模式挖掘是挖掘频繁出现的有序事件或子序列
B
背景 ackground
序列模式
首先找出所有的频繁集，这些项集出现的频繁性至少和预定义的最
小支持度一样；然后由频集产生强关联规则，这些规则必须满足最小支持度和最小置信度。支持度=序列出现次数/总序列数置信度=序列出现次数/特定子序列出现次数
序列ID（SID） 1 2 3 4
水平数据存储格式：GSP
1序列的ID_list 1 SID 1 EID 1 SID 1 2 EID 2 … … SPADE：垂直数据格式 SID 1 1 1 1 1 2 2 2 EID 1 2 3 4 5 1 2 3 4 项 1 1，2，3 1，3 4 3，6 1，4 3 2，3 1，5
background背景挖掘模式spadegsp分类模式序列模式关联模式apriori系列算法聚类模式关联模式挖掘模式算法序列模式挖掘是挖掘频繁出现的有序事件或子序列background背景序列模式首先找出所有的频繁集这些项集出现的频繁性至少和预定义的最小支持度一样
姓名：专业：

基于概念的序列模式挖掘研究

维普资讯
计算机应用
ＣｏｐｔｒＡｐｐｉａｔｎｓｍｕｅｌｉｃｏ
《自动化技术与应用》２００７年第２第７期６卷
基于概念的序列模式挖掘研究
王宇・周丽娟２段录平，一，
不同，它只需访问数据库一次。
本文内容组织如下：第—部分描述了一些基本概念；第二部分
集中在如何提高序列模式挖掘的效率上。经典的序列模式挖掘算
２ｅａｔｅｔｆｎｏｔｎｄｎｉｅｉ，ａｉ，ｏｍｌｎｅｉ，ｅｉ００７Ｃｉ）．ｐｒｎｏＩｆｍａｏａＥｇｅｒｇＣｐａＮｒａＵｖｒｔＢｉｇ１０３，ｈａＤｍｒｉｎｎｎｔｉｓｙｊｎｎ
ＡｂｔａｔＴｉｐｐｒｎｒｄｃｓｅｕｎｉｌａｔｎａｇｒｈｎｍｅＰＳｑｅｔｌａｔｒｇｒｈＢａｅｎＣｏｃｐ）ｗｈｃｓｒｃ：ｈｓａｅｔｕｅｓｑｅｔｔｒｌｏｉｍａｄＳＣ（ｅｕｎｉｔｎＡｌｏｉｍｓｄｏｎｅｔｉｏａａｐｅｔａＰｅｔ，ｉｈ
１引言
序列模式挖掘即从序列数据库中发现频繁子序列作为模式。它是一类重要的数据挖掘问题，有着非常广泛的应用前景，被应
越来越突出，主要原因是它们都需要多次访问数据库。
为了解决这一突出问，题本文提出了一种基于概念的序列模
式算法ｓＣＡｇｔｍｆｅｕｎｉａｔｎＢｓｄｏｏｃｐ）Ｐ（】ｈｏｑｅｔｌｔｒａｅｎＣｎｅｔ，ＳａＰｅ

一种快速最大频繁序列模式挖掘算法

Ａｓｒｃ：ｈｓｐｐｒｐｏｏｅｏｅａｏｔｍＭＦＰＮ（ｘｌｆｑｅｔｓｑｅｔａｅｎｎｂｔｔＴｉａｅｒｐｓｓａｎｖｌｌｒｈＳＡａｇｉｍａｉｒｕｎｅｕｎａｐｔｒｍｉｇｍａｅｉｌｔｎｉｌｒｈ．ＭＦＰＮｉｕｅｎｅｃｍｐｔｓｔｏａｉａ￣ｑｅｔｑｅｔａｅｓｉｅｕｎｅａｏｉｍ）ｇｔＳＡｓｓｄｔｍｉｅｔｏｌｅｅｆｍｍｏｈｅｘｌｅｕｎｕｎｉｐｔｒｓｑｅｃｅｓｌａｔｎｎ
包含关系）Ｊ但对一些密集的数据库，．闭项集仍相当庞大．而最大频繁序列集合要比所有的频繁序
列集合小很多，比闭项集小很多．给出一个最大频繁序列集合，可以很容易地分析出数据库中的很也
多有用信息（例如，哪些是最长的频繁序列及最大频繁序列之间重叠的部分等）而且不易被太多重复，的冗余信息所困扰．并且所有的频繁序列都可以从最大频繁序列集合中推导出，若对某个频繁序列感
２ＯＯ６年７月
Ｊｌ２０ｕｙ０６
一
种快速最大频繁序列模式挖掘算法
常晓宇，王，秀娟，春一，春光徐路周
（吉林大学计算机科学与技术学院，长春１０１）３０２
摘要：针对序列模式挖掘中，频繁子序列个数随模式长度增加而爆炸性增长的问题，提出一种从序列数据库中挖掘最大频繁序列模式的新算法（ＳＡ．ＭＦＰＮ充分利用不同序列ＭＦＰＮ）ＳＡ可能具有相同前缀的性质来减少项集比较次数．在标准测试数据集上的实验结果表明了

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第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次。从理论上来讲,