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

广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者虢音勰次 驯口年乡月歹纱日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 矗 曰直口时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 敝储魏韵胀新签名釉氐沙，年多月歹少日 基于多序列的序列模式挖掘算法的研究和应用 摘要 数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量数据中 发现有趣知识的过程，是涉及人工智能和数据库等学科的一个相当活跃的 研究领域。序列模式发现是其中一个重要的研究方向。 序列数据库由记录带有或不带有具体时间概念的有序元素或事件的序 列组成。序列模式挖掘就是在序列数据库中发现频繁发生的有序事件或者 子序列模式。序列模式挖掘有着广阔的应用前景，例如交易数据库中的客 户行为分析、w e b 日志分析、文本分析、d n a 分析和自然灾害预测等等。 现实世界中的事物是相互联系的，挖掘基于多序列的序列模式能够更 好地反映现实世界中事物的关联。本文在传统的序列模式挖掘基础上，通 过改进实现了多序列模式的挖掘。首先，对传统的序列模式概念进行扩充， 提出了多序列模式概念( m u l t i p l es e q u e n t i a lp a t t e r n s ) p _ j , 及基于多序列约束的 优化和剪枝技术。其次，在p r e f i x s p a n 算法的基础上实现了多序列模式的 挖掘算法( m s _ p r e f i x s p a n ) ；在c l o s p a n 算法的基础上实现了闭合多序列模 式的挖掘算法( c m sc l o s p a n ) 。最后，将闭合多序列模式挖掘算法应用到实 际数据分析中。 实验结果表明，本文提出的多序列模式挖掘算法能够准确高效地挖掘 出多序列模式，并在实际数据分析中挖掘出了较有实用意义的模式。 关键词：数据挖掘序列模式挖掘多序列模式挖掘多序列约束 r e s e a r c ha n d a p p l i c a t i o no fm i n i n g s e q u e n c e p a t t e r n si nm u l t i s e q u e n c e 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 e 。f e x t r a c t i n ga n dm i n i n g1 ( n 。w l e d g e 舶m j a 唱ea m 。u n t 。fd a t ai n d a t a b a s e ，d a t aw a r e h 。u s i n ga n do t h e r i n f o 册a t i 。n ! ：幻? 锄她1 8 “s a 唧a c “v e r e s e a r c h 蹦d r e l a t e d t oa 砌c i a l i i g e n c e a n dm a b a 8 e s y s 钯m d is c o v e 秽o f s e q u e n t i a l 刚e m s i sa ni m p 。n a n t 蹦d i n d a t am m m g r e s e a r c h a s e q u e n c ed a t a b a s ec o n s i s t so f s e q u e n c e so fo r d e r e de l e m e n t so re v e n t s j ：e c 咖酣w l m o w “h u t a c o n c r e t e n o t i o no f t i m e s e q u e n t i a j p a t t e mm i n i n g i s t n e m l n l n go f 疗e q u e n t l yo c c u r r i n go r d e r e de v e n t so r s u b s e q u e n c e sa sp a t t e m s i t y 1 儿蛔垤甜a p p l i c a t i o n i nf u t u r es u c ha st h e a n a l y s i so fc u s t o m e r b e h 痂r 1 nt r 觚s a c t l o nd a t a b a s e , w e b u s a g el o ga n a l y s i s ，t e x ta n a l y s i s ，d n a a n a i y s i sa n d _ ln er e a lw o r l di s i n t e r c o n n e c t e d ，a n dm i n i n gs e q u e n t i a lp a t t e m sb a s e d o n ? u l n p l e s e q u e n c e sc a nb e t t e rr e f l e c tt h er e a l w o r l dr e l e v a n c e i n t h i sp a p e r ， 1 m p r o v e m e n to ft h et r a d i t io n a ls e q u e n t i a l p a t t e r n sm i n i n gt oa c h i e v eam u l t i p l e s e q u e n t l a ip a t t e m sm i n i n g f i r s t ，e x p a n d t h ec o n c e p to f t h et r a d i t i o n a ls e q u e n t i a l p a t t e m st op u tf o n v a r dt h e c o n c e p to fm u l t i p l es e q u e n t i a lp a t t e m sa n d p r o p o s e o p t i m i z a t l o na n dp r u n i n gt e c h n i q u e sb a s e do n m u l t i p l es e q u e n t i a lc o n s t r a i n t s s e c o n d ，b a s e do nt h e p r e f i x s p a na l g o r i t h mw ed e s i g n e dm u l t i p l es e q u e n t i a l 鼍a r t 锄8 m m m g 羽g o r i t h r n ( m s p r e f i x s p a n ) ；b a s e do nc 1 0 s p a na i g o m mw e 三e s i g n e d c l o s e dm u h 。s e q u e n t i a l p a t t e r n sm i n i n ga l g o m m ( c m sc 1 。s p a n ) j ：1 n a y ；c l o s e d m u l t i 。s e q u e n t i a lp a t t e mm i n i n ga l g 。r i t h mi s a p p l i e dt 。t h er e a 】 t h ee x p e r i m e n t a l r e s u l t ss h o wt h a t t h ep r o p 。s e d m u l t i 。l e s e q u e l l t i a l p 撕e m sm i m n g 甜g o r i t h mc a n a c c u r a t e l ya n de 触t i v e l y m i n i n g 。u i t - tv t h e 二l t i p l e i i s e q u e n t i a lp a t t e m s ，a n dc a nm i n i n go u tt h es i g n i f i c a n c ep a t t e m so f r e a ld a t a k e yw o r d s ：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 sm i n i n g ；m u l t i p l es e q u e n t i a l p a t t e m sm i n i n g ；m u l t i p l es e q u e n t i a lc o n s t r a i n t i i i 目录 摘要i a b s t r a c t i i 第1 章绪论1 1 1 数据挖掘一1 1 1 1 数据挖掘的数据源l 1 1 2 数据挖掘可发现的模式类型3 1 1 3 数据挖掘的应用热点4 1 2 序列模式挖掘。5 1 2 1 序列模式挖掘简介5 1 2 2 序列模式挖掘的国内外研究现状6 1 3 本文的主要内容和组织8 第2 章序列模式挖掘研究概述9 2 1 序列模式的基本概念9 2 1 1 频繁模式9 2 1 2 序列模式12 2 2 经典序列模式挖掘算法1 5 2 2 1g s p 算法15 2 2 2s p a d e 算法18 2 2 3p r e f i x s p a n 算法2 1 2 3 经典闭序列模式挖掘算法2 3 2 3 1c l o s p a n 算法2 3 2 3 2b i d e 算法2 6 第3 章基于多序列的序列模式挖掘2 9 3 1 多序列模式介绍2 9 3 1 1 多序列模式的提出一2 9 3 1 2 多序列模式的基本概念3 0 3 1 3 多序列与多维、多层的区别3 2 3 1 4 多序列模式与多时间序列跨事务关联规则的区别一3 3 3 2 基于多序列约束的优化和剪枝技术一3 3 3 3 基于多序列的序列模式挖掘算法m sp r e f i x s p a n 一3 5 3 3 1 算法实现3 5 3 3 2 实验分析一3 7 3 4 基于多序列的闭序列模式挖掘算法c m sc l o s p a n 4 0 3 4 1 算法实现4 0 3 4 2 实验分析4 2 3 5 本章总结4 4 第4 章多序列模式挖掘算法的应用研究4 5 4 1 弓i 言4 5 4 2 在气象数据挖掘中的应用4 5 4 2 1 数据预处理4 5 4 2 2 算法在实际应用中的性能分析4 8 4 2 3 挖掘结果分析4 8 i v 4 3 本章总结51 第5 章总结与展望5 2 5 1 - 1 2 作总结5 2 5 2 存在问题及改进方向5 2 参考文献5 4 至5 【谓 5 9 攻读硕士学位期间发表的学术论文5 9 v 广西大掌硕士掌位论文 基于多序列的序歹模式挖掘算法的研舅并口应用 1 1 数据挖掘 第1 章绪论 近年来，数据挖掘得到了信息产业界和整个社会的极大关注，其主要原因是随着计 算机、数据自动采集、数据库等技术的不断发展，各种组织中已经存储了大量的信息数 据，并迫切需要将这些数据转化为有用的信息和知识。这种需求普遍存在于各个行业当 中，例如：欺诈检测、市场分析和科学研究等等。 数据挖掘的一个广义定义：数据挖掘是从存放在数据库、数据仓库或其他信息库中 的大量数据中发现有趣知识的过程【l6 】。目前业界普遍认为，数据挖掘是知识发现的一个 步骤，负责在己根据要求进行整理的数据中发现隐藏的模式。从技术实现的角度看，数 据挖掘是一个交叉性学科，它涉及到包括数据库和数据仓库技术、统计学、机器学习、 高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理以及空间 和时间数据分析。数据库和数据仓库技术是数据挖掘生存的前提，前者为数据挖掘提供 了大量的可用数据，如果没有大量的数据作为挖掘土壤，数据挖掘是无法实现的。数据 挖掘可以看作是统计学的应用延伸，目前数据挖掘技术与统计学有很大范围的交叉，但 是数据挖掘也突破了统计学的限制，能够完成统计学无法完成的任务。数据挖掘能够更 深刻细致地描述蕴藏于数据中的模式，而不仅仅局限于像统计学那样在全局层面体现数 据的特性；数据挖掘能够让用户参与到挖掘过程，或根据用户的约束进行定向挖掘；数 据挖掘可以把数据分析工作平民化，可根据用户的领域需要，由用户自行挖掘。 1 1 1 数据挖掘的数据源 数据挖掘有着丰富的数据源，可以在多种数据存储库上进行挖掘。论理上，数据挖 掘可以应用于任何类型的信息存储库以及瞬念数据( 如数据流) 。目前，数据挖掘已被 应用到了多种数据存储库当中。 ( 1 ) 关系数据库【16 】。关系数据库是目前的主流数据库类型，是目前数据挖掘的一 种主要数据形式。当数据挖掘应用于关系数据库时，可以搜索趋势或数据模式，这样的 挖掘是s q l 关系查询语句难以做到的。例如：数据挖掘系统可以进行偏差检测，如哪 种商品的销售与前一年相比变化较大。这种偏差还可以进一步挖掘，挖掘该商品是否存 广西大学硕士学位论文基于多序列的序歹n 模式挖掘算法的研究和应用 在一些变动，例如：包装、价格等等。 ( 2 ) 数据仓库【1 6 1 。数据仓库是一个从多个数据源收集信息的储存库，收集得到的 信息以一致的模式存放在单个站点上。数据仓库通过数据清理、数据变换、数据集成、 数据装入和定期数据刷新来构造。那些经过加工存放于数据仓库的数据非常适合进行数 据挖掘，虽然目前联机分析处理已经应用到了数据仓库中，但是仍然需要更多的数据挖 掘工具，以进行更深入的自动分析。 ( 3 ) 事务数据库 1 引。事务数据库一般是文件型数据库，库中的每条记录就是一个 事务。通常，一个事务由事务标识号和项列表构成，其中事务标识号是唯一的，用于区 别每一个事务，项列表是事务的内容( 例如购物清单) 。事务数据库可能有一些附加表， 例如销售事务数据库可能包含关于销售的其他信息的附加表，这些附加表中记录了事务 的日期、顾客的i d 、销售者的i d 等等。目前，在事务数据库上的数据挖掘主要集中在 频繁模式的挖掘，这些频繁模式中包含了关联规则、序列模式等等。例如：数据挖掘可 以在购物篮数据中分析出“客户喜欢同时购买哪些商品呢? ”等，基于频繁度的模式。 随着数据库技术的发展和计算机的普遍应用，各种高级数据和信息系统已经出现， 它们为数据挖掘提供了新的、更丰富的数据源，同时也对数据挖掘提出了新的挑战。 ( 1 ) 时间数据库、序列数据库和时间序列数据岸1 6 】。时间数据库( t e m p o r a ld a t a b a s e ) 通常存放包含时间相关属性的关系数据。这些属性可能涉及若干时间标签，每个都有不 同的语义。序列数据库( s e q u e n c ed a t a b a s e ) 存放具有或不具有具体时间概念的有序事 件的序列。例如：客户购物序列、w e b 点击流和生物学序列等。时间序列数据库 ( t i m e s e r i e sd a t a b a s e ) 存放定时( 如每天、每周等) 重复测量得到的值或事件的序列。 例如：股票交易、库存控制和气象数据等。利用数据挖掘技术可以从这些数据库中挖掘 出有助于制定决策或规划的演变特征和变化趋势，因此基于这些数据库进行数据挖掘是 目前数据挖掘的一个重要研究方向。例如：可以挖掘股票交易数据，发现可能有助于制 定投资策略的趋势。 ( 2 ) 数据流【l 酬。许多应用涉及称作数据流( s t r e a md a t a ) 的一类新的数据的产生和 分析，其中数据动态地从观测平台( 或窗口) 流进和流出。这种数据流具有以下特点： 海量甚至无限，动态变化，以固定的次序流进流出，只允许一遍或少数几遍扫描，要求 快速的响应时间【1 6 。由于数据流通常不存放在任何数据储存库中，数据流的有效管理和 分析对研究工作提出了巨大挑战。目前，挖掘数据流主要涉及数据流中的一般模式和动 态变化的有效发现。例如：根据消息流中的异常检测发现计算机网络的入侵。 2 广西大学硕士掌位论文基于多序列的序歹模式挖掘算法的研究和应用 ( 3 ) 万维网 1 6 】。万维网对数据挖掘提供了大量的数据，但同时也提出了巨大的挑 战。例如：理解用户的访问模式不仅有助于改进系统设计( 通过提供高度相关的对象间 的有效访问) ，而且还有助于实现更好的市场决策( 例如，通过在频繁访问的文档上放 置广告，或提供更好的顾客用户分类和行为分析) 。 1 1 2 数据挖掘可发现的模式类型 数据挖掘具有丰富的数据源，同样地，数据挖掘可以发现类型丰富的模式。一般而 言，数据挖掘任务可以分为预测和描述两大类。预测性挖掘任务对当前数据进行推断， 以做出预测。描述性挖掘任务描述数据库中数据的一般性质。 数据挖掘系统是一个开放、交互性系统，用户需要参与到挖掘过程当中，应能根据 用户的要求做出相应的响应。因此，需要数据挖掘系统能够根据用户的需求挖掘不同类 型的模式，能挖掘各种粒度( 即不同的抽象层) 下的模式，能够允许用户提供参数，指 导或聚焦于用户感兴趣的模式的挖掘。一般情况下，很多模式并不是全局性的，它们只 能对数据库中的部分数据成立，因此，通常都会对挖掘出的模式附加一个确定性或“可 信性度量，以便于比较或评价该模式。 目前，数据挖掘的常见模式有以下几种： ( 1 ) 类概念描述【1 6 】：特征化和区分。用汇总的、简洁的和精确的方式描述各个类 和概念，这样的描述就称之为类概念描述( c l a s s c o n c e p td e s c r i p t i o n ) 1 1 6 】。可以通过以 下方法实现类概念描述：1 、数据特征化，一般地汇总所研究类( 通常称为目标类t a r g e t c l a s s ) 的数据，是目标类数据的一般特性或特征的汇总。例如：数据特征化应当能产生 一年之内在本商场内花费在一万元以上的客户特征的汇总描述。结果有可能是客户的年 龄、收入等信息描述。2 、数据区分，分析目标类与一个或多个可比较类( 通常称为对 比类c o n t r a s t i n gc l a s s ) 之间的差别，即将目标类数据对象的一般特性与一个或多个对比 类对象的一般特性进行比较。例如：数据区分应当能比较经常购买电脑产品和偶尔购买 电脑产品的两组顾客。结果可能是经常购买电脑产品的顾客大多比较年青，而偶尔购买 电脑产品的客户年龄都比较大。 ( 2 ) 分类和预测【1 6 】。分类首先找出能够描述和区分数据类或概念的模型( 或函数) ， 然后使用该模型预测类标号未知的对象类。分类结果的导出模型是基于对训练数据集 ( 类标号已知的数据对象) 的分析。分类模型有多种可用的表示形式：决策树、神经网 厂西大掌硕士掌位论文基于多序歹的序罗h 模式挖掘算法的研要辫口应用 络等。预测是建立连续值函数模型。例如：为银行贷款建立一个分类模型，对安全贷款 和风险贷款进行分类；也可以建立预测模型，给定顾客的收入、年龄，预测他们在计算 机设备上的花费。 ( 3 ) 聚类分析【1 6 】。聚类是一个将物理或抽象对象的集合分成相似对象类的过程。 与分类不同的是，聚类中每个对象的类标号都是未知的，聚类将数据对象分成类或簇， 使得同一簇中的对象相似度很高，不同簇间的对象相异度很高。聚类分析已广泛用于多 个应用领域，包括市场研究、模式识别、数据分析和图像处理。聚类还可用于离群点检 测( o u t l i e rd e t e c t i o n ) 。 ( 4 ) 离群点分析【1 6 】。数据库中那些与数据的一般行为或模型不一致的数据对象就 是离群点( o u t l i e r ) 。离群点分析就是在数据库中发现离群点的过程。大部分情况下，离 群点会被当作噪声或异常而被丢弃，但在一些应用场合，离群点更能吸引人的兴趣。例 如：欺诈检测、入侵检测。 ( 5 ) 频繁模式挖掘【16 1 。频繁模式是在数据中频繁出现的模式，有多种类型的频繁 模式，包括项集、子序列和子结构。一般地，频繁项集是指频繁地在事务数据库中同时 出现的项的集合。例如，在购物篮中，剃须刀和剃须膏经常被同时购买。频繁出现的子 序列，即序列数据库中频繁出现的子序列。例如，用户先购买数码相机然后购买内存卡、 充电电池、打印相纸等与数码相机相关的耗材。子结构可能涉及多种类型，如图、树或 格。如果一个子结构频繁出现，则称它为频繁结构模式。频繁序列模式的挖掘是本文的 研究重点。 1 1 3 数据挖掘的应用热点 作为一个新兴的研究领域，自2 0 世纪8 0 年代，数据挖掘已经取得了广泛和重大的 进展。目前，数据挖掘已被应用于众多的领域，同时出现了大量的商品化的数据挖掘系 统。下面介绍几个数据挖掘的应用领域。 ( 1 ) 金融数据分析【l6 1 。金融业有着很长的历史，分析金融数据也由来已久，这使 得银行和金融机构收集的金融数据通常质量较高，是数据挖掘应用的一个难得的领域。 数据挖掘可应用于贷款偿还预测和顾客信用政策分析。在实际生活中，有很多因素会对 贷款偿还和顾客信用评定产生不同程度的影响，数据挖掘有助于从众多因素中识别重要 的因素，去掉不相关的因素，帮助银行更好的开展业务。 4 广西大掌硕士掌位论文基于多序列的序列模式挖掘算法的研究和应用 ( 2 ) 零售业数据分析【l6 | 。零售业是数据挖掘的主要应用领域，因为零售业收集了 丰富的信息。随着基于w e b 或电子商务进行的商业活动日益方便和流行，零售业收集 的数据量迅速增长。这就为数据挖掘提供了海量的数据。数据挖掘在零售业中的应用十 分广泛，能提供丰富的分析。例如：基于销量、顾客、产品、时间和地区等维度的多维 分析能帮助商家更深刻细致地了解销售情况，制定详细的销售计划。通过进行特征分析， 分析客户的消费习惯，发现不同类型客户的消费习惯，从而进行相应的推销或折扣，有 利于维系老客户，发展新客户。通过购物篮数据挖掘，可以进行产品推荐，捆绑销售等。 ( 3 ) 其他应用【16 1 。数据挖掘也被广泛应用于其他领域，包括生物学数据分析、入 侵检测等。生物学的基因、氨基酸、蛋白质数据是海量的，这就为数据挖掘提供了丰富 的数据，同时也对数据挖掘提出了巨大挑战，例如，如何识别在各种生物功能、遗传疾 病和进化方面扮演重要角色的d n a 或氨基酸序列模式。随着计算机网络应用的普及， 网络日益深入到人们的日常生活中，安全问题成为了一个热点问题。入侵检测是一种有 效的预防安全问题的手段，可以通过异常检测来尽早发现可能的潜在入侵行为。异常检 测通过构建正常行为模型( 称为特征描述) ，可以用来发现与特征描述严重偏离的新模 式，这些新模式有可能就是入侵行为。异常检测的主要优势是可以发现以前未曾观测到 的入侵。 1 2 序列模式挖掘 1 2 1 序列模式挖掘简介 在数据库中，序列数据是一种很重要的数据类型，常见的有时间数据库、序列数据 库等。在其他领域，序列型数据也广泛存在，例如：生物d n a 序列。序列数据中往往 包含着有价值的信息，由于数据间的有序性，序列数据尤其合适用于预测。例如，对于 商店而言，一个客户的购买清单就包含了序列数据，可以从中推断出该客户的购买习惯， 商家可以对其进行有针对性的推销。在证券市场上，交易价格受多种因素影响，这些因 素的变动最终导致了价格的变化，如果能够掌握这样的变化序列，将有助于投资者制定 投资策略。在天气预报中，通过分析历史气象数据，可以发现一些气候变化的规律，在 气候变化发生之初对气象进行预测，避免造成巨大损失。由于序列数据自身的特质，以 及蕴含的潜在价值，使得序列模式挖掘成为了数据挖掘的一个研究热点。 基于多序列的序列模式挖掘算法的研究和应用 序列模式挖掘问题是由a g r a w a l 和s r i k a n t 在1 9 9 5 年，基于对消费者的购买序列首 先提出的。该问题的描述如下【1 6 】：“给定一个序列的集合，其中每个序列都由事件( 或 元素) 的列表组成，而每个事件都由一个项集组成，给定用户指定的最小支持度阈值 m i n ，序列模式挖掘找出所有的频繁子序列，即，在序列集合中出现频率不小于sup m i ns u p 的子序列。”以此相关的概念将在第2 章进行详细介绍。序列模式挖掘问题提出 后，引起了业界的高度关注，许多后续研究取得了富有成效的结果。 1 2 2 序列模式挖掘的国内外研究现状 序列模式挖掘在1 9 9 5 年被提出后，经过十多年的发展，挖掘算法不断被改进，挖掘 环境不断复杂化。目前，序列模式挖掘算法主要分为两种类型：第一种类型是基于a p r i o r i 性质；第二种类型是基于模式增长。在经典的序列模式挖掘算法中，属于第一种类型的 有：a p f i o r i a l l 10 1 ，g s p 8 1 等；属于第二种类型的有：f r e e s p a n 6 6 1 ，p r e f i x s p a n 9 1 等。模式 增长类型的算法能够有效地避免生成候选集，在很大程度上提高了序列模式挖掘算法的 效率。在数据格式方面，目前大多数算法使用的是水平格式。另外一种数据格式是垂直 格式，使用垂直格式的算法有s p a d e 5 1 ，s p a m 4 9 1 等。经典的序列模式挖掘算法都是在 序列数据库中挖掘所有的序列模式，每一个序列模式包含了组合数级的频繁子序列，如 果序列模式长度较长，那么频繁子序列的数量将非常之大，这不仅浪费了挖掘时间，也 使得挖掘结果存在大量的冗余模式。针对存在冗余模式的问题，人们提出了闭合序列模 式的概念，并提出了相应的挖掘方法，算法c l o s p a n 6 1 、f m c s p 37 1 、c t s p 6 5 】等就是专 门挖掘闭合序列模式的算法。c l o s p a n 是一个高效的闭合序列模式挖掘算法，在模式长 度很长和最小支持度较小时，效率要比p r e f x i s p a n 算法高。c t s p 在挖掘闭合模式的同 时考虑了三种时间约束：最小时间间隔，最大时间间隔，滑动时间窗口。f m c s p 具有 较好的时空效率。解决冗余模式问题的另一个有效方法是约束挖掘。目前已有的约束类 型有：项约束、长度约束、正则表达式约束、持续时间约束、间隔约束等。算法s p i r i t 7 】 是一个基于正则表达式约束的算法，它允许用户通过正则表达式的形式来约束要挖掘的 模式，这不仅提高了挖掘效率，也大大减少了冗余模式，使得挖掘结果更集中于用户的 目标。 串行算法并行化能有效的提高算法的效率，在数据挖掘领域也提出了很多并行化的 算法。c o n g 等人提出了一个基于抽样的并行数据挖掘框梨2 3 1 。序列模式挖掘算法并行 6 基于多序列的序歹q 模式挖掘算法的研究和应用 化，是一种有效提高算法效率的手段。相关算法有m p s p m 1 1 1 、s p s p m 1 1 1 、h p s p m 1 1 1 、 p s p a d e 12 1 、s t p f 1 3 】等。其中，m p s p m 、s p s p m 、h p s p m 是基于a p r i o r i 性质的并行 化算法：p s p a d e 是基于s p a d e 改进而来的；s t p f 是基于树投影的并行化算法。算法 p a r - c s p 2 6 】是一个挖掘闭合序列模式的算法，这是第一个挖掘闭合序列模式的并行化算 法。 经过了十多年的发展，序列模式的挖掘环境越来越复杂，多层、多维、多序列等序 列模式挖掘相继出现，针对动态数据提出了增量式序列模式挖掘。多层序列模式挖掘有 利于挖掘常识性的知识。p l a n t e v i t 等人在2 0 0 6 年提出了一个挖掘层次序列模式的算法 h y p e t 矧。在多维挖掘方面，p i n t o 等人提出t - - 个多维序列模式挖掘算法 3 1 】：u n i s e q 、 s e q d i m 、d i m s e q 。算法u n 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 q d i m 是先挖掘序列模式，然后依据序列模 式构造维度投影数据库，最终在维度投影数据库中挖掘出多维序列模式。d i m s e q 算法 是先挖掘维度模式，然后依据维度模式构造序列投影数据库，最终在序列投影数据库中 挖掘出多维序列模式。在这三个算法中s e q d i m 是可扩展性和效率都较高的一个。国内 也提出了许多多维序列模式挖掘算法，肖仁财等提出了一个多维序列模式s e q m d p 2 9 】 算法，该算法在效率方面优于s e q d i m 。以前的序列模式挖掘主要集中在单序列的挖掘， 在近一两年，基于多序列的序列模式挖掘正在慢慢被重视。c h e n 等人在2 0 0 6 年提出了 一个基于多序列的序列模式挖掘算法m i l e 1 7 】，该算法是将多序列根据时间点转化为单 序列来进行挖掘，并未实现真正意义上的多序列挖掘。在动态数据环境中，传统的序列 模式挖掘算法并不适用，因此，人们提出了增量式挖掘序列模式。算法i n c s p a n 1 9 】是一 个增量式挖掘序列模式的算法，该算法能够在两种增量类型下进行挖掘：一种是基于序 列的项更新：一种是基于序列数据库的序列更新，且i j d n 入新的序列。邹翔等人提出了 基于分布式环境的序列模式挖掘算法f d m s p 5 0 】，该算法具有较好的时空效率和良好的 可扩展性。 随着序列模式挖掘研究的深入，出现了许多新的研究领域和新的模式类型。在文章 5 5 仲提出了一种基于图的后序列模式挖掘任务，并提出了序列模式图模型，该模型能 够描述任何一种序列模式的挖掘结果，并且还可以作为进一步挖掘新模式的基础。在文 章 4 6 3 0 】中提出了使用概念格来进行序列模式挖掘。在文章 6 3 d f l 提出了负序列模式挖 掘，在文章 6 7 d p 提出了模糊序列模式挖掘，这两种序列模式是不同于传统序列模式的 7 厂西大学硕士掌位论文基于多序列的序列模式挖掘算法的研究和应用 新模式类型。 1 3 本文的主要内容和组织 本文共有五章，下面介绍本文的内容结构。 第1 章：绪论。首先详细介绍数据挖掘的数据源，数据挖掘的主要功能( 即数据挖掘所 能发现的模式) ，数据挖掘的应用热点。然后详细介绍序列模式挖掘。最后详细介绍序 列模式挖掘的国内外现状。 第2 章：序列模式挖掘研究概述。首先详细介绍序列模式挖掘的基本概念。然后介绍多 个经典的序列模式挖掘算法和闭合序列模式挖掘算法。 第3 章：基于多序列的序列模式挖掘。首先详细介绍多序列模式的提出和基本概念，详 细介绍基于多序列约束的优化和剪枝技术。然后详细介绍多序列模式挖掘算法 m s ，并进行实验，分析实验结果。最后详细介绍闭合多序列模式挖掘算法prefixspan c m s ，并进行实验，分析实验结果。clospan 第4 章：多序列模式挖掘算法的应用研究。用闭合多序列模式挖掘算法挖掘气象数据， 并分析实验结果。 第5 章：总结与展望。介绍本文的主要工作和创新点，给出多序列模式挖掘的进一步研 究方向。 广西大掌硕士掌位论文基于多序列的序列模式挖掘算法的研究和应用 第2 章序列模式挖掘研究概述 序列模式挖掘是数据挖掘中的一个重要研究方向，序列模式挖掘被广泛地应用于生 物医学、金融分析、电信分析和客户行为分析等领域。近年来，人们在序列模式挖掘领 域进行了大量的研究，取得了很大的进展。本章我们将全面描述序列模式挖掘的基本概 念，以及频繁模式挖掘的发展过程，最后详细介绍多个经典序列模式挖掘算法。 2 1 序列模式的基本概念 序列模式是频繁模式的一种，是频繁模式的应用性扩展。本节将详细介绍频繁模式 的基本概念，然后详细介绍序列模式。 2 1 1 频繁模式 频繁模式( f r e q u e n tp a t t e r n ) 是频繁地出现在数据集中的模式( 如项集、子序列或 子结构) 。频繁模式的挖掘由a g r a w a l 等人在1 9 9 3 年提出，是基于分析购物篮中的关联 规则提出的，目的在于通过研究顾客购物清单中不同商品之间的关联，分析顾客的购买 习惯。发现这样的关联有助于零售商了解哪些商品频繁地被顾客同时购买，从而帮助他 们制定更好的营销策略。频繁项集的挖掘问题是频繁模式挖掘的起源性问题，随后频繁 模式挖掘被扩展应用到了更高级的挖掘环境中，相继出现了序列和结构数据挖掘。虽然 频繁模式中有多种不同的具体模式，但是这些模式都有一个共同的特征：频繁。在挖掘 这些频繁模式时，都需要一个由用户指定的参数，该参数称为最小支持度阈值，只有当 一个模式的支持度不小于最小支持度阈值时，该模式才能称为频繁模式。 2 1 1 1 频繁项集 频繁项集是频繁出现的项的集合。频繁项集的挖掘是关联规则挖掘的第一步，进而 由频繁项集生成关联规则。下面将详细介绍频繁项集相关的概念。 定义2 1 ：全项集。一般用i 表示，l = i i ，1 2 ，1 3 ，i m ) ，是所有项的集合。 定义2 2 ：项集【16 1 。由项构成，是全项集的子集，一般用大写字母表示。a ，。 项集的长度由项集中所含项数量表示，项集的长度一般用，表示。，项集表示长度为i 的项集。 9 基于多序歹g 的序列模式挖掘算法的研究和应用 定义2 3 ：事务【16 1 。事务是一个二元组 ，其中t i d 是事务标识符，a 是项 集。事务一般用r 表示。 定义2 4 ：事务数据库【1 6 】。一般用d 表示，由事务构成的数据库，在事务数据库中 事务的标识符t i d 具有唯一性。 定义2 5 ：支持度( 计数) 1 6 】。支持度( 计数) 一般用s 表示。设有项集a 和事务 数据库d ，则项集a 在d 中的支持度( 计数) 可表示为s u p p o r t d ( a ) ，该支持度( 计数) 等于d 中包含a 的事务的数量。s u p p o r t d ( a ) = i i ( e d ) a ( a b ) ) i 。 支持度计数一般可简称为支持度。 定义2 6 ：最小支持度阂值 16 1 。该值由用户指定，一般用m i n _ s u p p o r t 表示。 定义2 7 ：频繁项集【16 1 。当一个项集的支持度s ，不小于最小支持度阈值m i n _ s u p p o r t 时，该项集称为频繁项集。 表2 - 1 是一个典型的项集事务数据库id ，以该数据库为例，说明概念2 1 2 7 。 表2 1 项集事务数据库i d t a b l e2 - 1i t e m s e t st r a n s a c t i o n sd a t a b a s e i d t i d ( 事务标识符)项集 t 1i l ，1 2 ，1 5 t 21 2 ，1 4 t 31 2 ，1 3 t 4 i l ，1 2 ， 1 4 。 t 51 1 ，1 3 t 6 1 2 ，1 3 t 7i l ，1 3 t 81 1 ，1 2 ，1 3 ，1 5 t 9 i l ，1 2 ， 1 3 项集事务数据库id 中共有5 个项，全项集i = 1 1 ，1 2 ，1 3 ，1 4 ，1 5 ) 。共有9 个事 务，每个事务包含一个项集，事务t 1 的项集a - - 1 1 ，1 2 ，1 5 ，其中项集a 包含了三个 项，是一个3 项集，项集长度为，= 3 。设项集b = 1 1 ，1 2 j ，则项集b 在id 中的支持 度为s u p p o r h) = ，事务t 1 ，t 4 ，t 8 ，t 9 包含了项集b ；设项集 ， )，则项_d(b 4 c = 1 2 1 5 集c 在i _ d 中的支持度为s u p p o r ho ( c ) = 2 ，事务t 1 ，t 8 包含了项集c 。设最小支持度 阈值m i ns u p p o r t = 3 ，则项集b 为频繁项集，而c 为非频繁项集。 1 0 广西大掌硕士学位论文基于多序列的序列模式挖掘算法的研究和应用 在大型数据集中挖掘频繁项集时，往往产生大量的满足最小支持度阈值m i ns u p p o r t 的频繁项集，尤其在m i ns u p p o r t 很小的时候情况更加严重，这是因为如果一个项集是 频繁的，则它的每个子集也是频繁的。大量的频繁项集不仅可能存在大量冗余，也难以 体现挖掘结果的价值。例如：一个包含了1 0 0 个项的频繁项集a = a l ，a 2 ，a 1 0 0 ) ， 它可以产生2 1 0 0 1 个频繁子项集，这样的频繁子项集冗余度非常高，使得挖掘结果缺乏 实际使用意义。为了缓解这个问题，人们引进了闭频繁项集和极大频繁项集的概念。 定义2 8 ：闭频繁项集【l6 1 。设有项集事务数据库d ，项集x 。如果不存在x 的真超 集y 使得y 与x 在d 中具有相同的支持度，则称项集x 在数据库d 中是闭的。如果 项集x 在d 中同时是闭的和频繁的，那么项集x 就可以称为闭频繁项集。 定义2 9 ：极大频繁项集【1 6 】。设有项集事务数据库d ，项集x 。如果x 是数据d 中 的频繁项集，并且不存在这样的项集y ，1 ) 、y 是x 的真超集，x c y 。2 ) 、y 在d 中 是频繁的。则称x 是d 中的极大频繁项集。 a p r i o r i 性质【1 6 】：频繁模式的所有非空子模式也必然是频繁的。该性质是频繁模式挖 掘中的一个重要性质，很多算法都是在这个性质基础上进行的。 下面以项集事务数据库id 为例，说明定义2 8 2 9 。 设项集a = 1 1 ) ，b = 1 2 ，1 5 ) ，c = 1 1 ，1 2 ，1 5 ) ，最小支持度阈值m i n _ s u p p o r t = 2 。 则a ，b ，c 在i _ d 中的支持度分别为s u p p o r t i) = ，) = ，d(c)_d(a 6 s