Luận văn thạc sĩ khoa học máy tính tìm kiếm mô típ trên dữ liệu chuỗi thời gian với độ đo xoắn thời gian động dựa vào cấu trúc chỉ mục ts tree

Luận văn thạc sĩ về tìm kiếm mô típ trên dữ liệu chuỗi thời gian sử dụng độ đo xoắn thời gian động và cấu trúc chỉ mục TS-Tree. Nghiên cứu khoa học máy tính chuyên sâu.

• Tác giả: Ngô Thảo Chương
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Trường Đại Học Bách Khoa
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Tìm Kiếm Mô Típ Trên Dữ Liệu Chuỗi Thời Gian Với Độ Đo Xoắn Thời Gian Động Dựa Vào Cấu Trúc Chỉ Mục Ts-Tree
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2017
• Địa điểm: Tp. Hồ Chí Minh

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT LUẬN VĂN
• ABSTRACT
• LỜI CAM ĐOAN
• 1. CHƯƠNG I: GIỚI THIỆU ĐỀ TÀI
• 1.1. Giới thiệu đề tài
• 1.2. Mục tiêu của đề tài
• 1.3. Giới hạn của đề tài
• 1.4. Tóm lược những kết quả thu được
• 1.5. Cấu trúc luận văn
• 2. CHƯƠNG II: CƠ SỞ LÝ THUYẾT
• 2.1. Dữ liệu chuỗi thời gian
• 2.2. Độ đo xoắn thời gian động (Dynamic Time Warping - DTW)
• 2.2.1. Chặn dưới cho khoảng cách DTW
• 2.2.2. Mở rộng chặn dưới cho độ đo xoắn thời gian động với PAA
• 2.3. Ký hiệu hóa chuỗi thời gian
• 2.4. Giới thiệu bài toán tìm kiếm tương tự
• 2.5. Phát hiện motif trên dữ liệu chuỗi thời gian
• 2.5.1. Khái niệm motif dữ liệu chuỗi thời gian
• 2.5.2. Một số khái niệm liên quan đến motif
• 3. CHƯƠNG III: CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Giải thuật tìm kiếm chân phương (Brute Force)
• 3.2. Giải thuật chiếu ngẫu nhiên
• 3.3. Tổng quan về cây R*-Tree
• 3.4. Thao tác chèn thêm phần tử mới
• 3.5. Thao tác xóa phần tử
• 3.6. Cấu trúc chỉ mục TS-Tree
• 3.7. Các thành phần phân tách (Separators)
• 3.8. Sự rời rạc hóa
• 3.9. Thông tin mô tả trong cây TS-Tree
• 3.10. Các thao tác chèn phần tử trong cây TS-Tree
• 3.11. Thao tác xóa phần tử trong cây TS-Tree
• 3.12. Thao tác tìm kiếm trong TS-Tree
• 3.13. Cấu trúc chỉ mục TS-Tree làm việc với độ đo DTW
• 3.14. Tính khoảng cách tới MD (metadata) – MD Mindist
• 3.15. Khoảng cách ngắn nhất từ Q tới thành phần trong nút
• 4. CHƯƠNG IV: PHƯƠNG HƯỚNG GIẢI QUYẾT VẤN ĐỀ
• 4.1. Đề xuất giải thuật tìm kiếm Brute force trên cấu trúc chỉ mục TS-Tree
• 4.2. Mô hình thực hiện phương pháp
• 4.2.1. Tìm kiếm motif bằng phương pháp Brute Force
• 4.2.2. Tìm kiếm motif bằng phương pháp Brute Force trên cấu trúc chỉ mục TS-Tree
• 5. CHƯƠNG V: THỰC NGHIỆM
• 5.1. Thông tin về các bộ dữ liệu thực nghiệm
• 5.2. Thực nghiệm với các bộ dữ liệu nhỏ hơn 10
• 5.2.1. Dữ liệu Small Power Italia
• 5.2.2. Dữ liệu Small ECG (Điện tâm đồ)
• 5.2.3. Dữ liệu Small Power
• 5.2.4. Dữ liệu Small EEG (Điện não đồ)
• 5.2.5. Dữ liệu Memory
• 5.2.6. Dữ liệu TEK17
• 5.3. Thực nghiệm với các bộ dữ liệu lớn hơn 10
• 5.3.1. Dữ liệu Power
• 5.3.2. Dữ liệu ECG
• 5.3.3. Dữ liệu Power Italia
• 5.4. Bảng tổng kết và nhận xét các kết quả thực nghiệm
• 6. CHƯƠNG VI: KẾT LUẬN
• 6.1. Những đóng góp của đề tài
• 6.2. Hướng phát triển của đề tài
• DANH MỤC TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới Thiệu Chung Về Tìm Kiếm Motif Chuỗi Thời Gian

Trong kỷ nguyên số, dữ liệu chuỗi thời gian trở thành yếu tố then chốt trong nhiều lĩnh vực, từ khoa học kỹ thuật đến kinh tế và tài chính. Các bài toán khai phá dữ liệu chuỗi thời gian như gom cụm, phân lớp, dự báo ngày càng quan trọng. Để giải quyết những bài toán này, việc tìm kiếm motif hiệu quả trên dữ liệu chuỗi thời gian trở thành một bài toán cốt lõi. Hiện nay, nhiều cấu trúc chỉ mục như A-tree, M-tree, R*-tree, và TS-Tree đã được phát triển để tăng tốc quá trình truy xuất dữ liệu. Tuy nhiên, TS-Tree, kết hợp với độ đo Dynamic Time Warping (DTW), hứa hẹn mang lại hiệu quả cao hơn trong việc tìm kiếm motif chính xác và nhanh chóng. Đây là tiền đề cho các nghiên cứu về sau, nhằm cải tiến các thuật toán, nâng cao hiệu quả và độ chính xác.

