Luận văn thạc sĩ về chuỗi con trong dữ liệu chuỗi thời gian và độ đo xoắn thời gian động

Chuyên đề chuỗi con trong dữ liệu chuỗi thời gian bằng ..., tiếp cận liên ngành, kết quả nghiên cứu có giá trị ứng dụng cao trong chuyên ngành

• Tác giả: Võ Đức Vĩnh
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa - ĐHQG TP. HCM
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Kết Chuỗi Con Trên Dữ Liệu Chuỗi Thời Gian Dùng Độ Đo Xoắn Thời Gian Động
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Đị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
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ ĐỀ TÀI
• 1.1. KHAI PHÁ DỮ LIỆU CHUỖI THỜI GIAN
• 1.1.1. Dữ liệu lớn
• 1.1.2. Dữ liệu chuỗi thời gian
• 1.2. CÁC BÀI TOÁN LIÊN QUAN ĐẾN DỮ LIỆU CHUỖI THỜI GIAN
• 1.2.1. Phân lớp (Classification)
• 1.2.2. Gom cụm (clustering)
• 1.2.3. Dự báo (predicting/forcasting)
• 1.2.4. Phát hiện bất thường (novelty detection)
• 1.2.5. Phát hiện mô típ (motif detection)
• 1.3. BÀI TOÁN KẾT CHUỖI CON TRÊN DỮ LIỆU CHUỖI THỜI GIAN
• 1.4. Ý NGHĨA BÀI TOÁN KẾT CHUỖI CON. MỤC TIÊU VÀ NHIỆM VỤ CỦA ĐỀ TÀI
• 1.5. CÁC KẾT QUẢ ĐẠT ĐƯỢC
• 1.6. BỐ CỤC LUẬN VĂN
• 1.7. CÁC CÔNG TRÌNH LIÊN QUAN
• 1.7.1. CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN ĐỘ ĐO TƯƠNG TỰ
• 1.7.1.1. Phương pháp xoắn thời gian động (Dynamic Time Warping)
• 1.7.1.2. Phương pháp chuỗi con chung dài nhất
• 1.7.2. CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN KẾT CHUỖI CON
• 1.7.2.1. Phân đoạn chuỗi thời gian nhờ các điểm cực trị quan trọng
• 1.7.2.2. Phương pháp kết chuỗi con trực tiếp (nested loop join)
• 1.7.2.3. Phương pháp kết chuỗi con trên dữ liệu đã lập chỉ mục (indexing)
• 1.7.2.4. Phương pháp kết chuỗi con dựa trên các phân đoạn không đồng nhất (non-uniform segment)
• 1.7.2.5. Phương pháp đề nghị cho bài toán kết chuỗi con
• 1.8. ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG
• 1.8.1. RÀNG BUỘC ĐƯỜNG XOẮN ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG
• 1.8.1.1. Ràng buộc Sakoe-Chiba
• 1.8.1.2. Ràng buộc hình bình hành Itakura
• 1.8.2. KỸ THUẬT TỪ BỎ SỚM KHI TÍNH KHOẢNG CÁCH DTW
• 1.9. CÁC ĐIỂM CỰC TRỊ QUAN TRỌNG
• 1.9.1. Điểm cực trị thông thường (extreme points)
• 1.9.2. Điểm cực trị quan trọng (important extrema)
• 1.10. PHƯƠNG PHÁP ĐỀ NGHỊ
• 1.11. KHÁI QUÁT BÀI TOÁN KẾT CHUỖI CON
• 1.12. HỆ THỐNG ĐỀ NGHỊ CHO BÀI TOÁN KẾT CHUỖI CON
• 1.13. QUÁ TRÌNH CHUẨN HÓA DỮ LIỆU
• 1.14. QUÁ TRÌNH PHÂN ĐOẠN CHUỖI THỜI GIAN
• 1.15. QUÁ TRÌNH KẾT CHUỖI CON
• 1.16. MÔI TRƯỜNG THỰC NGHIỆM
• 1.17. DỮ LIỆU THỰC NGHIỆM
• 1.18. CÁC THAM SỐ ƯỚC LƯỢNG
• 1.19. PHƯƠNG PHÁP THỰC NGHIỆM
• 1.20. THỰC NGHIỆM VỀ CÁC CỰC TRỊ QUAN TRỌNG
• 1.21. THỰC NGHIỆM VỀ BÀI TOÁN SO TRÙNG CHUỖI CON
• 1.22. THỰC NGHIỆM SO SÁNH GIẢI THUẬT KẾT CHUỖI CON DÙNG CỬA SỔ TRƯỢT TỪNG ĐIỂM VỚI CỬA SỔ TRƯỢT TỪNG ĐOẠN
• 1.23. THỰC NGHIỆM KIỂM CHỨNG TÍNH CHẤT GIAO HOÁN CỦA PHÉP KẾT TRÊN DỮ LIỆU CHUỖI THỜI GIAN
• 1.24. TỔNG KẾT NỘI DUNG CỦA LUẬN VĂN
• 1.25. NHỮNG ĐÓNG GÓP CỦA ĐỀ TÀI
• 1.26. HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO
• BẢNG THUẬT NGỮ ANH - VIỆT VÀ TỪ VIẾT TẮT
• DANH MỤC HÌNH
• DANH MỤC GIẢI THUẬT
• DANH MỤC BẢNG BIỂU

