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 Sử Dụng Độ Đo Xoắn Thời Gian Động Và Cấu Trúc Chỉ Mục TSTree

• Tác giả: Ngô Thảo Chương
• Người hướng dẫn: PGS. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa, Đại học Quốc gia TP. Hồ Chí Minh
• 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

• 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

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.

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, khối lượng dữ liệu chuỗi thời gian toàn cầu tăng trưởng với tốc độ nhanh chóng, đòi hỏi các phương pháp khai phá dữ liệu hiệu quả để xử lý và phân tích. 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 giúp phát hiện các xu hướng, dự báo và phân loại dữ liệu chính xác hơn.

Tuy nhiên, việc tính toán khoảng cách giữa các chuỗi con để phát hiện motif gặp nhiều thách thức, đặc biệt khi sử dụng độ đo Euclid truyền thống, vốn không phù hợp với dữ liệu chuỗi thời gian nhiều chiều và dễ bị ảnh hưởng bởi nhiễu. Độ đo xoắn thời gian động (Dynamic Time Warping - DTW) được xem là giải pháp hiệu quả hơn nhờ khả năng đo lường khoảng cách chính xác giữa các chuỗi có biến dạng về thời gian. Song song đó, cấu trúc chỉ mục TS-Tree được phát triển nhằm tăng tốc quá trình truy vấn và tìm kiếm trên dữ liệu chuỗi thời gian lớn.

Luận văn tập trung nghiên cứu 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 với cấu trúc chỉ mục TS-Tree. Phạm vi nghiên cứu bao gồm các bộ dữ liệu mẫu đại diện cho nhiều lĩnh vực khác nhau, với mục tiêu nâng cao tốc độ tìm kiếm và độ chính xác so với phương pháp tìm kiếm chân phương (Brute Force). Kết quả nghiên cứu có ý nghĩa quan trọng trong việc phát triển các ứng dụng khai phá dữ liệu chuỗi thời gian, góp phần nâng cao hiệu quả xử lý dữ liệu lớn trong thực 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 hai lý thuyết và mô hình chính:

1. Độ đo xoắn thời gian động (Dynamic Time Warping - DTW):
   DTW là phương pháp đo khoảng cách giữa hai chuỗi thời gian cho phép biến dạng về thời gian, giúp phát hiện các mẫu tương tự ngay cả khi chúng bị lệch hoặc kéo dài. DTW được tính bằng cách xây dựng ma trận khoảng cách giữa các điểm dữ liệu và tìm đường xoắn có chi phí tối thiểu. Mặc dù DTW cho kết quả chính xác hơn so với độ đo Euclid, nhưng chi phí tính toán cao với độ phức tạp O(m*n), trong đó m và n là chiều dài hai chuỗi.

2. Cấu trúc chỉ mục TS-Tree:
   TS-Tree là cấu trúc chỉ mục dạng cây được thiết kế đặc biệt cho dữ liệu chuỗi thời gian. Nó lưu trữ thông tin 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 tăng tốc quá trình tìm kiếm bằng cách tỉa nhánh hiệu quả. TS-Tree hỗ trợ tốt cho độ đo DTW nhờ khả năng tính toán khoảng cách chặn dưới (mindist) giữa chuỗi truy vấn và các nút trong cây, giảm thiểu số phép tính DTW cần thiết.

Các khái niệm chính được sử dụng bao gồm: chuỗi thời gian, chuỗi con (subsequence), motif, trùng khớp không tầm thường (non-trivial match), rời rạc hóa dữ liệu (symbolic aggregate approximation - SAX), và các ràng buộc toàn cục trong DTW như dải Sakoe-Chiba và hình bình hành Itakura.

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

Phương pháp nghiên cứu chủ yếu dựa trên thực nghiệm và so sánh hiệu quả giữa giải thuật đề xuất và giải thuật tìm kiếm chân phương (Brute Force):

• Nguồn dữ liệu:
  Sử dụng các bộ dữ liệu mẫu chuỗi thời gian đa dạng về kích thước và lĩnh vực như Small Power Italia, Small ECG, Small EEG, Memory, TEK17, Power, ECG, Power Italia. Các bộ dữ liệu này có kích thước chuỗi con từ 5 đến 25 điểm, đại diện cho các ứng dụng thực tế trong y học, điện năng và sinh học.

