论文部分内容阅读
各种操作系统、应用程序、设备等产生的日志数据蕴藏着丰富的信息,对日志数据的挖掘和分析不仅能够帮助管理人员提前发现、避开潜在的隐患,找到安全事件的根本原因,还能够挖掘出日志数据背后潜在的更多的信息。随着日志数据的重视程度越来越高,如何有效的挖掘和分析日志数据已成为当前的研究热点。日志数据具有时间序列的性质,使用时间序列数据挖掘技术能够对其进行更有效的挖掘和分析。序列模式挖掘作为时间序列数据挖掘技术的重要研究内容之一,能够挖掘日志数据中频繁出现的序列模式,这些频繁出现的序列模式往往反映了日志记录的事件之间的相互关系,具有重要的研究意义和价值。本文对序列模式挖掘的两个应用广泛的GSP算法和PrefixSpan算法进行了改进,主要的研究工作如下:(1)针对GSP算法需要遍历整个序列集、需要多次遍历k频繁序列以及遍历k频繁序列速度慢的缺陷,提出了一种基于序列集优化及索引前缀树的GSP改进算法。该算法基于本文所提的序列集优化方法以及本文设计的索引前缀树数据结构,有效减少了算法的运行时间。对比实验结果表明,基于序列集优化及索引前缀树的GSP改进算法的运行时间明显低于未改进的GSP算法,但会花费了更多的空间代价。(2)针对PrefixSpan算法占据了大量内存的缺陷,提出了一种基于后缀索引的PrefixSpan改进算法。对比实验结果表明,基于后缀索引的PrefixSpan改进算法在运行时的内存使用情况明显低于未改进的PrefixSpan算法,并且其运行时间与未改进的PrefixSpan算法的运行时间相接近。(3)为了验证PrefixSpan算法记录的后缀中含有非频繁项对算法的时间性能是否会产生影响,提出了一种基于投影数据库优化的PrefixSpan算法。对比实验结果表明,后缀中含有非频繁项不会降低PrefixSpan算法的时间性能,删除后缀中非频繁项的操作反而会花费大量时间。本研究同时证明了基于后缀索引的PrefixSpan算法不会因为使用了后缀索引导致其时间性能的降低。(4)对改进前后的GSP算法和改进前后的PrefixSpan算法进行了对比,深入论述的两类算法的特点,并说明了各算法的使用范围。