Tóm tắt

I. Tổng quan về dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian là một tập hợp các mẫu dữ liệu được ghi nhận theo thời gian, có thể là đơn biến hoặc đa biến. Dữ liệu chuỗi thời gian tồn tại trong nhiều lĩnh vực như kinh tế, tài chính, y tế và giáo dục. Việc khai thác thông tin từ dữ liệu chuỗi thời gian có ý nghĩa quan trọng trong việc phát hiện các mô hình và xu hướng. Các bài toán liên quan đến dữ liệu chuỗi thời gian bao gồm phân lớp, gom cụm, dự báo và phát hiện bất thường. Đặc biệt, bài toán kết chuỗi con trên dữ liệu chuỗi thời gian được xem là một trong những vấn đề cốt lõi trong khai phá dữ liệu. Theo khảo sát của Tufte, E., hơn 75% hình ảnh trong các tờ báo và tạp chí thể hiện dữ liệu chuỗi thời gian. Điều này cho thấy sự phổ biến và tầm quan trọng của loại dữ liệu này trong nghiên cứu và ứng dụng thực tiễn.

1.1 Đặc điểm của dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian có những đặc điểm riêng biệt như tính liên tục và phụ thuộc vào thời gian. Độ đo tương tự giữa các chuỗi thời gian thường phụ thuộc vào cách thức đánh giá, có thể sử dụng các phương pháp như đo Euclid hoặc đo DTW. Dữ liệu chuỗi thời gian thường không đồng nhất, có thể bị nhiễu hoặc thiếu giá trị, điều này tạo ra thách thức trong việc phân tích và khai thác thông tin. Việc hiểu rõ các đặc điểm này là cần thiết để phát triển các phương pháp phân tích hiệu quả hơn.

II. Phân tích bài toán kết chuỗi con

Bài toán kết chuỗi con là một vấn đề quan trọng trong khai thác dữ liệu chuỗi thời gian. Nó liên quan đến việc tìm kiếm các chuỗi con tương tự trong một chuỗi thời gian lớn hơn. Các phương pháp hiện tại thường sử dụng phân đoạn chuỗi thời gian để tìm kiếm các chuỗi con tương tự. Tuy nhiên, nhiều phương pháp này có độ phức tạp cao và thời gian tính toán lâu. Luận văn này đề xuất một phương pháp mới, sử dụng các điểm cực trị quan trọng để phân đoạn chuỗi thời gian, từ đó giảm thiểu độ phức tạp tính toán. Kết quả thực nghiệm cho thấy phương pháp này có thể đạt được độ chính xác cao trong việc tìm kiếm các chuỗi con.

2.1 Phương pháp phân đoạn chuỗi thời gian

Phương pháp phân đoạn chuỗi thời gian dựa trên việc xác định các điểm cực trị quan trọng. Kỹ thuật này có độ phức tạp chỉ là O(n), giúp giảm thiểu thời gian tính toán. Các phân đoạn này được sử dụng làm mẫu truy vấn trong quá trình tìm kiếm chuỗi con. Việc sử dụng các điểm cực trị quan trọng không chỉ giúp cải thiện hiệu suất mà còn tăng độ chính xác trong việc phát hiện các chuỗi con tương tự. Điều này cho thấy giá trị thực tiễn của phương pháp đề xuất trong việc xử lý dữ liệu chuỗi thời gian.

III. Ứng dụng và giá trị thực tiễn

Nghiên cứu về kết chuỗi con trong dữ liệu chuỗi thời gian có nhiều ứng dụng thực tiễn trong các lĩnh vực như tài chính, y tế và công nghiệp. Việc phát hiện các mô hình lặp lại trong dữ liệu chuỗi thời gian có thể giúp các nhà phân tích đưa ra các quyết định chính xác hơn. Phương pháp sử dụng đo DTW kết hợp với kỹ thuật từ bỏ sớm cho phép xử lý các chuỗi thời gian có độ dài khác nhau và lệch pha, điều này rất hữu ích trong các ứng dụng thực tế. Kết quả thực nghiệm cho thấy phương pháp này có thể áp dụng hiệu quả trên các bộ dữ liệu lớn, từ đó mở ra hướng nghiên cứu mới trong lĩnh vực khai thác dữ liệu chuỗi thời gian.