• Phương pháp phân tích:

  • Xây dựng cấu trúc chỉ mục TS-Tree cho toàn bộ chuỗi thời gian.
  • Áp dụng giải thuật tìm kiếm motif dựa trên độ đo DTW kết hợp TS-Tree (BF_DTW_TS-Tree).
  • So sánh với giải thuật tìm kiếm motif chân phương (BF_DTW) về thời gian thực thi và số lượng motif tìm được.
  • Đánh giá độ chính xác và tốc độ thông qua các chỉ số thời gian tìm kiếm và số thể hiện motif.

• Timeline nghiên cứu:
  Quá trình nghiên cứu được thực hiện trong khoảng thời gian từ đầu năm đến tháng 7 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 BF_DTW_TS-Tree cho thấy thời gian tìm kiếm nhanh hơn đáng kể so với giải thuật BF_DTW truyền thống. Ví dụ, trên bộ dữ liệu Power Italia kích thước 25, thời gian thực thi giảm khoảng 30-40%. Trên các bộ dữ liệu nhỏ hơn như Small ECG và Small Power, thời gian giảm trung bình từ 20-35%.

2. Độ chính xác tìm kiếm motif được duy trì:
   Số lượng motif tìm được bởi BF_DTW_TS-Tree tương đương hoặc cao hơn so với BF_DTW, chứng tỏ cấu trúc TS-Tree không làm giảm độ chính xác mà còn giúp loại bỏ các phép tính thừa, tập trung vào các ứng viên tiềm năng.

3. Khả năng thích nghi với chuỗi dữ liệu lớn:
   Thời gian tìm kiếm không phụ thuộc nhiều vào kích thước chuỗi con, cho thấy giải thuật có khả năng mở rộng tốt với dữ liệu chuỗi thời gian dài và phức tạp.

4. Hiệu quả tỉa nhánh trong TS-Tree:
   Việc lưu trữ thông tin cận trên và cận dưới trong các nút TS-Tree giúp giảm số lượng nút cần duyệt, từ đó giảm số phép tính DTW tốn kém. Các phép tính mindist cho phép loại bỏ nhanh các nhánh không phù hợp.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện hiệu suất là do TS-Tree tận dụng được đặc điểm rời rạc hóa và thông tin mô tả trong các nút để tỉa nhánh hiệu quả, giảm thiểu số phép tính DTW phức tạp. So với các nghiên cứu trước đây chỉ sử dụng độ đo Euclid hoặc cấu trúc chỉ mục R*-Tree, TS-Tree kết hợp DTW mang lại độ chính xác cao hơn và tốc độ xử lý nhanh hơn.

Kết quả cũng phù hợp với các nghiên cứu ứng dụng DTW trong nhận dạng mẫu và phân loại chuỗi thời gian, đồng thời mở ra hướng phát triển các giải thuật tìm kiếm motif hiệu quả hơn trong tương lai. Việc áp dụng TS-Tree giúp giải quyết bài toán tìm kiếm motif trong dữ liệu lớn, đa chiều và có biến dạng về thời gian, rất phù hợp với các ứng dụng thực tế như phân tích tín hiệu y tế, dự báo tài chính và xử lý dữ liệu đa phương tiện.

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à tỷ lệ giảm thời gian.

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

1. Phát triển giải thuật tìm kiếm motif đa cấp:
   Áp dụng kỹ thuật phân cấp trong TS-Tree để tăng khả năng xử lý dữ liệu chuỗi thời gian rất lớn, giảm thiểu độ phức tạp tính toán. Mục tiêu giảm thời gian tìm kiếm thêm 20% trong vòng 1 năm, do nhóm nghiên cứu chuyên ngành khoa học máy tính thực hiện.

2. Tối ưu hóa rời rạc hóa và tham số DTW:
   Nghiên cứu lựa chọn tham số ràng buộc toàn cục (Sakoe-Chiba, Itakura) và kích thước cửa sổ rời rạc hóa để cân bằng giữa độ chính xác và tốc độ. Mục tiêu cải thiện độ chính xác motif lên trên 95% trong 6 tháng, do nhóm phát triển thuật toán đảm nhiệm.

3. Mở rộng ứng dụng vào dữ liệu thực tế đa lĩnh vực:
   Áp dụng giải thuật vào các bộ dữ liệu chuỗi thời gian thực tế trong y tế, tài chính, khí tượng để đánh giá hiệu quả và điều chỉnh thuật toán phù hợp. Thời gian thực hiện dự kiến 1 năm, phối hợp với các chuyên gia ngành liên quan.

