微信服务号

微信订阅号

2025-5-13- 16
Home > Archive>Volume 31, Issue 7, 2020 >2169-2183. DOI:10.13328/j.cnki.jos.005851
PDF HTML XML Export Cite reminder
Frequent Episode Mining Algorithm Compatible with Various Support Definitions
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61802274, 61701201, U1509213); "Integration of Cloud Computing and Big Data, Innovation of Science and Education" Foundation of Ministry of Education of China (2017B06109); Natural Science Foundation of Jiangsu Province of China (BK20141307, BK20170758); "333 Engineering" Foundation of Jiangsu Province of China (BRA2015212); Open Project Foundation of Key Laboratory of Wireless Communications of Jiangsu Province of China (2017WICOM02)

  • Article
    • | |
  • Metrics
    • |
  • Reference [25]
    • |
  • Related
    • |
  • Cited by
    • | |
  • Comments
    Abstract:

    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.

    Reference
    [1] Mannila H, Toivonen H, Verkamo AI. Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, 1997,1(3):259-289.
    [2] Méger N, Rigotti C. Constraint-based mining of episode rules and optimal window sizes. In:Proc. of PKDD. 2004. 313-324.
    [3] Lin YF, Huang CF, Tseng VS. A novel methodology for stock investment using high utility episode mining and genetic algorithm. Applied Soft Computing, 2017,59:303-315.
    [4] Ma X, Pang HH, Tan KL. Finding constrained frequent episodes using minimal occurrences. In:Proc. of the ICDM. 2004. 471-474.
    [5] Zhou WZ, Liu HY, Cheng H. Mining closed episodes from event sequences efficiently. In:Proc. of the PAKDD. 2010. 310-318.
    [6] Wu JJ, Wan L, Xu ZR. Algorithms to discover complete frequent episodes in sequences. In:Proc. of the PAKDD. 2011. 267-278.
    [7] Wu CW, Lin YF, Yu PS, Tseng VS. Mining high utility episodes in complex event sequences. In:Proc. of the SIGKDD. 2013. 536-544.
    [8] Lin SK, Qiao JZ. An episode mining method based on episode matrix and frequent episode tree. Control and Decision, 2013,28(3):339-344(in Chinese with English abstract).
    [9] Ao X, Luo P, Li CK, Zhuang FZ, He Q, Shi ZZ. Discovering and learning sensational episodes of news events. In:Proc. of the WWW. 2014. 217-218.
    [10] Huang KY, Chang CH. Efficient mining of frequent episodes from complex sequences. Information Systems, 2008,33(1):96-114.
    [11] Iwanuma K, Ishihara R, Takano Y, Nabeshima H. Extracting frequent subsequences from a single long data sequence. In:Proc. of the ICDM. 2005. 186-193.
    [12] Avinash A, Ibrahim A, Sastry PS. Pattern-growth based frequent serial episode discovery. Data & Knowledge Engineering, 2013,87:91-108.
    [13] Laxman S. Discovering frequent episodes:Fast algorithms, connections with HMMs and generalizations[Ph.D. Thesis]. Bangalore, 2006.
    [14] Laxman S, Sastry PS, Unnikrishnan K. Discovering frequent episodes and learning hidden Markov models:A formal connection. IEEE Trans. on Knowledge and Data Engineering, 2005,17(11):1505-1517.
    [15] Laxman S, Sastry PS, Unnikrishnan KP. A fast algorithm for finding frequent episodes in event streams. In:Proc. of the SIGKDD. 2007. 410-419.
    [16] Zhu HS, Wang P, He XM, Li YJ, Wang W, Shi BL. Effcient episode mining with minimal and non-overlapping occurrences. In:Proc. of the ICDM. 2010. 1211-1216.
    [17] Zhu HS, Wang P, Wang W, Shi BL. Discovering frequent closed episodes from an event sequence. In:Proc. of the IJCNN. 2012. 2292-2299.
    [18] Liao GQ, Yang XT, Xie S, Yu PS, Wan CX. Two phase mining for frequent closed episodes. In:Proc. of the WAIM. 2016. 55-66.
    [19] Avinash A, Laxman S, Sastry PS. A unified view of the apriori-based algorithms for frequent episode discovery. Knowledge and Information Systems, 2012,31:223-250.
    [20] Zhu HS, Wang W, Shi BL. Extracting non-redundant episode rules based on frequent closed episodes and their generators. Chinese Journal of Computers, 2012,35(1):53-64(in Chinese with English abstract).
    [21] Zhu HS. Research on stream prediction based on episode rule matching[Ph.D. Thesis]. Shanghai:Fudan University, 2011(in Chinese with English abstract).
    附中文参考文献:
    [8] 林树宽,乔建忠.一种基于情节矩阵和频繁情节树的情节挖掘方法.控制与决策,2013,28(3):339-344.
    [20] 朱辉生,汪卫,施伯乐.基于频繁闭情节及其生成子的无冗余情节规则抽取.计算机学报,2012,35(1):53-64.
    [21] 朱辉生.基于情节规则匹配的数据流预测研究[博士学位论文].上海:复旦大学,2011.
    Related
    Cited by
Get Citation

朱辉生,陈琳,倪艺洋,汪卫,施伯乐.融合多种支持度定义的频繁情节挖掘算法.软件学报,2020,31(7):2169-2183

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:March 27,2018
  • Revised:December 28,2018
  • Online: July 11,2020
  • Published: July 06,2020
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2044213Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063