3.1 Tính ứng dụng trong thực tiễn

Các ứng dụng của nghiên cứu này có thể được thấy rõ trong việc phân tích dữ liệu tài chính, nơi mà việc phát hiện các xu hướng và mô hình lặp lại là rất quan trọng. Ngoài ra, trong lĩnh vực y tế, việc phân tích dữ liệu chuỗi thời gian từ các thiết bị theo dõi sức khỏe có thể giúp phát hiện sớm các vấn đề sức khỏe. Phương pháp đề xuất không chỉ giúp cải thiện độ chính xác mà còn giảm thiểu thời gian tính toán, từ đó nâng cao hiệu quả trong việc xử lý và phân tích dữ liệu chuỗi thời gian.

Nội dung chính

## Tổng quan nghiên cứu

Dữ liệu chuỗi thời gian là một trong những loại dữ liệu phổ biến và quan trọng trong nhiều lĩnh vực như khoa học kỹ thuật, kinh tế, tài chính, y tế, giáo dục, môi trường và sinh học. Theo khảo sát, hơn 75% các hình biểu diễn dữ liệu trong các tạp chí khoa học từ năm 1974 đến 1989 là dữ liệu chuỗi thời gian. Với sự phát triển của công nghệ số, khối lượng dữ liệu chuỗi thời gian ngày càng tăng nhanh, dự kiến đạt khoảng 35 Zettabyte vào năm 2020. Bài toán kết chuỗi con trên dữ liệu chuỗi thời gian là một bài toán tổng quát và căn bản trong khai phá dữ liệu chuỗi thời gian, có ứng dụng rộng rãi trong phân lớp, gom cụm, phát hiện mô típ, phát hiện bất thường và nhiều lĩnh vực khác.

Mục tiêu nghiên cứu của luận văn là đề xuất một phương pháp mới để giải quyết bài toán kết chuỗi con trên dữ liệu chuỗi thời gian đơn biến đồng nhất, sử dụng độ đo xoắn thời gian động (DTW) kết hợp với kỹ thuật phân đoạn chuỗi dựa trên các điểm cực trị quan trọng. Phạm vi nghiên cứu tập trung trên dữ liệu ngoại tuyến với các bộ dữ liệu có chiều dài lên đến hàng chục nghìn đ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 2014.

Nghiên cứu có ý nghĩa quan trọng trong việc nâng cao hiệu quả và độ chính xác của các thuật toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian, góp phần giảm thiểu chi phí tính toán và tăng tốc độ xử lý, từ đó hỗ trợ các ứng dụng thực tiễn như phát hiện đạo nhạc, phân tích tài chính và nhiều lĩnh vực khác.

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

### Khung lý thuyết áp dụng

- **Dữ liệu chuỗi thời gian (Time Series Data):** Chuỗi thời gian đơn biến đồng nhất được biểu diễn dưới dạng vectơ giá trị n chiều, trong đó các điểm dữ liệu được lấy mẫu cách đều nhau theo thời gian.

- **Độ đo xoắn thời gian động (Dynamic Time Warping - DTW):** Là phương pháp tính khoảng cách giữa hai chuỗi thời gian có thể khác chiều dài và lệch pha, cho phép ánh xạ không tuyến tính giữa các điểm dữ liệu. DTW được tính bằng quy hoạch động với độ phức tạp O(mn), trong đó m, n là chiều dài hai chuỗi.

- **Ràng buộc Sakoe-Chiba:** Giới hạn phạm vi tìm đường xoắn tối ưu trong ma trận DTW nhằm giảm chi phí tính toán, bằng cách chỉ xét các ô trong một cửa sổ có bán kính r quanh đường chéo chính.

- **Kỹ thuật từ bỏ sớm (Early Abandon):** Tăng tốc quá trình tính DTW bằng cách dừng tính toán khi khoảng cách tích lũy vượt quá ngưỡng cho phép.

- **Điểm cực trị quan trọng (Important Extrema):** Các điểm cực đại và cực tiểu được xác định dựa trên tham số R (được tính từ độ lệch chuẩn mẫu), giúp phân đoạn chuỗi thời gian thành các đoạn có ý nghĩa, giảm thiểu số lượng điểm cần xử lý.

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

- **Nguồn dữ liệu:** Sử dụng các bộ dữ liệu chuỗi thời gian thực nghiệm đa dạng như dữ liệu chứng khoán, dữ liệu sinh học (EEG), dữ liệu năng lượng và dữ liệu chuyển động.

