PHÁT HIỆN MOTIF BẰNG THUẬT TOÁN SCRIMP++ CẢI TIẾN
Tóm tắt
Motif trên chuỗi thời gian là cặp chuỗi con giống nhau nhất trong một chuỗi thời gian hay các cặp chuỗi giống nhau nhất trong một cơ sở dữ liệu chuỗi thời gian. Khám phá motif trên chuỗi thời gian là bài toán quan trọng trong khai phá dữ liệu chuỗi thời gian. Gần đây, một số thuật toán mới đã được giới thiệu cho bài toán khám phá motif dựa vào vector chứa khoảng cách giữa một chuỗi con với lân cận gần nhất của nó. Các thuật toán này sử dụng kĩ thuật kết hợp việc chuẩn hóa chuỗi thời gian vào trong công thức tính độ đo khoảng cách Euclid khi tính toán ma trận khoảng cách. Phương pháp tiêu biểu cho cách tiếp cận này là thuật toán Scrimp++. Bài báo này giới thiệu một phiên bản cải tiến của thuật toán Scrimp++ cho bài toán khám phá motif nhằm cải thiện thời gian thực thi của thuật toán. Kết quả thực nghiệm cho thấy thuật toán đề xuất thực hiện tốt hơn thuật toán gốc về mặt thời gian nhưng vẫn đảm bảo về độ chính xác.
Từ khóa
Toàn văn:
PDFTrích dẫn
Cao, D. T., & Duong, T. A. (2015). An efficient method for motif and anomaly detection in time series based on clustering. International Journal of Business Intelligence and Data Mining, 10, 356-377.
Castro, N., & Azevedo, P. (2010). Multiresolution Motif Discovery in Time Series. the SIAM International Conference on Data Mining (SDM 2010), (pp. 665-676). Columbus, Ohio, USA.
Chiu, B., Keogh, E.,& Lonardi, S. (2003). Probabilistic discovery of time series motifs. the 9th International Conference on Knowledge Discovery and Data mining (KDD'03),
(pp. 493-498).
Ferreira, P., Azevedo, P., Silva, C., & Brito, R. (2006). Mining approximate motifs in time series. the 9th Int. Conf. on Discovery Science, (pp. 89-101).
Lin, J., Keogh, E., Lonardi, S., & Patel, P. (2002). Finding motifs in time series. Proc. of 2nd Workshop on Temporal Data Mining (KDD’02).
Lin, Y., McCool, M. D., & Ghorbani, A. A. (2010). Motif and anomaly discovery of time series based on subseries join. IAENG International Conference on Data Mining and Applications, ICDMA.
Mohammad, Y., & Nishida, T. (2014). Exact Discovery of Length-Range Motifs. series Lecture Notes in Computer Science, 8398, 23-32.
Mueen, A., Keogh, E., Zhu, Q., & Cash, S. (2009). Exact Discovery of Time Series Motifs. Proc. of SIAM Int. on Data Mining, 473-484.
Nguyen. T. S., & Duong, T. A. (2016). Discovery of time series k-motifs based on multidimensional index. Knowledge and Information Systems, 46(1), 59-86.
Pariwatthanasak, K., & Ratanamahatana, C. A. (2019). Time Series Motif Discovery Using Approximated Matrix Profile. In S. S. Yang XS. (Ed.), Third International Congress on Information and Communication Technology, 797. Springer, Singapore.
Rakthanmanon, T., Campana, B. J. L., Mueen, A., Batista, G., Westover, M. B., Zhu, Q., J., Zakaria, & Keogh, E. J. (2013). Addressing Big Data Time Series: Mining trillions of time series subsequences under dynamic time warping. TKDD 7.3 (2013), 10.
Yankov, D., Keogh, E., Medina, J., Chiu, B., & Zordan, V. (2007). Detecting Motifs Under Uniform Scaling. the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (pp. 844-853).
Yeh, C. M., Zhu, Y., Ulanova, L., Begum, N., Ding, Y., Dau, H. A., & Silva, D. F. (2016). Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets. 2016 IEEE 16th International Conference on Data Mining (ICDM), (pp. 1317-1322).
Zhu Y., Yeh, C.-C. M., Zimmerman, Z., Kamgar, K., & Keogh, E. (2018). Matrix Profile XI: SCRIMP++: Time Series Motif Discovery at Interactive. ICDM.
Zhu, Y., Zimmerman Z., Senobari, N. S., Yeh, C.C. M., Funning, G., Mueen, A., Brisk, P., & Keogh, E. (2016). Matrix profile II: Exloiting a Novel Algorithm and CPUs yo break he one Hunded Milion Barries for Time Series motifs and joins. ICDM.
DOI: https://doi.org/10.54607/hcmue.js.19.3.3280(2022)
Tình trạng
- Danh sách trống