事件序列上频繁情节发现的研究

论文摘要

情节是指事件序列上相互邻近并且满足一定结构关系的事件类型的集合,情节规则的发现在企业内部网络警报的集中安全管理、电信警报的分析等领域有着重要的应用。本文介绍了情节的基本概念和频繁情节发现的基本方法。对于情节发现中最小发生的寻找,本文提出一个定理,由长度为l 的串行情节最小发生的集合找到长度为l+1 的串行情节最小发生的集合。因为情节和序列模式有着很多的相似之处,本文将一种高效的序列模式挖掘算法PrefixSpan 应用到串行情节的发现上。为此,首先本文提出了一个采用伪投影方法将事件序列变为序列数据库的算法。使用这个方法,本文在PrefixSpan 的基础上给出了修改的算法,用于串行情节的发现。实验表明改进的算法比传统的算法在性能上有很大提高。由于传统的情节并不能表达事件之间的时间间隔,本文在情节中引入了时间间隔的概念,提出了带时间间隔的串-并行情节,它同时考虑了并行情节表达的同时性和串行情节表达的顺序性。本文在挖掘带时间间隔序列模式算法I-PrefixSpan 的基础上给出了修改算法,用来发现带时间间隔的串-并行情节。

论文目录

• 第1章 绪论
• 1.1 问题的提出背景
• 1.2 情节研究的现状
• 1.3 本文的主要工作
• 第2章 情节
• 2.1 情节
• 2.1.1 事件序列
• 2.1.2 情节和频繁情节
• 2.2 情节和序列模式
• 第3章 频繁情节发现的基本算法
• 3.1 WINEPI 算法
• 3.1.1 规则的生成
• 3.1.2 寻找频繁情节
• 3.1.3 生成候选情节
• 3.1.4 情节的识别
• 3.2 MINEPI 算法
• 3.2.1 情节的最小发生
• 3.2.2 Minepi 算法概要
• 3.2.3 串行情节最小发生发现的一个定理
• 第4章 改进的PREFIXSPAN 算法在情节发现上的应用
• 4.1 PREFIXSPAN 算法
• 4.1.1 基本定义
• 4.1.2 算法和示例
• 4.1.3 伪投影
• PREFIXSPAN 算法用于串行情节的发现'>4.2 EPI_PREFIXSPAN 算法用于串行情节的发现
• 4.3 算法实验结果分析
• 第5章 带有时间间隔的情节发现
• 5.1 带有时间间隔的序列模式挖掘
• 5.1.1 时间间隔序列模式简介
• 5.1.2 问题的定义
• 5.1.3 挖掘算法
• 5.2 带有时间间隔的情节发现
• 5.2.1 带有时间间隔的情节
• 5.2.2 带时间间隔的串-并行情节的发现方法
• 5.2.3 算法的实验结果
• 第6章 总结与展望
• 6.1 总结
• 6.2 未来工作
• 参考文献
• 摘要
• ABSTRACT
• 致谢
• 导师及作者介绍