面向数据流的频繁模式挖掘算法研究

论文摘要

随着信息时代的发展,数据挖掘成了当前重要的研究方向,通过近十年的努力,数据挖掘技术已经相当成熟。然而,近几年来出现了一种新的数据模型,即数据流,这种数据模型广泛存在于现实生活中,如网站服务器的日志文件、股票交易、网络传感器、天气和环境监测等都产生大量的数据流。在数据流环境中进行挖掘是一项具有挑战性的工作,传统的数据挖掘技术只能处理静态数据,对这种大量的、快速的数据流却无能为力。频繁模式挖掘是数据挖掘中一项非常重要的任务,最近几年,在数据流频繁模式挖掘领域已经产生了大量的研究成果。然而这些研究都需要大量的存储空间,挖掘效率也不够高,尤其是无法对新到来的数据进行实时更新。针对这些问题,本文提出了一种新的数据流频繁模式挖掘方案,包含相应的数据过滤、编码方法、新的概要数据结构和挖掘算法,并实现了面向数据流的频繁模式挖掘系统。首先,提出基于Hash结构的数据过滤和编码方法。针对数据流快速、无限的特征,通过滑动窗口来对数据流进行缓冲,从而限制每次处理的数据量。通过Hash表对基本窗口中的数据进行过滤和重编码,进一步减小挖掘的数据量,而且简化数据类型,得到项目之间的规范顺序。这些有助于构造和更新前缀树结构。其次,提出了一种新的概要数据结构NCH-Tree。在NCH-Tree结构中引入B+树的思想,把所有事务的时间信息存放在一个链表中,方便进行更新。再次,在数据过滤、编码和概要数据结构NCH-Tree的基础上,进一步提出数据流频繁模式挖掘算法,很好地满足了数据流频繁模式挖掘的需求。最后,设计并实现了面向数据流的频繁模式挖掘系统。在该系统中,设计了一种概要数据结构来存储频繁模式集,通过此结构,挖掘算法可以和用户进行交互,根据用户的不同需求返回不同的结果。通过实验可以发现,本文所提出的面向数据流的频繁模式挖掘算法能很快对新到来的数据进行更新并保证较高的挖掘准确性,同时,此算法的挖掘效率高于同类算法。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第1章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 本文的研究内容
• 1.4 本文结构
• 第2章 数据流和频繁模式挖掘
• 2.1 数据流
• 2.1.1 数据流模型
• 2.1.2 数据流模型的特点
• 2.2 数据流管理系统
• 2.3 数据流处理
• 2.3.1 数据流处理模型
• 2.3.2 数据流处理技术
• 2.4 频繁模式挖掘算法分析
• 2.4.1 Apriori算法
• 2.4.2 FP-growth算法
• 2.4.3 FP-growth算法的发展和改进
• 2.4.4 部分枚举算法
• 2.4.5 挖掘结果处理
• 2.5 数据流频繁模式挖掘
• 2.6 本章小结
• 第3章 面向数据流的频繁模式挖掘算法研究
• 3.1 挖掘算法分析
• 3.1.1 启发式频繁模式挖掘算法
• 3.1.2 批处理式频繁模式挖掘算法
• 3.2 基于Hash表的滑动窗口预处理
• 3.2.1 滑动窗口技术
• 3.2.2 数据过滤和重编码
• 3.3 NCH-Tree及算法
• 3.3.1 NCH-Tree的结构
• 3.3.2 NCH-Tree的构造和更新
• 3.4 基于NCH-Tree的频繁模式挖掘
• 3.5 基于NC-PB的用户查询模块
• 3.5.1 输出缓存（NC-PB）
• 3.5.2 基于NC-PB的限制性模式查询
• 3.6 本章小结
• 第4章 实验分析
• 4.1 过滤和重编码性能分析
• 4.1.1 实验结果
• 4.1.2 实验分析
• 4.2 挖掘和更新性能分析
• 4.2.1 实验结果
• 4.2.2 实验分析
• 4.3 本章小结
• 第5章 NCH-DSFM系统的设计和实现
• 5.1 滑动窗口预处理模块设计
• 5.1.1 设计内容
• 5.1.2 设计目的
• 5.1.3 实现方法
• 5.2 基于NCH-Tree的挖掘模块设计
• 5.2.1 设计内容
• 5.2.2 设计目的
• 5.2.3 实现方法
• 5.3 基于NC-PB的查询模块的设计
• 5.3.1 设计内容
• 5.3.2 设计目的
• 5.3.3 实现方法
• 5.4 本章小结
• 第6章 总结和展望
• 参考文献
• 致谢
• 攻读硕士期间参加的项目和发表的论文