Cấu trúc Chỉ Mục TS-Tree Cho Dữ Liệu Chuỗi Thời Gian Với Độ Đo Xoắn Thời Gian Động

Luận văn về cấu trúc chỉ mục TS-Tree, giải pháp tối ưu cho dữ liệu chuỗi thời gian. Nghiên cứu độ đo xoắn thời gian động (DTW) giúp tăng tốc tìm kiếm và độ chính xác.

• Tác giả: Nguyễn Minh Hiếu
• 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: Cấu trúc chỉ mục TS-Tree cho dữ liệu chuỗi thời gian với độ đ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: 2015
• Địa điểm: Tp. Hồ Chí Minh

Tóm tắt

I. TS Tree là gì Tổng quan cấu trúc chỉ mục cho dữ liệu

Trong kỷ nguyên số, dữ liệu chuỗi thời gian xuất hiện tràn lan trong mọi lĩnh vực, từ khoa học kỹ thuật đến kinh tế và tài chính. Việc khai thác hiệu quả dữ liệu chuỗi thời gian đóng vai trò then chốt. Một trong những bài toán quan trọng nhất là tìm kiếm tương tự, đòi hỏi các cấu trúc chỉ mục mạnh mẽ và nhanh chóng. TS-Tree nổi lên như một giải pháp tiềm năng, được thiết kế đặc biệt để đáp ứng yêu cầu này. Tuy nhiên, các cấu trúc chỉ mục truyền thống như R*-Tree thường gặp khó khăn với dữ liệu đa chiều và độ đo Euclid cứng nhắc. Luận văn này sẽ tập trung vào cấu trúc chỉ mục TS-Tree, một giải pháp hứa hẹn để tăng tốc tìm kiếm tương tự và nâng cao độ chính xác khi kết hợp với độ đo xoắn thời gian động (DTW). Nghiên cứu này sẽ so sánh hiệu quả của TS-Tree so với R*-Tree, làm nổi bật những ưu điểm vượt trội của TS-Tree trong bài toán tìm kiếm tương tự dữ liệu chuỗi thời gian.

1.1. Giới thiệu chung về dữ liệu chuỗi thời gian Time Series Data

Dữ liệu chuỗi thời gian, xuất hiện phổ biến trong thực tế, đòi hỏi các phương pháp xử lý đặc biệt. Dữ liệu này bao gồm một chuỗi các giá trị được đo lường theo thời gian, thể hiện sự biến đổi của một hiện tượng nào đó. Ứng dụng của dữ liệu chuỗi thời gian rất đa dạng, từ phân tích thị trường chứng khoán đến giám sát sức khỏe bệnh nhân và dự báo thời tiết. Việc khai thác thông tin từ dữ liệu chuỗi thời gian đòi hỏi các kỹ thuật phức tạp, bao gồm phân tích xu hướng, dự đoán tương lai và tìm kiếm các mẫu tương tự. Các phương pháp chỉ mục hiệu quả đóng vai trò quan trọng trong việc tăng tốc quá trình tìm kiếm và khai thác dữ liệu chuỗi thời gian, cho phép các nhà nghiên cứu và doanh nghiệp đưa ra quyết định chính xác và kịp thời.

1.2. Tầm quan trọng của bài toán tìm kiếm tương tự Time Series

Trong khai phá dữ liệu chuỗi thời gian, bài toán tìm kiếm tương tự giữ một vị trí then chốt. Khả năng tìm kiếm các mẫu tương tự trong một tập dữ liệu lớn có thể giúp khám phá ra các xu hướng tiềm ẩn, dự đoán các sự kiện tương lai và phát hiện các dị thường. Các ứng dụng của bài toán này rất rộng rãi, từ phát hiện gian lận trong giao dịch tài chính đến tìm kiếm các đoạn nhạc giống nhau và dự đoán nhu cầu năng lượng. Để giải quyết hiệu quả bài toán tìm kiếm tương tự, cần có các cấu trúc chỉ mục và các thuật toán tìm kiếm tối ưu. TS-Tree được kỳ vọng sẽ là một giải pháp hiệu quả, cho phép tìm kiếm nhanh chóng và chính xác các mẫu tương tự trong dữ liệu chuỗi thời gian.

II. Thách thức và vấn đề trong Indexing Time Series Data

Việc xây dựng cấu trúc chỉ mục hiệu quả cho dữ liệu chuỗi thời gian đối mặt với nhiều thách thức. Dữ liệu thường có kích thước lớn và chiều cao, đòi hỏi các phương pháp chỉ mục có khả năng mở rộng tốt. Hơn nữa, các độ đo khoảng cách truyền thống như Euclid có thể không phù hợp với dữ liệu chuỗi thời gian, do không tính đến sự biến dạng thời gian. Các cấu trúc chỉ mục hiện có như R*-Tree và M-Tree có những hạn chế nhất định khi xử lý dữ liệu đa chiều và độ đo không gian phức tạp. TS-Tree được thiết kế để giải quyết những vấn đề này bằng cách sử dụng các kỹ thuật rời rạc hóa và thông tin mô tả để giảm kích thước chỉ mục và tăng tốc quá trình tìm kiếm. Nghiên cứu này sẽ khám phá cách TS-Tree vượt qua những thách thức này và cung cấp một giải pháp hiệu quả hơn cho bài toán tìm kiếm tương tự.

2.1. Hạn chế của độ đo Euclid cho dữ liệu chuỗi thời gian

Độ đo Euclid, một trong những độ đo khoảng cách phổ biến nhất, có những hạn chế khi áp dụng cho dữ liệu chuỗi thời gian. Độ đo này nhạy cảm với sự khác biệt về thời gian giữa hai chuỗi, ngay cả khi chúng có hình dạng tương tự. Điều này có thể dẫn đến kết quả tìm kiếm không chính xác, đặc biệt là khi dữ liệu bị biến dạng thời gian. Ví dụ: hai chuỗi thời gian có thể biểu diễn cùng một hiện tượng, nhưng bị trễ thời gian do sự khác biệt về tốc độ thu thập dữ liệu. Trong trường hợp này, độ đo Euclid có thể đánh giá chúng là khác biệt, mặc dù chúng thực chất là tương tự. Do đó, cần có các độ đo khoảng cách khác, như độ đo xoắn thời gian động (DTW), để xử lý sự biến dạng thời gian và cung cấp kết quả tìm kiếm chính xác hơn.

2.2. Khó khăn khi xây dựng chỉ mục cho dữ liệu đa chiều

Việc xây dựng chỉ mục cho dữ liệu đa chiều là một thách thức lớn trong lĩnh vực khai phá dữ liệu. Khi số chiều tăng lên, không gian dữ liệu trở nên thưa thớt, và các phương pháp chỉ mục truyền thống như R*-Tree trở nên kém hiệu quả. Điều này là do số lượng nút cần truy cập để tìm kiếm một đối tượng cụ thể tăng lên đáng kể. Hơn nữa, việc tính toán khoảng cách giữa các đối tượng trong không gian đa chiều trở nên tốn kém hơn về mặt tính toán. Để giải quyết những vấn đề này, cần có các kỹ thuật giảm chiều và các cấu trúc chỉ mục đặc biệt, được thiết kế để xử lý hiệu quả dữ liệu đa chiều. TS-Tree được kỳ vọng sẽ là một giải pháp tiềm năng, nhờ khả năng giảm chiều dữ liệu và tổ chức chỉ mục một cách hiệu quả.

III. Phương pháp TS Tree và độ đo xoắn thời gian động DTW

Để khắc phục những hạn chế của các phương pháp truyền thống, luận văn này tập trung vào cấu trúc chỉ mục TS-Tree kết hợp với độ đo xoắn thời gian động (DTW). DTW là một phương pháp mạnh mẽ để tính toán sự tương đồng giữa hai chuỗi thời gian, cho phép sự biến dạng thời gian và cung cấp kết quả chính xác hơn so với độ đo Euclid. TS-Tree sử dụng các kỹ thuật rời rạc hóa và thông tin mô tả để giảm kích thước chỉ mục và tăng tốc quá trình tìm kiếm. Bằng cách kết hợp TS-Tree và DTW, chúng ta có thể đạt được hiệu suất tìm kiếm cao và độ chính xác tốt, đặc biệt là trong các ứng dụng mà dữ liệu chuỗi thời gian bị biến dạng thời gian.

3.1. Chi tiết cấu trúc chỉ mục TS Tree

