论文部分内容阅读
系统仿真技术综合集成了计算机技术、网络技术、图形图像处理技术、信息处理技术、自动控制技术等多个领域的知识,是系统分析和研究的重要手段。数据挖掘技术是获取仿真数据中隐藏知识的有力工具。随着仿真系统复杂程度的提高和规模的增大,仿真时间越来越长、仿真所产生的数据量越来越大。这使得仿真数据具有数据流的特征。因此有必要采用数据流挖掘技术处理仿真数据。数据流是一种连续、高速、无限、时变的有序数据序列。数据流的特征对数据流的挖掘提出了严峻的挑战。传统面向静态数据集的算法无法直接用于挖掘数据流,而现有数据流挖掘算法存在时空效率不高的缺陷。因此,针对仿真中常用的数据挖掘任务,研究时空效率高效的相应数据流挖掘算法具有重要意义。关联规则挖掘是仿真中最常用的一类数据挖掘任务,而频繁模式挖掘是生成关联规则的关键步骤。为此,论文研究了数据流中频繁模式挖掘的关键算法,重点研究了数据流中最大频繁项集、频繁闭项集和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体系结构的仿真系统中,采用模块化开发思想设计了通用性强的数据流挖掘构件和通用数据流挖掘成员,以提高算法资源的重用性。并以“导弹突防仿真系统”为例,介绍了通用关联规则挖掘成员的设计思想。