4. Xây dựng công cụ phần mềm hỗ trợ khai phá dữ liệu chuỗi thời gian:
   Phát triển phần mềm tích hợp giải thuật tìm kiếm motif dựa trên TS-Tree và DTW, cung cấp giao diện thân thiện cho người dùng cuối. Mục tiêu hoàn thành trong 18 tháng, do nhóm kỹ thuật phần mềm và nghiên cứu phối hợp thực hiện.

Đố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ó thể ứng dụng các phương pháp và giải thuật trong luận văn để 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 học máy và trí tuệ nhân tạo.

2. Chuyên gia phân tích dữ liệu và kỹ sư dữ liệu:
   Sử dụng cấu trúc chỉ mục TS-Tree và độ đo DTW để tối ưu hóa quá trình truy vấn và phân tích dữ liệu chuỗi thời gian trong các hệ thống lớn, nâng cao hiệu quả xử lý.

3. Người làm việc trong lĩnh vực y tế và sinh học:
   Áp dụng giải thuật để phân tích dữ liệu điện tâm đồ, điện não đồ, giúp phát hiện các mẫu bệnh lý hoặc xu hướng sức khỏe quan trọng.

4. Chuyên gia tài chính và kinh tế:
   Tận dụng kỹ thuật tìm kiếm motif để phát hiện các mẫu biến động giá cổ phiếu, dự báo xu hướng thị trường, hỗ trợ quyết định đầu tư.

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 đo khoảng cách giữa các chuỗi thời gian có biến dạng về thời gian, giúp phát hiện các mẫu tương tự ngay cả khi chúng bị lệch hoặc kéo dài, trong khi Euclid chỉ đo khoảng cách điểm đối điểm, dễ bị sai lệch do nhiễu.

2. TS-Tree giúp tăng tốc tìm kiếm motif như thế nào?
   TS-Tree lưu trữ thông tin cận trên và cận dưới của các chuỗi con đã rời rạc hóa, cho phép tỉa nhánh hiệu quả trong quá trình duyệt cây, giảm số phép tính DTW phức tạp cần thực hiện.

3. Giải thuật BF_DTW_TS-Tree có thể áp dụng cho dữ liệu lớn không?
   Có, giải thuật này thích nghi tốt với dữ liệu chuỗi thời gian lớn nhờ cấu trúc chỉ mục TS-Tree giúp giảm thiểu số phép tính khoảng cách, đồng thời thời gian tìm kiếm không phụ thuộc nhiều vào kích thước chuỗi con.

4. Các tham số quan trọng trong DTW và TS-Tree là gì?
   Các tham số như kích thước cửa sổ rời rạc hóa (PAA), số lượng ký tự trong SAX, và ràng buộc toàn cục (Sakoe-Chiba, Itakura) ảnh hưởng đến độ chính xác và tốc độ tìm kiếm, cần được điều chỉnh phù hợp với từng bộ dữ liệu.

5. Giải thuật này có thể áp dụng cho các lĩnh vực nào ngoài khoa học máy tính?
   Giải thuật phù hợp với nhiều lĩnh vực như y tế (phân tích tín hiệu sinh học), tài chính (dự báo thị trường), khí tượng (dự báo thời tiết), và xử lý đa phương tiện (nhận dạng mẫu âm thanh, hình ảnh).

Kết luận

• Luận văn đã đề xuất và 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 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 truyền thống.
• Thực nghiệm trên nhiều bộ dữ liệu mẫu cho thấy giải thuật đề xuất giảm thời gian tìm kiếm từ 20-40% trong khi vẫn duy trì độ chính xác cao.
• Cấu trúc TS-Tree giúp tỉa nhánh hiệu quả, giảm số phép tính DTW phức tạp, thích nghi tốt với dữ liệu chuỗi thời gian lớn và đa chiều.
• Nghiên cứu mở ra hướng phát triển các giải thuật tìm kiếm motif đa cấp, tối ưu tham số và ứng dụng rộng rãi trong nhiều lĩnh vực thực tế.
• Đề nghị các nhà nghiên cứu và chuyên gia ứng dụng tiếp tục phát triển và triển khai giải thuật trong các hệ thống khai phá dữ liệu chuỗi thời gian lớn.

Hành động tiếp theo: Khuyến khích nghiên cứu mở rộng giải thuật, xây dựng công cụ phần mềm hỗ trợ và áp dụng vào các bộ dữ liệu thực tế đa dạng nhằm nâng cao giá trị ứng dụng.