1.1. Vai Trò Của Dữ Liệu Chuỗi Thời Gian Trong Ứng Dụng Thực Tế

Dữ liệu chuỗi thời gian đóng vai trò then chốt trong nhiều lĩnh vực, từ khoa học kỹ thuật đến kinh tế, tài chính, y học, và nhiều lĩnh vực khác. Việc thu thập và phân tích dữ liệu chuỗi thời gian cho phép chúng ta hiểu rõ hơn về các xu hướng, mô hình, và sự biến động của các hiện tượng theo thời gian. Các ứng dụng bao gồm dự báo giá cổ phiếu, phân tích lưu lượng truy cập web, theo dõi tình trạng sức khỏe bệnh nhân, và giám sát hiệu suất hệ thống. Phân tích chuỗi thời gian cho phép đưa ra quyết định thông minh hơn và tối ưu hóa hiệu quả hoạt động.

1.2. Bài Toán Tìm Kiếm Motif và Tầm Quan Trọng Trong Khai Phá Dữ Liệu

Tìm kiếm motif trong dữ liệu chuỗi thời gian là bài toán xác định các đoạn con (subsequence) tương tự nhau xuất hiện nhiều lần trong một chuỗi thời gian dài. Các motif này đại diện cho các mẫu (pattern) quan trọng hoặc hành vi lặp đi lặp lại. Tìm kiếm motif là một bước quan trọng trong khai phá dữ liệu chuỗi thời gian, giúp chúng ta khám phá ra các quy luật tiềm ẩn, phát hiện dị thường, và dự đoán các sự kiện trong tương lai. Việc tìm kiếm motif hiệu quả có thể giúp chúng ta hiểu rõ hơn về dữ liệu và đưa ra các quyết định thông minh hơn.

II. Thách Thức Khi Tìm Kiếm Motif Trên Chuỗi Thời Gian Lớn

Việc tìm kiếm motif trên dữ liệu chuỗi thời gian lớn đối mặt với nhiều thách thức đáng kể. Thứ nhất, khối lượng dữ liệu lớn đòi hỏi thuật toán có khả năng mở rộng cao để đảm bảo thời gian xử lý hợp lý. Thứ hai, dữ liệu chuỗi thời gian thường có độ nhiễu cao, đòi hỏi các phương pháp lọc và xử lý trước hiệu quả. Thứ ba, việc chọn độ đo khoảng cách phù hợp giữa các chuỗi con ảnh hưởng lớn đến chất lượng motif tìm được. Độ đo Euclid tuy đơn giản nhưng không hiệu quả với nhiều loại dữ liệu chuỗi thời gian. Việc lựa chọn cấu trúc chỉ mục phù hợp cũng là một yếu tố quan trọng. TS-Tree kết hợp với DTW được kỳ vọng sẽ giải quyết một số hạn chế này, nhưng việc tối ưu hóa hiệu suất vẫn là một thách thức.

2.1. Hạn Chế Của Độ Đo Euclid Trong Phân Tích Chuỗi Thời Gian

Độ đo Euclid là một trong những độ đo khoảng cách phổ biến nhất, nhưng nó có một số hạn chế khi áp dụng cho dữ liệu chuỗi thời gian. Thứ nhất, nó rất nhạy cảm với sự khác biệt về thời gian (time shifts) giữa các chuỗi. Thứ hai, nó không thể xử lý tốt các chuỗi có độ dài khác nhau. Thứ ba, nó không phù hợp với các loại dữ liệu chuỗi thời gian có biến động lớn hoặc có tính phi tuyến. Do đó, cần phải sử dụng các độ đo khoảng cách khác phù hợp hơn, chẳng hạn như DTW, để đảm bảo độ chính xác của việc tìm kiếm motif.

2.2. Yêu Cầu Về Khả Năng Mở Rộng Của Thuật Toán Cho Dữ Liệu Lớn

Khi làm việc với dữ liệu chuỗi thời gian lớn, khả năng mở rộng của thuật toán là một yếu tố quan trọng. Thuật toán cần phải có khả năng xử lý khối lượng dữ liệu lớn một cách hiệu quả và không tốn quá nhiều thời gian. Các thuật toán có độ phức tạp tính toán cao có thể trở nên không khả thi khi áp dụng cho dữ liệu lớn. Do đó, cần phải sử dụng các kỹ thuật tối ưu hóa và các cấu trúc dữ liệu phù hợp để cải thiện khả năng mở rộng của thuật toán. TS-Tree là một cấu trúc chỉ mục hứa hẹn có thể giúp tăng tốc quá trình tìm kiếm motif trên dữ liệu lớn.

2.3. Vấn Đề Xử Lý Nhiễu Trong Dữ Liệu Chuỗi Thời Gian Thực Tế

Dữ liệu chuỗi thời gian thực tế thường chứa nhiều nhiễu, có thể ảnh hưởng đến độ chính xác của việc tìm kiếm motif. Nhiễu có thể đến từ nhiều nguồn khác nhau, chẳng hạn như lỗi đo lường, sai sót trong quá trình thu thập dữ liệu, hoặc các yếu tố bên ngoài không liên quan. Do đó, cần phải sử dụng các phương pháp tiền xử lý dữ liệu để loại bỏ hoặc giảm thiểu ảnh hưởng của nhiễu. Các phương pháp phổ biến bao gồm lọc trung bình, lọc Kalman, và phân tích wavelet. Việc xử lý nhiễu hiệu quả có thể cải thiện đáng kể độ chính xác của việc tìm kiếm motif.

III. Giải Pháp TS Tree và Dynamic Time Warping DTW

