Luận văn: Phát hiện motif trên time series dựa vào giải thuật của Mueen

Luận văn thạc sĩ nghiên cứu phát hiện motif trên chuỗi thời gian time series dựa vào giải thuật của Mueen, phân tích cấu trúc dữ liệu và thực nghiệm chi tiết.

• Tác giả: Lưu Hải Nam
• Người hướng dẫn: TS. Nguyễn Thành Sơn
• Trường học: Trường Đại học Sư phạm Kỹ thuật Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phát hiện motif trên time series dựa vào giải thuật của Mueen
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Thành phố Hồ Chí Minh

Tóm tắt

I. Tổng quan luận văn phát hiện motif trên time series

Luận văn thạc sĩ nghiên cứu bài toán phát hiện motif trên time series dựa vào giải thuật của Mueen. Tác giả Lưu Hải Nam thực hiện đề tài dưới sự hướng dẫn của TS. Nguyễn Thành Sơn tại Trường Đại học Sư phạm Kỹ thuật TP.HCM. Motif là các mẫu con lặp lại trong chuỗi thời gian. Việc phát hiện motif đóng vai trò nền tảng trong khai thác dữ liệu chuỗi thời gian. Dữ liệu chuỗi thời gian xuất hiện rộng rãi trong y học, tài chính, kỹ thuật. Kích thước dữ liệu thường rất lớn. Việc tìm mẫu lặp bằng phương pháp thủ công không khả thi. Thuật toán của Mueen giải quyết vấn đề này bằng cách tăng tốc độ tính toán. Luận văn trình bày cơ sở lý thuyết, các công trình liên quan, và các thuật toán MK, MOEN, HIME. Cấu trúc luận văn gồm bốn chương chính. Chương một trình bày lý thuyết nền. Chương hai mô tả các thuật toán phát hiện motif. Chương ba trình bày kết quả thực nghiệm. Chương bốn đưa ra kết luận. Đề tài có giá trị ứng dụng thực tiễn cao trong lĩnh vực khoa học máy tính.

1.1. Khái niệm time series và motif

Time series là chuỗi trị số thực đo tại các thời điểm cách đều nhau. Motif là mẫu con xuất hiện lặp lại nhiều lần trong chuỗi. Phát hiện motif giúp tìm ra quy luật ẩn trong dữ liệu. Ứng dụng trải rộng từ tài chính đến y học. Ví dụ điển hình là các chỉ số chứng khoán biến động theo chu kỳ. Bài toán so trùng chuỗi con là nền tảng của khai thác dữ liệu chuỗi thời gian. Dữ liệu ngày càng lớn khiến việc tìm kiếm thủ công không còn khả thi. Các thuật toán tự động trở nên cần thiết. Nghiên cứu này tập trung vào giải thuật của Abdullah Mueen. Giải thuật này nổi bật nhờ tốc độ xử lý nhanh.

1.2. Mục tiêu và cấu trúc đề tài

Đề tài xây dựng và cài đặt thuật toán MOEN dựa trên phương pháp FFT. Đề tài cũng cài đặt thuật toán HIME dựa vào phương pháp SAX. Các thuật toán được so sánh bằng thực nghiệm trên nhiều tập dữ liệu. Luận văn chia làm bốn chương rõ ràng. Chương một trình bày cơ sở lý thuyết. Chương hai mô tả chi tiết các thuật toán. Chương ba trình bày kết quả thực nghiệm và demo. Chương bốn tổng kết các đóng góp. Cấu trúc này giúp người đọc dễ theo dõi logic nghiên cứu. Mục tiêu cuối cùng là đưa ra giải pháp phát hiện motif hiệu quả.

II. Vấn đề đặt ra trong phát hiện motif time series