TS-Tree là một cấu trúc chỉ mục dựa trên cây, được thiết kế đặc biệt cho dữ liệu chuỗi thời gian. Cấu trúc này sử dụng các kỹ thuật rời rạc hóa và thông tin mô tả để giảm kích thước chỉ mục và tăng tốc quá trình tìm kiếm. Mỗi nút trong TS-Tree chứa một tập hợp các thành phần phân tách và thông tin mô tả, cho phép ước tính khoảng cách giữa các chuỗi thời gian một cách nhanh chóng. Khi một chuỗi thời gian mới được chèn vào TS-Tree, nó sẽ được so sánh với các thành phần phân tách trong các nút, và được chèn vào nhánh phù hợp. Quá trình tìm kiếm trong TS-Tree tương tự, với các nhánh không liên quan bị loại bỏ dựa trên thông tin mô tả.

3.2. Ưu điểm của DTW so với các độ đo khác cho Time Series

Độ đo xoắn thời gian động (DTW) có nhiều ưu điểm so với các độ đo khoảng cách khác khi áp dụng cho dữ liệu chuỗi thời gian. DTW cho phép sự biến dạng thời gian, có nghĩa là nó có thể tìm thấy các mẫu tương tự ngay cả khi chúng không hoàn toàn đồng bộ về thời gian. Điều này đặc biệt hữu ích trong các ứng dụng mà dữ liệu chuỗi thời gian bị ảnh hưởng bởi sự trễ thời gian hoặc sự thay đổi tốc độ. Hơn nữa, DTW không yêu cầu các chuỗi thời gian phải có cùng độ dài, cho phép so sánh các chuỗi có độ dài khác nhau. Tuy nhiên, DTW có độ phức tạp tính toán cao hơn so với các độ đo khác, đòi hỏi các kỹ thuật tối ưu để tăng tốc quá trình tính toán.

IV. Hệ thống so trùng mẫu sử dụng TS Tree và DTW Cách triển khai

Luận văn này trình bày một hệ thống so trùng mẫu sử dụng TS-Tree và DTW để tìm kiếm các mẫu tương tự trong dữ liệu chuỗi thời gian. Hệ thống bao gồm các thành phần chính: lập chỉ mục, chuẩn hóa dữ liệu, thu giảm số chiều, rời rạc hóa dữ liệu và so trùng mẫu. Thành phần lập chỉ mục xây dựng TS-Tree từ dữ liệu chuỗi thời gian. Thành phần so trùng mẫu sử dụng TS-Tree và DTW để tìm kiếm các mẫu tương tự với mẫu truy vấn do người dùng cung cấp. Hệ thống được thiết kế để dễ dàng mở rộng và tùy chỉnh, cho phép các nhà nghiên cứu và doanh nghiệp áp dụng nó cho các ứng dụng khác nhau.

4.1. Chuẩn hóa dữ liệu và giảm chiều với PAA

Để cải thiện hiệu suất của hệ thống, dữ liệu chuỗi thời gian được chuẩn hóa trước khi được đưa vào TS-Tree. Quá trình chuẩn hóa đảm bảo rằng tất cả các chuỗi thời gian có cùng phạm vi giá trị, giúp giảm sự ảnh hưởng của sự khác biệt về tỷ lệ. Hơn nữa, kỹ thuật thu giảm số chiều PAA (Piecewise Aggregate Approximation) được sử dụng để giảm kích thước của dữ liệu và tăng tốc quá trình lập chỉ mục và so trùng mẫu. PAA chia chuỗi thời gian thành các đoạn bằng nhau và tính giá trị trung bình của mỗi đoạn, tạo ra một phiên bản rút gọn của chuỗi ban đầu.

4.2. Rời rạc hóa dữ liệu với SAX Symbolic Aggregate Approximation

Để giảm kích thước của chỉ mục và tăng tốc quá trình tìm kiếm, kỹ thuật rời rạc hóa dữ liệu SAX (Symbolic Aggregate approXimation) được sử dụng. SAX chuyển đổi chuỗi thời gian thành một chuỗi các ký hiệu, mỗi ký hiệu đại diện cho một phạm vi giá trị. Bằng cách sử dụng SAX, có thể giảm đáng kể kích thước của dữ liệu và tăng tốc quá trình tìm kiếm. Hơn nữa, SAX cho phép sử dụng các thuật toán tìm kiếm chuỗi hiệu quả, giúp tìm kiếm các mẫu tương tự một cách nhanh chóng.