Để vượt qua những thách thức trên, việc kết hợp cấu trúc chỉ mục TS-Tree với độ đo Dynamic Time Warping (DTW) được xem là một giải pháp đầy tiềm năng. TS-Tree giúp tổ chức và truy xuất dữ liệu chuỗi thời gian một cách hiệu quả, giảm thiểu số lượng phép so sánh cần thiết. Trong khi đó, DTW có khả năng xử lý tốt các biến dạng thời gian và độ dài khác nhau giữa các chuỗi con, từ đó nâng cao độ chính xác của việc tìm kiếm motif. Sự kết hợp này hứa hẹn mang lại hiệu quả cao hơn so với các phương pháp truyền thống sử dụng độ đo Euclid.

3.1. Cấu Trúc Chỉ Mục TS Tree Tổ Chức Dữ Liệu Chuỗi Thời Gian Hiệu Quả

TS-Tree là một cấu trúc chỉ mục được thiết kế đặc biệt để lưu trữ và truy xuất dữ liệu chuỗi thời gian một cách hiệu quả. Nó sử dụng một cấu trúc cây phân cấp để tổ chức dữ liệu, cho phép tìm kiếm nhanh chóng các đoạn con tương tự. Các nút trong cây TS-Tree chứa thông tin tóm tắt về các chuỗi con con, giúp giảm thiểu số lượng phép so sánh cần thiết. Ngoài ra, TS-Tree cũng hỗ trợ các thao tác chèn, xóa, và cập nhật dữ liệu một cách hiệu quả, làm cho nó trở thành một lựa chọn phù hợp cho các ứng dụng yêu cầu tính linh hoạt cao.

3.2. Dynamic Time Warping DTW Độ Đo Khoảng Cách Chống Biến Dạng Thời Gian

Dynamic Time Warping (DTW) là một độ đo khoảng cách mạnh mẽ có khả năng xử lý tốt các biến dạng thời gian và độ dài khác nhau giữa các chuỗi thời gian. Nó tìm kiếm một sự tương ứng tối ưu giữa các điểm dữ liệu trong hai chuỗi, cho phép chúng ta so sánh các chuỗi có hình dạng tương tự nhưng không hoàn toàn khớp về thời gian. DTW được sử dụng rộng rãi trong nhiều ứng dụng, chẳng hạn như nhận dạng giọng nói, phân tích tín hiệu điện tim (ECG), và tìm kiếm motif trong dữ liệu chuỗi thời gian. Tuy nhiên, DTW có độ phức tạp tính toán cao, do đó cần phải sử dụng các kỹ thuật tối ưu hóa để cải thiện hiệu suất.

3.3. Tối Ưu Hóa DTW với Chặn Dưới Để Tăng Tốc Tìm Kiếm Motif

Do độ phức tạp tính toán của DTW, việc sử dụng các chặn dưới (lower bounding techniques) là rất quan trọng để tăng tốc quá trình tìm kiếm motif. Các chặn dưới cho phép chúng ta loại bỏ các chuỗi con không tiềm năng một cách nhanh chóng, giảm thiểu số lượng tính toán DTW tốn kém. Một số chặn dưới phổ biến cho DTW bao gồm LB_Keogh, LB_Kim, và LB_Improved. Việc lựa chọn chặn dưới phù hợp có thể cải thiện đáng kể hiệu suất của việc tìm kiếm motif.

IV. Ứng Dụng TS Tree và DTW Trong Tìm Kiếm Motif Hiệu Quả

Việc kết hợp TS-Tree và DTW mang lại một phương pháp tìm kiếm motif mạnh mẽ và hiệu quả. TS-Tree cung cấp một cấu trúc chỉ mục hiệu quả để lưu trữ và truy xuất dữ liệu chuỗi thời gian, trong khi DTW đảm bảo độ chính xác cao trong việc so sánh các chuỗi con. Các nghiên cứu đã chỉ ra rằng phương pháp này có thể đạt được hiệu suất tốt hơn so với các phương pháp truyền thống sử dụng độ đo Euclid hoặc các cấu trúc chỉ mục khác. Tuy nhiên, việc tối ưu hóa các tham số của TS-Tree và DTW, cũng như lựa chọn chặn dưới phù hợp, là rất quan trọng để đạt được hiệu suất tối ưu.

4.1. Đề Xuất Giải Thuật Tìm Kiếm Motif Dựa Trên Cấu Trúc TS Tree và Độ Đo DTW

Một giải thuật tìm kiếm motif điển hình dựa trên TS-Tree và DTW bao gồm các bước sau: (1) Xây dựng cây TS-Tree từ dữ liệu chuỗi thời gian. (2) Duyệt cây TS-Tree để tìm kiếm các nút tiềm năng chứa motif. (3) Sử dụng DTW để so sánh các chuỗi con trong các nút tiềm năng. (4) Áp dụng các chặn dưới cho DTW để loại bỏ các chuỗi con không tiềm năng. (5) Trả về các motif tìm thấy cùng với độ tương tự của chúng. Việc tối ưu hóa các bước này có thể cải thiện đáng kể hiệu suất của giải thuật.

4.2. Kết Quả Thực Nghiệm So Sánh Với Các Phương Pháp Tìm Kiếm Motif Khác

Các kết quả thực nghiệm thường so sánh phương pháp TS-Tree và DTW với các phương pháp tìm kiếm motif khác, chẳng hạn như giải thuật tìm kiếm vét cạn (brute force), hoặc các phương pháp sử dụng độ đo Euclid và các cấu trúc chỉ mục khác. Các kết quả này thường cho thấy rằng phương pháp TS-Tree và DTW có thể đạt được độ chính xác tương đương hoặc cao hơn, đồng thời có thời gian thực hiện ngắn hơn đáng kể, đặc biệt là trên dữ liệu lớn. Tuy nhiên, kết quả có thể khác nhau tùy thuộc vào các tham số và bộ dữ liệu được sử dụng.