Dữ liệu chuỗi thời gian trong thực tế thường có kích thước rất lớn. Việc so sánh từng cặp chuỗi con tốn nhiều thời gian tính toán. Phương pháp brute-force đòi hỏi số lần gọi hàm khoảng cách rất lớn. Độ phức tạp tăng theo bậc hai với chiều dài chuỗi. Điều này gây khó khăn khi xử lý dữ liệu thực tế quy mô lớn. Các thuật toán truyền thống làm việc trực tiếp trên dữ liệu thô. Cách tiếp cận này không tận dụng được các tính chất toán học của phép đo khoảng cách. Vấn đề đặt ra là làm sao giảm số lần tính toán mà vẫn đảm bảo độ chính xác. Cần một phương pháp có khả năng loại bỏ sớm các ứng viên không tiềm năng. Giải thuật của Mueen giải quyết vấn đề bằng cách khai thác tính đối xứng của khoảng cách Euclide. Giải thuật cũng áp dụng bất đẳng thức tam giác để xây dựng cận dưới. Nhờ đó, số phép tính khoảng cách thực tế giảm đáng kể. Đây là bước đột phá so với phương pháp truyền thống.

2.1. Hạn chế của phương pháp truyền thống

Phương pháp brute-force yêu cầu duyệt qua toàn bộ cặp chuỗi con có thể. Độ phức tạp tính toán tăng nhanh theo chiều dài chuỗi thời gian. Với dữ liệu lớn, thời gian xử lý trở nên không chấp nhận được. Phương pháp làm việc trực tiếp trên dữ liệu thô, không giảm chiều. Không có cơ chế loại bỏ sớm các ứng viên kém tiềm năng. Mỗi phép so sánh đều phải tính toán đầy đủ khoảng cách. Điều này lãng phí tài nguyên tính toán. Các hệ thống thực tế cần xử lý dữ liệu theo thời gian thực. Phương pháp cũ không đáp ứng được yêu cầu tốc độ. Cần cải tiến thuật toán để khắc phục hạn chế này.

2.2. Yêu cầu về hiệu năng và độ chính xác

Thuật toán mới cần đảm bảo cả tốc độ lẫn độ chính xác. Việc giảm số phép tính không được làm mất mẫu motif thực sự. Cận dưới của khoảng cách phải được tính toán chặt chẽ. Kỹ thuật từ bỏ sớm cần áp dụng đúng thời điểm. Dữ liệu đầu vào đa dạng đòi hỏi thuật toán tổng quát. Kết quả thực nghiệm cần so sánh trên nhiều tập dữ liệu khác nhau. Độ tin cậy của thuật toán quyết định giá trị ứng dụng. Yêu cầu này định hướng cho việc thiết kế giải thuật MK của Mueen và Keogh.

III. Giải thuật của Mueen phát hiện motif hiệu quả

Giải thuật MK của Mueen và Keogh áp dụng ba kỹ thuật tăng tốc chính. Kỹ thuật đầu tiên khai thác tính đối xứng của phép đo khoảng cách Euclide. Từ đó, thuật toán xây dựng hàm cận dưới Lower Bound. Kỹ thuật thứ hai khai thác bất đẳng thức tam giác và điểm tham chiếu trong không gian nhiều chiều. Nếu cận dưới lớn hơn giá trị tốt nhất hiện tại, ứng viên bị loại bỏ ngay. Kỹ thuật thứ ba áp dụng từ bỏ sớm trong quá trình liệt kê cặp motif. Nhờ vậy, thuật toán chọn ra cặp có vị trí và khoảng cách tốt nhất nhanh hơn nhiều. Đầu vào của thuật toán là chuỗi thời gian T có chiều dài n và chiều dài motif m. Đầu ra là cặp motif có khoảng cách tốt nhất thỏa điều kiện đầu vào. Song song với MK, luận văn cài đặt thêm thuật toán MOEN dựa trên FFT. Thuật toán HIME dựa trên phương pháp SAX cũng được xây dựng để so sánh. Các thuật toán được đánh giá bằng thực nghiệm trên tập dữ liệu thực tế.

3.1. Ba kỹ thuật tăng tốc trong thuật toán MK

