计算机应用 ›› 2019, Vol. 39 ›› Issue (2): 421-428.DOI: 10.11772/j.issn.1001-9081.2018061366

• 数据科学与技术 • 上一篇    下一篇

基于时滞特征的时序依赖情节发现

顾佩月1,2, 刘峥1,2, 李云1,2, 李涛1,2   

  1. 1. 江苏省大数据安全与智能处理重点实验室(南京邮电大学), 南京 210023;
    2. 南京邮电大学 计算机学院, 南京 210023
  • 收稿日期:2018-07-02 修回日期:2018-08-20 出版日期:2019-02-10 发布日期:2019-02-15
  • 通讯作者: 刘峥
  • 作者简介:顾佩月(1994-),女,江苏泰兴人,硕士研究生,主要研究方向:日志分析、数据挖掘;刘峥(1980-),男,江苏南京人,讲师,博士,CCF会员,主要研究方向:图数据挖掘与查询、网络数据挖掘;李云(1975-),男,安徽合肥人,教授,博士,CCF会员,主要研究方向:机器学习、数据挖掘、分布式计算、模式识别;李涛(1975-2017),男,四川梓潼人,教授,博士,主要研究方向:数据挖掘、机器学习、信息检索。
  • 基金资助:
    江苏省自然科学基金资助项目(BK20171447);江苏省高等学校自然科学研究项目(17JKB520024);南京邮电大学引进人才科研启动基金资助项目(NY215045)。

Time lag based temporal dependency episodes discovery

GU Peiyue1,2, LIU Zheng1,2, LI Yun1,2, LI Tao1,2   

  1. 1. Jiangsu Key Laboratory of Big Data Security & Intelligent Processing(Nanjing University of Posts and Telecommunications), Nanjing Jiangsu 210023, China;
    2. School of Computer Science & Technology, Nanjing University of Posts and Telecommunications, Nanjing Jiangsu 210023, China
  • Received:2018-07-02 Revised:2018-08-20 Online:2019-02-10 Published:2019-02-15
  • Supported by:
    This work is partially supported by the Natural Science Foundation of Jiangsu Province (BK20171447), the Natural Science Foundation for Colleges and Universities of Jiangsu Province (17JKB520024), the Introduction of Talent Research Start-up Foundation of Nanjing University of Posts and Telecommunications (NY215045).

摘要: 对于事件序列中的时序依赖发现,传统的频繁情节发现方法一方面使用时间窗口机制挖掘事件之间简单的关联依赖,另一方面无法有效处理事件的交叉时序关联。针对以上问题,提出了时滞情节发现的概念,在频繁情节发现的基础上,设计了一种基于相邻事件匹配集(AEM)的时滞情节发现算法。首先,引入时滞的概率统计模型进行事件序列匹配,避免预先设定时间窗口,处理可能存在的交叉关联;然后,将时滞挖掘转化为最优化问题,使用迭代的方式得到时滞情节之间的时间间隔分布;最后,利用假设检验区分串行时滞情节和并行时滞情节。理论分析与实验结果表明,与目前最新的时滞挖掘方法迭代最近事件(ICE)算法相比,基于AEM的时滞情节发现算法模拟的时滞分布与真实时滞分布的平均KL距离为0.056,缩短了20.68%。基于AEM的时滞情节发现算法通过时滞的概率统计模型衡量事件多种匹配情况的可能性,获得一对多的相邻事件匹配集,比ICE算法中的一对一匹配更加有效地模拟了实际情况。

关键词: 时序依赖, 事件序列, 频繁情节, 时滞, 概率统计模型

Abstract: Concerning the problem that a predefined time window is usually used to mine simple association dependencies between events in the traditional frequent episode discovery, which cannot effectively handle interleaved temporal correlations between events, a concept of time-lag episode discovery was proposed. And on the basis of frequent episode discovery, Adjacent Event Matching set (AEM) based time-lag episode discovery algorithm was proposed. Firstly, a probability statistical model introduced with time-lag was introduced to realize event sequence matching and handle optional interleaved associations without a predefined time window. Then the discovery of time lag was formulated as an optimization problem which can be solved iteratively to obtain time interval distribution between time-lag episodes. Finally, the hypothesis test was used to distinguish serial and parallel time-lag episodes. The experimental results show that compared with Iterative Closest Event (ICE) algorithm which is the latest method of time-lag mining, the Kullback-Leibler (KL) divergence between true and experimental distributions discovered by AEM is 0.056 on average, which is decreased by 20.68%. AEM algorithm measures the possibility of multiple matches of events through a probability statistical model of time lag and obtains a one-to-many adjacent event matching set, which is more effective than the one-to-one matching set in ICE for simulating the actual situation.

Key words: temporal dependency, event sequence, frequent episode, time lag, probability statistical model

中图分类号: