间隔事件流上的频繁情节挖掘方法研究

摘要

随着信息时代的到来，人们需要分析处理越来越多的数据，而这些海量数据的背后隐藏着大量的人们所需要的规则和知识，数据挖掘就是随着人们的这一需要应运而生的。虽然最近几十年对数据挖掘技术的研究已经很成熟，但随着RFID、Sensor等EDGE(Electronic Data Gathering Equipment)设备的广泛应用，出现了大量的事件流数据。传统的数据挖掘技术往往针对静态数据进行处理，对这种事件流数据不适用。
　　频繁情节挖掘是事件流挖掘领域中的重要方面。目前对频繁情节挖掘的研究主要针对静态数据和点事件类型的数据，但是在真实情况下，对事件流的处理往往比静态数据更有意义，而且事件的发生很多是带有时间间隔的，不可能完全按照点事件类型进行处理。本文针对这些问题，提出了在具有时间间隔的事件流上进行频繁情节挖掘的算法，可以有效地把事件流和时间间隔事件结合起来解决。
　　首先，对于时间间隔事件，提出了基于关系元组的表示方法，它可以有效的区分出滑动窗口内所有的频繁情节，避免了传统的对有时间间隔事件处理时，丢失情节的情况。但是基于关系元组的表示方法还存在一些问题，所以在此基础上本文又提出了基于矩阵的表达方法，它可以使用户清楚的了解所挖掘出的频繁情节的内部关系。
　　其次，因为我们日常生活中接触的事件类型往往是有间隔的，即事件需要持续一段时间后才结束，而现阶段的挖掘方法都不能处理这种间隔事件。所以本文提出了一种关系线索树和B+树相结合的方法，它可以对事件流中的间隔事件进行频繁情节挖掘，可以构建并有效地存储事件流中滑动窗口内的所有情节，也避免了对源数据的多次扫描。
　　最后，本文在此基础上提出了一种基于线性链表的深度优先算法，它采用深度优先构建线性链表的方法，针对最小发生情节，采用一种最小误差系数的修剪方法对滑动窗口内的情节进行修剪，在一定程度上减少了时间和空间代价的消耗。
　　通过实验可以发现，本文所提出的针对具有时间间隔的事件流上的频繁情节挖掘算法可以很快地对新到来的事件进行处理，并挖掘出滑动窗口内的所有频繁情节。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 研究现状

1．3 本文的研究内容

1．4 本文结构

第2章 事件流和频繁情节挖掘

2．1 事件流

2．1．1 事件流特点

2．1．2 基于时间间隔的事件流

2．2 间隔事件的表达方式

2．2．1 传统的间隔事件关系的表达方法

2．2．2 基于五元组的间隔事件关系表达方法

2．3 频繁情节挖掘

2．3．1 Winepi算法

2．3．2 Minepi算法

2．3．3 Minepi算法的改进

2．3．4 基于自动机的方法

2．4 本章小结

第3章 间隔事件关系的表达方法研究

3．1 现有的表达方法分析

3．2 基于七元组的层次表达方法

3．3 基于矩阵的表达方法

3．4 本章小结

第4章 间隔事件流上的频繁情节挖掘算法研究

4．1 现阶段频繁情节挖掘算法分析

4．2 两种基于前缀树的结构

4．3 基于RT-T的间隔事件流关系存储算法

4．3．1 RT-T结构

4．3．2 RT-Tree的构建和更新

4．4 基于缓存区结构的间隔事件流频繁情节挖掘算法

4．4．1 顺序链表缓存结构

4．4．2 B+树索引缓存区结构

4．4．3 B+树索引缓存区结构的构建和更新

4．5 线性链表深度优先算法

4．5．1 LLDF的结构

4．5．2 LLDF的构建和更新

4．6 最小误差系数方法分析

4．7 本章小结

第5章 实验结果与分析

5．1 时间代价比较

5．1．1 实验结果

5．1．2 实验分析

5．2 空间代价比较

5．2．1 实验结果

5．2．2 实验分析

5．3 准确性分析

5．3．1 实验结果

5．3．2 实验分析

5．4 本章小结

第6章 总结和展望

参考文献

致谢

攻读硕士期间参加的项目和发表的论文