4.3. Ưu Điểm và Hạn Chế Của Phương Pháp Kết Hợp TS Tree và DTW

Phương pháp kết hợp TS-Tree và DTW có nhiều ưu điểm, bao gồm khả năng xử lý biến dạng thời gian, hiệu quả trên dữ liệu lớn, và độ chính xác cao. Tuy nhiên, nó cũng có một số hạn chế, chẳng hạn như độ phức tạp trong việc xây dựng và duy trì cây TS-Tree, và độ nhạy cảm với các tham số. Việc lựa chọn các tham số phù hợp và tối ưu hóa các bước của giải thuật là rất quan trọng để đạt được hiệu suất tối ưu.

V. Kết Luận và Hướng Phát Triển Cho Tìm Kiếm Motif Tương Lai

Trong bối cảnh dữ liệu chuỗi thời gian ngày càng trở nên phổ biến, việc tìm kiếm motif hiệu quả trở thành một bài toán quan trọng. Việc kết hợp TS-Tree và DTW là một hướng đi đầy hứa hẹn để giải quyết bài toán này. Các nghiên cứu trong tương lai có thể tập trung vào việc cải tiến cấu trúc TS-Tree, phát triển các chặn dưới DTW hiệu quả hơn, và khám phá các phương pháp kết hợp TS-Tree và DTW với các kỹ thuật học máy khác để tăng cường khả năng phát hiện motif trong dữ liệu chuỗi thời gian.

5.1. Tổng Kết Những Đóng Góp Quan Trọng Trong Nghiên Cứu Tìm Kiếm Motif

Nghiên cứu về tìm kiếm motif đã có những đóng góp quan trọng trong việc phát triển các thuật toán và cấu trúc dữ liệu hiệu quả để khai phá thông tin từ dữ liệu chuỗi thời gian. Các đóng góp này bao gồm việc phát triển các độ đo khoảng cách chống biến dạng thời gian, các cấu trúc chỉ mục để tăng tốc quá trình tìm kiếm, và các kỹ thuật để xử lý nhiễu và dữ liệu lớn. Những tiến bộ này đã mở ra nhiều ứng dụng mới trong các lĩnh vực khác nhau.

5.2. Hướng Nghiên Cứu Tiềm Năng Để Cải Thiện Hiệu Suất và Độ Chính Xác

Các hướng nghiên cứu tiềm năng để cải thiện hiệu suất và độ chính xác của tìm kiếm motif bao gồm việc phát triển các cấu trúc chỉ mục mới, các độ đo khoảng cách mạnh mẽ hơn, các kỹ thuật tối ưu hóa để giảm độ phức tạp tính toán, và các phương pháp để kết hợp tìm kiếm motif với các kỹ thuật học máy khác. Ngoài ra, cần phải nghiên cứu các phương pháp để xử lý dữ liệu chuỗi thời gian phức tạp, chẳng hạn như dữ liệu đa biến hoặc dữ liệu có cấu trúc phân cấp.

5.3. Ứng Dụng Mới Của Tìm Kiếm Motif Trong Kỷ Nguyên Dữ Liệu Lớn

Tìm kiếm motif có tiềm năng ứng dụng rộng rãi trong kỷ nguyên dữ liệu lớn. Các ứng dụng tiềm năng bao gồm phát hiện gian lận tài chính, dự đoán lỗi thiết bị, phân tích hành vi khách hàng, và giám sát sức khỏe cộng đồng. Việc phát triển các thuật toán và công cụ tìm kiếm motif hiệu quả sẽ mở ra nhiều cơ hội mới để khai thác thông tin từ dữ liệu chuỗi thời gian và giải quyết các bài toán quan trọng trong nhiều lĩnh vực.

Nội dung chính

Tổng quan nghiên cứu

Dữ liệu chuỗi thời gian ngày càng trở nên quan trọng trong nhiều lĩnh vực như khoa học kỹ thuật, kinh tế, tài chính, y học và nhiều ngành công nghiệp khác. Theo ước tính, với sự bùng nổ của dữ liệu số hóa, việc khai thác và phân tích dữ liệu chuỗi thời gian đã trở thành một thách thức lớn đối với các nhà khoa học máy tính. Một trong những bài toán trọng tâm là tìm kiếm motif — các mẫu chuỗi con xuất hiện thường xuyên và có ý nghĩa trong dữ liệu chuỗi thời gian. Việc tìm kiếm motif không chỉ giúp phát hiện các xu hướng, mẫu lặp lại mà còn hỗ trợ dự báo và phân loại dữ liệu hiệu quả.

Mục tiêu chính của nghiên cứu là phát triển giải thuật tìm kiếm motif trên dữ liệu chuỗi thời gian sử dụng độ đo xoắn thời gian động (Dynamic Time Warping - DTW) kết hợp với cấu trúc chỉ mục TS-Tree nhằm tăng tốc độ tìm kiếm và nâng cao độ chính xác. Phạm vi nghiên cứu tập trung trên các bộ dữ liệu mẫu đại diện cho nhiều lĩnh vực khác nhau, với kích thước chuỗi con từ khoảng 5 đến 25 điểm, thực hiện tại Trường Đại học Bách Khoa, Đại học Quốc gia TP. Hồ Chí Minh trong năm 2017.

Nghiên cứu có ý nghĩa quan trọng trong việc cải thiện hiệu quả khai phá dữ liệu chuỗi thời gian, đặc biệt trong các ứng dụng đòi hỏi xử lý dữ liệu lớn và phức tạp. Các chỉ số đánh giá như thời gian thực thi và độ chính xác tìm kiếm motif được sử dụng làm metrics để đo lường hiệu quả của giải thuật đề xuất.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Dữ liệu chuỗi thời gian (Time Series Data): Chuỗi các giá trị thực được ghi nhận tại các thời điểm liên tục hoặc cách đều nhau, có thể xem là dữ liệu đa chiều với chiều dài n.

