Extended vertical lists for temporal pattern mining from multivariate time series
Corresponding Author
Anton Kocheturov
Center for Applied Optimization, Industrial and Systems Engineering, University of Florida, Gainesville, Florida
Present Address: Anton Kocheturov, Corporate Technology, Siemens Corporation Princeton, NJ, USA.
Petar Momcilov, Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas
Correspondence
Anton Kocheturov, Corporate Technology, Siemens Corporation, Princeton, NJ, USA.
Email: [email protected]
Search for more papers by this authorPetar Momcilovic
Industrial and Systems Engineering, University of Florida, Gainesville, Florida
Present Address: Anton Kocheturov, Corporate Technology, Siemens Corporation Princeton, NJ, USA.
Petar Momcilov, Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas
Search for more papers by this authorAzra Bihorac
Division of Nephrology, Hypertension, and Renal Transplantation, University of Florida, Gainesville, Florida
Search for more papers by this authorPanos M. Pardalos
Center for Applied Optimization, Industrial and Systems Engineering, University of Florida, Gainesville, Florida
Search for more papers by this authorCorresponding Author
Anton Kocheturov
Center for Applied Optimization, Industrial and Systems Engineering, University of Florida, Gainesville, Florida
Present Address: Anton Kocheturov, Corporate Technology, Siemens Corporation Princeton, NJ, USA.
Petar Momcilov, Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas
Correspondence
Anton Kocheturov, Corporate Technology, Siemens Corporation, Princeton, NJ, USA.
Email: [email protected]
Search for more papers by this authorPetar Momcilovic
Industrial and Systems Engineering, University of Florida, Gainesville, Florida
Present Address: Anton Kocheturov, Corporate Technology, Siemens Corporation Princeton, NJ, USA.
Petar Momcilov, Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas
Search for more papers by this authorAzra Bihorac
Division of Nephrology, Hypertension, and Renal Transplantation, University of Florida, Gainesville, Florida
Search for more papers by this authorPanos M. Pardalos
Center for Applied Optimization, Industrial and Systems Engineering, University of Florida, Gainesville, Florida
Search for more papers by this authorAbstract
In this paper, the problem of mining complex temporal patterns in the context of multivariate time series is considered. A new method called the Fast Temporal Pattern Mining with Extended Vertical Lists is introduced. The method is based on an extension of the level-wise property, which requires a more complex pattern to start at positions within a record where all of the subpatterns of the pattern start. The approach is built around a novel data structure called the Extended Vertical List that tracks positions of the first state of the pattern inside records and links them to appropriate positions of a specific subpattern of the pattern called the prefix. Extensive computational results indicate that the new method performs significantly faster than the previous version of the algorithm for Temporal Pattern Mining; however, the increase in speed comes at the expense of increased memory usage.
CONFLICT OF INTEREST
The authors declare no potential conflict of interests.
REFERENCES
- Aggarwal, C. C., & Han, J. (2014). Frequent pattern mining: Springer International Publishing, 471.
- Aggarwal, C. C., Ta, N., Wang, J., Feng, J., & Zaki, M. (2007). Xproj: A framework for projected structural clustering of xml documents. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA, pp. 46–55.
- Agrawal, R., Imielinski, T., & Swami, A. (1993a). Database mining: A performance perspective. IEEE Transactions on Knowledge and Data Engineering, 5(6), 914–925.
- Agrawal, R., Imieliński, T., & Swami, A. (1993b). Mining association rules between sets of items in large databases. In ACM SIGMOD Record, 22, pp. 207–216.
- Allen, J. F. (1984). Towards a general theory of action and time. Artificial intelligence, 23(2), 123–154.
- Ayres, J., Flannick, J., Gehrke, J., & Yiu, T. (2002). Sequential pattern mining using a bitmap representation. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA, pp. 429–435.
- Batal, I., Cooper, G. F., Fradkin, D., Harrison, J. Jr., Moerchen, F., & Hauskrecht, M. (2016). An efficient pattern mining approach for event detection in multivariate temporal data. Knowledge and Information Systems, 46(1), 115–150.
- Batal, I., Fradkin, D., Harrison, J., Moerchen, F., & Hauskrecht, M. (2012). Mining recent temporal patterns for event detection in multivariate time series data. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Beijing, China, pp. 280–288.
- Batal, I., Valizadegan, H., Cooper, G. F., & Hauskrecht, M. (2011). A pattern mining approach for classifying multivariate temporal data. In 2011 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), Atlanta, Georgia, pp. 358–365.
- Chen, F., Deng, P., Wan, J., Zhang, D., Vasilakos, A. V., & Rong, X. (2015). Data mining for the internet of things: Literature review and challenges. International Journal of Distributed Sensor Networks, 11(8), 431047.
- Chen, Y., Keogh, E., Hu, B., Begum, N., Bagnall, A., Mueen, A., & Batista, G. (2015). The UCR time series classification archive. www.cs.ucr.edu/~eamonn/time_series_data/
- Deshpande, M., Kuramochi, M., Wale, N., & Karypis, G. (2005). Frequent substructure-based approaches for classifying chemical compounds. IEEE Transactions on Knowledge and Data Engineering, 17(8), 1036–1050.
- Hauskrecht, M., Visweswaran, S., Cooper, G. F., & Clermont, G. (2013). Data-driven identification of unusual clinical actions in the ICU. In Proceedings of the Annual Symposium of the American Medical Informatics Association, Washington, DC.
- Keogh, E., Chu, S., Hart, D., & Pazzani, M. (2004). Segmenting time series: A survey and novel approach. Data mining in time series databases, 57, 1–22.
10.1142/9789812565402_0001 Google Scholar
- Kocheturov, A., & Pardalos, P. (2018). Frequent temporal pattern mining with extended lists. In Trends in Biomathematics: Modeling, Optimization and Computational Problems, Cham: Springer, pp. 233–244.
- Korenkevych, D., Ozrazgat-Baslanti, T., Thottakkara, P., Hobson, C. E., Pardalos, P., Momcilovic, P., & Bihorac, A. (2016). The pattern of longitudinal change in serum creatinine and 90-day mortality after major surgery. Annals of surgery, 263(6), 1219–1227.
- Kuramochi, M., & Karypis, G. (2001). Frequent subgraph discovery. In ICDM 2001, Proceedings IEEE International Conference on Data Mining, 2001, IEEE, San Jose, CA, USA, USA, pp. 313–320.
- Lee, G., & Yun, U. (2017). A new efficient approach for mining uncertain frequent patterns using minimum data structure without false positives. Future Generation Computer Systems, 68, 89–110.
- Moerchen, F. (2006). Algorithms for time series knowledge mining. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA: ACM, pp. 668–673.
- Moore, G. E. (1975). Progress in digital integrated electronics. Electron Devices Meeting, 21, 11–13.
- Moskovitch, R., & Shahar, Y. (2015). Classification of multivariate time series via temporal abstraction and time intervals mining. Knowledge and Information Systems, 45(1), 35–74.
- Papapetrou, P., Kollios, G., Sclaroff, S., & Gunopulos, D. (2009). Mining frequent arrangements of temporal intervals. Knowledge and Information Systems, 21(2), 133.
- Patel, D., Hsu, W., & Lee, M. L. (2008). Mining relationships among interval-based events for classification. In Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, New York, NY, USA: ACM, pp. 393–404.
- Seeja, K., & Zareapoor, M. (2014). Fraudminer: A novel credit card fraud detection model based on frequent itemset mining. The Scientific World Journal, 2014, Article ID 252797, 10 pages.
- Srivastava, J., Cooley, R., Deshpande, M., & Tan, P.-N. (2000). Web usage mining: Discovery and applications of usage patterns from web data. Acm SIGKDD Explorations Newsletter, 1(2), 12–23.
10.1145/846183.846188 Google Scholar
- Thottakkara, P., Ozrazgat-Baslanti, T., Hupf, B. B., Rashidi, P., Pardalos, P., Momcilovic, P., & Bihorac, A. (2016). Application of machine learning techniques to high-dimensional clinical data to forecast postoperative complications. PloS one, 11(5), e0155705.
- Tiple, P., Cavique, L., & Cavalheiro Marques, N. (2017). Ramex-forum: A tool for displaying and analyzing complex sequential patterns of financial products. Expert Systems, 34(1), e12174.
- Tong, Y., Chen, L., Cheng, Y., & Yu, P. S. (2012). Mining frequent itemsets over uncertain databases. Proceedings of the VLDB Endowment, 5(11), 1650–1661.
10.14778/2350229.2350277 Google Scholar
- Tsai, C.-W., Lai, C.-F., Chiang, M.-C., & Yang, L. T. (2014). Data mining for internet of things: A survey. IEEE Communications Surveys and Tutorials, 16(1), 77–97.
- Winarko, E., & Roddick, J. F. (2007). Armada—An algorithm for discovering richer relative temporal association rules from interval-based data. Data & Knowledge Engineering, 63(1), 76–90.
- Wu, S.-Y., & Chen, Y.-L. (2007). Mining nonambiguous temporal patterns for interval-based events. IEEE Transactions on Knowledge & Data Engineering, 6, 742–758.
- Yun, U., Lee, G., & Lee, K.-M. (2016). Efficient representative pattern mining based on weight and maximality conditions. Expert Systems, 33(5), 439–462.
- Zaki, M. J. (2000). Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3), 372–390.
- Zaki, M. J. (2001). Spade: An efficient algorithm for mining frequent sequences. Machine learning, 42(1), 31–60.
- Zaki, M. J. (2005). Efficiently mining frequent trees in a forest: Algorithms and applications. IEEE Transactions on Knowledge and data Engineering, 17(8), 1021–1035.
