数据流频繁模式挖掘关键算法及其仿真应用研究

论文摘要

系统仿真技术综合集成了计算机技术、网络技术、图形图像处理技术、信息处理技术、自动控制技术等多个领域的知识,是系统分析和研究的重要手段。数据挖掘技术是获取仿真数据中隐藏知识的有力工具。随着仿真系统复杂程度的提高和规模的增大,仿真时间越来越长、仿真所产生的数据量越来越大。这使得仿真数据具有数据流的特征。因此有必要采用数据流挖掘技术处理仿真数据。数据流是一种连续、高速、无限、时变的有序数据序列。数据流的特征对数据流的挖掘提出了严峻的挑战。传统面向静态数据集的算法无法直接用于挖掘数据流,而现有数据流挖掘算法存在时空效率不高的缺陷。因此,针对仿真中常用的数据挖掘任务,研究时空效率高效的相应数据流挖掘算法具有重要意义。关联规则挖掘是仿真中最常用的一类数据挖掘任务,而频繁模式挖掘是生成关联规则的关键步骤。为此,论文研究了数据流中频繁模式挖掘的关键算法,重点研究了数据流中最大频繁项集、频繁闭项集和Top-K最频繁项集的挖掘算法,以及基于频繁闭项集的数据流分类算法和基于Top-K频繁模式的高维数据流聚类算法。论文最后研究了如何将数据流挖掘算法快速集成到不同的仿真系统中,着重考虑了数据流挖掘算法资源在仿真中的重用。论文的主要研究工作及创新包括以下六个方面:（1）提出了一种数据流最大频繁项集挖掘算法。相对于完全频繁项集和频繁闭项集,最大频繁项集的数目最少,挖掘最大频繁项集的算法具有较高的时空效率。为此,论文研究了数据流中最大频繁项集的挖掘技术,旨在提供一种能够在任意时刻都快速维护数据流滑动窗口中最大频繁项集的算法。主要研究内容包括三个方面。首先提出了一种面向数据流的最大频繁项集剪枝技术,即子集等价剪枝技术。接着,提出了一种最大频繁项集单遍挖掘算法FPMFI-DS。其中,FPMFI-DS算法中应用了子集等价剪枝技术以降低算法的搜索空间大小,从而提高算法效率。最后,基于FPMFI-DS算法,提出了一种能够在线更新挖掘数据流滑动窗口中最大频繁项集的算法FPMFI-DS+。实验表明,对于稠密数据集子集等价剪枝技术能够缩小约40%的搜索空间;FPMFI-DS算法的挖掘速度快并具有良好的可扩展性;FPMFI-DS+算法更新挖掘速度快并具有良好的稳定性。（2）提出了一种数据流频繁闭项集挖掘算法。频繁闭项集的数目介于完全频繁项集和最大频繁项集之间,并保存了所有项集的支持度信息。因此挖掘数据流中的频繁闭项集既具有较高的时空效率,又保证了信息的完全性。为此,论文提出了一种频繁闭项集挖掘算法FPCFI-DS。该算法能够在有限的存储空间中高速挖掘数据流滑动窗口中的频繁闭项集,并且能够在任意时刻都维护数据流当前窗口中的频繁闭项集。实验表明,FPCFI-DS算法的时空效率显著优于同类经典算法Moment。（3）提出了一种数据流Top-K最频繁项集挖掘算法。Top-K最频繁项集挖掘的优点是不需要用户指定最小支持度阈值,仅指定需要寻找的项集数目k。已有Top-K最频繁项集挖掘算法存在初始项目数目过多、初始边界支持度过高的问题。为此,论文首先提出了一种基于混合搜索方式的高效Top-K最频繁项集挖掘算法MTKFP。该算法综合利用宽度优先搜索和深度优先搜索挖掘Top-K最频繁项集。然后基于MTKFP算法,提出了一种基于Chernoff不等式的数据流Top-K最频繁项集挖掘算法MTKFP-DS。实验表明,MTKFP算法所获得的初始项目数目至少低于已有算法70%,初始边界支持度高于已有算法,从而MTKFP算法的性能优于已有最好算法1倍以上;MTKFP-DS算法适合于对数据流数据的挖掘。（4）提出了一种基于频繁闭项集的数据流分类算法。相对于某些传统分类算法,基于关联规则的分类具有更高的精度。此类算法通常采用频繁项集作为生成类关联规则的依据。但挖掘频繁项集易遭受组合爆炸问题,从而影响算法效率;另外,数据流的出现也对分类算法提出了新的挑战。为此,论文提出了一种高效的基于频繁闭项集的数据流分类算法CBC-DS。在该算法中,设计了高效的频繁闭项集单遍挖掘算法和有效的分类器构建方法。实验表明,CBC-DS算法的平均分类精度比经典算法CMAR高1.09%左右,分类速度快于CMAR算法。（5）提出了基于Top-K频繁模式的高维数据流聚类算法。高维数据聚类是聚类问题中的研究难点。基于密度和基于网格的综合方法能够较好地解决该问题,该方法的关键在于发现高密单元格。传统方法采用挖掘频繁项集的方式发现高密单元格,该方式的不足是需要用户指定最小密度阈值,而且不利于发掘稀疏子空间中的高密单元格。为此,论文分别提出了基于Top-K最频繁项集、基于N-most interesting项集和基于Top-K项目的高维数据流聚类算法。这些算法不需要用户指定最小密度阈值。第二种算法有利于特定维的子空间分组的高密单元格发掘,第三种算法有利于特定子空间的高密单元格的发掘,从而解决稀疏子空间中高密单元格的发掘。实验表明,所提出的算法适用于对高维数据流的聚类。（6）研究了数据流挖掘技术在仿真中的应用。论文提出了基于数据流挖掘技术的仿真应用框架。并且为了能够将数据流挖掘算法快速集成到基于HLA体系结构的仿真系统中,采用模块化开发思想设计了通用性强的数据流挖掘构件和通用数据流挖掘成员,以提高算法资源的重用性。并以“导弹突防仿真系统”为例,介绍了通用关联规则挖掘成员的设计思想。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景
• 1.1.1 数据流技术的兴起
• 1.1.2 仿真对数据流技术的需求
• 1.1.3 数据流频繁模式挖掘
• 1.1.4 数据流频繁模式挖掘面临的挑战
• 1.2 课题研究内容
• 1.2.1 课题来源
• 1.2.2 课题研究重点
• 1.2.3 课题研究难点
• 1.3 论文的主要工作和创新
• 1.4 论文的组织结构
• 第二章 频繁模式挖掘的相关研究
• 2.1 数据流频繁模式挖掘算法的研究现状
• 2.1.1 根据挖掘内容分类
• 2.1.2 根据窗口模型分类
• 2.1.3 根据是否近似算法分类
• 2.1.4 设计立方体
• 2.1.5 基于频繁模式的其它数据流算法
• 2.2 基于树搜索方式的频繁模式挖掘
• 2.2.1 搜索空间树
• 2.2.2 搜索方式
• 2.2.3 剪枝技术
• 2.3 项集频率计数的主要数据结构
• 2.3.1 位图
• 2.3.2 前缀树
• 2.3.3 出现传递列表
• 2.4 小结
• 第三章 挖掘数据流中的最大频繁项集
• 3.1 引言
• 3.2 相关知识
• 3.2.1 最大频繁项集挖掘基础
• 3.2.2 相关研究
• 3.3 子集等价剪枝技术
• 3.3.1 已有剪枝技术综述
• 3.3.2 子集等价剪枝技术的描述
• 3.3.3 子集等价剪枝技术的优化和实现
• 3.4 最大频繁项集单遍挖掘算法FPMFI-DS
• 3.4.1 文法顺序FP-Tree
• 3.4.2 项顺序策略和剪枝技术
• 3.4.3 FPMFI-DS 算法的伪代码
• 3.5 最大频繁项集在线更新挖掘算法FPMFI-DS+
• 3.5.1 添加事务
• 3.5.2 删除事务
• 3.6 实验评测
• 3.6.1 子集等价剪枝的性能
• 3.6.2 FPMFI-DS 算法的性能
• 3.6.3 FPMFI-DS+算法的性能
• 3.7 小结
• 第四章 挖掘数据流中的频繁闭项集
• 4.1 引言
• 4.2 相关研究
• 4.3 FPCFI-DS 算法
• 4.3.1 主要数据结构
• 4.3.2 构建GCT
• 4.3.3 删除过期事务
• 4.3.4 添加新事务
• 4.4 实验评测
• 4.4.1 性能比较
• 4.4.2 性能分析
• 4.5 小结
• 第五章 挖掘数据流中的Top-K 最频繁项集
• 5.1 Top-K 模式的类型
• 5.2 基于混合搜索的Top-K 最频繁项集挖掘
• 5.2.1 问题的提出
• 5.2.2 相关研究
• 5.2.3 基本思想
• 5.2.4 算法描述
• 5.2.5 实验评测
• 5.3 挖掘数据流中的Top-K 最频繁项集
• 5.3.1 问题的提出
• 5.3.2 相关研究
• 5.3.3 MTKFP-DS 算法
• 5.3.4 实验评测
• 5.4 小结
• 第六章 基于频繁模式的数据流分类和聚类
• 6.1 基于频繁闭项集的数据流分类
• 6.1.1 问题的提出
• 6.1.2 相关知识
• 6.1.3 CBC-DS 算法
• 6.1.4 实验评测
• 6.2 基于Top-K 频繁模式的高维数据流聚类
• 6.2.1 问题的提出
• 6.2.2 基本概念
• 6.2.3 高维数据的映射
• 6.2.4 高密单元格的挖掘
• 6.2.5 高密单元格的聚类
• 6.2.6 实验评测
• 6.3 小结
• 第七章 数据流挖掘技术在仿真中的应用
• 7.1 引言
• 7.2 基于数据挖掘的仿真执行周期
• 7.2.1 基于传统数据挖掘技术的仿真执行周期
• 7.2.2 基于数据流挖掘技术的仿真执行周期
• 7.3 基于数据流挖掘的仿真应用框架
• 7.4 数据流挖掘算法的重用
• 7.4.1 数据流挖掘算法资源库
• 7.4.2 数据流挖掘构件
• 7.4.3 通用数据流挖掘成员
• 7.5 应用举例
• 7.5.1 系统描述
• 7.5.2 数据获取
• 7.5.3 数据预处理
• 7.5.4 关联规则挖掘
• 7.6 小结
• 第八章 结束语
• 8.1 工作总结
• 8.2 工作展望
• 致谢
• 攻读博士学位期间发表的论文
• 攻读博士学位期间参加的主要科研工作
• 参考文献