iBet uBet web content aggregator. Adding the entire web to your favor.

Link to original content: https://doi.org/10.1145/2939672.2939761

Keeping it Short and Simple | Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

research-article

Keeping it Short and Simple: Summarising Complex Event Sequences with Multivariate Patterns

Authors:

Jilles Vreeken,

Arno SiebesAuthors Info & Claims

KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Pages 735 - 744

https://doi.org/10.1145/2939672.2939761

Published: 13 August 2016 Publication History

Abstract

We study how to obtain concise descriptions of discrete multivariate sequential data. In particular, how to do so in terms of rich multivariate sequential patterns that can capture potentially highly interesting (cor)relations between sequences. To this end we allow our pattern language to span over the domains (alphabets) of all sequences, allow patterns to overlap temporally, as well as allow for gaps in their occurrences. We formalise our goal by the Minimum Description Length principle, by which our objective is to discover the set of patterns that provides the most succinct description of the data. To discover high-quality pattern sets directly from data, we introduce Ditto, a highly efficient algorithm that approximates the ideal result very well.

Experiments show that Ditto correctly discovers the patterns planted in synthetic data. Moreover, it scales favourably with the length of the data, the number of attributes, the alphabet sizes. On real data, ranging from sensor networks to annotated text, Ditto discovers easily interpretable summaries that provide clear insight in both the univariate and multivariate structure.

References

[1]

R. Agrawal and R. Srikant. Mining sequential patterns. In ICDE, pages 3--14, Los Alamitos, CA, USA, 1995. IEEE Computer Society.

Digital Library

[2]

R. Bathoorn, A. Koopman, and A. Siebes. Reducing the frequent pattern set. In ICDM-Workshop, pages 1--5, 2006.

Digital Library

[3]

R. Bertens and A. Siebes. Characterising seismic data. In SDM, pages 884--892. SIAM, 2014.

[4]

K. Budhathoki and J. Vreeken. The difference and the norm -- characterising similarities and differences between databases. In ECML PKDD. Springer, 2015.

[5]

Y.-C. Chen, J.-C. Jiang, W.-C. Peng, and S.-Y. Lee. An efficient algorithm for mining time interval-based patterns in large database. In CIKM, pages 49--58. ACM, 2010.

Digital Library

[6]

B. Chiu, E. Keogh, and S. Lonardi. Probabilistic discovery of time series motifs. In KDD, pages 493--498. ACM, 2003.

Digital Library

[7]

T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley-Interscience New York, 2006.

Digital Library

[8]

P. Grünwald. The Minimum Description Length Principle. MIT Press, 2007.

[9]

Y. He, J. Wang, and L. Zhou. Efficient incremental mining of frequent sequence generators. In DASFAA, pages 168--182, 2011.

Digital Library

[10]

H. T. Lam, F. Mörchen, D. Fradkin, and T. Calders. Mining compressing sequential patterns. In SDM, 2012.

[11]

H. T. Lam, F. Mörchen, D. Fradkin, and T. Calders. Mining compressing sequential patterns. Statistical Analysis and Data Mining, 7(1):34--52, 2014.

Digital Library

[12]

J. Lin, E. Keogh, P. Patel, and S. Lonardi. Finding motifs in time series. In KDD-TDM, pages 53--68, 2002.

[13]

J. Lin, E. Keogh, L. Wei, and S. Lonardi. Experiencing sax: A novel symbolic representation of time series. Data Min. Knowl. Disc., 15(2):107--144, Oct. 2007.

Digital Library

[14]

H. Mannila and C. Meek. Global partial orders from sequential data. In KDD, pages 161--168, 2000.

Digital Library

[15]

H. Mannila, H. Toivonen, and A. I. Verkamo. Efficient algorithms for discovering association rules. In KDD, pages 181--192, 1994.

[16]

H. Mannila, H. Toivonen, and A. I. Verkamo. Discovery of frequent episodes in event sequences. Data Min. Knowl. Disc., 1(3):259--289, 1997.

Digital Library

[17]

D. Minnen, C. Isbell, I. Essa, and T. Starner. Detecting subdimensional motifs: An efficient algorithm for generalized multivariate pattern discovery. In ICDM, pages 601--606. IEEE, 2007.

Digital Library

[18]

F. Mörchen and A. Ultsch. Efficient mining of understandable patterns from multivariate interval time series. Data Min. Knowl. Disc., 15(2):181--215, 2007.