- **Phương pháp phân tích:** Áp dụng kỹ thuật phân đoạn chuỗi thời gian dựa trên các điểm cực trị quan trọng với độ phức tạp O(n). Tiếp đó, sử dụng giải thuật cửa sổ trượt dịch chuyển từng điểm để thực hiện kết chuỗi con, kết hợp với độ đo DTW có bổ sung kỹ thuật từ bỏ sớm và ràng buộc Sakoe-Chiba nhằm tăng tốc độ tính toán.

- **Timeline nghiên cứu:** Nghiên cứu được thực hiện trong khoảng thời gian từ tháng 7 đến tháng 12 năm 2014, bao gồm các giai đoạn thu thập dữ liệu, phát triển thuật toán, thực nghiệm và đánh giá kết quả.

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

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

- **Phân đoạn chuỗi thời gian hiệu quả:** Việc sử dụng điểm cực trị quan trọng với tham số R được xác định bằng hai lần độ lệch chuẩn mẫu giúp phân đoạn chuỗi thời gian chính xác, phù hợp với các bộ dữ liệu có biên độ dao động mạnh. Độ phức tạp của quá trình phân đoạn chỉ là O(n), cho phép xử lý các chuỗi dài đến hàng chục nghìn điểm.

- **Giải thuật kết chuỗi con chính xác:** Giải thuật cửa sổ trượt dịch chuyển từng điểm không mắc lỗi tìm sót ứng viên, đảm bảo độ chính xác cao trong việc tìm kiếm chuỗi con tương tự. Thực nghiệm trên bộ dữ liệu Power_Italy với chiều dài 45,000 điểm cho thấy thời gian xử lý khoảng hơn 2 giờ, chấp nhận được trong bối cảnh xử lý ngoại tuyến.

- **Tăng tốc tính toán DTW:** Kỹ thuật từ bỏ sớm và ràng buộc Sakoe-Chiba giúp giảm đáng kể thời gian tính toán khoảng cách DTW, loại bỏ các đường xoắn không có ý nghĩa và giảm số lượng phép tính cần thiết.

- **Tính giao hoán tương đối của phép kết chuỗi con:** Thực nghiệm cho thấy phép kết chuỗi con có tính giao hoán tương đối, nghĩa là kết quả phép kết giữa hai tập dữ liệu T1 và T2 gần bằng kết quả khi đổi chỗ hai tập này, với sai số trong khoảng ±ε.

### Thảo luận kết quả

Nguyên nhân của hiệu quả trên là do việc phân đoạn chuỗi thời gian dựa trên các điểm cực trị quan trọng giúp giảm số lượng mẫu truy vấn Q cần tìm kiếm, từ đó giảm chi phí tính toán. So với các phương pháp phân đoạn phức tạp khác, phương pháp này đơn giản hơn nhưng vẫn đảm bảo độ chính xác cao.

Việc sử dụng DTW thay vì khoảng cách Euclid giúp xử lý tốt các chuỗi có độ dài khác nhau và lệch pha, phù hợp với nhiều ứng dụng thực tế. Kỹ thuật từ bỏ sớm và ràng buộc Sakoe-Chiba là những cải tiến quan trọng giúp giảm đáng kể thời gian tính toán, điều này được minh họa qua các biểu đồ so sánh thời gian thực thi giữa các phương pháp.

So với các nghiên cứu trước đây, phương pháp đề xuất có ưu điểm về tính đơn giản, hiệu quả và khả năng áp dụng trên các bộ dữ liệu lớn. Điều này mở ra hướng phát triển cho các ứng dụng khai phá dữ liệu chuỗi thời gian trong thực tế.

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

- **Áp dụng phân đoạn dựa trên điểm cực trị quan trọng:** Khuyến nghị các nhà nghiên cứu và phát triển ứng dụng sử dụng kỹ thuật phân đoạn này để giảm chi phí tính toán trong các bài toán khai phá dữ liệu chuỗi thời gian, đặc biệt với dữ liệu có biên độ dao động lớn.

- **Tích hợp kỹ thuật từ bỏ sớm và ràng buộc Sakoe-Chiba trong DTW:** Động viên việc áp dụng các kỹ thuật này nhằm tăng tốc độ xử lý, giảm thời gian thực thi mà không làm giảm độ chính xác, phù hợp với các ứng dụng yêu cầu xử lý nhanh.

- **Phát triển giải thuật cửa sổ trượt dịch chuyển từng điểm:** Khuyến khích sử dụng giải thuật này trong các hệ thống tìm kiếm tương tự chuỗi con để đảm bảo không bỏ sót ứng viên, nâng cao độ tin cậy của kết quả.