V. Kết quả thực nghiệm và đánh giá hiệu năng của TS Tree

Để đánh giá hiệu quả của TS-Tree, các thực nghiệm đã được thực hiện trên nhiều tập dữ liệu khác nhau, bao gồm dữ liệu chứng khoán, dữ liệu năng lượng, dữ liệu điện não đồ và dữ liệu nhu cầu năng lượng điện. Các kết quả thực nghiệm cho thấy rằng TS-Tree có hiệu suất tốt hơn so với R*-Tree trong hầu hết các trường hợp. Đặc biệt, TS-Tree có thời gian lập chỉ mục ngắn hơn, số lần truy xuất nút ít hơn và thời gian đáp ứng nhanh hơn so với R*-Tree. Các kết quả này chứng minh rằng TS-Tree là một cấu trúc chỉ mục hiệu quả cho dữ liệu chuỗi thời gian.

5.1. So sánh thời gian lập chỉ mục giữa TS Tree và R Tree

Thời gian lập chỉ mục là một yếu tố quan trọng trong việc đánh giá hiệu quả của một cấu trúc chỉ mục. Các thực nghiệm cho thấy rằng TS-Tree có thời gian lập chỉ mục ngắn hơn đáng kể so với R*-Tree trên hầu hết các tập dữ liệu. Điều này là do TS-Tree sử dụng các kỹ thuật rời rạc hóa và thông tin mô tả để giảm kích thước của chỉ mục, giúp quá trình lập chỉ mục diễn ra nhanh chóng hơn. Kết quả này cho thấy rằng TS-Tree là một lựa chọn tốt hơn cho các ứng dụng mà thời gian lập chỉ mục là một yếu tố quan trọng.

5.2. Đánh giá khả năng truy vấn và thời gian đáp ứng của TS Tree

Khả năng truy vấn và thời gian đáp ứng là các yếu tố quan trọng khác trong việc đánh giá hiệu quả của một cấu trúc chỉ mục. Các thực nghiệm cho thấy rằng TS-Tree có số lần truy xuất nút ít hơn và thời gian đáp ứng nhanh hơn so với R*-Tree trên hầu hết các tập dữ liệu. Điều này là do TS-Tree sử dụng các kỹ thuật rời rạc hóa và thông tin mô tả để loại bỏ các nhánh không liên quan trong quá trình tìm kiếm, giúp tìm kiếm các mẫu tương tự một cách nhanh chóng. Kết quả này cho thấy rằng TS-Tree là một lựa chọn tốt hơn cho các ứng dụng mà thời gian truy vấn là một yếu tố quan trọng.

VI. Tổng kết và hướng phát triển của cấu trúc TS Tree cho Time Series

Luận văn này đã trình bày một nghiên cứu về cấu trúc chỉ mục TS-Tree cho dữ liệu chuỗi thời gian với độ đo xoắn thời gian động (DTW). Các kết quả thực nghiệm cho thấy rằng TS-Tree là một cấu trúc chỉ mục hiệu quả, có hiệu suất tốt hơn so với R*-Tree trong hầu hết các trường hợp. Trong tương lai, có thể nghiên cứu thêm về các kỹ thuật tối ưu hóa TS-Tree, như điều chỉnh các tham số của cấu trúc và sử dụng các phương pháp giảm chiều tiên tiến hơn. Hơn nữa, có thể áp dụng TS-Tree cho các ứng dụng khác nhau, như phân tích thị trường chứng khoán, giám sát sức khỏe bệnh nhân và dự báo thời tiết.

6.1. Những đóng góp của nghiên cứu về TS Tree và DTW

Nghiên cứu này đã đóng góp vào lĩnh vực khai phá dữ liệu chuỗi thời gian bằng cách trình bày một phân tích chi tiết về cấu trúc chỉ mục TS-Tree và độ đo xoắn thời gian động (DTW). Các kết quả thực nghiệm đã chứng minh rằng TS-Tree là một cấu trúc chỉ mục hiệu quả, có hiệu suất tốt hơn so với R*-Tree trong hầu hết các trường hợp. Hơn nữa, nghiên cứu này đã cung cấp một hệ thống so trùng mẫu sử dụng TS-Tree và DTW, cho phép các nhà nghiên cứu và doanh nghiệp áp dụng nó cho các ứng dụng khác nhau.

