I. Giới thiệu đề tài
Luận văn tập trung vào việc tìm kiếm mô típ trên chuỗi thời gian sử dụng độ đo xoắn động và cấu trúc TSTree. Chuỗi thời gian đóng vai trò quan trọng trong nhiều lĩnh vực như tài chính, y tế, và khoa học kỹ thuật. Mô típ là các mẫu lặp lại trong dữ liệu, việc phát hiện chúng giúp giải quyết các bài toán như phân lớp, dự báo. Độ đo xoắn động (DTW) được sử dụng để tính khoảng cách giữa các chuỗi, khắc phục hạn chế của độ đo Euclid. Cấu trúc TSTree hỗ trợ hiệu quả cho việc lưu trữ và tìm kiếm dữ liệu chuỗi thời gian.
1.1. Mục tiêu đề tài
Mục tiêu chính là đề xuất giải thuật tìm kiếm mô típ trên chuỗi thời gian sử dụng độ đo xoắn động và cấu trúc TSTree. Các bước thực hiện bao gồm khảo sát độ đo xoắn động, nghiên cứu cấu trúc TSTree, đề xuất giải thuật, và kiểm tra hiệu quả thông qua thực nghiệm. Kết quả mong đợi là tăng tốc độ tìm kiếm và độ chính xác so với phương pháp truyền thống.
1.2. Giới hạn đề tài
Luận văn giới hạn trong việc nghiên cứu tìm kiếm mô típ trên chuỗi thời gian với độ đo xoắn động và cấu trúc TSTree. Dữ liệu sử dụng là các bộ dữ liệu mẫu phổ biến trong cộng đồng nghiên cứu. Các thử nghiệm được thực hiện trên các bộ dữ liệu nhỏ và lớn để đánh giá hiệu quả của giải thuật.
II. Cơ sở lý thuyết
Chương này trình bày các khái niệm cơ bản về chuỗi thời gian, độ đo xoắn động, và cấu trúc TSTree. Chuỗi thời gian là dãy các giá trị được ghi lại theo thời gian. Độ đo xoắn động (DTW) là phương pháp tính khoảng cách linh hoạt giữa hai chuỗi, phù hợp với dữ liệu có biến động thời gian. Cấu trúc TSTree là cấu trúc chỉ mục hiệu quả cho việc lưu trữ và tìm kiếm dữ liệu chuỗi thời gian.
2.1. Độ đo xoắn động DTW
Độ đo xoắn động (DTW) là phương pháp tính khoảng cách giữa hai chuỗi thời gian bằng cách tìm đường đi tối ưu trên ma trận khoảng cách. DTW khắc phục hạn chế của độ đo Euclid khi xử lý dữ liệu có độ dài khác nhau hoặc biến động thời gian. Các ràng buộc như Sakoe-Chiba và Itakura được áp dụng để giảm độ phức tạp tính toán.
2.2. Cấu trúc TSTree
Cấu trúc TSTree là cấu trúc chỉ mục dựa trên cây, được thiết kế để lưu trữ và tìm kiếm hiệu quả dữ liệu chuỗi thời gian. TSTree sử dụng các thành phần phân tách và thông tin mô tả để tối ưu hóa quá trình tìm kiếm. Cấu trúc này hỗ trợ tốt cho việc tìm kiếm mô típ với độ đo DTW.
III. Phương pháp giải quyết
Luận văn đề xuất giải thuật tìm kiếm mô típ trên chuỗi thời gian sử dụng độ đo xoắn động và cấu trúc TSTree. Giải thuật bao gồm các bước: xây dựng cấu trúc TSTree, tính toán khoảng cách DTW, và tìm kiếm mô típ. Kết quả được so sánh với phương pháp tìm kiếm chân phương (Brute Force) để đánh giá hiệu quả.
3.1. Giải thuật đề xuất
Giải thuật đề xuất kết hợp độ đo xoắn động và cấu trúc TSTree để tăng tốc độ tìm kiếm mô típ. Các bước thực hiện bao gồm: xây dựng TSTree, tính toán khoảng cách DTW, và tìm kiếm mô típ dựa trên cấu trúc cây. Giải thuật được thiết kế để xử lý hiệu quả các bộ dữ liệu lớn.
3.2. Thực nghiệm và đánh giá
Thực nghiệm được thực hiện trên các bộ dữ liệu mẫu như Small Power Italia, Small ECG, và Small EEG. Kết quả cho thấy giải thuật đề xuất có thời gian tìm kiếm nhanh hơn so với phương pháp tìm kiếm chân phương. Độ chính xác của giải thuật cũng được cải thiện đáng kể.
IV. Kết luận và hướng phát triển
Luận văn đã đề xuất và thực nghiệm giải thuật tìm kiếm mô típ trên chuỗi thời gian sử dụng độ đo xoắn động và cấu trúc TSTree. Kết quả cho thấy giải thuật hiệu quả hơn phương pháp truyền thống về cả thời gian và độ chính xác. Hướng phát triển tiếp theo là nghiên cứu các giải thuật tối ưu hơn và ứng dụng trong các lĩnh vực thực tế.
4.1. Đóng góp của đề tài
Đề tài đã đề xuất giải thuật hiệu quả cho tìm kiếm mô típ trên chuỗi thời gian, kết hợp độ đo xoắn động và cấu trúc TSTree. Kết quả thực nghiệm chứng minh tính khả thi và hiệu quả của giải thuật.
4.2. Hướng phát triển
Hướng phát triển tiếp theo bao gồm nghiên cứu các giải thuật tối ưu hơn, ứng dụng trong các lĩnh vực như y tế, tài chính, và khoa học kỹ thuật. Các nghiên cứu về cải tiến độ đo xoắn động và cấu trúc TSTree cũng là hướng đi tiềm năng.