• Độ đo xoắn thời gian động (Dynamic Time Warping - DTW): Phương pháp tính khoảng cách giữa hai chuỗi thời gian cho phép uốn cong trục thời gian để tìm sự tương đồng tốt hơn so với độ đo Euclid truyền thống. DTW được áp dụng rộng rãi trong nhận dạng mẫu, sinh trắc học, và phân tích chuỗi thời gian đa phương tiện.

• Cấu trúc chỉ mục TS-Tree: Một cấu trúc cây cân bằng, tương tự R*-Tree nhưng tối ưu cho dữ liệu chuỗi thời gian với thông tin mô tả cận trên và cận dưới của các chuỗi con đã được rời rạc hóa. TS-Tree hỗ trợ hiệu quả cho việc tỉa nhánh và tăng tốc truy vấn trên dữ liệu chuỗi thời gian.

• Khái niệm Motif: Motif là các chuỗi con xuất hiện nhiều lần trong chuỗi thời gian chính, có khoảng cách DTW nhỏ hơn một ngưỡng R và không phải là trùng khớp tầm thường. Motif bậc K là tập hợp các motif khác nhau ít nhất 2R về khoảng cách.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Sử dụng các bộ dữ liệu mẫu chuỗi thời gian phổ biến trong cộng đồng nghiên cứu, bao gồm dữ liệu điện tâm đồ (ECG), điện não đồ (EEG), dữ liệu công suất (Power), và các dữ liệu thiên văn học.

• Phương pháp phân tích: Nghiên cứu phát triển giải thuật tìm kiếm motif dựa trên độ đo DTW kết hợp cấu trúc chỉ mục TS-Tree. So sánh hiệu quả với giải thuật tìm kiếm motif chân phương (Brute Force) về thời gian thực thi và độ chính xác.

• Cỡ mẫu và chọn mẫu: Các bộ dữ liệu có kích thước chuỗi con từ 5 đến 25 điểm, được lựa chọn đại diện cho nhiều lĩnh vực khác nhau nhằm đánh giá tính tổng quát của giải thuật.

• Timeline nghiên cứu: Nghiên cứu được thực hiện trong năm 2017, bao gồm khảo sát lý thuyết, phát triển giải thuật, thực nghiệm trên bộ dữ liệu mẫu và phân tích kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Tăng tốc độ tìm kiếm motif: Giải thuật tìm kiếm motif dựa trên cấu trúc chỉ mục TS-Tree với độ đo DTW cho thời gian thực thi nhanh hơn đáng kể so với giải thuật Brute Force. Ví dụ, trên bộ dữ liệu Small Power Italia (chuỗi con kích thước 7), thời gian tìm kiếm giảm khoảng 30-40%.

2. Độ chính xác cao: Giải thuật đề xuất vẫn đảm bảo độ chính xác trong việc phát hiện motif, tương đương với giải thuật Brute Force, nhờ sử dụng thông tin cận trên và cận dưới trong TS-Tree để tỉa nhánh hiệu quả.

3. Khả năng xử lý chuỗi dữ liệu lớn: TS-Tree thích nghi tốt với các chuỗi dữ liệu có kích thước lớn hơn 10, như bộ dữ liệu Power và ECG với chuỗi con kích thước 25, thời gian tìm kiếm không tăng đáng kể so với kích thước chuỗi con.

4. Thời gian tìm kiếm không phụ thuộc kích thước chuỗi con: Thời gian tìm kiếm motif không biến động nhiều khi thay đổi kích thước chuỗi con, nhờ cấu trúc chỉ mục TS-Tree giúp giảm số lượng phép tính DTW cần thiết.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện hiệu quả là do TS-Tree lưu trữ thông tin mô tả cận trên và cận dưới của các chuỗi con đã được rời rạc hóa, giúp loại bỏ nhanh các nhánh không phù hợp trong quá trình tìm kiếm. So với giải thuật Brute Force có độ phức tạp bậc hai, giải thuật đề xuất giảm đáng kể số phép tính DTW tốn kém.

Kết quả phù hợp với các nghiên cứu trước đây về ứng dụng TS-Tree trong truy vấn dữ liệu chuỗi thời gian, đồng thời khắc phục nhược điểm của độ đo Euclid trong việc tính khoảng cách. Việc áp dụng DTW giúp tăng độ chính xác khi xử lý dữ liệu có biến động thời gian hoặc nhiễu.

Dữ liệu có thể được trình bày qua biểu đồ so sánh thời gian thực thi giữa hai giải thuật trên các bộ dữ liệu khác nhau, cũng như bảng tổng hợp số lượng motif tìm được và thời gian tương ứng.

Đề xuất và khuyến nghị

1. Phát triển giải thuật tìm kiếm motif đa luồng: Áp dụng kỹ thuật song song để tận dụng sức mạnh xử lý đa nhân, giảm thời gian thực thi trên các bộ dữ liệu lớn, hướng tới xử lý thời gian thực.

2. Tối ưu hóa cấu trúc TS-Tree: Nghiên cứu cải tiến thuật toán rời rạc hóa và phân tách trong TS-Tree để giảm thiểu kích thước cây và tăng tốc độ truy vấn, đặc biệt với dữ liệu có chiều cao.

3. Mở rộng ứng dụng sang các lĩnh vực khác: Áp dụng giải thuật vào các lĩnh vực như y tế, tài chính, và công nghiệp để khai thác motif trong dữ liệu thực tế, từ đó hỗ trợ dự báo và phân tích chuyên sâu.

4. Phát triển giao diện trực quan: Xây dựng công cụ trực quan hóa kết quả tìm kiếm motif giúp người dùng dễ dàng phân tích và đánh giá các mẫu motif phát hiện được.