6.2. Các hướng nghiên cứu tiềm năng trong tương lai về TS Tree

Trong tương lai, có nhiều hướng nghiên cứu tiềm năng về TS-Tree. Một hướng là nghiên cứu các kỹ thuật tối ưu hóa TS-Tree, như điều chỉnh các tham số của cấu trúc và sử dụng các phương pháp giảm chiều tiên tiến hơn. Một hướng khác là nghiên cứu các biến thể của TS-Tree, được thiết kế để phù hợp với các loại dữ liệu chuỗi thời gian khác nhau. Hơn nữa, có thể áp dụng TS-Tree cho các ứng dụng khác nhau, như phân tích thị trường chứng khoán, giám sát sức khỏe bệnh nhân và dự báo thời tiết.

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

Chương 1: chương này giới thiệu tổng quan về đề tài, mục đích nghiên cứu của đề tài, tại sao lại chọn đề tài này và hướng nghiên cứu của đề tài 3 Cấu trúc chỉ mục TS-Tree trên dữ liệu thời gian với độ đo DTW  Chương 2: chương này tập trung nghiên cứu các lý thuyết liên quan cần tìm hiểu như: - Bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian - Độ đo DTW (dynamic time warping) và những cải tiến so với độ đo Euclid - Giới thiệu cấu trúc chỉ mục R*-tree và những hạn chế khi làm việc trên độ đo DTW - Giới thiệu tổng quan về cấu trúc chỉ mục TS-Tree  Chương 3: trong chương này tập trung nghiên cứu cấu trúc chỉ mục TS-Tree và những ưu điểm của nó trên độ đo DTW so với R*- tree - Cấu trúc của cấu trúc chỉ mục TS-Tree và các thao tác trên cây - Cấu trúc chỉ mục TS-Tree làm việc trên độ đo DTW - So sánh những ưu điểm của cấu trúc chỉ mục TS-Tree so với R*-tree  Chương 4: trình bày kiến trúc tổng thể và thực hiện hệ thống so trùng mẫu con. Chương này sẽ phân tích những vấn đề chính mà hệ thống cần phải giải quyết và một số chi tiết hiện thực của các thành phần quan trọng. Các nội dung được trình bày bao gồm cách thức lưu trữ dữ liệu, truy vấn chuỗi con dựa trên các cấu trúc chỉ mục.  Chương 5: nêu một số kết quả và nhận xét dựa trên các thực nghiệm.

Có bốn bộ dữ liệu được thu thập từ thực tế làm dữ liệu mẫu bao gồm dữ liệu chứng khoán, dữ liệu năng lượng, dữ liệu điện não đồ và dữ liệu nhu cầu điện năng của Italia.  Chương 6: điểm qua toàn bộ luận văn và nêu một số kết luận sau khi thực hiện đề tài bao gồm các công việc đã hoàn thành, đánh giá luận văn và hướng phát triển.  Phần tài liệu tham khảo, bảng phụ lục một số khái niệm liên quan và bảng thuật ngữ Anh-Việt đối chiếu. 4 Cấu trúc chỉ mục TS-Tree trên dữ liệu thời gian với độ đo DTW CHƯƠNG 2: CÁC CÔNG TRÌNH LIÊN QUAN VÀ LÝ THUYẾT NỀN TẢNG Chương này xin giới thiệu các kiến thức liên quan tới lĩnh vực tìm kiếm thông tin trên dữ liệu chuỗi thời gian.

Chúng tôi sẽ trình bày các kiến thức liên quan tới bài toán tìm kiếm tương tự, độ đo khoảng cách Euclid và cấu trúc chỉ mục R*-Tree, làm tiền đề để nghiên cứu cấu trúc chỉ mục TS-Tree trên dữ liệu chuỗi thời gian. Chúng tôi cũng đề cập tới độ đo xoắn thời gian động và việc áp dụng độ đo xoắn thời gian động trong bài toán tìm kiếm tương tự dữ liệu chuỗi thời gian 2.1 Bài toán tìm kiếm tương tự 2.1 Dữ liệu chuỗi thời gian (time series data) Chuỗi thời gian (time series) là một chuỗi trị số thực được ghi nhận tại những khoảng thời gian 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à một thời điểm xác định T= (t1,t2 ….) với ti thuộc R, còn X là giá trị quan sát được tại thời điểm T đó.

