数据挖掘.doc

中山大学硕士论文 序列模式挖掘算法研究中山大学硕士学位论文序列模式挖掘算法研究Research on Sequential Pattern Mining Algorithms专业名称：计算机软件与理论学位申请人：贺桂娇导师姓名及职称：印鉴教授答辩委员会主席（签名）：_答辩委员会委员（签名）：_ _ _ _ 中山大学信息与科学技术学院贰零零柒年拾月IV论文题目：序列模式挖掘算法研究专业：计算机软件与理论硕士生：贺桂娇指导老师：印鉴教授摘 要关联规则是数据挖掘中比较活跃的研究方向之一，它反映了大量数据中项目之间有趣的关联或联系，一个比较经典例子就是“90%的客户在购买面包和黄油的同时也购买了牛奶”，数据库中的每个项目以平等一致的方式来处理。而加权关联规则则考虑了各个项目的不同的关注度，从一定程度上提高了传统关联规则的兴趣度。序列模式是在关联模型中增加了时间属性，把数据之间的关联性与时间联系起来，寻找的事务之间在时间上的先后次序关系，预测将来可能出现的值的分布。目前，对序列模式挖掘算法的研究很多，主要集中在如何提高算法的时间效率和减少空间上的开销。但在庞大的交易数据库里，这些算法很容易产生几百、几千个序列模式，如果每个序列都要实验一遍，代价太高了且让人无所适从，如何从事务数据库中找出商家更感兴趣的精简的“黄金”序列就成了当务之急。因此本文在序列模式的基础上提出了偏爱度，并结合加权的概念，提出了FSPAM算法，经原型验证，该算法挖掘出的序列模式更精简且更有效。其次、序列模式的经典算法的主要思想都是最开始从数据库中找到所有长度为1的频繁序列，由此产生长度为2的频繁序列集，接着得到长度为3的频繁序列集，如此反复直到数据库不再发现频繁序列为止。象这样重复扫描数据库，造成系统沉重的负担而导致效率不佳。本文利用邻接矩阵来记录事物数据库中2-项频繁项集，进而生成需要的频繁模式。可以大大减少扫描数据库的次数，使系统的性能得到改善。关键字：关联规则，加权，偏爱度，序列模式Title:Research on Sequential Pattern Mining AlgorithmsMarjor:Computer Software and TheoryName:He GuijiaoSupervisor:Yin Jian ProfessorAbstractAssociation rule is one of the prevailing study orientations in data mining，which reflects interesting correlation or link among numerous data items. One typical example is that 90% customers purchase milk while purchasing bread and butter, each item in the database is dealt with in the same way . Yet in weight association rule, highlight degree of each item is considered, and interest in traditional association rule is improved to some extent. Frequent sequential patterns add property of time to association model , integrate time with correlation between data., seek after the time sequence of events and forecast the distribution of values .At present, studies on frequent sequential pattern mining calculation mainly focus on how to improve time efficiency and how to minimize space occupying. But this calculating may produce hundreds or even thousands of frequent sequential patterns from numerous database, if each of them needs to be tested, it will cost too much .So it is essential to seek the golden sequence which customers are most interested in. Therefore Preference based on Frequent sequential patterns is referred to in this thesis .Combined with the concept of weight , FSPAM calculation is put forward. Through primary test , frequent sequential pattern out of this calculation is more concise and more effective.Secondly ,the main thoughts about classic calculation of frequent sequential patterns begin by finding all the frequent sequences with 1 length, resulting in frequent sequence group with 2 lengths, then with 3 lengths and so on and on ,until no more sequence can be found in the database . So repeated scans on database burden the system, which results in low efficiency. In this thesis, adjacent arrays are used to record database frequent item-sets, further to produce frequency mode, to reduce database scans and improve the performance of the system.Key words：Association Rule, weight ,Frequent Sequential Pattern Mining, Frequent itemsets目 录摘 要IAbstractII目 录III第1章 绪论51.1 论文的研究背景51.2 论文选题的意义61.3 序列模式挖掘的国内外研究现状61.4 本文的主要研究内容71.5 本文的结构安排81.6 本章小结8第2章 数据挖掘与关联规则挖掘92.1 数据挖掘概述92.2 序列模式挖掘概述122.3 关联规则152.4 加权关联规则252.5 本章小结30第3章 序列挖掘模式及相关算法313.1 序列模式挖掘的概念与描述313.2 序列模式挖掘基本步骤：333.3 序列模式一般算法353.4 本章小结43第4章 基于邻接矩阵的加权偏爱序列444.1 序列模式改进算法的提出444.2 问题的描述454.3 有向邻接矩阵的引入474.4 加权偏爱支持度概念484.5 基于邻接矩阵的FSPAM算法。494.6 序列模式改进算法FSPAM挖掘步骤534.7 FSPAM挖掘算法示例说明544.8 算法的特点及性能分析57第5章 算法原型及结果分析605.1 背景介绍605.2 开发前的准备：615.3数据预处理615.4 实现方法645.5 结果分析665.6 本章小结66第6章 结论与展望686.1 本文结论686.2 存在的问题以及进一步研究方向686.3 未来研究展望69参考文献71附录 本文算法autoFSPAM原型代码73致 谢89论文原创性声明90学位论文使用授权声明90中山大学硕士论文 序列模式挖掘算法研究第1章 绪论1.1 论文的研究背景 在20世纪90年代，随着计算机应用的普及，信息技术得以快速发展，并在各个行业中逐渐被广泛应用，为企业竞争态势构成了不可忽视的影响。一方面，由于数据库管理系统的广泛应用，各个领域每时每刻都在产生大量的数据。根据一项研究显示，全世界的数据量每二十个月就会番一番1，在这些海量的数据中，往往蕴含有丰富的、对企业有指导意义的知识。另一方面，由于计算机硬件价格的逐渐下降、信息技术的普及化、数据存储、处理以及传输已成为任何企业都可以负担的投资，企业很难单靠传统的信息管理方式如简单的数据录入、查询、统计等事务性处理过程建立起竞争优势2。企业急需一种能从海量数据中发现潜在知识的“工具”，以解决“数据爆炸与知识贫乏”的矛盾。而对以上的挑战，数据挖掘和知识发现技术应运而生，并得到蓬勃的发展3，越来越显示出其强大的生命力。数据挖掘是从大量的、不完全的、有噪音的、模糊的、随机的实际数据中，提取隐含在当中人们不知道的潜在有用的信息和知识的过程4。它的一个重要的应用是关联规则的发现。关联规则发现是在数据库中寻找数据对象间的关联模式5，例如，“在购买面包和黄油的顾客中，90%的人同时也购买了牛奶。”就是一种关联模式，早期主要用于零售业交易数据分析，以进行物品更合理的摆放，最终提高销售量。因此，该方法有时也直接称为“货篮分析”。序列模式是从关联规则中演变而来，序列模式发现是在数据库中寻找基于一段时间区间的关联模式6，例如，“在某一时间购买个人电脑的所有顾客中，60%会在 3 个月内购买应用软件。”就是一序列模式。序列模式同关联模式非常相似，区别在于序列模式表述的是基于时间的关系，而不是关于数据对象间的关系。在实际应用中，多数数据集中的数据都带有时间特征，这类数据称为时态数据(Temporal Data)7，例如，某顾客在超市内某时间段内购买商品的序列、天气数据和生产数据等。序列模式挖掘最初是由于在零售业中的应用而发展起来的。现在，序列模式已经应用到了科研和商用的其他许多领域。例如，在医疗领域，一个病人每看一次病，他的症状就可以组成一次事务，而这个病人的所有看病记录(即所有事务)就可以形成一个“症状序列”，从所有病人的症状序列中挖掘出一个模式，这个模式将会帮助医生诊断这些症状预示着何种疾病。序列模式挖掘是数据挖掘中一个重要的、富有挑战性的研究课题，在实际中具有广泛的应用，包括顾客购物模式分析和互连网访问模式分析，以及序列分析或者其它与时间相关的处理过程分析，例如，科学实验、自然灾难事件、疾病防治、DNA 序列、股票序列的分析等。1.2 论文选题的意义 在零售业中对顾客的购买行为进行序列分析，那么就有可能发现顾客的购买习惯和购买特点。如果充分的利用顾客的这些购买特点，可以帮助许多商家制定销售决策，如促销分析、交叉购物、引导消费等，增加商品的销售量，提高企业的效益。通常，一个庞大的事务数据库经过挖掘引擎的筛选和处理后会生成大量的序列模式，并以序列的形式提供给最终用户，然而，事实证明这些序列的可靠性和有趣性并不像想象中那么完美，现有的许多序列的挖掘方法耗费很长的时间生成序列模式，而产生的序列有大量用户不感兴趣的（比如是显然的或不相关的），有的甚至是虚假的，当然也有用户确实需要的序列，那如何从大量的序列模式中去掉无用、虚假的序列，挖掘出精简有效的黄金序列是当务之急。其次，借用其他工具提高传统算法的效率，也是大多数研究员一直在讨论的问题。因此，挖掘出精简、高效的序列模式并应用到零售业中，产生有意义的信息，并将这些信息归纳作为企业决策时的参考，最终使企业具有更强大的竞争优势，这将会是一份重要意义和富有挑战性的工作。1.3 序列模式挖掘的国内外研究现状序列模式挖掘8的概念首先是由 R.Agrawal 等人在 1995 年对超市购物篮数据的分析提出的，此后人们不断地研究和改进在时间序列数据库中挖掘序列模式和其他频繁模式的算法。现有的序列模式挖掘算法主要分为两类。第一类是基于 R.Agrawal 和 R.Srikant 在 1994 年提出的 Apriori 特性9的算法。Apriori 特性首先应用在关联规则挖掘中，其基本思想是频繁模式的子序列也一定是频繁模式。基于 Apriori 特性，人们提出了一系列类Apriori 的序列模式挖掘算法，这些算法中有采用水平数据格式(Horizontal Data Format)的算法，如 AprioriAll 算法8、GSP 算法10等；有采用垂直数据格式(Vertical Data Format)的算法，如 SPADE 算法11等。第二类是 J.Han 等人提出的基于模式增长(Pattern-growth)策略的算法，如 FreeSpan 算法12、PrefixSpan 算法13等。另外，C.Antunes 等人提出了 SPARSE 算法14，该算法的主要思想是将候选序列的产生和在投影数据库空间搜索结合起来，每一步在产生出频繁元素后，通过增长长度寻找模式。以上这些算法都是在静态的序列数据库中挖掘所有的序列模式，它们都属于一般的序列模式挖掘算法。但是，由于一般的大型数据库都是随着时间的变化而不断更新的，当数据库发生变化之后，原先挖掘的一部分序列模式可能不再满足最小支持度，同时还可能有新的序列模式出现，如果使用上述算法，就必须在更新后的序列数据库中重新进行挖掘。在处理具有海量数据的大型数据库时，对整个数据库重新执行一般的序列模式挖掘算法显然是低效的。在这种情况下，一系列增量式序列模式挖掘算法被提出，其基本思想都是尽可能地利用已发现序列模式的信息来发现新数据库中的序列模式，从而提高模式挖掘的效率。Masseglia 等人提出了用于序列模式增量式更新的 ISE 算法15，该算法利用已有对原始数据库的挖掘结果来产生候选项目集，减少了候选项目集的规模。但没有降低对整个数据库的扫描次数，算法的 I/O 消耗仍然很大。周斌等人提出了在数据库更新的情况下的序列模式增量式挖掘算法IMSP，其主要思想是利用序列的 CTID 表来加速挖掘过程。但该方法要求预知前次挖掘的每个序列模式的 CTID 表，且在计算过程中将产生关于每个候选序列的 CTID 表。当数据库规模很大时，对存储空间的消耗很大。等等。此外，当前国内外学者还广泛关注以下的研究方向。1) 约束(Constrained)序列模式挖掘在很多序列模式挖掘任务中，用户不需要找出数据库中所有可能存在的序列模式，而是加入一定的约束，找出用户感兴趣的序列模式16。如 Agrawal 等人将序列模式挖掘问题加以泛化，引入了时间约束、滑动时间窗口(Sliding Time Window)和分类约束，并提出了 GSP 算法。2) 闭合(Closed)序列模式挖掘 当序列模式很长时，由于每一个序列模式包含了组合数级的频繁子序列，挖掘所需的开销很大，然而在实际应用经常需要挖掘特别长的模式，如DNA序列。闭合序列模式挖掘研究如何挖掘满足不存在与其具有相同支持度的超序列条件下的序列模式。 3) 多维(Multi-dimension)序列模式挖掘 在序列模式中融合感兴趣的多维信息，在考虑与时间戳相关属性的同时，挖掘多维信息中感兴趣的模式，将得到能提供给用户更丰富信息的多维序列模式。H.Pinto 等人提出的 UniSeq 算法能有效地挖掘多维序列模式，多维序列模式挖掘是复杂数据类型挖掘的一个前沿研究领域，有着极为广阔的应用前景。综上所述，可以看出如何在大型序列数据库中挖掘更高效、更实用价值的频繁序列模式是有待于进一步研究的课题。1.4 本文的主要研究内容数据挖掘是近年来兴起的多学科相互融合的应用技术，广泛地应用于各个领域，特别是金融业、商业管理、市场分析以及科学研究等领域。序列模式是数据挖掘研究的重要内容之一，人们对于它的理解认识与研究越来越重视，本文主要应用数据挖掘中有关理论，对序列挖掘的挖掘算法作一些探索性的研究。本文的主要研究内容如下： 对数据挖掘技术产生的背景作了概括性的描述，然后介绍了数据挖掘的基本概念和定义，接着说明了数据挖掘的功能以及可以发现的知识模式，阐述了数据挖掘的一般过程，详细描述了数据挖掘的常用技术方法及广泛的应用领域。 关联规则是序列模式的基础，它反映了大量数据中项目之间有趣的关联或相关联系。在关联规则中,各个项目都是按平等一致的方式加以处理,但事实上，不同的项目往往有不同的重要性,因此根据每个项的关注程度赋予不同的权值，能挖掘出企业感兴趣的利润较大商品的销售规则。 序列模式挖掘是在关联模型中增加了时间属性,寻找的是事务之间在时间上的先后次序关系,它根据数据随时间变化的趋势,发现某一时间内数据的相关处理模型,预测将来可能出现的值的分布。即可以预测用户将来可能的购买行为。 提出购买序列的偏爱度，能更好区别购买频繁的序列，同时引入不同商品的关注度，就能挖掘出利润较高的频繁序列，即黄金序列模式。 经典序列模式挖掘是从频繁项目集挖掘发展而来的，重复扫描数据库，造成系统沉重的负担，以邻接矩阵频繁模式来记录2-项频繁集，进而生成需要的频繁模式，可以大大减少扫描数据库的次数，使系统的性能得到改善。1.5 本文的结构安排第1章 绪论。主要介绍了本文的研究背景，序列模式的国内外研究情况，本文的选题意义以及本文的主要研究内容和基本结构。第2章 数据挖掘与关联规则挖掘。首先，论述数据挖掘技术应用产生的研究背景，介绍了数据挖掘的基本概念、定义，说明了数据挖掘的功能以及可以发现的知识模式，阐述了数据挖掘的一般过程；接着，详细的探讨了关联规则相关概念、算法及优缺点，最后介绍了加权关联规则，为后续章节做了很好的铺垫。第3章 关联规则中加入时间因子，引出序列模式以及它的基本理论，分析了几中常用的算法。 第4章 是基于邻接矩阵的加权偏爱序列算法研究。首先，本章提出一个同时考虑顾客购买支持度和商品权值的加权偏爱支持度的概念，能挖掘出更精简、利润更高的序列模式，其次，利用邻接矩阵来记录2-项频繁集，并利用矩阵的特点产生需要的序列模式，大大的提高了算法的效率，最后对它进行性能分析和实例说明。该章是本文的核心部分，力求表现数据挖掘的基本思想与相关挖掘算法基本原理的有效结合。第5章 对本文提出的算法，做了一个原型系统，第6章 对本文工作进行了结论性总结，并对未来工作进行了展望。1.6 本章小结本章第一节介绍了本课题的研究背景，第二节提出了论文的选题依据，课题研究的主要目的是把序列模式和零售业信息结合，有效的为企业的决策处理增加效用，第三节阐述了本课题研究领域的现状，第四节简单的概括本文每部分的组织结合和研究内容44中山大学硕士论文 序列模式挖掘算法研究第2章 数据挖掘与关联规则挖掘2.1 数据挖掘概述数据挖掘（Data Mining ，DM）技术可以帮助人们从大量的数据中智能地、自动地抽取隐含的、事先未知的、具有潜在价值的知识或信息。目前，数据挖掘不仅被许多研究人员看作是数据库系统和机器学习方面的一个重要研究课题，而且被许多产业界看作是一个能带来巨大回报的重要领域，从数据库或数据仓库中发现出来的规则和知识可以用在信息管理、查询响应、决策支持、过程控制等许多方面。2.1.1 数据挖掘的发展数据挖掘是一个逐渐演变的过程。在电子化数据处理的初期，人们试图通过某种方式来实现自动决策支持，当时的机器学习成为人们关心的焦点，机器学习的过程就是将一些已知的并被成功解决的问题作为范例输入计算机，机器通过学习这些范例总结并生成相应的规则，这些规则具有通用性，使用他们可以解决某一类问题。随后，随着神经网络技术的形成和发展，使人们的注意力转向知识工程。知识工程不同于机器学习那样给计算机输入范例，让其生成规则，而是直接给计算机输入已被代码化的规则，计算机通过使用这些规则来解决某些问题。专家系统就是使用这种方法所取得的成果，但它投资大，效果不甚理想等不足。二十世纪八十年代人们又在新的神经网络理论的指导下，重新会到机器学习的方法上，并将其成果应用处理大型商业数据库，从而产生了一个新的术语数据库中的知识发现（Knowledge Discovery in Database，KDD）。1989年8月，在第十一界国际人工智能联合会议的专题研讨会上，首次提出了基于数据库的知识发现技术。到目前为止，由美国人工智能协会主办的KDD国际研讨会已经召开了8次，规模由原来的专题研讨会发展到国际学术大会，研究中心也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的渗透。1995年，在加拿大召开了第一届知识发现和数据挖掘国际学术会议。由于数据库中的数据被形象的喻为“矿床”，因此数据挖掘一词很快流传开来。在1995年的美国计算机年会（ACM）上，正式提出了数据挖掘的概念。由于数据挖掘是KDD过程中最为关键的步骤，在实际应用中对数据挖掘和KDD这两个术语往往不加以区别。1998年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议上不仅进行了学术讨论，并且由30多家软件公司展示了他们的数据挖掘软件产品，不少软件已经在北美、欧洲等国得到应用。1999年，亚太地区在北京召开的第三届PAKDD会议收到158篇论文，反响空前热烈。IEEE的Knowledge and Data Engineering会刊率先在1993年出版了KDD技术专刊。并行计算、计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专刊和专题讨论，甚至到脍炙人口的程度。2.2.2数据挖掘的定义数据挖掘（Data Mining）就是从大量的、不完全的、有噪音的、模糊的、随机的实际应用的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。与数据挖掘相近的同义词有数据融和、数据分析和决策支持等。这个定义包括好几层含义：数据源必须是真实的、大量的、含噪音的；发现的是用户感兴趣的知识，发现的知识要可接受、可理解，可运用，并不要求发现放之四海皆准的知识，仅支持特定的问题发现。发现知识可以是数学的，也可以是非数学的，可以是演绎的，也可以是归纳的。发现的知识可以用于信息管理，查询优化，决策支持和过程控制等，还可以用于数据自身的维护。因此，数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的技术热点。简而言之，数据挖掘其实是一类深层次的数据分析方法。数据分析本身已经有很多年的历史，只不过在过去的数据收集和分析的目的是用于科学研究，另外，由于当时计算机能力的限制，对大量数据量进行分析的复杂数据分析方法受到很大的限制。现在，由于各行业业务自动化的实现，商业领域产生了大量的业务数据，这些数据不再是为了分析的目的而收集的 ，而是由于商业运做而产生。分析这些数据也不再是单纯的为了研究需要，更主要是为了商业决策提供真正有价值的信息，进而获取利润。但所有企业面临一个共同的问题是；企业数据量非常大，而其中真正有价值的信息却很少，因此从大量的数据中经过深层分析，获得有利于商业运作、提高竞争力的信息，就象从矿石中淘金一样，数据挖掘也因此而得名17。因此，数据挖掘可以描述为；按企业即定业务目标，对大量的企业数据进行探索和分析，揭示隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。2.1.3 数据挖掘对象原则上讲，数据挖掘可以在任何类型的信息存储上进行。这包括关系数据库、数据仓库、事务数据库、面向对象的数据库、对象关系数据库、空间数据库、时间序列数据库、文本数据库、多媒体数据库和万维网等。2.1.4 数据挖掘的目的数据挖掘的任务是从大量的数据中发现知识，知识是人类认识的成果或结晶。包括经验知识和理论知识。从工程角度定义，知识是有助解决问题的有格式的可复用的信息。在传统的决策支持系统中，知识库的知识和规则是由专家或程序员建立的，是外部输入的，而数据挖掘的任务是发现大量的数据中尚未被发现的知识，是从系统内部自动获取知识的过程，对于那些决策者已经明确了解信息，可以查询、联机分析（OLAP）或者其他工具直接获得，比如“列出各子公司上个月的销售情况“。而另外一些隐藏在大量数据中的关系、趋势，即使是管理这些数据的专家也没有能力发现，这些信息对于决策者而言可能是至关重要的，数据挖掘的目的正是为了解决此类问题。数据挖掘发现的知识通常是用以下形式表示的：概念（Concepts）、规则（Rules）、规律（Regularities）、模式（Patterns）、约束（Constraints）、可视化（Visualizations）等5。这些知识可以直接提供给决策者，用以辅助决策过程，或者提供给领域专家，修正专家已有的知识体系，也可以作为新的知识专门存储到应用系统的知识存储机构中，比如专家系统（Expert System）、规则库（Rule Base）等。2.1.5 数据挖掘过程。如下图2-1图 2-1 数据挖掘的通用过程图 2-1 是数据挖掘的通用过程，一般由以下步骤组成：数据清理，消除噪音或者不一致的数据。数据集成：将多种数据源组合在一起。数据选择：从数据库中检索与分析任务相关的数据。数据变换：数据变换或统一成适合挖掘的形式。数据挖掘：利用智能手段提取数据中的特征模式。模式评估：根据某种兴趣度度量，识别表达知识的有趣模式。知识表示：从模式中提取用户可以直接采用的知识。首先将各种数据采集到数据库中，通过数据清理和集成把数据库中这些数据有用的部分提取出来，然后放到一个大的数据仓库中。在数据仓库中根据挖掘的目标选择或变换相关的数据集，采用某种挖掘算法对数据集进行挖掘，由挖掘得出的模式数量一般很大，通过模式评估获得有趣的模式，最后从这些模式中提取出人们用于决策或者研究的知识。在理解数据挖掘的具体实施过程时，我们还应该注意以下几点：1）数据挖掘仅仅是整个挖掘过程中的一个重要步骤。2）数据挖掘质量的好坏不但取决于所选用的数据挖掘技术，而且还取决于所挖掘的数据的质量和数量，如果选择了错误的数据或不适当的数据，或对数据进行了不适当的转化，则挖掘结果不会成功。3）真正的挖掘过程是一个不断反馈的过程。比如，用户在挖掘过程中发现选择数据不太满意，或使用的挖掘技术产生不了期望的结果。这时，用户需要重复先前的过程，甚至重新开始。4）可视化技术在数据挖掘的各个阶段都应起着重要的作用。比如在数据预处理阶段，用户可以用散点图、直方图等统计可视化技术来显示有关数据，以期对数据有一个初步的了解，从而为更好地选择数据打下基础，在数据挖掘阶段，用户则要使用与领域问题有关地可视化工具，在结果表示阶段，则可能要用到可视化技术以使发现知识更易于理解等。2.1.6 数据挖掘的主要技术数据挖掘是一个交叉学科领域，受多个学科影响，包括数据库系统、统计学、机器学习、可视化和信息科学。此外，它还依赖于所用的数据挖掘方法，以及可以使用的其他学科的技术，如神经网络、模糊或粗糙集理论、知识表示、归纳逻辑程序设计或高性能计算；依赖于所挖掘的数据类型或给定的数据挖掘应用。数据挖掘系统也可能集成空间数据分析、信息检索、模式识别、图像分析、信号处理、计算机图形学、Web 技术、经济、商业、生物信息学或心理学领域的技术。数据挖掘有多种不同的分类方法。从挖掘技术的角度考虑，有机器学习、统计学、可视化、模式识别、神经网络以及面向数据库或数据仓库的技术等，对于复杂的数据挖掘系统可能同时运用多种数据挖掘技术，或者采用有效的、集成的技术；从应用的角度分析，不同的应用领域需要集成针对该应用特别有效的方法，而普通的、全能的数据挖掘系统可能无法胜任特定领域的挖掘任务。2.2 序列模式挖掘概述2.2.1 什么是序列模式挖掘序列模式挖掘5 (Sequential Pattern Mining) 即从序列数据库中发现频繁子序列以作为模式，它是指挖掘基于时间或者其它顺序的出现频率高的模式。它是一类重要的数据挖掘问题，有着非常广泛的应用前景，包括顾客购买行为的分析、网络访问模式分析、科学实验的分析、疾病治疗的早期诊断、自然灾害的预测、DNA序列的破译等等。序列模式挖掘问题是由Agrawal 和 Srikant最先提出的：给定一个序列集，其中每一个序列由项集构成，然后给定由用户确定的最小支持度阈值(Minimum Support Threshold), 序列模式挖掘就是去发现所有的频繁子序列（即：这些子序列的出现频率不小于给定的最小支持度）。序列模式的一个例子就是“一个 9 个月前买了一台 PC 的顾客有可能在一个月内买一个新的 CPU”。由于许多商业交易、电信记录、天气数据和生产过程都是时间序列数据，在针对目标市场、客户吸引、气象预报等的数据分析中，序列模式挖掘是很有用途的。进行序列模式挖掘时有很多参数对于挖掘的结果影响很大。首先是时间序列的持续时间(Duration) T，也就是这个时间序列的有效时间或者是用户选择的一个时间段，例如 1999 年。这样序列模式挖掘就被限定为对某段特定时间内的数据的挖掘。其次是事件折叠窗口(Event Folding Window) w，在一段时间内发生的几件事件可以被看作是同时发生的，如果 w 被设置为持续时间 T 的长度，我们就可以发现一些关联模式 “在 1999 年，一个买了 PC 机用户又买了数字照相机”（并不考虑先后顺序）。如果 w 被设置为 0，那么序列模式就是两个事件发生在不同的时间里 “已经买了 Pc 机和内存的顾客有可能在以后买一个光驱”。如果 W 被设置为一段时间间隔（例如一个月或者是一天），那么在这段时间的交易在分析中可以被看作是同时发生的。最后一个参数是时间间隔(Interval) int, 这个参数表示发现的模式的时间间隔。int = 0：表示没有时间间隔；即是，所找出的是严格连续的序列。我们要考虑参数 w，例如如果事件折叠窗口 w 设置为一个星期，那么发生了事件 A, 事件 B 会在一星期内发生。Min_interval int Max_interval：表示我们要找出最小时间间隔为 Min_interval，而最大时间间隔为 Max_interval 的模式。例如，模式 “如果某人租了影片 A, 很可能会在 30 天内租影片 B” 蕴涵 int 30。int = c 而 c 不为 0, 那么意味着两件事的间隔为固定的时间，例如：“每当股票 A 下跌了超过 5%，那么两天后会发生什么事？”，将搜索间隔 int = 2(天)的序列模式。2.2.2 序列模式挖掘传统算法及瓶颈到目前为止很多研究已经对如何有效地进行序列模式挖掘作出了贡献。几乎所有频繁模式挖掘的方法都是基于Apriori性质（频繁项集的所有非空子集都一定也是频繁的，或一个非频繁模式的任何超模式（Super-Pattern）一定非频繁）的算法，本文称之为Apriori-like算法。Apriori-like序列模式挖掘方法尽管降低了搜索空间，但是要面临三个不容忽视的内在的开销，这些开销是不依赖具体的实现技术而独立的。（1）潜在的巨大的候选序列集因为候选序列集包括了一个序列中的元素和项的重复的所有可能的排列； 因此即使对一个适度大小的种子集合， Apriori-like算法也可能会产生一个非常庞大的候选序列集。例如：如果有1000个长度为1的频繁序 列 设 为 , , 一 个 Apriori-like 算 法 将 生 成1000 1000+=1,499,500个候选序列;其中1000 1000指：, , , ；指 ：, 。（2） 对数据库的多遍扫描因为每一次对数据库的扫描候选序列的长度仅增长1，所以若要发现长度为15的序列模式(abc)(abc)(abc)(abc)(abc), Apriori-like算法必须扫描数据库至少15次。（3） 当要挖掘出的序列模式较长时的算法瓶颈一个长的序列模式必须由短的序列模式组合而成，但是这样的候选序列的数量的增长与要被挖掘序列模式的长度的增长是成指数关系的。例如：假定在一个数据库中仅有一个序列：,其长度为 100，在这个数据库中最小的支持度阈值为 1（即每一个出现的模式都是频繁的）。为了得出这个长度为 100 的序列模式 Apriori-like 算法必须产生100个长度为1的候选序列，100100+= 14,950个长度为2的候选序列， =161,700个length-3候选序列， ，很明显，所有要被产生的候选序列个数要大于。总之，传统的序列模式挖掘算法，当从序列数据库中挖掘长模式或支持度较低时，存在所挖出的频繁子序列个数会随模式长度增加而爆炸性增长，以及将会遇到较高的计算复杂度等等很多问题。这样便限制了这些算法的应用，因为很多有用的长模式不能被有效地挖掘出来，而在很多实际应用中，如进行 DNA 序列分析和股票序列分析等，经常会碰到含有大量长模式的序列数据库。因此，很有必要发现更有效的方法来解决这些问题。2.2.3 序列模式和关联规则的异同点序列模式是从关联规则演化出来，因此它的一些概念和算法与关联规则中的十分相似，但又比关联规则更为复杂。 相同点。 两者的挖掘对象都是事务数据库，都希望从事务数据库中发现规律，从而知道管理者根据规律做出决策，将利益最大化。两者都是以项为基本单位，项集的概念也是相同的。都有包含定理，都有支持率的概念。挖掘的基本步骤相同，先根据最小支持度找出数据库中的所有频繁序列(或项目集合)，接着在所有频繁序列(或项目集合)中产生序列模式(关联规则)。序列模式的挖掘算法都是由关联规则挖掘的算法演变而来，比如AprioriAll 是由 Apriori 演变而来。 不同点。 关联规则挖掘的是顾客的某一次购物行为中的规律，而序列模式挖掘的是顾客的多次购物行为中的规律，挖掘的结果是由若干项集组成的序列；序列模式挖掘中定义了序列，序列是若干项集的有序集合，关联规则中没有“序列”的概念；关联规则中除了定义支持度用来衡量关联规则整个数据集中的统计重要性外，还定义了置信度用来衡量关联规则的可信程度，在序列模式中衡量序列模式是否是用户所需要的标准之一是支持度，没有置信度的概念；挖掘任务的不同决定了挖掘算法的不同，由于序列模式挖掘算法挖掘的是由若干项组成的序列，而关联规则挖掘算法挖掘的仅仅只是项。所以，在数据库中搜索一个序列显然要比搜索一个项集更加困难，在同样的条件下，候选序列的个数要比候选项目集的个数多得多。从这两方面来说，序列模式挖掘算法比关联规则挖掘算法更为复杂。2.3 关联规则序列挖掘（Sequential Mining）或称序列模式挖掘，是指从序列数据库中发现相对时间或其他顺序所出现的高频率的子序列。它的分析与关联规则是一样的，是在关联规则的基础上加入了时间因子生成的，更重视的是前因（后果）关系，因此本章先介绍与序列模式相关的关联规则、加权关联规则的基本概念以及常用算法，然后在下一章讨论了序列模式的基本概念、基本理论以及常用的算法。2.3.1关联规则基本作用关联规则挖掘是一种非常重要的知识发现方法。最早是由Agrawal等人提出的（1993），最初提出的动机是针对购物篮分析（Basket Analysis）问题提出的，其目的是为了发现交易数据库（Transaction Database）中不同商品之间的联系规则。通过对交易数据库的智能分析，可以获得有关的顾客购买模式的一般的规则，这些规则刻画了顾客购买行为模式，可以用来指导商家科学的安排进货、库存以及货架设计等。此外，在其他领域也得到了广泛的讨论。2.3.2关联规则定义关联规则是发现交易数据库中不同商品(项)之间的联系，即购买了某一商品对购买其它商品的影响。 通过关联分析，可以发现三种规则：有用的、价值不高的、费解的。价值不高的规则往往是对一些商业领域内众所周知的规则的重现。比如今天是情人节，那么鲜花的价格肯定会暴涨，这样的规则己经为人们所感知并运用到了商业运作中。费解的规则往往是数据中一些偶然的东西。比如：有一天某个超市发现购买消夏商品的顾客增加，但是只有这一天销量特别突出，前后销量趋于平常。造成这种偶然的情况的原因很可能是偶然的，如附近的几个居民区那天停电等。对于这样费解的规则，因为它出现的概率很低，我们没有必要对其进行分，也没有必要采取什么行动。只有在事物之间潜在的经常发生的规则才是有用的规则，“潜在的”就是说别人还没有发现的，还没有广泛的应用到商业运作中。“经常发生的”说明规则发生的概率很大，我们对其采取行动产生的效益可能也很大。2.3.2关联规则的表述形式一个数据库的关联规则挖掘可以描述如下：设是个项目的集合，事务数据库是由一系列具有唯一标识TID的事务组成，每个事务（i=1，2，,n）都对应I上的一个子集。定义2-1 设，项目集（Itemset）在数据集D上的支持度（Support）是包含的事务在D中所占的百分比，即support（）=| |/|D|定义2-2 对项目集I和事务集D，T中所有满足用户指定的最小支持度（Minsupport）的项目集，即大于或等于Minsupport的I的非空子集，成为频繁项目集（Frequent Itemsets）或者大项目集（Large Itemsets）。在频繁项目集中挑选出所有不被其他元素包含的频繁项目集称为最大频繁项目集（Maximum Frequent Itemsets）或最大大项目集（Maximum Large Itemsets）定义2-3 一个定义在I和D上的形如的关联规则通过满足一定的可信度、信任度或置信度（Confidence）来给出。所谓规则的可信度是指包含和的事务数与包含的事务数之比，即confidence(=)=support()/support()其中， I，= 定义2-4 D在I上满足最小支持度和最小信任度（Minconfidence）的关联规则称为强关联规则（Strong Association Rule）通常我们所说的关联规则一般是指上面定义的强关联规则。2.3.4关联规则挖掘步骤：一般地，给定一个事务数据库，关联规则挖掘问题通过用户指定最小支持度和最小可信度来寻找强关联规则的过程。关联规则挖掘问题可以划分成两个子问题。（1）发现频繁项目集通过用户给定的最小支持度，寻找所有频繁项目集，即满足Support不小于Minsupport的所有项目子集。事实上，这些频繁项目集可能具有包含关系。一般地，我们只关心那些不被其他频繁项目集所包含地所谓地最大频繁项目集的集合。发现所有的频繁项目集是形成关联规则的基础。（2）生成关联规则通过用户给定的最小可信度，在每个最大频繁项目集中，寻找Confidence不小于Minconfidence的关联规则。第2个子问题比较简单，因此目前第1个子问题是研究的重点。2.3.5 经典的发现频繁项目集的Apriori算法Apriori算法是一种最有影响力的挖掘布尔关联规则频繁项集的算法，算法使用频繁项集性质的先验知识。正如我们将看到的，Apriori使用一种称作逐层搜索的迭代方法，k-项集用于探索(k+1)-项集。首先，找出频繁1-项集的集合。该集合记作。 用于找频繁2-项集的集合，而用于找，如此下去，直到不能找到频繁k-项集。找每个需要一次数据库扫描。为提高频繁项集逐层产生的效率，一种称作Apriori性质的重要性质用于压缩搜索空间。我们先介绍该性质，然后用一个例子解释它的使用。 Apriori性质：频繁项集的所有非空子集都必须也是频繁的。Apriori性质基于如下观察：根据定义，如果项集I不满足最小支持度阈值S，则I不是频繁的，即P(I)S。如果项A添加到I，则结果项集(即)不可能比I更频繁出现。因此，也不是