一种基于MDL的日志序列模式挖掘算法

doi:10.19678/j.issn.1000-3428.0057181

计算机工程 ›› 2021, Vol. 47 ›› Issue (2): 118-125. doi: 10.19678/j.issn.1000-3428.0057181

一种基于MDL的日志序列模式挖掘算法

杜诗晴¹, 王鹏², 汪卫²

1. 复旦大学软件学院, 上海 201203;
2. 复旦大学计算机科学技术学院, 上海 201203

收稿日期:2020-01-13 修回日期:2020-02-17 出版日期:2021-02-15 发布日期:2020-02-28
作者简介:杜诗晴(1995-),女,硕士研究生,主研方向为数据挖掘;王鹏(通信作者),副教授、博士生导师;汪卫,教授、博士生导师。
基金资助:
国家自然科学基金（61672163）。

A MDL-based Pattern Mining Algorithm for Log Sequences

DU Shiqing¹, WANG Peng², WANG Wei²

1. Software School, Fudan University, Shanghai 201203, China;
2. School of Computer Science, Fudan University, Shanghai 201203, China

Received:2020-01-13 Revised:2020-02-17 Online:2021-02-15 Published:2020-02-28

摘要/Abstract

摘要： 日志数据是互联网系统产生的过程性事件记录数据，从日志数据中挖掘出高质量序列模式可帮助工程师高效开展系统运维工作。针对传统模式挖掘算法结果冗余的问题，提出一种从时序日志序列中挖掘序列模式（DTS）的算法。DTS采用启发式思路挖掘能充分代表原序列中事件关系和时序规律的模式集合，并将最小描述长度准则应用于模式挖掘，设计一种考虑事件关系和时序关系的编码方案，以解决模式规模爆炸问题。在真实日志数据集上的实验结果表明，与SQS、CSC与ISM等序列模式挖掘算法相比，该算法能高效挖掘出含义丰富且冗余度低的序列模式。

关键词: 数据挖掘, 日志分析, 事件关系, 最小描述长度准则, 序列模式

Abstract: Logs contain rich information about procedural events generated in Internet systems,and the mining of high-quality sequence modes from log data can improve the efficiency of system operation and maintenance. To address the problem of redundant results of traditional pattern mining algorithms,this paper proposes a Discovering sequential patterns from Temporal log Sequences (DTS) algorithm. DTS heuristically discovers the set of patterns that can best represent the event relationships and temporal regularities in the original sequence. At the same time,DTS applies the Minimum Description Length (MDL) principle to pattern mining,and proposes an encoding scheme that considers event relationships as well as temporal relationships to solve pattern explosion. Experimental results on real log datasets show that compared with SQS,CSC,ISM and other sequential pattern mining algorithms,the proposed algorithm is capable of efficiently mining meaningful sequential patterns with low redundancy.

Key words: data mining, log analysis, event relationships, Minimum Description Length (MDL) principle, sequential patterns

中图分类号:

TP391

杜诗晴, 王鹏, 汪卫. 一种基于MDL的日志序列模式挖掘算法[J]. 计算机工程, 2021, 47(2): 118-125.

DU Shiqing, WANG Peng, WANG Wei. A MDL-based Pattern Mining Algorithm for Log Sequences[J]. Computer Engineering, 2021, 47(2): 118-125.

https://www.ecice06.com/CN/Y2021/V47/I2/118

图/表 7

20210225091554

20210225091558

20210225091601

20210225091604

20210225091610

20210225091614

20210225091618

参考文献 20