Kỹ thuật đầu tiên là khai thác tính đối xứng của khoảng cách Euclide. Từ tính đối xứng này, thuật toán xây dựng hàm cận dưới hiệu quả. Kỹ thuật thứ hai sử dụng bất đẳng thức tam giác với điểm tham chiếu. Ba điểm P, Q, R trong không gian d chiều tạo ra cận dưới nhỏ hơn khoảng cách thực. Nếu cận dưới vượt giá trị tốt nhất hiện tại, ứng viên bị loại ngay lập tức. Kỹ thuật thứ ba là từ bỏ sớm trong quá trình duyệt. Ba kỹ thuật này kết hợp giúp giảm đáng kể số lần gọi hàm khoảng cách. Kết quả là tốc độ xử lý nhanh hơn nhiều so với brute-force.

3.2. Cài đặt và so sánh với MOEN HIME

Thuật toán MOEN được xây dựng dựa trên phương pháp biến đổi Fourier nhanh FFT. Thuật toán HIME dựa vào phương pháp xấp xỉ SAX để giảm chiều dữ liệu. Cả hai thuật toán được cài đặt song song với MK để so sánh hiệu năng. Thực nghiệm sử dụng các tập dữ liệu do tác giả và cộng sự cung cấp. Kết quả so sánh cho thấy sự khác biệt về tốc độ và độ chính xác giữa các thuật toán. Việc so sánh giúp xác định phương pháp phù hợp nhất cho từng loại dữ liệu. Đây là đóng góp thực nghiệm quan trọng của luận văn.

IV. Kết luận và ứng dụng phát hiện motif time series

Luận văn hoàn thành mục tiêu xây dựng và cài đặt các thuật toán phát hiện motif. Thuật toán MK dựa trên giải thuật của Mueen cho thấy hiệu quả vượt trội. Ba kỹ thuật tăng tốc giúp giảm đáng kể thời gian tính toán. Thuật toán MOEN và HIME được cài đặt để đối chiếu kết quả. Kết quả thực nghiệm khẳng định tính đúng đắn của các phương pháp được trình bày. Nghiên cứu góp phần làm rõ cơ sở lý thuyết về phát hiện motif trên chuỗi thời gian. Ứng dụng thực tế trải rộng trong nhiều lĩnh vực. Ngành tài chính có thể dùng để phát hiện chu kỳ biến động giá. Ngành y học có thể áp dụng để tìm mẫu bất thường trong tín hiệu sinh học. Ngành kỹ thuật có thể sử dụng để giám sát cảm biến theo thời gian thực. Luận văn mở ra hướng nghiên cứu tiếp theo về tối ưu hóa thuật toán. Các công trình tương lai có thể kết hợp học máy để nâng cao độ chính xác.

4.1. Đóng góp chính của luận văn

Luận văn cài đặt thành công ba thuật toán phát hiện motif khác nhau. Thuật toán MK dựa trên giải thuật của Mueen được triển khai đầy đủ. Thuật toán MOEN áp dụng phương pháp FFT để tăng tốc xử lý. Thuật toán HIME sử dụng phương pháp SAX để giảm chiều dữ liệu. Ba thuật toán được so sánh trên cùng tập dữ liệu thực nghiệm. Kết quả cho thấy sự khác biệt rõ rệt về hiệu năng. Đóng góp này giúp người đọc có cái nhìn tổng quan về các hướng tiếp cận. Đây là nền tảng cho các nghiên cứu tiếp theo trong lĩnh vực.

4.2. Hướng ứng dụng và phát triển tương lai

Kết quả nghiên cứu có thể ứng dụng trong phân tích dữ liệu tài chính. Ngành y học có thể khai thác để phát hiện bất thường trong tín hiệu điện tim. Ngành công nghiệp có thể dùng để giám sát cảm biến máy móc. Hướng phát triển tiếp theo tập trung vào tối ưu hóa tốc độ xử lý. Kết hợp học máy với thuật toán truyền thống là hướng đi tiềm năng. Nghiên cứu mở rộng có thể áp dụng cho dữ liệu đa chiều. Việc xử lý dữ liệu thời gian thực cũng là thách thức cần giải quyết.

Trích đoạn nội dung tài liệu

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 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  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  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].