- **Mở rộng nghiên cứu cho dữ liệu luồng (streaming data):** Đề xuất nghiên cứu tiếp theo tập trung vào việc áp dụng và tối ưu các phương pháp trên cho dữ liệu chuỗi thời gian dạng luồng, nhằm đáp ứng yêu cầu xử lý thời gian thực.

- **Đào tạo và chuyển giao công nghệ:** Khuyến nghị các tổ chức giáo dục và doanh nghiệp tổ chức các khóa đào tạo về kỹ thuật khai phá dữ liệu chuỗi thời gian, giúp nâng cao năng lực ứng dụng trong thực tế.

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

- **Nhà nghiên cứu và sinh viên ngành Khoa học Máy tính:** Có thể sử dụng luận văn làm tài liệu tham khảo để phát triển các thuật toán khai phá dữ liệu chuỗi thời gian, đặc biệt trong lĩnh vực xử lý tín hiệu và học máy.

- **Chuyên gia phân tích dữ liệu và kỹ sư dữ liệu:** Áp dụng các phương pháp đề xuất để cải thiện hiệu quả xử lý và phân tích dữ liệu chuỗi thời gian trong các dự án thực tế như tài chính, y tế, và môi trường.

- **Doanh nghiệp công nghệ và phát triển phần mềm:** Sử dụng kết quả nghiên cứu để xây dựng các sản phẩm và dịch vụ liên quan đến phân tích dữ liệu lớn, đặc biệt là các hệ thống phát hiện mô típ, dự báo và phát hiện bất thường.

- **Cơ quan quản lý và hoạch định chính sách:** Tham khảo để hiểu rõ hơn về các công nghệ khai phá dữ liệu chuỗi thời gian, từ đó áp dụng trong việc phân tích dữ liệu kinh tế, tài chính và xã hội nhằm đưa ra các quyết sách phù hợp.

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

1. **Phân đoạn chuỗi thời gian dựa trên điểm cực trị quan trọng là gì?**  
Là kỹ thuật xác định các điểm cực đại và cực tiểu quan trọng trong chuỗi thời gian dựa trên tham số R, giúp phân đoạn chuỗi thành các đoạn có ý nghĩa, giảm số lượng điểm cần xử lý mà vẫn giữ được đặc trưng của dữ liệu.

2. **DTW có ưu điểm gì so với khoảng cách Euclid?**  
DTW cho phép tính khoảng cách giữa các chuỗi có độ dài khác nhau và lệch pha về thời gian, giúp nhận dạng các mẫu có hình dạng tương tự nhưng không đồng bộ về thời gian, điều mà khoảng cách Euclid không làm được.

3. **Kỹ thuật từ bỏ sớm giúp tăng tốc DTW như thế nào?**  
Kỹ thuật này dừng tính toán khoảng cách DTW ngay khi giá trị tích lũy vượt quá ngưỡng cho phép, tránh tính toán thừa và giảm đáng kể thời gian xử lý.

4. **Giải thuật cửa sổ trượt dịch chuyển từng điểm có ưu điểm gì?**  
Giải thuật này đảm bảo không bỏ sót ứng viên trong quá trình tìm kiếm chuỗi con tương tự, giúp tăng độ chính xác của kết quả so với các phương pháp dịch chuyển từng đoạn.

5. **Phương pháp đề xuất có thể áp dụng cho dữ liệu luồng không?**  
Hiện tại phương pháp chủ yếu áp dụng cho dữ liệu ngoại tuyến, tuy nhiên có thể mở rộng và tối ưu cho dữ liệu luồng trong các nghiên cứu tiếp theo nhằm đáp ứng yêu cầu xử lý thời gian thực.

## Kết luận

- Đề xuất phương pháp phân đoạn chuỗi thời gian dựa trên điểm cực trị quan trọng với tham số R được xác định bằng độ lệch chuẩn mẫu, giúp giảm chi phí tính toán và giữ độ chính xác cao.  
- Sử dụng giải thuật cửa sổ trượt dịch chuyển từng điểm kết hợp với độ đo DTW có bổ sung kỹ thuật từ bỏ sớm và ràng buộc Sakoe-Chiba, nâng cao hiệu quả tìm kiếm chuỗi con tương tự.  
- Thực nghiệm trên các bộ dữ liệu thực tế cho thấy phương pháp có thể xử lý chuỗi dài đến hàng chục nghìn điểm với độ chính xác và thời gian chấp nhận được.  
- Phép kết chuỗi con có tính giao hoán tương đối, mở ra hướng nghiên cứu mới trong khai phá dữ liệu chuỗi thời gian.  
- Đề xuất mở rộng nghiên cứu cho dữ liệu luồng và ứng dụng trong các lĩnh vực thực tiễn như phát hiện đạo nhạc, phân tích tài chính và y tế.