[1]	AGRAWAL R,SRIKANT R.Mining sequentialp patterns[C]//Proceedings of the 11th International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,1995:3-14.
[2]	NWALD P D.The minimum description length principle (adaptive computation and machine learning)[M].Cambridge,USA:MIT Press,2007.
[3]	TATTI N,VREEKEN J.The long and the short of it:summarising event sequences with serial episodes[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2012:462-470.
[4]	LAM H T,MÖRCHEN F,FRADKIN D,et al.Mining compressing sequential patterns[J].Statistical Analysis and Data Mining:the ASA Data Science Journal,2014,7(1):34-52.
[5]	IBRAHIM A,SASTRY S,SASTRY P S.Discovering compressing serial episodes from event sequences[J].Knowledge and Information Systems,2016,47(2):405-432.
[6]	MIN D,LI F,ZHENG G,et al.DeepLog:anomaly detection and diagnosis from system logs through deep learning[C]//Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security.New York,USA:ACM Press,2017:1285-1298.
[7]	XIAO Y,JOSHI P,XU J,et al.CloudSeer:workflow monitoring of cloud infrastructures via interleaved logs[C]//Proceedings of the 21st International Conference on Architectural Support for Programming Languages and Operating Systems.New York,USA:ACM Press,2016:489-502.
[8]	SHUANG Kai,LI Yiwen,LÜ Zhiheng,et al.Log template extraction algorithm based on normalized feature discrimination[J].Journal of Beijing University of Posts and Telecommunications,2020,43(1):68-73.(in Chinese)双锴,李怡雯,吕志恒,等.基于归一化特征判别的日志模板挖掘算法[J].北京邮电大学学报,2020,43(1):68-73.
[9]	WANG Weihua,YING Shi,JIA Xiangyang,et al.A multi-type failure prediction method based on log clustering[J].Computer Engineering,2018,44(7):67-73(in Chinese)王卫华,应时,贾向阳,等.一种基于日志聚类的多类型故障预测方法[J].计算机工程.2018,44(7):67-73.
[10]	HE S L,ZHU J M,HE P J,et al.Experience report:system log analysis for anomaly detection[C]//Proceedings of the 27th International Symposium on Software Reliability Engineering.Washington D.C.,USA:IEEE Press,2016:207-218.
[11]	JIAN P,HAN J,MORTAZAVI-ASL B,et al.PrefixSpan:mining sequential patterns by prefix-projected growth[C]//Proceedings of the 17th International Conference on Data Engineering.New York,USA:ACM Press,2001:215-224.
[12]	GOMARIZ A,CAMPOS M,MARIN R,et al.ClaSP:an efficient algorithm for mining frequent closed sequences[EB/OL].[2019-12-10].http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=30AC1EBBDC64DA97300F9BCB9A1606B1?doi=10.1.1.377.3720&rep=rep1&type=pdf.
[13]	GUAN Enzheng,CHANG Xiaoyu,WANG Zhe,et al.Mining maximal sequential patterns[C]//Proceedings of International Conference on Neural Networks and Brain.Washington D.C.,USA:IEEE Press,2005:525-528.
[14]	HU J Y,MOJSILOVIC A.High-utility pattern mining:a method for discovery of high-utility item sets[J].Pattern Recognition,2007,40(11):3317-3324.
[15]	TZVETKOV P,YAN X,HAN J.TSP:mining top-k closed sequential patterns[J].Knowledge and Information Systems,2005,7(4):438-457.
[16]	VREEKEN J,VAN LEEUWEN M,SIEBES A.Krimp:mining itemsets that compress[J].Data Mining and Knowledge Discovery,2011,23(1):169-214.
[17]	FU Q,LOU J G,WANG Y,et al.Execution anomaly detection in distributed systems through unstructured log analysis[C]//Proceedings of the 9th IEEE International Conference on Data Mining.Washington D.C.,USA:IEEE Press,2009:149-158.
[18]	HE P J,ZHU J M,ZHENG Z B,et al.Drain:an online log parsing approach with fixed depth tree[C]//Proceedings of 2017 IEEE International Conference on Web Services.Washington D.C.,USA:IEEE Press,2017:33-40.
[19]	FOWKES J,SUTTON C.A subsequence interleaving model for sequential pattern mining[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2016:835-844.
[20]	YAN Y,CAO L,MADDEN S,et al.SWIFT:mining representative patterns from large event streams[EB/OL].[2019-12-10].https://arxiv.org/pdf/1602.05012.pdf.

选择文件类型/文献管理软件名称

选择包含的内容

一种基于MDL的日志序列模式挖掘算法

A MDL-based Pattern Mining Algorithm for Log Sequences

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 20

相关文章 15

编辑推荐

Metrics

本文评价

[1]	杨鸿茜, 武优西, 耿萌, 刘靖宇, 李艳. 高效的一次性弱间隙序列模式挖掘算法[J]. 计算机工程, 2024, 50(3): 60-67.
[2]	邵良杉, 赵松泽. 基于多模型融合的不完整数据分数插补算法[J]. 计算机工程, 2023, 49(9): 79-88, 98.
[3]	席荣康, 蔡满春, 芦天亮. 基于数据增强与流数据处理的Tor流量分析模型[J]. 计算机工程, 2023, 49(3): 177-184.
[4]	谷青竹, 董红斌. PPDM中面向k-匿名的MI Loss评估模型[J]. 计算机工程, 2022, 48(4): 143-147.
[5]	王璐, 刘晓清, 何震瀛. 连续时间区间内的频繁词序列挖掘算法[J]. 计算机工程, 2022, 48(2): 79-85,91.
[6]	张攀, 高丰, 周逸, 饶涵宇, 毛冬, 李静. 一种在线实时微服务调用链异常检测方法[J]. 计算机工程, 2022, 48(11): 161-169.
[7]	吴军, 欧阳艾嘉, 张琳. 面向置换检验的冗余对比模式过滤算法[J]. 计算机工程, 2022, 48(1): 75-84.
[8]	吴军, 欧阳艾嘉, 张琳. 面向对比序列模式发现的独立精确置换检验算法[J]. 计算机工程, 2021, 47(8): 45-53,61.
[9]	魏文浩, 唐泽坤, 刘刚. 基于距离和密度的PBK-means算法[J]. 计算机工程, 2020, 46(9): 68-75.
[10]	史明阳, 王鹏, 汪卫. 有监督时间序列分割与状态识别算法[J]. 计算机工程, 2020, 46(5): 131-138.
[11]	张潘, 卢光跃, 吕少卿, 赵雪莉. 基于矩阵分解的属性网络表示学习[J]. 计算机工程, 2020, 46(10): 67-73.
[12]	王慧健, 刘峥, 李云, 李涛. 基于神经网络语言模型的时间序列趋势预测方法[J]. 计算机工程, 2019, 45(7): 13-19,25.
[13]	张玺君, 袁占亭, 张红, 高玮军, 张恩展. 交通轨迹大数据预处理方法研究[J]. 计算机工程, 2019, 45(6): 26-31.
[14]	李克,王海,徐小龙,杜煜. 基于众包感知的移动网络小区信息侦测方法[J]. 计算机工程, 2019, 45(2): 92-100.
[15]	崔晨,邓赵红,王士同. 基于Lasso稀疏学习的径向基函数神经网络模型[J]. 计算机工程, 2019, 45(2): 173-177.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

一种基于MDL的日志序列模式挖掘算法

A MDL-based Pattern Mining Algorithm for Log Sequences

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 20

相关文章 15

编辑推荐

Metrics

本文评价