Digital Library

[19]

T. Oates and P. R. Cohen. Searching for structure in multiple streams of data. In ICML, pages 346--354, 1996.

[20]

N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal. Discovering frequent closed itemsets for association rules. In ICDT, pages 398--416. ACM, 1999.

Digital Library

[21]

J. Pei, J. Han, B. Mortazaviasl, J. Wang, H. Pinto, Q. Chen, U. Dayal, and M. Hsu. Mining sequential patterns by pattern-growth: The prefixspan approach. IEEE TKDE, 16(11):1424--1440, 2004.

Digital Library

[22]

A. Siebes, J. Vreeken, and M. van Leeuwen. Item sets that compress. In SDM, pages 393--404. SIAM, 2006.

[23]

K. Smets and J. Vreeken. The odd one out: Identifying and characterising anomalies. In SDM, pages 804--815. SIAM, 2011.

[24]

K. Smets and J. Vreeken. Slim: Directly mining descriptive patterns. In SDM, pages 236--247. SIAM, 2012.

[25]

Y. Tanaka, K. Iwamoto, and K. Uehara. Discovery of time-series motif from multi-dimensional data based on mdl principle. Mach. Learn., 58(2--3):269--300, 2005.

Digital Library

[26]

N. Tatti. Significance of episodes based on minimal windows. In ICDM, pages 513--522, 2009.

Digital Library

[27]

N. Tatti and B. Cule. Mining closed episodes with simultaneous events. In KDD, pages 1172--1180, 2011.

Digital Library

[28]

N. Tatti and J. Vreeken. The long and the short of it: Summarizing event sequences with serial episodes. In KDD, pages 462--470. ACM, 2012.

Digital Library

[29]

U. Vespier, A. J. Knobbe, S. Nijssen, and J. Vanschoren. MDL-based analysis of time series at multiple time-scales. In ECML PKDD, pages 371--386. Springer, 2012.

[30]

U. Vespier, S. Nijssen, and A. Knobbe. Mining characteristic multi-scale motifs in sensor-based time series. In CIKM, pages 2393--2398. ACM, 2013.

Digital Library

[31]

J. Vreeken. Causal inference by direction of information. In SDM. SIAM, 2015.

[32]

J. Vreeken, M. van Leeuwen, and A. Siebes. Krimp: Mining itemsets that compress. Data Min. Knowl. Disc., 23(1):169--214, 2011.

Digital Library

[33]

J. Wang and J. Han. Bide: Efficient mining of frequent closed sequences. In ICDE, page 79, 2004.

Digital Library

[34]

G. Webb and J. Vreeken. Efficient discovery of the most interesting associations. ACM TKDD, 8(3):1--31, 2014.

Digital Library

[35]

C.-W. Wu, Y.-F. Lin, P. S. Yu, and V. S. Tseng. Mining high utility episodes in complex event sequences. In KDD, pages 536--544. ACM, 2013.

Digital Library

Cited By

Gandreti SA. IP. S. S(2024)Breadth-First Search Approach for Mining Serial Episodes with Simultaneous EventsProceedings of the 7th Joint International Conference on Data Science & Management of Data (11th ACM IKDD CODS and 29th COMAD)10.1145/3632410.3632445(36-44)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3632410.3632445
Xu JZhang CXie MZhan XYan LTao YPan Z(2024)IMVis: Visual analytics for influence maximization algorithm evaluation in hypergraphsVisual Informatics10.1016/j.visinf.2024.04.0068:2(13-26)Online publication date: Jun-2024
https://doi.org/10.1016/j.visinf.2024.04.006
Jentner WLindholz GHauptmann HEl-Assady MMa KKeim D(2023)Visual Analytics of Co-Occurrences to Discover Subspaces in Structured DataACM Transactions on Interactive Intelligent Systems10.1145/357903113:2(1-49)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3579031
Show More Cited By

Index Terms

Keeping it Short and Simple: Summarising Complex Event Sequences with Multivariate Patterns
1. Information systems
  1. Information systems applications
    1. Data mining

Recommendations

Discovering compressing serial episodes from event sequences

Most pattern mining methods yield a large number of frequent patterns, and isolating a small relevant subset of patterns is a challenging problem of current interest. In this paper, we address this problem in the context of discovering frequent episodes ...
Summarizing data succinctly with the most informative itemsets
Special Issue on the Best of SIGKDD 2011