Các giải pháp trên nên được thực hiện trong vòng 1-2 năm tới, phối hợp giữa các nhà nghiên cứu và doanh nghiệp ứng dụng để đảm bảo tính khả thi và hiệu quả.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu khoa học máy tính: Đặc biệt những người quan tâm đến khai phá dữ liệu chuỗi thời gian, xử lý dữ liệu lớn và phát triển thuật toán tìm kiếm motif.

2. Chuyên gia phân tích dữ liệu và khoa học dữ liệu: Có thể áp dụng các giải thuật và cấu trúc chỉ mục TS-Tree để nâng cao hiệu quả phân tích dữ liệu chuỗi thời gian trong các dự án thực tế.

3. Người làm trong lĩnh vực y tế và sinh học: Sử dụng để phân tích dữ liệu điện tâm đồ, điện não đồ nhằm phát hiện các mẫu bất thường hoặc xu hướng bệnh lý.

4. Doanh nghiệp tài chính và kinh tế: Áp dụng để phân tích chuỗi thời gian giá chứng khoán, dự báo xu hướng thị trường dựa trên motif phát hiện được.

Mỗi nhóm đối tượng có thể sử dụng kết quả nghiên cứu để phát triển các ứng dụng chuyên biệt, từ đó nâng cao hiệu quả công việc và ra quyết định chính xác hơn.

Câu hỏi thường gặp

1. Độ đo DTW có ưu điểm gì so với Euclid trong tìm kiếm motif?
   DTW cho phép uốn cong trục thời gian để so sánh các chuỗi có biến dạng về thời gian, giúp phát hiện motif chính xác hơn trong dữ liệu có nhiễu hoặc biến động không đồng đều.

2. TS-Tree khác gì so với R-Tree trong lưu trữ dữ liệu chuỗi thời gian?*
   TS-Tree lưu trữ thông tin cận trên và cận dưới của chuỗi con đã rời rạc hóa, giúp tỉa nhánh hiệu quả hơn và phù hợp với độ đo DTW, trong khi R*-Tree chủ yếu dùng cho dữ liệu không gian với độ đo Euclid.

3. Giải thuật đề xuất có thể áp dụng cho dữ liệu chuỗi thời gian lớn không?
   Có, TS-Tree giúp giảm số phép tính DTW cần thiết, do đó giải thuật thích nghi tốt với dữ liệu lớn và có thể mở rộng thêm bằng kỹ thuật song song.

4. Làm thế nào để chọn ngưỡng khoảng cách R trong tìm kiếm motif?
   Ngưỡng R được chọn dựa trên đặc điểm dữ liệu và mục tiêu phân biệt motif, thường được xác định qua thử nghiệm hoặc dựa trên phân phối khoảng cách trong dữ liệu.

5. Giải thuật có thể áp dụng cho dữ liệu chuỗi thời gian không đều không?
   DTW có khả năng xử lý dữ liệu không đều về thời gian, tuy nhiên cần chuẩn hóa hoặc tiền xử lý để đảm bảo tính nhất quán khi xây dựng cấu trúc chỉ mục TS-Tree.

Kết luận

• Đề tài đã phát triển thành công giải thuật tìm kiếm motif trên dữ liệu chuỗi thời gian sử dụng độ đo DTW kết hợp cấu trúc chỉ mục TS-Tree, nâng cao hiệu quả tìm kiếm so với phương pháp Brute Force truyền thống.
• Giải thuật đề xuất cho thấy thời gian thực thi nhanh hơn khoảng 30-40% trên các bộ dữ liệu mẫu, đồng thời giữ được độ chính xác cao trong phát hiện motif.
• TS-Tree chứng minh là cấu trúc chỉ mục phù hợp cho dữ liệu chuỗi thời gian đa chiều, hỗ trợ tốt cho việc tỉa nhánh và giảm thiểu số phép tính DTW.
• Nghiên cứu mở ra hướng phát triển các giải thuật tìm kiếm motif hiệu quả hơn, có thể áp dụng trong nhiều lĩnh vực thực tế như y tế, tài chính và công nghiệp.
• Các bước tiếp theo bao gồm tối ưu hóa giải thuật, mở rộng ứng dụng và phát triển công cụ trực quan hóa kết quả nhằm hỗ trợ người dùng cuối.

Quý độc giả và nhà nghiên cứu được khuyến khích áp dụng và phát triển thêm các giải pháp dựa trên kết quả nghiên cứu này để nâng cao hiệu quả khai phá dữ liệu chuỗi thời gian trong thực tế.

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

Chương I: chương này giới thiệu tổng quan và tại sao lại chọn đề tài, mục tiêu, giới hạn và tóm lược các kết quả thu được. Chương II: trình bày cơ sở lý thuyết liên quan cần tìm hiểu bao gồm độ đo xoắn thời gian động, các phương pháp thu giảm kích thước của dữ liệu chuỗi thời gian, bài toán tìm kiếm tương tự, khái niệm motif trên dữ liệu chuỗi thời gian Chương III: trong chương này tập trung khảo sát các công trình liên quan đến luận văn bao gồm: phương pháp tìm kiếm motif dựa vào giải thuật tìm kiếm chân phương (Brute Force), phương pháp tìm kiếm motif dựa vào giải thuật chiếu ngẫu nhiên, cấu trúc chỉ mục R*-Tree, cấu trúc chỉ mục TS-Tree. Chương IV: Trình bày cấu trúc chỉ mục TS-Tree làm việc với độ đo xoắn thời gian động. Đề xuất giải thuật tìm kiếm motif trên dữ liệu chuỗi thời gian với độ đo xoắn thời gian động dựa vào cấu trúc chỉ mục TS-Tree.

Chương V: tiến hành đưa dữ liệu vào thực nghiệm trên giải thuật đề xuất và giải thuật tìm kiếm chân phương sau đó so sánh kết quả và đưa ra một số nhận xét về kết quả thu được. Chương VI: Chúng tôi đưa ra một số kết luận sau khi thực hiện đề tài. 3 Tìm kiếm motif trên dữ liệu chuỗi thời gian với độ đo DTW dựa vào cấu trúc chỉ mục TS-Tree CHƯƠNG II: CƠ SỞ LÝ THUYẾT Trong chương này sẽ trình bày những kiến thức liên quan đến bài toán tìm kiếm motif trên dữ liệu chuỗi thời gian. Chúng tôi sẽ trình bày khái niệm về dữ liệu chuỗi thời gian, độ đo xoắn thời gian động, khái niệm về bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian và khái niệm về motif.1 Dữ liệu chuỗi thời gian Chuỗi thời gian là một chuỗi trị số thực, mỗi trị biểu diễn một giá trị một giá trị đo tại những thời điểm cách đều nhau.

Có thể xem chuỗi thời gian là một tập hợp chuỗi dữ liệu 2 chiều (T,X). Trong đó T là tập thời điểm xác định T= (t1, t2… ) với ti thuộc R, còn X là tập hợp giá trị quan sát được tại từng thời điểm thuộc tập T đó. Với những giá trị quan sát thu nhận được tại những khoảng thời gian bằng nhau thì ta có được n giá trị quan sát trong khoảng thời gian đó thì chuỗi có thể được xem là dữ liệu trong không gian n chiều. Dữ liệu chuỗi thời gian được sử dụng trong rất nhiều lĩnh vực khác nhau, chính vì thế có thể xem dữ liệu thời gian như những thông tin ghi lại trên từng phút, từng giây.

Do đó dữ liệu chuỗi thời gian thường rất dài tuy nhiên giá trị giao động không cao và thường giao động trong khoảng xấp xỉ nào đó. Ví dụ, hệ thống thu thập thông tin về nhiệt độ khí hậu tại một khu vực cụ thể nào đó thường nằm trong khoảng 20 đến 30 độ.2 Độ đo xoắn thời gian động (Dynamic Time Warping - DTW) Độ đo xoắn thời gian động được Berndt và Clifford giới thiệu vào năm 1994 [10] trong công trình nghiên cứu về độ đo DTW(xoắn thời gian động) trong cơ sở dữ liệu. Độ đo DTW hiệu quả hơn độ đo Euclid trong việc tính toán khoảng cách giữa 2 mẫu dữ liệu chuỗi thời gian. Trên thực tế có những mẫu dữ liệu chuỗi thời gian giống nhau nhưng khi tính toán bằng độ đo Euclid thì lại cho kết quả khác xa nhau.

Chính vì thế nên độ đo Euclid thường cho ra kết quả tính toán kém chính xác hơn so với độ đo xoắn thời gian động đối với các dữ liệu nhiều chiều. Bên cạnh đó có rất nhiều công trình nghiên cứu ứng dụng độ đo xoắn thời gian động vào trong các thực tế như: công trình nghiên cứu của Gavrila và Davis năm 1995 trong ngành sinh trắc học, Munich và Perona năm 1999 trong ngành chữ ký điện tử, Kovacs và Vajna năm 2000 trong dữ liệu vân tay. Tuy nhiên độ đo xoắn thời gian động có một nhược điểm là thời gian tính toán không được nhanh. 4 Tìm kiếm motif trên dữ liệu chuỗi thời gian với độ đo DTW dựa vào cấu trúc chỉ mục TS-Tree Trước khi tìm hiểu về độ đo khoảng cách DTW chúng ta sẽ nói sơ qua về độ đo khoảng cách Euclid.

Giả sử chúng ta có 2 chuỗi thời gian Q = Q1, Q2,…., Qn và C = C1, C2, …, Cn. Độ đo khoảng cách Euclid được xác định bằng công thức sau: 𝑛 𝐷 (𝑄, 𝐶 ) = √∑(𝑞𝑖 − 𝑐𝑖 ) (2.1) 𝑖=1 Độ do Euclid có ưu điểm là dễ hiểu, dễ tính toán nhưng độ đo này không làm việc tốt trên dữ liệu nhiễu, dữ liệu chuỗi thời gian liên quan đến lĩnh vực đa phương tiện (multimedia). Hình 2-1 dưới đây mô tả sự khác nhau giữa hai độ đo Euclid và độ đo DTW. Hình 2-1 Độ đo Euclid và độ đo xoắn thời gian động (Nguồn [3])1 Giả sử ta có 2 chuỗi thời gian Q và C có chiều dài lần lượt là n và m với Q = Q1, Q2, Q3, …., Cm theo hình 2-2 và độ đo xoắn thời gian động giữa Q và C theo hình 2.3 Hình 2-2: Hai mẫu dữ liệu chuỗi thời gian Q và C (Nguồn [3])2 5 Tìm kiếm motif trên dữ liệu chuỗi thời gian với độ đo DTW dựa vào cấu trúc chỉ mục TS-Tree Hình 2-3: Độ đo xoắn thời gian động giữa hai mẫu dữ liệu chuỗi thời gian Q và C (Nguồn [3])3 Để tính toán độ đo xoắn thời gian động giữa hai chuỗi trên, ta xây dựng một ma trận có kích thước n*m với n là số hàng của ma trận và m là số cột của ma trận.

Trong đó phần tử (ith,jth) của ma trận chứa khoảng cách d(qi,cj) giữa hai điểm qi, cj trên 2 chuỗi dữ liệu Q và C Trong đó d(qi, cj) được tính toán như sau: d(qi, cj) = (qi - cj)2 Ma trận chứa khoảng cách d(qi,cj) là ma trận xoắn. Một đường xoắn ( warping path ) là một tập các phần tử liên tục của ma trận định nghĩa một đường ánh xạ giữa Q và C W = w1, w2, …., wk với max(m,n) ≤ K ≤m+ n -1 d(qi, cj) đường xoắn W Hình 2-4 Ma trận xoắn ( nguồn [3] ) 4 6 Tìm kiếm motif trên dữ liệu chuỗi thời gian với độ đo DTW dựa vào cấu trúc chỉ mục TS-Tree Có rất nhiều đường xoắn thỏa mãn các điều kiện trên nhưng chúng ta chỉ quan tâm đến đường xoắn có chi phí tối thiểu: 𝐾 𝐷𝑇𝑊 (𝑄, 𝐶 ) = 𝑚𝑖𝑛 √∑ 𝑊𝑘 (2.2) 𝑘=1 { Độ phức tạp của giải thuật khi tính toán độ đo khoảng cách DTW là O(m*n). Do phải tính toán trên toàn bộ tập ma trận nên thời gian tính toán của độ đo DTW là khá cao. Đối với việc tính toán độ đo xoắn thời gian động chúng ta có một số ràng buộc sau: - Điều kiện biên: w1 = (1,1) và wk = (m,n) ràng buộc này yêu cầu đường xoắn phải bắt đầu và kết thúc ở hai góc đối diện của ma trận.

- Tính liên tục: wk = (a,b) thì wk-1 = (a',b') trong đó a-a' ≤ 1 và b-b' ≤ 1. Ràng buộc này yêu cầu đường xoắn phải di chuyển giữa những ô liền kề (kể cả những ô liền kề theo đường chéo). - Tính đơn điệu tăng: wk = (a,b) thì wk-1 = (a',b'), với a-a' ≥ 0 và b-b' ≥ 0. Ràng buộc này yêu cầu các điểm trong đường xoắn W phải có tính đơn điệu tăng theo thời gian.

Như đã đề cập ở trên việc tính toán trên toàn bộ ma trận nhằm tìm ra đường xoắn có chi phí tối thiểu tốn thời gian khá cao. Nhằm giảm thiểu chi phí tính toán cũng như hạn chế việc tìm ra những đường xoắn không phù hợp, công trình nghiên cứu của nhóm tác giả Sakoe-Chiba, tác giả Itakura [11] đã đề xuất ra những ràng buộc toàn cục (global constraints) để tăng tốc thời gian tính toán của độ đo xoắn thời gian động như hình 2-5. Hình 2-5: Hai ràng buộc toàn cục của dải Sakoe-Chiba và hình bình hành Itakura (Nguồn[3]) 5 7 Tìm kiếm motif trên dữ liệu chuỗi thời gian với độ đo DTW dựa vào cấu trúc chỉ mục TS-Tree 2.1 Chặn dưới cho khoảng cách DTW Mặc dù độ đo xoắn thời gian động cho kết quả tính toán chính xác nhưng lại gây ra chi phí tính toán cao. Để giải quyết vấn đề trên Keogh [3] đã đề xuất chỉ tính toán khoảng cách chặn dưới để giảm thiểu chi phí tính toán.

Ta định nghĩa chặn dưới (L) và chặn trên (U) của chuỗi dữ liệu chuỗi thời gian như sau: Ui = max (qi-r : qi+r), Li = min (qi-r: qi+r). Trong đó chỉ số r được định nghĩa tùy theo mô hình hoặc xem như là khoảng trong của độ đo xoắn thời gian động. Với Wk = (i,j) ta có j-r ≤ i ≤ j+r. Ta có mô hình chặn trên và chặn dưới theo Sakoe-Chiba, Itakura như hình 2-6 Đối với dải Sakoe-Chiba, r không phụ Đối với hình bình hành Itakura, r là một thuộc vào i hàm theo i Hình 2-6 Cận trên và cận dưới trong 2 mô hình Sakoe-Chiba(A) và Itakura(B) (Nguồn 3)6 Ta có chặn dưới LB_Keogh được định nghĩa bằng công thức 2.3) 0 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 Theo hình 2-7 ta có tổng bình phương khoảng cách từ mỗi phần của chuỗi thời gian C không nằm trong lớp bao giữa U và L tới các cạnh trực giao gần nhất của lớp bao để thu được khoảng cách chặn dưới Keogh.

Hình 2-7 Khoảng cách LB_Keogh trong 2 mô hình Sakoe-Chiba(A) và Itakura(B) (Nguồn [3])7 8 Tìm kiếm motif trên dữ liệu chuỗi thời gian với độ đo DTW dựa vào cấu trúc chỉ mục TS-Tree 2.2 Mở rộng chặn dưới cho độ đo xoắn thời gian động với PAA Để giảm thiểu chi phí tính toán của độ đo xoắn thời gian động ta đã có cải tiến bằng cách tính toán theo cận trên và cận dưới. Ngoài ra chúng ta có thể tiếp tục cải tiến giải thuật xoắn thời gian động bằng việc thu giảm chiều trong chuỗi dữ liệu thời gian cần tính toán bằng một số phương pháp như Fourier Transforms [14], Wavelets [15], Piecewise Aggregate Approximation (PAA)[16]. Trong đó Phương pháp xấp xỉ gộp từng đoạn (Piecewise Aggregate Approximation - PAA) được Keogh và các đồng sự đề nghị năm 2000. Phương pháp được lựa chọn vì cách tính toán rất đơn giản, chúng ta có thể tuần tự xấp xỉ k giá trị liền kề nhau thành cùng một giá trị trung bình bình cộng của k điểm đó.

Giả sử chúng ta có một chuỗi thời gian có chiều dài n được biến đổi thành về chuỗi thời gian khác có số chiều ít hơn N ( với 1 ≤ N ≤ n) có dạng 𝐶̅ = 𝑐̅1, 𝑐̅2,. Phần tử thứ i được tính toán theo công thức 2.