（计算机软件与理论专业论文）序列模式挖掘维护算法的研究.pdf

摘要 摘要 现有的序列模式挖掘算法能有效地在大型数据库中挖掘出完整的序列 模式集。然而在这些算法中仍存在两个值得注意的问题，一是大多数增量 挖掘算法一般只考虑向数据库中增加事务和数据序列的情况，很少考虑删 除这些数据的情况；二是目前序列模式的增量式挖掘算法主要集中在数据 库更新基础上的序列模式维护技术的研究，很少有算法考虑到当算法参数 发生变化时，如何根据前次挖掘结果尽快挖掘新条件下的序列模式集。这 两类问题的研究在电子商务、顾客购物模式以及w e b 访问挖掘等领域中具 有重要的意义。 针对以上两个问题，本文首先提出了当从序列数据库中删除某些数据 时序列模式的增量式更新算法。该算法以a p r i o r i 的候选产生和测试策略为 基础，将前次挖掘得到的频繁序列集保存起来，同时采用一种新的候选序 列集生成方法，仅生成新出现的候选模式，缩小了模式的搜索空间，在一 定程度上减小了候选集的规模，降低了模式挖掘的时间。在从序列数据库 中删除数据的情况下进行序列模式的增量式挖掘时，该算法的性能明显优 于g s p 。 其次，提出了当算法参数发生变化时序列模式的增量式更新算法。该 算法基于候选库c b 的结构，将前次挖掘得到的候选序列模式及其支持度 的信息都保存在候选库中，以便下次挖掘时使用。当指定的最小支持度小 于前次挖掘时的最小支持度时，挖掘过程中应及时对候选库进行更新。该 算法减小了候选集的规模，缩小了模式搜索空间，降低了模式挖掘的时间。 在最小支持度阂值逐渐变小时，该算法的性能明显优于g s p 。 实验结果表明，本文提出的两种算法在挖掘时间上以及生成的候选集 的规模上都明显优于现有的同类算法，实现了预期的研究目标。 关键词数据挖掘；序列模式挖掘；增量式更新；候选库；最小支持度 燕山大学工学硕士学位论文 a b s t r a c t t h ee x i s t i n g a l g o r i t h m sf o rs e q u e n t i a lp a t t e r n sm i n i n gc a ne f f i c i e n t l y d i s c o v e rt h ec o m p l e t es e to fs e q u e n t i a lp a t t e r n si nl a r g ed a t a b a s e h o w e v e r , t h e s ea l g o r i t h m sm a yb ei n e f f i c i e n ti nd e a l i n gw i t ht h ef o l l o w i n gt w op r o b l e m s f i r s t l y , m a n yl a r g ed a t a b a s e sn o to n l ya d dt r a n s a c t i o n sa n dd a t as e q u e n c e s ，b u t a l s od e l e t et h e s ed a t af r o mt i m et ot i m e ，w h i l em o s to ft h ei n c r e m e n t a lm i n i n g a l g o r i t h m sd o n tc o n s i d e rt h ed e l e t i o no fd a t a ；s e c o n d l y ，s of a r , t h er e s e a r c h e s o ni n c r e m e n t a lm i n i n go fs e q u e n t i a lp a t t e r n sm o s t l yf o c u so nt h eu p d a t eo f d a t a b a s e ，b u tp a yl i t t l ea t t e n t i o nt ot h ec h a n g e so fp a r a m e t e r , w h i c hm e a n st h e m i n i m u ms u p p o r tm a yb eo f t e nc h a n g e db yu s e et h er e s e a r c h e so nt h et w o p r o b l e m s c a nb e a p p l i e di nm a n yf i e l d s ，s u c h a se l e c t r o n i cc o m m e r c e ， c u s t o m e rp u r c h a s ep a t t e r n s ，w e bu s a g em i n i n g ，a n ds oo n a c c o r d i n gt oa b o v et w oq u e s t i o n s ，a ne f f i c i e n ta l g o r i t h mi sp r o p o s e dt o s o l v et h ep r o b l e mo fi n c r e m e n t a lu p d a t i n go fs e q u e n t i a lp a r e m sw h e ns o m e d a t aa r ed e l e t e df r o ma no r i g i n a ld a t a b a s e t h ea l g o r i t h m ，b a s e do na p r i o r i c a n d i d a t eg e n e r a t i o na n dt e s tp h i l o s o p h y , u t i l i z e st h ei n f o r m a t i o no b t a i n e d d u r i n gp r i o rm i n i n gp r o c e s s e sa n ds t o r e st h es e to fd i s c o v e r e df r e q u e n t s e q u e n c e si n ad a t a b a s ef o rf u r t h e rm i n i n g i t a d o p t s an e wc a n d i d a t e g e n e r a t i o nt e c h n i q u e ，w h i c hc u t sd o w nt h es i z eo fc a n d i d a t es e t si ns o m e e x t e n ta n dr e d u c e st h em i n i n gt i m e t h ea l g o r i t h mo u t p e r f o r m st h eg s p a l g o r i t h mf o ri n c r e m e n t a lm i n i n go fs e q u e n t i a lp a r e m sw h e ns o m ed a t aa r e d e l e t e df r o ma no r i g i n a ld a t a b a s e s e c o n d ，a na l g o r i t h mf o ri n c r e m e n t a lu p d a t i n go fs e q u e n t i a lp a t t e r n si s p r o p o s e dw h e nt h ea l g o r i t h m i cp a r a m e t e r ( m i n i m u ms u p p o r tt h r e s h o l d ) i s c h a n g e db yu s e lt h ea l g o r i t h m ，b a s e do nt h es t r u c t u r eo fc a n d i d a t eb a s e ( c b ) ， s t o r e st h es e q u e n t i a lp a t t e r n sa n dt h e i rs u p p o r td i s c o v e r e dd u r i n gp r i o rm i n i n g p r o c e s s e si nc bf o rf u r t h e rq u e r i e s w h e nt h es u b s e q u e n tm i n i m u ms u p p o r t n a b s a a c t t h r e s h o l ds p e c i f i e db yu s e rb e c o m e ss m a l l e r , c bs h o u l db eu p d a t e di nt i m e d u r i n gs u b s e q u e n tm i n i n gp r o c e s s e s t h ea l g o r i t h mr e d u c e st h es i z eo fs e to f c a n d i d a t es e q u e n c e s ，d e c r e a s e st h em i n i n gt i m ea n di m p r o v e st h e m i n i n g e f f i c i e n c y w h e nt h em i n i m u ms u p p o r tt h r e s h o l dg e t sg r a d u a l l ys m a l l e r , t h e a l g o r i t h mo u t p e r f o r m st h eg s pa l g o r i t h ms i g n i f i c a n t l y e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h m sp r o p o s e di nt h i sp a p e ra r e m o r ee f f i c i e n tt h a nt h ec u r r e n to n e s ，a n dt h ea n t i c i p a t e dr e s u l t sa r er e a l i z e d k e y w o r d sd a t am i n i n g ；s e q u e n t i a lp a t t e r nm i n i n g ；i n c r e m e n t a l u p d a t i n g ； c a n d i d a t eb a s e ；m i n i m u ms u p p o r t m 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文序列模式挖掘维护算法 的研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研 究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已 发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体， 均己在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字：圉l 唬磊 日期：夕噼，月2 - e t 燕山大学硕士学位论文使用授权书 序列模式挖掘维护算法的研究系本人在燕山大学攻读硕士学位期 间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有， 本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解 燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送 交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学， 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部 分内容。 本学位论文属于 保密口，在 年解密后适用本授权书。 不保密d 。 日期：障f 猬日 日期：吧厂琦声月多侣 吖磊互 篙瓣 卧 名 名 椰 獬 摊 第l 章绪论 第1 章绪论 近年来，随着信息技术的发展，许多领域积累了大量的数据。这些数 据繁杂无序，但又蕴藏了许多具有重大应用价值的知识和信息。因此，人 们迫切需要开发出有效的技术和工具，以支持从海量数据中自动地抽取出 有价值的知识和信息。数据挖掘就是为了满足这一需求产生并发展起来的， 特别是其中的序列模式挖掘，由于其具有广泛的应用，已经成为数据挖掘 中的研究热点之一。 1 1 数据挖掘技术 数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识【l 】。这些 知识是隐含的、事先未知的潜在有用信息，提取的知识表示为概念、规则、 规律、模式等形式。 1 1 1 数据挖掘产生的背景 近十几年来，人们利用信息技术生产和搜集数据的能力大幅度提高， 特别是i n t e m e t 的发展，更使得数据和信息以爆炸性的速度增长。隐含在 数据内部的信息在决策生成的过程中具有重要的参考价值。尽管目前的数 据库系统可以高效地实现数据的录入、查询、统计等功能，但由于数据量 庞大以及数据库系统中分析方法的严重缺乏，使得它无法发现数据中隐藏 的相互联系和规则，更无法根据当前的数据去预测未来的发展趋势。这种 “数据爆炸但知识贫乏”的现象1 2 】迫切需要系统地开发强有力的智能数据 分析工具，以从这些海量的数据中自动、高效地提取所需的有用知识。 建立在数据库系统之上的计算机决策支持系统的出现，为进行高层次 的数据决策分析提供了很好的思路和方法。但由于决策支持系统在数据的 采集、分析方法上的灵活性等方面存在局限性，使得人们不得不寻求更有 效的途径去开拓数据决策分析的思路。人工智能为此做出了巨大贡献，人 工智能经历了博弈、自然语言理解和知识工程等阶段，已经进入了机器学 燕山大学工学硕士学位论文 习的热点阶段 3 l 。机器学习能够使用计算机模拟人类的学习方式，通过对 数据对象之间关系的分析，提取出隐含在数据中的模式。 正是由于实际工作的需要和相关技术的发展，利用数据库技术来存储 管理数据，利用机器学习的方法来分析数据，从而挖掘出大量的隐藏在数 据背后的知识，这两种思想的结合促成了数据挖掘的产生【4 1 。 实际上，数据挖掘是一门交叉性学科，涉及到机器学习、模式识别、 统计学、智能数据库、知识获取、数据可视化、高性能计算、专家系统等 多个领域f 5 7 】。数据挖掘发现的知识可以用在信息管理、过程控制、科学研 究、决策支持等许多方面。 1 1 2 数据挖掘的任务 数据挖掘的任务就是从数据集中发现模式。模式可以有很多种，按功 能可以分为两大类：描述型( d e s c r i p t i v e ) 模式和预测型( p r e d i c t i v e ) 模式【8 1 。 在实际应用中，挖掘任务又可分为以下几种：分类知识发现、数据聚类、 关联规则发现、序列模式发现、异常发现等。 分类知识发现是数据挖掘中最常见的，其旨在根据样本数据寻求相应 的分类规则，然后根据该规则来确定某一非样本个体或对象是否属于某一 特定的组或类。在这种分类知识发现中，样本个体或对象的类标记是已知 的。数据挖掘的任务在于从样本数据的属性中发现个体或对象分类的一般 规则，从而根据该规则对非样本数据对象进行分类。 数据聚类是用于发现在数据库中未知的数据类。这种数据类划分的依 据是“物以类聚”，即考察个体或数据对象间的相似性，满足相似性条件的 个体或数据对象划分在一组内，不满足相似性条件的个体或数据对象划分 在不同的组。由于在数据挖掘之前，数据类划分的数量与类型均是未知的， 因此在数据挖掘后需要对数据挖掘的结果进行合理的分析与解释。 关联规则发现是在数据库中寻找数据对象间的关联模式，例如“在购 买面包和黄油的顾客中，9 0 的人同时也购买了牛奶。”就是一种关联模式。 关联模式发现早期主要用于零售业交易数据分析，以进行物品更合理的摆 放，最终提高销售量。因此，该方法有时也直接称为“货篮分析”。 2 第1 章绪论 序列模式发现是在数据库中寻找基于一段时间区间的关联模式，例如 “在某一时间购买个人电脑的所有顾客中，6 0 会在3 个月内购买应用软 件。”就是一序列模式。序列模式同关联模式非常相似，区别在于序列模式 表述的是基于时间的关系，而不是关于数据对象间的关系。 异常发现用于在数据库中发现数据中存在的偏差或异常，它们与数据 的一般行为或模型不一致。例如下列几种偏差或异常就应引起人们的关注： 不适用于任何一标准类的异常，有时可能意味着严重的错误或欺诈；相邻 时间段内信息的异常变动。 其中，序列模式挖掘由于在实际中具有广泛的应用，已经成为数据挖 掘中的研究热点之一。 1 2 序列模式挖掘技术 序列模式挖掘即从序列数据库中发现频繁子序列以作为模式，它是指 挖掘基于时间或者其它顺序出现频率高的模式，是一类非常重要的数据挖 掘问题。 1 2 1 应用领域 在实际应用中，多数数据集中的数据都带有时间特征，这类数据称为 时态数据( t e m p o r a ld a t a ) t 9 1 ，例如某顾客在超市内某时间段内购买商品的序 列、天气数据和生产数据等。序列模式挖掘的目标是在带有时间特征的数 据库中挖掘频繁发生的序列，从而实现对未来行为的预测。 序列模式挖掘最初是由于在零售业中的应用而发展起来的。现在，序 列模式已经应用到了科研和商用的其他许多领域。例如，在医疗领域，一 个病人每看一次病，他的症状就可以组成一次事务，而这个病人的所有看 病记录( a p 所有事务) 就可以形成一个“症状序列”，从所有病人的症状序列 中挖掘出一个模式，这个模式将会帮助医生诊断这些症状预示着何种疾病。 序列模式挖掘是数据挖掘中一个重要的、富有挑战性的研究课题，在 实际中具有广泛的应用，包括顾客购物模式分析和互连网访问模式分析， 以及序列分析或者其它与时间相关的处理过程分析，例如科学实验、自然 燕山大学工学硕士学位论文 灾难事件、疾病防治、d n a 序列、股票序列的分析等1 1 0 1 。 1 2 2 国内外研究现状 序列模式挖掘的概念首先是由r a g r a w a l 等人在1 9 9 5 年针对超市购物 篮数据的分析提出的1 1 1 】，此后人们不断地研究和改进在时间序列数据库中 挖掘序列模式和其他频繁模式的算法。现有的序列模式挖掘算法主要分为 两类：第一类是基于r a g r a w a l 和r s r i k a n t 在1 9 9 4 年提出的a p r i o r i 特性 【1 2 】的算法。a p r i o r i 特性首先应用在关联规则挖掘中，其基本思想是频繁模 式的子序列也一定是频繁模式。基于a 面o r i 特性，人们提出了一系列类 a p r i o r i 的序列模式挖掘算法，这些算法中有采用水平数据格式( h o r i z o n t a l d a t af o r m a t ) 的算法，如a p r i o r i a l l 算法 1 1 】、g s p 算法i 1 3 】、p s p 算法等； 有采用垂直数据格式( v e r t i c a ld a t af o r m a t ) 的算法，如s p a d e 算法1 15 、 s p a m 算法【l 6 j 等。第二类是j h a n 等人提出的基于模式增长伊a r e n a g r o w t h ) 策略的算法，如f r e e s p a n 算法【1 7 】、p r e f i x s p a n 算法【18 】等。 另外，c a n t u n e s 等人提出了s p a r s e 算法f l9 】，该算法的主要思想是 将候选序列的产生和在投影数据库空间搜索结合起来，每一步在产生出频 繁元素后，通过增长长度寻找模式。该算法应用在密集型数据库中能获得 较好的性能。 以上这些算法都是在静态的序列数据库中挖掘所有的序列模式，它们 都属于一般的序列模式挖掘算法。但是，由于一般的大型数据库都是随着 时间的变化而不断更新的，当数据库发生变化之后，原先挖掘的一部分序 列模式可能不再满足最小支持度，同时还可能有新的序列模式出现，如果 使用上述算法，就必须在更新后的序列数据库中重新进行挖掘。在处理具 有海量数据的大型数据库时，对整个数据库熏新执行一般的序列模式挖掘 算法显然是低效的。在这种情况下，一系列增量式序列模式挖掘算法被提 出，其基本思想都是尽可能地利用已发现序列模式的信息来发现新数据库 中的序列模式，从而提高模式挖掘的效率。 m a s s e g l i a 等人提出了用于序列模式增量式更新的算法i s e l 2 ，该算法 利用已有对原始数据库的挖掘结果来产生候选项目集，减少了候选项目集 第1 章绪论 的规模。但没有降低对整个数据库的扫描次数，算法的i o 消耗仍然很大。 周斌等人提出了在数据库更新的情况下的序列模式增量式挖掘算法 i m s p l 2 1 1 ，其主要思想是利用序列的c t i d 表来加速挖掘过程。但该方法要 求预知前次挖掘的每个序列模式的c t i d 表，且在计算过程中将产生关于 每个候选序列的c t i d 表。当数据库规模很大时，对存储空间的消耗很大。 邹翔提出了一种称为f i m s 的序列模式增量式更新算法【2 2 j ，处理因数 据库更新而引起的序列模式维护问题。该算法的主要思想是利用原先的序 列模式挖掘结果，通过建立一个投影数据库来减少对整个数据库的扫描次 数和候选序列的生成。 h c h e n g 等人提出了当向数据库中添加新的事务和数据序列时序列模 式的增量式更新算法i n c s p a i l 【2 鄂， 该算法采用缓冲率、频繁序列集及缓冲 半频繁序列集的技术，提高了序列模式增量挖掘的效率。 基于s p a d e 方法，一些学者提出用于数据库更新的序列模式的增量 式更新算法i s m ( 2 4 1 。该算法将所有频繁序列及其负边界组成一个序列网 格，当增量数据到达时，对增量部分进行扫描同时更新序列网格。然后， 根据序列网格和增量数据决定原始数据库中应当扫描的部分。 此外，当前国内外学者广泛关注的研究方向还包括： ( 1 ) 约束( c o n s t r a i n e d ) 序列模式挖掘在很多序列模式挖掘任务中，用 户不需要找出数据库中所有可能存在的序列模式，而是加入一定的约束， 找出用户感兴趣的序列模式 2 5 , 2 6 。如a g r a w a l 等人将序列模式挖掘问题加 以泛化，引入了时间约束、滑动时间窗口( s l i d i n gt i m ew i n d o w ) 和分类约 束，并提出了g s p 算法。 ( 2 ) 闭合( c l o s e d ) 序列模式挖掘当序列模式很长时，由于每一个序列模 式包含了组合数级的频繁子序列，挖掘所需的开销很大，然而在实际应用 经常需要挖掘特别长的模式，女i d n a 序列。闭合序列模式挖掘 2 7 - 2 9 1 研究如 何挖掘满足以下条件的序列模式：不存在与其具有相同支持度的超序列。 ( 3 ) 周期性( p e r i o d i c ) 模式挖掘 周期性模式挖掘1 3 2 j 的目标是在时间 序列数据库中挖掘重复发生的模式，其中挖掘局部频繁发生模式具有较高 的应用价值，例如自然灾难分析、天气预报分析等。 燕山大学工学硕士学位论文 h ) 结构( s t r u c t u r e ) 模式挖掘 结构模式挖掘【3 3 q 7 1 研究的是在结构或者 半结构数据集中挖掘频繁子结构，例如树、有向循环图( d a g ) 和包含环的 普通图等。因为大多数人类活动和自然现象都包含了结构，例如分子和生 物结构、万维网的连接结构等，为结构模式挖掘提供了广阔的应用前景。 f 5 ) 多维( m u l t i d i m e n s i o n ) 序列模式挖掘在序列模式中融合感兴趣的 多维信息，在考虑与时间戳相关属性的同时，挖掘多维信息中感兴趣的模 式，将得到能提供给用户更丰富信息的多维序列模式。h p i n t o 等人提出的 u n i s e q 算法 3 8 1 能有效地挖掘多维序列模式，多维序列模式挖掘是复杂数据 类型挖掘的一个前沿研究领域，有着极为广阔的应用前景。 1 2 3 存在的主要问题 在对序列模式挖掘算法的研究过程中，发现了两个值得注意的问题。 一是大多增量挖掘算法一般都只考虑向数据库中增加事务以及数据序列的 情况，很少考虑删除这些数据的情况，而这种情况在电子商务以及w e b 访 问挖掘等领域中经常存在。无论向数据库中增加数据还是从数据库中删除 数据的情况，本文都称之为面向数据集的序列模式增量式挖掘问题；二是 目前序列模式的增量式挖掘算法的研究主要集中在数据库的更新上，很少 有算法考虑到当算法参数( 最小支持度) 发生变化时，如何根据前次挖掘的 结果尽快挖掘新条件下的序列模式集，本文将这种情况称为面向算法参数 的序列模式增量式挖掘问题。这两类问题在以前的研究算法中尚未涉及到 或涉及很少。 虽然利用目前的序列模式挖掘算法( 例如，g s p 算法或者p r e f i x s p a n 算 法) 也可以解决面向数据集的序列模式增量式更新的问题以及面向算法参 数的序列模式增量式更新的问题，但是这些算法必须在更新的数据库上或 者是在新的算法参数下重新挖掘数据库，没有充分利用前次序列模式挖掘 得到的结果，使得挖掘效率大大降低，而且也不符合增量挖掘的思想。 结合序列模式挖掘的国内外研究现状，可以看出由于数据库更新或者 算法参数发生变化而引起的序列模式的增量式挖掘是有待于进一步研究的 课题，涉及到当从序列数据库中删除事务和数据序列时，如何利用已有的 6 第1 章绪论 序列模式集挖掘新的序列模式的问题，以及当算法参数( 即最小支持度) 发 生变化时，如何高效地挖掘新的序列模式等问题。 1 3 本课题要解决的问题及意义 通过对国内外研究现状的分析，可以看出现有的序列模式增量式挖掘 算法一般只能处理向数据库中增加事务以及数据序列时序列模式的维护问 题，而对于在删除这些数据的情况下以及算法参数发生变化时的序列模式 维护问题却无能为力。 尽管当前的p r e f i x s p a n 算法在挖掘序列模式时已经获得了很好的性 能，完全可以用来挖掘新数据库中以及新的算法参数下的序列模式。但是， 这样就没有充分利用已有序列模式挖掘的结果，势必降低模式挖掘的效率， 而且也不符合增量挖掘的思想。 因此，本课题将对于从数据库中删除事务以及数据序列时的序列模式 增量式挖掘问题以及算法参数发生变化时交互的序列模式挖掘问题分别进 行研究，提出有效的解决方法，并编程实现以验证其有效性和优越性。 本课题所要解决的这两个问题都属于序列模式增量挖掘的范畴，所不 同的是前者是面向数据集的序列模式增量挖掘，而后者是面向算法参数的 序列模式增量挖掘。无论是哪种形式的增量挖掘，归根结底所面临的问题 都是如何利用已有序列模式挖掘的结果，加快本次挖掘的过程。这两类问 题的研究在顾客购物模式、客户保持、电子商务以及w e b 访问挖掘等领域 具有重要的应用价值。 1 4 课题的主要研究内容及本文结构 本课题的主要研究内容包括： 为了解决当从序列数据库中删除事务以及数据序列时序列模式的增量 式更新问题，提出一种有效的算法，该算法将基于a p r i o r i 的候选产生和测 试特性，利用在前次模式挖掘过程中得到的信息，同时采用一种新的候选 生成方法，这种方法将使得候选集的规模及挖掘新的序列模式的开销大大 降低，提高增量式挖掘的效率。 7 燕山大学工学硕士学位论文 为了解决算法参数( 即最小支持度) 发生变化而序列数据库不变的情况 下交互的序列模式挖掘问题，提出一种有效的算法。该算法将基于候选库 c b 的结构，将前次挖掘所获得的候选序列及其支持计数的信息都保存在 c b 中，而且在用户定义的最小支持度变小时，对候选库c b 进行及时更新。 该算法采用直接生成新的候选序列的方式，将节省拼接操作及支持计数的 开销，提高交互式序列挖掘的效率。 本文的结构如下： 本文第一章介绍了课题的产生背景、研究现状、以及课题的主要工作 和思想。第二章将介绍序列模式挖掘的基本理论，并对现有的几种经典序 列模式一般挖掘算法及增量式挖掘算法进行简要分析，为后继的研究打下 基础。第三章给出当从序列数据库中删除事务和数据序列时序列模式的增 量式挖掘的问题定义，基于a p r i o r i 的特性，将提出一种序列模式的增量式 更新算法i u 二d ( i n c r e m e n t a lu p d a t i n gw h e nd e l e t i n gs o m ed a t a ) ，并给出实例 说明与性能分析。第四章给出最小支持度发生变化时交互式序列模式挖掘 的问题定义。基于候选库c b 的结构，将讨论新的候选序列集的产生方式， 提出交互式序列模式发现的有效算法i s p m ( i n t e r a c t i v es e q u e n t i a lp a _ 【t e m m i n i n g ) ，并给出实例说明与性能分析。第五章将对于以前两章所提出的算 法用j a v a 语言进行编程实现，介绍实验所用数据集的来源，阐述算法实现 中的关键技术，并给出实验结果及结果分析。最后对本文提出的算法性能 做出总结，并对未来的研究方向进行展望。 8 第2 章序列模式挖掘的基础理论 第2 章序列模式挖掘的基础理论 2 1序列模式挖掘的相关定义 为了描述问题的方便性，r a g r a w a l 和r s r i k a n t 在文献【1 1 和 1 3 中给 出了序列模式挖掘问题的以下一些基本定义。设非空集合i = 佛i 2 i ，i 。) ， 其中i 。( 1 s i ”) 称为项( i t e m ) 。 定义2 1 ：项集( i t e m s e t ) 是由若干项组成的集合。序列( s e q u e n c e ) 是由 若干项集组成的有序列表。序列s 可表示为 ，其中j ，是项集， 即s ，量i ( 1 j ，) 。j ，也称为序列5 的一个元素，表示为( 葺x 2 - 呵。) ，其中 i ( 1 七s m ) 。如果元素中只有一个项，例如元素0 ) ，则可以简写成x 。 任何项在一个序列的每个元素中最多可以出现次，但可以出现在一个序 列的不同元素之中。 定义2 2 ：一个序列中项的数目定义为这个序列的长度( l e n g t h ) ，长度 为z 的序列称之为扛序列。序列中项集的数目称为这个序列的大d 、( s i z e ) 。 定义2 3 ：设有两个序列，其中a = 、f l = ，如果 存在1 ，2 所，使得a l - b 矿口2 呈6 矿、b j ，则称a 是卢的 一个子序习j ( s u b s e q u e n c e ) ，卢是口的个超序列( s u p e r - s e q u e n c e ) ，以a 口 表示。 定义2 4 ：序列数据库s 是由 组成的集合，其中s 是一个序列， j f 堤该序列的标识( 叻。如果序列a 是s 的子序列，则称元组 包含 序列a ，记为c z c - s 。a 在s 中的支持数是指s 中包含a 序列的个数，记为 d 5 ) ，即仃s ) = l i ( s ) s ) ) l 。a 在s 中的支持度 是指s e e 包含口的序列在所有序列中所占的比例，设s e f 序列总数为，则 有s u p p o r t s ) = 叮s ) u 。 定义2 5 ：在一组序列中，不能包含在任何其他序列中的序列称为最大 序列( m a x i m a ls e q u e n c e ) 。 定义2 6 ：给定一个最小支持度m i n s u p ，如果一个序列a 在序列数据库s 9 燕山大学工学硕士学位论文 中的支持度s u p p o r t s 陋) m i n s u p ，则称序列a 是s 中的一个序列模式。一 个长度为，的序列模式称为，模式。 定义2 7 ：顾客事务数据库是元组( c i d ，t i d ，构成的集合，其a c i d 是顾客编号，t i d 是事务时间，堤一个项集。每一个( c i d ，t i d ，元组 称为一个事务( t r a n s a c t i o n ) 。 序列模式挖掘的问题定义如下：现有序列数据库s ，给出了最小支持 度m i n s u p ，序列模式挖掘就是要找出序列数据库s 中所有满足m i n s u p 的 序列模式。 2 2 序列模式的一般挖掘算法 在r a g r a w a l 等人提出序列模式挖掘的概念之后，越来越多的科研工 作者逐渐关注于序列模式挖掘的研究【3 9 枷】，提出了一系列序列模式挖掘算 法。现有的序列模式挖掘算法基本上可以分为两大类： 第一类是基于a p f i o f i 特性的算法，主要包括a p r i o r i a l l 算法和g s p 算法等。这类算法中大多数采取了候选序列生成和检查的方法( c a n d i d a t e g e n e r a t i o n a n d t e s ta p p r o a c h ) ，在基于己生成的频繁序列集中搜索更长的 频繁序列，在执行过程中需要多次扫描数据库。 第二类是j h a n 等人提出的基于模式增长的算法，包括f r e e s p a n 算法、 p r e f i x s p a n 算法等。这类方法采取了一种分而治之( d i v i d e 。a n d c o n q u e r ) 的 模式增长策略，基于现有的序列模式将序列数据库递归地投影到一系列更 小的投影数据库，只需通过探索每个投影数据库中局部的频繁部分使序列 模式得到增长。 2 2 1 a p r i o r i a l l 算法 a p r i o f i a l l 算法源于频繁项集算法a p f i o f i ，它把a p r m r i 的基本思想扩 展到序列模式挖掘中，是一个需要多遍扫描数据库的算法。该算法将序列 模式挖掘过程分为五个阶段： ( 1 ) 排序阶段将原始的数据库以顾客编号为主键，以事务时间为次键 进行排序，然后将原始事务数据库转换为顾客序列数据库。 第2 章序列模式挖掘的基础理论 ( 2 ) 频繁项集阶段这个阶段将找出所有的频繁项集，以每个频繁项集 为唯一元素的序列即为频繁1 - 序列模式。 f 3 ) 转换阶段这个阶段分为两步，第一步删除序列中的非频繁项集， 第二步将序列中的频繁项集转换至所定义的整数值。 ( 4 ) 序列阶段序列阶段算法的基本思想是分阶段找出所有的频繁序 列，在每个阶段中，从一个由频繁序列组成的种子集开始，利用这个种子 集产生新的候选序列，然后找出其中的频繁序列，这些频繁序列构成下一 阶段的种子集。 ( 5 ) 最大序列阶段若最终目的是要发现所有的最大频繁序列，算法将 包含最大序列阶段。在这个阶段，频繁序列集中不是最大序列的频繁序 列将被删除。 a p r i o r i a l l 算法遵循候选产生和测试的原则，需要多次扫描数据库。在 挖掘过程中没有考虑时间间隔约束的存在，它认为一个序列中所有的元素 出现在数据库中足够多的数据序列中，就被认为是频繁的。只要两个k 序 列有共同的最大前缀时就可以创建候选( k + 1 ) - 序列，这种产生候选序列的 方法使得它不能发现所有的序列模式。 2 2 2g s p 算法 g s p ( g e n e r a l i z e ds e q u e n t i a lp a t t e r n s ) 算法在a p r i o r i a l l 算法的基础上， 引入了分类、滑动窗口和时间间隔限制的概念，可以挖掘出更具有一般意 义的序列模式【1 3 】。 g s p 算法描述如下： ( 1 ) 扫描序列数据库，得到长度为1 的序列模式厶，作为初始的种子集。 ( 2 ) 根据长度为i 的种子集厶通过连接操作和剪切操作生成长度为i - i - 1 的候选序列模式e + 1 然后扫描序列数据库，计算每个候选序列模式的支 持数，产生长度为i + l 的序列模式上。，并将工。作为新的种子集。 ( 3 ) 重复第二步，直到没有新的序列模式或者没有新的候选序列模式产 生为止。 产生候选序列模式主要分两步： 燕山大学1 ：学硕士学位论文 连接阶段：如果去掉序列模式s 1 的第一个项目与去掉序列模式s z 的最 后一个项目所得到的序列相同，则可以将s 与s 2 进行连接，即将j 2 的最后 一个项目添加到s - 中。 剪切阶段：若某候选序列模式的某个子序列不是序列模式，则此候选 序列模式不可能是序列模式，将它从候选序列模式中删除。 g s p 算法是a p r i o r i a l l 算法的扩展，这两种算法之间的关键不同在于 候选序列产生的方式。g s p 算法仍然遵循候选产生和测试的策略，需要多 次扫描序列数据库。同a p d o d a l l 算法一样，在支持度阀值较低时，将会 产生大量的候选序列。 2 2 3 p r e f i x s p a n 算法 p r e f i x s p a n ( p r e f i x - p r o j e c t e ds e q u e n t i a lp a t t e r nm i n i n g ) 算法是基于模式 增长的挖掘方法。该算法基于频繁前缀子序列投影并通过在其后添加频繁 项来实现序列的增长。 2 2 3 1 相关定义首先介绍前缀( p r e f i x ) 、后缀( s u f f i x ) 、投影数据库和序 列在投影数据库中的支持度等概念。 定义2 8 ：设序列中的每个元素中所有的项以字母顺序排列，给定序 列a = ，卢= 胛) ，其中口l ，口2 ，- ，口。在序列数据 库s 中都是频繁项集。当且仅当满足以下三个条件时，称口是a 的一个前 缀：当i m l 时，口。- - - a 成立；口，c a ，；( 日。一口，) 中所有的项在字母顺序 表中均排在口。中的项之后。 定义2 9 ：给定序列a = ，其中口l ，a 2 ，a 。在序列数据 库s 中都是频繁项集。若卢= ( 埘 ) 是口的一个前缀，则序列 y = 称为a 关于前缀p 的后缀，其中口。”= ( 口。一口。) ，表示为 y = a 卢，或者a = p y 。 定义2 1 0 ：设a 是序列数据库s 中的一个序列模式，则d - 投影数据库 是s 中的所有序列关于前缀a 的后缀的集合，表示为s l 。 定义2 1 1 ：设a 是序列数据库s 中的一个序列模式，口是以a 为前缀 的序列模式，则卢在a - 投影数据库s l 中的支持度是在s i 。中满足卢c _ c t y 第2 章序列模式挖掘的基础理论 的序列y 在s i 。所占的比例，表示为s u p p o r t s l 。( 卢) 。 2 2 3 2 p r e f i x s p a n 算法p r e f i x s p a n 算法描述如下： 输入：序列数据库s | 。，最小支持度m i n s u p 。 输出：整个序列模式集p 。 调用：p r e f i x s p a n ( a ，f ，s 1 。) ，其中a 是一个序列模式，2 是序列a 的 长度，若a 不为空序列，则s i 。是a 一投影数据库，否则1 = 0 且s l 。是序列数 据库s 。 b e g i n ( 1 ) 扫描s i 。，找出所有的频繁项b 。b 可以添加到序列a 的最后一个元 素中形成一个新的序列模式，或作为一个单独的元素( 6 ) 添加到序列a 中形 成一个新的序列模式。如果没有找到任何频繁项，该分支的递归过程结束。 ( 2 ) 对于每一个频繁项b ，将其添加到序列a 上形成一个新的序列模式 a ，将a 添加到p 中。 ( 3 ) 对于每一个序列模式a ，构造a 投影数据库s l ，然后递归地调用 p r e f i x s p a n ( a ，l + 1 ，s l 。) a ( 4 ) 若所有分支的递归过程都己完成，则输出p 。 e n d 与前两种算法相比，p r e f i x s p a n 算法不需要产生候选序列模式，可以 大大缩小模式搜索空间，而且该算法构造的投影数据库相对于初始数据库 不断减小。其主要开销就在于投影数据库的构造。 2 2 4 算法的性能分析 类a p r i o r i 算法都包含逐步产生候选序列然后检查是否频繁的过程，使 得此类算法存在三个与实现技术无关的缺点： ( 1 ) 当序列数据库很大时，需要产生和检查的候选序列的数量巨大。 ( 2 ) 在挖掘过程中，需要多次扫描数据库。 ( 3 ) 如果序列数据库中存在很长的序列模式，这些算法将存在很大困难 甚至不能挖掘出序列模式。 基于模式增长的算法采取了分而治之的策略，这类算法的基本思想是 燕山大学工学硕士学位论文 根据现有的序列模式将序列数据库递归地投影到一系列更小的投影数据 库，只需通过探索每个投影数据库中局部的频繁部分使序列模式得到增长， 直至没有新的序列模式产生为止 1 8 】。基于模式增长的算法具有以下优点： ( 1 ) 在挖掘过程中不会产生任何无价值的候选序列。 ( 2 ) 采用分而治之的策略有效地减少了需要处理的数据。 ( 3 ) 需要的内存空间比较稳定。 p r e f i x s p a n 算法的性能要优于a p r i o r i a l l 算法和g s p 算法，特别是在 最小支持度较低时，p r e f i x s p a n 算法的优势更加明显。p r e f i x s p a n 算法的优 越性能得益于以下三个因素： ( 1 ) 采用了模式增长的方法，不需要产生候选序列。p r e f i x s p a n 算法与 a p r i o r i a l l 算法、g s p 算法不同，它通过构造投影数据库来产生频繁序列， 避免了产生和测试一些无效的候选序列，只需要搜索一小部分空间，而 a p r i o r i a l l 算法和g s p 算法