序列模式挖掘及其应用研究

序列模式挖掘及其应用研究摘 要序列模式挖掘是数据挖掘研究的一个重要的研究领域。目前，成熟的序列模式挖掘算法主要有三类：基于 Apriori 性质的候选码生成 -测试的算法；基于垂直格式的候选码生成- 测试的算法；基于投影数据库的模式增长算法。近年来，序列模式挖掘在分布式环境下的应用的研究逐渐成为热点，提出了各种算法。本文介绍序列模式挖掘算法及各自的优缺点和在分布式环境下的应用，在此基础上发现了分布式环境下站点之间局部模式子树的传输存在问题。本文提出了分布式环境下基于叶子节点传输的序列模式挖掘方法 LMSP(leaf-based mining of sequential patterns)，即在生成全局 L2 序列模式的过程中，各站点传输局部 L2 子树时只传输局部子树的叶子节点的序列以及所有节点的支持度计数，在选举站点上再根据接收到的子树信息将局部 L2 子树还原。接着又简单地提出约减的树结构的传输，除根节点外的每个节点都只记录相对其父节点的后缀序列。实验结果表明，LMSP 算法性能优于 FDMSP 算法。文章最后简单的介绍了序列模式挖掘的实际应用。关键词：数据挖掘；序列模式；分布式算法；数据传输AbstractSequential pattern mining is an important domain of data mining. Now there are three types of mature algorithms of sequential patterns mining: Apriori-based algorithms by candidate sequence generating-and-testing; vertical format database based algorithms by candidate sequence generating-and-testing; projection database based algorithms with by pattern-growth. In recent years, mining of sequential patterns in distributed environment is becoming hot topic, and some algorithms have been proposed. In this paper, three algorithms of sequential pattern mining and advantages and disadvantages of them are introduced, and then the applications of sequential pattern mining algorithms in distributed environment. Since this, we find a problem of local pattern subtree transportation from one site to another in distributed environment. In this paper, we propose a leaf-based algorithm in distributed environment, LMSP (leaf-based mining of sequential patterns), only transport the leaf node sequences and all the support counts of the local L2 subtree, while every site transporting the local L2 subtree to polling site in the course of global L2 patterns generating. At polling site, we get the local L2 subtree back from received subtree message. And we also propose transportation of reduction subtree simply， all the nodes (except the root) register only suffix according to its parent instead of the entire sequence. The experiments show that the algorithm LMSP outperforms the algorithm FDMSP. The last part of this paper, we simply introduce the applications of sequential pattern mining.Key words: data mining; sequential pattern; distributed algorithm; data transportation目 录1. 引言 .11.1 数据挖掘概述 .11.1.1 什么是数据挖掘？.11.1.2 数据挖掘能做什么？.11.1.3 数据挖掘技术的发展前景.21.2 序列模式挖掘概述 .21.2.1 序列模式挖掘定义.21.2.2 序列模式挖掘传统算法及瓶颈.32. 序列模式挖掘算法 .42.1 序列模式挖掘基础知识 .42.1.1 相关定义.42.1.2 相关性质和定理.52.2 序列模式挖掘算法分析 .62.2.1 GSP 算法 .62.2.2 FreeSpan 算法 .82.2.3 PrefixSpan 算法 .102.2.4 三类算法分析与比较.123. 分布式环境下的序列模式挖掘 .153.1 相关概念 .163.2 分布式环境下序列模式挖掘算法 .173.2.1 算法主要思想.173.2.2 算法详细描述.203.2.3 约减 的树结构传输.233.3 LMSP 算法性能分析 .234. 序列模式挖掘的应用 .254.1 会员顾客购物模式挖掘 .254.2 网络入侵检测系统 .265. 小结 .2711. 引言1.1 数据挖掘概述1.1.1 什么是数据挖掘？日常生活中我们经常遇到这种情况：超市的经营者希望将顾客经常同时购买的商品放在临近的货架上，以增加销售；保险公司的决策者想知道购买某种保险的客户一般具有哪些特征（比如年龄或社会身份） ，以制定出有效的营销策略；医学研究人员希望从许多病历中找出同种疾病患者的共同特征，从而为预防和治愈这种疾病提供帮助。现有信息管理系统中的数据分析工具，无论是查询、统计还是报表，都是对指定的数据进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取，所以无法对上述问题给出答案。然而随着信息系统的广泛应用和数据量的急剧增加，人们希望能够提供更高层次的数据分析功能，从而更好的为决策和科研工作提供支持。为了满足这种需求，从大量的数据中提取出隐藏在其中的有用信息，将机器学习应用于大型数据库的数据挖掘（Data Mining）技术得到了很大的发展。数据挖掘，也称为数据库中的知识发现（Knowledge Discovery in Database, KDD） ，是从大量的数据中提取出可信、新颖、有效并能被人理解的模式的高级处理过程。数据库中的知识发现过程一般由以下步骤组成 1：1） 数据清理（消除噪音或不一致数据）2） 数据集成（多种数据源可以组合在一起）3） 数据选择（从数据库中检索与分析任务相关的数据）4） 数据变换（数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作）5） 数据挖掘（基本步骤，使用智能方法提取数据模式）6） 模式评估（根据某种兴趣度度量，识别表示知识的真正有趣的模式）7） 知识表示（使用可视化和知识表示技术，向用户提供挖掘的知识）由此可见，数据挖掘是数据库中知识发现的一个步骤，并且是最重要的一个步骤。我们往往不加以区别的使用 KDD 和数据挖掘，一般在研究领域被称为数据库中知识发现的，在工程领域则称为数据挖掘。1.1.2 数据挖掘能做什么？数据挖掘所涉及的学科领域和方法很多，以下是四种非常重要的发现任务 2：2数据总结，其目的是对数据进行浓缩，给出它的紧凑描述。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。分类，其目的是学会一个分类函数或分类模型（也称作分类器） ，该模型能把数据库中的数据项映射到给定类别中的某一个。聚类，是把一组个体按照相似性归成若干类别，即“物以类聚” 。它的目的是使属于同一类别的个体间的距离尽可能地小，而不同类别间的距离尽可能地大。关联规则，是形式如下的一种规则， “在购买面包和黄油的顾客中，有 90的人同时也买了牛奶”(面包黄油=牛奶) 。关联规则发现的思路还可以用于序列模式发现。用户在购买物品时，除了具有上述关联规律，还有时间或序列上的规律。1.1.3 数据挖掘技术的发展前景随着 KDD 在学术界和工业界的影响越来越大，国际 KDD 组委会于 1995 年把专题讨论会更名为国际会议，在加拿大蒙特利尔市召开了第一届 KDD 国际学术会议，以后每年召开一次。近年来，KDD 在研究和应用方面发展迅速，尤其是在商业和银行领域的应用比研究的发展速度还要快。目前数据挖掘的研究方向主要有两方面：一是对数据挖掘方法的进一步研究，主要是要适应更大型的数据库、更高的维数和更复杂的关系；二是数据挖掘的应用，尤其是数据挖掘系统的开发，并且在商业、经济、金融、管理等领域都取得了应用性成果。数据挖掘的发展趋势 34主要有：数据挖掘与数据库系统、数据仓库系统和 Web数据库系统的集成；复杂数据类型的挖掘；数据挖掘中的隐私保护和信息安全。1.2 序列模式挖掘概述1.2.1 序列模式挖掘定义序列模式挖掘（sequential pattern mining）是一类重要的数据挖掘问题，且有着广泛的应用范围和发展前景，比如顾客购买行为的分析、网络访问模式的分析、科学实验的分析、自然灾害的预测、疾病治疗的早期诊断、DNA 序列的破译等等。序列模式挖掘问题是由 Agrawal 和 Srikant 在文献5中最先提出的，文中对序列规定了时间限制、滑动时间窗口和用户规定的分类，并总结了序列模式的定义：给定一个序列集，其中每一个序列由项集构成，然后给定由用户确定的最小支持度阈值3(minimum support threshold)，序列模式挖掘就是去发现所有的频繁子序列（即：这些子序列的出现频率不小于给定的最小支持度） 。1.2.2 序列模式挖掘传统算法及瓶颈到目前为止对如何有效地进行序列模式挖掘的研究已经取得了很好的进展。传统的序列模式挖掘算法都是基于 Apriori 性质（频繁项集的所有非空子集都一定也是频繁的，或一个非频繁模式的任何超模式都一定非频繁）的算法，这类算法我们称之为Apriori-like 算法。Apriori-like 序列模式挖掘虽然降低了搜索空间，但是却带来了三个不容忽视的开销，并且这些开销是不依赖具体的实现技术而存在的。1） 潜在的巨大的候选序列集因为候选序列集包括了一个序列中的元素和项的重复的所有可能的排列；因此即使对一个适度大小的种子集合，Apriori-like 算法也可能会产生一个非常庞大的候选序列集。例如：如果有 1000 个长度为 1 的频繁序列设为,，一个Apriori-like 算法将产生 10001000+1000999/2 =1,499,500 个候选序列；其中10001000 指：, , ,；1000999/2 指：,。2） 对序列数据库的多遍扫描因为每一次对序列数据库的扫描，候选序列的长度仅增加 1，所以如果要发现长度为 L 的序列模式，Apriori-like 算法必须扫描数据库至少 L 次。3） 当要挖掘出的序列模式较长时的算法瓶颈一个长的序列模式是由短的序列模式组合而成的，但是这样的候选序列的数量的增长与要被挖掘序列模式的长度的增长是成指数关系的。例如：假设在一个序列数据库中仅有一条序列：，其长度为 100，在这个数据库中最小支持度阈值为1（即每一个出现的序列模式都是频繁的） 。为了得到这个长度为 100 的序列模式，Apriori-like 算法必须产生 100 个长度为 1 的候选序列， 100100+10099/2=14，950个长度为 2 的候选序列， 3100=161，700 个长度为 3 的候选序列，。总之，传统的序列模式挖掘算法，当从序列数据库中挖掘长模式或支持度较低时，存在所挖出的频繁子序列个数会随模式长度增加而爆炸性增长，以及将会遇到较高的计算复杂度等等很多问题。这样便限制了这些算法的应用，因为很多有用的长模式不能被有效地挖掘出来，而在很多实际应用中，如进行 DNA 序列分析和股票序列分析等，经常会碰到含有大量长模式的序列数据库。因此，很有必要发现更有效的方法来解决4这些问题。52. 序列模式挖掘算法2.1 序列模式挖掘基础知识2.1.1 相关定义设 I = i1,i2,in是一个项目集合，项目集或者项集（items）就是各种项目组成的集合，即 I 的所有子集。一个序列就是若干项集的有序列表，一个序列 S 可表示为,其中 sj 为项集，也称作 S 的元素。元素由不同的项组成，可表示为（x 1,x2,xn） 。当元素只包含一项时，一般省去括号，如（x 2）一般表示为 x2，元素之间是有顺序的，但元素内的项是无序的，一般定义为词典序。序列包含项的个数称为序列的长度，长度为 L 的序列记为 L-序列。序列数据库就是元组（tuples）的集合，其中 s 是序列，sid 是该序列的序列号，元组的个数称为序列数据库的大小，记作：SDB。定义 1（子序列，超序列）：序列 T是另一个序列 S的子序列，需要满足下面条件：存在 1j 1j 2j mn 且 t1 sj1,t2 sj2,tm sjm。称序列 T 是序列 S 的子序列，序列 S 是序列 T 的超序列，记作 T S。例如序列是序列的子序列，是的超序列。定义 2（支持度）： 序列数据库 D 是元组的集合，sid 为序列标识号，如果序列 T 是 S 的子序列（即 T S）称元组包含序列 T；则序列 T 在序列数据库 D 中的支持度是数据库中包含 T 的元组数，即 support(T)| DTS |，记作 support（T） 。例如在表 1 中 supprot(a)=4。定义 3（频繁序列模式）：给定一个最小支持度阈值 minsupport，如果序列 s 的支持度不小于 minsupport，则称序列 s 为频繁序列模式，所有的频繁序列模式集合记作FS。例如在表 1 中序列就是一个频繁序列模式。长度为 L 的序列模式称为 L-模式。定义 4（前缀）：假定每个元素中的项目是按照词典序排列的,给定序列 = ,= (mn),如果 ei/=ei（im-1）,e m/ em,并且（e m -em/）中的项目均需在 em/中项目的后面，则称 是 的前缀。例如序列是序列的前缀。6定义 5（最大子序列）：给定序列 和 ,如果 是 的子序列,则 关于 的投影 /需要满足 是 /的前缀， /是 的满足上述条件的最大子序列。定义 6（后缀）：序列 关于子序列 =的