Lúc này nếu chúng ta xem xét các giá trị quan sát đó trong những khoảng thời gian bằng nhau với n giá trị quan sát trong khoảng thời gian đó thì chuỗi thời gian có thể được xem là dữ liệu trong không gian n chiều. Mỗi lần quan sát trong một khoảng thời gian như vậy sẽ phát sinh ra một điểm trong không gian n chiều. Tập hợp các điểm X= (x1, x2,…xn) được xem như tập hợp các đối tượng trong không gian n chiều ([2][4][12]). Trong khá nhiều các ứng dụng hiện nay 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.

Chính vì vậy, thông thường dữ liệu chuỗi thời gian là rất dài tuy nhiên giá trị giao động thì lại không cao và thường xấp xỉ trong một khoảng nào đó. Ví dụ, một hệ thống lưu lại các giá trị về nhiệt độ khí hậu thì thường nằm trong khoảng -20 tới 20 độ. Hơn nữa có khi thông tin lưu trữ trong nhiều ngày lại không cách xa nhau khoảng 10 độ.2 Bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian Trong việc khai thác thông tin trên dữ liệu chuỗi thời gian, chúng ta có rất nhiều bài toán khác nhau như gom cụm, phân lớp, tìm mô típ, phát hiện mẫu bất thường, khám phá luật kết hợp và trực quan hóa dữ liệu. Trong số đó thì tìm kiếm tương tự (similarity search) là một trong những bài toán đó.

Với mục đích là tìm ra các mô hình giống nhau trên tập dữ liệu ghi nhận được trong một khoảng thời gian nào đó chúng ta có thể dự đoán được xu hướng dữ liệu trong tương lai. Sau đây là một số ví dụ trong thực tế. - Nhận dạng các công ty có mô hình tăng trưởng giống nhau - Xác định những thời điểm mà các chỉ số chứng khoán có sự biến đông tương tự nhau 5 Cấu trúc chỉ mục TS-Tree trên dữ liệu thời gian với độ đo DTW - Tìm xem 1 giai điệu nhạc có tương tự với 1 bản nhạc nào trước đó hay không… Bài toán tìm kiếm tương tự hay còn gọi là so trùng mẫu (pattern matching) trên dữ liệu chuỗi thời gian là việc thiết kế một phương pháp tìm kiếm nhanh chóng và chính xác trong cơ sở dữ liệu chuỗi thời gian những mẫu con trùng hay sấp xỉ với mẫu yêu cầu. Chúng ta có 2 kiểu so trùng mẫu  So trùng toàn chuỗi (whole matching) là loại so trùng chiều dài của dữ liệu truy vấn và chiều dài dữ liệu tham khảo bằng nhau và xem xét 2 đường biểu diễn dữ liệu có tương tự nhau không theo định nghĩa về độ tương tự cho trước.

Bài toán này ta thường được dùng trong việc gom cụm, hay phân loại dữ liệu thời gian. Ví dụ cho loại so trùng này là “Tìm mức nước ở 2 dòng sông có thay đổi giống nhau trong 1 năm?”  So trùng chuỗi con (subsequence matching) là loại so trùng chiều dài của dữ liệu truy vấn ngắn hơn rất nhiều so với chiều dài của dữ liệu tham khảo. Mục đích là tìm những đoạn trong dữ liệu tham khảo tương tự với dữ liệu truy vấn. Một số ứng dụng của bài toán này là tìm những mẫu dữ liệu quan trọng hay những thay đổi bất thường trong dữ liệu ban đầu.

Ví dụ: “Tìm các tháng mà giá chứng khoán của công ty có sự thay đổi giống với tháng hiện tại?”, hay “những thời điểm nào mà giá chứng khoán thay đổi theo dạng hình răng cưa”… 2.3 Mô hình bài toán so trùng dữ liệu chuỗi thời gian Một trong những thử thách lớn nhất trong bài toán so trùng mẫu trên dữ liệu chuỗi thời gian là tập trung vào việc thiết kế một phương pháp lưu trữ hiệu quả và tìm kiếm nhanh để tìm trong cơ sở dữ liệu chuỗi thời gian những mẫu con trùng hoặc xấp xỉ với mẫu yêu cầu. Trong hầu hết các nghiên cứu về bài toán so trùng trên dữ liệu chuỗi thời gian, mô hình chủ yếu được áp dụng là mô hình rút trích thông tin (information retrieval).1 mô tả mô hình rút trích thông tin phổ biến được sử dụng trong bài toán so trùng dữ liệu chuỗi thời gian. Phần lập chỉ mục (Indexing): trong giai đoạn này chuỗi dữ liệu thời gian sẽ được lưu trữ theo dạng chỉ mục nhằm giúp cho quá trình tìm kiếm được tăng tốc. Do dữ liệu chuỗi thời gian thường rất lớn nên trước khi lập chỉ mục chúng ta thường thu giảm số chiều (reduce dimension) của chuỗi dữ liệu ban đầu.

