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

摘要 摘要 现有的序列模式挖掘算法能有效地在大型数据库中挖掘出完整的序列 模式集。然而在很多应用中，用户更希望找出感兴趣的、更复杂的模式， 而不是所有的模式。本文主要研究了如何在序列模式挖掘中引入约束和如 何有效地在多维序列数据库中挖掘多维序列模式等问题，这些问题的研究 在顾客购物模式、互连网访问模式、自然灾难事件、疾病防治、d n a 序列 以及其它与时间相关处理过程的分析中具有重要的意义。 本文首先提出了一种带有时间间隔约束的序列模式挖掘算法。此算法 在p r e f i x s p a n 算法的基础上，对第一层投影数据库的构造方法进行了扩展， 并在搜索频繁项时绑定了时间间隔约束，从而得到满足时间间隔约束的序 列模式。在挖掘带有时间间隔约束的序列模式时，此算法的性能明显优于 g s p 算法。 其次，提出了一种基于模式增长的泛化序列模式挖掘算法。此算法的 基本思想是首先搜索频繁项，然后通过递归地挖掘投影数据库得到相应的 泛化序列模式子集，并在构造投影数据库和序列模式增长过程中直接引入 滑动时间窗口和时间约束，从而得到泛化序列模式。此算法继承了模式增 长算法的优点，其性能明显优于g s p 算法。 最后，提出了一种新的多维序列模式挖掘算法。此算法首先在序列信 息中挖掘序列模式，然后针对每个序列模式，仅在包含此模式的元组的多 维信息中挖掘出相应的多维模式，从而缩小了搜索空间。对于多维模式的 挖掘，本文基于h t r e e 结构提出了一种新的快速有效挖掘方法。在维度较 高时，此算法能获得优于u n i s e q 算法的性能。 实验结果表明，本文提出的三种算法的挖掘性能明显优于现有的同类 算法，实现了预期的研究目标。 关键词数据挖掘；序列模式挖掘；模式增长；时间间隔约束；泛化序列模 式：多维序列模式 燕山大学工学硕士学位论文 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 e s e to fs e q u e n t i a l p a r e m si nl a r g ed a t a b a s e h o w e v e r , f o rm a n y a p p l i c a t i o n s ，a u s e rm a yo f t e nl i k et of i n dd e s i r e da n dm o r e c o m p l i c a t e dp a r e m s i n s t e a do ff e n d i n ga l lt h ep o s s i b l e s e q u e n t i a lp a t t e m s t h ep a p e rh a sm a i n l y c o n c e r n e do nh o wt o i n c o r p o r a t eu s e r - s p e c i f i e dc o n s 仃a i n t si nt h em i n i n go f s e q u e n t i a lp a r e r n sa n dh o wt om i n ee f f i c i e n t l ym u l t i d i m e n s i o n a ls e q u e n t i a l p a t t e r n si n am u l t i d i m e n s i o n a l s e q u e n c ed a t a b a s e w h i c h 眦i m p o r t a n td a t a m i n i n gp r o b l e m s 谢廿1b 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 ea n a l y s i so fc u s t o m e r p u r c h a s ep a t t e r n s o rw e ba c c e s s p a t t e m s t h ea n a l y s i s o fs e q u e n c i n go r t i m e r e l a t e dp r o c e s ss u c ha ss c i e n t i f i ce x p e r i m e n t s ，n a t u r a ld i s a s t e r s ，d i s e a s e t r e a t m e n t sa n dd n a s e q u e n c e ，a n ds oo n 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 ht i m eg a pc o n s t r a i n t s i sp r o p o s e d t h ea l g o r i t h me x t e n d st h ep r e f i x s p a na l g o r i t h mt od e a lw i t ht i m e g a pc o n s t r a i n t s t h em e t h o du s e dt oc o n s t r u c tp r o j e c t e dd a t a b a s e si nt h ef i r s t r e c u r s i o nl e v e li sr e d e f i n e da n dt h es e a r c h s p a c e f o r f r e q u e n t i t e m si s c o n s t r a i n e di nt h ef r a c t i o nw i t h i nt h et i m eg a pi n s t e a do ft h ew h o l ep r o j e c t e d d a t a b a s 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 rm i n i n gs e q u e n t i a l p a r e m s 、柑t ht i m eg a pc o n s t r a i n t s s e c o n d ，a na l g o r i t h mb a s e do nt h ep a r e m g r o w t ha p p r o a c hf o rm i n i n g 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 i s p r o p o s e d t h em a i ni d e a i s f i n d i n g t h e f r e q u e n ti t e m sa n dt h e nt h es u b s e t so fg 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 sa r em i n e d b yc o n s t r u c t i n gt h ec o r r e s p o n d i n gs e to fp r o j e c t e dd a t a b a s ea n dm i n i n ge a c h r e c u r s i v e l y t h es l i d i n gw i n d o w s a n dt i m ec o n s t r a i n t sa r ed i r e c t l yi n c o r p o r a t ei n t h ep r o c e s s e so fp r o j e c t i n gp r o j e c t e dd a t a b a s em a dg r o w i n gf r e q u e n tp a t t e r n s t h e a l g o r i t h mo u t p e r f o r m s t h eg s p a l g o r i t h mf o rm i n i n gg e n e r a l i z e ds e q u e n t i a l p a t t e r n sb e c a u s et h ep a t t e m g r o w t ha p p r o a c hl e a d st oe f f i c i e n tp r o c e s s i n g t 1 f i n a l l y , an e w e f f i c i e n ta l g o r i t h mf o rm i n i n gm u l t i d i m e n s i o n a ls e q u e n t i a l p a t t e m s i s p r o p o s e d t h ea l g o r i t h m f i r s tm i n ea l l s e q u e n t i a lp a t t e r n sf r o m s e q u e n t i a li n f o r m a t i o n ，t h e nf o re a c hs e q u e n t i a lp a t t e r n ，f i n di t sc o r r e s p o n d i n g d i m e n s i o n a l p a t t e r n s i nt h em u l t i - d i m e n s i o n a l i n f o r m a t i o ni nw h i c ht h e m u l t i - d i m e n s i o n a ls e q u e n c e sc o n t a i n i n gi t ，t h i sr e d u c e st h es e a r c hs p a c e an e w m e t h o db a s e do nh - t r e es t r u c t u r ei s p r o p o s e dt oi m p r o v et h ee f f i c i e n c y a t m i n i n gm u l t i - d i m e n s i o n a lp a t t e m s w h e nd i m e n s i o n a l i t yi sh i g h ，t h ea l g o r i t h m o u t p e r f o r m s t h eu n i s e q a l g o r i t h m 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 s p 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 e r e a l i z e d k e y w o r d sd a t am i h i n g ；s e q u e n t i a lp a r e mm i n i n g ；p a t t e m - g r o w t h ；t i m eg a p c o n s t r a i n t s ；g e n e r a l i z e d 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 s e q u e n t i a lp a t t e r n i i i 第1 章绪论 第1 章绪论 在过去的二十年里，人们收集数据的能力迅速提高，在许多领域中积 累了大量信息丰富的数据。这些数据繁杂无序，但又蕴藏了许多具有重大 应用价值的知识和信息。因此，人们迫切需要开发出有效的技术和工具， 用以从海量数据中找出有用的知识和信息，知识发现( k n o w l e d g ed i s c o v e r y o fd a t a b a s e ) 正是针对这一需求产生并发展起来的。数据挖掘( d a t am i n i n 9 1 是知识发现的核心技术，特别是其中的序列模式挖掘，由于其具有广泛的 应用，已经成为数据挖掘中的研究热点之一。 1 1 知识发现和数据挖掘 数据库中的知识发现是一门交叉性学科，涉及到机器学习、模式识别、 统计学、智能数据库、知识获取、数据可视化、高性能计算、专家系统等 多个领域i ”。 1 1 1 知识发现的产生 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积 累的数据越来越多，数据集的数量、种类和规模不断增大。特别是作为全 球信息系统的月维网的发展，更使得各种数据以爆炸性的速度增长。数据 丰富，但信息贫乏口j 。隐含在数据内部的信息如关于数据之间的关联性、归 类性、序列性以及对数据整体特征的描述和对其发展趋势的预测等，在决 策生成的过程中具有重要的参考价值。尽管目前的数据库系统可以高效地 实现数据的存取、查询、统计等功能，但通过这种方式所获得的信息量仅 仅是整个数据库所包含信息量很少的一部分。因此，迫切需要一种新技术 从海量数据中自动、高效地提取有用的知识【3 】。 建立在数据库系统之上的计算机决策支持系统的出现，为进行高层次 的数据决策分析提供了很好的思路和方法。但由于决策支持系统在数据的 采集、分析方法上的灵活性等方面存在局限性，使得人们不得不寻求更有 燕山大学工学硕士学位论文 效的途径去开拓数据决策分析的思路。人工智能为此做出了巨大贡献，人 工智能经历了博弈、自然语言理解和知识工程等阶段，已经进入了机器学 习的热点阶段。机器学习能够模拟人类的学习方式，通过对数据对象之间 关系的分析，提取出隐含在数据中的模式。 f r i d m a n 列举了激发知识发现的开发、应用和研究兴趣的四个主要的技 术理由t 4 】： ( 1 ) 超大规模数据库的出现，例如商业数据仓库和计算机自动收集的数 据记录。 ( 2 ) 先进的计算机技术，例如更快和更大的计算能力和并行体系结构。 ( 3 ) 对大型数据集的快速访问。 ( 4 1 对海量数据应用精深的统计方法的能力。 知识发现正是在应用需求背景下，基于数据库技术、人工智能、机器 学习和统计学等相关技术的发展和结合而产生的5 , 6 1 。当前知识发现技术已 在市场分析、政府管理、健康医疗、科学发现、电信行业、金融及制造业 等方面得到应用并取得良好效果。 1 1 2 数据挖掘知识发现的核心 知识发现是指从大量的数据中识别出有效的、新颖的、潜在有用的、 以及最终可理解的模式的非平凡处理过程 7 1 。 知识发现过程包括以下步骤1 2 j ： ( 1 ) 数据清理消除噪声和不一致数据。 ( 2 ) 数据集成多种数据源可以组合在一起。 ( 3 ) 数据选择从数据库中检索出与分析任务相关的数据。 ( 4 ) 数据变化将数据变化或统一成适合挖掘的形式。 ( 5 ) 数据挖掘使用智能方法提取数据模式。 ( 6 ) 模式评估根据某种兴趣度度量，识别表示知识的真正有趣的模式。 ( 7 ) 知识表示使用可视化和知识表示技术，向用户提供挖掘出的知识。 可见，数据挖掘是知识发现的核心部分。f a y y a d 等人给出了这两个术 语更严格的区分：知识发现是从大量数据中发现知识的全部过程，而数据 2 第1 章绪论 挖掘是整个过程中一个特定的、关键的步骤隋1 。 1 1 3 数据挖掘的功能 数据挖掘功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任 务一般可以分为两类：描述型( d e s c 邱t i v e ) 和预测型( p r e d i c t i v e ) 吼描述性挖 掘任务找出数据库中数据的一般特性。预测性挖掘任务在当前数据上进行 推断，以进行预测。 数据挖掘的功能按照发现的模式类型可以分为以下6 种： ( 1 ) 概念类描述( c o n e e p t c l a s sd e s c r i p t i o n ) 数据可以与类或概念相关 联。例如，在某商店，销售的商品类包括计算机和打印机，顾客概念包括 大客户和零售客户。类概念描述可以通过三种方法得到；数据特征化，一 般地汇总所研究类的数据；数据区分，将目标类与一个或多个对比类进行 比较；数据特征化和比较。 f 2 ) 关联分析( a s s o c i a t i o na n a l y s i s )关联分析发现关联规则，这些规则 展示属性值频繁地在给定数据集中一起出现的条件。关联分析的一个典型 例子是购物篮分析，该过程通过发现顾客放入其购物篮中不同商品之间的 联系，分析顾客的购买习惯。在大型数据库中，关联规则的数量很多，需 要使用支持度( s u p p o r t ) s t l 可信度( c o n f i d e n c e ) 两个阀值来选择其中的强规 则。 ( 3 ) 分类和预测( c l a s s m c a t i o na n dp r e d i c t i o n )分类是要找出描述并区 分数据类或概念的模型( 或函数) ，以便能够使用模型预测类标记未知的对象 类。例如，利用当前的病历数据建立起各种疾病的分类规则，那么当新的 病人到来时，就可以根据其症状及其分类规则来决定病人所患疾病的种类。 分类可以用来预测数据对象的类标记。然而，在某些应用中，人们可 能希望预测某些未知的数据值，而不是类标记。当被预测的值是数值数据 时，通常称之为预测。 ( 4 ) 聚类( c l u s t e r i n g ) 聚类分析数据对象，而不考虑已知的类标记。 般情况下，训练数据中不提供类标记，因不知道从何开始。聚类可以用于 产生类标记。对象根据最大化类内的相似性、最小化类间的相似性的原则 燕山大学工学硕士学位论文 进行聚类或分组。与分类不同，进行聚类之前并不知道要划分成几个组和 什么样的组，也不知道根据哪些数据项来定义组。当要分析的数据缺乏描 述信息，或者是无法组织成任何分类模式时，可以采用聚类分析。 ( 5 ) 孤立点分析( o u t l i e ra n a l y s i s ) 数据库中可能包含一些数据对象，它 们与数据的一般行为或模型不一致，这些对象称为孤立点。大部分数据挖 掘方法将孤立点视为噪声或异常而丢弃。然而在一些应用中( 如欺骗检测) ， 罕见的事件可能比正常出现的哪些更有趣。 ( 6 ) 演变分析( e v o l u t i o na n a l y s i s ) 数据演变分析描述行为随时间变化 的对象的规律或趋势，并对其建模。尽管这可能包括时间相关数据的特征 化、区分、关联、分类或聚类，演变分析的不同特点包括时间序列数据分 析、序列或周期模式匹配和基于类似性的数据分析。 其中，序列模式挖掘由于在实际中具有广泛的应用，已经成为数据挖 掘中的研究热点之一。 1 2 序列模式挖掘 序列模式挖掘( s e q u e n t i a lp a t t e r nm i n i n g ) 是指在数据库中挖掘相对时间 或其他序列出现频率高的模式。序列摸式的一个典型的例子是“9 个月以前 购买奔腾p c 的顾客很可能在1 个月内订购新的c p u 芯片”。 在实际应用中，多数数据集中的数据都带有时间特征，这类数掘称为 时态数据( t e m p o r a ld a t a ) i 擒】，例如某顾客在超市内某时间段内购买商品的序 列、天气数据和生产数据等。序列模式挖掘的目标是在带有时间特征的数 据库中挖掘频繁发生的序列，从而实现对未来行为的预期。 序列模式挖掘是数据挖掘中一个重要的、富有挑战性的研究课题，在 实际中具有广泛的应用，包括顾客购物模式分析和互连网访问模式分析， 以及序列分析或者其它与时间相关的处理过程分析，例如科学实验、自然 灾难事件、疾病防治，d n a 序列、股票序列的分析等 1 1 】。 1 3 序列模式挖掘的研究现状 序列模式挖掘的概念是r a g r a w a l 等人在1 9 9 5 年首先提出的【l2 1 ，此后 4 第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 特性【据】的算法。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 ld a t af o r m a t ) 的算法，如a p r i o r i a l l 算法旧、g s p 算法【、p s p 算法1 1 s 1 等；有采取垂直数据格式( v e r t i c a ld a t a f o r m a t ) 的算法，如s p a d e 算法【1 6 】、s p a m 算法f 1 7 】等。第二类是j h a n 等人 提出的基于模式增长( p a t t e r n g r o w t h ) 策略的算法，如f r e e s p a n 算法【1 8 】、 p r e f i x s p a n 算法【1 9 1 等。 另外，c a n t u n e s 等人提出了s p a r s e 算法【2 “，该算法的主要思想是将 候选序列的产生和在投影数据库空间搜索结合起来，每一步在产生出频繁 元素后，通过增长长度寻找模式。该算法应用在密集型数据库中能获得较 好的性能。 以上算法都是在序列数据库中挖掘所有的序列模式，而且除了( i s p 算 法之外，它们挖掘的都是普通的序列模式。每一个序列模式包含了组合数 缎的频繁子序列，若序列模式的长度很长，则频繁子序列的数量往往大得 惊人。 在很多序列模式挖掘任务中，用户不需要找出数据库中所有可能存在 的序列模式，而是加入一定的约束，找出用户感兴趣的序列模式 2 1 , 2 2 1 。 a g r a w a l 等人将序列模式挖掘问题加以泛化，引入了时间约束、滑动时间窗 d ( s l i d i n gt i m ew i n d o w ) 和分类约束，并提出了g s p 算法。g s p 算法是基于 a 研o r i 特性的算法，同样具有类a p r i o r i 算法的缺点。 以上介绍的序列模式挖掘算法都是在一维信息中挖掘序列模式。若能 在序列模式中融合感兴趣的多维信息，在考虑与时间戳相关属性的同时， 挖掘多维信息中感兴趣的模式，则将得到能提供给用户更丰富信息的多维 序列模式。h p i n t o 等人提出的u n i s e q 算法【2 3 1 能有效地挖掘多维序列模式， 但在维度较高时其挖掘性能会有所下降。 此外，当前国内外学者广泛关注的研究方向还包括： 5 燕山大学工学硕士学位论文 ( 1 ) 增量式( i n c r e m e n t a l ) 序列模式挖掘 当数据库中加入新的数据序列 后，原先的部分序列模式可能不再满足最小支持度，同时可能有新的序 列模式出现。在具有海量数据的数据库中，重新挖掘显然效率很低，增量 式序列模式挖掘【2 4 - 2 7 1 研究如何利用已有的结果挖掘得到新的序列模式集， 以提高挖掘效率。 ( 2 ) 闭合( c l o s e d ) 序列模式挖掘当序列模式很长时，由于每一个序列模 式包含了组合数级的频繁子序列，挖掘所需的开销很大，然而在实际应用 经常需要挖掘特别长的模式，女i d n a 序列。闭合序列模式挖掘【2 8 3 0 1 研究如 何挖掘满足以下条件的序列模式：不存在与其具有相同支持度的超序列。 ( 3 ) 周期性( p e r i o d i c ) 模式挖掘周期性模式挖掘 3 卜。3 】的目标是在时间序 列数据库中挖掘重复发生的模式，其中挖掘局部频繁发生模式具有较高的 应用价值，例如自然灾难分析、天气预报分析等。 ( 4 ) 结构( s t r u c t u r e ) 模式挖掘结构模式挖掘3 8 1 研究的是在结构或者 半结构数据集中挖掘频繁子结构，例如树、有向循环图回a g ) 和包含环的普 通图等。因为大多数人类活动和自然现象都包含了结构，例如分子和生物 结构、万维网的连接结构等，为结构模式挖掘提供了广阔的应用前景。 ( 5 ) 近似( a p p r o x i m a t e ) 序列模式挖掘由于很多数据集都存在噪声数 掘，这些噪声数据会影响挖掘的结果。近似序列模式挖掘1 3 9 , 4 0 解决在噪声 数据集中挖掘序列模式的问题，其挖掘的是近似匹配的序列模式，而不是 完全匹配模式。近似序列模式挖掘主要应用在生物医学分析和人类行为模 式分析中。 综上所述，可以看出如何在大型序列数据库中挖掘更复杂的频繁序列模 式是有待于进一步研究的课题，涉及到如何在序列模式挖掘中加入各种约 束，以缩小搜索空间并得到用户感兴趣的模式，如何有效地在多维序列数 据库中挖掘多维序列模式等问题。 1 4 课题的研究内容和思路 本课题“序列模式挖掘算法的研究”来源于河北省博士科研基金资助 项目。 6 第1 章绪论 通过分析国内外序列模式挖掘的研究现状，可以发现现有的挖掘普通 序列模式的算法已经具有较好的性能，例如p r e f i x s p a n 算法，可以在这些 算法上加以扩展和改进，以挖掘更复杂的序列模式。 本课题有三个研究重点：第一，研究如何在大型序列数据库中快速有 效地挖掘带有时间间隔约束的序列模式：第二，尝试在现有算法上加以扩 展，在大型序列数掘库中挖掘带有时间约束和滑动时间窗口的泛化序列模 式：第三，研究如何在多维序列数据库中挖掘感兴趣的多维序列模式。 1 4 1带有时间间隔约束的序列模式挖掘 时间间隔约束( t i m eg a pc o n s t r a i n t s ) 限定了序列模式的两个相邻元素之 间的时间间隔不大于用户设定的值。 时间间隔约束序列模式挖掘在许多领域特别是在序列数据库中存在长 序列模式时具有重要的应用价值，例如d n a 序列分析、科学实验的分析等。 本文在p r e f i x s p a n 算法的基础上，对构造投影数据库的方法以及搜索 频繁项的方法进行扩展，以在搜索频繁项过程中处理时间间隔约束，从而 挖掘出带有时间间隔约束的序列模式。 1 4 2 泛化序列模式挖掘 通过在序列模式挖掘中加入各种约束，可以根据用户的兴趣进行挖掘， 从而提高挖掘的效率和质量。泛化序列模式( g e n e r a l i z e ds e q u e n t i a lp a t t e m s ) 在序列模式基本模型基础上引入了分类、滑动时间窗口和时间约束。 泛化序列模式挖掘在市场分析、医学研究、科学实验分析等领域具有 较好的应用前景。例如，在疾病治疗中，根据医院病历库中患有某种疾病 的病人出现的相同症状可以对病人做出初步诊断，如某种病人的症状为： 先是1 3 天干咳，接着是2 4 天温度在3 8 4 0 ，5 之间的发热，且所有的症 状发生在2 周之内。 本文提出一种基于模式增长的泛化序列模式挖掘算法，在p r e f i x s p a n 算法基础上进行如下扩展： ( 1 ) 投影数据库构造方法的扩展。在构造1 序列模式的投影数据库时， 7 燕山人学工学硕士学位论文 对序列关于所有包含l - 序列模式的前缀进行投影；定义新的投影规则，当 模式的长度大于或等于2 时，采用新的投影规则构造其投影数据库。 ( 2 ) 频繁项搜索方法的扩展。根据序列模式增长的两种方法分别在相应 范围内搜索频繁项，并按相应的方法追加到当前模式上，从而得到新的泛 化序列模式。 1 4 3 多维序列模式挖掘 在很多序列模式挖掘应用中，可以将序列模式与其发生的多维环境信 息结合在一起，构成多维序列模式，从而提供给用户更丰富的信息。例如， 在顾客购买模式分析中购买模式和顾客的年龄、职业、居住地点等结合在 一起，在疾病治疗中，病人的症状和年龄、性别等结合在一起。 多维序列数据库中的信息可分为序列信息和多维信息，通过将有效的 序列模式挖掘算法和多维分析方法集成在一起，可以快速有效地挖掘多维 序列模式。 本文将多维序列模式挖掘过程分为丽步：第一步，在序列信息中挖掘 序列模式：第二步，对于每个序列模式，从包含此序列模式的所有元组中 的多维信息中挖掘相应的多维模式。对于序列模式的挖掘，可以采用 p r e f i x s p a n 算法；对于多维模式的挖掘，本文基于j h a n 等人提出的h t r e e 结构1 4 1 1 提出一种新的多维模式挖掘方法。 1 5 本文的组织 本文第一章介绍了课题的来源、研究现状、以及课题的研究内容和思 路。第二章介绍了序列模式挖掘的基本模型，并对现有的序列模式挖掘算 法以及它们的优点和缺点进行了分析，着重介绍了目前最优秀的序列模式 挖掘算法呻r e 丘x s p a r i 算法，为后继的研究打下基础。第三章给出了带有 时间间隔约束的序列模式的问题定义，扩展了p r e f i x s p a n 算法，提出了 种带有时间间隔约束的序列挖掘模式的算法并给出了实验结果。第四章针 对序列模式基本模型缺少时间约束、严格的事务定义、分类层次这三个问 题，给出了泛化序列模式挖掘的问题定义，提出了一种基于模式增长策略 8 第1 章绪论 的泛化序列模式挖掘算法并给出了实验结果。第五章给出了多维序列模式 挖掘的问题定义，提出了基于h t r e e 结构的多维模式挖掘方法，并将有效 的序列模式挖掘算法和多维分析方法结合在一起，提出了一种新的多维序 列模式挖掘算法并给出了实验结果。最后对本文提出的算法的性能做出了 总结，并对未来的研究方向进行了展望。 9 燕山大学工学硕士学位论文 第2 章序列模式挖掘基础理论 2 1 序列模式挖掘的基本模型 序列模式挖掘的目的是在序列数据库中挖掘出频繁发生的模式【1 2 1 。设 非空集合i = 屯r ，。 ，其中( 1 s 七兰”) 为项( i t e m ) 。 定义2 1 ：项集( i t e r n s e t ) 是由若干项组成的集合。序歹l j ( s e q u e n c e ) 是由若 干项集组成的有序列表。序列s 可表示为 ，其中s 。是项集，即 s ，r ( 1 ，) 。j ，也称为序列s 的一个元素，表示为( x l x 2 x ，) ，其中 x 。i ( 1 j | m ) 。不包含任何元素的序列称为空序列，表示为。如果元素 中只有一个项，例如元素扛) ，则可以简写成x 。任何项在一个序列的每个元 素中最多可以出现一次，但可以出现在一个序列的不同元素之中。 定义2 2 ：一个序列中项的数目定义为这个序列的长度( 1 e n g t h ) ，一个长 度为，的序列称之为，序列。一个序列中项集的数目称为这个序列的大小 ( s i z e ) 。 定义2 3 ：设两个序列a = 、f l = ，如果存在 l 兰j l j 2 m i n s u p ，则称序列“是s 中的一个序列模式。一个 长度为f 的序列模式称为f 。模式。 序列模式挖掘问题定义如下：现有序列数据库s ，给出了最小支持度 m i n s u p ，序列模式挖掘就是要找出序列数据库s 中所有满足m i n s u p 的序列 模式。 定义2 8 ：顾客事务数据库是元组( c i d ，t i d ，构成的集合，其中c i d 是顾客编号，t i d 是事务时间，盖是一个项集。每一个( c i d ，t 1 d ，元组 称为一个事务( t r a n s a c t i o n ) 。 表2 - 1 一个顾客事务数据库 t 曲l e2 1ac u s t o m e r - t r a n s a c t i o nd a t a b a s e 顾客i d ( c i d l事务时间( t 1 d ) 购买的物品( 1 t e m s l l1a j2a b c l3a c 14d l5c f 21a 6 22c 23b e 24a e 3 1e f 32a b 33d f 34c 35b 41e 42 窑 43a f 44c 45b 46c 如表2 - 1 所示的顾客事务数据库，记录了顾客的购买行为，包含顾客编 号( c i d ) 、事务时f 司( t i d ) 、购买的物品( i t e m s ) 三个字段，所有的记录以c i d 燕山大学工学硕士学位论文 为主键、t i d 为次键排序。 一个顾客所有的事务构成一个序列，这样的序列称为顾客序列，其中 每一个事务中购买的物品成为顾客序列中的一个项集，这些项集按照事务 时间排列。 表2 - 2 与表2 1 事务数据库对应的顾客序列数据库 t a b l e2 - 2c u s t o m e r - s e q u e n c ev e r s i o no f t h ed a t a b a s ei nt a b l e2 - l 顾客i d ( c i d ) |顾客序列 1l 2 3 4 l 表2 2 是与表2 1 顾客事务数据库相对应的顾客序列数据库。假设用户 给定的最小支持度m i n s u p = 5 0 ，因为顾客1 和顾客3 的顾客序列都包含了 序列 ，即 满足最小支持度，所以 是一个长度为3 的序列模式。 2 2 序列模式挖掘算法 在r a g r a w a l 等人提出序列模式挖掘的概念之后，越来越多的科研工作 者逐渐关注于序列模式挖掘的研究1 4 2 。0 1 ，提出了一系列序列模式挖掘算法。 现有的序列模式挖掘算法基本上可以分为两大类： 第一类是基于r a g r a w a l 等人提出的a p r i o r i 特性的算法，主要包括 a r ) r i o r i a l l 算法、g s p 算法和s p a d e 算法等。这类算法中大多数采取了逐 层的、候选序列生成和检查方法( 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 ) ，在 基于已生成的频繁序列集中搜索更长的频繁序列，在执行过程中需要多次 扫描数据库。在第一次扫描数据库时，所有满足最小支持度的频繁1 序列 组成一个种子集( s e e ds e t ) 。通过此种子集产生长度为2 的候选序列，然后再 次扫描数据库，计算出这些候选序列的支持度，满足最小支持度的候选序 列即为频繁2 序列，这些序列又构成新的种子集。如此迭代下去，直到没 有发现新的频繁序列产生为止。 第二类是j h a r t 等人提出的基于模式增长的算法，包括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 ) 的模 1 2 第2 章序列模式挖掘基础理论 式增长策略，基于现有的序列模式将序列数据库递归地投影到一系列更小 的投影数据库，只需通过探索每个投影数据库中局部的频繁部分使序列模 式得到增长。 2 2 1 a p r i o r i a l l 算法 a p r i o r i a l l 算法将序列的长度定义为序列中包含的项集的数量。该算法 将序列模式挖掘过程分为五个阶段： ( 1 ) 排序阶段。将原始的数据库以c i d 为主键，以事务时间为次键进行 排序，然后将原始事务数据库转换为顾客序列数据库。 ( 2 ) 频繁项集阶段。这个阶段将找出所有的频繁项集，以每个频繁项集 为唯一元素的序列即为频繁1 序列模式。 ( 3 ) 转换阶段。这个阶段分为两步，第一步删除序列中的非频繁项集， 第二步将序列中的频繁项集转换至所定义的整数值。 ( 4 ) 序列阶段。序列阶段算法的基本思想是分阶段找出所有的频繁序列， 在每个阶段中，从一个由频繁序列组成的种子集开始，利用这个种子集产 生新的候选序列，然后找出其中的频繁序列，这些频繁序列构成下一阶段 的种子集。 ( 5 ) 最大序列阶段。若最终目的是要发现所有的最大频繁序列，算法将 包含最大序列阶段。在这个阶段，频繁序列集中不是最大序列的频繁序 列将被删除。 2 2 2 f r e e s p a n 算法 f r e e s p a n 算法在保留了类a 州o r i 算法基本策略的同时，大幅度降低了在 候选集生成与测试上所耗费的工作。以表2 2 所示的序列数据库为例，设最 小支持度为5 0 ，f r e e s p a n 算法挖掘过程如下： 首先扫描序列数据库找出所有的频繁项。以“项：支持数”的形式表 示频繁项和其支持度，将所有的频繁项按照支持度降序方式排列，构成如 下列表厂l i s t = a ：4 ，6 ：4 ，c ：4 ，d ：3 ，p ：3 ，厂3 ) 。这6 个频繁项形成 相应的6 个l 。序列模式： ：4 ， ：4 ， ：4 ， ：3 ， ： 燕山大学工学硕士学位论文 3 ， ：3 。 因此，整个序列模式集可分为6 个无交集的子集：只包含a 的序列模 式：包含b 但不包含厂? 瞎f 中b 之后的项的序列模式；包含c 但不包含，l i s t 中c 之后的项的序列模式；包含d 但不包含厂l i s t 中d 之后的项的序列模式； 包含e 但不包含厂l i s t 中e 之后的项的序列模式；包含，1 的序列模式。 通过递归地挖掘以上6 个序列模式的投影数据库可得到相应的序列模 式子集。非频繁项将从投影数据库中删除，如例子中的项p 。在每个投影数 据库中挖掘序列模式的具体过程如下： ( 1 ) 挖掘仅包含项a 的序列模式。通过挖掘 投影数据库：f ， ， ， 可以得到仅包含a 的序列模式，满足条件的只有个 序列模式，即 ：2 。 ( 2 ) 挖掘包含b 但不包含正凰，中排在b 之后的项的序列模式。通过挖掘 一投影数据库： ， ， ， ) 可以得到包含b 但不包含船t 中排在b 之后的项的序列模式； ：4 ， ：2 ， ： 2 ， ：2 ，。 ( 3 ) 挖掘包含c 但不包含正，i s t 中排在c 之后的项的序列模式。 投 影数据库包含4 个序列( ， ， ， ， 其挖掘过程如下： 扫描 投影数据库得到所有长度为2 的频繁序列：f ：4 ， ：2 ， ：3 ， ：3 ， ：2 ， ：3 l ，再次扫描 投影数据库得到这些频繁序列的投影数据库。 一投影数据库为 ， ， ， ) ，通过挖掘得到4 个长度为3 的序列模式：f ：3 ， ： 3 ， ：2 ， ：2 ，再用这4 个序列模式对序列数据库投影得到 相应的投影数据库。 一投影数据库为 ， ， ) ，没有发现长 度为4 的频繁序列，该分支上的挖掘过程结束。类似地，其他3 个投影数 据库也没有发现长度为4 的序列模式。至此， 投影数据库挖掘结束。 其他长度为2 的频繁序列 ， ， ， ， 的投 1 4 第2 章序列模式挖掘基础理论 影数据库的挖掘采用与以上相同的方法挖掘。 f 4 ) 挖掘其他序列模式子集。通过构造投影数据库并在其中递归地挖掘 可得到相应的序列模式子集，最后得到完整的序列模式集。 f r e e s p a n 算法针齐j - g s p 算法而言最大的改进之处在于它成功地将模式 的生成限制在越来越小的投影数据库中。这不但减少了需要检查的候选序 列的数量，也将候选序列的生成限制在那些至少能和已知频繁壳维序列组合 成一个( 计1 1 频繁序列的项上。但是，f r e e s p a n 算法也导致了些不容忽视 的开销，一是原始序列必须保存在每个相应的投影数