论文部分内容阅读
在过去的十几年间，研究人员对序列模式挖掘进行了深入广泛的研究，并取得了一系列的研究成果。这些研究成果已经被广泛的应用到社会生产生活的各个领域中。序列模式挖掘已经成为数据挖掘领域中一个重要的研究方向。 近年来在高速网络、事务日志、金融和传感器网络等领域出现了一种称为数据流的新的数据类型。它具有与普通数据集截然不同的特性，如:持续不断产生数据、数据产生速度快、数据量庞大以致只能顺序访问一遍数据、数据产生的次序无法控制等。随着数据流应用的不断增多，目前数据流环境中的数据挖掘已经成为了研究的热点。但因为现存的绝大多数序列模式挖掘算法都是基于传统的数据挖掘方法，数据集的静态性、算法的多遍扫描性以及挖掘结果的非实时性，从而使得它们无法被直接应用到数据流环境中。 由于序列组合数目的爆炸性，使得在数据流环境中进行序列模式挖掘的研究变得更加困难，因此目前绝大多数的研究工作都集中在了数据流环境中的频繁模式挖掘上，而对数据流环境中的序列模式挖掘的研究还很少。 考虑到序列模式挖掘在数据流应用中的重要性，本文对数据流环境中序列模式挖掘方法进行了初步的研究，并且给出了三种不同挖掘问题（全局频繁序列、近似序列模式和当前频繁序列）的解决方法。本文的主要研究内容和创新成果如下: 1.给出了数据流环境中基于计数估计模型的频繁序列挖掘方法。 为实现算法的一遍扫描，我们根据序列支持度计数的大小将其划分为非频繁序列、近似频繁序列和频繁序列三种。对于数据流中每一个新出现的序列，我们都利用序列计数估计模型对序列的支持度计数进行估计，如果序列的最大计数估计值大于给定的近似频繁序列的支持度阈值，则我们将其保留在序列监控树中，否则我们将其抛弃掉。对于序列监控树的维护，我们采用了定期或者限制大小进行裁减的方法。 2.给出了数据流环境中基于分类的近似序列模式挖掘方法。 首先通过序列（加权序列）之间的编辑距离来对序列进行分类，利用序列的多队列排列对挖掘结果进行压缩合并，并将其保存到一个近似序列模式树中。算法在近似序列模式树的基础上回答任何时刻提出的近似序列模式查询请求。为满足用户对于历史数据查询的要求，算法采用了倾斜窗口来对历史数据进行存储和维护。 3.给出了数据流环境中基于滑动窗口的当前频繁序列模式挖掘方法。 提出了一种有效的挖掘当前窗口中频繁序列的算法，算法采用滑动窗口技术来满足用户对当前频繁序列的查询请求。给出了ε-近似序列集的定义，通过ε-近似序列集使得算法能够对数据流只进行一遍扫描就可以得到可控误差范围内的挖掘结果。利用一种压缩的数据结构GSP-tree来存储和维护整个滑动窗口中各分区的近似序列集，并通过合并各分区的近似序列集的来响应用户当前的查询请求。 实验对比和性能分析结果表明，本文所提出的基于计数估计模型的频繁序列挖掘方法、基于分类的近似序列模式挖掘方法以及基于滑动窗口的当前频繁序列模式挖掘方法在进行数据流环境中的三种不同序列模式挖掘问题上具有很好的性能。