Knowledge discovery from data is an inherently iterative process. That is, what we know about the data greatly determines our expectations, and therefore, what results we would find interesting and/or surprising. Given new knowledge about the data, our ...
Krimp: mining itemsets that compress

One of the major problems in pattern mining is the explosion of the number of results. Tight constraints reveal only common knowledge, while loose constraints lead to an explosion in the number of returned patterns. This is caused by large groups of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '16: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 2016

2176 pages

ISBN:9781450342322

DOI:10.1145/2939672

General Chairs:
Balaji Krishnapuram
IBM
,
Mohak Shah
Bosch
,
Program Chairs:
Alex Smola
Amazon
,
Charu Aggarwal
IBM
,
Dou Shen
Baidu
,
Rajeev Rastogi
Amazon

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 August 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Dutch national program COMMIT
Cluster of Excellence 'Multimodal Computing and Interaction' within the Excellence Initiative of the German Federal Government

Conference

KDD '16

Sponsor:

KDD '16: The 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 13 - 17, 2016

California, San Francisco, USA

Acceptance Rates

KDD '16 Paper Acceptance Rate 66 of 1,115 submissions, 6%;

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
513
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)1

Reflects downloads up to 03 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gandreti SA. IP. S. S(2024)Breadth-First Search Approach for Mining Serial Episodes with Simultaneous EventsProceedings of the 7th Joint International Conference on Data Science & Management of Data (11th ACM IKDD CODS and 29th COMAD)10.1145/3632410.3632445(36-44)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3632410.3632445
Xu JZhang CXie MZhan XYan LTao YPan Z(2024)IMVis: Visual analytics for influence maximization algorithm evaluation in hypergraphsVisual Informatics10.1016/j.visinf.2024.04.0068:2(13-26)Online publication date: Jun-2024
https://doi.org/10.1016/j.visinf.2024.04.006
Jentner WLindholz GHauptmann HEl-Assady MMa KKeim D(2023)Visual Analytics of Co-Occurrences to Discover Subspaces in Structured DataACM Transactions on Interactive Intelligent Systems10.1145/357903113:2(1-49)Online publication date: 19-Jun-2023
https://dl.acm.org/doi/10.1145/3579031
Gandreti SP. S. S(2023)Efficient Depth-First Search Approach for Mining Injective General EpisodesProceedings of the 6th Joint International Conference on Data Science & Management of Data (10th ACM IKDD CODS and 28th COMAD)10.1145/3570991.3571012(1-9)Online publication date: 4-Jan-2023
https://dl.acm.org/doi/10.1145/3570991.3571012
van der Linden SWulterkens Bvan Gilst MOvereem Svan Pul CVilanova Avan den Elzen S(2023)FlexEvent: going beyond Case‐Centric Exploration and Analysis of Multivariate Event SequencesComputer Graphics Forum10.1111/cgf.1482042:3(161-172)Online publication date: 27-Jun-2023
https://doi.org/10.1111/cgf.14820
Yu PNordman AMeyer LBoonsong SVrotsou K(2023)Interactive Transformations and Visual Assessment of Noisy Event Sequences: An Application in En-Route Air Traffic Control2023 IEEE 16th Pacific Visualization Symposium (PacificVis)10.1109/PacificVis56936.2023.00017(92-101)Online publication date: Apr-2023
https://doi.org/10.1109/PacificVis56936.2023.00017
Wu JLiu DGuo ZXu QWu Y(2022)TacticFlow: Visual Analytics of Ever-Changing Tactics in Racket SportsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.311483228:1(835-845)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1109/TVCG.2021.3114832
Liu JZhou MFournier-Viger PYang MPan LNouioua M(2022)Discovering Representative Attribute-stars via Minimum Description Length2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00010(68-80)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00010
Galbrun E(2022)The minimum description length principle for pattern mining: a surveyData Mining and Knowledge Discovery10.1007/s10618-022-00846-z36:5(1679-1727)Online publication date: 4-Jul-2022
https://doi.org/10.1007/s10618-022-00846-z
Cüppers JKalofolias JVreeken J(2022)Omen: discovering sequential patterns with reliable prediction delaysKnowledge and Information Systems10.1007/s10115-022-01660-164:4(1013-1045)Online publication date: 5-Mar-2022
https://doi.org/10.1007/s10115-022-01660-1
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents