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

基于聚类分区的序列模式挖掘算法研究 摘要 信息技术的日新月异使得各个领域的数据量激增，在此背景下诞生的知识 发现和数据挖掘给人们提供了一种新的认识数据、理解数据的智能手段。序列 模式发现是其中的一个重要研究课题。数据规模的增大对挖掘算法提出了更高 的要求。本文针对目前序列模式发现研究中的一些问题展开研究，主要研究工 作如下： ( 1 ) 详细讨论了序列模式的基本模型以及经典的发现方法，展现了序列模 式发现研究领域的应用前景及所面i 临的挑战。 ( 2 ) 针对p r e f i x s p a n 算法产生的投影数据库花费较多的存储空间及扫描时 间，提出p s d 算法，舍弃了对非频繁项的存储及对投影序列数小于最小支持数 的投影数据库的扫描，减少了不必要的存储空间，提高了查询速度。实验证明， p s d 算法比p r e f i x s p a n 算法具有更好的时空性能。 ( 3 ) 对较大数据集挖掘序列模式，提出基于分区的序列模式挖掘算法，以 期克服有限存储问题，为并行处理及分布式处理做好基础。此外，当给出的分 区数固定时，不同的分区性能可能存在较大差异，本文通过聚类方法对数据集 预处理，以得到可以产生较少局部频繁序列的特定分区，最终得到较少的全局 候选序列以减少第二遍扫描时间。理论分析和实验表明，本文所提出的方法可 比普通分区方法得到更加优化的分区从而效率更高。 关键词：数据挖掘，序列模式，投影数据库，分区算法，聚类 r e s e a r c ho ns e q u e n t i a lp a t t e r n sm i n i n gb a s e do n c l u s t e r i n gp ar t i t i o n a b s t r a c t t h eq u i c kd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g yl e a d sar a p i di n c r e a s ei na l l k i n d so fd a t a j u s tt h e s ee a s e sb r i n gb i r t ht ot h ek d da n dd a t am i n i n gt h a tp r o v i d e p e o p l ean e wa p p r o a c ht ou n d e r s t a n dd a t a t h ed i s c o v e r yo fs e q u e n t i a lp a t t e r n si s a t l i m p o r t a n tf i e l di nk d d d a t as c a l e se n l a r g e m e n tp u tf o r w a r dh i g h e rr e q u i r e m e n t s f o rt h ea l g o r i t h m t h i sd i s s e r t a t i o nr e s e a r c h e so nt h ep r o b l e mo fs e q u e n t i a lp a t t e r n s m i n i n gi nd a t a b a s e s t h em a i nc o n t e x ti sa sf o l l o w s ： ( 1 ) t h eb a s i cm o d e lo fs e q u e n t i a lp a t t e r na n ds e v e r a lc l a s s i c a lm i n g i n g a l g o r i t h m si sd i s c u s s e di nd e t a i l b a s e do nt h e s e ，t h ea p p l i c a b l ef u t u r ea n dp o s s l i b e c h a l l e n g eo fs e q u e n t i a lp a t t e r nm i n i n gi se x h i b i t e d ( 2 ) p r o j e e t i o nd a t a b a s e st h a tp r e f i x s p a np r o d u c e dc o s tm o r er e d u n d a n tm e m o r ya n d s c a n - t i m e as 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 mp s db a s e do np r e f i x s p a ni sp r e s e n t e di n t h i sp a p e r t h ea l g o r i t h md e c r e a s e st h er e d u n d a n tm e m o r ya n ds c a n t i m eb ya b n e g a t i n gt h e n o n - f r e q u e n ti t e m sa n dp r o j e c t i o nd a t a b a s e sw h i c hs e q u e n t i a ln u m b e ri s l o w e rt h a n m i n i m u ms u p p o r t e x p e r i m e n t sd e m o n s t r a t et h a tp s di sm o r ee f f i c i e n tt h a n p r e f i x s p a n ( 3 ) t h i sd i s s e r t a t i o ns h o w sap a r t i t i o n - b a s e da p p r o a c hf o r t h ev e r yl a r g ed a t a s e t t oo v e r c o m en o to n l yt h el i m i t e dm e m o r yi s s u e ，b u ta l s oi np a r a l l e lp r o c e s s i n ga n d d i s t r i b u t e dp r o c e s s i n g f o rg i v e nt h en u m b e ro ff r a g m e n t s ，d i f f e r e n tp a r t i t i o n s i m p a c to np e r f o r m a n c ed r a m a t i c a l l y t h ec l u s t e r i n ga l g o r i t h mi su s e dt op a r t i t i o n t h ei n p u td a t a s e ti no r d e rt og e tt h es p e c i a lf r a g m e n t sw h i c hc a ng e n e r a t et h e s m a l l e rn u m b e ro fl o c a lf r e q u e n tp a t t e r n sa sw e l la st h es m a l l e rn u m b e ro fg l o b a l p a t t e r nc a n d i d a t e s 。t h e o r i e sa n a l y s i sa n de x p e r i m e n t sp r o v et h a t i tg e n e r a t e s o p t i m a lp a r t i t i o na n de x h i b i t sg o o de f f i c i e n c yt h a nc o m m o n m e t h o d s k e y w 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 ，p r o je c t i o nd a t a b a s e ，p a r t i t i o n b a s e d a p p r o a c h ，c l u s t e r i n g 图2 1 图3 1 图3 2 图3 3 图4 1 图4 2 插图清单 一个分类的例子17 两种算法在不同支持度下运行时间比较。2 6 两种算法在不同支持度下投影数据库所需空间比较2 7 两种算法在不同支持度下扫描投影数据库次数比较2 7 对d 1 两种分区在不同支持度下性能比较3 4 对d 2 两种分区在不同支持度下性能比较3 5 i i i 表2 1 表2 2 表2 3 表2 4 表2 5 表2 6 表2 7 表2 8 表2 9 表2 一1 0 表2 一1 1 表3 一l 表3 2 表3 3 表3 4 表4 1 表4 2 表4 3 表4 4 表格清单 一个小型的事务数据库9 转换后的事务数据库9 挖掘结果1 l 序列模式的挖掘步骤1 3 原始数据库一1 4 频繁项集1 4 转换后的数据库1 5 频繁卜序列1 6 频繁2 序列1 6 一个序列数据库2 0 投影数据库和序列模式2 1 一个序列数据库d 2 4 序列数据库d 的投影数据库和序列模式2 5 i b m 数据生成器的命令行选项说明2 5 两种算法在不同支持度下时空性能比较2 6 对数据集d 随机分区与聚类分区性能比较3 3 对d 1 两种分区在不同支持度下挖掘结果3 4 对d 2 两种分区在不同支持度下挖掘结果3 4 随机分区和聚类分区序列数比较一3 5 i v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 佥g 里王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 靴敝储糯：獬 签字日期：哆年。月g 日 ， 学位论文版权使用授权书 本学位论文作者完全了解金罂至些太堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金胆王些太堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手一 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：导师签名： 签字日期：哆年，。月8 日 签字日期： l 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 乡南 ，厂l 1瓤 以嚏厂 翰钐 一 叫 致谢 值此论文完成之际，谨向我的导师胡学钢教授表示最真挚的谢意! 在近三 年的硕士研究生课程学习和撰写学位论文的过程中，自始至终得到了导师的悉 心指导，无论从课程学习、论文选题，还是到收集资料、论文成稿，都倾注了 导师的心血，正是导师的辛勤努力才使我迈入理论研究的殿堂。胡老师渊博精 深的学识，严谨求实的科研态度，宽以待人严于律己的学者作风，使我倍受教 育，在以后的学习和工作中，我将牢记胡老师的谆谆教诲。 感谢宿州学院李鸿教授在论文写作过程中提出的宝贵意见和建议。 感谢人工智能与数据挖掘研究室的吴共庆老师，在课题完成的过程中给予 的认真指导。感谢研究室的同学们在撰写论文期间给予的热情帮助。 感谢我的家人，无论在学业上、事业上都是我一生中最大的支柱。 最后，对在学习、工作和生活中曾经给予我关心、鼓励和帮助的所有领导、 老师、同学、朋友和亲人表示最诚挚的感谢和最崇高的敬意! 作者：吴楠 2 0 0 9 年4 月 第一章绪论 1 1 数据挖掘概述 1 1 1 数据挖掘的发展 随着计算机技术和i n t e r n e t 的不断发展，近年来数据挖掘技术引起了社会 各界的普遍关注，其主要原因是数据搜集工具的进步使得我们拥有数量庞大的 数据，大量数据信息在给人们带来方便的同时也带来了一大堆问题：第一是数 据信息过量，难以消化；第二是数据信息真假难以辨识；第三是数据信息形式 不一致，难以统一处理。人们开始考虑：“如何才能不被数据信息淹没，而是从 中及时发现有用的知识、提高信息利用率? 另一方面，随着数据库技术的迅速发展以及数据库管理系统的广泛应用， 人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望 能够对其进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统 可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关 系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏 的知识的手段，导致了“数据丰富但信息贫乏 的现象。面对这些呈爆炸式增 长的数据，迫切需要新型的技术和工具将这些海量数据转化成有用的信息和知 识，从而可以广泛用于各种应用，包括商务管理、生产控制、市场分析、工程 设计和科学探索等。因此，数据挖掘成为日益受到重视的研究领域。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种 商业数据是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访 问，进而发展到对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高 级的阶段，它不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之 间的潜在联系，从而促进信息的传递。 数据挖掘是信息技术自然演化的结果。数据挖掘和知识发现技术最早源于 人工智能的学习，并在2 0 世纪8 0 年代末开始逐渐发展起来【1 5 1 。 1 1 2 数据挖掘的概念 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程1 6 j 。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义 包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感 兴趣的知识；发现的知识要可接受、可理解、可运用；并不要求发现放之四海 而皆准的知识，仅支持特定的问题发现。 何为知识? 从广义上理解，数据、信息也是知识的表现形式，但是人们更 把概念、规则、模式、规律和约束等看作知识。人们把数据看作是形成知识的 源泉，好像从矿石中采矿或淘金一样。原始数据可以是结构化的，如关系数据 库中的数据；也可以是半结构化的，如文本、图形和图像数据；甚至是分布在 网络上的异构型数据。 发现知识的方法可以是数学的，也可以是非数学的；可以是演绎的，也可 以是归纳的。发现的知识可以被用于信息管理，查询优化，决策支持和过程控 制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人 们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支 持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是教据库技术、人工 智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员， 投身到数据挖掘这一新兴的研究领域，形成新的技术热点。 这里所说的知识发现，不是要求发现放之四海而皆准的真理，也不是要去 发现崭新的自然科学定理和纯数学公式，更不是什么机器定理证明。实际上， 所有发现的知识都是相对的，是有特定前提和约束条件，面向特定领域的，同 时还要能够易于被用户理解。最好能用自然语言表达所发现的结果。 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的 大盘业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决 策的关键性数据。 简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已 经有很多年的历史，只不过在过去数据收集和分析的目的是用于科学研究，另 外，由于当时计算能力的限制，对大数据量进行分析的复杂数据分析方法受到 很大限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务 数据，这些数据不再是为了分析的目的而收集的，而是由于商业运作而产生。 分析这些数据也不再是单纯为了研究的需要，更主要是为商业决策提供真正有 价值的信息，进而获得利润。但所有企业面临的一个共同问题是：企业数据量 非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析， 获得有利于商业运作、提高竞争力的信息，就像从矿石中淘金一样，数据挖掘 也因此而得名。 因此，数据挖掘可以描述为：按企业既定业务目标，对大量的企业数据进 行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型 化的先进有效的方法。 1 1 3 数据挖掘的任务 数据挖掘的任务是从大量的数据中发现模式，所谓模式是指关于数据集的 某种抽象描述。一般而言，按照其作用模式可以分为两大类：预测型模式 ( p r e d i c t i v ep a t t e r n ，如：序列模式、分类模式、回归模式、偏差分析等) 和描 2 述型模式( d e s c r i p t i v ep a t t e r n ，如：聚类模式、关联模式和序列模式等) 。预测 型模式能够根据已有的数据集，预测某些( 未知的) 数据项的值。描述型模式 是对数据中存在的规律、规则作出一种描述，或者根据数据间的相似性将数据 分组，它一般不能直接用于预测 7 1 。 ( 1 ) 关联规则( a s s o c i a t i o nr u l e ) 若两个或多个变量的取值之间存在某种规律性，就称为关联。关联可分为 简单关联、时序关联、因果关联。关联分析的目的是找出数据库中隐藏的关联 规则。有时并不知道数据库中数据的关联规则，即使知道也是不确定的，因此 关联分析生成的规则带有可信度。 货篮分析问题就是一个典型的关联规则挖掘的应用实例。货篮问题的处理 对象称为货篮数据，即通过对顾客购物车中所购不同商品之间的关联关系的分 析，来帮助零售商建立有利的市场经营策略。如买尿布的男士很可能同时也要 买啤酒，通过对顾客的购物分析，可以决定将尿布和啤酒放到一起销售，来增 加这两种商品的营业额。 ( 2 ) 序列模式( s e q u e n t i a lp a t t e r n ) 序列模式与关联规则相仿，主要把数据之间的关联性与时间联系起来。序 列模式不仅需要考虑事件是否发生，而且需要考虑事件发生的时间。它可看成 是一种特定的关联模型，它在关联模型中增加了时何属性。它根据时间序列型 数据，由历史的和当前的数据去推测未来的数据，也可以认为是以时间为关键 属性的关联知识。例如，在购买彩电的人们当中，7 0 的人会在5 个月内购买 影碟机。 序列模式根据数据随时间变化的趋势，发现某一时间段内数据间的相关性 处理模型，预测将来可能出现值的分布情况。 ( 3 ) 分类模式( c l a s s i f i c a t i o np a t t e r n ) 分类模式是反映同类事物间的共性以及异类事物间的差异的特征知识。构 造某种分类器，将数据集上的数据映射到特定的类上，其主要目的是用以提取 数据类的特征模型，进而预测事物发展的趋势。例如，银行部门根据以前的数 据将客户分成了不同的类别，现在就可以根据这些来区分新申请贷款的客户， 以采取相应的贷款方案。 ( 4 ) 聚类模式( c l u s t e r i n gp a t t e r n ) 数据库中的记录可被划分为一系列有意义的子集，即聚类。聚类模式与分 类模式不同，聚类模式在事先并不知道分组及怎样分组的情况下，而知道划分 数据的基本原则。在这种原则的指导下，把一组个体按照个体间的相似性划分 成若干类，这种划分的结果称为聚类模式。其目的是使得属于同一个类别的数 据间的相似性尽可能大，而不同类别的数据间的相似性尽可能小。聚类增强了 人们对客观现实的认识，是概念描述和偏差分析的先决条件。 3 ( 5 ) 回归模式( r e g r e s s i o np a t t e r n ) 回归模式的函数定义与分类模式相似，它们的差别在于分类模式的预测值 是离散的，回归模式的预测值是连续的。如给出某种动物的特征，可以用分类 模式判定这种动物是哺乳动物还是鸟类：给出某个人的教育情况、工作经验， 可以用回归模式判定这个人的年工资在哪个范围内，是在6 0 0 0 元以下，还是在 6 0 0 0 元到1 万元之间，或者1 万元以上。 ( 6 ) 偏差分析( d e v i a t i o nd e t e c t i o n ) 数据库中的数据常有一些异常记录，从数据库中检测出这些偏差是很有意 义的。偏差包括很多潜在的知识，如分类中的反常实例、不满足规则的特例、 观测结果与模型预测值的偏差等。 在实际情况中，数据挖掘系统的任务不是单一的，经常要同时发现多种模 式。 1 1 4 数据挖掘的热点 历经了十几年的发展，数据挖掘技术本身已经积累了一批有价值的理论和 技术成果。同时，包括统计学、人工智能等在内的相关学科的发展从某种程度 上对数据挖掘技术发展起到了极大地推动作用。根据麻省理工学院的科技评 论评估，“数据挖掘”技术是对未来人类产生重大影响的十大新兴技术之一。 如今的数据挖掘已成为计算机、信息科学以及相关领域的一个研究热点，而且 在银行、电信、保险、交通、零售以及天文学、分子生物学等领域得到应用。 就目前看来，将来的几个热点包括网站的数据挖掘( w e bs i t ed a t am i n i n g ) 、 生物信息或基因( b i o i n f o r m a t i c s g e n o m i c s ) 的数据挖掘、文本的数据挖掘 ( t e x t u a lm i n i n g ) 及工程应用中的数据挖掘。下面就这几个方面加以简单介绍。 ( 1 ) w e b 的数据挖掘 随着w e b 技术的发展，电子商务、电子政务等网站风起云涌。如何吸引客 户、建立客户的忠诚度是必须面对的问题。而网站的数据量非常大，并且与传 统数据格式不同，大部分数据来源于单击数据流，因此网站的数据挖掘重点是 数据准备。目前，有许多厂商正在致力于开发专门用于网站数据挖掘的软件。 ( 2 ) 生物信息或基因的数据挖掘 基因的组合千变万化，患某种病的人的基因和正常人的基因到底差别多 大? 能否找出其中不同的地方，进而对其不同之处加以改变，使之成为正常基 因? 这些都需要数据挖掘技术的支持。 对于生物信息或基因的数据挖掘，和通常的数据挖掘相比，在数据的复杂 的程度、数据量、还有分析和建立模型的算法都要复杂得多。从分析算法上讲， 更需要一些新的和好的算法。现在很多厂商正在致力于这方面的研究。 ( 3 ) 文本的数据挖掘 4 无论是在数据结构还是在分析处理方法方面，文本数据挖掘和前面谈到的 数据挖掘相差很大。文本数据挖掘并不是一件容易的事情，尤其是在分析方法 方面，还有很多需要研究的专题。但文本数据挖掘可以扩大数据挖掘的应用领 域，因为许多非格式化的数据都比较容易转换成文本数据。如现在许多大公司 都设立客户服务中心，如果把同客户的谈话转化为文本数据，再对这些数据进 行挖掘，进而了解客户对服务的满意程度和客户的需求以及客户之间的相互关 系等信息，将对公司的业务发展起推动作用。 ( 4 ) 工程应用中的数据挖掘 在工程领域中，积累的数据越来越多，如果工程领域的数据完全依靠手工 分析显然是不现实的，因此必须提高自动化、智能化的程度。更重要的是，有 些情况下人难以到达现场，如航空、航天、深水作业等。这些都对信息的智能 处理提出了要求。因此，数据挖掘对工程领域的意义是不言而喻的。近几十年 来专家系统在工程领域得到广泛的应用，但是专家系统中知识一般是人工提取， 归纳总结后用适合机器存储和应用的方式表示出来并灌输给机器，因此专家系 统只是一个模式匹配系统，知识的获取成为影响专家系统的一个瓶颈。例如， 2 0 世纪6 0 年代由斯坦福大学开发的名为d e n d r a l 的专家系统能根据质谱仪 给出的数据发现已知或未知的高分子化合物的分子结构；7 0 年代开发出的诊断 和治疗传染性血液病的专家系统p r o s p e c t o r ；8 0 年代开发的为美国著名的 计算机公司d e c 做v a x 机硬件配置的专家系统x c o n 等都难以逾越这个瓶颈。 数据挖掘作为一种新的知识获取工具，将有效地改善专家系统的这种状态，对 工程的智能化、信息化、自动化的发展起着不可估量的作用。 1 2 序列模式挖掘技术 1 2 1 序列模式的提出 近年来，序列模式挖掘逐渐成为数据挖掘领域的研究热点之一。序列模式 挖掘是从关联规则的频繁项目集挖掘发展而来的，它在关联模型中增加了时间 属性，把数据之间的关联性与时间联系起来，寻找的是事务之间在时间上的先 后次序关系。它根据数据随时间变化的趋势，发现某一时间段内数据的相关处 理模型，预测将来可能出现的值的分布。举例说明，租借“星球大战”的顾客 接下来会租借“帝国反击战”，再是“杰达武士归来”( 这三部影片是以故事发 生的时间先后而情节连续的) ，即模式“星球大战”、“帝国反击战”、“杰达武士 归来”出现的频率较高。假如现在已经知道有许多客户租借了“星球大战”，但 还没有租借后两部电影，如果上述模式正确，这些顾客会接着租借“帝国反击 战”和“杰达武士归来”，店主可以根据这些信息合理安排。当然，顾客在租借 任何两部影片之间，可以租借其他任何影片，这仍然支持该模式。如何根据已 知的数据预测顾客接下来的行为，促使了序列模式挖掘的产生。 5 序列模式挖掘最初是由于在零售业中的应用而发展起来的，包括策划附加 销售( a d d o ns a l e s ) 、计算顾客满意度等，但是现在，序列模式已经应用到了 科研和商用的其他许多领域。比如，在医疗领域，一个病人每看一次病，他( 或 她) 的症状就可以组成一次事务( t r a n s a c t i o n ) ，而这个病人的所有看病记录( 即 所有事务) 就可以形成一个“症状序列 ，从所有病人的症状序列中挖掘出一个 模式，这个模式将会帮助医生诊断这些症状预示着何种疾病。 1 2 2 序列模式的研究概况 序列模式挖掘的概念是r a g r a w a l 等人在1 9 9 5 年首先提出的【s 】，此后，人 们不断地研究和改进在时间序列数据库中挖掘序列模式和其他频繁模式的算 法。现有的序列模式挖掘算法主要分为两类：第一类是基于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 特性【9 】的算法。a p r i o r i 特性首先应用在关联规则挖掘 中，其基本思想是频繁模式的子模式也一定是频繁模式。基于a p r i 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 算法【1 0 】、g s p 算法】、p s p 算法【1 2 】等；有采取垂直数据格式( v e r t i c a ld a t af o r m a t ) 的算法，如s p a d e 算 法【1 3 】、s p a m 算法【1 4 】等。第二类是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 5 】、p r e f i x s p a n 算法【1 6 】等。另 外，c a n t u n e s 等人提出了s p a r s e 算法【l7 】，该算法的主要思想是将候选序列 的产生和在投影数据库空间搜索结合起来，每一步在产生出频繁元素后，通过 增长长度寻找模式。该算法应用在密集型数据库中能获得较好的性能。 以上算法都是在序列数据库中挖掘所有的序列模式，而且除了g s p 算法之 外，它们挖掘的都是普通的序列模式。每一个序列模式包含了组合数级的频繁 子序列，若序列模式的长度很长，则频繁子序列的数量往往大得惊人。 在很多序列模式挖掘任务中，用户不需要找出数据库中所有可能存在的序 列模式，而是加入一定的约束，找出用户感兴趣的序列模式【l 驯l l9 ，a g r a w a l 等 人将序列模式挖掘问题加以泛化，引入了时间约束、滑动时间窗口( s l i d i n gt i m e w i n d o w ) 和分类约束，并提出了g s p 算法。g s p 算法是基于a p r i o r i 特性的算 法，同样具有类a p r i o r i 算法的缺点。 以上介绍的序列模式挖掘算法都是在一维信息中挖掘序列模式。若能在序 列模式中融合感兴趣的多维信息，在考虑与时间相关属性的同时，挖掘多维信 息中感兴趣的模式，则将得到能提供给用户更丰富信息的多维序列模式。h p i n t 等人提出的u n i s e q 算法【2 0 】能有效地挖掘多维序列模式，但在维度较高时其挖 掘性能会有所下降。 6 1 3 本文的内容与组织 本文研究了数据库中序列模式发现以及进一步应用的问题，由五章组成， 具体组织方式如下： 第一章绪论首先简述了本文的选题背景，然后详细阐述了数据挖掘的定义、 任务及当前的应用热点，最后介绍了数据库中序列模式发现的提出以及研究概 况。本文主要就是研究序列模式发现问题。 第二章主要概述了数据挖掘中的序列模式发现问题，首先介绍了数据库中 的序列模式的产生背景及相关定义，然后说明了序列模式挖掘与关联规则挖掘 的相同与不同点，最后具体介绍了几种经典的序列模式发现方法：a p r i o r i a l l 算法、g s p 算法和p r e f i x s p a n 算法。 第三章提出了基于投影的p s d 算法，该算法在p r e f i x s p a n 算法基础上舍弃 了非频繁项存储及投影序列数小于最小支持度的投影数据库扫描。舍弃非频繁 项，将大大减少保存投影数据库所需内存空间，也将减少其后挖掘中扫描不必 要项的时间。在对投影数据库进行挖掘前，先比较其包含的序列数和最小支持 数，放弃挖掘序列数已小于最小支持数的投影数据库，减少了扫描不可能出现 频繁序列的投影数据库的时间，提高了算法执行效率。实验结果证明，p s d 算 法的时空性能比p r e f i x s p a n 算法明显提高。 第四章研究了基于分区的方法解决数据集很大不能装入内存的挖掘问题， 还介绍了一种通过聚类预处理数据集的方法。对多分区挖掘过程中，首先挖掘 各分区的局部频繁序列集，然后求其交集即部分全局频繁序列集，最后对并集 与交集的差即全局候选序列集作第二遍扫描，找出剩余的全局频繁序列。当给 出的分区数固定时，不同的分区性能差距明显，故通过聚类将数据库尽量分成 “不相似”分区，以得到可以产生较少局部频繁序列的特定分区，最终得到较 少的全局候选序列即第二遍扫描序列，从而提高整体的运算速度。理论分析和 实验表明，本文所提出的方法可比普通分区方法得到更加优化的分区从而效率 更高。 第五章是对全文的总结，对本文的主要研究工作进行简要地阐述，展望未 来可以进一步研究的方向。 第二章序列模式概述 一个大型超市的管理者经常需要考虑这样的问题，如卖什么商品、如何设 计购物优惠券、如何摆放商品等等。通过分析过去一段时间内顾客的购物情况 可以帮助管理者更好的解决这些问题。条形码技术的出现使得零售机构能够收 集和储存大量这种销售数据，顾客的每一次购物称为一次“事务( t r a n s a c t i o n ) ， 每次事务发生可以记录下该事务的发生时间、顾客i d 号、所购商品代号等 等，这些数据称为“购物篮数据”( b a s k e td a t a ) ，一般都储存在数据库管理系 统中。数据库管理系统虽然能够提供高效的查询或更新，但却缺乏有效的分析 工具，不能从这些数据中发现有价值的信息，从而更好的为超市管理者服务。 为了解决这个问题，1 9 9 3 年，a g r a w a l 等人提出了关联规则挖掘问题希望 能从事务数据库中发现有关顾客购买行为方面的知识，从而指导超市的经营策 略。一个关联规则的例子是“购买了牛奶和面包的顾客有9 0 的可能会购买黄 油，“ 牛奶，面包卜- 黄油) 就是一个关联规则。但是，关联规则讨论的只 是一次事务内部的模式，有时随着时间的推移，事务之间也会有某种联系或者 发展趋势，关联规则无法揭示其中的规律。 在1 9 9 5 年举行的第1 l 届数据工程国际会议上，a g r a w a l 和s r i k a n t 提出了 序列模式挖掘问题，希望能从大型数据库中发现一些模式，这些模式揭示了事 务之间的某些联系和规律，从而能够预测事务将来的发展趋势。如“购买了电 视机的顾客有6 0 的可能会在3 个月内购买影碟机 ，“ 电视机) - ， 影碟机) 这样一个模式会帮助销售者及时调整销售策略，获取更大的利润。 2 1 序列模式的定义 为了更加准确和形象的描述序列模式挖掘问题，首先介绍一个小型的事务 数据库，该数据库中包含三个属性：顾客i d 、事务发生时间、该次事务发生时 所购商品代号，并以顾客i d 和事务发生时间为关键字进行排序。假设这个数 据库描述了从6 月2 5 日到7 月2 5 日这一段时间内所有购物信息，如第一条记 录表示顾客l 在6 月2 5 日购买了商品3 0 。具体细节如表2 1 所示。 a g r a w a l 和s r i k a n 给出了如下定义： 定义2 1 事务数据库( t r a n s a c t i o nd a t a b a s e ) ：序列模式挖掘的数据库，记 为d ，d = t l ，t 2 ，t k ，t n ) ，其中k = l ，2 ，n ，如表2 1 所示。t k ( k = l ， 2 ，n ) 为一条事务。如表2 1 中每一条记录就是一次事务。 定义2 2 项( i t e m ) ：表示一个商品被购买或没有购买，通常用i j ( j - 1t om ) 表示。 定义2 3 项集( i t e m s e t ) ：若干项组成的非空集合，用i ( i l i 2 i m ) 表示， 其中i i ( ：i = lt om ) 代表一个项。 表2 1 一个小型的事务数据库 顾客i d事务发生时间所购商品 l 6 2 5 3 0 l6 3 09 0 26 1 0 1 0 ，2 0 26 1 53 0 26 2 0 4 0 ，6 0 ，7 0 3 6 2 5 3 0 ，5 0 ，7 0 4 6 2 5 3 0 46 3 0 4 0 ，7 0 4 7 2 59 0 56 1 29 0 定义2 4 序列( s e q u e n c e ) ：由若干项集组成的有序列表，用s 表 示，其中s i ( j - 1t on ) 表示一个项集。也就是说，组成序列的元素为项集，本 文在以后提到的“序列中的元素( e l e m e n t s ) ”时，一般也是指项集。 在表2 1 中，我们可以将每一件商品看成是一个项，相应的，顾客每次购 物的商品集合就是一个项集，如第一条记录中的( 3 0 ) 和第三条记录中的 ( 1o ，2 0 ) 。根据事务发生的时间，将一个顾客所购商品的项集排成一个列表， 就是一个序列，这个序列我们称之为顾客序列( c u s t o m e r s e q u e n c e ) 。如顾客2 的购物序列为 ，表示该顾客有三次购物事务，第一次购 买了商品l0 、2 0 ，第二次购买了商品3 0 ，第三次购买商品4 0 、6 0 、7 0 。转换 后的数据库如表2 2 所示，序列模式挖掘的对象正是形如表2 2 的数据库。 表2 2 转换后的事务数据库 顾客i d购物序列 1 2 3 4 5 定理2 1 序列的包含定理：已知序列a = 和序列b = ， 如果存在整数i l 、i 2 、i n 且i l i 2 i 。，使得a l b i l ，a2 b ，a 。b i 。，则 称序列b 包含序列a ，或序列a 被序列b 包含，序列b 称为序列a 的子序列。 以表2 2 中的序列为例，序y l j 被序列 包含，因 为( 3 0 ) ( 3 0 ) ，( 9 0 ) c - - ( 9 0 ) 。 定义2 5 序列的长度( 1 e n g t h ) ：关于序列的长度，每一种算法都有不同的 定义，如在a p r i o r i a l l 算法和i u s 算法中，序列的长度是指一个序列中的项集 9 数，但在其它算法中，一个序列的长度则是指该序列中的项的数目。 如对于序y u ，在a p r i o r i a l l 算法和i u s 算法中，它的长度为2 ， 称为2 序列，但在其它算法中，它的长度为3 ，是一个3 序列。 定义2 6 项集的支持数：项集i 的支持数是指，在一次事务中购买i 中所 有商品的顾客数。项集i 与1 序列 有同样的支持数。 定义2 7 一个序列的支持数( t h es u p p o r tf o ras e q u e n c e ) 和支持率：当一 个顾客的顾客序列包含某个序列s 时，称该顾客支持序列s ，序列s 的支持数是 指所有支持s 的顾客数目，记为o 。序列s 的支持率，记为：s u p p o r t ( s ) s u p p o r t ( s ) 2 尚1 0 0 其中l d i 是事务数据库中的顾客数目。在一次挖掘中，用户往往会定义一个 最小支持度来寻找满足条件的结果。 定义2 8 频繁项集( f r e q u e n ti t e m s e t ) 和频繁序列( f r e q u e n ts e q u e n c e ) ：满 足所定义的最小支持度的项集和序列分别叫做频繁项集( 或大项集) 和频繁序 列( 或大序列) ； 若s u p p o r t ( s ) 不小于用户指定的最小支持率( 记为m i n s u p p o r t ) ，则称s 为 频繁序列( 或大序列) ，否则称s 为非频繁序列( 或小序列) 。 定义2 9 最大序列( m a x i m a ls e q u e n c e ) ：在一个序列集合中，当一个序列 不被其它任何序列包含时，我们称这个序列为最大序列。 比如在表2 2 的五个序列中， 就是一个最大序列，因为它不被 其他任何序列包含，而 则不是一个最大序列，因为 。 定义2 1 0 序列模式( s e q u e n t i a lp a t t e r n ) ：给出一个数据库d 和顾客事务， 并由用户定义一个最小支持率，序列模式挖掘就是从所有满足最小支持率的序 列中找出所有的最大序列，每一个最大序列就是一个序列模式。 以表2 2 为例挖掘序列模式，假设用户定义的最小支持率为2 5 ，也就是 说最小支持数必须大于等于2 ( 2 5 x5 = 1 2 5 ，取大于1 2 5 的最小整数即为2 ) 。 通过挖掘发现，在所有满足最小支持率的序列集合里， 和 是其中的最大序列，符合定义的要求，是我们需要的结果。 顾客1 和4 支持序y l j ，顾客4 在购买3 0 和9 0 这两个商品之间购 买了商品( 4 0 ，7 0 ) ，但是因为我们并不要求项集之间的连续性，只需要顾客序列 包含该序列，所以顾客4 仍然是支持序列 的。 顾客2 和顾客4 支持序列 ，顾客2 虽然在购买商品( 4 0 ，7 0 ) 时 同时购买了商品6 0 ，但由于( 4 0 ，7 0 ) ( 4 0 ，6 0 ，7 0 ) ，从而 包含于顾客 2 的顾客序列，所以顾客2 支持序列 。 序y d 只被顾客2 一人支持，其支持率没有达到最小支持率， 所以不是序列模式。序列 、 、 、 、 、 1 0 和 的支持率虽然都大于最小支持率2 5 ，是频繁序列，但是由于它们 不是最大序列，所以也不是序列模式。 表2 2 中符合条件的序列模式如表2 3 所示。 表2 3 挖掘结果 支持度大于2 5 的序列模式 2 2 序列模式与关联规则的比较 2 2 1 关联规则概述 关联规则发现源于购物篮分析。关联规则研究有助于发现交易数据库中不 同商品( 项目) 之间的联系，找出顾客购买行为模式，如购买了某一商品对购买 其他商品的影响。分析结果可以应用于商品货架布局、存货安排以及根据购买 模式对用户进行分类【2 1 - 2 3 1 。 项和项集：同序列模式定义中的相同，项表示d 中商品的名称，项集是若 干项的集合。若顾客购买了某商品( 即发生了一次事务) ，则该商品对应的项标 志符就包含在该事务中。 设t k 和x 分别为d 中的事务和项集，如果x t k ，称事务t k 包含项集x ， 或项集x 被事务t k 包含。数据集d 中包含项集x 的事务数称为项集x 的支持 数，记为0x o 项集x 的支持率，记作s u p p o r t ( x ) ， s u p p o r t ( x ) _ 尚1 0 0 其中，i d i 是数据集d 的事务数。若s u p p o r t ( x ) 不小