Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering ›› 2021, Vol. 47 ›› Issue (2): 118-125. doi: 10.19678/j.issn.1000-3428.0057181

• Advanced Computing and Data Processing • Previous Articles     Next Articles

A MDL-based Pattern Mining Algorithm for Log Sequences

DU Shiqing1, WANG Peng2, WANG Wei2   

  1. 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

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

杜诗晴1, 王鹏2, 汪卫2   

  1. 1. 复旦大学 软件学院, 上海 201203;
    2. 复旦大学 计算机科学技术学院, 上海 201203
  • 作者简介:杜诗晴(1995-),女,硕士研究生,主研方向为数据挖掘;王鹏(通信作者),副教授、博士生导师;汪卫,教授、博士生导师。
  • 基金资助:
    国家自然科学基金(61672163)。

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

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

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

CLC Number: