nach oben

Data Mining and Knowledge Discovery

Erschienen in:

30.06.2023

`TIRPClo`: efficient and complete mining of time intervals-related patterns

verfasst von: Omer Harel, Robert Moskovitch

Erschienen in: Data Mining and Knowledge Discovery | Ausgabe 5/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Mining frequent Time Intervals-Related Patterns (TIRPs) from series of symbolic time intervals offers a comprehensive framework for heterogeneous, multivariate temporal data analysis in various application domains. While gaining a growing interest in recent decades, the efficient mining of frequent TIRPs is still a high computational challenge which has also not yet been investigated in its full complexity. The majority of previous methods discover only the first instances of the TIRPs within each series of symbolic time intervals, whereas their re-occurring instances are ignored. This eventually results in an incomplete discovery of frequent TIRPs, a problem that lies also in the challenge of mining only the frequent closed TIRPs, which was only recently investigated for the first time. In this paper, we introduce TIRPClo—an efficient algorithm for the complete mining of either the entire set of frequent TIRPs, or only the frequent closed TIRPs. The algorithm proposes a non-ambiguous sequential representation of symbolic time intervals series through the intervals’ end-points, as well as a memory-efficient index and a novel method for data projection, due to which it is the first algorithm to guarantee a complete discovery of frequent closed TIRPs. The experimental evaluation conducted on eleven real-world and four synthetic datasets demonstrates that TIRPClo is up to 10 times faster when mining the entire set of frequent TIRPs, and up to more than 100 times faster when mining only the frequent closed TIRPs compared to four state-of-the-art methods, while also reporting lower memory measurements.

Vorheriger Artikel Hydra: competing convolutional kernels for fast and accurate time series classification

Nächster Artikel Social norm bias: residual harms of fairness-aware algorithms

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

https://github.com/TIRPClo/Complete-Time-Intervals-Related-Patterns-Mining.

Allen JF (1983) Maintaining knowledge about temporal intervals. Commun ACM 26(11):832–843. https://doi.org/10.1145/182.358434CrossRefMATH

Ayres J, Flannick J, Gehrke J, et al (2002) Sequential pattern mining using a bitmap representation. In: Proceedings of the Eighth ACM SIGKDD international conference on knowledge discovery and data mining. Association for Computing Machinery, New York, NY, USA, KDD ’02, pp 429–435, https://doi.org/10.1145/775047.775109

Batal I, Sacchi L, Bellazzi R, et al (2009) A temporal abstraction framework for classifying clinical temporal data. In: AMIA Annual Symposium Proceedings, vol 2009. American Medical Informatics Association, Rockville, MD, p 29

Benavoli A, Corani G, Mangili F (2016) Should we really use post-hoc tests based on mean-ranks? J Mach Learn Res 17(1):152–161MathSciNetMATH

Chang L, Wang T, Yang D, et al (2008) Seqstream: mining closed sequential patterns over stream sliding windows. In: 2008 Eighth IEEE International Conference on Data Mining. IEEE Computer Society, Washington, DC, USA, ICDM ’08, pp 83–92, https://doi.org/10.1109/ICDM.2008.36

Chen YC, Peng WC, Lee SY (2015) Mining temporal patterns in time interval-based data. IEEE Trans Knowl Data Eng 27(12):3318–3331. https://doi.org/10.1109/TKDE.2015.2454515CrossRef

Chen YC, Weng JTY, Hui L (2016) A novel algorithm for mining closed temporal patterns from interval-based data. Knowl Inf Syst 46(1):151–183. https://doi.org/10.1007/s10115-014-0815-2CrossRef

Demšar J (2006) Statistical comparisons of classifiers over multiple data sets. J Mach Learn Res 7:1–30MathSciNetMATH

Ezeife CI, Lu Y, Liu Y (2005) Plwap sequential mining: open source code. In: Proceedings of the 1st international workshop on open source data mining: frequent pattern mining implementations. Association for Computing Machinery, New York, NY, USA, OSDM ’05, pp 26–35, https://doi.org/10.1145/1133905.1133910

Fournier-Viger P, Lin JCW, Kiran RU et al (2017) A survey of sequential pattern mining. Data Sci Pattern Recogn 1(1):54–77

Fumarola F, Lanotte PF, Ceci M et al (2016) Clofast: closed sequential pattern mining using sparse and vertical id-lists. Knowl Inf Syst 48(2):429–463. https://doi.org/10.1007/s10115-015-0884-xCrossRef

Garcia S, Herrera F (2008) An extension on" statistical comparisons of classifiers over multiple data sets" for all pairwise comparisons. J Mach Learn Res 9(12):2677MATH

Gomariz A, Campos M, Marin R, et al (2013) Clasp: An efficient algorithm for mining frequent closed sequences. In: Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, Berlin, pp 50–61, https://doi.org/10.1007/978-3-642-37453-1_5

Han J, Pei J, Mortazavi-Asl B, et al (2000) Freespan: Frequent pattern-projected sequential pattern mining. In: Proceedings of the Sixth ACM SIGKDD international conference on knowledge discovery and data mining. Association for Computing Machinery, New York, NY, USA, KDD ’00, pp 355–359, https://doi.org/10.1145/347090.347167

Han J, Pei J, Mortazavi-Asl B, et al (2001) Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth. In: proceedings of the 17th international conference on data engineering. IEEE Computer Society, Washington, DC, USA, pp 215–224

Harel OD, Moskovitch R (2021) Complete closed time intervals-related patterns mining. In: proceedings of the 35th AAAI conference on artificial intelligence. AAAI Press, Palo Alto, CA

Höppner F (2001) Learning temporal rules from state sequences. In: IJCAI Workshop on Learning from Temporal and Spatial Data, Citeseer

Höppner F (2002) Time series abstraction methods: a survey. Informatik bewegt: Informatik 2002–32 Jahrestagung der Gesellschaft für Informatik ev (GI)

Huang JW, Jaysawal BP, Chen KY et al (2019) Mining frequent and top-k high utility time interval-based events with duration patterns. Knowl Inf Syst 61(3):1331–1359. https://doi.org/10.1007/s10115-019-01333-6CrossRef

Huang KY, Chang CH, Tung JH, et al (2006) Cobra: Closed sequential pattern mining using bi-phase reduction approach. In: International Conference on data warehousing and knowledge discovery. Springer, Berlin, pp 280–291, https://doi.org/10.1007/11823728_27

Hui L, Chen YC, Weng JTY et al (2016) Incremental mining of temporal patterns in interval-based database. Knowl Inf Syst 46(2):423–448. https://doi.org/10.1007/s10115-015-0828-5CrossRef

Itzhak N, Jaroszewicz S, Moskovitch R (2023) Continuously predicting a time intervals based pattern completion towards event prediction. PAKDD, Osaka, Japan

Jakkula VR, Cook DJ (2011) Detecting anomalous sensor events in smart home data for enhancing the living experience. Artif Intell Smart Living 11(201):1

Kam PS, Fu AWC (2000) Discovering temporal patterns for interval-based events. In: International conference on data warehousing and knowledge discovery. Springer, Berlin, pp 317–326, https://doi.org/10.1007/3-540-44466-1_32

Kostakis O, Gionis A (2017) On mining temporal patterns in dynamic graphs, and other unrelated problems. In: International conference on complex networks and their applications. Springer, Berlin, pp 516–527, https://doi.org/10.1007/978-3-319-72150-7_42

Kostakis O, Papapetrou P, Hollmén J (2011) Artemis: Assessing the similarity of event-interval sequences. In: Joint European conference on machine learning and knowledge discovery in databases, Springer, pp 229–244, https://doi.org/10.1007/978-3-642-23783-6_15

Kotsifakos A, Papapetrou P, Athitsos V (2013) ibsm: interval-based sequence matching. in: proceedings of the 2013 siam International Conference on Data Mining, SIAM, pp 596–604, https://doi.org/10.1137/1.9781611972832.66

Lavrac N, Keravnou E, Zupan B (2000) Intelligent data analysis in medicine. Encycl Comput Sci Technol 42(9):113–157MATH

Lee Z, Lindgren T, Papapetrou P (2020) Z-miner: An efficient method for mining frequent arrangements of event intervals. In: Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. Association for Computing Machinery, New York, NY, USA, KDD ’20, pp 524–534, https://doi.org/10.1145/3394486.3403095

Lin J, Keogh E, Lonardi S, et al (2003) A symbolic representation of time series, with implications for streaming algorithms. In: Proceedings of the 8th ACM SIGMOD workshop on research issues in data mining and knowledge discovery. Association for Computing Machinery, New York, NY, USA, DMKD ’03, pp 2–11, https://doi.org/10.1145/882082.882086

Lin MY, Lee SY (2002) Fast discovery of sequential patterns by memory indexing. In: International conference on data warehousing and knowledge discovery. Springer, Berlin, pp 150–160, https://doi.org/10.1007/3-540-46145-0_15

Mabroukeh NR, Ezeife CI (2010) A taxonomy of sequential pattern mining algorithms. ACM Comput Surv 43(1):1–41. https://doi.org/10.1145/1824795.1824798CrossRef

Mirbagheri SM, Hamilton HJ (2020a) High-utility interval-based sequences. In: International Conference on big data analytics and knowledge discovery, Springer, pp 107–121, https://doi.org/10.1007/978-3-030-59065-9_9

Mirbagheri SM, Hamilton HJ (2020b) Similarity matching of temporal event-interval sequences. In: Canadian conference on artificial intelligence, Springer, pp 420–425, https://doi.org/10.1007/978-3-030-47358-7_43

Mirbagheri SM, Hamilton HJ (2021) Mining high utility patterns in interval-based event sequences. Data Knowl Eng 135(101):924. https://doi.org/10.1016/j.datak.2021.101924CrossRef

Mörchen F, Fradkin D (2010) Robust mining of time intervals with semi-interval partial order patterns. In: Proceedings of the 2010 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp 315–326, https://doi.org/10.1137/1.9781611972801.28

Mörchen F, Ultsch A (2005) Optimizing time series discretization for knowledge discovery. In: Proceedings of the Eleventh ACM SIGKDD international conference on knowledge discovery in data mining. Association for Computing Machinery, New York, NY, USA, KDD ’05, pp 660–665, https://doi.org/10.1145/1081870.1081953

Mordvanyuk N, López B, Bifet A (2021) verttirp: Robust and efficient vertical frequent time interval-related pattern mining. Expert Syst Appl 168(114):276. https://doi.org/10.1016/j.eswa.2020.114276CrossRef

Mordvanyuk N, López B, Bifet A (2022) Ta4l: efficient temporal abstraction of multivariate time series. Knowl-Based Syst 244(108):554. https://doi.org/10.1016/j.knosys.2022.108554CrossRef

Moskovitch R (2022) Multivariate time series mining. Wiley’s Data Mining and Knowledge Discovery

Moskovitch R, Shahar Y (2015a) Classification-driven temporal discretization of multivariate time series. Data Min Knowl Disc 29(4):871–913. https://doi.org/10.1007/s10618-014-0380-zMathSciNetCrossRef

Moskovitch R, Shahar Y (2015b) Classification of multivariate time series via temporal abstraction and time intervals mining. Knowl Inf Syst 45(1):35–74. https://doi.org/10.1007/s10115-014-0784-5CrossRef

Moskovitch R, Shahar Y (2015) Fast time intervals mining using the transitivity of temporal relations. Knowl Inf Syst 42(1):21–48. https://doi.org/10.1007/s10115-013-0707-xCrossRef

Moskovitch R, Peek N, Shahar Y (2009) Classification of ICU patients via temporal abstraction and temporal patterns mining. Notes of the intelligent data analysis in medicine and pharmacology (IDAMAP 2009) Workshop. American Medical Informatics Association, Verona, Italy, pp 35–40

Moskovitch R, Walsh C, Wang F, et al (2015) Outcomes prediction via time intervals related patterns. In: 2015 IEEE international conference on data mining. IEEE Computer Society, Washington, DC, USA, pp 919–924, https://doi.org/10.1109/ICDM.2015.143

Novitski P, Cohen CM, Karasik A, et al (2020) All-cause mortality prediction in t2d patients. In: International conference on artificial intelligence in medicine. Springer, Berlin, pp 3–13, https://doi.org/10.1007/978-3-030-59137-3_1

Papapetrou P, Kollios G, Sclaroff S et al (2009) Mining frequent arrangements of temporal intervals. Knowl Inf Syst 21(2):133. https://doi.org/10.1007/s10115-009-0196-0CrossRef

Patel D, Hsu W, Lee ML (2008) Mining relationships among interval-based events for classification. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data. Association for Computing Machinery, New York, NY, USA, SIGMOD ’08, pp 393–404, https://doi.org/10.1145/1376616.1376658

Pei J, Han J, Mortazavi-Asl B, et al (2000) Mining access patterns efficiently from web logs. In: Pacific-Asia conference on knowledge discovery and data mining. Springer, Berlin, pp 396–407, https://doi.org/10.1007/3-540-45571-X_47

Rebane J, Karlsson I, Bornemann L et al (2021) Smile: a feature-based temporal abstraction framework for event-interval sequence classification. Data Min Knowl Disc 35(1):372–399. https://doi.org/10.1007/s10618-020-00719-3MathSciNetCrossRef