Một số phương pháp thu giảm số chiều được biết cho đến nay như: phép biến đổi Fourier rời rạc (Discrete Fourier Transform - DFT), phép biến đổi Wavelet rời rạc (Discrete Wavelet Transform - DWT), xấp xỉ tuyến tính từng đoạn (Piecewise Linear Approximation - PLA), xấp xỉ hằng số từng đoạn thích nghi (Adaptive Piecewise Constant Approximation- APCA), xấp xỉ gộp ký hiệu hóa (Symbolic Aggregate approXimation - SAX)… Các cấu trúc lập chỉ mục quen thuộc là R-Tree, R*-Tree, M-tree…trong đó R*- Tree là cấu trúc chỉ mục nền tảng cho việc phát triển cấu trúc TS-Tree. Xuất hiện sau 6 Cấu trúc chỉ mục TS-Tree trên dữ liệu thời gian với độ đo DTW này, hầu hết các phương thức thao tác trên cây TS-Tree đều giống với R*-Tree. Chúng ta sẽ tìm hiểu kỹ hơn về vấn đề này trong các mục sau. So trùng mẫu: sau khi thiết lập chỉ mục cho dữ liệu chuỗi thời gian, quá trình so trùng mẫu là quá trình tìm kiếm các chuỗi thời gian con thỏa mãn điều kiện truy vấn.

Việc truy vấn thông thường sẽ bị ảnh hưởng bởi 2 yếu tố: một là cấu trúc chỉ mục chúng ta vừa thiết lập, hai là độ đo mà chúng ta áp dụng trong quá trình tìm kiếm. Việc lập chỉ mục không hẳn lúc nào cũng đem lại kết quả truy vấn nhanh mà có khi lại đem lại kết quả ngược lại. Với độ đo trước giờ chúng ta vẫn quen thuộc là độ đo Euclid, tuy nhiên trong đề tài này sẽ không dùng độ đo này mà chúng ta sẽ thay thế hoàn toàn bằng độ đo DTW để xem TS-Tree có làm việc tốt trên độ đo này hay không. Chuỗi thời gian Chuỗi thời gian truy vấn Lập chỉ mục Thu giảm số chiều So trùng mẫu Lập chỉ mục Chỉ mục So trùng mẫu (R*-Tree và TS-Tree) Kết quả truy vấn Hình 2.

Kiến trúc tổng thể của hệ thống so trùng mẫu 2.2Độ đo tương tự DTW (dynamic time warping) 2.1 Giới thiệu DTW Vấn đề trong các cấu trúc chỉ mục chuỗi dữ liệu thời gian hiện là một vấn đề rất được nhiều nhà khoa học nghiên cứu. Hầu hết các cấu trúc chỉ mục đang vận đụng độ đo Euclid trong việc tính toán khoảng cách giữa hai đối tượng trong dữ liệu chuỗi thời gian. Mặc dù vậy qua các trường hợp cho thấy rằng độ đo này lại chưa chính xác và linh hoạt trong các chuỗi dữ liệu có hình dáng giống nhau nhưng có sự xê dịch về mặt thời gian do quá trình tính toán dựa trên cùng một thời điểm. Chính vì vậy độ đo xoắn thời gian động được nghiên cứu như là một độ đo mang tính linh hoạt hơn trong việc khắc phục điểm yếu trên của độ đo Euclid.

Chính vì tính linh hoạt cho kết quả chính xác hơn nên độ đo xoắn thời gian động bắt đầu đóng vai trò quan trọng trong nhiều lĩnh vực như khoa học, y khoa, công nghiệp, hay tài chính nơi mà các dữ liệu yêu cầu tính toán với độ chính xác cao hơn.