Hành động tiếp theo là triển khai áp dụng phương pháp trong các dự án thực tế và nghiên cứu mở rộng để xử lý dữ liệu chuỗi thời gian dạng luồng, đồng thời đào tạo nhân lực chuyên môn về lĩnh vực này.

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

CHƯƠNG 1. TỔNG QUAN VỀ ĐỀ TÀI. KHAI PHÁ DỮ LIỆU CHUỖI THỜI GIAN. Dữ liệu lớn.

Dữ liệu chuỗi thời gian. CÁC BÀI TOÁN LIÊN QUAN ĐẾN DỮ LIỆU CHUỖI THỜI GIAN. BÀI TOÁN KẾT CHUỖI CON TRÊN DỮ LIỆU CHUỖI THỜI GIAN. Ý NGHĨA BÀI TOÁN KẾT CHUỖI CON.

MỤC TIÊU VÀ NHIỆM VỤ CỦA ĐỀ TÀI. CÁC KẾT QUẢ ĐẠT ĐƯỢC. BỐ CỤC LUẬN VĂN. CÁC CÔNG TRÌNH LIÊN QUAN.

CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN ĐỘ ĐO TƯƠNG TỰ. Phương pháp xoắn thời gian động (Dynamic Time Warping). Phương pháp chuỗi con chung dài nhất. CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN KẾT CHUỖI CON.

Phân đoạn chuỗi thời gian nhờ các điểm cực trị quan trọng. Phương pháp kết chuỗi con trực tiếp (nested loop join). Phương pháp kết chuỗi con trên dữ liệu đã lập chỉ mục (indexing). Phương pháp kết chuỗi con dựa trên các phân đoạn không đồng nhất (non-uniform segment).

Phương pháp đề nghị cho bài toán kết chuỗi con. ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG. RÀNG BUỘC ĐƯỜNG XOẮN ĐỘ ĐO XOẮN THỜI GIAN ĐỘNG. Ràng buộc Sakoe-Chiba.

Ràng buộc hình bình hành Itakura. KỸ THUẬT TỪ BỎ SỚM KHI TÍNH KHOẢNG CÁCH DTW. CÁC ĐIỂM CỰC TRỊ QUAN TRỌNG. Điểm cực trị thông thường (extreme points).

Điểm cực trị quan trọng (important extrema). PHƯƠNG PHÁP ĐỀ NGHỊ. KHÁI QUÁT BÀI TOÁN KẾT CHUỖI CON. HỆ THỐNG ĐỀ NGHỊ CHO BÀI TOÁN KẾT CHUỖI CON.

QUÁ TRÌNH CHUẨN HÓA DỮ LIỆU. QUÁ TRÌNH PHÂN ĐOẠN CHUỖI THỜI GIAN. QUÁ TRÌNH KẾT CHUỖI CON. MÔI TRƯỜNG THỰC NGHIỆM.

DỮ LIỆU THỰC NGHIỆM. CÁC THAM SỐ ƯỚC LƯỢNG. PHƯƠNG PHÁP THỰC NGHIỆM. THỰC NGHIỆM VỀ CÁC CỰC TRỊ QUAN TRỌNG.

THỰC NGHIỆM VỀ BÀI TOÁN SO TRÙNG CHUỖI CON. THỰC NGHIỆM SO SÁNH GIẢI THUẬT KẾT CHUỖI CON DÙNG CỬA SỔ TRƯỢT TỪNG ĐIỂM VỚI CỬA SỔ TRƯỢT TỪNG ĐOẠN. THỰC NGHIỆM KIỂM CHỨNG TÍNH CHẤT GIAO HOÁN CỦA PHÉP KẾT TRÊN DỮ LIỆU CHUỖI THỜI GIAN. TỔNG KẾT NỘI DUNG CỦA LUẬN VĂN.

NHỮNG ĐÓNG GÓP CỦA ĐỀ TÀI. HƯỚNG PHÁT TRIỂN .66 TÀI LIỆU THAM KHẢO. 67 BẢNG THUẬT NGỮ ANH - VIỆT VÀ TỪ VIẾT TẮT. A TÁC VỤ KẾT DÙNG ĐỘ ĐO EUCLID VÀ DTW.

C x DANH MỤC HÌNH Hình 1. Dữ liệu chuỗi thời gian đơn biến ghi nhận giá chứng khoán. Dữ liệu chuỗi thời gian đa biến ghi nhận vị trí. So trùng toàn chuỗi.

So trùng chuỗi con. Tìm kiếm k láng giềng gần nhất. Một số độ đo Minkowski phổ biến (nguồn [23]). Cách ánh xạ cặp điểm trong độ đo Euclid và độ đo DTW (nguồn [9]).