Sacchi L, Larizza C, Combi C et al (2007) Data mining with temporal abstractions: Learning rules from time series. Data Min Knowl Disc 15(2):217–247. https://doi.org/10.1007/s10618-007-0077-7MathSciNetCrossRef

Shahar Y (1997) A framework for knowledge-based temporal abstraction. Artif Intell 90(1–2):79–133. https://doi.org/10.1016/S0004-3702(96)00025-2CrossRefMATH

Sharma AK, Patel D (2018) Stipa: A memory efficient technique for interval pattern discovery. In: 2018 IEEE International conference on big data (Big Data). IEEE Computer Society, Washington, DC, USA, pp 1767–1776, https://doi.org/10.1109/BigData.2018.8622421

Shknevsky A, Shahar Y, Moskovitch R (2021) The semantic adjacency criterion in time intervals mining. arXiv preprint arXiv:2101.03842

Srikant R, Agrawal R (1996) Mining sequential patterns: Generalizations and performance improvements. In: International conference on extending database technology. Springer, Berlin, pp 1–17, https://doi.org/10.1007/BFb0014140

Tzvetkov P, Yan X, Han J (2005) Tsp: mining top-k closed sequential patterns. Knowl Inf Syst 7(4):438–457. https://doi.org/10.1007/s10115-004-0175-4CrossRef

Villafane R, Hua KA, Tran D et al (2000) Knowledge discovery from series of interval events. J Intell Inf Syst 15(1):71–89. https://doi.org/10.1023/A:1008781812242CrossRef

Wang J, Han J (2004) Bide: Efficient mining of frequent closed sequences. In: Proceedings. 20th international conference on data engineering. IEEE Computer Society, Washington, DC, USA, pp 79–90, https://doi.org/10.1109/ICDE.2004.1319986

Winarko E, Roddick JF (2007) Armada: an algorithm for discovering richer relative temporal association rules from interval-based data. Data Knowl Eng 63(1):76–90. https://doi.org/10.1016/j.datak.2006.10.009CrossRef

Wu SY, Chen YL (2007) Mining nonambiguous temporal patterns for interval-based events. IEEE Trans Knowl Data Eng 19(6):742–758. https://doi.org/10.1109/TKDE.2007.190613CrossRef

Yan X, Han J, Afshar R (2003) Clospan: mining: closed sequential patterns in large datasets. In: Proceedings of the 2003 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp 166–177, https://doi.org/10.1137/1.9781611972733.15

Yang CW, Jaysawal BP, Huang JW (2017) Subsequence search considering duration and relations of events in time interval-based events sequences. In: 2017 IEEE International conference on data science and advanced analytics (DSAA), IEEE, pp 293–302, https://doi.org/10.1109/DSAA.2017.47

Yang Z, Wang Y, Kitsuregawa M (2007) Lapin: effective sequential pattern mining algorithms by last position induction for dense databases. In: International conference on database systems for advanced applications. Springer, Berlin, pp 1020–1023, https://doi.org/10.1007/978-3-540-71703-4_95

Zaki MJ (2001) Spade: an efficient algorithm for mining frequent sequences. Mach Learn 42(1–2):31–60. https://doi.org/10.1023/A:1007652502315CrossRefMATH

Zhang J, Wang Y, Yang D (2015) Ccspan: mining closed contiguous sequential patterns. Knowl-Based Syst 89:1–13. https://doi.org/10.1016/j.knosys.2015.06.014CrossRef

Zhao Q, Bhowmick SS (2003) Sequential pattern mining: a survey. ITechnical Report CAIS Nayang Technological University Singapore 1(26):135

Titel: TIRPClo: efficient and complete mining of time intervals-related patterns
verfasst von: Omer Harel
Robert Moskovitch
Publikationsdatum: 30.06.2023
Verlag: Springer US
Erschienen in: Data Mining and Knowledge Discovery / Ausgabe 5/2023
Print ISSN: 1384-5810
Elektronische ISSN: 1573-756X
DOI: https://doi.org/10.1007/s10618-023-00944-6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 5/2023

Enforcing fairness using ensemble of diverse Pareto-optimal models

Hydra: competing convolutional kernels for fast and accurate time series classification

Parameterizing the cost function of dynamic time warping with application to time series classification

Social norm bias: residual harms of fairness-aware algorithms

Knowledge graph embedding methods for entity alignment: experimental review

Fair detection of poisoning attacks in federated learning on non-i.i.d. data

Premium Partner