融合多种支持度定义的频繁情节挖掘算法  

Frequent Episode Mining Algorithm Compatible with Various Support Definitions

作　　者：朱辉生 陈琳 倪艺洋 汪卫[3] 施伯乐[3] ZHU Hui-Sheng;CHEN Lin;NI Yi-Yang;WANG Wei;SHI Bai-Le(School of Mathematics and InformationTechnology,Jiangsu Second Normal University,Nanjing 211200,China;School of Computer Science and Technology,Taizhou University,Taizhou 225300,China;School of Computer Science,Fudan University,Shanghai 200433,China)

机构地区：[1]江苏第二师范学院数学与信息技术学院,江苏南京211200 [2]泰州学院计算机科学与技术学院,江苏泰州225300 [3]复旦大学计算机科学技术学院,上海200433

出　　处：《软件学报》2020年第7期2169-2183,共15页Journal of Software

基　　金：国家自然科学基金(61802274,61701201,U1509213);教育部“云数融合科教创新”基金(2017B06109);江苏省自然科学基金(BK20141307,BK20170758);江苏省“333工程”基金(BRA2015212);江苏省无线通信重点实验室开放研究基金(2017WICOM02)。

摘　　要：事件序列中蕴藏的频繁情节刻画了用户或系统的行为规律.现有的频繁情节挖掘算法在各自支持度定义下具有较好的挖掘效果,但在支持度定义发生变化时却很难甚至无法直接挖掘频繁情节.针对用户多变的支持度定义需求,提出了一种频繁情节挖掘算法FEM-DFS(frequent episode mining-depth first search).该算法通过单遍扫描事件序列,以深度优先搜索方式来发现频繁情节,以共享前/后缀树来存储频繁情节,以单调性、前缀单调性或后缀单调性来压缩频繁情节的搜索空间.实验评估证实了所提出算法的有效性.Frequent episodes hidden in an event sequence describe the behavioral regularities of users or systems.Existing algorithms yield good results for mining frequent episodes under their respective definitions of support,but each of them is difficult or impossible to directly mine frequent episodes when the definition of support is changed.To meet the needs of changeable support definitions of users,an algorithm called FEM-DFS(frequent episode mining-depth first search)is proposed to mine frequent episodes in this paper.After scanning the event sequence one pass,FEM-DFS finds frequent episodes in a depth first search fashion,stores frequent episodes in a shared prefix/suffix tree and compresses the search space of frequent episodes by utilizing monotonicity,prefix monotonicity or suffix monotonicity.Experimental evaluation demonstrates the effectiveness of the proposed algorithm.

关 键 词：事件序列 频繁情节 挖掘 支持度 深度优先遍历 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]