（计算机软件与理论专业论文）序列模式挖掘若干问题研究.pdf

序列模式挖掘的若干问题研究摘要 【摘要】 序列模式挖掘在w e b 同志挖掘、自然灾害预测、d n a 和蛋白质序列模式发 现等领域有着广泛应用。基于频繁模式增长的p r e f i x s p a n 是目前性能最好的序列 模式挖掘算法之一。然而在密数据集和长序列模式挖掘过程中，会出现大量的重 复投影数据库，使得这类算法性能下降。同时，序列数据库往往是动态更新的， 如果每次都是从原始数据库中进行挖掘更新序列模式，将面临巨大的搜索空间， 效率低下，通过在已有的模式基础上挖掘新的模式，可以减少挖掘原始数据库的 次数。 本文针对序列模式挖掘搜索空问大，序列数据库更新频繁等特点，对序列模 式挖掘算法及其相关算法进行了研究。主要工作成果为： 1 1给出了一种针对序列模式的压缩表示方法，节省了基于频繁模式增长的 序列模式挖掘算法所需要的内存空间。 2 )提出了一种序列模式挖掘算法，通过对投影数据库的伪投影做单项杂凑 函数，如m d 5 等，检查是否存在重复的投影数据库，避免大量重复数据库的 扫描，从而生成了压缩的前缀树，并采用一些必要条件简化压缩前缀树结点 的搜索。并根掘压缩前缀树给出了一种构造闭合序列模式的算法。 3 ) 证明了当前基于p r e f i x s p a n 的i n c s p a n 系列算法并不能挖掘出所有的序 列模式，这类基于半频繁模式的增量序列模式挖掘算法存在缺陷。并提出了 一种新的增量序列模式挖掘算法，通过| j i 缀树来表示序列模式，然后不断地 扫描增量序列产生的增量集来维护这个树的结构，在扫描过程中通过广度剪 枝和深度剪枝算法来缩小搜索空间。然后结合压缩前缀树和增量剪枝策略， 进一步提高增量序列模式挖掘算法的效率。 4 ) 对序列流数据给出了一种近似准确的序列模式挖掘算法，并证明了算法 的正确性 关键词：序列模式挖掘，投影数掘库，前缀树，单向杂凑函数，增量序列模 式挖掘，广度剪枝，深度剪枝 中图法分类号：t p 3 1 1 序列模式挖掘的若干问题研究 a b s t t a c t a b s t r a c t s e q u e n c ep a t t e r nm i n i n gh a sb r o a da p p l i c a t i o n si nt h ea n a l y s i so fw e bl o gm i n i n g , t h e p r e d i c t i o no f d i s a s t e r sa n dt h ep a t t e r nd i s c o v e r yo f d n aa n dp r o t e i ns e q u e n c e s p r e f i x s p a n , w h i c h i sb a s e do nf r e q u e n tp a t t e r ng r o w t ha p p r o a c h , i sc u r r e n t l yo n eo ft h ef a s t e s ta l g o r i t h m st o w a r d s t h i st a r g e t h o w e v e r , p r e f i x s p a nw i l lp r o d u c eh u g ea m o u n to fd u p l i c a t e dp r o j e c td a t a b a s e si n m i n i n gd e n s ed a t as e t sa n dl o n gs e q u e n c ep a t t e r n s a tt h es a m et i m e , t h es e q u e n c ed a t a b a s e u p d a t e sf r e q u e n t l y , i f w er e p e a t e d l ym i n i n go r i g i n a ld a t a b a s ef o rs e q u e n c ep a t t e r n ，w eh a v et od e a l w i t hh u g es e a r c hs p a c ea n dl o we f f i c i e n c y m i n i n gn e ws e q u e n c ep a t t e r n sb a s e do ne x i s t e do n e s c a na v o i dt h ep r o b l e m s w ef o c u so nt h eh u g es e a r c hs p a c e ，a n df r e q u e n tu p d a t e so ns e q u e n c ed a t a b a s e f o rs e q u e n c ep a t t e nm i n i n g ，t h em a i nw o r ki n c l u d e s ： 1 )w ep r o p o s e dac o m p r e s sr e p r e s e n t a t i o nf o rs e q u e n c ep a t t e r na n ds a v e m e m o r yf o rp a t t e r ng r o w t hm i n i n gb a s e ds e q u e n c ep a t t e r nm i n i n g 2 ) w ed e s i g n e da na l g o r i t h m ，w h i c ha v o i d s s c a n n i n gd u p l i c a t e dp r o j e c t d a t a b a s e sb yc h e c k i n ge v i d e n c e sc o m p u t e db ye x e r c i s i n go n ew a yh a s h f u n c t i o ns u c ha sm d 5t op s e u d op r o j e c t i o n so f p r o j e c td a t a b a s e s ，a n da l s o i m p r o v e si t sp e r f o r m a n c eb ys i m p l i f y i n gt h es e a r c hi nt h ep r o j e c tt r e e u s i n gs o m en e c e s s a r yc o n d i t i o n s ，a n dw eg i v ea na l g o r i t h mf o rp r o d u c t i n g c l o s e ds e q u e n c ep a t t e mb yu s i n gc o m p r e s s e dp r e f i xt r e e 3 ) w ep r o v e dt h a ti n c s p a ns e r i e sa l g o r i t h m s ，w h i c ha l ep r e f i x s p a nb a s e d c a n n o tc r e a t ea l ls e q u e n c ep a t t e r n sa n da l g o r i t h m sb a s e do ns e m i f r e q u e n t p a t t e r n sh a v es o m ew e a k n e s s a n dw ec o n s t r u c t e dap r e f i xt r e et or e p r e s e n t t h es e q u e n c ep a t t e r n s ，a n dc o n t i n u o u s l ys c a nt om a i n t a i nt h et r e es t r u c t u r e ， t h e nu s ew i d t hp r u n i n ga n dd e p t hp n m i n gt oe l i m i n a t et h es e a r c h s p a c e w ec o m b i n e dc o m p r e s sp r e f i xt r e ea n dp r u n i n gs t r a t e r yt oe n h a n c e t h ea l g o r i t h m 4 )w ed e s i g n e das e q u e n c es t r e a ma l g o r i t h ma n dp r o v et h ec o r r e c t n e s so f t h e a l g o r i t h m k e yw o r d s ：s e q u e n c ep a t t e r nm i n i n g ，p r o j e c td a t a b a s e ，p r e f i xt r e e ，o n ew a yh a s h f u n c t i o n ，i n c r e m e n t a ls e q u e n c ep a a e mm i n i n g ；w i d t hp r u n i n g ；d e p t hp r u n i n g 论文独创性声明 本论文怒我个人存导师指导下述行的研究工作及取得的研究成采。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 势表示了谢意。 作者链名：丝日期： 论文使篇授权声裂 矿刁毒s 国挈会 。j ! j l 本人完全了鳃复旦大学霄关像蜜、使髑学缀论文熬撰定，期：学校有奴曝蜜 送交论文静鬟印件，允许论文被查阕鞠借鬻；学校可瑷公布论文静全部线部分肉 容，可阻采用影印、缩印或其它复制手段僳存论文。保密的论文在解密后遵守此 规定。 作者签名：导师 堤8 国 序列模挖掘的若干问题研究 第1 章绪论 1 。1 研究背景 1 1 1 序列模式挖掘概述 第1 章绪论 随着计算机软硬件技术的发展，信息技术已经渗透到几乎所有的传统行业 中，数据采集、存储与管理技术的进步，使得各行业产生了海量的数据。如何搜 索和挖掘这些数据，将这些数据转化为人们需要的信息，进而促进生产力的发展 已经成为一个非常重要的课题。近年来，互联网产业的兴起，特别是搜索引擎在 商业上的巨大成功，使人们更加感受到了处理海量信息技术的重要性。海量数据 的过滤、分析、检索和挖掘等问题已经成为当前软件技术中最热门的话题之一。 国际上目前关注海量数据处理的会议有v l d b ，s i g m o d ，k d d ，s i g i r 等。 挖掘的假设是过去的数据对未来有一定的预测作用，虽然没有理论能够证明 这一点，但是从目i ；i 情况来看，这种假设在大多数领域是成立的。序列模式挖掘 字面上解释为用某种挖掘方法从海量的序列数据中找到一定的模式。模式 ( p a t t e r n ) 一词的所指的范围很广，a l e x a n d e r 认为“每个模式都描述了一个在 我们的环境中不断出现的问题，然后描述了该问题的解决方案的核心。通过这种 方式，你可以无数次地使用那些已有的解决方案，无需在重复相同的工作” o h r v 0 2 1 ，他把模式理解为一类典型问题的解决方案；而 t k 0 2 认为，模式是指需 要分类的图片、声音信号或任何可度量得型别；维基百科( w w w w i k i p e d i a o r g ) 则认为模式是能够制造或者产生某种事物的框架、模板或者模型，更抽象地说， 就是一组规则标准。 挖掘的模式也应该满足一定的限制，并不是所有的模式都是有用的。例如， 在关联规则的挖掘中，置信度( c o n f i d e n c e ) 用于定义度量挖掘出来的模式是否有 用。从什么样的序列数据，有什么样的限制、找到什么样的规则模型，不同的人 有不同的理解。因此对于一个序列模式挖掘问题，首先要搞清楚这三个方面的问 题，才能够找到合适的挖掘算法。 数据既可以是存放在数据库中的有结构化数据，也可以是一种无结构或者是 半结构化的数据，既可以是存放在一台机器上的单机数据，也可以是存放在多台 机器上的分布式数据，数据对象既可以是文本，也可以是图像、视频等多媒体信 息。由于从自然界中获取的数据存在大量的冗余、不完整、不一致，表达形式多 序列模式挖掘的若干问题研究第1 章绪论 样，连续的变量在输入到计算机的过程中还要经历离散化的过程，因此在挖掘开 始阶段需要对数据进行清理、集成、选择和变换，最终整理成所需要的数据。序 列数据按照所研究的性质不同，可以有不同的分类，按照多研究对象的多少分， 序列可分成一元序列和多元序列；按照序列的连续性分，序列可划分为连续序列 和离散序列；按照序列的统计特性分，序列可划分成平稳时日j 序列和非平稳时日j 序列，按照序列的分布规律分，序列可划分为高斯型时间序列和非高斯型时间序 列 w z l 0 2 l 。序列数据的性质直接影响到最终序列模式挖掘的方法。 数据挖掘最终的任务是找到数据集中存在的模式，具体到数据挖掘的一些常 用技术上看，关联分析是指在交易数据库中发现频繁出现的项或者项集，进而得 到统计意义上用户购买行为一组规则，所要找的模式即为购买行为的一组规则； 分类是指构造一组能够描述数据集特征的模型，以便能够对未知类别的样本进行 归类，所要找的模式为分类模型或者称为分类器；聚类是根据某种相似性的原则， 将数据集中的对象进行分组，所要找的模式是对数据集的一种描述，如簇的中心 点( e e n t r o i d ) 、半径( r a d i u s ) 等。广义上讲，序列模式就是序列数据库中暗含的任意 一组规则或者模型，例如，对于连续序列分析而言，既可以用自回归模型，也可 以是a r m a 模型等。狭义上说，序列模式特指符号( s y m b o l i c ) 序列数据库中支持 度超过一定阈值的频繁序列，因为数字曲线序列模式通常属于趋势分析和统计时 间序列预测的范畴【“0 1 】，全文将沿用狭义的说法。 最后一个要搞清楚是模式的约束条件和建模的原则、参数。前面已经提到置 信度的问题，再例如对于一类典型的分类器决策树，树结点属性分裂原则可 以g i n i 系数增益最大化，也可以是熵的增益最大化，对于聚类而言，可以用欧 式距离和曼哈坦( m a n h a t t a n ) 距离进行度量，也可以用编辑距离( e d i td i s t a n c e ) 进行 相似性度量。对于序列模式挖掘而言，关键原则是支持度的大小以及相应的约束 条件，它直接决定了一个序列是否是所需要的序列模式。 模型的最终选择既要根据数据的特点，也要根据实际情况。在明确了数据对 象、一些人为的限制和原则以及模型以后，剩下的就是构建挖掘算法，即在计算 机上的一个实践。挖掘算法具体怎么实现没有限制，因此数据挖掘吸收了传统的 机器学习、模式识别、统计分析等领域的方法，并结合了数据库技术和算法理论。 由于处理的对象是海量的数据，数据挖掘相比与其领域的技术而言更关注效率， 同为线性时间复杂度的算法，线性时间系数的大小对数据处理的速度有极大的影 响，此外，挖掘算法还要关注其他一些度量，例如对于分类问题，准确率也是一 个很重要的指标。对于序列模式挖掘而言，如何有效地减少搜索空间、节省内存 进一步提高算法的效率是问题的关键。 2 序列模式挖掘的善十问题研究第1 章绪论 1 1 2 序列模式挖掘的应用 序列并不一定特指时问有先后关联的数据，各种物理量如长度、温度、速度、 质量的递增取值都可以组成相应的序列。只常中的数据或多或少的都与这些物理 量相关，例如，一个客户在商店的历史购买行为可以看成一个序列，一篇文章可 以看成是由一个个句子序列构成，而d n a 序列、r n a 序列由一些位置上有先后 关系的碱基构成。这些序列是所研究系统的历史行为的客观记录，因而包含了系 统的结构特征和运行规律。 序列模式挖掘在零售和电子商务领域、生物数据分析、信息安全、金融业等 领域都有广泛的应用。零售就是把商品卖给最终的客户，客户在他的在的购买历 史记录和服务消费的记录上留给零售商大量有价值的信息。关联分析在零售业分 析中通常指的是发现顾客频繁同时购买的商品集，发现客户购买模式，进而提高 服务的质量，例如美国沃尔玛超市通过建立数据仓库，发现客户经常购买啤酒和 尿布，于是将这两个风马牛不相及的产品放在一起销售使得这两种产品的销量双 双激增；序列模式挖掘与频繁模式挖掘的区别在于购买是否发生在同时或者在同 一个时间范围内，例如客户在购买了自行车后，发现打气筒非常重要；在购买了 手机以后，有了对手机的装饰品的购买欲望。如果超过一定比例的客户都具有这 种行为特点，那么对那些购买自行车的用户推销打气筒，对购买手机的用户推销 装饰品能够起到很好的效果。因此，序列模式分析有助于商家发现潜在的商机。 除了用户的购买行为，随着互联网和电子商务的发展，用户的在线浏览行为 也提供了很多有价值的信息。利用c o o k i e s 、注册登记等方法，电子商务商家可 以随时跟踪客户，对用户的点击流进行过滤( f i l t e r i n g ) 、反蜘蛛化( d e s p i d e r i n g ) 、 客户验证( u s e ri d e n t i f i c a t i o n ) 、会话( s e s s i o n i z a t i o n ) 、路径补全( p a t hc o m p l e t i o n ) 等操作以后 l b 0 3 1 ，通过对用户频繁访问的序列模式改善网站的结构，对提高网站 的可用性，进而对提供服务质量具有重要的意义。这类通过分析客户行为提供个 性化服务的推荐技术成为了网络营销学的一个重要组成部分。 生物信息学主要研究对象之一是d n a 序列和蛋白质序列。世界上三大核酸 数据库( g e n b a n k 、e m b l 、d d b j ) 和蛋白质序列数据库( 如s w i s s p o r t 、p i r ) 都含 有t b 级的数据，且都以指数方式增长。转录调控是后基因组时代研究的热点之 一，其中转录因子结合位点或顺式调控元件是一类受到广泛关注的功能元素，如 图1 1 所示，它与转录因子结合并触发相应基因的表达是高等生物对生理环境改 变的一种有效应答。目前人类基因组中，仅有数量非常少的顺式调控元件被正确 识别，特别地，转录因子与顺式调控元件结合规律的研究仍处于数据积累早期， 急需发展新的计算生物学方法并开发相应的软件对其进行预测，序列模式挖掘能 3 序列模式挖掘的若十问题研究第1 章绪论 够有效地提供一些序列上的统计规律，从而为实验生物学家提供重要的指导信 息。此项研究也被列入到国家8 6 3 计划中。 t a b i e1 1s t r u c t u r eo f g e n e 图1 1 基冈结构图 网络安全是计算机领域最为活跃的分支之一，入侵检测是网络安全研究的 热点。入侵检测系统首先收集用户的行为数据，进行整理过滤，接着采用聚类的 方法对用户行为进行分组，然后应用异常点分析的手段找到异常的行为模式，建 立异常行为模式的数据库。序列模式挖掘能够发现这些异常行为模式的特征，如 果用户的行为特征符合这些异常模式，入侵检测系统可以提前进行防范，避免系 统可能遭受的攻击和破坏。 与入侵检测的思想类似，在会融业领域，序列模式挖掘可用于会融犯罪的侦 破。例如当日i 沈钱活动同益猖獗，严重威胁国家安全和经济发展，我国于2 0 0 6 年l o 月3 1 日通过了反洗钱法，并于2 0 0 7 年1 月l 同实行这部法律。和入侵异 常模式类似，洗钱和其他形式的余融犯罪行为和合法的行为相比也有其特殊的行 为模式，可利用数据挖掘中的聚类、异常点分析等手段从银行和金融机构的数据 库、数据仓库中识别出这种异常的行为模式。然后通过序列模式挖掘找出这类行 为模式的特征，有助于调查人员对异常的交易活动进行调查或者对可疑资金临时 冻结，最终起到防范会融风险的效果。 1 1 3 研究意义 综上分析，序列模式挖掘在很多领域具有重要的应用。数据挖掘的本质是一 个人工智能问题，它是在某一个假设空问上寻找问题的解，通常采用一些启发式 的搜索方法提高算法的效率，如在机器学习中采用某种归纳偏置，即按某种原则 生成的子空间上寻找最符合要求的解，而数据挖掘结合了数据库技术，对算法的 效率要求更高，特别是一些统计问题，如频繁模式挖掘等，往往需要遍历整个搜 索空间，因此通常结合一些剪枝的方法提高算法的效率，如a p r i o r i 性质，即子 模式的支持度不小于父模式。 4 序列模式挖掘的若干问题研究第1 章绪论 与数据挖掘的其他问题类似，序列模式挖掘算法也往往面l 临巨大的搜索空间 大，在1 1 2 节中提到的应用领域中，海量的数据会造成算法的运行时间无法满 足实际需求，其结果是模式挖掘出来了，商机也已经错过了。同时，序列数据库 也不是一成不变的，每天都会有大量新的序列添加到数据库中，如何及时有效的 更新序列模式也成为十分紧迫的任务。有鉴于此，我们分别发表了“无重复投影 数据库扫描的序列模式挖掘”和“一种基于前缀树的序列模式挖掘算法”论文来 解决这方面的问题，本文以这两篇论文为基础，对序列模式挖掘算法进行更加深 入的研究，对于提高算法的效率具有重要的理论意义和应用价值。 1 2 本文工作 本文针对序列模式挖掘搜索空间大，序列数据库更新频繁等特点列序列模式 挖掘算法，主要工作成果为： 1 ) 给出了一种针对序列模式的压缩表示方法，节省了基于频繁模式增长的 序列模式挖掘算法所需要的内存空间。 2 ) 提出了一种序列模式挖掘算法，通过对投影数据库的伪投影做单项杂凑 函数，如m d 5 等，检查是否存在重复的投影数据库，避免大量重复数据 库的扫描，从而生成了压缩的前缀树，并采用一些必要条件简化压缩前 缀树结点的搜索。并根据压缩i j i 缀树给出了一种构造闭合序列模式的算 法。 3 ) 证明了当前基于p r e f i x s p a n 的i n c s p a n 系列算法并不能挖掘出所有的序 列模式，这类基于半频繁模式的增量序列模式挖掘算法存在缺陷。并提 出了一种新的增量序列模式挖掘算法，通过前缀树来表示序列模式，然 后不断地扫描增量序列产生的增量集来维护这个树的结构，在扫描过程 中通过广度剪枝和深度剪枝算法来缩小搜索空间。然后结合压缩前缀树 和增量剪枝策略，进一步提高增量序列模式挖掘算法的效率。 4 ) 对序列流数据给出了一种近似准确的序列模式挖掘算法，并证明了算法 的正确性 1 3 文章结构 本文共分为五章，每章的主要内容介绍如下。 第一章简要地介绍了序列模式挖掘的研究背景并给出了序列模式挖掘的一 些应用；论述了本文的立论意义：然后介绍了本文主要的研究内容及成果；最 序列模式挖掘的若干问题研究第1 章绪论 后，给出了本文的整体组织结构。 第二章回顾了序列模式挖掘的发展，介绍了过去几种常用的序列模式挖掘基 本算法，包括基于候选集的挖掘算法和频繁模式增长算法；然后描述了宁列模式 其他一些相关问题，包括多维序列模式挖掘、基于约束的序列模式挖掘、闭合序 列模式挖掘、分布式序列模式挖掘等。 第三章提出了一种无重复投影数据库的序列模式挖掘算法。分析了基于单个 项的序列模式挖掘算法，并将这个新算法扩展到闭合序列模式挖掘和含项集的序 列模式挖掘中。用理论分析和实验证明了新算法具有较好的性能。 第四章首先分析了以往的增量挖掘算法存在不完备性的问题，运用两种剪枝 策略，并结合了第三章提到的一些技术，提出了一种基于前缀树的增量序列模式 挖掘算法。最后针对序列流数据，给出了一种近似的挖掘算法。 第五章是讨论与小结部分，对本文的工作进行总结并指出了未来的研究方 向。 6 序列模式挖掘的若干问题研究第2 章序列模式挖掘的研究现状 第2 章序列模式挖掘的研究现状 2 1 序列模式挖掘的一些基本概念 序列模式挖掘 a s g y l 最早是由a g r a w a l 和s r i k a n t 提出，主要用于分析用户的 购买模式，为方便后面的介绍，给出下面几个序列相关的定义。 定义2 1 ( 序列，序列的长度) 序列是事件e l , e 2 e n 构成的有序串，记为： e l ，e 2 p ，其中每一个事件可以是简单项或者项集。序列的长度是序列中事件 的个数。 定义2 2 ( 子序列，序列数据库，支持度) a s 9 5 1 如果序列的每个事件都是给 定序列s l = ，s 2 = ( ，西行) ，j l 是s 2 的子序列，当且仅当存 在1 5 h i 2 和序列t = ，同时含有s 和t 的序列是指序列 ， 还是指序列 ，定义并没有指明。而 与 的 支持度显然可能是刁i 相同的。按照关联分析的定义， 更符合实际 情况。然而在大量的文献中关注的重点是支持度，置信度只做为一个辅助量，本 文中也不将这个量作为论证的重点。 序列模式挖掘的任务是指从s d b 中找出所有支持度大于f 的序列5 。【a s 9 5 将序列模式挖掘算法分为五个阶段，分别是排序阶段( s o r tp h r a s e ) 、大项集阶段 7 序列模式挖掘的若十问题研究第2 章序列模式挖掘的研究现状 ( l i t e m s e tp h r a s e ) 、转化阶段( t r a n s f o r m a t i o np h r a s e ) 、序列阶段( s e q u e n c ep h r a s e ) 、 最大化阶段( m a x i m a lp h r a s e ) 。在排序阶段，按照某个关键字( 如客户i d ) 和次 关键字( 购买时间) 将关系型数据进行排序：接着在大项集阶段找到所有的频繁 项集组成集合，并进行编码，建立频繁项和编码之自j 的一一映射关系；在转化阶 段，通过这种映射关系对数据库进行处理，以生成一个内存中较小的映像并在序 列阶段找到所有的序列模式；最后在最大化阶段，去掉不必要的子序列模式，找 到包含序列元素最多的序列模式。所有的序列模式挖掘算法都可以分为这五个阶 段，从上面的过程不难看出序列阶段是整个挖掘的核心，不同的算法的最大区别 在于序列阶段不一样。整个过程如图2 1 所示。 用户名 张- 三 张三 王五 乇五 张_ = 三 拳阴 车四 于五 李四 李四 购夏时间购买物品 电脑土帆 最不器 i 乜脑主机 显币器 用户名 张_ 三 张二三 张- 三 车四 李网 李明 车吗 王冠 下五 1 = 五 购买时闻购买物品 2 0 0 0 年i 片5 j电脑主帆 2 0 0 0 年1 月8 显不嚣 2 0 0 2 芷l o 月4 h 打印机 2 0 0 1 年1 0 月5 f 1电脑土机 2 0 0 2 芷l o f t 4 打印机 电脑土机 2 。叭年l o 月5 1疆不器 2 0 0 2 年8 月7 2 0 0 2 年1 月7 【 打印机 描仪 2 0 0 1 蛊二j o h s h 2 0 0 2 年1 f 1 7 h 显不嚣 f 描仪 2 0 0 2 年”j 7 “打印机 电脑主机 2 0 0 0 往2 f 1 3 n 2 0 0 2 扯8 f 1 7 h 轻示器 打印机 转化l i j l i 面尹1 序列 = f i 醇1p r o c e s so f s e q u e n t i a lp a t t e mm i n i n g ( m i ns u p - - 2 ) 图2 1 序列模式挖掘过程( 最小支持度为2 ) 根据序列阶段的不同，序列模式挖掘有两大类基本的算法，一类是基于候选 集的，另一类是基于频繁模式增长的算法的。2 2 节和2 3 总结了这两类算法过 去的研究，在2 4 节讨论了一些其他的相关研究。 8 序列模式挖掘的若干问题研究第2 章序列模式挖掘的研究现状 2 。2 基于候选集的序列模式挖掘 基于候选集的序列模式挖掘算法的理论基础是a 嘶o f i 性质f f d s 9 3 1 ，最初 a p r i o d 性质用于频繁模式挖掘，很容易证明序列数据同样满足a p n o d 性质，即 如果s 是5 的子序列，那么j 的支持度不小于s 。 这类算法的共同特点是首先要产生大量的候选集。根据转化阶段转化的数据 形式不同，可以简略的将这类算法分为水平数据形式的序列模式挖掘和垂直形式 的序列模式挖掘【h p v 0 4 。 2 2 1 水平数据形式的序列模式挖掘 运用水平形式数据挖掘的算法主要有a p d o r i a l l 、a p d o d s o m e 、 d y n a m i c s o m e a s 9 5 1 和g s p 【删，a p f i o r i a l l 和g s p 直接借鉴频繁的a p r o i r i 挖掘 方法l a s 叫，首先生成频繁模式l l ，然后，长度为k 的序列模式集l k 通过连接生 成候选集c k 并根据a p r i o r i 性质对c k 进行剪枝，原始数据库中对c k 进行计数得 到序列模式集l k + l ，再不断循环最终得到所有的序列模式。g s p 与a p r i o d a l l 的 不同之处在于g s p 统计较少的候选集，并且在数据转化过程中不需要事先计算 频繁项集【m d w o 卯。在计数过程中需要判断一个候选序列是否是序列数据库中一条 序列的子序列，予序列函数( s u b s e q u e e n c ef u n c t i o n ) 可以采用对候选集作 h a s h t r e e 的方法加快速度。 候选集c k 不一定从l k - l 连接和剪枝生成。在a p r i o r i s o m e 中，c k 可以从c k 1 或者l k - l 两种方法连接生成。整个挖掘过程分为前推阶段( f o r w a r dp b x a s e ) 和 回溯阶段( b a c k w a r dp h r a s e ) 。在前推阶段，根据序列模式集数量与候选集数量比 值i l k | l i c k - i i 来确定c k 从c k i 还是l k - l 中生成，这样绕开候选集和序列模式集数 量比较接近的情况，减轻了最大化阶段的负担。当这个比值总是很小的时候， a p r o i r i s o m e 退化成a p r i o r i a l l ；在回溯阶段，如果l k 还没有生成，则通过c k 计 数从而直接计算出l k 。d y n a m i c s o m e 则更加灵活，c k 值不但可以从c k 1 和l k 1 生成，还可以从c 。和ck 。( m k ) 连接而成。回溯阶段和a p r o i r i s o m e 相同。 2 2 2 垂直数据形式的序列模式挖掘 与水平数据形似的序列模式挖掘算法的连接阶段不同，垂直数据形式的序列 模式挖掘既可以用广度优先策略搜索空间也可以用深度优先策略搜索空间。 s p a d e ( s e q u e n t i a lp a t t e r nd i s c o v e r yu s i n ge q u i v a n t l a n tc l a s s ) 【2 蝴采用格理论 9 序列模式挖掘的若干问题研究第2 章序列模式挖掘的研究现状 ( l a t t i c e t h e o r e t i c ) 方法，将搜索空间划分为能够完全存放在内存中的小块，以序 列i d 为主属性，而已时问标识为辅助属性对第k 1 层的序列格进行连接，生成 第k 层的格。这个生成过程仍难会产生大量的候选集。格的连接操作很容易通过 位图实现，s p a m ( s e q u e n t i a lp a t t e r nm i n i n gu s i n gab i t m a pr e p r e s e n t a t i o n ) t 4 0 7 0 2 1 将垂直形式的数据结构改进成位图形式，采用深度优先策略进行搜索，算法本质 上与s p a d e 类似，也许需要产生大量的候选集，不过他通过s - p r i m i n g 和i - p r u n i n g 进行了优化。 2 3 频繁模式增长的序列模式挖掘 另一类基于频繁模式增长的算法思想来源于交易数据库中f p g r o w t h h p y o o l 算法，最早 h p 0 0 针对w e b 日志给出了一种序列模式挖掘，通过构造w a p t r e e ( w e ba c c e s sp a t t e r nt r e e ) 描述序列模式，自底向上进行挖掘。g r c 0 5 给出了另 一种自顶向下的算法，提高了算法的性能。但序列的特点决定了w a p t r e e 共享 的结点不多，整体性能提高有限。 f r e e s p a n r n m 删算法将搜索空间进行划分，基于投影序列自项向下的递归生 成一些投影数据库( p r o j e c td a t a b a s e ) ，相比于g s p 中搜索子序列数掘库投影， f r e e s p a n 搜索更小的投影数据库。f r e e s p a n 的代价是可能会产生很多琐碎的投影 数据库，在某些情况下算法收敛的速度会很慢，p r e f i x s p a n ! p h m 0 ”解决了这个问题， 它不需要检查潜在的频繁投影项集，另一方面，如果序列数据库能够装载到内存 中，可以采用伪投影( p s e u d o p r o j e c t ) 减少生成投影数据库的代价，我们将在下 一章讨论这个算法。 2 4 序列模式挖掘的其他若干问题 序列模式挖掘针对不同的商业应用也有进一步的研究，根据序列数据的特 点、人为的限制要求、挖掘模式的要求等，序列模式挖掘还大致分为序列模式挖 掘的分布式或并行算法、多维序列模式挖掘、增量序列模式挖掘、闭合序列模式 挖掘带约束的序列模式挖掘、针对流数据的序列模式挖掘等，这些算法的基本思 想多数都以2 3 节讨论的算法为基础，结合现实情况做了适当的更改。下面介绍 这方面最近的一些研究。 1 0 序列模式挖掘的若干问题研究第2 章序列模式挖掘的研究现状 2 4 1 分布式序列模式挖掘 随着计算机应用技术的发展，单计算机系统已经不能够满足海量数据的处理 需求。由网络连接多台计算机形成的分布式系统成为当今主流系统，因此数据往 往呈分布式状态。f d m | 。h n 9 6 1 解决了分布式环境中关联规则挖掘问题。分布式序 列模式挖掘算法应该满足三个条件 z z l 0 5 1 ，一是分布式序列模式挖掘算法最终得 到的全局数据序列集合必须与在单计算机系统中将所有数据集中执行现有算法 得到的数据序列集合完全一致；二是分布式序列模式挖掘通讯代价较小；三是分 布式序列模式挖掘算法应该具有比将所有数据集中在单机系统上执行现有算法 相同或更好的效率。 p s p a d e l ： 吐0 1 1 是一种在共享内存机上实现的算法，该算法基于s p a d e ，运用 数据并行化( d a t ap a r a l l e l i s m ) 和任务并行化( t a s kp a r a l l e l i s m ) 两种手段实现。 数据并行化是将多个处理器同时数据库的各个不同部分，但同时处理全局计算树 ( c o m p u t a t i o n t r e e ) 。在任务并行化中处理器则是共享数据库，但是异步的处理 计算树。f d m s p t z z l 0 5 基于p r e f i x s p a n ，利用序列模式前缀指定选举站点统计序 列的全局支持计数，并利用局部约简、选举约简、计数约简等方法减少候选序列 数，使得算法具有较高的性能。 2 4 2 多维序列模式挖掘 数据库中的项通常会有一些其他的属性，对一个购买商品，往往具有如价格、 质量、产地等属性，对某个用户，也具有性别、年龄、地区等额外属性。而不同 年龄的人对不同价格的同类商品具有不同的偏好，单纯只考虑购买商品可能不能 得出有效的模式。交易数据库中针对这种情况提出了多维关联规则挖掘 h f 9 5 i s a 9 5 1 以解决这方面的问题。在序列数据库中，多维序列模式挖掘也可以解决相应的问 题。 多维序列模式挖掘算法由 p h p o i 提出，算法以p r e f i x s p a n 和b u c i b r 9 9 1 为基 础。u n i s e q 采用将多维属性信息内嵌到序列中，d i m s e q 和s e q d i m 将多维属 性和序列分开，d i m s e q 首先寻找多维模式( m d p a t t e m s ) ，对于每一个多维模 式生成投影数据库然后对投影数据库进行序列模式挖掘。s e q - d i m 则首先挖掘序 列模式，对每一个序列模式生成的投影数据库挖掘多维模式。 序列模式挖掘的菪十问题研究第2 章序列模式挖掘的研究现状 2 4 3 增量序列模式挖掘 数据库随着时间的变化，会有相应的增加、修改和删除，如果在某个时刻已 经挖掘出数据库中的模式，对更新的数据进行挖掘时，则可以利用这些模式作中 间结果，在大多数情况利用这个中b j 结果可以提高算法的效率，如在交易数据库 中，增量模式挖掘l d h ”9 6 j l 从9 7 】r r b a 9 刀证明了这种方法的有效性。 i s m 【9 砌驯是第一个增量序列模式挖掘算法。该算法基于s p a d e ，考虑了序 列数据库的附加和插入操作，缺陷是需要存储大量的序列索引，并维护庞大的增 序格( i s l ) 。每次更新i s l ，除了更新序列模式集( f s ) ，还要维护否定边界( n r ) 。 i s e “”i 在i s m 基础上还增加了序列的删除操作。 i n c s p a n c w 叫和i n c s p a n + i n s 0 0 5 1 算法基于p r e f i x s p a n ，i n c s p a n 提出了半频繁 模式的概念。本文在4 2 节详细讨论i n c s p a n 系列算法，并指出其中存在缺陷。 2 4 4 闭合序列模式挖掘 定义2 5 一个序列j 为闭合序列模式，当且仅当s 是一个序列模式且不存在 s 的超序列s ：使得s 和s 有相同的支持度。 和序列模式算法的其他相关问题一致，闭合序列模式挖掘来源于交易数据库 中的闭合模式挖掘，如c l o s e t l 9 “m 删、m a f i a 8 0 0 0 ”、c h a r m 2 “0 2 1 、 c l o s e t + w “9 吲、c r o p i 。s z 洲。闭合序列模式运用闭合模式特有的性质进行剪枝。 基于p r e f i x s p a n 的算法c l o s p a n y h “0 3 】首先通过对前缀树进行适当的剪枝避免了 部分重复投影数据库的扫描，然后对序列模式集进行额外的约简，使得最终的序 列模式都是闭合序列模式。b i d e w “叫则是另一种思路，首先证明了如果一个序 列既不存在前向扩展( f o r w a r de x t e n s i o n ) 也不存后向扩展( b a e k w o r de x t e n s i o n ) ，则 该序列是闭合序列模式。通过这种双向闭合扩展检查( b i d i r e c t i o n a lc l o s u r e c h e c k i n g ) 的方式，引入向后扫描( b a c k s e a n ) 进行剪枝，最终生成闭合序列模式， b i d e 还采用一种s e a n s k i p 的技术对算法进行优化，实验表明b i d e 算法要优于 c l o s p a n 。 2 4 5 基于约束的序列模式挖掘 现实中用户可能只对一些特殊的序列模式感兴趣，根据人们的经验，有一些 在统计上表现为有规律的模式并不有用。这种特殊的需求有助于缩小搜索空间提 高算法效率，从序列模式挖掘的概念一出现，这种针对用户特定需求的序列模式 1 2 序列模式挖掘的菪十问题研究第2 章序列模式挖掘的研究现状 算法也是一个非常热门的话题。 两种最常见的序列模式挖掘的限制为滑动窗口( s l i d i n gw i n d o w ) 和时间间 隔( t i m eg a p ) 。滑动窗口指的是某一段时间内的窗口内的序列模式，一个序列 窗口的大小指的是最后一个元素的时间和低一个元素的时间之差，它针对的目标 是整个序列。而时自j 间隔指的是相邻两个序列元素之间的i 日j 隔，分为最小间隔 ( m i n i m a lg