（计算机应用技术专业论文）基于约束的序列模式挖掘算法的研究.pdf

摘要 摘要 现有的序列模式挖掘算法能有效地在大型数据库中挖掘出完整的序列 模式集。然而，随着应用领域越来越细化，用户对挖掘出来的序列模式提 出了更高的要求。因此，将用户的要求或兴趣转化成一种或多种约束，来 限定挖掘的序列模式是序列模式挖掘领域内的一个研究重点。本文针对这 些问题，将研究重点放在基于约束的序列模式挖掘算法的研究上，这些研 究问题在超市中顾客购买模式、网站访问页面的序列模式、电信告警序列 模式和d n a 模式等中有重要的意义。 本文首先提出了一种基于规则表达式约束的增量式序列模式挖掘算 法。此算法用规则表达式来表示用户的要求，然后把规则表示式约束有机 融合到增量挖掘过程中，采用三种优化策略优化挖掘过程，以减少所消耗 的时间。在动态数据库中挖掘约束序列模式时，此算法的性能明显优于 f a s t u p 算法。 其次，提出了当算法参数发生变化时序列模式的增量式更新算法。该 算法基于格频繁模式树的结构，将前次挖掘得到的候选序列模式及其支持 度的信息和索引集映射表都保存在格频繁模式树中，以便下次挖掘时使用， 缩小了模式搜索空间，降低了模式挖掘的时间。在最小支持度闽值逐渐变 小时，该算法的性能明显优于m e m i s p 算法。 最后，提出了一种基于时间粒度的周期约束序列模式挖掘算法。该算 法采用日历中的时间概念作为周期约束中时间戳的表示方法，描述现实世 界中的时间概念，通过构建h p c s b ，采用两种候选序列生成方式，提高 了挖掘效率，其算法的性能优于p r e f i x s p a n 算法。 实验结果表明，本文提出的三种算法的挖掘性能明显优于现有的同类 算法，实现了预期的研究目标。 关键词数据挖掘；序列模式挖掘；约束挖掘；规则表达式约束；周期约束 燕山大学工学硕士学位论文 a b s t r a c t t h ec u r r e n ta l g o r i t h m sf o rm 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 ym i n et h e c 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 , a l o n gw i t l lt h e a p p l i c a t i o n sb e c o m i n g m o r ea n dm o r ec o m p l e x ，m o r ea n dm o r ec u s t o m e r sj u s t f o c u so nt h e i ri n t e r e s t e ds e q u e n t i a lp a t t e m si n s t e a do ft h ef r e q u e n tp a t t e r n s s o av e r y i m p o r t a n t t a s ki st h e s e q u e n t i a lp a t t e r n sm i n i n gc o n s i d e r i n gt h e c u s t o m e r s r e q u i r e m e n t sa sc o n s t r a i n t s t h ep a p e rh a sm a i n l yf o c u s e do nh o w t om i n es e q u e n t i a lp a t t e r n sw i t hc o n s t r a i n t s ，w h i c ha r ei m p o r t a n td a t am i n i n g p r o b l e m sw i t hb r o a da p p l i c a t i o n s ，i n c l u d i n gt h ec u s t o m e rp u r c h a s ep a t t e r n so r t h ep a g ea c c e s s i n gp a t t e r n so faw e bs i t e ，t h et e l e c o mw a r n i n gp a t t e r n sa n dt h e d n a s e q u e n t i a lp a t t e r n s f i r s t ，a na l g o r i t h mf o rm i n i n gs e q u e n t i a lp a t t e r n sw i t hr e g u l a re x p r e s s i o n c o n s t r a i n t si sp r o p o s e d t h ea l g o r i t h ma d o p t sr e g u l a re x p r e s s i o nt od e n o t e c o n s t r a i n t so fu s e r sa n dt h e ns y n c r e t i z ei ti n t ot h ep r o c e s so fi n c r e m e n t a l m i n i n g t h ea l g o r i t h mu s e st h r e es t r a t e g i e s t o o p t i m i z em i n i n gp r o c e s s ，i n o r d e rt od e c r e a s et 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 ef a s t u p a l g o r i t h mf o rm i n i n gs e q u e n t i a lp a t t e m si nd y n a m i cd 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 et h ea l g o r i t h m ，b a s e d o nt h es t r u c t u r eo fl a t t i c e f r e q u e n t p a t t e r nt r e e ( l f p t r e e ) ，s t o r e s t h e s e q u e n t i a lp a t t e n s a n dt h e i r s u p p o r t d i s c o v e r e dd u r i n gp r i o rm i n i n gp r o c e s s e di nl f p - t r e ea n dt h ei n d e xs e tm a p p e d t a b l e ( i s m t ) f o rf u r t h e rq u e r i 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 et 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 t 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 d g 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 e st h em e m i s pa l g o r i t h ms i g n i f i c a n t l y i i a b s t r a c t f i n a l l y , a ne f f e c t i v ea p p r o a c hf o rm i n i n gp e r i o d i cc o n s t r a i n ts e q u e n t i a l p a t t e r ni sp r o p o s e dt h ea l g o r i t h ma d o p t sg r a n u l a r i t i e s b a s e dp e r i o d i ct i m e c o n s t r a i n tt od e s c r i b er e a l l i f ep e r i o d i ct i m ec o n c e p t s as i m p l ea n dn o v e l h y p e r - l i k e dd a t as t r u c t u r e ，h p c s b ，i sd e f i n e d ，a n da l s ou s e st w om e t h o d st o g e n e r a t e c a n d i d a t e s e q u e n c e s ，i n o r d e rt o i m p r o v e t h e e f f i c i e n c y t h e p c s m i n ea l g o r i t h mo u t p e r f o r m e st h ep r e f i x s p a na 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 w 1 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 m a 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 ；c o n s t r a i n t sm i n i n g ；r e g u l a re x p r e s s i o nc o n s t r a i n t ；p e r i o d i cc o n s t r a i n t i 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于约束的序列模式挖掘 算法的研究，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进 行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人 已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集 体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字：索4 衾贿日期：加塔年，f 月巧目 燕山大学硕士学位论文使用授权书 基于约束的序列模式挖掘算法的研究系本人在燕山大学攻读硕士学 位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所 有，本人如需发布将署名燕山大学为第一完成单位及相关人员。本人完全了 解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送 交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学， 可以采用影印、缩印或其它复制手段保存论文，可以公布论文的全部或部分 内容。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密囤。 ( 请在以上相应方框内打“4 ”) 作者签名： 宗饺妇 日期：硼绰月掰日 导师签名：日期：棚g 年口月均日 第1 章绪论 第1 章绪论 近年来，随着信息技术的发展，许多领域积累了大量的数据。这些数 据繁杂无序，但又蕴藏了许多具有重大应用价值的知识和信息。因此，人 们迫切需要开发出有效的技术和工具，以支持从海量数据中自动地抽取出 有价值的知识和信息。数据挖掘( d a t am i n i n g ) 就是为了满足这一需求产生 并发展起来的，特别是其中的序列模式挖掘( s e q u e n t i f lp a a e mm i n i n g ) ，由 于其具有广泛的应用，已经成为数据挖掘中的研究热点之一。 1 1 序列模式挖掘技术 序列模式挖掘即从序列数据库中发现频繁子序列以作为模式，它是指 挖掘基于时间或者其它顺序出现频率高的模式，是一类非常重要的数据挖 掘问题i l j 。 1 1 1 序列模式的产生 数据挖掘中一个重要的应用是关联规则的发现。关联规则发现是在数 据库中寻找数据对象间的关联模式，例如，“在购买面包和黄油的顾客中， 9 0 的人同时也购买了牛奶。”就是一种关联模式。关联模式发现早期主要 用于零售业交易数据分析，以进行物品更合理的摆放，最终提高销售量。 因此，该方法有时也直接称为“货篮分析”。 序列模式是从关联规则中演变而来，序列模式发现是在数据库中寻找 基于一段时间区间的关联模式，例如，“在某一时间购买个人电脑的所有顾 客中，6 0 会在3 个月内购买应用软件。”就是一序列模式。序列模式同关 联模式非常相似，区别在于序列模式表述的是基于时间的关系，而不是关 于数据对象间的关系。 在实际应用中，多数数据集中的数据都带有时间特征，这类数据称为 燕山大学工学硕士学位论文 时态数据( t e m p o r a ld a t a ) i “，例如，某顾客在超市内某时间段内购买商品的 序列、天气数据和生产数据等。 序列模式挖掘最初是由于在零售业中的应用而发展起来的。现在，序 列模式已经应用到了科研和商用的其他许多领域。例如，在医疗领域，一 个病人每看一次病，他的症状就可以组成一次事务，而这个病人的所有看 病记录( 即所有事务) 就可以形成一个“症状序列”，从所有病人的症状序列 中挖掘出一个模式，这个模式将会帮助医生诊断这些症状预示着何种疾病。 序列模式挖掘是数据挖掘中一个重要的、富有挑战性的研究课题，在 实际中具有广泛的应用，包括顾客购物模式分析和互连网访问模式分析， 以及序列分析或者其它与时间相关的处理过程分析，例如，科学实验、自 然灾难事件、疾病防治、d n a 序列、股票序列的分析等p j 。 1 1 2 序列模式挖掘的国内外研究现状 序列模式挖掘【4 】的概念首先是由r a g r a w a l 等人在1 9 9 5 年对超市购物 篮数据的分析提出的，此后人们不断地研究和改进在时间序列数据库中挖 掘序列模式和其他频繁模式的算法。现有的序列模式挖掘算法主要分为两 类。第一类是基于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 特性【5 】 的算法。a p r i o r i 特性首先应用在关联规则挖掘中，其基本思想是频繁模式 的子序列也一定是频繁模式。基于a p r i 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 算法 4 1 、g s p 算法 6 1 、p s p 算法【7 1 等；有 采用垂直数据格式( v e r t i c a ld a t af o r m a t ) 的算法，如s p a d e 算澍引、s p a m 算法网、l a p i n s p a m 算法【1 0 1 等。第二类是j h a n 等人提出的基于模式增 长( p a t t e m g r o w t h ) 策略的算法，如f r e e s p a n 算法【l l 】、p r e f i x s p a n 算澍1 2 1 、 n s e 算法【”l 、l a p i n 算法【14 1 、i - s p a m 算法等。 另外，c a n t u n e s 等人提出了s p a r s e 算法【1 6 1 ，该算法的主要思想是 将候选序列的产生和在投影数据库空间搜索结合起来，每一步在产生出频 繁元素后，通过增长长度寻找模式。 以上这些算法都是在静态的序列数据库中挖掘所有的序列模式，它们 2 第1 章绪论 都属于一般的序列模式挖掘算法。但是，由于一般的大型数据库都是随着 时间的变化而不断更新的，当数据库发生变化之后，原先挖掘的一部分序 列模式可能不再满足最小支持度，同时还可能有新的序列模式出现，如果 使用上述算法，就必须在更新后的序列数据库中重新进行挖掘。在处理具 有海量数据的大型数据库时，对整个数据库重新执行一般的序列模式挖掘 算法显然是低效的。在这种情况下，一系列增量式序列模式挖掘算法被提 出，其基本思想都是尽可能地利用已发现序列模式的信息来发现新数据库 中的序列模式，从而提高模式挖掘的效率。 m a s s e g l i a 等人提出了用于序列模式增量式更新的i s e 算法i l ”，该算法 利用已有对原始数据库的挖掘结果来产生候选项目集，减少了候选项目集 的规模。但没有降低对整个数据库的扫描次数，算法的i o 消耗仍然很大。 周斌等人提出了在数据库更新的情况下的序列模式增量式挖掘算法 i m s p 1 8 】，其主要思想是利用序列的c t i d 表来加速挖掘过程。但该方法要 求预知前次挖掘的每个序列模式的c t i d 表，且在计算过程中将产生关于 每个候选序列的c t i d 表。当数据库规模很大时，对存储空间的消耗很大。 邹翔提出了一种称为f i m s 的序列模式增量式更新算法【”】，处理因数 据库更新而引起的序列模式维护问题。c l e e 等提出了s w f 算法 2 0 1 ，该算 法采用滑动窗口过滤技术来维护数据库的更新，并且把数据库分割成一些 小的数据库，用一个过滤阈值来处理候选项目的生成。 h c h e n g 等人提出了当向数据库中添加新的事务和数据序列时序列模 式的增量式更新i n c s p a n 算法【2 i 】，该算法采用缓冲率、频繁序列集及缓冲 半频繁序列集的技术，提高了序列模式增量挖掘的效率。 基于s p a d e 方法，一些学者提出用于数据库更新的序列模式的增量 式更新i s m 算法口2 】。该算法将所有频繁序列及其负边界组成一个序列网 格，当增量数据到达时，对增量部分进行扫描同时更新序列网格。然后， 根据序列网格和增量数据决定原始数据库中应当扫描的部分。 c a r s o n k a i s a n g 等人提出了当向原始数据库中添加新的数据事务、删 除旧的数据事务和对原始数据序列进行修改时的序列模式维护数据结构 c a n t r e e ( c a n o n i c a l o r d e rt r e e ) l ”】，该算法不需要调整、合并或者在维护过 燕山大学工学硕七学位论文 程中分割树的节点。 此外，当前国内外学者还广泛关注以下的研究方向。 ( 1 ) 约束( c o n s t r a i n e d ) 序列模式挖掘在很多序列模式挖掘任务中，用 户不需要找出数据库中所有可能存在的序列模式，而是加入一定的约束， 找出用户感兴趣的序列模式【2 抛7 1 。如a g r a w a l 等人将序列模式挖掘问题加 以泛化，引入了时间约束、滑动时间窗e 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 ) 序列模式挖掘当序列模式很长时，由于每一个序列 模式包含了组合数级的频繁子序列，挖掘所需的开销很大，然而在实际应 用经常需要挖掘特别长的模式，如d n a 序列。闭合序列模式挖掘f 2 2 1 研究 如何挖掘满足不存在与其具有相同支持度的超序列条件下的序列模式。 ( 3 ) 周期性( p e r i o d i c ) 模式挖掘 周期性模式挖掘 3 3 , 3 4 1 的目标是在时间 序列数据库中挖掘重复发生的模式，其中挖掘局部频繁发生模式具有较高 的应用价值，例如，自然灾难分析、天气预报分析等。 ( 4 ) 结构( s t r u c t u r e ) 模式挖掘结构模式挖掘【3 5 。8 】研究的是在结构或者 半结构数据集中挖掘频繁子结构，例如，树、有向循环图( d a g ) 和包含环 的普通图等。因为大多数人类活动和自然现象都包含了结构，例如，生物 结构、万维网的连接结构等，为结构模式挖掘提供了广阔的应用前景。 ( 5 1 多维( m u l t i d i m e n s i o n ) 序列模式挖掘在序列模式中融合感兴趣的 多维信息，在考虑与时间戳相关属性的同时，挖掘多维信息中感兴趣的模 式，将得到能提供给用户更丰富信息的多维序列模式p 9 啦l 。h p i n t o 等人提 出的u n i s e q 算法【4 3 】能有效地挖掘多维序列模式，多维序列模式挖掘是复 杂数据类型挖掘的一个前沿研究领域，有着极为广阔的应用前景。 综上所述，可以看出如何在大型序列数据库中挖掘更复杂的频繁序列 模式是有待于进一步研究的课题，涉及到如何在序列模式挖掘中加入各种 约束，以缩小搜索空问并得到用户感兴趣的模式等问题。 1 1 3 序列模式和关联规则的异同点 序列模式中的一些概念和算法与关联规则中的十分相似，但又比关联 4 第l 章绪论 规则更为复杂。 ( 1 ) 相同点两者的挖掘对象都是事务数据库，都希望从事务数据库中 发现规律，从而知道管理者根据规律做出决策，将利益最大化。两者都是 以项为基本单位，项集的概念也是相同的。都有包含定理，都有支持率的 概念。挖掘的基本步骤相同，先根据最小支持度找出数据库中的所有频繁 序列( 或项目集合) ，接着在所有频繁序列( 或项目集合) 中产生序列模式( 关 联规则) 。序列模式的挖掘算法都是由关联规则挖掘的算法演变而来，比如 a p r i o r i a l l 是由a p r i o r i 演变而来，还有本文所研究的序列模式挖掘也是由 关联规则的增量式挖掘算法发展而来。 ( 2 ) 不同点关联规则挖掘的是顾客的某一次购物行为中的规律，而序 列模式挖掘的是顾客的多次购物行为中的规律，挖掘的结果是由若干项集 组成的序列；序列模式挖掘中定义了序列，序列是若干项集的有序集合， 关联规则中没有“序列”的概念；关联规则中除了定义支持度用来衡量关 联规则整个数据集中的统计重要性外，还定义了置信度用来衡量关联规则 的可信程度，在序列模式中衡量序列模式是否是用户所需要的标准之一是 支持度，没有置信度的概念；挖掘任务的不同决定了挖掘算法的不同，由 于序列模式挖掘算法挖掘的是由若干项组成的序列，而关联规则挖掘算法 挖掘的仅仅只是项。所以，在数据库中搜索一个序列显然要比搜索一个项 集更加困难，在同样的条件下，候选序列的个数要比候选项目集的个数多 得多。从这两方面来说，序列模式挖掘算法比关联规则挖掘算法更为复杂。 1 2 基于约束的序列模式挖掘技术 约束序列模式挖掘是将用户的要求或兴趣转化成一种或多种约束，然 后用这些约束来限定挖掘出来的序列模式，已经成为序列模式挖掘领域中 的一个研究重点。 1 2 1基于约束的序列模式挖掘的产生 数据库中知识发现是当前涉及人工智能和数据库等学科的一个相当活 燕山大学工学硕士学位论文 跃的研究领域，序列模式的发现是其中一个重要的研究课题。随着序列模 式挖掘研究的深入，该技术已经日趋成熟并在越来越多的领域内被广泛应 用。例如，挖掘超市中顾客购买模式，挖掘网站访问页面的序列模式，挖 掘电信告警模式，挖掘d n a 模式等。然而，随着应用领域越来越细化， 很多新问题已经不能再用传统的序列模式挖掘算法解决了，用户对挖掘出 来的序列模式提出了更高的要求。因此，将用户的要求或兴趣转化成一种 或多种约束，来限定挖掘的序列模式已经成为序列模式挖掘领域中的一个 研究重点。 序列模式是非监督知识，因为在模式建立前结果是未知的，模式的产 生不受任何监督。缺乏焦点正是这种非监督知识挖掘的一个特征。序列模 式挖掘系统中存在着这样的问题：与用户的交互限制在较低的范围内：指 定抽取模式的最小支持度，然后采用一个序列模式挖掘算法，最终生成的 模式量很大，但对用户有用的却很少，这不但降低了挖掘的效率，也降低 了效力。所以在挖掘过程中也需要用户的控制，需要一种新颖的模式挖掘 解决方案。在挖掘过程中，用户可以通过约束来表达焦点和兴趣度。 用户经常希望在模式的结构上增加额外的约束来限制要发现的模式， 直观的处理办法是：在发现所有的频繁模式之后，用户通过后处理操作删 除不满足约束的模式。显然这种方法是低效的而且也不是令人满意的，因 为系统将大量的时间仍然花费在了发现频繁模式上。如果考虑将这些约束 推进到模式挖掘过程中，可以将模式的检索空间限制在用户感兴趣的范围， 从而可以提高性能。 1 2 2 常见约束及分类 随着序列模式挖掘的应用越来越复杂，为了更有效地挖掘出用户感兴 趣地序列模式，而不是仅仅局限在挖掘出所有频繁出现的大量的序列模式 上，人们针对各种应用，已经提出了各种各样的约束及挖掘的策略。从应 用的角度看，以下的七种约束包括了目前在应用中的大部分约束。 ( 1 ) 项约束( i t e mc o n s t r a i n t ) 单项或者项集必须出现或者不能出现在频 繁序列模式中。项约束可以表示为c i m ( a ) z ( 妒i ：1 - i l e n ( c t ) ，a i 】o v ) 或者 6 第1 章绪论 c t c l l l ( “) ；( 妒i ：1 _ i _ l e n ( a ) ，a i n v n u l l ) ，其v 是所有项的子集，妒 j ， v ，0 ，已，萑，1 ，1 2 。例如，对一w e b 服务器的日志进行挖掘，用 户可能只对关于访问在线图书馆站点的日志感兴趣，设b 是在线图书馆站 点集合，那么相应的项约束就是c b 。k s t 0 ”( 口) = v i ：1 5 0 。 ( 3 ) 超模式约束( s u p e r - p a t t e mc o n s t r a i n t ) 发现包含特定序列子模式的 序列模式。例如，市场分析员可能比较感兴趣一个顾客在购买了p c 之后， 又购买了d c 。这样的约束可以表示为c 。“a ) z a 。 ( 4 ) 聚集约束( a g g r e g a t ec o n s t r a i n t ) 在模式中对单项的某些属性进行 合计的约束。合计的函数可以是s u m 、a v g 、m a x 、m i n 、s t a n d a r d d e v i a t i o n 等。例如，超市分析员可能关心平均价格超过i o o y 的频繁序列模式。 ( 5 ) 规则表达式约束( r e g u l a re x p r e s s i o nc o n s t r a i n t ) 发现满足正则表 达式的频繁序列模式。一个序列模式满足该约束当且仅当该序列模式能够 被这一组规则表达式所对应的确定有限自动机所接受。例如，为了找出从 雅虎首页出发，经过一系列的网页最终到达h o t e l s i n n e w y o r k 页面的网页 访问流模式，可使用一个规则表达式t r a v e l ( n e wy o r k l n e wy o r kc i t y ) ( h o t - e l sa n dm o t e l s l o d i n g ) ，其中“i ”符号表示“或者”的意思。 ( 6 ) 持续时间约束( d u r a t i o nc o n s t r a i n t ) 在含有时间戳的序列中，序列 的每一项表示一个事件的发生。这种约束要求频繁序列模式的第一项和最 后一项之间的时间间隔大于或者小于一个给定的值。形式表示为d u r ( a ) 0 t ，其中0 = s 三) 。序列a 满足该约束当且仅当f 卢s d b ij1 鱼1 鱼l 。( a 芦l e n ( 卢) ，同时，a 【1 卢 i x ，a 【l e n ( a ) 】卢 i l 吲a ) 】，并且 卢【i l c g ( a ) i t e m 一卢【l l e g ( a ) 】t i m e 0a t i a n i n s u p 。 ( 7 ) 间隙约束( g a pc o n s t r a i n t ) 在含有时间戳的数据序列中，它要求在 序列数据库中频繁出现的模式两个相邻的元素之间满足大于或者小于给定 的g a p 。形式上可以表示为g a p ( a ) 0 a t ，其中0 ， ，a t 是一个给定的 正整数。数据序列a 满足g a p 约束当且仅当i 卢s d b ljl i l - - l i e n ( a 矗1 燕山大学工学硕士学位论文 ( p ) s t a 【l 】卢【i l ，口 1 e n ( a ) 】卢 i l e n ( a ) 】，对每一个l 时称为m i n g a p 约束。 就约束的属性来分，上述的各种约束可分为以下四类。 ( 1 ) 简洁性约束( s u c c i n c t n e s s ) 简洁约束可以用一种精确“公式 ( f o r m u l a ) ”来表示。根据该公式，可生成所有满足该约束的模式，无需在 挖掘过程中反复检查模式是否满足约束。 ( 2 ) 反单调性约束( a n t i - m o n o t o n y ) 设c a 表示反单调约束，那么如果 序列a 满足c n 意味着a 的所有非空子序列都满足该约束。 ( 3 ) 单调约束( m o n o t o n y ) 设c m 表示单调约束，那么如果序列“满足 c m 意味着a 所有的超市序列也满足该约束。 ( 4 ) 强约束( t o u g h ) 不属于上述任何一种约束的约束。一个满足强约束 的序列，其子序列和超市序列是否满足该约束都是不可确定的。 在这四种基于属性分类的约束中，简洁性约束时一种最容易处理的约 束，因为其可以直接通过选择谓词从序列数据库中将所有满足约束的序列 选择出来。反单调约束时一种具有a p r i o r i 性质的约束，容易与序列模式挖 掘过程结合，最常见的最小支持度约束就是一种反单调约束，即一个序列 若满足最小支持度的约束，则该序列的所有的非空子序列均满足最小支持 度的约束。在序列模式挖掘过程中，大多数算法均利用该约束的这一特性 进行非频繁单项的剪枝操作，这是在所有序列模式挖掘中都必需的约束。 相对而言，单调约束与强约束的处理起来较为困难，其难点在于挖掘过程 中，很难利用约束对搜索空间进行有效剪枝。相比反单调约束，单调约束 和强约束不能根据当前序列模式是否满足约束而确定是否有必要进行进一 步的挖掘，即难以有效的进行搜索空间的剪枝。例如，若序列模式p 不满 足反向单调约束c a ，则基于p 进行扩展的序列模式都不能满足c a ，因此 p 这一枝可以从搜索空间中剪除。而若序列模式p 不满足单调约束c m 或者 强约束c t ，基于p 进行扩展的序列模式有可能会满足c m 或者c t ，因此基 于p 的挖掘还要进行下去，若最终挖掘不到满足c m 或者c t 的模式，则所 有的挖掘工作将是徒劳无功的。这正是单调约束和强约束难以结合到序列 8 第1 章绪论 模式挖掘过程中，并且挖掘效率低下的主要原因。 1 2 _ 3 基于约束的序列模式挖掘算法 目前，基于约束的序列模式挖掘方法存在两种框架。第一种框架是基 于反单调性性质的约束序列模式挖掘框架。第二种框架基于前缀单调性性 质的p r e f i x g r o w t h 框架 4 4 1 。 反单调性也就是如果一个序列满足约束条件，那么它的所有子序列模 式也满足约束条件。基于反单调性性质的约束序列模式挖掘能够解决一些 约束条件，比如项目约束、长度约束等满足反单调性性质的约束，并且还 有其它一些约束条件能够被转化成满足反单调性的约束条件。但是，不能 解决不满足反单调性的约束条件，比如规则表达式约束等。针对这个问题， j i a n p e i 等人扩展了基于反单调性的约束序列模式挖掘框架，提出了一个新 的基于前缀单调性质的p r e f i x g r o w t h 框架。 g a r o f a l a k i s 等人提出了s p i r i t 算法1 4 5 j ，用规则表达式作为约束，并 且采用了约束放松策略过滤出那些不可能成为频繁的序列模式，获得了不 同程度的约束加强。h a m z a ，m e e r 等人提出了n e w s p i r i t 算法1 4 “，构造 了频繁模式树存储满足规则表达式的序列模式。p r e f i x g r o w t h 框架基于前 缀单调性性质，不仅把满足单调性和反单调性约束并且把不满足反单调性 的规则表达式约束推进到该算法中。 1 3 课题的主要研究内容及本文的结构 本文的主要包括以下的研究内容。 ( 1 ) 为了解决动态数据库中带约束的序列模式挖掘问题，提出一个有效 的算法r e ! n c u p ，该算法将基于p r e f i x - g r o w t h 特性，利用前次模式挖掘过 程中得到的信息，同时采用三种优化策略优化挖掘过程，减少挖掘时间， 提高挖掘效率。 ( 2 ) 为了解决最小支持度阈值参数而数据库不变的情况下的交互式序 列模式挖掘问题，提出一个有效的算法m i f s p m 。该算法间将利用格频繁 9 燕山大学工学硕士学位论文 模式树l f p t r e e 存储前次挖掘出来的结果，以层的形式读入内存，并采用 基于内存索引技术，只需遍历一次内存序列数据库，同时采用一种新的候 选序列集生成方法。 ( 3 ) 为了解决传统的序列模式挖掘算法不适合挖掘周期性序列模式的 问题，提出一个基于时间粒度的周期约束序列模式挖掘算法p c s m i n e ，该 算法将首先用日历中基本的时间粒度单位描述现实世界中的时间概念，给 出了基于时间粒度的周期约束的定义，并用该周期约束预处理事务交易序 列数据库以得到满足周期约束的序列数据库，通过构建h p c s b ，采用两 种候选序列生成方式的方法挖掘周期性序列模式，提高了挖掘效率。 本文总体上分为5 章，从第2 章开始具体布局如下。 第2 章将针对现存的带约束的序列模式挖掘算法不能解决动态数据库 中的约束序列模式挖掘问题，采用p r e f i x s p a n 技术，结合增量挖掘算法， 提出了一种挖掘算法，采用三种优化策略优化挖掘过程。 第3 章将针对改变最小支持度阈值而数据库不变的情况下的交互式序 列模式挖掘问题，提出了一种快速的、基于内存索引的挖掘算法m i f s p m 。 第4 章将针对传统的序列模式挖掘算法不适合挖掘周期性序列模式挖 掘的问题，给出了周期约束的问题定义，并提出了一种基于时间粒度的序 列模式挖掘算法。 第5 章将对于以前三章所提出的算法用j a v a 语言进行编程实现，介绍 实验所用环境的设置和数据集的来源，并给出实验结果及结果分析。 最后对本文提出的算法性能做出总结，并对未来的研究方向进行展望。 1 0 第2 章基于约束的增量式序列模式挖掘算法 第2 章基于约束的增量式序列模式挖掘算法 2 1引言 自从r a g r a w a l 等人在1 9 9 5 年提出序列模式后，序列模式挖掘在交易 数据库分析、w e b 访问日志、基因工程以及医学等领域内越来越具有广泛 的应用前景。 近年来，国外的一些专家学者在序列模式的增量式挖掘方面提出了许 多解决办法，有效地利用前次序列模式挖掘得到的结果，减少了挖掘时问 和扫描数据库的次数，提高了挖掘的效率。但是挖掘出的序列模式信息量 很大，并且往往不能满足用户的需求。约束条件在序列模式挖掘过程中日 益显得重要。传统的序列模式挖掘系统只是在固定的最小支持度阈值下挖 掘，挖掘过程缺少用户的参与。虽然已经有一些基于约束的序列模式挖掘 算法，但是这些挖掘算法只是解决了静态数据库中的约束挖掘问题，在动 态数据库中同样需要解决约束挖掘问题。 因此，基于约束的序列模式挖掘系统存在两方面的问题。一方面问题 是约束只限制在静态数据库中，动态数据库没有实现约束挖掘。另一方面 问题是现有的增量挖掘算法不能满足用户的需求。直观的解决方法是：用 增量挖掘算法发现所有的频繁模式之后，用户通过后处理操作删除不满足 约束的模式。显然这种方法是低效的而且也不是令人满意的，针对上述问 题，本文用规则表达式来表示用户的需求，然后把约束条件有机地融合到 增量挖掘过程中，采用三种优化策略优化挖掘过程，以减少挖掘所消耗的 时间，并且也能实现在动态数据库中挖掘出令用户满意的序列模式。 2 2 规则表达式概念 规则表达式可以作为约束说明工具，首先因为规则表达式提供了一简 燕山大学工学硕士学位论文 单自然的描述序列模式族的语法。并且，规则表达式有能力表达大范围的 有趣的而非琐碎的模式约束，这个观察可以通过在每一个串处理任务中充 分利用规则表达式来证明，利用r e s 与确定有限自动机等价的性能而把规 则表达式推进到数据挖掘的计算过程中，一系列s p i r i t 算法的主要的区 别因素是在挖掘过程中生成和剪枝候选模式是规则表达式约束被推进的 度。实验结果把规则表达式合并到挖掘计算过程中，能带来性能上的大幅 度提高，也验证了r e s 是用户聚焦在感兴趣的模式的用户级工具。 r 是规则表达式操作符如析取( i ) 、闭包( + ) 建立的序列元素上的规则表 达式。规则表达式与确定的有限自动机有同样的功效。所以给定一规则表 达式r ，能建立相应的确定有限自动机a r ，接受r 生成的语言。确定有限 自动机是一个有限状态机，包含定义的开始状态和一个或者多个状态以及 状态间的转换。 从状态b 到c 通过元素s i 可表示为b 量斗c 或者b j c ( s ) ，序列s 被 a r 接受，如果因为s 中元素能令序列从开始状态转换到可被接受的状态( 最 终状态1 。如一个规则表达式e = 1 ( 2 2 1 2 3 4 1 4 4 ) ，它的等价确定有限自动机如 图2 1 所示。 1 图2 - 1e 的确定有限自动机 f i g 2 - 1d e t e r m i n i s t i cf m i t ea u t o m a t o nf o re 定义3 1 ：序列s 对确定有限自动机a n 的状态b 是合法的，如果对s 中从b 状态开始的转换序列是确定的。 定义3 2 ：序列s 对确定有限自动机a r 的状态b 是有效的，如果s 对 b 是合法的，且从b 开始在输入s 的情况下转化路径的最后状态是a r 可接 受的状态。 说s 是有效的，如果s 对a r 的开始状态a 是有效的，等价地说s 是 a r 可接受的。 1 2 第2 章基于约束的增量式序列模式挖掘算法 设d b 为原始序列数据库，m i n s u p 为最小支持度阈值，d b 为新增的序 列数据库。u = d b + d b 为在d b 中添加新数据后的新的数据库。设d b 中的 频繁序列集合为u k f k ，d b 中满足约束条件的频繁的序列模式集合为u 山k ， 基于模式扩展的规则表达式为e 。d b 中满足约束条件的频繁序列模式集合 为u k g k ，u 中满足约束条件的频繁序列模式集合为u k 。 2 3 一般序列模式挖掘算法分析 现存的增量挖掘算法能够很好地解决数据库更新问题。i s m 算法是基 于s 队d e 方法的序列模式维护算法，将所有的频繁序列与其负边界组成 一个序列网格，并且采用网格搜索技术和简单的连接操作来挖掘所有序列 模式，适合于垂直数据库。但是，在处理具有海量数据的大型数据库时， 维护频繁序列的负边界将会导致极大的内存消耗，并且如果转化为一般的 事务数据库，则增加了挖掘时间和i o 开销。i u s 算法【4 7 j 通过反复利用初 始数据库中的频繁序列和负边界序列，将计算开销降到最小。为了控制负 边界序列所消耗的内存和时间，该算法定义了一个新的变量即负边界序列 最小支持度，只有那些支持度值在最小支持度值和负边界序列最小支持度 之间的序列才能进入负边界，并且采用了扩展前缀和后缀两种产生候选序 列的方法比i s m 算法考虑地更加周详。i n c s p 算法【4 卅为了有效的处理新事 务和新的顾客序列，采用序列合并技术，如果顾客序号和已存在的顾客序 号一样则把新增的事务添加到原始数据库中。但是采用了合并技术不可能 再重新运行原先的算法挖掘序列模式，所以对原先不频繁的后来变成频繁 的模式和新增的模式这两种情况分别计算支持度。但是它需要生成全部的 候选序列模式，再修剪掉那些不是频繁的序列，浪费了空间和时间资源。 上述算法只是解决了数据库的更新问题，没有考虑到用户交互问题， 不能满足用户的指定的需求。 g a r o f a l a k i s 等在序列模式挖掘中提出了把规则表达式作为约束并且构 建了一种s p i r i t 框架。该框架把规则表达式与确定性有限状态自动机等价 起来，并且应用了具有很好性能的放宽约束的办法过滤掉了那些不可能是 燕山大学