Kỹ thuật từ bỏ sớm trong tính khoảng cách DTW (nguồn [28]). Phương pháp chuỗi con chung dài nhất (nguồn [1]). Các loại cực trị: nghiêm cách (hình bên trái), trái và phải (hình giữa), và cực trị phẳng (hình bên phải). Tổng quan về công trình của Yi.

Nhánh bên phải là mô hình kết chuỗi con dựa trên các phân đoạn không đồng nhất (nguồn [16]). Cây thứ bậc của quá trình phân đoạn không đồng nhất (nguồn [16]). Cách tính khoảng cách xoắn thời gian động. A) Hai chuỗi thời gian 𝑄 và 𝐶.

B) Ma trận tính DTW. C) Kết quả ánh xạ điểm trong DTW (nguồn [7]). Đồ thị biểu diễn hai chuỗi thời gian. Ma trận tính DTW cho hai chuỗi thời gian.

Ràng buộc Sakoe-Chiba (nguồn [5]). Ràng buộc Itakura (nguồn [8]). Kỹ thuật từ bỏ sớm khi tính DTW hai chuỗi thời gian (nguồn [10]). Từ bỏ sớm trong khoảng cách xoắn thời gian động (a) Tính bước đầu tiên và kiểm tra có vượt quá hay không; (b) Tính lề của ma trận; (c) Tính thân của ma trận sử dụng từ bỏ sớm; (d) So sánh kỹ thuật từ bỏ sớm với cách tính thông thường.

Các loại cực trị: nghiêm cách (trái), trái và phải (giữa), và cực trị phẳng (phải) (nguồn [17][18]). Các cực trị thông thường tìm được theo Mã giả 1 (nguồn [18]). Khuyết điểm của điểm cực trị thông thường. Bốn loại cực tiểu quan trọng: nghiêm cách (hình phía trên bên trái), trái và phải (hình phía trên bên phải), phẳng (hình phía dưới) (nguồn [18]) .12: Các cực trị quan trọng được tìm thấy theo giải thuật (nguồn [18]).

Kiến trúc bài toán kết chuỗi con. Dữ liệu chưa chuẩn hóa có đường căn bản bất kỳ. Dữ liệu đã chuẩn hóa có đường căn bản 𝑥 = 0. Sơ đồ tổng hợp quá trình chuẩn hóa dữ liệu.

Tham số 𝑅 giúp xác định các điểm cực trị quan trọng (nguồn [18]). Điểm cực trị quan trọng tìm được trên dữ liệu Chromosome. Điểm cực trị quan trọng tìm được trên dữ liệu Stock. Các điểm cực trị quan trọng (nguồn [18]).

Cửa sổ trượt trong giai đoạn kết chuỗi con (nguồn [12]). Các cực trị được xác định trên dữ liệu Chromosome độ dài 128. Các cực trị được xác định trên dữ liệu Runoff độ dài 204. Các cực trị được xác định trên dữ liệu Chromosome độ dài 1000.

Các điểm cực trị được xác định trên dữ liệu Eeg độ dài 15000. Các điểm cực trị được xác định trên dữ liệu Stock độ dài 500. Các cực trị tìm được trên dữ liệu Power_Demand_Italy độ dài 10000. Các điểm cực trị được xác định trên dữ liệu Koski độ dài 120000.

Các điểm cực trị được xác định trên dữ liệu Power độ dài 10000. Kết quả so trùng chuỗi con trên dữ liệu Stock. Kết quả so trùng chuỗi con trên dữ liệu Runoff chiều dài 204. Kết quả so trùng chuỗi con trên dữ liệu Memory.

Kết quả so trùng chuỗi con trên dữ liệu Power_Demand_Italy. Kết quả so trùng chuỗi con trên dữ liệu Eeg độ dài 30000. Kết quả so trùng chuỗi con trên dữ liệu Chormosome độ dài 10000. Kết quả so trùng chuỗi con trên dữ liệu Power độ dài 10000.

Kết quả so trùng chuỗi con trên dữ liệu Chromosome_1 độ dài 128. Kết quả so trùng chuỗi con trên dữ liệu Koski_ecg độ dài 10000. Kết quả kết chuỗi con trên dữ liệu Runoff. Kết quả kết chuỗi con trên dữ liệu Chromosome_1 chiều dài 128.

Kết quả kết chuỗi con trên dữ liệu Power chiều dài 5000. Hệ thống kết chuỗi con .65 xii DANH MỤC GIẢI THUẬT Mã giả 1. Giải thuật xác định các điểm cực trị thông thường (nguồn [18][17]). Giải thuật xác định các điểm cực trị quan trọng (nguồn [18]).

Giải thuật xác định tham số R. Giải thuật so trùng chuỗi con đề xuất sử dụng độ đo DTW. Giải thuật kết chuỗi con được đề nghị .48 xiii DANH MỤC BẢNG BIỂU Bảng 1. Các loại dữ liệu thực nghiệm.

