MỞ ĐẦU 1.0 Giới thiệu về motif chuỗi thời gian Dữ liệu chuỗi thời gian được ứng dụng rất phổ biến ở rất nhiều lĩnh vực như khoa học kỹ thuật, kinh tế tài chính, môi trường trong thời kỳ 4. Trong những ứng dụng này, việc phát hiện motif hay còn gọi là phát hiện mẫu lặp trong dữ liệu chuỗi thời gian là công việc cần thiết để phục vụ các công việc cao hơn trong việc khai phá dữ liệu như gom cụm, phân lớp, khai phá luật kết hợp v. Phát hiện motif chính là tìm chuỗi con trong dữ liệu chuỗi thời gian sao cho nó tương đồng với nhau về hình dạng cũng như kích thước. Thuật toán phát hiện motif thực ra nó là sự cải tiến của các thuật toán tìm kiếm chuỗi con truy vấn xem nó có xuất hiện trong dữ liệu chuỗi thời gian? Có rất nhiều thuật toán phát hiện motif được đề xuất, nhưng mô hình của những thuật toán tối ưu gồm các thuật toán sau MK, MOEN, MASS (Mueen’s Algorithm for Similarity Search) và thuật toán HIME (Hierarchical based Motif Enumeration) dựa vào các tiền đề chung là phương pháp thu giảm số chiều và các cấu trúc chỉ mục không gian đa chiều.
Hiển nhiên, độ phức tạp của phương pháp phát hiện motif chính xác theo kiểu BruteForce là bậc hai theo chiều dài của chuỗi thời gian mà từ đó các motif được phát hiện hay các chuỗi con truy vấn được tìm thấy trong dữ liệu chuỗi thời gian và tiêu biểu là thuật toán MK của Mueen Keogh [1].Tuy nhiên, ở thuật toán này chuỗi truy vấn hay motif có chiều dài bằng với dữ liệu chuỗi thời gian. Vì lý do đó, có nhiều thuật toán phát hiện motif xấp xỉ được giới thiệu và ứng dụng rất nhiều trong thực tế, nó rất cần thiết để phục vụ công việc khai phá dữ liệu cao cấp hơn như gom cụm, phân lớp, khai phá luật kết hợp v. Với cách tiếp cận này thường có độ phức tạp tính toán là O(n) hay O(nlogn), với n là số chuỗi trong cơ sở dữ liệu chuỗi thời gian hay chiều dài của chuỗi thời gian mà từ đó các chuỗi con hay motif được rút trích ra. Độ phức tạp của các giải thuật này giảm hơn nhiều lần so với phương pháp phát hiện motif chính xác.
Tuy nhiên, các thuật toán này yêu cầu nhiều tham số cần phải xác định trước, làm cho việc tính toán lớn và không mềm dẻo với khối lượng dữ liệu chuỗi thời gian lớn với các chuỗi truy vấn có chiều dài thay đổi tiêu biểu là thuật toán MOEN [2] của ông Mueen đề xuất năm 2014. 13 Luan van Một số thuật toán phát hiện motif xấp xỉ gần đây được đề xuất bằng cách chuẩn hóa dữ liệu đầu vào, dùng các phương pháp thu giảm số chiều của dữ liệu chuỗi thời gian, rút trích các đặc trưng như phương pháp biến đổi về miền tần số (FFT – Fast Fourier Transform), phương pháp rời rạc hóa (DWT – Discrete Wavelet Transform), phương pháp xấp xỉ gộp từng đoạn (PAA – Piecewise Aggregate Approximation) và phương pháp ký hiệu hóa dữ liệu (SAX – Symbolic Aggregate Approximation) v. sau đó sử dụng phép đo khoảng cách Euclide để gom cụm các chuỗi con có độ tương đồng từ đó tìm ra motif có khoảng cách tốt nhất. Trong số các thuật toán đã được đề xuất, thuật toán phát hiện motif chuỗi thời gian với chiều dài motif thay đổi do ông Abdullah Mueen và đồng sự giới thiệu trong [2] gọi là thuật toán MOEN.
Thuật toán này có thể phát hiện motif trong thời gian tuyến tính. Đây là thuật toán được trích dẫn nhiều và là cơ sở cho nhiều cách tiếp cận hiện nay trong việc giải bài toán phát hiện motif trên dữ liệu chuỗi thời gian phục vụ cho việc khai phá dữ liệu. Tuy nhiên, các kỹ thuật xử lý chuỗi chưa thật sự hữu hiệu khi cập nhật việc đo khoảng cách dễ dẫn đến việc sai khi phân cụm chuỗi con, vẫn sử dụng thuật toán BruteForce đã được tối ưu bằng cách bỏ qua việc chuẩn hóa dữ liệu cho mỗi vòng lặp hay sử dụng phương pháp từ bỏ sớm phục vụ cho thuật toán của mình nên phức tạp của thuật toán vẫn là bậc hai tuy nhiên nhanh gấp 2 lần so với thuật toán MK. Ngoài ra, để cải thiện thuật toán MOEN nhanh hơn năm 2015 ông đề xuất một thuật toán MASS bằng cách biến đổi dữ liệu đã được chuẩn hóa trước đó về miền tần số áp dụng Fast Fourier Tranform và cho kết quả chính xác và nhanh hơn rất nhiều lần so với thuật toán MOEN được giới thiệu năm 2014.
Bên cạnh đó, nhóm Yifeng Gao, Jessica Lin đã dựa vào các thuật toán của Mueen đưa ra một thuật toán phát hiện motif mang tên HIME [11] bằng phép biến đổi rời rạc hóa và phương pháp xấp xỉ gộp ký hiệu hóa áp dụng cho thuật toán của họ. Với thuật toán này việc xử lý dữ liệu chuỗi thời gian lớn nhanh hơn gấp 25 lần so với thuật toán Bruteforce và gấp 4 lần so với thuật toán MASS mà ông Abdullah Mueen đề xuất và cho kết quả chính xác như các thuật toán trên.1 Tổng quan về chuỗi thời gian và bài toán phát hiện motif trên dữ liệu chuỗi thời gian.1 Tổng quan về chuỗi thời gian. Một chuỗi thời gian (time series) là một chuỗi các điểm dữ liệu đo đạc được theo từng khoảng thời gian liền nhau theo một tần suất thời gian thống nhất.1 minh họa một ví dụ về chuỗi thời gian biểu diễn giá cổ phiếu của FPT (đơn vị VNĐ) từ tháng 01/2019 đến tháng 11/2019.1 Đường biểu diễn một chuỗi thời gian. Dữ liệu chuỗi thời gian được sử dụng phổ biến trong nhiều ứng dụng thực tế, từ các lĩnh vực khoa học kỹ thuật cho đến kinh tế, tài chính, môi trường, thời tiết, địa lý và y học.
Trong những ứng dụng này, việc phát hiện các chuỗi motif có xuất hiện trong cơ sở dữ liệu chuỗi thời gian là một công việc rất cần thiết. Mặc dù có nhiều cách tiếp cận khác nhau đã được đề xuất, các thuật toán trước đây thì thường phát hiện motif cho một chiều dài nhất định như thuật toán MK sử dụng thuật toán BruteForce được cải tiến. Tuy nhiên, những năm gần đây các thuật toán phát hiện motif với mọi chiều dài chuỗi con cũng đã được đề xuất như thuật toán MOEN, MASS, HIME v.với kết quả rất ấn tượng Những khó khăn và thách thức khi nghiên cứu về cơ sở dữ liệu chuỗi thời gian: 15 Luan van Dữ liệu thường rất lớn. Chẳng hạn, trong 1 giờ, dữ liệu điện tâm đồ (ECG) [5] có thể lên đến hàng GB dữ liệu.
Phụ thuộc nhiều vào yếu tố chủ quan của người dùng và tập dữ liệu khi đánh giá mức độ tương tự giữa các cơ sở dữ liệu chuỗi thời gian. Dữ liệu không đồng nhất: định dạng của dữ liệu khác nhau, tần số lấy mẫu khác nhau. Ngoài ra, dữ liệu có thể bị nhiễu, thiếu một vài giá trị. Do giới hạn về bộ nhớ máy tính và thời gian thực hiện, việc phân tích đúng trên các tập dữ liệu chuỗi thời gian rất lớn là điều không thể.
Vì vậy, một trong những vấn đề trọng tâm của việc khai phá dữ liệu chuỗi thời gian là làm sao để thu giảm số chiều của chuỗi dữ liệu thời gian nhưng vẫn giữ được các tính chất đặc trưng của chúng. Bài toán phát hiện motif trong cơ sở dữ liệu chuỗi thời gian đã được nhiều nhà nghiên cứu quan tâm trong những năm qua vì đây là bài toán cơ bản và là một thành phần nền tảng của nhiều bài toán khác trong khai phá dữ liệu chuỗi thời gian. Đây là bài toán khó vì kích thước dữ liệu chuỗi thời gian thường lớn và vì chúng ta không thể lập chỉ mục dữ liệu chuỗi thời gian một cách dễ dàng như trong hệ thống cơ sở dữ liệu truyền thống. Một vài thí dụ về ứng dụng của phát hiện motif trên chuỗi thời gian có thể nêu ra như sau: Quản lý làm mát trung tâm dữ liệu của HPE tại Virginia Hoa Kỳ [3].
Phân tích sự vận động của côn trùng tìm ra các biến đổi gens [2]. Dự đoán về giới tính trong sinh lý học, phân tích điện não đồ chứng động kinh trên người [9]. Xác định những chứng khoán có giá biến động theo một kiểu cách giống nhau theo chu kỳ.2 Bài toán phát hiện motif trên dữ liệu chuỗi thời gian. Phát hiện motif chính là tìm chuỗi con trong dữ liệu chuỗi thời gian sao cho nó tương đồng với nhau về hình dạng cũng như kích thước.
Thời gian qua, đã và đang có nhiều quan tâm của các nhà nghiên cứu về bài toán phát hiện motif trong cơ sở dữ liệu chuỗi thời gian. Bài toán này là một thành phần quan trọng trong nhiều ứng dụng khai phá dữ liệu. Faloutsos (1994) [8] đưa ra những tính chất mà một phương pháp phát hiện motif (hay tìm chuỗi con) trong dữ liệu chuỗi thời gian nên có: Nó nên nhanh hơn việc quét tuần tự. Tổng phí về không gian nhỏ.
16 Luan van Cho phép các câu truy vấn có chiều dài khác nhau. Cho phép thực hiện các thao tác chèn và xóa mà không phải xây dựng lại chỉ mục. Không xảy ra lỗi tìm sót (false dismissals). Để đạt hiệu quả cao, số lỗi tìm sai (false alarms) cũng nên thấp.
Vì vậy, để việc phát hiện motif hữu hiệu trên không gian đặc trưng, một phương pháp thu giảm số chiều nên được kết hợp với một cấu trúc chỉ mục đa chiều nào đó. Bài toán phát hiện motif trên dữ liệu chuỗi thời gian được phân làm hai loại: phát hiện motif với chiều dài chuỗi truy vấn cố định hay motif chính xác(exact motif) và phát hiện motif với mọi chiều dài của chuỗi truy vấn hay motif xấp xỉ (approximate motif). Trong trường hợp phát hiện motif với chiều dài chuỗi truy vấn cố định hay motif chính xác: Sau khi các chuỗi thời gian trong cơ sở dữ liệu và chuỗi truy vấn được biến đổi vào không gian đặc trưng bằng một phương pháp thu giảm số chiều nào đó, quá trình tìm kiếm sẽ được thực hiện trong không gian đặc trưng dựa vào một cấu trúc chỉ mục đa chiều. Các motif với chuỗi truy vấn được tìm thấy trong không gian đặc trưng sẽ được hậu kiểm trong không gian gốc để loại bỏ những chuỗi tìm sai.
Trong trường hợp này, các chuỗi truy vấn hay motif và chuỗi thời gian được giả định là có chiều dài bằng nhau và được giới thiệu đó là thuật toán MK [1].