（计算机应用技术专业论文）序列模式挖掘算法研究与实现.pdf

江苏大学硕士学位论文 摘要 数据挖掘是从数据库或其它信息库的大量数据中挖掘出有效知识的过程，是 当前涉及人工智能和数据库等学科的一门相当活跃的研究领域，序列模式的发现 是其中的一个重要研究课题。 序列模式挖掘就是在时序数据库中挖掘相对时间或其他模式出现频率高的 模式。序列模式发现是最重要的数据挖掘任务之一，并有着广阔的应用前景，比 如交易数据库中的客户行为分析、w 曲访问日志分析、科学实验过程的分析、文 本分析、d n a 分析和自然灾害预测等等。 多维序列模式挖掘是在序列模式挖掘基础上考虑了其它一些维信息，像在顾 客购买行为分析中考虑到顾客的年龄、性别等信息，这样的模式融合了更多的信 息，应用价值更高。 本文在分析序列模式挖掘算法的基础上，对多维序列模式挖掘算法以及在应 用领域的具体实施方面做了较深入的探讨，主要贡献如下： ( 1 ) 提出高效的基于连接的多维序列模式挖掘算法s e q - m d p ( s e q u e n e e - m u l t i - d i m e n s i o n a lp a t t e r n ) 。在挖掘多维模式时，扫描一次投影库，记录下得到的 频繁项的所属属性以及元组信息，用于后续的连接，不需要再扫描投影库，仅通 过连接就可以获得所有的多维模式。实验表明该算法有较好的时间性能。 ( 2 ) 将多维序列模式挖掘算法应用于异常检测。针对入侵检测的特点将数据 挖掘技术应用于用户异常行为检测中，首先将用户行为数据库转化为多维序列数 据库，然后对其进行多维序列模式挖掘以提炼出用户高频行为模式，将当前模式 库与历史模式库做比较判断是否存在异常，实验说明了方法的可行性。 ( 3 ) 设计并实现了序列模式挖掘工具。此工具包含了几个有效的序列模式挖 掘算法，一方面用户可以根据自己的需求选择合适的算法，另一方面也是一个序 列模式挖掘算法的比较平台。与已有工具相比，此工具融合了几种效率比较高的 专门针对序列模式挖掘的算法，为用户提供了多种选择方法。 关键词：数据挖掘，序列模式，多维序列模式，入侵检测 江苏大擘硕士学位论文 a b s t r a c t d a t am i n i n gi st h ep r o c e d u r eo fe x t r a c t i n ga n dm i n i n gk n o w l e d g ef r o ml a r g e a m o u n to f d a t ai nd a t a b a s e , d a t aw a r e h o u s i n ga n do t h e ri n f o r m a t i o nr e p o s i t o ra n da l s o i sar a p i d l ye m e r g i n gr e s e a r c hf i e l dr e l e v a n tt o a r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s e s y s t e m d i s c o v e r yo f s e q u e n t i a lp a t e m si sa ni m p o r t a n tf i e l di nd a t am i n i n gr e s e a r c h s e q u e n t i a lp a t t e r nm i n i n gi st om i n i n gp a t t e r n st h a ta r ef r e q u e n tr e l a t i v et ot i m e o ro t h e rp a t t e r n si n $ 1 即l l l l e n c ed a t a b a s e i ti so n eo ft h em o s ti m p o r t a n tt a s k so fd a t a m i n i n ga n dw i l lh a v eb r o a da p p l i c a t i o ni nf u t u r es u c ha st h ea n a l y s i so fc u s t o m e r b e h a v i o ri nt r s n s a e t i o nd a t a b a s e ，w e bu s a g el o ga n a l y s i s ，t h ea n a l y s i so fs c i e n c e e x p e r i m e n tp r o c e d u r e ，t e x ta n a l y s i s ，d n aa n a l y s i sa n dn a t u r ed i s a s t e rp r e d i c t i o ne ta 1 m u l t i - d i m e u s i o n a ls e q u e n t i a lp a t t e r nm i n i n gi sb a s e do ns e q u e n t i a lp a t t e r n m i n i n ga n dc o n s i d e rs o m eo t h e ri n f o r m a t i o n ，l i k ea g e , g e n d e ro ro t h e ri n f o r m a t i o ni n a n a l y s i so fc u s t o m e r s p u r c h a s i n gb e h a v i o r s u c hp a t t e r n sc o m b i n em o r ei n f o r m a t i o n a n dt h ev a l u eo f a p p l i c a t i o ni sh i 班 o nt h eb a s i so ft h ea n a l y s i so fs e q u e n t i a lp a t t e r nm i n i n ga l g o r i t h m ，w ec o n v e r t o u rf o c u s e so i lm a l t i - d i m e n s i o n a l s e q u e n t i a lp a t t e r nm i n i n ga n dt h es p e c i f i c i m p l e m e n t a t i o ni nt h ef i e l do f a p p l i c a t i o n t h em a i nc o n t e x ti sa sf o l l o w s ： ( 1 ) t h i sp a p e rp r e s e n t sae f f i c i e n ta l g o r i t h mo fm i n i n gm u l t i - d i m e n s i o n a l s e q u e n t i a lp a a e r n i ts o a rp r o j e c t i o nd a t a b a s eo n c ea n d r e c o r dt h ea t t r i b u t en a m ea n d t h ei n f o r m a t i o no f r e c u r d so fa l lt h ef r e q u e n ti t e m sw h e nm i n i n gm d - p a t t e r n s ，f o rt h e f o l l o w i n gj o i n i n g w ec 尬g e ta l lt h em d - p a r e m sj u s tt h r o u g hj o i n i n ga n dn on e e dt o s c a np r o j e e t i o nd a t a b a s ea g a i n ( 2 ) t h ea p p l i c a t i o no fa n o m a l yd e t e c t i o nu s i n gt h ea l g o r i t h mo fs e q u e n t i a l p a r e mm i n i n g t h em e t h o do fd a t am i n i n ga r eu s e dt od e t e c ta b n o r m a lb d l a v i o ro f u s e l sf i ti n t oi n t r u s i o nd e t e c t i o ns y s t e m t h eb e h a v i o rd a t a b a s eo fu s e r sa r ec h a n g e d i n t os e q u e n c ed a t a b a s ef i r s t l y , t h e nm i n i n gf r e q u e n ts e q u e n t i a lp a t t e r n sf r o ms e q u e n c e d a t a b a s e , c o m p a r ec u r r e n tp a t t e r n sw i t l lh i s t o r i c a lp a t t e r n sa n dd e t e r m i n ew h e t h e r m e r ei sa b n o r m a l t h ee x p e r i m e n ts h o wt h ef e a s i b i l i t yo f t h i sm e t h o df i n a l l y ( 3 ) d e s i g na n di m p l e m e n tat o o lo fs e q u e n t i a lp a t t e r nm i n i n g i ti n c l u d es e v e r a l e f f i c i e n ts e q u e n t i a lp a t t e r nm i n i n ga l g o r i t h m s o nt h eo n eh a n d , u s e r s 啪c h o o s e s u i t a b l ea l g o r i t h m sa c c o r d i n gt ot h e i ro w nn e e d s o nt h eo t h e rh a n d t h et o o li sa c o m p a r i s o n sp l a f f o r mo f s e q u e n t i a lp a t t e r nm i n i n ga l g o r i t h m s c o m p a r e dw i t he x i s t i n g t o o l s ，i tc o n v e r g es e v e r a le f f i c i e n ta l g o r i t h mf o rs e q u e n t i a lp a t t e r nm i n i n ga n dp r o v i d e a v a r i e t yo f o p f i o n sf o ru s e r s k e y w o r d ：d a t am i n i n g , s e q u e n t i a lp a t t e r n , m u l t i - d i m e n s i o n a ls e q u e n t i a lp a t t e r n , r e d u n d a n tm u l t i - d i m e n s i o n a lp a t t e r n , i n t r u s i o nd e t e c t i o n l i 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独。 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 寸 碧 五r 月 尚 1 名 年 签7 f 者 肿 怍 文论 ： 位 期 学 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密残 学位论文作者签名：尚石时 、j 伊7 年，l 月ig 目 指导教师签名：础 矽每阱l 圆e 江苏大学顾士学位论文 第一章绪论 1 1 课题研究背景与意义 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的 数据量急剧增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些信息 从数据库中抽取出来，将为应用部门创造很多潜在的利润，数据挖掘技术就是基 于这样的商业角度开发出来的。 确切地说，数据挖掘( d a t am i r a n g ) ，又称数据库中的知识发现( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ，k d d ) j 是指从大型数据库或数据仓库中提取隐含的、未知 的、非平凡的及有潜在应用价值的信息或模式，它是数据库研究中的一个很有应 用价值的新领域，融合了数据库、人工智能、机器学习、统计学等多个领域的理 论和技术。数据挖掘所包含的范畴很广，而在数据挖掘中，关联规则是其中非常 重要的一种挖掘模式。 自从美国i b ma l m a d e n 实验中心的r a g r a w a l 和t i m i e l i n s k i 等人在1 9 9 3 年论 述了挖掘关联规则的问题【1 】，人们在许多方向上做了大量的工作去发现属性之间 的关系。关联规则最初应用于交易数据库中发现项i j ( i t e m s ) 之间的潜在关系， a g r a w a l 等将这类关联规则称之为“布尔关联规则”( b o o l e a n a s s o c i a t i o nr u l e s ) 。 在1 9 9 6 年，r s r i k a n t 和a g r a w a l 又提出了挖掘“多值关联规则”( q u a n t i t a t i v e a s s o c i a t i o nr u l e s ) 的算法1 2 1 ，用来处理数据库中包含数量属性和类别属性的情况。 在数据挖掘研究领域，对于关联分析的研究开展的比较深入，人们提出了多种关 联规则的挖掘算法。关联分析的目的是挖掘隐藏在数据问的相互关系，它能发现 数据库中形如“9 0 的顾客在一次购买活动中购买商品a 的同时购买商品b ”之 类的知识。但是有一种形式的关联规则，它在实际分析中相当有用，然而运用已 有的成熟关联规则算法不能将它发现出来。 举例来讲，直接运用上面提到的技术无法发现以下规律： 夺某种股票换手率增长1 5 ，其股票收盘价可能随后上涨1 0 ： 夺某商品打折5 可以使其总销售额上升5 - 1 0 ； 夺病人在做治疗后，5 天内白血球数提高2 是由某药剂的剂量增力h i o 造 成。 江苏大学硕士学位论文 夺某只股票收盘价相对于时间出现的某种趋势变化。 对于上述关系，使用经典关联规则没有办法得到相应的规律。而在实际情况 下，这种规律恰恰经常是人们所关心的，而且经常成为决策者辅助决策的重要理 论依据。针对上述问题的存在，序列模式挖掘应运而生。 序列模式挖掘( s e q u e n c 露p a t t e r nm i n i n g ) 是指挖掘相对时问或其它出现频率高 的模式。序列模式挖掘与普通的关联规则非常相似，但是可以解决关联规贝l j 所不 能解决的问题。关联规则主要是针对事务数据库进行挖掘操作的，以便找到事务 数据库中属性之间的关联性：而序列模式挖掘的数据源则是序列数据库。序列数 据库是指由有序事件序列组成的数据库，可以有时间标记，也可以没有。 综上所述，序列模式挖掘是数据挖掘中一个重要的研究领域，对序列模式挖 掘的研究有重大的现实意义。 1 2 国内外研究现状 近年来，序列模式挖掘逐渐成为数据挖掘领域的研究热点之一。序列模式挖 掘是从关联规则的频繁项目集挖掘发展而来的，它在关联模型中增加了时间属 性，把数据之间的关联性与时间联系起来，寻找的是事务之间在时问上的先后次 序关系。它根据数据随时问变化的趋势，发现某一时问段内数据的相关处理模型， 预测将来可能出现的值的分布。目前已有许多学者对序列模式挖掘进行了深入的 研究。 序列模式挖掘问题的研究首先由m ma 1 m a d 曲研究中心的a g r a w a l 和s r i k a n t 1 3 1 提出：给定一个序列数据库，每个序列都是一个按时问顺序排列的事务( 1 r a n $ a c t i o n ) 的列表，每一事务包含一个项目( i t e m ) 的集合，挖掘的任务是找到所有满 足用户指定的最小支持度阈值的所有序列模式，支持度是指包含该序列模式的序 列数与数据库中序列总数之比：文中同时给出了两种类a p r i o d 算法的变种a p r i o r i s o m e 和a p r i o d a l l 。1 9 9 6 年，a g r a w a l 和s r i k a n t 提出了泛化序列模式挖掘方法g s p 4 ( o c n c r a l i z c ds e x l u c n t i a lp a t t 既 n s ) ，该方法对序列模式问题定义作了泛化处理， 使其包含了相邻事务的时间约束、滑动时间窗口和可由用户定义的类层次。这几 种方法都是基于a p r i o r i 算法，因此要多次扫描数据库且生成的候选项集数据量 大。 2 江苏大学硕士学位论文 j i a w e ih a r t 等人提出了基于数据库投影和分片挖掘的序列模式生长( d a t a b a s e p r o j e c t - b 丛e ds e q u e n t i a lp a t t e r ng r o w t h ) 技术f r e c s p a n ( f r e q u e n tp a t t e r n - p r o j e c t c d s e q u e n t i a lp a t t v mm i n i n g ) 算法t q 和p r e f i x s p a n ( m i n i n gs e q u e n t i a lp a t t e r n se f f i c i e n t l y b vp r e f i x p r o j e c t e dp a t t e r no r o w m ) g 法1 6 】。应用了前缀投影技术，这样就避免了 显著的候选产生时的花费，同时也减4 , t 投影数据库的大小，提高了挖掘效率。 美国c o m d l 大学的a y r c s 等人，提出了序列模式挖掘算法s p 枷川( s e q u e n t i a l p a t t e r nm i n i n g ) ，采用深度优先方式搜索模式空间，并且采用多种约减策略缩小搜 索空间；采用纵向位图来表示整个序列数据库，在数据库中序列模式很长时该算 法特别有效。 在国内，序列模式挖掘也是数据挖掘界的研究热点之一，受到了学术界和工 业界的广发关注。 宋世杰、胡华平等人在重新定义序列模式长度、增加序列模式挖掘粒度的基 础上，提出一种基于大项集重用的序列模式挖掘算法h v s m 8 ) ( f i r s t h o r i z o n t a l l y - l a s t - v e r t i c a l l y s c a n n i n g d a t a b a s es e q u e n t i a l p a t t e r n m i n i n g ) 。该算法采用垂直位图法 表示数据库，先横向扩展项集，将挖掘出的所有大项集组成一大序列项集，再纵 向扩展序列，将每个一大序列项集作为“集成块”，在挖掘k 大序列时重用大项 集。 聂成林在文献【9 】中，将概念格应用在序列模式挖掘中，仅需对交易数据库 扫描一次即可得到与挖掘任务相关的所有信息，从而减少了扫描原始交易数据库 的次数。为节约格的存储空间，还扩展了概念格模型，提出外延约简的概念，对 算法进行了优化。 上面介绍的算法都是针对一般序列模式挖掘，即不带有其它一些维信息的序 列模式，另一类更有价值的序列模式挖掘是多维序列模式挖掘。多维序列模式挖 掘是在序列模式挖掘基础上考虑了其它一些维信息，像在顾客购买行为分析中考 虑到顾客的年龄，性别等信息，这样的模式融合了更多的信息，应用价值更高。 在多维序列模式挖掘方面主要挖掘算法有u n i s c q ( c m b e dm u l t i d i m e n s i o n a l i f o r m a t i o ni n t os c q u 饥c c s ) ，s c q - d i m ( s c q u c n c c - m u l t i - d i m e n s i o n a lp a t t e r n ) ，d i m - s e q ( m u l t i d i m s i o n a lp a t t e r n s c q u e n c c ) 等算法1 0 1 。u i l i s e q 算法把多维信息嵌入到序列 中看作序列的项，采用p r e f i x s p a n 算法来挖掘多维序列模式，在维度较低时效率 江苏大学硕士学位论文 比较高，随着维度的不断升高效率不断下降。s e q - d i m 算法和d i m - s e q 算法将一 般序列模式和多维信息分开挖掘，前者先挖掘序列模式，然后再挖掘多维信息， 后者相反，先挖掘多维信息，然后挖掘序列模式。相对而言s e c l - d i m 算法更具有 针对性，效率也 土d i m s 闪算法要高，但是该方法要多次扫描投影数据库来挖掘 多维模式，因而在数据量比较大，维度较高时，时问开销还是比较大。 综上所述，序列模式挖掘是目前的一个热点研究领域，目前有待解决的问题 是如何进一步提高序列模式算法的效率以及如何用序列模式挖掘算法解决实际 问题。基于以上的分析，本文就针对多维序列模式挖掘以及序列模式挖掘方法在 入侵检测中的应用作了深入探讨，并设计实现一个专门针对序列模式挖掘的工 具。 1 3 论文研究的主要内容 本文主要对以下几方面作了深入的分析与探讨： 1 、对国内外序列模式挖掘算法作了对比与分析，重点介绍了a p r i o r i a l l 、 g s p 、p r e f i x s p a i l 三个经典序列模式挖掘算法以及u n i s c q 、s e c i - d i m 等多维序列 模式挖掘算法，分析了各自的优缺点。 2 、在分析多维序列模式挖掘的基础上，针对s e q 。d i m 算法存在的不足，提 出了一种高效的多维序列模式挖掘算法s e q - m d p ( s e q u e n c e ，m u l t i - d i m e n s i o n a l p a t t e r n ) 。该算法采用了以空间换取时间的策略，在寻找频繁项的同时记录下相 关信息以用于后续的操作，减少了扫描序列投影数据库的次数，大大节约了时间 开销。 3 、探讨了多维序列模式挖掘算法在入侵检测中的应用，采用s e q - m d p 算法 对用户异常行为数据作了分析。首先将用户行为数据作简单的处理，生成多维序 列数据库，然后采用多维序列模式挖掘算法挖掘出高频模式，将挖掘出的当前高 频模式库与历史高频模式库通过相似度比较判断是否存在异常。 4 、设计并实现一个序列模式挖掘工具，将几种效率比较高的序列模式挖掘 算法融合为序列模式挖掘平台，用户可以根据自己的需求选择合适的算法，方便 了用户操作。 4 江苏大擘硕士学位论文 1 4 论文的组织结构 本文的具体组织结构如下： 第一章绪论：介绍了课题的背景、研究意义国内外研究现状以及论文研究 的主要内容，最后给出了论文的组织结构。 第二章数据库中的序列模式发现：首先介绍了序列模式的相关概念，然后 介绍t - - 种经典的序列模式挖掘算法a p r i o r i a l l 、g s p 和p r e f i x s p a n 。接下来介绍 了多维序列模式挖掘的相关概念及相关挖掘算法u n i s e q 、s e q - d i m 等，最后总结 了本幸的内容。 第三章多维序列模式挖掘算法研究：具体分析了多维序列模式挖掘方法， 并重点介绍了一种新的多维序列模式挖掘算法s c q - m d p ( s e q u c n c c m u l t i d i m e n s i o n a lp a t t e r n ) ，最后通过实验将该新算法与s c q - d i m 算法进行比较。 第四章s c q m d p 算法在异常检测中的应用：首先简单介绍了入侵检测的相关 知识，然后具体讨论 s e q - m d p 算法在用户异常行为检测中的应用，最后通过实 验验证此方法的可行性。 第五章序列模式挖掘工具的实现：具体分析序列模式挖掘工具的各个模块 的设计思想以及具体实现。 第六章结束语：总结本文的主要研究内容和创新点，给出序列模式挖掘进 一步的研究方向。 5 江苏大肇硕士学位论文 第二章数据库中的序列模式发现 顾客交易序列中的知识发现问题是近年数据挖掘的一个活跃的研究领域。近 几年来，随着数据库中数据挖掘研究和应用的不断深入，序列中的知识发现问题 正引起越来越多的人工智能和数据库界研究者的兴趣。 2 1 序列模式的提出 序列模式的概念最早是由a 掣a w a l 和s r i k a m 提出的，给定一个序列集，其中 每一个序列由项集构成，然后给定由用户确定的最小支持度阈值，序列模式挖掘 就是去发现所有的频繁予序列( 即：这些子序列的出现频率不小于给定的最小支 持度阈值) 。 序列模式分析同关联规则类似，但是它更侧重于分析事物之间的前因( 后果) 关系。这正如哲学中的“联系”包含各种联系：相似性、因果性等等。关联规则 只是说明了事物之间存在联系，而没有更进一步指明关系是什么类型。 发现序列模式的目的是为了寻找一段特定时间以外的可预测行为模式。这就 意味着在给定时间内的一种特定行为有可能产生其他行为或在一段时间框架内 的连续行为。这种规则生成方法是关联技术的变体。其会根据不同的因素如随时 间的变化来分析客户的购物行为。算法可通过查看1 0 , 0 0 0 个采购的集合来代替查 看1 0 ，0 0 0 次采购。比如说这些集合是一位客户连续的购物行程的采购列表。作为 一个典型业务实例，一个列表的集合可以是有关电脑的采购： ( 1 ) 十二月份的电脑 ( 2 ) 一月份的电脑游戏和游戏杆 r 3 ) - - 月份的附加电脑内存，以及更大的硬盘驱动 如果这种可能使用不同的时间标度却有着相同规则的序列关联被一系列的 客户所重复，那么序列关联算法通常将会返回一条规则，如：当客户在购买了电 脑之后又购买了电脑游戏的情况下，3 0 的可能性在后来选购时会额外再买内 存。 该算法也拥有在列表的各项问定义最小和最大时间段的能力。比如，这将会 使上述规则能包括既不会早在购买电脑游戏前一个月购买，也不会在购买了电脑 6 汪苏大学硕士学位论文 游戏后三个月后购买电脑内存的语句。 2 2 序列模式相关概念及定义 文献 3 】给出的有关序列模式的基本概念如下： 在交易数据库d b 中，每个商品称为一个数据项( i t e m ，以下简称项) ，非空 集合卢加，如，如 称为数据项集( i t e m s c t ，以下简称项集) ，其中每个城ls 七s m ) 是 一个项。长度为k 的项集称为颁集。d b 中每个交易( t r a n s a c t i o n ) f h 顾客号、交易 时间和该交易所购买的项集构成。不考虑顾客购买项的数量并假定同一时问一位 顾客只进行一次交易。 表2 1 交易数据库示例表2 2 对应的序列数据库 顾客号交易时间项集 l9 3 0 6 2 5c l9 3 0 6 3 0h 29 3 0 6 1 0 a b 29 3 0 6 1 5 c h 29 3 0 6 2 0 d ，f ，g 29 3 0 6 2 5 h 39 3 0 6 2 5 c ，e ，g 49 3 0 6 j 2 5 c 49 3 0 6 3 0 d ，g ，h 49 3 0 7 2 5 h 5 9 3 0 6 1 2h 顾客号顾客序列 l 2 3 4 5 和口玩幻，6 p ，如果存在一组整数 l 巍 幻 和 。 2 3 经典序列模式发现算法 序列模式的发现算法基本上可以分为以下两大类： 第一类是基于a p f i o f i 特性的、逐层( 1 e v e l - w i s e ) 的发现方法，包括a p r i o r i a i l 算法 2 1 和g s p 算法t 3 等，这类方法最先由r a g r a w a l 等入提出。关子频繁序列有以 下的重要特性( a p d o f i 特性) ：在交易数据库中，如果某一长度为k 的序列不是频繁 的。那么它的任何长度为针1 的超序列也不可能是频繁的。此类算法根据这个特 性在基于已生成的频繁序列搜寻更长的频繁序列的过程中对待检查的序列集进 行有效的修剪。除此之外，此类方法中的大多数采取了一种逐层的、候选序列生 成和测试方法( c a n d i d a t eg e n e r a t i o n - a n d - t e s ta p p r o a c h ) 。在算法执行中，需要多趟 扫描原序列数据库。算法的第一趟扫描将发现频繁i 序列。而第 趟以频繁k - 1 序 列的集合作为种子集来生成候选卜序列，然后扫描原数据库得到每个候选序列的 支持度，满足最小支持度的候选序列即为频繁序列，并将它作为下一趟扫描的种 子集。算法如此迭代地执行，直至没有频繁序列被发现或没有候选序列生成，算 法终止。 另一类方法由h a n 等人提出，称为基于序列模式增长( s e q u e n t i a lp a t t e r n s 江苏大学硕士学位论文 g r o w t h ) 方法，包括f r s p a n 算法f 5 4 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 3 1a p r i o r i a i l 算法 a p r i o r i a l l 算法将序列的长度定义为序列中包含的项集的数量。算法将序列 模式发现的过程分为以下五个阶段： ( 1 ) 排序阶段：将交易数据库以c i d 为主键，t i d 为次键排序，得到顾客序列数 据库。 ( 2 ) 频繁项集阶段：此阶段将发现所有的频繁项集，以每个频繁项集为唯一元 素的序列即为频繁i 一序列。 在关联规则发现的问题中，算法也需要首先发现频繁项集。这里发现频繁项 集的过程与之相似。二者之间的区别在于对项集支持度定义的不同。序列模式问 题中项集支持度是指序列数据库中支持项集的顾客数，而关联规则问题中则定义 为支持项集的交易数。对关联规则问题中发现频繁项集的过程稍做修改，便可用 于序列问题的频繁项集发现。 对发现的所有频繁项集。将其映射至一个连续整数的集合。映射的目的在于 将每个频繁项集视为单一的实体，可以减少检查一个序列是否包含于顾客序列的 时间开销。表2 3 为表2 1 中的频繁项集及一个可能的映射。 ( 3 ) 变换阶段：正如将在下面看到的，在序列阶段，需要重复地确定一个给定 频繁序列的集合中的哪些包含于一个顾客序列。为加快这个过程，算法需要对顾 客序列进行变换。变换的方法如下： 江苏大学硕士学位论文 表2 4 转换后的数据库 客号原序列 转换后序列用映射代替 l 2 ( a b ) ( c h ) f g ) ( h p ( c ) ( h ) ) ( d ) ( g ) ( d g ) p 3 ( c e g p 4 1 ；卜一) f o re a c hl 中的频繁卜序列壤d o d e l e t ef t o m a l ls u b s e q u e n c e so f s t 2 3 2g s p 算法 文献 4 】改进了基本序列模型，提出了泛化序列模式的发现，并给出了相应 的发现算法e p 6 s p 算法。 江苏大学硕士学位论文 2 3 2 1 基本序列模型的局限性 基本序列模型存在以下的局限性： 缺少时间约束。在实际应用中，用户通常希望指定序列模式的元素之间的 最大或最小时间间隔。例如用户不会关心顾客在购买了项目a 而在三年后又购买 了项目b 这样的序列，如果是两者的时间间隔在三个月内会更有意义。 对交易的死板的定义。在许多应用领域，只要交易发生的时间间隔在一个 较小的时间窗口内，序列模式的一个元素中的项目是否出现于不同的交易中无关 紧要。也就是说，序列模式的一个元素可由来自多个交易中的项目的并集组成， 只要这些交易发生的最早和最迟时间之差在一个滑动时间窗“s f i d i n gt i m e w i n d o w ) 内。 缺少分类层次。许多数据集具有用户对项目定义的分类层次，并且需要发 现跨越不同类层次上项目的序列模式。 为克服以上局限性，作者将序列模式的基本模型进行了扩展，加入了时间约 束、滑动时间窗口和分类层次，提出了泛化序列模式发现问题并给出了相应的 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 ) 。g s p 算法在序列模式发现过程中结合时 间约束、滑动时间窗口和分类层次进行。 2 3 2 2 泛化序列模式 定义2 4 泛化序列模式问题中，序列p 被数据序列赤 包含的 含义重新定义如下： ( 1 ) 如基本模型中定义，在没有时间约束、滑动时间窗口和分类层次情况下， 若序列5 是数据序列d 的子序列，则称跑含s ； ( 2 ) 加入分类层次：交易孢含一个项善e 玑若工在仲或x 是砷某一项目的祖 先。如果交易跑含项集y 曰中的所有项目，则孢含项集y o 数据序列孢含序列 j ，如果存在整数f ，f ，使得墨d , 1 ，是噶2 ，& 丸； ( 3 ) 加入滑动窗口：如上文所述，滑动窗口因允许数据序列d 中的多个交易包 含j 中的一个元素而放宽了j 包含j 的条件。数据序列d 包含序列5 ，若存在整数 z ，翔 如9 f 甄，使得： l 幽包含于集合u ：ld t ，l g 白 2 t r a n s a c t i o n - t i m e ( d , ) - t r a n s a c t i o n - t i m e ( d t i ) w i n d o w s i z e ，1 蚴 1 2 江苏大学硕士学位论文 ( 4 ) 加入时间约束：时间约束限制了包含j 中连续元素的交易集合间的时间间 隔。给定用户定义的w i n d o ws i z e ，m a xg a p ，r a i n _ g a p ，数据序列孢含序列s ，若 存在整数f ，白， 如9 世 呶使得： 1 袍含于集合u ：。d k ，l g 匀 2 t r a n s a c t i o n - t i m c ( d h i ) 一t r a m a c t i o n - t i m e ( d 1 3 i ng a p 2 及其子序列c ，如果满足以下条件之一， 则c 是j 的连续子序列： ( 1 ) c 是由删除s 中第一个元素s ，或最后一个元素粕中的某一项目得到的； ( 2 ) c 是由删除s 中任一具有多于两个项目的元素中的某一项目得到的； ( 3 ) c 是c 的连续子序列，c 是s 的连续子序列。 因此有如下的性质： 性质2 1 对任一数据序列d ，若它包含序列s ，则d 必然包含f 的任连续子序 列。 注意到如果没有m a xg a p 约束，则秘然包含5 的任一子序列( 包括非连续子序 列) ，这个特性是生成候选序列的基础。 2 3 2 3g s p 算法 g s p 算法是个迭代的过程。在每一次迭代中，首先生成候选序列，然后扫 描序列数据库计算候选序列的支持度以确定频繁序列。 ( 1 ) 候选序列的生成 本阶段包括连接阶段和修剪阶段： 连接阶段，由频繁妒1 序列碌，生成候选是序列q 。对玩，中的两个序列j ? 和 印，如果分别删除s ，的第一个项和却中的