Two-Phase Mining for Frequent Closed Episodes

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9658
• 期：1
• 页码：55-66
• 全文大小：762 KB
• 参考文献：1.Mannila, H., Toivonen, H., Verkamo, A.I.: Discovering frequent episodes in sequences (Extended Abstract). In: Proceedings of KDD 1995, pp. 210–215 (1995)
  2.Mannila, H., Toivonen, H., Verkamo, A.I.: Discovery of frequent episodes in event sequences. Data Min. Knowl. Disc. 1(3), 259–289 (1997)CrossRef
  3.Laxman, S., Tankasali, V., White, R.: Stream prediction using a generative model based on frequent episodes in event sequences. In: Proceedings of KDD 2008, pp. 453–461 (2008)
  4.Ng, A., Fu, A.W.C.: Mining frequent episodes for relating financial events and stock trends. In: Proceedings of PAKDD 2003, pp. 27–39 (2003)
  5.Wan, L., Chen, L., Zhang, C.: Mining frequent serial episodes over uncertain sequence data. In: Proceedings of EDBT 2013, pp. 215–226 (2013)
  6.Wan, L., Chen, L., Zhang, C.: Mining dependent frequent serial episodes from uncertain sequence data. In: Proceedings of ICDM 2013, pp. 1211–1216 (2013)
  7.Katoh, T., Tago, S., Asai, T., Morikawa, H., Shigezumi, J., Inakoshi, H.: Mining frequent partite episodes with partwise constraints. In: Appice, A., Ceci, M., Loglisci, C., Manco, G., Masciari, E., Ras, Z.W. (eds.) NFMCP 2013. LNCS, vol. 8399, pp. 117–131. Springer, Heidelberg (2014)
  8.Ma, X., Pang, H., Tan, L.: Finding constrained frequent episodes using minimal occurrences. In: Proceedings of ICDM 2004, pp. 471–474 (2004)
  9.Laxman, S., Sastry, P.S., Unnikrishnan, K.P.: Discovering frequent episodes and learning hidden markov models: A formal connection. IEEE Trans. Knowl. Data Eng. 17(11), 1505–1517 (2005)CrossRef
  10.Laxman, S., Sastry, P., Unnikrishnan, K.: A fast algorithm for finding frequent episodes in event streams. In: Proceedings of KDD 2007, pp. 410–419 (2007)
  11.Huang, K., Chang, C.: Efficient mining of frequent episodes from complex sequences. Inf. Syst. 33(1), 96–114 (2008)CrossRef
  12.Zhou, W., Liu, H., Cheng, H.: Mining closed episodes from event sequences efficiently. In: Proceedings of PAKDD 2010, pp. 310–318 (2010)
  13.Tatti, N., Cule, B.: Mining closed strict episodes. In: Proceedings of ICDM 2010, pp. 501–510 (2010)
  14.Tatti, N., Cule, B.: Mining closed episodes with simultaneous events. In: Proceedings of KDD 2011, pp. 1172–1180 (2011)
  15.Zhu, H., Wang, W., Shi, B.: Frequent closed episode mining based on minimal and non-overlaping occurrence. J. Comput. Res. Dev. 50(4), 852–860 (2013)
  16.Wu, C., Lin, Y., Yu, P.S., Tseng, V.S.: Mining high utility episodes in complex event sequences. In: Proceedings of KDD 2013, pp. 536–544 (2013)
  17.Ao, X., Luo, P., Li, C., Zhuang, F., He, Q.: Online frequent episode mining. In: Proceedings of ICDE 2015, pp. 891–902 (2015)
  18.Tatti, N.: Discovering episodes with compact minimal windows. Data Min. Knowl. Disc. 28(4), 1046–1077 (2014)MathSciNet CrossRef MATH
  
• 作者单位：Guoqiong Liao (18)
  Xiaoting Yang (18)
  Sihong Xie (19)
  Philip S. Yu (19)
  Changxuan Wan (18)
  
  18. School of Information Technology, Jiangxi University of Finance and Economics, Nanchang, China
  19. Department of Computer Science, University of Illinois at Chicago, Chicago, IL, USA
  
• 丛书名：Web-Age Information Management
• ISBN：978-3-319-39937-9
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9658

文摘

The concept of episodes was introduced for discovering the useful and interesting temporal patterns from the sequential data. Over the years, many episode mining strategies have been suggested, which can be roughly classified into two classes: Apriori-based breadth-first algorithms and projection-based depth-first algorithms. As we know, both kinds of algorithms are level-wise pattern growth methods, so that they have higher computational overhead due to level-wise growth iteration. In addition, their mining time will increase with the increase of sequence length. In the paper, we propose a novel two-phase strategy to discover frequent closed episodes. That is, in phase I, we present a level-wise shrinking mechanism, based on maximal duration episodes, to find the candidate frequent closed episodes from the episodes with the same 2-neighboring episode prefix, and in phase II, we compare the candidates with different prefixes to discover the final frequent closed episodes. The advantage of the suggested mining strategy is it can reduce mining time due to narrowing episode mapping range when doing closure judgment. Experiments on simulated and real datasets demonstrate that the suggested strategy is effective and efficient.