（计算机应用技术专业论文）序贯模式挖掘技术研究及其在电梯设备维护维修中的应用.pdf

一h 海人学颂i ：学位论文 t h e p o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 摘要 数据挖掘是支持企业决策，处理大量信息的关键步骤之一。随着信息时代的 到来，数据量急速膨胀，数据挖掘有着广泛的应用前景。数据挖掘研究的重点是 提供处理大量复杂数据的高效技术。 序贯模式挖掘是数据挖掘中的一项关键技术。本文在归纳总结常见序贯模式 挖掘算法的基础上提出了三个序贯模式挖掘算法，包括针对多粒度和在不同抽象 层上的序贯模式挖掘、带多个属性的多维序贯模式挖掘以及基于约束的序贯模式 挖掘。文章讨论了序贯模式挖掘在具体领域服务中的应用。 具体而言，本文的工作如下： 1 )提出了一种考虑概念抽象层次的多层序贯模式挖掘算法。该算法考 虑了概念分层，各层不同最小支持度的选择策略。通过输入最小支 持度，该算法能够挖掘出有用的多层序贯模式。文章对各层独立选 择不同的支持度对算法性能的影响进行了实验分析。 2 )提出了一种涉及多个属性的多维序贯模式挖掘方法，并对两个算法 进行了比较实验，分析了属性个数变化与序列长度变化时的两种算 法的不同效率，通过实验分析，对于具体的数据集，给了算法选取 的依据。 3 )提出了一种基于条件约束的序贯模式挖掘的框架算法，用于指导带 约束条件的序贯模式挖掘，算法框架中的约束条件集可以包含任意 的用户指定的限制条件以及条件的优先级。通过提供约束条件及其 优先级，简化挖掘过程，提高挖掘结果的有效性。 4 )当前序贯模式挖掘的研究主要集中在频繁序列的产生上，本文从前 缀子序列的角度提出了序列规则产生方法。通过指定前缀子序列可 信度限制，挖掘出的序列规则具有更好的可理解性。 5 )介绍了一个从实际的i 邑梯设备维护维修数据中发现序贯模式的应 用。该应用通过对设备维护维修数据分析、预处理、数据变换后， 利用上述算法进行序贯模式挖掘。可以发现电梯设备维护维修之 间、维修与维修之帕j 的关系，可以确定过维护与欠维护活动，从而 可以用束指导制定电梯设备的维护策略。 关键词：数据挖掘知识发现频繁序列 序贯模式 第1 l j 】i ( 一l ：海人学硕l ：学位论文 t h e p o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y a b s t r a c t d a t am i n i n gi sak e y s t e p o fd e c i s i o n s u p p o r ta n dl a r g e s c a l e i n f o r m a t i o n p r o c e s s i n g ，i th a sw i d ea p p l i c a t i o n sw i t hd a t ae x p a n d i n gi nt h ec o m i n gi n f o r m a t i o n a g e c u r r e n td a t am i n i n gr e s e a r c hf o c u s e so ne x p l o r i n gt e c h n o l o g yo fp r o c e s s i n g l a r g e - s c a l ec o m p l e x d a t ae f f e c t i v e l ya n d e f f i c i e n t l y s e q u e n t i a lp a t t e r n sm i n i n g i sak e yt e c h n o l o g yo nd a t am i n i n g t h i sp a p e r p r o v i d e st h r e es e q u e n t i a lp a t t e r n sm i n i n ga l g o r i t h m sb a s e do nt h es u r v e yo f c u r r e n t s e q u e n t i a lp a t t e r n sr e s e a r c h ，i n c l u d i n gs e q u e n t i a lp a t t e r n sm i n i n go nm u l t i g r a n u l a r i t y a n dd i f i e r e n ta b s t r a c tl e v e l ，w i t hm u l t i a t t r i b u t ea n db a s e do nc o n s t r a i n t i td i s c u s s e s g e n e r a t i o na b o u ts e q u e n t i a l r u l e i n a d d i t i o n ，t h i sp a p e re x p l o r e sa p p l i c a t i o no f s e q u e n t i a lp a t t e m sm i n i n g i nf i e l ds e r v i c e s t h ec o n t r i b u t i o no f t h et h e s i si sa sf o l l o w s ： 1 ) a m u l t i - l e v e ls e q u e n t i a lp a t t e r n sm i n i n ga l g o r i t h mc o n s i d e r i n gc o n c e p th i e r a r c h y i sp r o v i d e d t h ea l g o r i t h mc o n s i d e r sc o n c e p th i e r a r c h y ，s e l e c t i o ns t r a t e g yf o r m i n i m u ms u p p o r tt h r e s h o l da d a p e dt od i f f e r e n tl e v e l t h ea l g o r i t h mc a np r o d u c e s o m eu s e f u lm u l t i l e v e ls e q u e n t i a lp a a e r n s t h i sp a p e ra l s o a n a l y s e se f f e c to n p e r f o r m a n c eb r o u g h tb yr e s p e c t i v es u p p o r to f e v e r y l e v e l 2 ) a m u l t i - d i m e n s i o ns e q u e n t i a lp a t t e r n sm i n i n gm e t h o dc o n s i d e r i n gm u l t i - a t t r i b u t e i sp r o v i d e d a f t e rc o m p a r e e x p e r i m e n ta b o u t t w o a l g o r i t h m s ，i ta n a l y s e sd i f f e r e n t e f f i c i e n c yo f t h et w oa l g o r i t h m sw i t hv a r i a t i o no fa t t r i b u t en u m b e r sa n ds e q u e n c e l e n g t h i tp r o v i d e s am e t h o da b o u t a l g o r i t h ms e l e c t i o nf o ra c t u a ld a t a 3 ) a f r a m ea l g o r i t h mb a s e do nc o n d i t i o nc o n s t r a i n ti sp r o v i d e d t h ea l g o r i t h mc a n b eu s e dt od i r e c ts e q u e n t i a lp a t t e r n sw i t hc o n d i t i o nc o n s t r a i n t sa n di ta l l o wa n y u s e r - s p e c i f i e d c o n d i t i o n sa n dt h e i r p r i o r i t i e s t h r o u g hp r o v i d i n g c o n s t r a i n t c o n d i t i o n sa n dt h e i rp r i o r i t i e s ，s e q u e n t i a lm i n i n gp r o c e d u r ec a nb es i m p l i f i e da n d p e r t i n e r 哦o f m i n i n gr e s u l t c a nb ei m p r o v e dt os o m ee x t e n t 4 ) c u r r e n ts e q u e n t i a lp a t t e r n sm i n i n gr e s e a r c hm a i n l yf o c u s e so nf r e q u e n ts e q u e n c e s g e n e r a t i o n ，t h i s t h e s i s p r e s e n t s am e t h o do f s e q u e n t i a l r u l e s g e n e r a t i o n c o n s i d e r i n gp r e f i xs u b s e q u e n c e s b y v i r t u eo fc o n f i d e n c eo f p r e f i x s u b s e q u e n c e s ，s e q u e n t i a l r u l e sb e c o m em o r e c o m p r e h e n s i b l e + 5 、s e q u e n t i a lp a t t e r n sm i n i n ga p p l i c a t i o n i ne l e v a t o rm a i n t e n a n c ea n dr e p a i ri s i n t r o d u c e d i tu s e st h ea b o v ea l g o r i t h m st om i n es e q u e n t i a l p a r e r n sa f t e r d a t a a n a l y s i s ，d a t ap r e p r o c e s s a n dd a t at r a n s f o r m a t i o n i tc a ne x t r a c t ss o m e a s s o c i a t i o n sb e t w e e ns c h e d u l e dm a i n t e n a n c ev i s i t sa n du n s c h e d u l e d r e p a i r ， r e p a i r a n d r e p a i r , i n a d d i t i o n ，i t c a n i d e n t i f y o v e r m a i n t e n a n c ea n d u n d e r - m a i n t e n a n c e s oi ti sh e l p f u lt op l a ne l e v a t o rm a i n t e n a n c es t r a t e g y k e y w o r d s ：d a t am i n i n g ，k n o w l e d g ed i s c o v e r y , f r e q u e n ts e q u e n c e ，s e q u e n t i a lp a t t e r n s 第1 v 负 上海大学预i ：学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 第一部分数据挖掘介绍 1 1数据挖掘的定义 第一章引言 数据挖掘( d a t am i n i n g ) 技术是随着数据库技术的迅速发展以及数据库 管理系统的广泛应用发展起来的。由于人们积累的数据越来越多，数据背后 隐藏着许多重要的信息，人们希望借助新的分析方法和工具对其进行更高层 次的分析，以便更好地利用这些数据。目前的数据库系统虽然可以高效地实 现数据的录入、查询、统计等功能，但无法发现数据中隐藏的关系和规则。 由于缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏” 的现象。这就需要有新工具来帮助人们自动地提取和分析隐藏在这些数据中 的知识，以便进行预测，从而更好地支持人们的决策活动。 数据挖掘的定义几经变动，最新的描述性定义是由u s a m a m f a y y y a d 给出的： “在数据中识别有效、新颖、可能有用、且最终可被理解的模式的非 平凡的过程” 1 2 。 作为一种较新的技术分支，由于人们的侧重点不同而形成了对数据挖掘 的广义和狭义两种不同的理解：广义的理解认为数据挖掘即数据库中的知识发 现k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 。即从大规模的数据库中抽取非平凡 的、隐含的、未知的、有潜在使用价值的信息的过程。狭义的理解认为数掘挖 掘是k d d 的一个步骤。 数据挖掘是数据库研究中的一个很有应用价值的新领域，融合了数据 库、人工智能、机器学习、统计学等多个领域的理论和技术。数掘挖掘工具 能够对将来的趋势和行为进行预测。它解决的问题不是数据的访问、数据的 分析等较基础性的问题，而是在决策过程中广泛存在的数据丰富，但信息匮 乏( d a t ar i c h ，i n f o r m a t i o np o o r ) n q 问题。 1 2 数据挖掘过程 一般我们对数据挖掘作广义的理解，即数据挖掘就是数据库中的知识发 现，而不是仅仅将数据挖掘看成是知识发现的一个步骤。 f a y y a d 指出数据挖掘过程通常由以下九个步骤组成：数据准备、数据 选择、数据预处理、数据转换、确定目标、确定知识发现算法、数据挖掘、 模式解释和知识评价。现对这九个步骤逐一进行阐述。 第l 页共6 l 撕 里! 些! 塑! ! ! 堡竺竺堡! ! ! ! ! 些! ! ! 坐! ! 苎垒 1 ) 数据准备了解应用领域的有关情况，包括应用中的先验知识和用 户目标，熟悉有关的背景知识，并弄清楚用户的要求。 2 ) 数据选择根据用户的要求将分布在各处以各种形式存放的数据， 按照需求收集归拢，以统一规范的形式集中存放，然后从数据库中捡索与分 析任务相关的数据。 3 ) 数据预处理主要是对上一阶段产生的数据进行再加工，检查数据 的完整性及数据的一致性，对其中的噪音数据进行处理，对丢失的数据可以 利用统计方法进行填补，去除噪声或无关数据，去除空白数据域，考虑时间 顺序和数据变化等。 4 ) 数据转换将经过预处理后的数据变换成适合挖掘的形式，如数据 项编码、汇总或聚集操作。 5 ) 确定目标根据用户的要求，确定要发现何种类型的知识，因为不 同要求会在具体的数据挖掘过程中采用不同的算法。 6 ) 选择数据挖掘算法根据数据挖掘的功能类型和数据的特点选择相 应的算法。可以通过四项指标即伸缩性、精确性、鲁棒性和可解释性来评价 所选择算法的性能。这包括选取合适的模型和参数，并使得数据挖掘算法与 评判标准相一致。 7 ) 数据挖掘这是整个挖掘过程最关键的步骤，也是技术难点所在。 选取相应的挖掘算法分析数据从数据中提取用户所需要的可能形成知识的 模式模型。 8 ) 模式解释对发现的模式进行解释，去掉多余的不切题意的模式， 转换成某个有用的模式。在此过程中，为了取得更为有效的知识，可能会返 回前面处理步骤中的某些步反复提取，从而提取出更有效的知识。 9 ) 知识评价将发现的知识以用户能了解的方式呈现给用户。这期间 也包含对知识的一致性的检查，以确信本次发现的知识不与以前发现的知识 相抵触。 在上述的每个处理阶段，数据挖掘系统会提供处理工具完成相应的工 作。在对挖掘的知识进行评测后，根据结果司。以决定是否重新进行某些处理 过程，在处理的任意阶段都可以返回以6 i 的阶段进行再处理。图1 1 是u s a m a m f a y y a d 等人给出的处理模型1 3 i 。 圈? 圈秽馏攀馏誊翥四琴圈 图1 1数据库中知识发现的处理过程模型 第2 】i c共6 1 页 ，j ：海人学坝一i ：学位论文 t h e p o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 1 3 数据挖掘分类 数据挖掘是一个交叉学科领域，受多个学科多种技术的影响，数据挖 掘可以按照应用领域、使用技术、挖掘的知识类型、挖掘的数据库类型、 操作等进行如下分类： 按照应用领域分类： 针对生物医学和d n a 数据分析的数据挖掘：针对金融领域数据分析的 数据挖掘：零售业中的数据挖掘：针对w e b 访问的数据挖掘等。 按照使用的技术分类： 基于统计的方法如贝叶斯方法、贝叶斯网络等： 决策树方法很多分类算法都采用决策树方法； 神经元网络方法有些分类算法使用神经元网络方法： 最近邻方法包括很多聚类算法； 遗传算法遗传算法一般被用来发现晟优的模型； 按照挖掘的知识类型分类： 包括特征化、区分、关联、分类、聚类、时间序列模式、孤立点分析、 演变分析、偏差分析和类似性分析等分类。 按照挖掘的数据库类型分类： 有面向关系数据库、事务数据库、面向对象数据库、对象关系的和数据 仓库的数据挖掘等。 按照数据挖掘操作分类： 预测建模即根据训练数据构造预测模型，以预测测试数据。 数据库分割即根据数据库对象的相似度将数据库分割成段，例如聚类 分析。 链接分析即数据库对象之阳j 或者对象组之间的关联，前者称关联规 则，后者称为顺序模式发现。 偏差检测即发现少量数掘的异常情况例如局外数据( o u t i e r ) 检测。 1 4 数据挖掘研究的发展 数据挖掘的研究是应用驱动的，它作为一门单独技术出现是由于大量电子数 据的出现。在数据挖掘技术兴起以前数据的分析大都是手工统计的方法。此时 的分析过程是：理解数据，统计提交报告。然而，随着数据采集技术的发展和 超大规模数据库、数据仓库的出现，一方面数据属性越来越多，另一方厩数据的 规模也越来越大，对数据进行分析的复杂度越来越高，手工方法不再适用。统计 方法决策者又难于掌握，于是需要计算机自动从大量的数据中提取知识。 第3 页菸6 i 页 ：海人学硕j ：学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 随着对于数据挖掘的需求的增多，越来越多的研究者投身于该领域的研究。 1 9 8 9 年到1 9 9 4 年召开了四届“数据库中的知识发现研讨会( w o r k s h o p o n k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) ”，该研讨会自1 9 9 5 年开始演变为“知识发现 与数据挖掘：学术年会( c o n f e r e n c eo nk n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 。 从1 9 9 9 年丌始，a c m 组织成立s i g k d d ( s p e c i a li n t e r e s tg r o u p o nk d d ) ，每年包含 数据挖掘或者知识发现主题的学术会议也越来越多。 随着数据挖掘技术的成熟和应用推广，很多软件提供商推出了相应的数据挖 掘软件包，系统或者解决方案。s a s ，s p s s ，i b m ，o r a c l e ，m i c o r s o f t 等软件公司 都开始涉足数据挖掘市场。 加拿大s i m o nf r a s e r 大学“智能数据库系统实验室”开发的d b m i n e r 就是一个 商用化的数据挖掘系统，该系统包括许多先进的挖掘算法，并有很多优秀的特点， 底层的挖掘细节对用户完全透明；挖掘的知识类型多样，从关联规则，序贯模式， 发现驱动的分类、聚类、预测、o l a p 分析器等，作为d b m i n e r 的扩展，已经研制 了若干专业的数据挖掘系统原型：g e o m i n e r 、m u l t i m e d i a m i n e r 、w e b l o g m i n e r ； m m 的a l m a d e n 实验室的q u e s t 项目也在数据挖掘领域取得了重大的研究成果，该 项研究包括了对关联规则，序列模式( s e q u e n t i a lp a t t e r n s ) ，分类以及时间序列聚类 ( t i m e s e q u e n c ec l u s t e r i n g ) 的研究。其代表性的产品有：d b 2i n t e l l i g e n tm i n e r f o r d a t a ；s a s 的e n t e r p r i s em i n e r ；此外，美国宾夕法尼亚大学的数据挖掘研究小组 也在这方面取得了显著成果，其主要研究包括：利用注释和文本对数以百万计的 文章进行聚类和分析；从多家乞援的病人数据库中发现可以提高医疗质量和降低 医疗费用的模式：基于d n a 序列预测基因模式等等。目前世界上知名的数据库大 公司如i b m ，o r a c l e ，s y b a s e 等都已在不同程度上将数据挖掘技术结合到其对应的 数据库产品中，使得数据库功能向智能化方向边出了重要一步。 1 5课题研究的意义 数据挖掘技术从一- 丌始就是面向应用的，序贯模式挖掘作为数据挖掘的一个 重要分支，应用领域越来越广，典型商业问题包括：数据库营销( d a t a b a s e m a r k e t i n g ) 、网络入侵检测( n e t w o r k i n t r u s i o nd e t e c t i n g ) 【4 ，w 曲同志挖掘( l o g m i n i n g ) ，d n a 序列模式( d n as e q u e n t i a lp a t t e r n s ) 研究等。 由于不同应用的需要，运用数据挖掘技术时，希望挖掘出满足不同需求的序 贯模式。研究多粒度、多维、基于约束的序贯模式，可以一定程度上解决实际中 的一些问题。对数据集的多粒度挖掘，能够得到不同抽象层次上的模式，这些模 式可以有目的地针对不同的用户：数据库中的数掘都会涉及到多个属性，研究f 确反映这些属性特点的多维模式是有意义的，它能更清晰地进行预测；基于约束 地挖掘可以给用户更大地自由度，让用户选择他们所关注地目标，使得数据挖掘 第4 负共6 1 j ：( ，i ：海夫学坝：i ：学位论义 t h e p o s t g r a d u a t et h e s i so f s h a n g h a iu n i v c r s i | y 地过程更有效。 将序贯模式挖掘的思想和方法应用于领域服务之中，为设备维护维修增添了 一类新的强有力的工具，也为领域服务问题提供了一种新的思路，与传统的统计 分析相比，数据挖掘方法显得更加简洁和直观。在领域服务的实践中，序贯模式 挖掘是一项具有实际意义的任务，它能发现大量服务数据中隐含的序列知识。 1 6本文组织 以往对数据挖掘和知识发现的研究多是在理论上对算法的提出及改进，而实 际将知识发现整个过程实际应用于某一领域相对较少。本文通过对序贯模式挖掘 的分析及研究，通过对领域服务数据运用序贯模式挖掘技术，包含了数据选择， 原始数据的预处理，到决定挖掘任务，实施挖掘算法，来发现序贯模式模式的完 整过程。具体安排如下： 第一章概述了数据挖掘的定义，分类，挖掘过程说明及其研究现状。简要 说明了本课题研究的意义。 第二章具体讨论了序贯模式挖掘的基本概念，挖掘的一般步骤，常见算法 比较以及当今面临的问题。 第三章针对常见的序贯模式挖掘算法，提出来改进的三种序贯模式挖掘算 法。 第四章探讨了序贯模式产生问题。当前研究主要集中在频繁模式的产生上， 本章从另一个角度探讨了序列符号化表示及规则产生时的的黄信度衡量问题。 第五章对于真实的电梯设备维护维修数据，针对序贯模式挖掘的特点进行 属性转换，数据不一致的处理，缺省数据的处理等方面的数据预处理工作 作了讨论。 第六章针对特定领域中服务数据，给出了如何运用前述的挖掘算法，解决 设备维护维修中的问题。 第七章全文的总结，这一章对全文的内容做了一个较为全面的概括，并在 此基础上提出了对将来的工作的展单。 第5 负共6 【 【二海人学埘l ： ：学位论文 t h e p o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 第二部分序贯模式挖掘及其算法研究 第二章序贯模式挖掘 2 1 序贯模式挖掘的基本概念 序贯模式挖掘( s e q u e n t i a lp a t t e r n sm i n i n i g ) 是在给定的序列集中挖掘所 有满足用户指定最小支持度和簧信度的摄长频繁序列的过程。它是数据挖掘技术 中一个非常重要的研究课题和领域。它首先是由r a k e s ha g r a w a l 、r a m a k r i s h n a n s r i k a n t 针对超市中购物篮数据的分析提出来的。序贯模式挖掘是这样一个过程， 它对数据集进行分析，并识别出隐藏在这些数据中的趋势。一个典型例子就是： 租“s t a rw a r s ”的顾客，以后会租“s t r i k e sb a c k ”，然后会租“r e t u r no f t h ej e d i ” 5 。序贯模式挖掘具有广阔的应用领域：像客户购买行为模式预测、w e b 访问模 式预测、疾病诊断、自然灾害预测、d n a 序列分析等。 数据挖掘起初主要是研究关联规则，由关联规则可以指导关联分析，找出事 务中项集之间的联系。它所考虑的是一次事务中项与项之间的关联关系，譬如一 次购买中购买某物品可能会购买另一物品，发现的是事务内的模式。对于序贯模 式挖掘而言，它考虑的是事务间的模式，按照关联规则的观点可以看作是在时间 轴上事务之间的关联关系。譬如，一次事务的出现可能会影响下一次事务的出现。 序贯模式挖掘分析及挖掘过程与关联规则是基本一致的，先挖掘频繁集，然 后产生关联规则序贯模式它们也各自具有针对多种不同应用的挖掘算法。然而， 序贯模式中包含有时问信息，在挖掘处理时是要考虑时间因素的。 下面说明本文将要用到有关概念、性质和定理，给出相关的形式化定义。 假设我们有交易数据库d ( 购物篮数据为例) ( c u s t o m e r _ i d ， t r a n s a c t i o nt i m e i t e m s e t ) 分别为顾客标识号，交易时间，物品集。 定义项集( i t e m s e t ) 假设i = ( i ，i 。i ，i 是各种项( i t e m ) 组成的集合。 一个项集x = i 、ii 。i ，1 k ” ，它是i 的子集，记做x g i 。 定义序列( s e q u e n c e ) 不同项集( i t e m s e t ) 的有序排列，序列s 可以表示为 s = ，s ( 1 蔓f ， 第6 虹共6 i 负 h 海人学顿j ：学位论文 t h e p o s t g r a d u a t el h c s i so f s h a n g h a iu n i v e r s i t y 如果存在整数1sj 。 j ! m i n s u p p 1 ，则x 在第l 层是频繁项集( l a r g ei t e m s e t ) 如果序列a 的支持 度s u p p o r t ( a ) m i n s u p p 1 ，则a 在第l 层是频繁序列( l a r g es e q u e n c e ) 频繁序 列实际就是频繁项集的有序表序列模式是具有最小支持阈值的最大序列 定义强序列满足最小支持度闽值和最小置信度的序列。 定义超集设x = i ，i ! i 。 为数据项集，x = ，j 。j n 为x 的超集( 父 集) ，如果对任意的k = 1 ，2 ，n ，有i 。，= j 。或在概念层次树中j 。是i t ，的祖先。 性质1 如果x 为频繁项集，则x 的超集x 也是频繁项集， 证明对任意交易t ，若t 包含x ，则t 必然包含x 因此 s u p p o r t ( x ) s u p p o r t ( x 1 定义超序列设序列s = ，s = 称为s 的超 序列，如果对任意的k = 1 ，2 ，n ，有y ，= x 。，或y 。是x 。，的超集。 性质2 ：如果s 为频繁序列，t ) 1 l js 的父序列s 的也是频繁序列。 证明：设有序列s = ( a 。a 。a 。) ，父序列s = ( b ，b 。b 。) ，对任意的顾客 序列c = ( t 。，t ! ，t 。) ，若c 包含s ，则存在i 。 i ! i 。使得a t 。，赴 t 。a 。m 由性质i 可知，b t 。，b ：s t 。b 。t 。即c 包含s ，因此s u p p o r t ( s ) ss u p p o r t ( s ) 箱7 页共6 i 页 ，l ：海人学现i ：学位论义 里! 望! 婴! ! ! ! ! ! ! 竺! ! ! ! ! ! ! ! ! ! ! 旦! ! 兰! 生 性质3 如果序列s 的超序列s 支持一个序列a ，则s 也支持a 。 证明：设序列s = ( a ，a 。a 。) ，超序列s = ( b ，b 。b 。) ，序列a = ( c 。c 。c 。) ， 如果s 不支持a ，一定jc a ( 1 f k ) ，使得对v a es ( 1 f h ) ，c ( m a 。，由性 质2 ，有c 仨b ( 1 i 一) ，矛盾。 性质4 超模式中的序列至少包含子模式中的序列 定理2 i所有频繁项集的非空子集都是频繁项集。 可以证明之：假设对于大k 项集i 存在非空子集x ( 去掉项a ，即i = x u a ) 不是大项集，根掘定义，项集x 不满足最小支持度闽值r a i ns u p ，即 s u p p o r t ( x ) m i ns u p 。如果项a 添加到x ，则结果项集( 即x u a ) 也不可 能是大项集，即s u p p o r t ( x u a = i ) m i n s u p 。与i 是大项集矛盾。所以定理 成立。 定理2 2所有频繁序列的非空子序列都是频繁序列。 证明：设s 为频繁序列，s 为长度不为零的s 的予序列，假设s 不是 频繁序列( s u p p o r t ( s ) m i ns u p ) ，则向s 中的元素添加项，使得新的序 列与s 相等，可知s u p p o r t ( s ) r a i ns u p ，与s 为频繁序列矛盾。 2 2 序贯模式挖掘算法简介 下面分析几种典型的序贯模式挖掘算法 ( 1 ) 一般序贯模式挖掘 5 中提出了算法a p r i o r i a l 。a p r i o r i s o m e 。d y n a m i c s o m e 。算法a p r i o r i a l l 是经典的关联规则算法a p r i o r i 的变形。在关联规则中的频繁项集在这里变成频 繁卜序列。也是产生候选决定频繁序列然后作为种子集进行下次候选序列的产生。 算法a p r i o r i s o m e 只是和a p r i o r i a l l 在”序列阶段”不同，a p r i o r i a l l 中， 计算所有的频繁序列，包括非最大序列。这些非最大序列在最大序列阶段时是必 须被删除的。a p r i o r i s o m e 把“序列阶段”细分为前推阶段和回溯阶段。前推阶 段( f o r w a r dp h a s e ) 只找出具有一定长度的频繁序列，而回溯阶段( b a c k w a r dp h a s e ) 找出所有剩余的频繁序列。 算法d y n a m i c s o m e 的思路和a p r i o r i s o m e 相比，多了一个初始化阶段。初始 化阶段预设一个步长s t e p ，控制哪些长度的序列丌始计数。d y n a m i c s o m e 不如 a p r i o r i a l l 和a p r i o r i s o m e 效率高，主要是它在前推阶段产生太多的候选，后两 者的优点是可以避免计数很多非最大序列，实验表明性能较好。 ( 2 ) 泛化的序贯模式挖掘算法 g s p 算法考虑了序列中元素问的时问间隔，事件重叠窗口，也简要讨论了项 的分层问题。算法中采用了特殊的数据结构，实验表明g s p 效率比类a p r i o r i 高。 ( 3 ) 基于树投影的挖掘算法系列 第8 砥共6 i 负 上海人学坝i i 学位论文 t h e p o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i t y 文献 8 提出一种新的算法f r e e s p a n 。它是一种基于频繁模式投影的序贯模 式挖掘。其基本思想就是：把频繁序列的挖掘和频繁模式的挖掘结合起来，并投 影序列数据库以精简查找空间，缩减候选子序列的产生。 f r e e s p a n 使用频繁项递归地把序列数据库投影到一系列更小的数据库中，然后 在每一个小的投影数据库中增长子序列的长度。f r e e s p a n 仅需在原始数据库上进 行三次扫描，扫描的次数不再与序列的最大长度相关。大大改善了算法性能。 文献 9 讨论了另一种投影算法p r e f i x s p a n ，它的基本思想是：仅仅检查一个 模式的前缀子序列，并投影它们相应的后缀子序列到投影数据库中，通过仅仅考 察局部的频繁序列来使序贯模式增长。为了提高算法性能，文中相应提出了两种 投影数据库的方法。 ( 4 ) 并行序贯模式挖掘算法 文献 1 0 中提出一个并行序贯模式算法族，它是类似于g s p 的并行版本，并 作了一些扩展。其特点是：输入数据是分布的，每一个处理器都有单独的候选序 列的哈希树数据结构。根据数据分布的不同分成三种算法e v e s 、e v e r 和e v e c 。 e v e s 把所有的序列完全平均分摊在不同的处理器上，当短的数据序列数量较大 时比较适合。e v e - r 分解每一个序列，以使每一处理器上的事务数相当；e v e c 也 是分解每一个序列，以使每一个处理器上的事务数相当，当事件时间窗口内长序 列较少时它比较适用。 ( 5 ) 统一的序贯模式挖掘框架算法 文献时1 提出了一种独特的统一的算法框架，其算法思想也是基于g s p 的。 输入序列被看成三列数据的序列：对象( 相当于超市数据中的顾客) 、时间、事件 列( 相当于顾客交易) ，对于序贯模式的时问限制及结构表示采用有向无环图。 另外对支持度的计算采用不同的计数方法，来满足不同条件下对序贯模式的不 同解释，这样对序贯模式的解释提供了很大的弹性。它在单一的算法框架下， 提供了对序列出现次数的多种计数方法。并提出了一种基于事件序列的模式发 现。在有向无环图中，为了对规则解释更清楚，增加了边限制、节点限制、全 局限制等限制。 2 3当今面临问题与今后研究热点 序贯模式挖掘是近年来知识发现很活跃的一个研究领域，虽然取得了一些进 展，但下面的问题值得更进一步的研究。 ( 1 ) 研究更高效的的算法。虽然现在已有很多优良的挖掘算法，机器性能 也越来越好，但对于同益膨胀的数据量需求，算法有时候仍然是瓶颈，像并行算 法研究就是一个很有意义的研究课题。 ( 2 ) 序贯模式的挖掘主要是为了应用，解决实际中的问题，如何将发现的 第9 页共6 i 页 j ：海人学硕j ：学位论文 t h ep o s t g r a d u a t et h e s i so f s h a n g h a iu n i v e r s i h 序贯模式、序列规则应用到实际领域中，进行交互式的序贯模式挖掘，不断进行 基于约束的挖掘，提供额外的控制方法，允许用户说明和使用约束( 结合背景知 识或领域知识) ，引导挖掘系统对感兴趣的模式更加有效的搜索等也是值得关注的 课题。 ( 3 ) 应用系统集成以及可扩展性一个单独的挖掘系统如果不同具体的应 用系统集成相结合，将毫无意义。数据挖掘应该和数据库管理系统或m i s 、电子 表单、实时传感采集系统、特别时决策支持系统集成在一起。 ( 4 ) 研究和开发可视化挖掘技术，提高模式的可理解度。 ( 5 ) 知识的更新维护由于数据的动态变化常常会使得以前发现得模式不再 有效，特别是数据库可能增加，删除或改变变量。发生这些情况时则要求设计数 据挖掘系统的过程中必须考虑知识的更新维护，如怎样解决知识冲突。另外数据 的动态性也提出了新的数据挖掘问题：趋势或变化模式发现任务以及主动数据库 挖掘研究。 2 4本章小结 本章简要地叙述了序贯模式挖掘的一些基本概念，分析了序贯模式挖掘的几 种常见算法。对当前序贯模式挖掘所面临的问题作了简短的说明，展望了未来序 贯模式挖掘的研究方向。 ， 第1 0 页共6 i 页 1 ：海人学坝j ：学位论文 t h ep o s t g r a d u a t e t h e s i so f s h a n g h a iu n i v e r s i t y 第三章三种类型的序贯模式挖掘算法 序贯模式挖掘是数据挖掘中的一项重要技术，同其他数据挖掘技术一样，针 对不同问题域的特点需要有与之相适应的挖掘算法。本章针对多粒度、多维属性 和带约束的情况提出了三种序贯模式挖掘算法。 3 1 多层序贯模式挖掘 3 1 1 多层序贯模式筒述 多层序贯模式挖掘可以在概念的不同抽象层次上挖掘。这种在不同抽象层上 发现的序贯模式可以针对不同的特定用户。比如，管理决策人员会对更加抽象的 模式感兴趣，便于进行宏观决策而一般的用户( 譬如维护服务人员) 对自己责 任范围内的更加具体的模式感兴趣。 假设有如图3 1 所示的概念分层图，可以有这样的序贯模式： c o m p u t e rjs o f t w a r e ( s u p p o r t ：o 2 0 ，c o n f i d e n c e ：o 6 0 ) d e s k t o pc o m p u t e rj e d u c a t i o n s o f t w a r e ( s u p p o r t ：o 1 5 ，c o