基于半结构化数据的数据流挖掘算法研究

论文摘要

数据流作为一种重要的数据类型,广泛应用于网络流量监控、用户点击流分析、传感器网络数据处理等领域。与传统的数据类型相比,数据流具有高速性、连续性、实时性等特点。高速性和连续性要求数据流挖掘算法必须具有较高的时空效率。实时性要求挖掘结果应尽可能反映最新的变化趋势,并尽量消除历史数据对结果的影响。同时,半结构化数据在语义网络、化学化合物分析、社会结构信息挖掘等领域有着广泛应用。基于半结构化数据的挖掘,可以有效发现关联信息,还可以作为其他半结构化数据挖掘任务的基础而发挥重要的作用。然而,半结构化数据不仅含有数据内容信息,而且含有数据之间的关系信息,使用传统的挖掘算法对其进行挖掘的难度较大。半结构化数据广泛存在于数据流中,由于数据流和半结构化数据挖掘各自的复杂性,到目前为止,在数据流中高效挖掘半结构化数据的算法很少。本文针对这两方面的研究难点,首次基于一种重要的半结构化数据——树型数据,提出了其在数据流中频繁子树集的挖掘算法,解决了数据流挖掘的低效率问题,有较高的创新意义。本文的研究和创新工作可以分为如下四个方面：1.提出了针对数据流挖掘实时性特点的衰减策略实时性是数据流挖掘的基本要求,本文提出一种针对实时性特点的支持度衰减策略。该策略包括衰减机制和补偿放大机制,对历史数据支持度进行衰减,以削弱历史数据对挖掘结果的影响；同时放大新到达数据的支持度,以减少因为衰减造成的支持度信息损失,并加强新数据对结果的影响。在此基础上,进一步研究衰减和补偿放大之间的关系,进行相关的参数约束和理论分析,确保了频繁模式不会因为衰减机制而影响输出。最后,对衰减策略在真实数据流中进行验证,证明了其对数据流挖掘实时性的较大增益。2.提出了针对数据流挖掘高效性要求的批量挖掘模型数据流到达呈批量的特点,传统的逐条加入、整体挖掘方式不能适应数据流这种自然特性,因而造成很大的系统开销,不能满足数据流挖掘的高效性需求。本文提出了一种批量挖掘的方式,在数据流到达时对数据进行批量预处理,然后把处理结果作为中间结果,通过集合之间的运算批量添加到现有结果中。这样的方式加快了处理效率,符合数据流的特性；而且,将预处理结果代替原始数据加入当前结果,使运算量呈指数级减少。经理论分析和实验证明,采用批量挖掘模型的挖掘方法大大提高了数据流挖掘的效率。同时,该模型有较高的适应性和扩展性,可以方便地应用于多种数据流挖掘任务中。3.提出了基于连接的静态树型结构挖掘算法CFTMiner传统的静态树型结构数据的挖掘方法采用基于路径扩展的子树候选集生长方式,如果数据中含有较多的重复结构,算法效率很低。本文提出的CFTMiner算法以经典的DryadeParent算法为基础,采用基于连接的子树候选集生长方式,提高了重复数据的复用度；并针对DryadeParent中存在的初始化信息缺失问题,提出一种新的候选集初始化方法,消除了初始化时的信息丢失,同时避免在后续挖掘中额外的数据集扫描,减轻了系统负担,在一定程度上提高了算法的挖掘效率。实验证明,CFTMiner算法具有较高的时空效率。4.提出了数据流中树型数据的高效挖掘算法SFCLTreeMiner半结构化数据和数据流的挖掘两者都是当前研究的难点,目前,在数据流中进行半结构化数据挖掘的算法很少。本文结合前面提到的三个方面研究成果,提出一种在数据流中树型结构数据挖掘算法SFCLTreeMiner。该算法使用批量挖掘模型、结合时间衰减策略对快速到达的数据流进行处理；提出了一种针对树型数据的集合添加和删除的批量更新算法；针对挖掘过程中可能存在的误差进行了分析,并对正确性进行了证明。实验证明,SFCLTreeMiner使用衰减策略有效地保证了实时性,并通过批量挖掘和预处理方式,大大提高了数据流挖掘效率,同时具有较高的挖掘准确度。

