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.
