## 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.