论文目录

• 摘要
• ABSTRACT
• 图索引
• 表索引
• 第一章 绪论
• 1.1 研究背景和意义
• 1.1.1 研究背景
• 1.1.2 课题研究意义
• 1.2 研究现状
• 1.2.1 数据流管理系统研究现状
• 1.2.2 数据流挖掘研究现状
• 1.2.2.1 数据流预测查询算法
• 1.2.2.2 数据流频繁模式挖掘算法
• 1.2.2.3 数据流分类算法
• 1.2.2.4 数据流聚类算法
• 1.2.3 数据流半结构化数据挖掘研究
• 1.3 论文主要研究内容
• 1.4 论文结构安排
• 参考文献
• 第二章 频繁模式挖掘及算法
• 2.1 问题定义
• 2.1.1 基本概念
• 2.1.2 事务数据集的表示
• 2.2 频繁模式挖掘算法
• 2.2.1 先验原理
• 2.2.2 Apriori算法
• 2.2.3 FP-growth算法
• 2.2.4 频繁模式简约形式挖掘
• 2.3 本章小结
• 参考文献
• 第三章 半结构化数据的频繁模式挖掘研究
• 3.1 引言
• 3.2 半结构化数据和相关研究
• 3.2.1 图型结构数据挖掘
• 3.2.1.1 图集中的频繁子图挖掘算法
• 3.2.1.2 单图中的频繁子图挖掘算法
• 3.2.2 序列结构数据挖掘
• 3.2.3 树型结构数据挖掘
• 3.3 树型结构数据基本概念
• 3.3.1 树型数据
• 3.3.2 子树的频繁模式
• 3.4 基于连接的频繁闭子树挖掘算法
• 3.4.1 DryadeParent算法思路
• 3.4.2 改进算法CFTMiner
• 3.4.2.1 存在的问题
• 3.4.2.2 改进后的算法
• 3.4.2.3 正确性分析
• 3.4.3 实验分析
• 3.5 本章小结
• 参考文献
• 第四章 数据流挖掘的支持度衰减策略
• 4.1 引言
• 4.2 相关研究
• 4.3 问题描述
• 4.3.1 时间模型
• 4.3.2 数据流的定义
• 4.3.3 滑动窗口模型
• 4.4 衰减机制
• 4.4.1 衰减模型
• 4.4.2 补偿放大模型
• 4.4.3 衰减与补偿放大的关系约束
• 4.5 实验分析
• 4.5.1 实验环境
• 4.5.2 实时性比较
• 4.6 本章小结
• 参考文献
• 第五章 基于批量更新模式的数据流挖掘研究
• 5.1 引言
• 5.2 相关研究
• 5.3 批量更新模式
• 5.4 基于批量更新模式的频繁闭子树挖掘算法
• 5.4.1 挖掘模型
• 5.4.2 数据流批量预处理
• 5.4.3 闭子树集的添加和删除
• 5.4.4 结果集更新
• 5.4.5 正确性分析
• 5.5 算法误差分析
• 5.5.1 衰减误差
• 5.5.2 近似误差
• 5.5.3 累积误差
• 5.5.4 误差分析小结
• 5.6 实验分析
• 5.6.1 实验环境
• 5.6.2 NASA数据集性能对比
• 5.6.2.1 支持度阈值为50%的评测
• 5.6.2.2 支持度阈值为25%的评测
• 5.6.3 CSLOGS数据集性能对比
• 5.6.4 精确性评测
• 5.7 本章小结
• 参考文献
• 第六章 结束语
• 6.1 研究工作总结
• 6.2 未来工作展望
• 致谢
• 攻读博士学位期间发表的学术论文