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

中山大学硕士论文 序列模式挖掘算法研究 论文题目：序列模式挖掘算法研究 专业：计算机软件与理论 硕士生：贺桂娇 指导老师：印鉴教授 摘要 关联规则是数据挖掘中比较活跃的研究方向之一，它反映了大量数据中项 目之间有趣的关联或联系，一个比较经典例子就是“9 0 的客户在购买面包和 黄油的同时也购买了牛奶”，数据库中的每个项目以平等一致的方式来处理。而 加权关联规则则考虑了各个项目的不同的关注度，从一定程度上提高了传统关 联规则的兴趣度。序列模式是在关联模型中增加了时间属性，把数据之间的关 联性与时间联系起来，寻找的事务之间在时间上的先后次序关系，预测将来可 能出现的值的分布。 目前，对序列模式挖掘算法的研究很多，主要集中在如何提高算法的时间 效率和减少空间上的开销。但在庞大的交易数据库里，这些算法很容易产生几 百、几千个序列模式，如果每个序列都要实验一遍，代价太高了且让人无所适 从，如何从事务数据库中找出商家更感兴趣的精简的“黄金”序列就成了当务 之急。因此本文在序列模式的基础上提出了偏爱度，并结合加权的概念，提出 了f s p a m 算法，经原型验证，该算法挖掘出的序列模式更精简且更有效。 其次、序列模式的经典算法的主要思想都是最开始从数据库中找到所有长 度为l 的频繁序列，由此产生长度为2 的频繁序列集，接着得到长度为3 的频 繁序列集，如此反复直到数据库不再发现频繁序列为止。象这样重复扫描数据 库，造成系统沉重的负担而导致效率不佳。本文利用邻接矩阵来记录事务数据 库中2 项频繁序列，进而生成需要的频繁模式。可以大大减少扫描数据库的次 数，使系统的性能得到改善。 关键字：关联规则，加权，偏爱度，序列模式 中山大学硕士论文 序列模式挖掘算法研究 t i t l e ：r e s e a r c ho ns e q u e n t i a lp a t t e r nm i n i n ga l g o r i t h m s m a r j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：h eg u i j i a o s u p e r v i s o r ：y i nj i a np r o f e s s o r a b s t r a c t a s s u e i a t i o nr u l ei so n eo ft h ep r e v a i l i n gs t u d yo r i e n t a t i o n si nd a t am i n i n g ， w h i c hr e f l e c t si n t e r e s t i n gc o r r e l a t i o no rl i n ka m o n gn u m e r o u sd a t ai t e m s 0 n e t y p i c a le x a m p l ei st h a t9 0 c u s t o m e r sp u r c h a s em i l kw h i l ep u r c h a s i n gb r e a da n d b u t t e r , e a c hi t e mi nt h ed a t a b a s ei sd e a l tw i t l li nt h es a n l ew a y y b ti nw e i g h t a s s o c i a t i o nr o l e h i g h l i g h td e g r e eo fe a c hi t e mi sc o n s i d e r e d , a n di n t e r e s ti n t r a d i t i o n a la s s o c i a t i o nr u l ei si m p r o v e dt os o m ee x t e n t f r e q u e n ts e q u e n t i a lp a t t e r n s a d dp r o p e r t yo ft i m et oa s s o c i a t i o nm o d e i ，i n t e g r a t et i m ew i t hc o r r e l a t i o nb e t w e e n d a t a s e e ka f t e rt h et i m es e q u e n c eo f e v e n t sa n df o r e c a s tt h ed i s t r i b u t i o no f v a l u e s a tp r e s e n t , s t u d i e s0 1 1f r e q u e n ts e q u e n t i a lp a t t e r nm i n i n gc a l c u l a t i o nm a i n l y f o c u so nh o wt oi m p r o v et i m ee f f i c i e n c ya n dh o wt om i n i m i z es p a c eo c c u p y i n g b u t t h i sc a l c u l a t i n 2m a yp r o d u c eh u n d r e d so re v e nt h o u s a n d so ff r e q u e n ts e q u e n t i a l p a t t e r n sf r o mn u m e r o u sd a t a b a s e ，i fe a c ho ft h e mn e e d s t ob et e s t e d ，i tw i l lc o s tt o o m u c h s oi ti se s s e n t i a lt os e e kt h eg o l d e ns e q u e n c ew h i c hc u s t o m e r sa r em o s t i n t e r e s t e di n n l e r e f o r ep r e f e r e n c eb a s e do nf r e q u e n ts e q u e n t i a lp a t t e r n si sr e f e f r e d t oi nt h i st h e s i s c o m b i n e dw i t l lt h ec o n c c ：p to fw e i g h t f s p a mc a l c u l a t i o ni sp u t f o r w a r d t h r o u 【g hp r i m a r yt e s t 舶q u e n ts e q u e n t i a lp a t t e r no u to ft h i sc a l c u l a t i o ni s m o r ec o n c i s ea n dm o l 弓e f f e e t i v e s e c o n d l y , t h em a i nt h o u g h t sa b o u tc l a s s i cc a l c n l a t i o no ff r e q u e n ts e q u e n t i a l p a t t e r n sb e g i nb yf i n d i n ga l lt h ef r e q u e n ts e q u e n c e sw i t h l l e n g t h , r e s u l t i n gi n f r e q u e n ts e q u e n c eg r o u pw i t l l2l e n g t h s t h e n w i t h3l e n g t h sa n ds oo na n do n ，u n t i l n om o r es e q u e n c ec a i lb ef o u n di nt h ed a t a b l e s or e p e a t e ds c a n so nd a t a b l e b u r d e nt h es y s t e m w h i c hr e s u l t si nl o we f f i c i e n c y i nt h i st h e s i s ，a d j a c e n ta r r a y s a r eu s e dt or e c o r dd a t a b a s ef r e q u e n ti t e r n s e t s ，f u r t h e rt op r o d u c ef r e q u e n c ym o d e ，t o r e d u c ed a t a b a s es c a n sa n di m p r o v et h ep e r f o r m a n c eo ft h es y s t e m k e yw o r d s ：a s s o c i a t i o nr u l e ，w e i g h t ，f r e q u e n ts e q u e n t i a lp a t t e r nm i n i n g ，f r e q u e n t i t e n l s e t s i l 序列模式挖掘算法研究 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不包含任何其他个人或集体已经发表或 撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：能喻 日期：少叼年o 月口日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规 定，即：学校有权保留学位论文并向国家主管部门或其指定 机构送交论文的电子版和纸质版，有权将学位论文用于非赢 利目的的少量复制并允许论文进入学校图书馆、院系资料室 被查阅，有权将学位论文的内容编入有关数据库进行检索， 可以采用复印、缩印或其他方法保存学位论文。保密的学位 论文在解密后使用本规定。 学位论文作者签名：1 赂至碲导师签名：杉甲髟 日期：2 司年归月d 日日期：翊年l f 月琴日 o 。 中山大学硕士论文 序列模式挖掘算法研究 1 1 论文的研究背景 第1 章绪论 在2 0 世纪9 0 年代，随着计算机应用的普及，信息技术得以快速发展，并 在各个行业中逐渐被广泛应用，为企业竞争态势构成了不可忽视的影响。一方 面，由于数据库管理系统的广泛应用，各个领域每时每刻都在产生大量的数据。 根据一项研究显示，全世界的数据量每二十个月就会番一番l lj ，在这些海量的 数据中，往往蕴含有丰富的、对企业有指导意义的知识。另一方面，由于计算 机硬件价格的逐渐下降、信息技术的普及化、数据存储、处理以及传输已成为 任何企业都可以负担的投资，企业很难单靠传统的信息管理方式如简单的数据 录入、查询、统计等事务性处理过程建立起竞争优势【2 j 。企业急需一种能从海 量数据中发现潜在知识的“工具”，以解决“数据爆炸与知识贫乏”的矛盾。而 对以上的挑战，数据挖掘和知识发现技术应运而生，并得到蓬勃的发展【，越 来越显示出其强大的生命力。 数据挖掘是从大量的、不完全的、有噪音的、模糊的、随机的实际数据中， 提取隐含在当中人们不知道的潜在有用的信息和知识的过程1 4 j 。它的一个重要 的应用是关联规则的发现。关联规则发现是在数据库中寻找数据对象间的关联 模式【5 】，例如，“在购买面包和黄油的顾客中，9 0 的人同时也购买了牛奶。”就 是一种关联模式，早期主要用于零售业交易数据分析，以进行物品更合理的摆 放，最终提高销售量。因此，该方法有时也直接称为“货篮分析”。 序列模式是从关联规则中演变而来，序列模式发现是在数据库中寻找基于 一段时间区间的关联模式【6 】，例如，“在某一时间购买个人电脑的所有顾客中， 6 0 会在3 个月内购买应用软件。”就是一序列模式。序列模式同关联模式非 常相似，区别在于序列模式表述的是基于时间的关系，而不是关于数据对象间 的关系。在实际应用中，多数数据集中的数据都带有时间特征，这类数据称为 时态数据( t e m p o r a ld a t a ) ( ”，例如，某顾客在超市内某时间段内购买商品的序列、 天气数据和生产数据等。 序列模式挖掘最初是由于在零售业中的应用而发展起来的。现在，序列模 式已经应用到了科研和商用的其他许多领域。例如，在医疗领域，一个病人每 看一次病，他的症状就可以组成一次事务，而这个病人的所有看病记录( 即所有 事务) 就可以形成一个“症状序列”，从所有病人的症状序列中挖掘出一个模式， 这个模式将会帮助医生诊断这些症状预示着何种疾病。序列模式挖掘是数据挖 掘中一个重要的、富有挑战性的研究课题，在实际中具有广泛的应用，包括顾 客购物模式分析和互连网访问模式分析，以及序列分析或者其它与时间相关的 处理过程分析，例如，科学实验、自然灾难事件、疾病防治、d n a 序列、股票 序列的分析等。 中山大学硕士论文 序列模式挖掘算法研究 1 2 论文选题的意义 在零售业中对顾客的购买行为进行序列分析，那么就有可能发现顾客的购 买习惯和购买特点。如果充分的利用顾客的这些购买特点，可以帮助许多商家 制定销售决策，如促销分析、交叉购物、引导消费等，增加商品的销售量，提 高企业的效益。 通常，一个庞大的事务数据库经过挖掘引擎的筛选和处理后会生成大量的 序列模式，并以序列的形式提供给最终用户，然而，事实证明这些序列的可靠 性和有趣性并不像想象中那么完美，现有的许多序列的挖掘方法耗费很长的时 间生成序列模式，而产生的序列有大量用户不感兴趣的( 比如是显然的或不相 关的) ，有的甚至是虚假的，当然也有用户确实需要的序列，那如何从大量的序 列模式中去掉无用、虚假的序列，挖掘出精简有效的黄金序列是当务之急。 其次，借用其他工具提高传统算法的效率，也是大多数研究员一直在讨论 的问题。 因此，挖掘出精简、高效的序列模式并应用到零售业中，产生有意义的信 息，并将这些信息归纳作为企业决策时的参考，最终使企业具有更强大的竞争 优势，这将会是一份重要意义和富有挑战性的工作。 1 3 序列模式挖掘的国内外研究现状 序列模式挖掘m 1 的概念首先是由r a g r a w a l 等人在1 9 9 5 年对超市购物 篮数据的分析提出的，此后人们不断地研究和改进在时间序列数据库中挖掘序 列模式和其他频繁模式的算法。现有的序列模式挖掘算法主要分为两类。第一 类是基于r a g r a w a l 和r s r i k a n t 在1 9 9 4 年提出的a 砸o r i 特性【9 l 的算法。 a p d o r i 特性首先应用在关联规则挖掘中，其基本思想是频繁模式的子序列也一 定是频繁模式。基于a p d 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 算法瑾j 、g s p 算澍”j 等；有采用垂直数据格式( v e r t i c a ld a t af o r m a t ) 的算法，如s p a d e 算法【i l j 等。第二类是j h a n 等人提出的基于模式增长 ( p a t t e m g r o w t h ) 策略的算法，如f r e e s p a n 算法【1 2 】、p r e f i x s p a n 算法【1 3 】等。另外， c a n t u n e s 等人提出了s p a r s e 算法【l ”，该算法的主要思想是将候选序列的产 生和在投影数据库空间搜索结合起来，每一步在产生出频繁元素后，通过增长 长度寻找模式。以上这些算法都是在静态的序列数据库中挖掘所有的序列模式， 它们都属于一般的序列模式挖掘算法。 但是，由于一般的大型数据库都是随着时间的变化而不断更新的，当数据 库发生变化之后，原先挖掘的一部分序列模式可能不再满足最小支持度，同时 还可能有新的序列模式出现，如果使用上述算法，就必须在更新后的序列数据 库中重新进行挖掘。在处理具有海量数据的大型数据库时，对整个数据库重新 执行一般的序列模式挖掘算法显然是低效的。在这种情况下，一系列增量式序 列模式挖掘算法被提出，其基本思想都是尽可能地利用已发现序列模式的信息 来发现新数据库中的序列模式，从而提高模式挖掘的效率。m a s s e g l i a 等人提出 了用于序列模式增量式更新的i s e 算法【l5 1 ，该算法利用已有对原始数据库的挖 2 中山大学硕士论文序列模式挖掘算法研究 掘结果来产生候选项目集，减少了候选项目集的规模。但没有降低对整个数据 库的扫描次数，算法的i o 消耗仍然很大。周斌等人提出了在数据库更新的情 况下的序列模式增量式挖掘算法i m s p ，其主要思想是利用序列的c t i d 表来 加速挖掘过程。但该方法要求预知前次挖掘的每个序列模式的c t i d 表，且在 计算过程中将产生关于每个候选序列的c t i d 表。当数据库规模很大时，对存 储空间的消耗很大。等等。 此外，当前国内外学者还广泛关注以下的研究方向。1 ) 约束( c o n s t r a i n e d ) 序列模式挖掘在很多序列模式挖掘任务中，用户不需要找出数据库中所有可能 存在的序列模式，而是加入一定的约束，找出用户感兴趣的序列模式【1 6 】。如 a g r a w a l 等人将序列模式挖掘问题加以泛化，引入了时间约束、滑动时间窗口 ( s l i d i n gt i m ew i n d o w ) 和分类约束，并提出了g s p 算法。2 ) 闭合( c l o s e d ) 序列 模式挖掘当序列模式很长时，由于每一个序列模式包含了组合数级的频繁子序 列，挖掘所需的开销很大，然而在实际应用经常需要挖掘特别长的模式，如d n a 序列。闭合序列模式挖掘研究如何挖掘满足不存在与其具有相同支持度的超序 列条件下的序列模式。3 ) 多维( m u l t i d i m e n s i o n ) 序列模式挖掘在序列模式中 融合感兴趣的多维信息，在考虑与时间戳相关属性的同时，挖掘多维信息中感 兴趣的模式，将得到能提供给用户更丰富信息的多维序列模式。h p i n t o 等人提 出的u n i s e q 算法能有效地挖掘多维序列模式，多维序列模式挖掘是复杂数据 类型挖掘的一个前沿研究领域，有着极为广阔的应用前景。 综上所述，可以看出如何在大型序列数据库中挖掘更高效、更实用价值的 频繁序列模式是有待于进一步研究的课题。 1 4 本文的主要研究内容 数据挖掘是近年来兴起的多学科相互融合的应用技术，广泛地应用于各个 领域，特别是金融业、商业管理、市场分析以及科学研究等领域。序列模式是 数据挖掘研究的重要内容之一，人们对于它的理解认识与研究越来越重视，本 文主要应用数据挖掘中有关理论，对序列挖掘的挖掘算法作一些探索性的研究。 本文的主要研究内容如下： 对数据挖掘技术产生的背景作了概括性的描述，然后介绍了数据挖掘的基 本概念和定义，接着说明了数据挖掘的功能以及可以发现的知识模式，阐 述了数据挖掘的一般过程，详细描述了数据挖掘的常用技术方法及广泛的 应用领域。 关联规则是序列模式的基础，它反映了大量数据中项目之间有趣的关联或 相关联系。在关联规则中，各个项目都是按平等一致的方式加以处理，但事 实上，不同的项目往往有不同的重要性，因此根据每个项的关注程度赋予不 同的权值，能挖掘出企业感兴趣的利润较大商品的销售规则。 序列模式挖掘是在关联模型中增加了时间属性，寻找的是事务之间在时间 上的先后次序关系，它根据数据随时间变化的趋势，发现某一时间内数据的 相关处理模型，预测将来可能出现的值的分布。即可以预测用户将来可能的 购买行为。 提出购买序列的偏爱度，能更好区别购买频繁的序列，同时引入不同商品 的关注度，就能挖掘出利润较高的频繁序列，即黄金序列模式。 3 中山大学硕士论文 序列模式挖掘算法研究 经典序列模式挖掘是从频繁项目集挖掘发展而来的，重复扫描数据库，造 成系统沉重的负担，以邻接矩阵来记录2 项频繁序列，进而生成需要的频 繁模式，可以大大减少扫描数据库的次数，使系统的性能得到改善。 1 5 本文的结构安排 第l 章绪论。主要介绍了本文的研究背景，序列模式的国内外研究情况， 本文的选题意义以及本文的主要研究内容和基本结构。 第2 章数据挖掘与关联规则挖掘。首先，论述数据挖掘技术应用产生的研 究背景，介绍了数据挖掘的基本概念、定义，说明了数据挖掘的功能以及可以 发现的知识模式，阐述了数据挖掘的一般过程；接着，详细的探讨了关联规则 相关概念、算法及优缺点，最后介绍了加权关联规则，为后续章节做了很好的 铺垫。 第3 章关联规则中加入时间因子，引出序列模式以及它的基本理论，分析 了几中常用的算法。 第4 章是基于邻接矩阵的加权偏爱序列算法研究。首先，本章提出一个同 时考虑顾客购买支持度和商品权值的加权偏爱支持度的概念，能挖掘出更精简、 利润更高的序列模式，其次，利用邻接矩阵来记录2 项频繁序列，并利用矩阵 的特点产生需要的序列模式，大大的提高了算法的效率，最后对它进行性能分 析和实例说明。该章是本文的核心部分，力求表现数据挖掘的基本思想与相关 挖掘算法基本原理的有效结合。 第5 章对本文提出的算法，做了一个原型验证系统。 第6 章对本文工作进行了结论性总结，并对未来工作进行了展望。 1 6 本章小结 本章第一节介绍了本课题的研究背景，第二节提出了论文的选题依据，课题 研究的主要目的是把序列模式和零售业信息结合，有效的为企业的决策处理增 加效用，第三节阐述了本课题研究领域的现状，第四节简单的概括本文每部分 的组织结合和研究内容。 4 中山大学硕士论文 序列模式挖掘算法研究 第2 章数据挖掘与关联规则挖掘 2 1 数据挖掘概述 数据挖掘( d a t am i n i n g ，d m ) 技术可以帮助人们从大量的数据中智能地、 自动地抽取隐含的、事先未知的、具有潜在价值的知识或信息。目前，数据挖 掘不仅被许多研究人员看作是数据库系统和机器学习方面的一个重要研究课 题，而且被许多产业界看作是一个能带来巨大回报的重要领域，从数据库或数 据仓库中发现出来的规则和知识可以用在信息管理、查询响应、决策支持、过 程控制等许多方面。 2 1 1 数据挖掘的发展 数据挖掘是一个逐渐演变的过程。在电子化数据处理的初期，人们试图通 过某种方式来实现自动决策支持，当时的机器学习成为人们关心的焦点，机器 学习的过程就是将一些已知的并被成功解决的问题作为范例输入计算机，机器 通过学习这些范例总结并生成相应的规则，这些规则具有通用性，使用他们可 以解决某一类问题。随后，随着神经网络技术的形成和发展，使人们的注意力 转向知识工程。知识工程不同于机器学习那样给计算机输入范例，让其生成规 则，而是直接给计算机输入已被代码化的规则，计算机通过使用这些规则来解 决某些问题。专家系统就是使用这种方法所取得的成果，但它投资大，效果不 甚理想等不足。二十世纪八十年代人们又在新的神经网络理论的指导下，重新 会到机器学习的方法上，并将其成果应用处理大型商业数据库，从而产生了一 个新的术语一数据库中的知识发现( 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 ) 。 1 9 8 9 年8 月，在第十一界国际人工智能联合会议的专题研讨会上，首次提 出了基于数据库的知识发现技术。到目前为止，由美国人工智能协会主办的 k d d 国际研讨会已经召开了8 次，规模由原来的专题研讨会发展到国际学术大 会，研究中心也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集 成，以及多种学科之间的渗透。 1 9 9 5 年，在加拿大召开了第一届知识发现和数据挖掘国际学术会议。由于 数据库中的数据被形象的喻为“矿床”，因此数据挖掘词很快流传开来。在 1 9 9 5 年的美国计算机年会( a c m ) 上，正式提出了数据挖掘的概念。由于数据 挖掘是k d d 过程中最为关键的步骤，在实际应用中对数据挖掘和k d d 这两个 术语往往不加以区别。 1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议上不仅 进行了学术讨论，并且由3 0 多家软件公司展示了他们的数据挖掘软件产品，不 少软件已经在北美、欧洲等国得到应用。1 9 9 9 年，亚太地区在北京召开的第三 届p a k d d 会议收到1 5 8 篇论文，反响空前热烈。i e e e 的k n o w l e d g ea n dd a t a e n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并行计算、计算机网络 5 中山大学硕士论文 序列模式挖掘算法研究 和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专刊和 专题讨论，甚至到脍炙人口的程度。 2 2 2 数据挖掘的定义 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪音的、模糊的、 随机的实际应用的数据中，提取隐含在其中的、人们事先不知道的、但又是潜 在的有用的信息和知识的过程。 与数据挖掘相近的同义词有数据融和、数据分析和决策支持等。这个定义 包括好几层含义：数据源必须是真实的、大量的、含噪音的；发现的是用户感 兴趣的知识，发现的知识要可接受、可理解，可运用，并不要求发现放之四海 皆准的知识，仅支持特定的问题发现。 发现知识可以是数学的，也可以是非数学的，可以是演绎的，也可以是归 纳的。发现的知识可以用于信息管理，查询优化，决策支持和过程控制等，还 可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据 的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这 种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、 数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据 挖掘这一新兴的研究领域，形成新的技术热点。 简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已 经有很多年的历史，只不过在过去的数据收集和分析的目的是用于科学研究， 另外，由于当时计算机能力的限制，对大量数据量进行分析的复杂数据分析方 法受到很大的限制。现在，由于各行业业务自动化的实现，商业领域产生了大 量的业务数据，这些数据不再是为了分析的目的而收集的，而是由于商业运做 而产生。分析这些数据也不再是单纯的为了研究需要，更主要是为了商业决策 提供真正有价值的信息，进而获取利润。但所有企业面临一个共同的问题是； 企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经 过深层分析，获得有利于商业运作、提高竞争力的信息，就象从矿石中淘金一 样，数据挖掘也因此而得名i i “。 因此，数据挖掘可以描述为；按企业即定业务目标，对大量的企业数据进 行探索和分析，揭示隐藏的、未知的或验证己知的规律性，并进一步将其模型 化的先进有效的方法。 2 1 3 数据挖掘对象 原则上讲，数据挖掘可以在任何类型的信息存储上进行。这包括关系数据 库、数据仓库、事务数据库、面向对象的数据库、对象一关系数据库、空间数 据库、时间序列数据库、文本数据库、多媒体数据库和万维网等。 2 1 4 数据挖掘的目的 数据挖掘的任务是从大量的数据中发现知识，知识是人类认识的成果或结 晶。包括经验知识和理论知识。从工程角度定义，知识是有助解决问题的有格 式的可复用的信息。在传统的决策支持系统中，知识库的知识和规则是由专家 6 中山大学硕士论文 序列模式挖掘算法研究 或程序员建立的，是外部输入的，而数据挖掘的任务是发现大量的数据中尚未 被发现的知识，是从系统内部自动获取知识的过程，对于那些决策者已经明确 了解信息，可以查询、联机分析( o l a p ) 或者其他工具直接获得，比如“列出 各子公司上个月的销售情况“。而另外一些隐藏在大量数据中的关系、趋势， 即使是管理这些数据的专家也没有能力发现，这些信息对于决策者而言可能是 至关重要的，数据挖掘的目的正是为了解决此类问题。 数据挖掘发现的知识通常是用以下形式表示的：概念( c o n c e p t s ) 、规则 ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 、约束( c o n s t r a i n t s ) 、可视化 ( v i s u a l i z a t i o n s ) 掣5 1 。 这些知识可以直接提供给决策者，用以辅助决策过程，或者提供给领域专 家，修正专家已有的知识体系，也可以作为新的知识专门存储到应用系统的知 识存储机构中，比如专家系统( e x p e r ts y s t e m ) 、规则库( r u l eb a s e ) 等。 2 1 5 数据挖掘过程。如下图2 - 1 图2 - 1 数据挖掘的通用过程 图2 1 是数据挖掘的通用过程，一般由以下步骤组成：数据清理，消除噪 音或者不一致的数据。 数据集成：将多种数据源组合在一起。 数据选择：从数据库中检索与分析任务相关的数据。 数据变换：数据变换或统一成适合挖掘的形式。数据挖掘：利用智能手段 提取数据中的特征模式。 模式评估：根据某种兴趣度度量，识别表达知识的有趣模式。 知识表示：从模式中提取用户可以直接采用的知识。 首先将各种数据采集到数据库中，通过数据清理和集成把数据库中这些数 据有用的部分提取出来，然后放到一个大的数据仓库中。在数据仓库中根据挖 掘的目标选择或变换相关的数据集，采用某种挖掘算法对数据集进行挖掘，由 挖掘得出的模式数量一般很大，通过模式评估获得有趣的模式，最后从这些模 式中提取出人们用于决策或者研究的知识。 在理解数据挖掘的具体实施过程时，我们还应该注意以下几点：1 ) 数据挖 掘仅仅是整个挖掘过程中的一个重要步骤。2 ) 数据挖掘质量的好坏不但取决于 7 中山大学硕士论文 序列模式挖掘算法研究 所选用的数据挖掘技术，而且还取决于所挖掘的数据的质量和数量，如果选择 了错误的数据或不适当的数据，或对数据进行了不适当的转化，则挖掘结果不 会成功。3 ) 真正的挖掘过程是一个不断反馈的过程。比如，用户在挖掘过程中 发现选择数据不太满意，或使用的挖掘技术产生不了期望的结果。这时，用户 需要重复先前的过程，甚至重新开始。4 ) 可视化技术在数据挖掘的各个阶段都 应起着重要的作用。比如在数据预处理阶段，用户可以用散点图、直方图等统 计可视化技术来显示有关数据，以期对数据有一个初步的了解，从而为更好地 选择数据打下基础，在数据挖掘阶段，用户则要使用与领域问题有关地可视化 工具，在结果表示阶段，则可能要用到可视化技术以使发现知识更易于理解等。 2 1 6 数据挖掘的主要技术 数据挖掘是一个交叉学科领域，受多个学科影响，包括数据库系统、统计 学、机器学习、可视化和信息科学。此外，它还依赖于所用的数据挖掘方法， 以及可以使用的其他学科的技术，如神经网络、模糊或粗糙集理论、知识表示、 归纳逻辑程序设计或高性能计算；依赖于所挖掘的数据类型或给定的数据挖掘 应用。数据挖掘系统也可能集成空间数据分析、信息检索、模式识别、图像分 析、信号处理、计算机图形学、w e b 技术、经济、商业、生物信息学或心理学 领域的技术。数据挖掘有多种不同的分类方法。从挖掘技术的角度考虑，有机 器学习、统计学、可视化、模式识别、神经网络以及面向数据库或数据仓库的 技术等，对于复杂的数据挖掘系统可能同时运用多种数据挖掘技术，或者采用 有效的、集成的技术；从应用的角度分析，不同的应用领域需要集成针对该应 用特别有效的方法，而普通的、全能的数据挖掘系统可能无法胜任特定领域的 挖掘任务。 2 2 序列模式挖掘概述 2 2 1 什么是序列模式挖掘 序列模式挖掘p 1 ( s e q u e n t i a lp a t t e mm i n i n g ) 即从序列数据库中发现频繁子 序列以作为模式，它是指挖掘基于时间或者其它顺序的出现频率高的模式。它 是一类重要的数据挖掘问题，有着非常广泛的应用前景，包括顾客购买行为的 分析、网络访问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害 的预测、d n a 序列的破译等等。序列模式挖掘问题是由a g r a w a l 和s r i k a n t 最 先提出的：给定一个序列集，其中每一个序列由项集构成，然后给定由用户确 定的最小支持度闽值( m i n i m u ms u p p o r tt h r e s h o l d ) ，序列模式挖掘就是去发现 所有的频繁子序列( 即：这些子序列的出现频率不小于给定的最小支持度) 。序 列模式的一个例子就是“一个9 个月前买了一台p c 的顾客有可能在一个月 内买一个新的c p u ”。由于许多商业交易、电信记录、天气数据和生产过程都 是时间序列数据，在针对目标市场、客户吸引、气象预报等的数据分析中，序 列模式挖掘是很有用途的。 进行序列模式挖掘时有很多参数对于挖掘的结果影响很大。 首先是时间序列的持续时间( d u r a t i o n ) t ，也就是这个时间序列的有效时间 8 中山大学硕士论文序列模式挖掘算法研究 或者是用户选择的一个时问段，例如1 9 9 9 年。这样序列模式挖掘就被限定为 对某段特定时间内的数据的挖掘。 其次是事件折叠窗口( e v e n tf o l d i n gw i n d o w ) w ，在一段时间内发生的几件 事件可以被看作是同时发生的，如果w 被设置为持续时间t 的长度，我们就 可以发现一些关联模式一“在1 9 9 9 年，一个买了p c 机用户又买了数字照 相机”( 并不考虑先后顺序) 。如果w 被设置为o ，那么序列模式就是两个事 件发生在不同的时间里一“已经买了p c 机和内存的顾客有可能在以后买一 个光驱”。如果w 被设置为一段时间间隔( 例如一个月或者是一天) ，那么在 这段时间的交易在分析中可以被看作是同时发生的。 最后一个参数是时间间隔( i n t e r v a l ) i n t ，这个参数表示发现的模式的时间间 隔。i n t = 0 ：表示没有时间间隔；即是，所找出的是严格连续的序列。我们要考 虑参数w ，例如如果事件折叠窗口w 设置为一个星期，那么发生了事件a ， 事件b 会在一星期内发生。m i ni n t e r v a l i n t m a xi n t e r v a l ：表示我们要 找出最小时间间隔为m i ni n t e r v a l ，而最大时间间隔为m a xi n t e r v a l 的模式。 例如，模式“如果某人租了影片a ，很可能会在3 0 天内租影片b ”蕴涵i n t 3 0 。i n t = c 而c 不为0 ，那么意味着两件事的间隔为固定的时间，例如： “每当股票a 下跌了超过5 ，那么两天后会发生什么事? ”，将搜索间隔i n t = 2 ( 天) 的序列模式。 2 2 2 序列模式挖掘传统算法及瓶颈 到目前为止很多研究已经对如何有效地进行序列模式挖掘作出了贡献。几 乎所有频繁模式挖掘的方法都是基于a p r i o r i 性质( 频繁项集的所有非空子集都 一定也是频繁的，或一个非频繁模式的任何超模式( s u p e r - p a r e m ) 一定非频繁) 的算法，本文称之为a p f i o f i 1 i k e 算法。a p d o d 1 i k e 序列模式挖掘方法尽管降低 了搜索空间，但是要面临三个不容忽视的内在的开销，这些开销是不依赖具体 的实现技术而独立的。 ( 1 ) 潜在的巨大的候选序列集 因为候选序列集包括了一个序列中的元素和项的重复的所有可能的排列； 因此即使对一个适度大小的种子集合，a p f i o d 1 i k e 算法也可能会产生一个非常 庞大的候选序列集。例如：如果有1 0 0 0 个长度为l 的频繁序列设为 ， ， ，一个a p f i o d - l i k e 算法将生成1 0 0 0 1 0 0 0 。1 0 0 0 x9 9 9 ；1 ，4 9 9 ，5 0 0 个候选序列；其中1 0 0 0 1 0 0 0 指： ， 2 ， ， ， ：! 旦旦壁兰! ! 竺指： 2 ， ， 。 ( 2 ) 对数据库的多遍扫描因为每一次对数据库的扫描候选序列的长度仅 增长1 ，所以若要发现长度为1 5 的序列模式 ( a b c ) ( a b c ) ( a b c ) ( a b c ) ( a b c ) ， a p f i o f i 1 i k e 算法必须扫描数据库至少1 5 次。 ( 3 )当要挖掘出的序列模式较长时的算法瓶颈一个长的序列模式必须由 短的序列模式组合而成，但是这样的候选序列的数量的增长与要被挖掘序列模 式的长度的增长是成指数关系的。例如：假定在一个数据库中仅有一个序列： ，其长度为1 0 0 ，在这个数据库中最小的支持度阈值为l ( 即每 9 中山大学硕士论文 序列模式挖掘算法研究 一个出现的模式都是频繁的) 。为了得出这个长度为1 0 0 的序列模式 a p 洲i k e 算法必须产生1 0 0 + - 愀l 的候选序列，1 0 0 l o o + 塑笋= 1 4 ，9 5 。个长度为2 的候选序列，( ：0 0 = 1 6 1 ，7 。个l e n g t h - 3 候选序列， 很明显，所有要被产生的候选序列个数要大于f | 二u v | - 2 ”一l * 1 0 ”。 = u ， 总之，传统的序列模式挖掘算法，当从序列数据库中挖掘长模式或支持度 较低时，存在所挖出的频繁子序列个数会随模式长度增加而爆炸性增长，以及 将会遇到较高的计算复杂度等等很多问题。这样便限制了这些算法的应用，因 为很多有用的长模式不能被有效地挖掘出来，而在很多实际应用中，如进行 d n a 序列分析和股票序列分析等，经常会碰到含有大量长模式的序列数据库。 因此，很有必要发现更有效的方法来解决这些问题。 2 2 3 序列模式和关联规则的异同点 序列模式是从关联规则演化出来，因此它的一些概念和算法与关联规则中 的十分相似，但又比关联规则更为复杂。 相同点。两者的挖掘对象都是事务数据库，都希望从事务数据库中发现规 律，从而知道管理者根据规律做出决策，将利益最大化。两者都是以项为 基本单位，项集的概念也是相同的。都有包含定理，都有支持率的概念。 挖掘的基本步骤相同，先根据最小支持度找出数据库中的所有频繁序列( 或 项目集合) ，接着在所有频繁序列( 或项目集合) 中产生序列模式( 关联规则) 。 序列模式的挖掘算法都是由关联规则挖掘的算法演变而来，比如a p r i o r i a l l 是由a 阳o r i 演变而来。 不同点。关联规则挖掘的是顾客的某一次购物行为中的规律，而序列模式 挖掘的是顾客的多次购物行为中的规律，挖掘的结果是由若干项集组成的 序列；序列模式挖掘中定义了序列，序列是若干项集的有序集合，关联规 则中没有“序列”的概念；关联规则中除了定义支持度用来衡量关联规则 整个数据集中的统计重要性外，还定义了置信度用来衡量关联规则的可信 程度，在序列模式中衡量序列模式是否是用户所需要的标准之一是支持度， 没有置信度的概念；挖掘任务的不同决定了挖掘算法的不同，由于序列模 式挖掘算法挖掘的是由若干项组成的序列，而关联规则挖掘算法挖掘的仅 仅只是项。所以，在数据库中搜索一个序列显然要比搜索一个项集更加困 难，在同样的条件下，候选序列的个数要比候选项目集的个数多得多。从 这两方面来说，序列模式挖掘算法比关联规则挖掘算法更为复杂。 2 3 关联规则 序列挖掘( s e q u e m i a lm i n i n g ) 或称序列模式挖掘，是指从序列数据库中发 现相对时间或其他顺序所出现的高频率的子序列。它的分析与关联规则是一样 1 0 中山大学硕士论文 序列模式挖掘算法研究 的，是在关联规则的基础上加入了时间因子生成的，更重视的是前因( 后果) 关系，因此本章先介绍与序列模式相关的关联规则、加权关联规则的基本概念 以及常用算法，然后在下一章讨论了序列模式的基本概念、基本理论以及常用 的算法。 2 3 1 关联规则基本作用 关联规则挖掘是一种非常重要的知识发现方法。最早是由a g r a w a l 等人提 出的( 1 9 9 3 ) ，最初提出的动机是针对购物篮分析( b a s k e ta n a l y s i s ) 问题提出 的，其目的是为了发现交易数据库( t r a n s a c t i o nd a t a b a s e ) 中不同商品之间的联 系规则。通过对交易数据库的智能分析，可以获得有关的顾客购买模式的一般 的规则，这些规则刻画了顾客购买行为模式，可以用来指导商家科学的安排进 货、库存以及货架设计等。此外，在其他领域也得到了广泛的讨论。 2 3 2 关联规则定义 关联规则是发现交易数据库中不同商品( 项) 之间的联系，即购买了某一商 品对购买其它商品的影响。通过关联分析，可以发现三种规则：有用的、价值 不高的、费解的。 价值不高的规则往往是对一些商业领域内众所周知的规则的重现。比如今 天是情人节，那么鲜花的价格肯定会暴涨，这样的规则己经为人们所感知并运 用到了商业运作中。费解的规则往往是数据中一些偶然的东西。比如：有一天 某个超市发现购买消夏商品的顾客增加，但是只有这一天销量特别突出，前后 销量趋于平常。造成这种偶然的情况的原因很可能是偶然的，如附近的几个居 民区那天停电等。对于这样费解的规则，因为它出现的概率很低，我们没有必 要对其进行分，也没有必要采取什么行动。只有在事物之间潜在的经常发生的 规则才是有用的规则，“潜在的”就是说别人还没有发现的，还没有广泛的应用 到商业运作中。“经常发生的”说明规则发生的概率很大，我们对其采取行动产 生的效益可能也很大。