Page 65 - 《软件学报》2021年第7期

王璐 等:基于事件关系保障识别质量的自适应分析方法 1983

3 基于事件关系保障识别质量的分析方法

3.1 事件关系挖掘与建模
(1) 事件关系挖掘
在各类事件关系中,本文选用能够反映事件间触发情况的因果关系进行事件识别,从而在某一事件发生后
可推理出与其相关的后续事件是否会发生.系统运行日志中一般仅记录系统的历史运行状态,从中较难直接挖
掘出事件因果关系.但日志记录了各事件的具体发生时间,为抽取事件时序关系提供了可能.因此,本文采用序
列模式挖掘算法对系统运行日志进行挖掘,得到事件时序关系,并根据定义 4 将满足转化约束的时序关系转换
为因果关系.
序列模式挖掘中常用的算法包括 GSP 算法(generalized sequential pattern mining algorithm)、AprioriAll 算
法等,它们通过一系列的序列连接、剪切操作生成包含时序关系的序列.相较于 AprioriAll 算法,GSP 算法引入
了时间约束,通过连接和剪切可有针对性地生成序列,算法执行效率较高.因此,本文建立了基于 GSP 算法的事
件关系挖掘方法,抽取出潜藏在系统运行日志中的事件因果关系.
定义 8(事件项目). GSP 算法中的事件项目是序列中的最小组成单位,简称项目,记作 i j ,j=1…n.本文将系统
资源、环境变量或软件性能指标等超过阈值的异常环境状态作为事件项目.例如,i 1 表示 CPU 使用率超过阈值,i 2
表示网络带宽超过阈值,i 3 表示响应时间超过阈值.
定义 9(项目集). 一个或多个事件项目的集簇组成 GSP 算法中的项目集,简称元素,记作{i 1 ,i 2 ,…,i n }.
定义 10(元素时间窗大小). 元素中最晚出现的事件项目 i n 与最先出现的事件项目 i 1 之间的最大允许时间
差,记作 ElementTimeWindow,简称 ETW.
定义 11(序列). 不同项目集的有序列表组成 GSP 算法中的序列,记作 s={i 1 ,i 2 }{i 3 ,i 4 ,i 5 }{i 6 ,i 7 }…{i p ,i q }.k-序
列是指序列中包含 k 个事件项目,该序列的长度为 k,如{i 1 ,i 2 }{i 3 ,i 4 ,i 5 }表示 5-序列.
定义 12(序列时间窗大小). 序列中最晚出现的事件项目 i q 与最先出现的事件项目 i 1 之间的时间间隔,记作
SequenceTimeWindow,简称 STW.
定义 13(序列数据库). 多条序列形成 GSP 算法中的序列数据库,记作 S.
定义 14(支持度). 序列 s 的支持度是指序列数据库 S 中包含序列 s 的序列个数.
定义 15(候选序列). 长度为 i 的序列经过连接和剪切操作产生长度为 i+1 的序列,这些序列称为候选序列.
定义 16(频繁序列). 给定最小支持度 minsup,若候选序列的支持度超过最小支持度,则为频繁序列.
本文主要从系统运行日志中挖掘获得事件因果关系.因此,在收集得到系统运行日志后,本文首先对其进行
去噪声处理和去缺失处理;然后进行时间约束处理,通过设置元素的时间窗大小 ETW 以及序列的时间窗大小
STW,将日志数据划分为序列,以得到序列数据库 S.因为只有符合时间约束的序列包含的事件项目才具有事件
相关性 [31] ,才能使得挖掘结果更符合事件发生的特点.序列数据库 S 则作为本文基于 GSP 算法的事件关系挖掘
算法的输入.下面介绍该算法的具体工作过程.
算法 1. 基于 GSP 算法的事件关系挖掘.
输入:序列数据库 S,元素时间窗大小 ETW,序列时间窗大小 STW,最小支持度 minsup;
输出:事件因果关系表 CRT.
1. C 1 =init(S) //得到候选 1-序列,为初始种子集
2. n=S.number //S 中序列的数量
3. F 1 ={f|fC 1 ,f.count/n≥minsup} //得到频繁 1-序列
4. for (k=2;F k–1 ;k++)
5. C k =JoinAndPrune(F k–1 ) //连接和剪切生成候选 k-序列
6. for each sS
7. for cC k