（计算机应用技术专业论文）序列模式发现中关键问题的研究.pdf

序列模式发现中关键问题的研究 摘要 数据库知识发现( k d d ) 是当前涉及人工智能和数据库等学科的一门相当 活跃的研究领域，序列模式发现是其中的一个重要研究方向。 当前序列模式发现算法需要多次扫描数据库，挖掘所有的频繁序列，时间 开销较大。在实际应用中，最小支持度的设置是一个敏感问题。为此，本文针 对以上关键问题进行研究，主要工作如下： ( 1 ) 提出一种基于统计方法动态确定最小支持度的算法n e w g s p 。传统的 序列模式发现算法中的最小支持度需要人为来设定，具有一定的局限性。 n e w g s p 采用采用统计方法，动态地确定最小支持度，压缩候选序列集。理论 分析及实验表明n e w g s p 较传统的序列模式发现算法在时间和空间性能上具有 一定的优越性。 ( 2 ) 提出一种基于图结构发现闭合序列模式的新算法g c l o s p a n 。挖掘闭 合序列集合能在保持信息完备性的前提下，比挖掘频繁序列全集更加精简有效。 g c l o s p a n 算法仅需扫描一次数据库，将与挖掘任务相关的信息映射在频繁2 序列图( f 2 s g ) 中，通过位置信息来计算支持度，不必反复扫描数据库，从而 减少搜索空间，提高了闭合序列的生成效率。理论分析实验表明，该算法较传 统的闭合序列模式发现算法在时间和空间性能上具有优越性。 ( 3 ) 基于上述研究，实现了序列模式发现的原型系统s e q d m ，从理论和 实验上证明了所提出的算法的正确性和有效性。 关键词：数据挖掘，序列模式，统计方法，频繁序列图，闭合序列模式 t h er e s e a r c ho nk e y p r o b l e m so fs e q u e n t i a lp a t t e r n sm i n i n g a b s t r a c t 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 s ( k d d ) i sar a p i d l ye m e r g i n gr e s e a r c hf i e l d r e l e v a n tt oa r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s es y s t e m t h ed i s c o v e r yo fs e q u e n t i a l p a t t e r n si sa ni m p o r t a n tf i e l di nk d d 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 sn e e dt os c a nd a t a b a s e sf o r m u l t i p l et i m e s ， a n dd i s c o v e ra l lt h ef r e q u e n ts e q u e n c e s ，t h e r e f o r et h et i m ep e r f o r m a n c eo ft h e s e a l g o r i t h m si sp o o r i nt h ep r a c t i c a lu s e ，s e t t i n gm i n s u p p o r ti sas e n s i t i v et a s k t h e w o r ko ft h i sd i s s e r t a t i o na i m sa tt h ep r o b l e m sm e n t i o n e da b o v e t h em a i n c o n t r i b u t i o no ft h i sd i s s e r t a t i o ni sa sf o l l o w s ： ( 1 ) as 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 mn e w g s pb a s e do nt h ed y n a m i c m i n s u pi sp r o p o s e d t r a d i t i o n a ls e q u e n t i a lp a t t e r nm i n i n gn e e d sp e o p l es e tu pt h e m i n s u p ，s ot h e r em u s tb es o m el i m i t a t i o n s i nt h i sd i s s e r t a t i o n ，t h ed y n a m i c m i n s u pw i l lb es e tu pb yu s i n gs t a t i s t i c sm e t h o d i th a sb e t t e rp e r f o r m a n c ei nt i m e a n ds p a c ep r o p e r t i e so v e rt r a d i t i o n a ls e q u e n t i a l p a t t e r nm i n i n ga l g o r i t h m su s i n g p a c k e dc a n d i d a t es e q u e n c e s ( 2 ) an e wc l o s e ds 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 mg - c l o s p a nb a s e do n g r a p hi sp r o p o s e d t h em i n i n go fc l o s e ds e q u e n c en o to n l yp r o v i d e st h es a m e i n f o r m a t i o n ，b u ta l s oi sm o r ec o m p a c ta n de f f e c t i v e f 2 s gi si n t r o d u c e dt oe x p r e s s t h es e q u e n t i a li n f o r m a t i o nr e l a t e dt ot h em i n i n gt a s kb ys c a n n i n gt h et r a n s a c t i o n d a t a b a s eo n l yo n et i m e b a s e do nt h i s ，t h eg r a p hr e p r e s e n t a t i o no ft h ed a t a b a s ec a n f u l l yu t i l i z et h ep r o p e r t yo fi t e mo r d e r i n gi nt h em i n i n gp r o c e s s ，t h u si m p r o v i n gt h e g e n e r a t i o ne f f i c i e n c yf r e q u e n tc l o s e ds e q u e n c e s t h e o r ya n a l y s i sa n de x p e r i m e n t s s h o wt h a ti th a sb e t t e rp e r f o r m a n c ei nt i m ea n ds p a c ep r o p e r t i e so v e rt r a d i t i o n a l c l o s e ds 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 ( 3 ) b a s e do nt h er e s e a r c ha b o v e ，a ne x p e r i m e n t a ls y s t e mo fm i n i n gs e q u e n t i a l p a t t e r n si s c a r r i e do u t ，a n dt h ea l g o r i t h m sa r ev a l i d a t e db o t he x p e r i m e n t a l l ya n d t h e o r e t i c a l l y 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 ，s t a t i s t i c sm e t h o d ，f r e q u e n ts e q u e n c e g r a p h ，c l o s e ds e q u e n t i a lp a t t e r n s 插图清单 图3 1 同一数据集下n e w g s p 算法与g s p 产生频繁序列个数比较2 6 图3 2n e w g s p 算法与g s p 执行时间比较2 6 图4 1 两种类型的边3 1 图4 2 一数据集下闭合序列和频繁序列个数比较3 5 图4 3g c l o s p a n 与c l o s p a n 、g s p 执行时间比较一3 5 图5 1s e q d m 系统功能模块3 7 图5 2s e q d m 系统主界面3 8 图5 3s e q d m 运行结果3 9 表格清单 2 1 交易数据库示例一一1 0 2 2 顾客序列表示1 0 2 3 系统进程调用数据示例一1 1 2 4 系统调用序列数据表示例1 1 2 5w e b 日志文件对应序列整理示例1 1 2 6 频繁项集及其映射1 3 2 7 由表2 2 库变换得到的数据库1 3 2 8 投影数据库和序列模式1 9 3 1i b m 数据生成器的命令行选项说明2 5 3 2 数据库d 1 c 5 t 3 n 0 0 5 s 4 1 1 2 5 的实验结果2 5 4 1 序列数据表一2 9 4 2 交易数据库示例二3 1 4 3 项目及其位置集合3 1 4 4 序列扩展s m 3 2 4 5 项扩展矩阵i m 3 2 4 6 数据库d 1 c 5 t 3 n 0 0 5 s 4 1 1 2 5 的实验结果3 4 4 7 数据库d * c 5 t 3 n 0 0 5 s 4 1 1 2 5 的实验结果( m i n s u p = 3 ) 3 4 i v 表表表表表表表表表表表表表表表表表 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据 我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得 金g 曼工些厶堂或其他教育机构的学位或证书而使用过的 材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文作者签名：孬锣功。签字日期：钙年乡月口日 学位论文版权使用授权书 本学位论文作者完全了解金目墨工些太堂有关保留、使用学位论文的规定，有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权世 王些厶堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 愿锰 签字日期：夕g 年易月d 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 加 咖 哳6 ， 胡利 孙 瑚 剑 阳 礁 字 脱7 矿15 a刁纱 致谢 值此论文完成之际，我很高兴有机会向在研究生阶段给予我支持和帮助的 各位老师、同学和亲人表示诚挚的感谢。 感谢我的导师胡学钢教授。我在硕士研究生课程学习和撰写学位论文的过 程中，得到了胡老师的精心指导。胡老师治学严谨，学识渊博，思想深邃，视 野雄阔，为我营造了一种良好的精神氛围。授人以鱼不如授人以渔，置身其间， 耳濡目染，潜移默化，使我不仅接受了全新的思想观念，领会了基本的思考方 式，掌握了通用的研究方法，而且还明白了许多待人接物与为人处世的道理。 感谢数据挖掘研究室的吴信东、田卫东、吴共庆、张玉红、张晶、谢飞等 老师，在课题完成的过程中他们给了我宝贵的意见和指导。 感谢我周围的一群风华正茂的有志青年。感谢李笛、周循、李培培、王强、 王翔、卫祥，与他们在一起学习生活的点点滴滴都是难忘而愉快的；感谢0 6 级与0 7 级的师弟师妹们，通过和他们的交流拓宽了我的思路；感谢合肥工业大 学人工智能与数据挖掘研究室每个成员对我的关怀和帮助，没有这个团结、上 进的集体就没有我今天的成绩。 感谢我的家人。父亲崇尚知识，热爱生活，对我影响至深，对我的学业也 给予了极大的鼓励与支持。母亲不顾身虚体弱、心力憔悴，毅然决然地表示即 使是节衣缩食，再辛苦也要全力支持我上学。古人云：“羊跪乳，鸦反哺。”今 后我将竭尽所能，加倍补偿这份一辈子也还不清的深情。 向合肥工业大学研究生部及计算机与信息学院的老师付出的辛勤工作表示 感谢。 作者：季钰 2 0 0 8 年5 月 第一章绪论 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，人 们面临的主要问题不再是缺乏足够的信息可以使用，而是面对浩瀚的数据海洋 如何有效地利用这些数据。面对这一挑战，数据挖掘1 1 ( d a t am i n i n g ，d m ) 和 数据库知识发现( 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 s ，k d d ) 应运而生，并显 示出强大的生命力。数据挖掘和知识发现使数据处理技术进入了一个更高级的 阶段。 1 1 数据挖掘 1 1 1 数据挖掘的概念和任务 ( 1 ) 数据挖掘的概念 数据挖掘的发展历史虽然较短，但从2 0 世纪9 0 年代以来，它的发展速度 很快，加之它是多学科综合的产物，目前还没有一个完整的定义，人们提出了 许多数据挖掘的定义【9 】，如s a s 研究所( 1 9 9 7 ) ：“在大量相关数据基础之上 进行数据探索和建立相关模型的先进方法”；b h a v a n i ( 1 9 9 9 ) ：“使用模式识别 技术、统计和数学技术，在大量的数据中发现有意义的新关系、模式和趋势的 过程”；h a n d e t a l ( 2 0 0 0 ) ：“数据挖掘就是在大型数据库中寻找有意义、有价值 信息的过程”。 还有的定义认为：数据挖掘是从数据集合中自动抽取隐藏在数据中的那些 有用信息的非平凡过程。这些信息的表现形式为：规则、概念、规律及模式等， 可帮助决策者分析历史数据及当前数据，从中发现隐藏的关系和模式，进而预 测未来可能发生的行为。 目前较通用的定义为：数据挖掘就是从大量的、不完全的、有噪声的、模 糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又 是潜在有用的信息和知识的过程。数据挖掘要解决的问题就是在庞大的数据中 寻找有价值的隐藏信息，加以分析，并将这些有意义的信息归纳成结构模式， 提供给有关部门在进行决策时参考【l 。 数据挖掘技术研究和探索的内容是极其丰富和具有挑战的，目前主要集中 在以下几个方面：数据挖掘技术与特定商业逻辑的平滑集成问题，数据挖掘技 术与特定数据存储类型的适应问题，大型数据的选择与规格化问题，数据挖掘 系统的构架与交互式挖掘技术，数据挖掘语言与系统的可视化问题，数据挖掘 理论与算法研究。 ( 2 ) 数据挖掘的任务 数据挖掘的目标是从数据中发现隐含的、有意义的知识，具体任务主要有 以下5 个方面： 分类：按照分析对象的属性、特征，建立不同的组类来描述事物。例如， 银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据这些来区 分新申请贷款的客户，以采取相应的贷款方案。 聚类：聚类分析又称为无指导的学习，其目的在于客观地按被处理对象的 特征分类，将有相同特征的对象归为一类。聚类与分类的区别是：分类规则需 要预先定义类别和分类样本；而聚类分析直接面向源数据，没有预先定义好的 类别和训练样本存在，所有记录都根据彼此相似程度加以归类。聚类增强了人 们对客观世界的认识，是概念描述和偏差分析的先决条件。 关联规则和序列模式的发现：关联是某种事物发生时其他事物会发生的这 样一种联系。“啤酒和尿布”就是从大型超市的购物篮中分析出的关联规则。与 关联不同，序列是一种纵向的联系。 预测：所谓预测，就是利用历史数据建立模型，再运用最新数据作为输入 值，获得未来变化的趋势或者评估给定样本可能具有的属性值或值的范围。一 个典型的例子是市场预测问题，数据挖掘使用过去有关促销的数据来寻找未来 投资中回报最大的用户。 偏差分析：偏差包括很多潜在的知识，如分类中的反常实例、不满足规则 的特例、观测结果与模型预测值的偏差等。偏差分析的基本方法是，寻找观测 结果与参照值之间有意义的差别，对分析对象的少数的、极端的特例的描述， 揭示内在的原因。 1 1 2 数据挖掘和相关技术的比较 数据挖掘融合了，而且将继续融合更多的学科，包括机器学习，模式识别， 统计，人工智能，专家系统，数据可视化和高效率计算等。数据挖掘与这些领 域的技术密切相关，但又有一定区别。下面简要讨论数据挖掘与这些技术的比 较。 ( 1 ) 数据挖掘与机器学习 数据挖掘和机器学习都是从数据中提取知识的过程，但二者是有区别的。 机器学习方法是计算机科学和人工智能发展的产物，是采用人工智能技术来实 现机器从客观世界中学习，而数据挖掘是在没有明确假设的前提下去挖掘信息、 发现知识，发现所得到的知识具有潜在性，有效性和实用性三个特征；数据挖 掘是面向大规模数据库的，且数据来源是现实世界中存在真实数据，存在一定 的缺失和噪音数据，而机器学习一般面向的是几百到几千条记录的数据，数据 大多是经过专家挑选的，没有或较少出现噪音和缺失数据 1 】。 机器学习方法可分为自组织学习和归纳学习两种，这些方法都在数据挖掘 过程中被运用。基于此，有人认为数据挖掘是利用机器学习的方法从数据库中 2 提取有价值的知识的过程，同时还继承和发展了其他学科的多种方法。 ( 2 ) 数据挖掘与数据库技术 数据挖掘从一开始就是面向应用的，它不仅是面向特定数据库的简单检索 查询调用，而且要对这些数据库进行微观即宏观的统计、分析、综合和推理， 用以指导实际问题的求解，力图发现事物间的相互联系，甚至可利用已有的数 据对未来的活动进行预测。 数据挖掘与目前数据库管理系统d b m s 的作用是不同的。首先，数据库管 理系统的侧重点是把大量的数据组织起来，以方便用户进行存取和维护，并对 数据的一致性和完整性进行约束。而数据挖掘则侧重于对数据库中的数据进行 分析，以得到有用的结果。再次，数据库中的数据库报表工具与数据挖掘也是 不同的，前者按用户提取数据库中的数据，进行简单的数学运算和处理，并以 特定方式提交给用户，而后者是要发现隐藏在数据背后的特征和趋势，给出关 于数据的总体特征和发展趋势。 ( 3 ) 数据挖掘与数理统计 数据挖掘与统计分析这两者之间的主要区别在于对大数据量的适应性，面 对记录数达10 万条以上的数据集，数据挖掘的算法必须仍然具有很好的性能； 数据挖掘需要考虑能对增量数据进行处理而不必从头计算一次；数据挖掘还需 要考虑如何处理数据集大于内存的问题及并行处理问题：此外，数据挖掘面向 解决工程问题。 数据挖掘不能替代传统的统计分析技术。相反，它是统计分析方法学的延 伸和扩展。大多数统计分析技术都基于完善的数学理论和高超的技巧，预测的 准确度还是令人满意的，但对使用者有很高的要求。而随着计算机能力的不断 增强，有可能利用计算机强大的计算能力只通过相对简单和固定的方法完成同 样的功能。 数据挖掘算法有些本来就是统计的方法。人们研究数据挖掘会关心它和大 数据量的结合( 有效性) ，会关心她的数据挖掘原语( 数据挖掘语言) 、算法性 能的优化、标准的接口等只有用软件实现时才考虑的事情。于是数据挖掘行业 制定了一些标准，比如，基于x m l 的p m m l ( 预言模型标记语言) ；微软的 o l ed bf o rd m ；s p s s 的c r i s p d m 。当然数据挖掘发展到这个程度时，就很 难看到其和统计的联系了。从这个意义上来说，数据挖掘仍然是计算机行业的 一个方向，而不是广义统计的一部分。同时，对于数据挖掘算法中来自机器学 习和人工智能的一部分，其核心是规则，而规则内部的获得机制虽然是基于数 理统计的，但这种技术本身已经不属于统计了。比如通过数据挖掘可以得出：“年 龄在3 0 3 5 ，工资在5 0 0 0 、8 0 0 0 元的客户会购买产品a ”。这是一个可以通过数 据挖掘获得的规则，在得出这个规则之前，算法会对数据集进行分析，该数据 集包括很多变量( 数据库的字段) ，“年龄”和“工资”是其中的两个，算法会根据 历史数据自动抽取这两个变量，而得出这样的规则。而依据统计方法，是不能 得出这样的规则的，它只能得出量化的概率关系，而规则的推导却不是统计学 的范畴。 1 - 1 3 数据挖掘应用热点 历经了十几年的发展，数据挖掘技术本身已经积累了一批有价值的理论和 技术成果。同时，包括统计学、人工智能等在内的相关学科的发展从某种程度 上对数据挖掘技术发展起到了极大地推动作用。根据麻省理工学院的科技评 论评估，“数据挖掘”技术是对未来人类产生重大影响的十大新兴技术之一。 如今的数据挖掘已成为计算机、信息科学以及相关领域的一个研究热点，而且 在银行、电信、保险、交通、零售以及天文学、分子生物学等领域得到应用。 就目前看来，将来的几个热点包括网站的数据挖掘( 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 ) 网站的数据挖掘 在对网站进行数据挖掘时，所需要的数据主要来自于两个方面：一方面是 客户的背景信息；而另一方面主要来自浏览者的点击流( c l i c k s t r e a m ) 。但有 的时候，客户不肯把这部分信息填写在登记表上。在这种情况之下，就不得不 从浏览者的表现数据中来推测客户的背景信息，进而再加以利用。 就分析和建立模型的技术和算法而言，网站的数据挖掘和传统数据挖掘的 差别并不是特别大，很多方法和分析思想都可以运用。所不同的是网站的数据 格式有很大一部分来自于点击流，和传统的数据库格式有区别。因而对电子商 务网站进行数据挖掘所做的主要工作是数据准备。 ( 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 1 都难以逾越这个 瓶颈。数据挖掘作为一种新的知识获取工具，将有效地改善专家系统的这种状 态，对工程的智能化、信息化、自动化的发展起着不可估量的作用。 1 1 4 数据挖掘面临的挑战 数据挖掘技术是一个年轻且充满希望的研究领域，商业利益的强大驱动力 将会不停地促进它的发展每年都有新的数据挖掘方法和模型问世，人们对它 的研究正日益广泛和深入。尽管如此，数据挖掘技术仍然面临着许多问题和挑 战：如数据挖掘方法的效率亟待提高，尤其是超大规模数据集中数据挖掘的效 率：开发适应多数据类型、容噪的挖掘方法，以解决异质数据集的数据挖掘问 题；动态数据和知识的数据挖掘；网络与分布式环境下的数据挖掘等；另外， 近年来多媒体数据库发展很快，面向多媒体数据库的挖掘技术和软件今后将成 为研究开发的热点。 1 2 频繁模式发现 如上节所述，在大规模数据集中发现频繁模式是数据挖掘的一个基本任务。 这类问题就是要在一类可能出现在数据集中的模式中，决定哪些模式是频繁地 出现的。它包括在事务数据库中发现关联规则、序列模式和在事件序列中发现 频繁情节等问题。 1 2 1 关联规则发现 从交易数据库中发现关联规则是r a g r a w a l 等人于1 9 9 3 年首先提出的 2 】， 已成为k d d 的重要研究方向之一。一个关联规则的例子是“9 0 的客户在购买 面包和黄油的同时也购买牛奶”，其直观的意义是：客户在购买某些东西的时候， 有多大的倾向购买另外一些东西。找出这样的规则，对于确定市场策略是很有 5 价值的。以后的诸多研究人员对关联规则发现问题进行了大量的研究 4 , 5 , 1 5 , 2 4 , 2 7 , 4 7 】。他们的工作包括对经典挖掘算法的优化以提高挖掘效率，如引入 随机抽样、并行的思想；提出各种扩展模型如泛化关联规则、周期关联规则， 对关联规则的应用进行推广等。 ( 1 ) 问题描述 发现关联规则问题的形式化描述如下： 设i = i l ，i 2 ，i m ) 是交易数据库d b 中项目的集合。d b 中的每个交易t 是 一组商品，显然满足t i ：每个交易有一个唯一的标识符，称作t i d 。如果项 目集x c _ t ，称交易t 支持x ；也称交易t 包含x 。关联规则是如下形式的一种 蕴含式：x y ，其中x c _ i ，y c i ，且x n y = 。如果d b 中有s 的交易支 持x ，称x 具有大小为s 的支持度，即p r o b ( x ) = s ，记为s u p p o r t ( x ) = s 。如果 d b 中支持x 的交易中有c 的交易同时也支持项目集y ，称规则x _ y 在交易 数据库d b 中具有大小为c 的可信度，即p r o b ( y i x ) = c 。如果项目集x 在交易 数据库d b 中支持度大于用户指定的最小支持度，称项目集x i 是频繁项目集 或频集。 关联规则的发现问题是：给定一个交易数据库d b ，求出所有支持度不低 于用户指定的最小支持度和最小可信度( m i n c o n f ) 的关联规则。 ( 2 ) 关联规则发现的经典算法 a g r a w a l 等人在1 9 9 3 年设计了一个基本算法，提出了挖掘关联规则的一个 重要方法这是一个基于两阶段频集思想的方法，将关联规则挖掘算法分为 两个子问题： 找到所有支持度大于最小支持度的项目集( 下文简称项集) 即频集； 使用从第一步得到的频集产生关联规则。对每一频繁项集a ，找到a 的 所有非空子集a ，如果s u p p o r t ( a ) s u p p o r t ( a ) m i n c o n f i d e n c e ，则生成关联规则 a j a a 。 事实上，在挖掘关联规则的整个执行过程中第一个子问题是核心问题。当 找到所有的频集后，相应的关联规则将很容易生成。 关于频繁项集有如下的特性：一个项集是频繁的当且仅当它的所有子集都 是频繁的。根据这个特性，算法使用了递推的方法来生成所有的频集，具体描 述如下： l 1 ：= l a r g el i t e m s e t s ； f o r ( k = 2 ；l k - 1 o ；k + + ) d o c k ：= a p r i o r i - g e n ( l k - 1 ) ； n e wc a n d i d a t e s f o r e a c ht r a n s a c t i o n st dd o 6 c t ：= s u b s e t ( c k ，t ) ； c a n d i d a t e sc o n t a i n e di nt f o r e a c hc a n d i d a t e sc c td o c c o u n t + + ； ) l k ：= c c kc c o u n t m i n s u p ) a n s w e r = k jkl k ； a p r i o r i g e n 函数以l k 1 ( 所有频繁( k 1 ) 项集) 作为输入参数，返回所有频繁 k 项集的集合l k ，由以下两步实现： 第一步，连接 i n s e r ti n t oc k s e l e c tp i t e m l ，p i t e m 2 ，p i t e m k - l ，q i t e m k - 1 f r o ml k - l p ，l k - 1 q w h e r ep i t e m l = q i t e m l ，p i t e m k 一2 = q i t e m k 一2 ，p i t e m k l q i t e m k - 1 ； 第二步，剪枝( p r u n i n g ) ，如果存在c 的( k 一1 ) - 子序列不包含于l k - 1 之中， 则删除所有项集c ec k 。 f o r e a c hi t e m s e t sc ec kd o f o r e a c h ( k 一1 ) 一s u b s e t sso fcd o i f ( s 萑l k 1 ) t h e n d e l e t ecf r o mc k ； 1 2 2 序列模式发现 在实际应用中，多数数据集中的数据都带有时间特征，我们称这类数据为 时态数据( t e m p o r a ld a t a ) 。例如某顾客在超市内某时间段内购买商品的序列。 时态数据挖掘的一个问题是从交易数据库中挖掘序列模式。和关联规则问题一 样，它也是源于对货篮数据的分析。序列模式挖掘的目标是从交易数据库中发 现客户购买行为中的序列模式，从而实现对顾客未来行为的预期。序列模式挖 掘算法通常需要将交易数据库按顾客标识重构，每个顾客的事务数据按购买时 间组成一个事务序列。这样由整个数据库中的数据集生成了一个含有多个长短 不一的序列的集合。然后从多个序列中间发现相同的子序列。满足一定支持度 的子序列便认为是要发现的序列模式。本文主要就是针对的序列模式发现研究。 1 2 3 关联规则与序列模式的比较 序列模式本质上可视为时态数据库( t e m p o r a ld a t a b a s e ) 上的关联规则，其 目标是发现事件间( i n t e r e v e n t ) 的模式( 序列) ，而关联规则是发现事件内 ( i n t e r a e v e n t ) 的模式( 称为项集) 。 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 算法。 第三章提出一种基于统计方法评定最小支持度大小，和传统的g s p 算法结 合形成新的算法n e w g s p 。传统的序列模式发现算法中的最小支持度需要人为 设定，具有一定的局限性。n e w g s p 采用采用统计方法，动态的确定最小支持 度，压缩候选序列集，较传统的序列模式发现算法在时间和空间性能上具有一 定的优越性。 第四章提出了以图结构表示序列数据库的模型，并在此基础上提出了一种 基于图结构发现闭合序列模式的新算法g c l o p s p a n 。挖掘闭合序列集合能在保 持信息完备性的前提下，比挖掘频繁序列全集更加精简有效。本文提出新的闭 合序列模式算法g c l o p s p a n ，该算法通过扫描一次数据库，将与挖掘任务相关 的信息映射在频繁2 序列图( f 2 s g ) 中，使用f 2 s g 表示数据库中的序列信息， 通过位置信息来计算支持度而不必反复扫描数据库，从而减少搜索空间，提高 了闭合序列的生成效率。理论分析实验证明，该算法较传统的闭合序列模式发 现算法在时间和空间性能上具有优越性。 第五章介绍了实现的序列发现系统( s e q d m 序列模式发现原型系统) ，该系 统包括了前面所提到的各种序列模式发现算法，可以方便的在同一平台下进行 算法的比较和分析，也有利于扩展和二次开发。 第六章是对全文的总结，对本文的主要研究工作进行简要地阐述，展望未 来可以进一步研究的方向。 第二章序列模式发现研究概述 本章我们全面研究了序列模式发现问题，包括数据库中频繁模式挖掘，序 列模式发现的问题定义，序列模式发现的研究现状以及几种经典序列模式发现 方法。 序列模式发现研究概况 序列模式挖掘的概念是r a g r a w a l 等人在1 9 9 5 年首先提出的，此后，人们 不断地研究和改进在时间序列数据库中挖掘序列模式和其他频繁模式的算法。 现有的序列模式挖掘算法主要分为两类：第一类是基于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 特性 m 的算法。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 7 】，g s p 算法【1 8 】，p s p 算法 3 2 】 等；有采取垂直数据格式( v e r t i c a ld a t af o r m a t ) 的算法，如s p a d e 算法【22 1 ，s p a m 算法【33 等。第二类是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 算法 ”】、p r e f i x s p a n 算法【2 0 】等。另外，c a n t u n e s 等人提出了 s p a r s e 算法【3 4 1 ，该算法的主要思想是将候选序列的产生和在投影数据库空间 搜索结合起来，每一步在产生出频繁元素后，通过增长长度寻找模式。该算法 应用在密集型数据库中能获得较好的性能。 以上算法都是在序列数据库中挖掘所有的序列模式，而且除了g s p 算法之 外，它们挖掘的都是普通的序列模式。每一个序列模式包含了组合数级的频繁 子序列，若序列模式的长度很长，则频繁子序列的数量往往大得惊人。 在很多序列模式挖掘任务中，用户不需要找出数据库中所有可能存在的序 列模式，而是加入一定的约束，找出用户感兴趣的序列模式l 35 3 6 j ，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 算法【3 7 能有效地挖掘多维序列模式，但在维度较高 时其挖掘性能会有所下降。 9 2 2 序列模式发现的形式化描述 2 2 1 数据源格式 序列挖掘可以适合很广泛的数据源形式，在对序列模式挖掘的形式化介绍 之前，先了解一下常用的数据源格式及背景。 ( 1 ) 交易数据库 带交易时间的交易数据库的典型形式是包含客户号( c u s ti d ) 、交易时间 ( t r a nt i m e ) 以及在交易中购买的项( i t e m ) 等的交易记录表。表2 1 给出了 一个这样数据表的示例( 为了清楚起见，我们对所有的交易按照客户号和交易 时间进行了排序) 。 表2 1 交易数据库示例一 客户号交易时间物品 ( c u s ti d ) ( t r a nt i m e ) ( i t e m ) l0 6 0 6 2 5c 10 6 0 6 3 0h 20 6 0 6 1 0a b 2 0 6 0 6 1 5c h 20 6 0 6 2 0d f g 20 6 0 6 2 5h 30 6 0 6 2 5c e g 40 6 0 6 2 5c 40 6 0 6 3 0 d q h 4 0 6 0 7 2 5h 50 6 0 6 1 2h 表2 2 顾客序列表示 客户号顾客序列 ( c u s ti m ( c u s t o m e rs e q u e n c e ) 1 2 3 4 5 这样的数据源需要进行形式化的整理，其中一个理想的预处理方法就是转 换成顾客序列，即将一个顾客的交易按交易时间排序成项目序列。例如表2 2 给出了表2 1 对应的所有顾客序列表。于是，对顾客购买行为的分析可以通过 对顾客序列的挖掘得到实现。 ( 2 ) 系统调用日志 操作系统及其系统进程调用是评价系统安全性的一个重要方面。通过对正 常调用序列的学习可以预测随后发生的系统调用序列，发现异常的调用。因此 序列挖掘是从系统调用等操作系统审计数据中发现有用模式的一个理想技术。 表2 3 给出了一个系统调用数据表示意，它是利用数据挖掘技术进行操作系统 安全性审计的常用数据源。 这样的数据源可以通过适当的数据整理使之成为调用序列，再通过相应的 挖掘算法表达到跟踪和分析操作系统审计数据的目的。表2 4 给出了一个可能 的调用序列生成结果，它把每个进程的所有调用按照调用时间组织程序列。 ( 3 ) w e b 日志 l o w e b 服务器的日志文件记录了用户访问信息，这些信息包括客户访问的i p 地址、访问时间、u r l 调用以及访问方式等考察用户u r l 调用顺序并从中发 现规律可以为改善站点设计和提高系统安全性提供重要的数据。对u r l 调用的 整理可以构成序列数据。如果这些序列数据是通过固定时间间隔整理而成，那 么其整理后的序列数据库可能如表2 5 所示。 在表2 5 中，诸如( b ，c ) 这类含有一个以上的序列元素记录了在采集的 时间间隔那被访问的u r l 的全体。当然，由于受采集间隔的限制，这里的b 和c 对应的u r l 的调用顺序就无法再区分了。 表2 3 系统进程调用数据示例 表2 4 系统调用序列数据表示例 进程号调用序列 ( 里! 吐虫 ! 竺皇! ! 一量曼旦旦曼里堡1 7 4 4 1069 9 2 2 2 形式化描述 文献e 1