Giá trị tham số 𝑅 cho từng bộ dữ liệu. Tổng hợp thời gian thực thi tìm kiếm chuỗi con. So sánh giải thuật cửa sổ trượt từng điểm và cửa sổ trượt từng đoạn. Tổng hợp tỷ lệ sai số giao hoán của phép kết chuỗi con.

TỔNG QUAN VỀ ĐỀ TÀI Phần đầu của chương điểm qua một số khái niệm cơ bản liên quan đến đề tài như: dữ liệu chuỗi thời gian, các đặc điểm và các bài toán liên quan đến dữ liệu chuỗi thời gian, bài toán kết chuỗi con trên dữ liệu chuỗi thời gian. Phần thứ hai giới thiệu sơ lược về mục tiêu và nội dung của đề tài. Bên cạnh đó, phần này cũng nêu lên những nội dung chính trong nghiên cứu và các kết quả đạt được của luận văn. Phần cuối chương sẽ giới thiệu sơ lược về nội dung chính trong từng chương của toàn bộ luận văn.

KHAI PHÁ DỮ LIỆU CHUỖI THỜI GIAN 1. Dữ liệu lớn “Lấy mẫu ngẫu nhiên 4000 bức hình từ 15 tờ báo và tạp chí trên thế giới xuất bản trong giai đoạn 1974 – 1989 cho thấy có hơn 75% là các hình biểu diễn dữ liệu chuỗi thời gian.” -- Theo khảo sát của tác giả Tufte, E. Trong thời đại ngày nay, với sự ra đời và phát triển của máy tính và các thiết bị kỹ thuật số có hỗ trợ thu thập dữ liệu, những dữ liệu mà con người dùng để phục vụ cuộc sống của mình gần như đã được số hóa toàn bộ. Chúng được chuyển thành các đối tượng dữ liệu có nghĩa và lưu trữ trong máy tính mà con người có thể dễ dàng truy vấn khi cần thiết.

Tuy nhiên, các loại dữ liệu ngày càng tăng nhanh tạo nên khối lượng dữ liệu lớn (big data). Do đó, công tác khai phá dữ liệu (data mining) càng trở nên quan trọng và thu hút được nhiều nghiên cứu trên thế giới nhằm đáp ứng yêu cầu truy hồi thông tin (information retrieval) đúng lúc và đầy đủ khi cần thiết. 2 Một trong những loại kể trên là dữ liệu chuỗi thời gian (time series data). Dữ liệu chuỗi thời gian tồn tại trong nhiều ứng dụng thuộc nhiều lĩnh vực khác nhau như: kinh tế, tài chính, y tế, giáo dục, môi trường, địa lý, và sinh học, vân vân.

Việc hiểu và dẫn xuất được thông tin ẩn trong các dữ liệu chuỗi thời gian có một ý nghĩa lớn góp phần quyết định đến sự phát triển của lĩnh vực. Do đó, khai phá dữ liệu chuỗi thời gian (time series data mining) đóng vai trò quan trọng và nhận được sự quan tâm từ rất nhiều nhà nghiên cứu trên thế giới. Các bài toán liên quan đến dữ liệu chuỗi thời gian có thể kể đến như: phân lớp, gom cụm, dự báo, phát hiện mô-típ, phát hiện bất thường, khai phá luật kết hợp và nhiều bài toán cơ bản khác. Trước khi giới thiệu đặc điểm và chi tiết về các bài toán phổ biến trên dữ liệu chuỗi thời gian, một số khái niệm quan trọng cần được định nghĩa.

Dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian1 𝑋 là một tập hợp nhiều mẫu dữ liệu (data samples), mỗi mẫu là một bộ (𝑇, 𝑉) biểu diễn các giá trị được ghi nhận từ một tín hiệu liên tục qua thời gian. Trong đó, 𝑇 là thời điểm tiến hành quan sát, 𝑉 là giá trị quan sát. Ký hiệu chuỗi thời gian có dạng: 𝑋 = ((𝑇1 , 𝑉1 ), (𝑇2 , 𝑉2 ), … , (𝑇𝑛 , 𝑉𝑛 )) Với 𝑛 là số lần đo đạt lấy mẫu, 𝑇𝑖+1 > 𝑇1 , ∀𝑖. Phần tử 𝑋𝑖 là một véc-tơ trong không gian 𝑘 chiều có dạng: 𝑋𝑖 = (𝑥𝑖1 , 𝑥𝑖2 , … , 𝑥𝑖𝑘 ) Nếu 𝑘 = 1 thì 𝑋 được gọi là chuỗi thời gian đơn biến (uni-variate time series).