Mining high utility episodes in complex event sequences

Cheng Wei Wu, Yu Feng Lin, Philip S. Yu, Vincent Shin-Mu Tseng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

66 Scopus citations

Abstract

Frequent episode mining (FEM) is an interesting research topic in data mining with wide range of applications. However, the traditional framework of FEM treats all events as having the same importance/utility and assumes that a same type of event appears at most once at any time point. These simplifying assumptions do not reflect the characteristics of scenarios in real applications and thus the useful information of episodes in terms of utilities such as profits is lost. Furthermore, most studies on FEM focused on mining episodes in simple event sequences and few considered the scenario of complex event sequences, where different events can occur simultaneously. To address these issues, in this paper, we incorporate the concept of utility into episode mining and address a new problem of mining high utility episodes from complex event sequences, which has not been explored so far. In the proposed framework, the importance/utility of different events is considered and multiple events can appear simultaneously. Several novel features are incorporated into the proposed framework to resolve the challenges raised by this new problem, such as the absence of antimonotone property and the huge set of candidate episodes. Moreover, an efficient algorithm named UP-Span (Utility ePisodes mining by Spanning prefixes) is proposed for mining high utility episodes with several strategies incorporated for pruning the search space to achieve high efficiency. Experimental results on real and synthetic datasets show that UP-Span has excellent performance and serves as an effective solution to the new problem of mining high utility episodes from complex event sequences.

Original languageEnglish
Title of host publicationKDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
EditorsRajesh Parekh, Jingrui He, Dhillon S. Inderjit, Paul Bradley, Yehuda Koren, Rayid Ghani, Ted E. Senator, Robert L. Grossman, Ramasamy Uthurusamy
PublisherAssociation for Computing Machinery
Pages536-544
Number of pages9
ISBN (Electronic)9781450321747
DOIs
StatePublished - 11 Aug 2013
Event19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013 - Chicago, United States
Duration: 11 Aug 201314 Aug 2013

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
VolumePart F128815

Conference

Conference19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013
CountryUnited States
CityChicago
Period11/08/1314/08/13

Keywords

  • Complex event sequences
  • Episode mining
  • High utility episodes
  • Utility mining

Fingerprint Dive into the research topics of 'Mining high utility episodes in complex event sequences'. Together they form a unique fingerprint.

  • Cite this

    Wu, C. W., Lin, Y. F., Yu, P. S., & Tseng, V. S-M. (2013). Mining high utility episodes in complex event sequences. In R. Parekh, J. He, D. S. Inderjit, P. Bradley, Y. Koren, R. Ghani, T. E. Senator, R. L. Grossman, & R. Uthurusamy (Eds.), KDD 2013 - 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 536-544). [2487654] (Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; Vol. Part F128815). Association for Computing Machinery. https://doi.org/10.1145/2487575.2487654