Phát hiện MOTIF trên chuỗi thời gian bằng cấu trúc chỉ mục đa chiều
Email tác giả liên hệ:
sonnt@hcmute.edu.vnTừ khóa:
Chuỗi thời gian, Chỉ mục đa chiều, MotifTóm tắt
Motif trong cơ sở dữ liệu chuỗi thời gian là các chuỗi lặp lại nhiều lần trong cơ sở dữ liệu chuỗi thời gian hoặc các chuỗi con lặp lại trong một chuỗi thời gian dài hơn. Phát hiện motif trên chuỗi thời gian là một công việc quan trọng trong khai phá dữ liệu chuỗi thời gian. Trong bài báo này, chúng tôi đề xuất một phương pháp phát hiện motif trên chuỗi thời gian dựa vào một cấu trúc chỉ mục đa chiều sử dụng vùng bao hình chữ nhật nhỏ nhất. Phương pháp do chúng tôi đề xuất hiệu quả về mặt thời gian xử lý lẫn không gian lưu trữ vì chỉ cần lưu các vùng bao nhỏ nhất của các chuỗi thời gian trong bộ nhớ chính và chỉ cần quét qua một lần toàn bộ cơ sở dữ liệu chuỗi thời gian cùng với môt vài lần đọc dữ liệu gốc từ đĩa để thẩm định lại kết quả. Chúng tôi minh họa tính hiệu quả của phương pháp đề xuất bằng thựcnghiệm trên các tập dữ liệu thực thuộc các lĩnh vực khác nhau. Kết quả thực nghiệm cho thấy phương pháp đề xuất có thể phát hiện motif một cách hiệu quả hơn những phương pháp thông dụng, phương pháp chiếu ngẫu nhiên.
Tải xuống: 0
Tài liệu tham khảo
N. Beckmann, H. Kriegel, R. Schneider, B. Seeger, “The R*-tree: An efficient and robustaccess method for points and rectangles,” in Proc. of 1990 ACM SIGMOD Conf., AtlanticCity, NJ, 1990, pp. 322-331.
S. S. Cheung, and T. P. Nguyen, (2005). Mining Arbitrary-Length Repeated Patterns inTelevision Broadcast. ICIP (3) 2005: 181- 184.
B. Chiu, E. Keogh, and S. Lonardi, Probabilistic discovery of time series motifs, Proc. ofthe 9th International Conference on Knowledge Discovery and Data mining (KDD’03), pp.493–498, 2003.
N. Castro and P. Azevedo, “Multiresolution Motif Discovery in Time Series,” inProceedings of the SIAM International Conference on Data Mining (SDM 2010), Columbus,Ohio, USA, 2010, pp. 665-676.
F. Erich, G.Thiemo, N. Jiri, S. Bernhard, (2009). On-line motif detection in time serieswith SwiftMotif. In: Pattern Recognition 42(11):3015-3031. Elsevier.
P. Ferreira, P. Azevedo, C. Silva, and R. Brito, (2006). Mining approximate motifs in timeseries, in Proceedings of the 9th International Conference on Discovery Science, pp. 89-101.
A. Guttman, “R-trees: a Dynamic Index Structure for Spatial Searching,” in Proc. of theACM SIGMOD Int. Conf. on Management of Data, 1984, pp. 47-57.
J. Lin, E. Keogh, S. Lonardi, P. Patel, (2002). Finding motifs in time series. In: Proc. 2ndWorkshop on Temporal Data Mining. Edmonton, Alberta, Canada.
Li, Q., Lopez, I.F.V. and Moon, B.: Skyline Index for time series data, IEEE Trans. onKnowledge and Data Engineering, Vol. 16, No. 4 (2004)
D. Minnen, C. Isbell, I. Essa, and T. Starner, (2007). Detecting Subdimensional Motifs:An Effcient Algorithm for Generalized Multivariate Pattern Discovery, Seventh IEEEInternational Conference on Data Mining, pp 601-606.
A. Mueen, E. Keogh, Q. Zhu, S. Cash, and B. West-over, (2009). Exact Discovery ofTime Series Motifs, in the Proceedings of SIAM International Conference on Data Mining,pp. 473-484.
A. Metwally, D. Agrawal, A. El Abbadi , “Efficient Computation of Frequent and Top-kElements in Data Streams,” in Proceedings of the 10th International Conference on DatabaseTheory, 2005, pp. 398-412.
T. Oates (2002). PERUSE: An Unsupervised Algorithm for Finding Recurring Patternsin Time Series, Second IEEE International Conference on Data Mining, pp. 330.
J. Shieh and E. Keogh, “iSAX: indexing and mining terabyte sized time series,” inProceedings of the 14th ACM SIGKDD International Conference on Knowledge Discoveryand Data Mining, 2008, pp. 623-631.
Y. Tanaka, K. Iwamoto, and K. Uehara, Discovery of time-series motif from multidimensional data based on MDL principle, Machine Learning, 58(2-3):269–300, 2005.
L. Xie, (2005). Unsupervised Pattern Discovery for Multimedia Sequences. Ph.D.Thesis, Columbia University.
D. Yankov, E. Keogh, J. Medina, B. Chiu, and V. Zordan, (2007). Detecting MotifsUnder Uniform Scaling, in Proceedings of the 13th ACM SIGKDD International Conferenceon Knowledge Discovery and Data Mining, pp. 844-853.
Tải xuống
Đã Xuất bản
Cách trích dẫn
Giấy phép
Tác phẩm này được cấp phép theo Giấy phép quốc tế Creative Commons Attribution-NonCommercial 4.0 .
Bản quyền thuộc về JTE.
