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

中国科学技术犬学硕士学位论文 摘要 摘要 数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd m a b a s e ，简称k d d ) 是当前涉及 人工智能和数据库等学科的一个相当活跃的研究领域，序列模式的发现是其中的 一个重要研究课题。随着对序列模式挖掘研究的深入，该技术已经目趋成熟并在 越来越多的领域中被广泛应用。例如：挖掘超市中顾客购买模式，挖掘网站访问 页面的序列模式，挖掘电信告警序列模式，挖掘d n a 模式等。然而，随着应用领 域越来越细化，很多新问题已经不能再用传统的序列模式挖掘方法解决了，用户 对挖掘出来的序列模式提出了更高的要求。因此，将用户的要求或兴趣转化成一 种或多种约束，来限定挖掘的序列模式已成为序列模式挖掘领域中的一个研究重 点。 本文针对上述的问题，将研究重点聚焦在基于约束的序列模式挖掘方法的研 究上。主要工作和特色如下： 1 ，针对基于约束的序列模式挖掘问题，在传统的序列模式挖掘方法基础上， 设计了一个适于不同约束类型的通用序列模式挖掘框架，并提出相应的单 项安全剪枝基本定理和单项安全剪枝松弛定理。在每轮模式生长的过程中， 利用该定理可对不满足该约束的扩展单项进行剪枝，以减小搜索空间，提 高挖掘效率。为使得配置挖掘策略更方便，该框架的逻辑部分利用c + + 模板 特性实现。 2 ，提出了一个针对单调约束的扩展单项剪技定理，并基于该定理为基于单调 约束的序歹b 模式挖掘设计了一种扩展单项剪枝策略。利用该策略，对每个 候选扩展单项进行合法性检查，剪除不能生成满足单调约束序列模式的扩 展单项，从而减d , y 搜索空间。和已有的e x a n m 、p r c f i x - g r o w t h 算法的比较 实验表明，该策略的其有更高的剪枝效率。 3 针对两种典型的强约束m a ) 【g a p 约束和a v ga g g m g a t c 约束，基于单项 安全剪枝松弛定理设计了相应的剪枝策略，并将其集成到通用序列模式挖 掘框架中，分别设计了基于m a x g a p 约束和a v ga g g r e g a t e 约束的序列模式 挖掘算法。与处理m a x g a p 约束的c c s m 算法的比较实验表明，本文算法 中固科学技术大学硕士学位论文 摘要 更有效，尤其是在较低支持度下的效果更明显。同时针对a v ga g g r e g a t e 约 束的实验数据也表明了剪枝策略是有效的。 关键词：序列模式挖掘，单调约束，强约束，剪枝策略 中国科学技术大学硕士学位论文a b s t r a c t a b s t r a c t k n o w l e d g ed i s c o v e r y i n d a t a b a s e ( k d d ) i sar a p i d l ye m e r g i n gr e s e a r c h f i e l d r e l e v a n tt oa r t i f i c i a l i n t e l l i g e n c ea n dd a t a b a s es y s t e m ，a n dd i s c o v e r yo fs e q u e n t i a l p a t t e r n si s a ni m p o r t a n tf i e l di nt h ek d dr e s e a r c h n o wt h et e c h n o l o g yh a sb e e n a p p l i e di nm o r e a n dm o r ed o m a i n s ，s u c h a s - m i n i n gt h ec u s t o m e r s p u r c h a s ep a t t e r n s ， t h ep a g e sa c c e s s i n gp a t t e r n so faw e b s 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 ed n a s e q u e n t i a lp a t t e r n s a l o n gw i t ht h ea p p l i c a t i o n sb e c o m i n gm o r ea n dm o r ec o m p l e x ， m a n yn e wp r o b l e m s c a nn o tb er e s o l v e db yt h et r a d i t i o n a ls e q u e n t i a lp a t t e r n sm i n i n g m e t h o d m o r ea n dm o r ec u s t o m e r sj u s tf 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 r n s i n s t e a do ft h ef r e q u e n tp a t t e r n s s oav e r yi m p o r t a n tt a s ki st h es e q u e n t i a lp a t t e r n s m i n i n gc o n s i d e r i n g t h e c u s t o m e r s r e q u i r e m e n t s a sc o n s t r a i n t s i nt h i sp a p e ro u rw o r kf o c u s e so nt h ec o n s t r a i n tb a s e d s e q u e n t i a lp a t t e r n sm i n i n g i t m a i n l yi n c t u d e s3p o i n t s 铋f o l l o w s 1 a i m i n ga tt h ep r o b l e mo fm i n i n gc o n s t r a i n tb a s e ds e q u e n t i a lp a t t e r n ，w e d e s i g n an e wf r a m e w o r kn a m e dc b p s a i g mt oh a n d l ev a r i o u sk i n d so f c o n s t r a i n t s w ea l s op r o v i d et h ei t e m ss a f e l yp r u n i n gt h e o r e ma n dt h ei t e m s s a f e & p r u n i n g r e l a x a t i o nt h e o r e mt or e d u c et h es e a r c hs p a c et oi m p r o v et h e m i n i n ge f f i c i e n c y i no r d e rt oc o n f i g u r et h em i n i n gs t r a t e g ym o r ef l e x i b l e ，w e u s ec 十+ t e m p l a t et oi m p l e m e n tt h ef r a m e w o r k 2 i nt h i sp a p e rw e p r o v i d eat h e o r e mt op r u n et h ee x t e n d e di t e m si nm o n o t o n y c o n s t r a i n tb a s e d s e q u e n t i a lp a t t e r n sm i n i n g a n d d e s i g n ac o r r e s p o n d i n g p r u n i n gs t r a t e g y w eu s et h es t r a t e g yt oc h e e ke a c hp o t e n t i a le x t e n d e di t e r n a n d p r u n e a l lt h ei t e m st h a tc a nn o t g e n e r a t e a p a t t e r ns a t i s f y i n g t h e m o n o t o n yc o n s t r a i n t c o m p a r i n gw i t he x a n t e a n d p r e f i x - g r o w t ha l g o r i t h m ， w ef i n dt h i ss t r a t e g yi sm o r ee r i e c t i v e 3 t oh a n d l et w ok i n d so f t y p i c a lt o u g hc o n s t r a i n t ：m a x g a pa n da v ga g g r e g a t e c o n s t r a i n t ，w ed e s i g nc o r r e s p o n d i n gs t r a t e g i e s b a s e do nt h ei t e n m5 咖f y 中国科学技术大学硕士学位论文a b s t t a c t p r u n i n gr e l a x a t i o nt h e o r e m a n di n t e g r a t et h e mi n t oc b p s a l g m t ob u i l dt h e 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 r n sw i t hm a x g a pc o n s t r a i n ta n da v g a g g r e g a t ec o n s t r a i n tr e s p e c t i v e l y c o m p a r i n gw i t hc c s ma l g o r i t h mw h i c h d e a l sw i t h m a x g a pc o n s t r a i n t w ef i n do u r a l g o r i t h m i sm o r ee f f e c t i v e ， e s p e c i a l l yi nt h ec o n d i t i o no fl o wm i n i m u ms u p p o r t o nt h eo t h e rh a n d ，w e c a l lc o n c l u d ef r o mt h e e x p e r i m e n t r e s u l t st h a tt h e p r u n i n gs t r a t e g y f o r p r o c e s s i n ga v ga g g r e g a t ec o n s t r a i n ti sa ne f f e c t i v es t r a t e g y k e y w o r d ：s e q u e n t i a lp a t t e r n sm i n i n g ，m o n o t o n yc o n s t r a i n t ，t o u g hc o n s t r a i n t ，p r u n i n g s t r a t e g y 中国科学技术人学颂：j ：学位论义结论 第一章绪论 随着数据库技术的不断发展及数据库管理系统的广泛应用数据库中存储的 数据量急刷增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些信息 从数据库中抽取出来，将为应用部门创造很多潜在的利润，数据挖掘技术就是基 于这样的商业角度开发出来的。 确切地说，数据挖掘( d a t am i n jn 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 ) ，是指从大型数据库或数据仓库中提取隐含的、未 知的、非平凡的及有潜在应用价值的信息或模式。它是数据库研究中的一个很有 应用价值的新领域，融合了数据库、人工智能、机器学习、统计学等多个领域的 理论和技术。数据挖掘所包含的范畴很广，而在数据挖掘中，关联规则是其中非 常重要的一种挖掘模式。 1 9 9 3 年，美国i b ma l m a d e n 实验中心的r a g r a w a l 和t i m i e l i r i s k j 等人论述了 挖掘关联规则的问题 1 ，并且提出了第一个关联规则的挖掘算法：a i s 算法 2 。 随后不久，人们发现了项目集的支持度和关联规则可信度属性的单调性，该算法 被改进并重新命名为a p r i o r i 算法 3 、4 。然而a p r i o r i 算法的最大的瓶颈就是多 遍扫描数据库带来的代价，后来人们对此问题进行了大量的研究，提出了很多解 决方法以减少对数据库的扫描次数，如：将候选数据集散列化 5 ，利用采样技 术 6 ，利用划分技术 7 动态项目集计数 8 平行计算 9 等。考虑到a p r i o v i 算法是一个宽度优先的算法，z a k i 从另一方面设计了一种深度优先的算法： e c l a t 1 0 、1 1 。随后，韩嘉巍等人提出了著名的f p - g r o w t h 算法 1 2 ，该方法利 用短模式的局部频繁单项生成长模式而不需要产生候选项目集。 关联规则最初应用于交易数据库中发现项目( i t e m s ) 之间的潜在关系。 r a g r a w a l 等将这类关联规则称之为“布尔关联规则”( b o o i e a na s s o e i a t i o n r u l e s ) 。在1 9 9 6 年，r s r i k a m 和a g r a w a l 又提出了挖掘“多值关联规则” ( q u a n t it a t i v ea s s o c i a t i o nr u l e s ) 的算法 1 3 ，用来处理数据库中包含数量属 性和类别属性的情况。对于数据库中的数量属性，r ，j m i l l e r 和y y a n g 在1 9 9 7 年提出将数量属性聚类，利用类与类之间的距离去产生关联规则 1 4 。在数据挖 掘研究领域，对于关联分析的研究开展的比较深入，人们提出了多种关联规则的 中田科学技术大学硕i ! 学位论文绪论 挖掘算法，如a p r i o r i 、s t e m 、a i s 、d t t p 等算法。关联分析的目的是挖掘隐藏在 数据间的相互关系，它能发现数据库中形如“9 0 的顾客在一次购买活动中购买 商品a 的同时购买商品b ”之类的知识。但是有一种在实际分析中相当有用的关联 规则，这些算法并不能将其挖掘出来。 例如，直接运用上面提到的技术无法发现以下规律： 某种股票换手率增长1 5 ，其股票收盘价可能随后上涨1 0 ； 某商品打折5 可以使其总销售额上升5 1 0 ； 病人在做治疗后，5 天内自血球数提高2 是由某药剂的剂量增加1 0 0 6 造成 的： 某只股票收盘价相对于时间出现的某种趋势变化； 对于上述关系，使用经典关联规则没有办法得到相应的规律。而实际情况下， 这种规律经常是人们所关心的，而且经常成为决策者辅助决策的重要理论依据针 对于上述问题的存在，经常要考虑到以序列模式数据挖掘作为解决方案。 1 1 序列模式挖掘 序列模式挖掘与普通的关联规则挖掘非常相似，但是可以解决关联规则所不 能解决的问题。关联规则主要是针对事务数据库进行挖掘操作的，以便找到事务 数据库中属性之间的关联性：而序列模式挖掘的数据源则是序列数据库。序列数 据库是指由有序事件序列组成的数据库，可以有时间标记，也可以没有。序列模 式就是指在序列数据库中出现的次数大于等于一个用户给定阈值的序列，该序列 可以是数据库中原有的序列，也可以是原序列数据库中某些序列的子序列：其中 子序列的概念将于第二章2 1 节提出。序列模式挖掘的任务就是从序列数据库中 挖掘出所有序列模式。 序列模式挖掘中的很多算法都继承自基本的关联规则挖掘算法。现有的序列 模式挖掘的算法大体上可以分为两类：“a p r i o r i l i k e ”( 类a p r i o r i 算法) 和 “f p g r o w t h 一1 i k e ”( 基于划分和模式生长的算法) 2 9 。最早的三个 “a p r i o r i 一1 i k e ”算法( a p r i o r i a l l 、a p r i o r i s o m e 、d y n a m i c s o m e ) 是由a g r a w a 提出的 1 5 。随后一个著名的“a p r i o r i 一1 i k e ”算法g s p 4 被提出来。g s p 算法 考虑时间方面的约束和分类学的知识。就像在关联规则的挖掘中一样，基于 中田科学技术人学螂! j ：学位论文 绪论 a p t io fi 的方法缺陷仍然表现在多遍扫描数据库和生成大量候选序列等代价较高 的操作上。因此，基于划分和模式生长的算法，如：f r e e s p a n 1 6 署l ：l p r e f jx s p a n 1 7 算法被提出来。f r e e s p a n 基于当前的频繁模式集合中的每个模式，将原序列数据 库划分为系列小的数据库，再在这些小数据库中分别挖掘其中的序列模式。 p r e f ix s p a n 算法通过使用基于前缀的投影划分方法改进了f r e e s p a n 算法。 1 2 序列模式挖掘的应用 在实际应用中，多数数据集中的数据都带有时间特征，这类数据被称为时 态数据( t e m p o r a ld a t a ) 。例如某顾客在超市内某个时间段内购买商品的序列。 时态数据挖掘的一个问题是从交易数据库中挖掘序列模式。和关联规则问题 样，它也是源于对货篮数据的分析。序歹1 j 模式挖掘的目标是从交易数据库中发现 客户购买行为中的序列模式，从而实现对顾客未来行为的预期。序列模式挖掘算 法通常需要将交易数据库按顾客标识重构，每个顾客的事务数据按购买时间组成 一个事务序列。这样由整个数据库中的数据集生成了一个含有多个长短不的序 列的集合。然后从多个序列中间发现相同的子序列。满足一定支持度的子序列便 认为是要发现的序列模式。举例来说，顾客租借录像带的一个典型的顺序是先租 “星球大战”，然后是“帝国反击战”，再是“杰达武士归来”( 这三部影片是 以故事发生的时闻先后而情节连续的 。值得注意的是租借这三部电影的行为并 不定需要是连续的。在任意两部之间，可以租借任何别的电影，仍然满足这个 序列模式，并且扩展一下，序列模式的元素也可以不只是一个物品( 如一部电影) ， 它也可以是一个物品的集合。 目前，序列模式挖掘已经应用于多个领域。例如：通过挖掘交易数据分析 客户的购买行为模式：通过挖掘股票交易的历史数据可以预测股票的走势：通过 挖掘网站中各个页面的访问序列模式，可以提高网页页面预取的命中率和w e b 服务器缓存的效率；通过挖掘电信告警序列模式可以分析出根源告警，以便更有 效地排除故障 2 5 1 。其他方面还包括：科学实验数据序列的挖掘、疾病诊断、自 然灾害预报、d n a 序列分析等。 然而，随着原始数据规模越来越庞大，应用划分越来越细化，用户对序列模 式挖掘的需求将不仅停留在找到所有的频繁序列模式这一问题上。因为在海量序 中国科学技术大学硕士学位论文结论 列数据中挖掘频繁模式，往往会得到大量的频繁序列模式，而对于细化后的应用， 并不是所有的序列模式都是有用的。同时，将如此大量的频繁模式作为结果反馈 给用户，也会给用户的应用带来巨大的负担。如何针对用户的兴趣，仅挖掘出用 户感兴趣的序列模式已成为目前序列模式挖掘领域中一个研究的热点。基于此， 研究人员扩展了目前的序列模式挖掘的方法，将用户的兴趣作为约束和序列模式 挖掘相结合，提出了基于约束的序列模式挖掘的概念。 3 基于约束的序列模式挖掘 基于约束的序列模式挖掘为用户提供了挖掘定制模式的方法。如上所述， 用户在应用中并不是对所有挖掘出来的序列模式都感兴趣，用户可能仅对其中 的满足某些条件的模式感兴趣。这些条件可以被转化成约束，和序列模式挖掘 的过程相结合，使得最终挖掘出的结果恰是用户感兴趣的模式。 其中最简单的一种结合就是先通过传统的序列模式挖掘方法挖掘出所有的 频繁序列模式，然后再对这些模式，按照用户定制的约束进行过滤，最终获得 所有满足用户要求的序列模式。然而，在海量数据中进行挖掘本身就是一种相 当耗时的操作，挖掘完毕后若再要进行第二轮的过滤，可能导致最终的挖掘效 率无法满足实际应用的需求。而且在第一轮的传统挖掘过程中，会产生大量不 满足用户兴趣约束的序列模式，挖掘这些序列模式往往是劳而无功的。如何将 用户的约束和传统的序列模式挖掘方法融合，在挖掘频繁序列模式的过程中， 利用约束提高挖掘的效率已经成为研究基于约束的序列模式挖掘算法的重点。 目前，各种约束按照不同的标准被划分成不同的类型，如单调约束、反向 单调约束、强约束等。同时，通过研究，也出现了大量的针对这些约束的高效 的挖掘算法，如：p r e f i x g r o w t h 1 8 ，e x a n k 1 9 ，2 9 。c s p a d e 2 0 ，c c s m 2 1 ， s p i r i t 3 0 等。 1 4 论文的组织结构 本文研究了基于约束的序列模式挖掘的问题。其中主要包括序列模式的基本 模型和扩展模型；序列模式挖掘的算法和基于约束的挖掘算法等方面的研究。 本文由六章组成，具体组织方式如下： 中国科学技术大学硕士学位论文 绪论 第一章是序言部分。主要概述了k d d 的背景，以及出此引出序列模式挖掘 的概念；提出了序列模式挖掘的应用领域；并进一步阐述了现阶段序列模式挖掘 的一个重要的研究方向基于约束的序列模式挖掘方法的研究。 第二章给出了序列模式挖掘相关概念和工作的介绍，包括传统序列模式挖掘 中的相关概念以及基于约束的序列模式挖掘中，对约束的分类和一些已经提出的 经典的约束模型。同时给出了序列模式挖掘的几个常见算法，包括：g s p 算法、 s p a d e 算法和p r e f i x s p a n 算法。 第三章对基于约束的序列模式挖掘进行了进一步的讨论，提出了如何将约束 结合到序列模式挖掘过程之中的方案。给出了单项安全剪枝基本定理和单项安全 剪枝松弛定理。并基于此，利用c + + 的模板特性，实现了一个通用的基于约束的 序列模式挖掘框架。 第四章给出了对单调约束的挖掘策略。首先介绍了已有的两个处理单调约束 的序列模式挖掘算法：e x a n t e 和p r e f i x - g r o w t h ，并分析了算法的不足之处。随 后给出了基于单项安全剪枝松弛定理进行剪枝的策略，并将该策略结合到框架之 中，生成处理单调约束的序列模式挖掘算法。最后对本文算法和e x a n t e 算法以 及p r e f i x g r o w t h 算法进行了比较分析。 第五章针对更加难以处理的约束强约束，进行了讨论。主要针对两种典 型的强约束：m a x g a p 约束和a v ga g g r e g a t e 约束。本文设计了不同的剪枝策略和 算法框架结合，从而生成了不同的处理m a x g a p 约束及a v ga g g r e g a t e 约束的算法， 并和已有的处理m a x g a p 约束的算法c c s m 作了比较实验。 最后一章是对全文的总结，对本文的研究工作做了简要地概述，并提出了进 一步研究的方向。 中国科学技术大学硕士学位论文背景和相关t 作 第二章背景和相关工作 这一章我们将简要的介绍一些序列模式挖掘中涉及的背景知识、序列模式挖 掘中涉及的约束类型和一些传统的序列模式挖掘算法。通过对背景知识的介绍， 我们将明确序列模式挖掘的依据。而传统的序列模式挖掘算法亦为本文进一步研 究基于约束的序列模式挖掘算法提供了基础。 2 1 背景知识 2 1 1 序列模式挖掘中的相关概念 序列模式挖掘的目的是在序列数据库中挖掘频繁序列模式。为了下文中论述 的方便，本节给出序列模式挖掘中所涉及的相关概念和定义。 定义1 ：序列数据库所谓序列数据库就是由多条序列记录组成的数据库，是一 系列二元组 的集合，其中s i d 表示序列的i d ，而s 表示相应的序列本身。 如表2 一l 所示的就是一个序列数据库。 表2 - 1 序列数据库 s e q u e n c ei d s e q u e n c e 1 0 a ， a ，b ，c ) - ， ，d ， ) 2 0 ，c ， ， 3 0 ， ， d ，p ，c ，b ) 4 0 e ，g ， a ，p ，c ，b ，c ) 其中s e q u e n c ei d 栏中的1 0 ，2 0 ，3 0 。4 0 表示的就是 二元组中的s i d ，而 s e q u e n c e 栏中的内容则表示相应的序列，相当于 二元组中的s 。 定义2 ： 项全集，。序列数据库中的每个序列的最小构成单元是单项( i t e m ) ，项 全集l = i l ，i 2 i 3 i 。) 是一个字符集，其中每个项称之为单项，它包含了所有出现 在序列数据库中的单项。例如上述的序列数据库的项全集，= a ，b ，c ，d ，e ，cg ) 。 定义3 ：项集。项集又称为元素( e l e m e n t ) 、事务( t r a n s a c t i o n ) 等。项集( i t e m s e t ) x 是一个非空的集合。并且x ，。项集的大小( 表示为闭) 为它所包含的项的数 6 中国科学技术大学硕士学位论文背景和相关工作 目。为了讨论的方便，通常将项集中的各个元素按照一定的次序排列，例如上述 的例子中，每个项集中的单项就是按照字典需进行排列的。即项集 和项 集 是等价的。 定义4 ；序列。序列( s e q u e n c e ) s 是一个有序的项集。可表示为s = s i ，s 2 ，s 沁，s 。 ， 其中的每个s j 都是一个元素。序列的长度就是该序列含有元素的个数，一个长度 为f 的序列称为- s e q u e n c e ( 1 - 序列) 。在每个元素中可以包含一个或者多个单项。 如果一个元素仅含有一个单项，则无需使用“ ”和“，”将其括起来，反之， 需要使用“ ”来界定一个元素。例如表2 1 中，s i d = l o 的序列由5 个元素组成，分别是：a ， ， ，d ，和 c ，p 。其中：a 和d 就是只包 含一个单项的元素。 定义5 ：子序列( s u b s e q u e n c e ) 和超序列( s u p e r s e q u e n e e ) 。如果序列o r , = a l ，a 2 ， a 。 序列1 3 = b l ，b 2 ，b 。) ，存在一系列的整数1 - j i j 2 j 。 m i n _ s u p p ，则序列n 为频繁序列模式，简称序列 模式。例如在表2 1 中，若最小支持度设为5 0 ，即一个序列出现的次数必须不 小于j s l * 5 0 = 2 ，( 其中1 研表示序列数据库的大小，本例中阎= 4 ) 才能称其为频 繁序列模式。如序列 ，d 就是一个频繁序列模式，分别出现在原序列数据 库中的第一和第三个序列中。 定义7 ：前缀、后缀和投影假设序列= a i a 2 ，a 1 1 ) ，序列鼻= b j ，b 2 ，b 。) ( msn ) ，存在一组整数ls j is j 2s s j m s n ，使得( 1 ) b i = a j i ( 1 曼j m ) ： ( 2 ) b 。互a i l i - 则称序列卢是序列a 的前缀。如果序列芦是序列a 的子序列，而序 列a 也是序列乜的子序列，当且仅当( 1 ) 啥有b 前缀，( 2 ) 不存在a 的超序列d ”， 使得8 ”也含有前缀，同时也是伐的子序列。这时n 称为序列月在序列a 上的 中国科学技术大学硕士学位论文 背景和相关工作 投影。假设序列a = e l ，e 2 ，e 。) 是前缀口= e l ，e 2 ，e m 1 ，e 。 ( m 茎n ) 在序列 a 上的投影，则称序列y = e 。：p 。， 为投影序列a 中相对于前缀卢的后 缀，可表示为：y = a 卢。其中e 。”= ( p 。一e 。) 。例如序列s i = a ， 就是 序列s = a ， ， ，d ， c ，p ) 的一个前缀，而序列5 2 = a ， 则不是 s 的前缀。s 2 在序列s 上的投影为s 3 = a ， ， ，d ， 。序列 ，d ， c ，p 则是投影序列s 3 中相对于l j 缀s 2 的后缀。 2 1 2 序列模式挖掘中常见的约束及分类 随着序列模式挖掘的应用越来越复杂，为了更有效地挖掘出用户感兴趣的序 列模式，而不是仅仅局限在挖掘出所有频繁出现的大量的序列模式上，人们针对 各种应用，已经提出了各种各样的约束及挖掘的策略。从应用的角度看，以下的 七种约束包括了目前在应用中的大部分约束 1 8 】。 约束一：i t e mc o n s t n i n 卜一单项或者项集必须出现或者不能出现在频繁序 列模式中。可表示为c i k 。( d ) s ( 中i ：l i l e n ( 叻，a i 】ov ) 或者c i i c m ( ) = ( 叫： l isl e n ( a ) ，a i 】f q v n u l l ) ，其中v 是所有项的子集，审 j ，v ) ，0 量，e ，芒，r ，一；) s 例如对一个w e b 服务器的日志进行挖掘，用户可能 只对关于访问在线图书馆站点的日志感兴趣，设b 是在线图书馆站点集合，那 么相应的项约束就是c b 0 0 k 。t o 。( q ) ；( v i ：11 is l e n ( a ) ，a 【i 】b ) 。 约束二：l e n g t hc o n s t r a i n 卜一要求频繁模式序列的长度大于或者小于某个 值。例如用户可能需要在生物基因链中挖掘长模式( 1 e n g t h 5 0 ) 。其约束可以表 示为c i 。( 吣- ：( 1 e n ( a ) 5 0 ) 。 约束三：s u p e r - p a t t e r nc o n s t r a i n t _ 一发现包含特定序列为子模式的序列模 式。例如，市场分析员可能比较感兴趣一个顾客在购买了p c 之后，又购买了 d c 。这样的约束可以表示为c p a t ( a ) z 旺。 约束四：a g g r e g a t ec o n s t 腿i n 卜一在模式中对单项的某些属性进行合计的约 束。合计的函数可以是s u m ，a v g ，m a x ，m i n ，s t a n d a r dd e v i a t i o n 等。例如超市 分析员可能关心平均价格超过1 0 0 ￥ 的频繁序列模式。 约束五：r e g u l a re x p r e s s i o nc o n s t 憎i n 卜一发现满足正则表达式的频繁序列 模式。一个序列模式满足该约束当且仅当该序列模式能够被这一组正则表达式所 8 中国科学技术人学硕士学位论文 背景和相关工作 对应的确定有限自动机所接受。例如，为了找出从雅虎首页出发，经过一系列的 网页最终到达h o t e l si nn e wy o r k 页面的网页访问流模式，可使用一个正则表达 式t r a v e l ( n e w y o r kin e wy o r k c i t y ) ( h o t e l sl h o t e l sa n dm o t e l sil o d g i n g ) ，其中“l ” 符号表示“或者”的意思。 约束六；d u r a t i o nc o n s t r a i n 卜一在含有时间戳的序列中，序列的每一项表示 一个事件的发生。这种约束要求频繁序列模式的第一项和最后一项之间的时间间 隔大于或者小于一个给定的值。形式化表示为：d u r ( a ) o a t ，其中0 = s ，) 。 序列a 满足该约束当且仅当j 卢s d bi jl i l i t e n ( a ) l e n ( 所，同时， a 1 】量p i t 】，a 1 e n ( a ) 】声 i l e 。似】，并且声 i l 。心) 】t i m e - p i l t i m e 0a t ) f 兰 m i n s u p p 。 约束七：g a p c o n s t r a i n t - 一在含有时间戳的序列中，它要求在序列数据库中 频繁出现的模式两个相邻的元素之间满足大于或者小于给定的g a p 。形式上可以 表示为：g a p ( a ) 0 a t ，其中0 佟，芝) ，a t 是一个给定的整数。序列吐满足g a p 约束当且仅当i 声s d b i jl l s l + i e n t a ) - l e n ( f 1 ) s t a 1 】卢 i l 】，a 1 e n ( a ) 三卢【i l c 咖d ，对每一个l m i n _ s u p p 。就g a p 约束而言，当0 = s 时，称为m a x g a p 约束。当0 = 芝 时称为m i n g a p 约束。 就约束的属性来分，上述的各种约束可分为以下四类： 简洁性约束( s u c c i n c t n e s s ) ：简洁约束可以用一种精确的“公式( f o r m u l a ) ” 来表示。根据该公式，可生成所有满足该约束的模式，无需在挖掘过程中反复检 查模式是否满足约束。 反单调约束( a n t i m o n o t o n y ) ：设c a 表示反单调约束，那么如果序列a 满足 c 意味着a 的所有非空子序列都满足该约束。 单调约束( m o n o t o n y ) ：设c m 表示单调约束，那么如果序列a 满足c m 意味 着a 所有的超序列也满足该约束。 强约束( t o u g h ) ：不属于上述任何一种约束的约束。一个满足强约束的序列， 其子序列和超序列是否满足该约束都是不可确定的。 针对上述的7 种基于应用的约束分类，其属性分类可参见表2 - 2 。在这四种 9 中闽科学技术大学硕。f ：学位论文背景和相关工作 基于属性分类的约束中，简洁性约束是一种最容易处理的约束，因为其可以直接 通过选择谓词从序列数据库中将所有满足约束的序列选择出来。反单调约束是一 种具有a p r i o r i 性质的约束，容易与序列模式挖掘过程结合，最常见的最小支持 度约束就是一种反单调约束，即一个序列若满足最小支持度的约束，则该序列的 所有的非空子序列均满足最小支持度的约束。在序列模式挖掘过程中，大多数算 法均利用该约束的这一特性进行非频繁单项的剪枝操作，这是在所有序列模式挖 掘中都必需的约束。相对而言，单调约束和强约束的处理起来较为困难，其难点 在于挖掘过程中，很难利用约束对搜索空间进行有效剪枝。相比反向单调约束， 单调约束和强约束不能根据当前序列模式是否满足约束而确定是否有必要进行 进一步的挖掘，即难以有效的进行搜索空间的剪枝。例如：若序列模式p 不满足 反向单调约束c ，则基于p 进行扩展的序列模式都不可能满足c ，因此p 这一 枝可以从搜索空间中剪除。而若序列模式p 不满足单调约束c ”或者强约束c t ， 基于p 进行扩展的序列模式有可能会满足c m 或者c t ，因此基于p 的挖掘还要进 行下去，若最终挖掘不到满足c m 或者c t 的模式，则所有的挖掘工作将是徒劳 无功的。这正是单调约束和强约束难以结合到序列模式挖掘过程之中，并且挖掘 效率低下的主要原因。表2 - 2 给出了上述7 种主要应用约束的属性分类。 l o 中国科学技术大学硕士学位论文 背景和相关工作 表2 2 基于应用分类的七种约束的属性分类列表 约束反单 邑 简洁 调调性 l t e mc o n s t r a i n t c k m 。) - ( vi ：ls f l e n ( q ) ，a i l o v ， y e sn oy c s 0 e 互，j ) c i k 。5 ( v i ：1 5 i s l e n ( 仅) ，a i 】n v y e sn oy e s o ) c i t e 。e 。) 5 ( ji ：l ! fs l e n ( a ) ，n f 】6 m n oy e sy e s 0 e ，) ) c i t e m ( 神i ( i ：l _ v y e sn oy e s m a x ( a ) v m i n ( a ) v n 0y e sy e s s u m ( a ) 茎v ( w i t hn o n n e g a t i v e y e sn o n 0 v a l u e s ) s u m ( a 她v ( w i t hn o n n e g a t i v e n 0y e sn 0 v a l u e s ) t o u g ha g g r e g a t e sg _ s u m ：s u m ( a ) 0v ，0 e ! ，兰 ( w i t h n 0n 0n 0 p o s i t i v ea n dn e g a t i v ev a l u e s ) a v e r a g e ：a v g ( a ) 0v ，0 e a t y e sn o n o 中田科学技术大学硕“ ：学位论文 背最和捎关工作 2 2 相关工作： 经过多年的研究工作，目前已有多种挖掘序列模式的方法，归结起来，基本 可分为两大类：通过生成候选序列并利用a p r i o r i 性质进行剪枝的a p r i o r i l i k e 算 法，以及通过对序列数据库进行划分的模式生长算法。 在a p r i o r i l i k e 算法中，典型的代表有g s p 算法，s p a d e 算法 2 2 1 等。其中 g s p 算法是基于水平数据格式的序列模式挖掘算法，而s p a d e 算法是基于垂直 数据格式的序列模式挖掘算法。所谓水平数据格式 2 3 1 是指：序列数据库以一种 自然的方式表现数据集合。每个序列在序列数据库中表中的字段表示为： 。而垂直数据格式【2 3 措的是：在序列数据库 中，每条记录表示一个元素而不是一个序列。记录的字段表示为： 。其中o b j e c t 就是序列中的一个元素，s e q u e n c e l d 表示 该元素所在序列的i d 号，而t i m e s t a m p 表示该元素在其所在s e q u e n c e 中的时间 戳。按照上述对序列的定义可知，由s e q u e n c e l d 和t i m e s t a m p 两个属性可以为 以确定一个元素在序列数据库中的位置。 在模式生长算法中，最具典型的代表为p r e f i x s p a n 算法。下面就对这几种算 法进行简单的介绍，这些算法也是后续章节中涉及到的各个基于约束的序列模式 挖掘算法的基础。 2 2 1g s p 算法 g s p 算法是一个迭代的过程。在每一次迭代中，首先生成候选序列，然后扫 描序列数据库计算每个候选模式的支持度，以确定哪些候选序列是频繁序列模 式。 ( i ) 候选序列模式的生成 本阶段由连接阶段和剪枝阶段组成。 连接阶段：连接阶段的作用是通过频繁的( k 1 ) 序列生成候选的k 序列。 对频繁( k 一1 ) 一序列集合中的两个序列s l 和，如果分别删除s ，的第一个单项和s 2 中的最后一个单项得到的两个子序列相同，则可将j 1 和s 2 用来进行连接。由它们 生成的候选序列是用s ：中的最后一个项对5 进行扩展。如果该项在s 2 中是一个单 1 2 中国科学技术人学坝上学位论文 背最和相关工作 独的序列元素，则它在候选序列中也作为一个单独的序列元素，否则该项被作为 候选序列中最后的序列元素的部分。例如序列( ，c 和 b ， 连接将生 成4 序列 ， ，而和 b ，c ，e ) 连接将生成序列 ，c ，e