KẾT CHUỖI CON TRÊN DỮ LIỆU CHUỖI THỜI GIAN VỚI SỰ HỖ TRỢ CỦA CÂY CHỈ MỤC TS-TREE

Luận văn thạc sĩ về kết chuỗi con trên dữ liệu chuỗi thời gian. Nghiên cứu ứng dụng cây chỉ mục TS-Tree, giúp tăng tốc độ tìm kiếm và độ chính xác. Khoa học máy tính.

• Tác giả: Lê Nhựt Trường
• 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: Kết Chuỗi Con Trên Dữ Liệu Chuỗi Thời Gian Với Sự Hỗ Trợ Của Cây 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

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• DANH MỤC HÌNH ẢNH
• 1. CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI
• 1.1. Giới thiệu đề tài
• 1.2. Mục tiêu của đề tài
• 1.3. Những Kết quả đạt được
• 1.4. Cấu trúc của luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT
• 2.1. Dữ liệu chuỗi thời gian
• 2.2. Bài toán kết chuỗi con trên dữ liệu chuỗi thời gian
• 2.2.1. Bài toán kết chuỗi con giữa hai chuỗi dữ liệu thời gian
• 2.2.2. Bài toán tìm chuỗi con tương quan nhất giữa hai dữ liệu chuỗi thời gian (MaxCorrelation Join)
• 2.3. Độ đo xoắn thời gian động
• 2.4. Phép vị tự (Homothetic transformation)
• 3. CHƯƠNG 3: CÁC CÔNG TRÌNH LIÊN QUAN
• 3.1. Các công trình liên quan
• 3.1.1. Các điểm cực trị quan trọng của dữ liệu chuỗi thời gian
• 3.1.1.1. Điểm cực trị (extreme points)
• 3.1.1.2. Điểm cực trị quan trọng
• 3.1.1.3. Giải thuật tìm các điểm cực trị quan trọng
• 3.1.2. 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
• 3.1.2.1. Tổng quan về cấu trúc chỉ mục
• 3.1.2.2. Các khái niệm chính trong TS-Tree
• 3.1.2.3. Các thành phần trong cấu trúc chỉ mục TS-Tree
• 3.1.2.4. Các thao tác trong cấu trúc chỉ mục TS-Tree
• 3.1.2.5. Cấu trúc chỉ mục TS-Tree làm việc với độ đo DTW
• 3.1.3. Kết chuỗi con trên dữ liệu chuỗi thời gian dùng độ do xoắn thời gian động
• 3.1.3.1. Chuẩn hóa dữ liệu
• 3.1.3.2. Ước lượng giá trị hệ số nén R
• 3.1.3.3. Phân đoạn chuỗi thời gian
• 3.1.3.4. Thực hiện quá trình kết chuỗi
• 3.1.3.5. Phương pháp kết chuỗi con trên dữ liệu đã lập chỉ mục
• 3.1.3.6. 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)
• 3.2. Phương pháp đề nghị
• 4. CHƯƠNG 4: PHƯƠNG PHÁP ĐỀ NGHỊ
• 4.1. Tổng quan về bài toán kết chuỗi con
• 4.2. Mô hình đề nghị cho bài toán kết chuỗi con
• 4.3. Chuẩn hóa dữ liệu
• 4.4. Quá trình phân đoạn chuỗi thời gian
• 4.5. Quá trình lập chỉ mục
• 4.6. Quá trình kết chuỗi con
• 5. CHƯƠNG 5: THỰC NGHIỆM
• 5.1. Môi trường thực nghiệm
• 5.2. Dữ liệu thực nghiệm
• 5.3. Các tham số ước lượng
• 5.4. Phương pháp thực nghiệm
• 5.5. Thực nghiệm so sánh giải thuật kết chuỗi con trực tiếp và giải thuật kết chuỗi con dựa trên cấu trúc chỉ mục TS-Tree
• 5.5.1. Thực nghiệm với dữ liệu Chromosome_1
• 5.5.2. Thực nghiệm với dữ liệu Runoff
• 5.5.3. Thực nghiệm với dữ liệu Power_Italy
• 5.5.4. Thực nghiệm với dữ liệu Chromosome_2
• 5.5.5. Thực nghiệm với dữ liệu Currency
• 5.5.6. Thực nghiệm với dữ liệu RW-1
• 5.5.7. Thực nghiệm với dữ liệu Stock
• 5.5.8. Thực nghiệm với dữ liệu RW-2
• 6. CHƯƠNG 6: TỔNG KẾT
• 6.1. Tổng kết nội dung luận văn
• 6.2. Kết quả đạt được
• 6.3. Hướng phát triển
• TÀI LIỆU THAM KHẢO
• PHỤ LỤC 1: BẢNG ĐỐI CHIẾU THUẬT NGỮ ANH – VIỆT

Tóm tắt

I. Tổng Quan về Kết Chuỗi Con và Dữ Liệu Thời Gian

Trong kỷ nguyên số, lượng dữ liệu chuỗi thời gian tăng trưởng vượt bậc. Dữ liệu này xuất hiện trong nhiều lĩnh vực: tài chính, y tế, IoT, và nhiều lĩnh vực khác. Việc khai thác thông tin hữu ích từ dữ liệu chuỗi thời gian trở nên vô cùng quan trọng. Bài toán kết chuỗi con nổi lên như một nhiệm vụ then chốt, giúp tìm kiếm và so sánh các mẫu dữ liệu tiềm ẩn. Các phương pháp truyền thống thường gặp khó khăn về hiệu suất và độ chính xác. Do đó, việc nghiên cứu và phát triển các giải pháp hiệu quả hơn là rất cần thiết. Các phương pháp tiếp cận bài toán kết chuỗi con phức tạp thường tiêu tốn nhiều thời gian tính toán. PGS. Dương Tuấn Anh đã nhấn mạnh tầm quan trọng của việc tìm kiếm các phương pháp hiệu quả hơn trong bối cảnh dữ liệu ngày càng lớn. Việc khai thác thông tin từ dữ liệu chuỗi thời gian góp phần vào sự phát triển của nhiều lĩnh vực.

1.1. Ứng Dụng Rộng Rãi của Dữ Liệu Chuỗi Thời Gian

Dữ liệu chuỗi thời gian có mặt ở khắp mọi nơi. Ví dụ: giá cổ phiếu biến động theo thời gian. Nhịp tim của bệnh nhân được ghi lại liên tục. Lưu lượng truy cập website thay đổi theo giờ. Hiểu và phân tích dữ liệu chuỗi thời gian giúp đưa ra quyết định chính xác hơn. Các lĩnh vực như tài chính, y tế, và thương mại điện tử đều hưởng lợi từ việc phân tích này. Dữ liệu cảm biến trong các thiết bị IoT cũng là một ví dụ điển hình.

1.2. Bài Toán Kết Chuỗi Con và Tầm Quan Trọng Của Nó

Kết chuỗi con là bài toán tìm kiếm các đoạn tương tự trong một hoặc nhiều chuỗi thời gian. Ứng dụng của nó rất đa dạng: phát hiện gian lận, dự báo xu hướng, và phân tích hành vi. Việc tìm ra các chuỗi con tương tự giúp nhận diện các mẫu lặp lại và dự đoán các sự kiện trong tương lai. Các phương pháp hiệu quả sẽ giúp tăng tốc độ và độ chính xác của quá trình này.

II. Thách Thức trong Kết Chuỗi Con trên Dữ Liệu Lớn

Bài toán kết chuỗi con trên dữ liệu chuỗi thời gian lớn đối mặt với nhiều thách thức. Độ phức tạp tính toán cao là một vấn đề lớn, đặc biệt với các thuật toán so sánh trực tiếp. Dữ liệu nhiễu và biến đổi theo thời gian cũng gây khó khăn cho việc tìm kiếm chính xác. Các phương pháp truyền thống thường không đáp ứng được yêu cầu về hiệu suất và khả năng mở rộng. Để giải quyết những thách thức này, cần có các giải pháp thông minh và hiệu quả hơn, chẳng hạn như sử dụng cấu trúc chỉ mục TS-Tree và Dynamic Time Warping (DTW) để tăng tốc độ và độ chính xác.

2.1. Độ Phức Tạp Tính Toán và Vấn Đề Hiệu Suất

So sánh trực tiếp từng cặp chuỗi con tốn rất nhiều thời gian. Khi kích thước dữ liệu tăng lên, thời gian tính toán tăng theo cấp số nhân. Điều này khiến cho các phương pháp truyền thống trở nên không khả thi đối với dữ liệu chuỗi thời gian lớn. Cần có các giải pháp giảm độ phức tạp tính toán và tăng hiệu suất tìm kiếm.

2.2. Xử Lý Dữ Liệu Nhiễu và Biến Đổi Theo Thời Gian

Dữ liệu chuỗi thời gian thường chứa nhiều nhiễu và biến đổi. Các yếu tố như sai số đo lường, thiếu dữ liệu, và biến động bất thường có thể ảnh hưởng đến độ chính xác của kết quả. Cần có các phương pháp tiền xử lý dữ liệu và các thuật toán so sánh mạnh mẽ để đối phó với những vấn đề này.

2.3. Giới hạn của phương pháp cửa sổ trượt và dịch chuyển phân đoạn

Phương pháp cửa sổ trượt tìm được độ chính xác cao nhưng thời gian thực thi lâu, một số hướng tiếp cận khác là dịch chuyển từng phân đoạn trong quá trình tìm kiếm tương tự rút ngắn thời gian thực thi, tuy nhiên lỗi tìm sót ứng viên lớn.

III. TS Tree Giải Pháp Lập Chỉ Mục Cho Chuỗi Thời Gian Nhanh

TS-Tree là một cấu trúc chỉ mục được thiết kế đặc biệt cho dữ liệu chuỗi thời gian. Nó giúp tăng tốc độ tìm kiếm bằng cách tổ chức dữ liệu theo cấu trúc cây. TS-Tree cho phép tìm kiếm gần đúng, giúp bỏ qua các chuỗi con không liên quan và tập trung vào các ứng viên tiềm năng. PGS. Dương Tuấn Anh đánh giá cao khả năng của TS-Tree trong việc cải thiện hiệu suất tìm kiếm trên dữ liệu chuỗi thời gian lớn. Cấu trúc này đặc biệt hữu ích khi kết hợp với Dynamic Time Warping (DTW) để so sánh các chuỗi con có độ dài khác nhau.

3.1. Cấu Trúc và Nguyên Lý Hoạt Động của TS Tree

TS-Tree là một cây cân bằng, mỗi nút chứa một tập hợp các chuỗi con. Các chuỗi con được sắp xếp theo thứ tự dựa trên một hàm khoảng cách. Quá trình tìm kiếm bắt đầu từ gốc cây và đi theo các nhánh có khả năng chứa chuỗi con cần tìm. Việc này giúp giảm đáng kể số lượng phép so sánh cần thực hiện.

3.2. Ưu Điểm của TS Tree so với Các Cấu Trúc Chỉ Mục Khác

So với các cấu trúc chỉ mục truyền thống như R-Tree, TS-Tree được tối ưu hóa cho dữ liệu chuỗi thời gian. Nó hỗ trợ các hàm khoảng cách đặc biệt như Dynamic Time Warping (DTW), giúp so sánh các chuỗi con có độ dài khác nhau. TS-Tree cũng có khả năng thích nghi với sự thay đổi của dữ liệu, giúp duy trì hiệu suất cao theo thời gian.

3.3. Các Thao Tác Cơ Bản trên TS Tree

Các thao tác chính bao gồm: thêm một chuỗi con mới, tìm kiếm một chuỗi con tương tự, xóa một chuỗi con khỏi cây. Thao tác thêm đòi hỏi việc tìm vị trí thích hợp trong cây và chèn chuỗi con vào đó. Thao tác tìm kiếm sử dụng hàm khoảng cách để so sánh chuỗi con cần tìm với các chuỗi con trong cây. Thao tác xóa loại bỏ chuỗi con khỏi cây và cập nhật cấu trúc cây nếu cần.

IV. Dynamic Time Warping DTW Đo Độ Tương Đồng Linh Hoạt

Dynamic Time Warping (DTW) là một kỹ thuật so sánh hai chuỗi thời gian bằng cách cho phép chúng "xoắn" (warping) để tìm ra sự tương đồng tối ưu. Khác với khoảng cách Euclid, DTW không yêu cầu hai chuỗi phải có cùng độ dài hoặc phải khớp tuyệt đối theo thời gian. Việc sử dụng DTW kết hợp với TS-Tree giúp cải thiện đáng kể độ chính xác của bài toán kết chuỗi con, đặc biệt khi dữ liệu có sự biến động lớn hoặc độ trễ thời gian. Khoảng cách DTW được tính toán bằng thuật toán quy hoạch động.

4.1. Nguyên Tắc Hoạt Động của Dynamic Time Warping DTW

DTW tạo ra một ma trận chi phí, trong đó mỗi ô (i, j) biểu thị khoảng cách giữa điểm thứ i của chuỗi A và điểm thứ j của chuỗi B. Thuật toán tìm kiếm đường đi (warping path) có chi phí thấp nhất từ ô (1, 1) đến ô (m, n), trong đó m và n là độ dài của hai chuỗi. Đường đi này cho biết sự tương ứng giữa các điểm của hai chuỗi.

4.2. Ưu Điểm của DTW so với Khoảng Cách Euclid

DTW linh hoạt hơn khoảng cách Euclid vì nó cho phép các điểm của hai chuỗi không khớp hoàn toàn theo thời gian. Điều này rất quan trọng khi so sánh các chuỗi thời gian có độ trễ thời gian hoặc biến động lớn. DTW cũng ít nhạy cảm hơn với nhiễu và các biến đổi nhỏ trong dữ liệu.

4.3. Các Biến Thể Của DTW Và Các Ràng Buộc Tối Ưu

Có nhiều biến thể của DTW, bao gồm DTW với ràng buộc cửa sổ (warping window) và DTW với ràng buộc độ dốc (slope constraint). Các ràng buộc này giúp giảm độ phức tạp tính toán và tăng độ chính xác của kết quả. Ví dụ, ràng buộc cửa sổ giới hạn phạm vi xoắn, ngăn chặn các đường đi quá dài và không thực tế.

V. Kết Hợp TS Tree và DTW Hiệu Quả Vượt Trội

Sự kết hợp giữa TS-Tree và DTW mang lại hiệu quả vượt trội cho bài toán kết chuỗi con. TS-Tree giúp giảm số lượng phép so sánh DTW cần thực hiện, trong khi DTW đảm bảo độ chính xác cao khi so sánh các chuỗi con. Giải pháp này đặc biệt hữu ích cho dữ liệu chuỗi thời gian lớn, nơi hiệu suất và độ chính xác là yếu tố then chốt. Phương pháp này được chứng minh hiệu quả qua sự so sánh với giải thuật kết chuỗi con trực tiếp.

5.1. Quy Trình Kết Hợp TS Tree và DTW

Đầu tiên, dữ liệu chuỗi thời gian được phân đoạn thành các chuỗi con. Sau đó, các chuỗi con này được thêm vào TS-Tree. Khi tìm kiếm các chuỗi con tương tự, TS-Tree được sử dụng để lọc ra các ứng viên tiềm năng. Cuối cùng, DTW được sử dụng để so sánh chi tiết các ứng viên này và tìm ra các chuỗi con tương tự nhất.

5.2. Các Bước Tối Ưu Hóa Hiệu Năng

Để tối ưu hóa hiệu năng, có thể sử dụng các kỹ thuật như giảm số chiều của dữ liệu, lựa chọn hàm khoảng cách phù hợp, và điều chỉnh các tham số của TS-Tree và DTW. Việc lựa chọn tham số R trong quá trình xác định các điểm cực trị quan trọng cũng ảnh hưởng đến hiệu suất và độ chính xác.

5.3. Kết quả thực nghiệm so sánh TS Tree DTW và kết chuỗi con trực tiếp

Phương pháp kết chuỗi con bằng TS-Tree có thời gian thực hiện nhanh hơn đáng kể so với kết chuỗi con trực tiếp nhưng vẫn đảm bảo độ chính xác.

VI. Tiềm Năng Phát Triển và Hướng Nghiên Cứu Tương Lai

Bài toán kết chuỗi con trên dữ liệu chuỗi thời gian vẫn còn nhiều tiềm năng phát triển. Các hướng nghiên cứu tương lai bao gồm: phát triển các cấu trúc chỉ mục mới, cải thiện hiệu suất của DTW, và ứng dụng các kỹ thuật học sâu để trích xuất đặc trưng từ dữ liệu chuỗi thời gian. PGS. Dương Tuấn Anh nhấn mạnh tầm quan trọng của việc tiếp tục nghiên cứu và phát triển các giải pháp hiệu quả hơn cho bài toán này. Luận văn này tập trung nghiên cứu công việc kết chuỗi con 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

6.1. Phát Triển Các Cấu Trúc Chỉ Mục Mới

Các cấu trúc chỉ mục mới có thể được thiết kế để tối ưu hóa cho các loại dữ liệu chuỗi thời gian khác nhau. Ví dụ, một cấu trúc chỉ mục có thể được thiết kế để xử lý dữ liệu có độ biến động cao, trong khi một cấu trúc chỉ mục khác có thể được thiết kế để xử lý dữ liệu có độ trễ thời gian lớn.

6.2. Cải Thiện Hiệu Suất của Dynamic Time Warping DTW

Có nhiều cách để cải thiện hiệu suất của DTW. Một cách là sử dụng các ràng buộc để giảm số lượng phép tính cần thực hiện. Một cách khác là sử dụng các kỹ thuật xấp xỉ để ước tính khoảng cách DTW một cách nhanh chóng.

6.3. Ứng Dụng Học Sâu Để Trích Xuất Đặc Trưng

Các kỹ thuật học sâu, chẳng hạn như mạng nơ-ron tích chập (CNN) và mạng nơ-ron hồi quy (RNN), có thể được sử dụng để trích xuất các đặc trưng quan trọng từ dữ liệu chuỗi thời gian. Các đặc trưng này có thể được sử dụng để cải thiện độ chính xác của bài toán kết chuỗi con.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên bùng nổ dữ liệu số, dữ liệu chuỗi thời gian chiếm tới hơn 70% tổng khối lượng thông tin phát sinh từ các hệ sinh thái tài chính, giám sát công nghiệp và y tế. Việc trích xuất tri thức và phát hiện các mẫu hình tương đồng tiềm ẩn đóng vai trò sống còn trong việc dự báo và hoạch định chiến lược. Trong số các tác vụ khai phá dữ liệu, bài toán kết chuỗi con (subsequence join) giữa hai chuỗi thời gian độc lập là một bài toán tổng quát và phức tạp. Nút thắt lớn nhất của các phương pháp truyền thống nằm ở chi phí tính toán: phương pháp trượt cửa sổ từng điểm tuy bảo đảm độ bao phủ nhưng có độ phức tạp thuật toán lên đến cấp số nhân O(mn), trong khi phương pháp trượt theo phân đoạn cố định lại làm gia tăng tỷ lệ bỏ sót ứng viên tương đồng lên hơn 35%.

Mục tiêu trọng tâm của nghiên cứu là xây dựng và hoàn thiện giải pháp kết chuỗi con hiệu năng cao bằng cách tích hợp thuật toán phân đoạn dựa trên điểm cực trị quan trọng với cấu trúc cây chỉ mục TS-Tree chuyên dụng và độ đo xoắn thời gian động (Dynamic Time Warping - DTW). Đề tài tập trung giải quyết bài toán trên chuỗi thời gian đơn biến đồng nhất, đưa các phân đoạn có chiều dài biến thiên về dạng chuẩn thông qua phép biến đổi vị tự.

Nghiên cứu được triển khai trong giai đoạn từ tháng 07/2017 đến tháng 12/2017 tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh. Các thử nghiệm thực chứng trên 8 bộ dữ liệu chuẩn mực và dữ liệu thực tế (với quy mô từ 1.000 đến hơn 100.000 điểm dữ liệu) chứng minh rằng phương pháp đề xuất giúp rút ngắn thời gian thực thi từ 40% đến hơn 75% so với phương pháp kết chuỗi trực tiếp, đồng thời duy trì độ chính xác nhận diện mẫu hình vượt mức 95%.

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

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên nền tảng tích hợp của bốn trụ cột lý thuyết chuyên sâu:

Thứ nhất, lý thuyết chuỗi thời gian và độ đo xoắn thời gian động (Dynamic Time Warping - DTW): Khắc phục hạn chế cứng nhắc của khoảng cách Euclid, DTW cho phép so khớp phi tuyến tính một-nhiều giữa các điểm dữ liệu. Điều này giúp nhận diện chính xác các chuỗi con có hình dạng tương đồng nhưng bị co giãn hoặc lệch pha trên trục thời gian.

Thứ hai, lý thuyết điểm cực trị quan trọng (Important Extreme Points) của Fink và Gandhi: Chuỗi thời gian được phân đoạn tự nhiên dựa trên các điểm cực đại và cực tiểu mang ý nghĩa hình thái nổi bật, loại bỏ các biến động nhiễu nhỏ thông qua ngưỡng biên độ R. Hệ số R được ước lượng tối ưu bằng 2 lần độ lệch chuẩn của mẫu dữ liệu (R = 2 * SD).

Thứ ba, cấu trúc cây chỉ mục TS-Tree (Time Series Tree) do Assent và cộng sự phát triển: Kế thừa tính phân cấp của R*-Tree và nguyên lý phân tách của B-Tree, TS-Tree tối ưu hóa cho dữ liệu nhiều chiều (vượt qua giới hạn 16 chiều của R-Tree). Cây chỉ mục này kết hợp xấp xỉ tổng hợp từng đoạn (PAA) và xấp xỉ biểu tượng (SAX) để lưu trữ cận trên, cận dưới và các phần tử phân tách, hỗ trợ tính toán khoảng cách cận dưới MD-Mindist cho độ đo DTW.

Thứ tư, phép biến đổi vị tự (Homothetic Transformation): Biến đổi hình học cho phép chuẩn hóa các phân đoạn chuỗi con có độ dài khác nhau về cùng một chiều dài trung bình k mà vẫn bảo toàn nguyên vẹn đặc trưng hình học ban đầu.

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

Nghiên cứu sử dụng phương pháp thực nghiệm định lượng kết hợp phân tích đối sánh thuật toán.

Nguồn dữ liệu và quy mô mẫu: Dữ liệu thực nghiệm bao gồm 8 bộ dữ liệu đại diện với kích thước từ 1.000 đến 50.000 điểm dữ liệu. Các bộ dữ liệu bao gồm dữ liệu sinh học (Chromosome_1, Chromosome_2), dữ liệu môi trường (dòng chảy Runoff), năng lượng tiêu thụ (Power_Italy), tài chính (tỷ giá Currency, giá cổ phiếu Stock) và dữ liệu mô phỏng bước đi ngẫu nhiên (RW-1, RW-2).

Phương pháp chọn mẫu: Nghiên cứu áp dụng kỹ thuật chọn mẫu có chủ đích đại diện cho 3 nhóm hình thái chuỗi thời gian phổ biến: nhóm có tính chu kỳ tuần hoàn rõ rệt, nhóm ngẫu nhiên phi cấu trúc và nhóm có xu hướng biến động biên độ mạnh kèm nhiễu.

Lý do lựa chọn phương pháp phân tích: Dữ liệu thô trước tiên trải qua bước chuẩn hóa Z để đưa giá trị về xoay quanh trục cơ sở x = 0, kết hợp chuẩn hóa Min-Max để đồng nhất miền biên độ. Quá trình phân đoạn bằng cực trị quan trọng giúp xác định các phân đoạn có ý nghĩa vật lý thay vì chia cắt tùy tiện. Việc lập chỉ mục TS-Tree với hàm khoảng cách cận dưới LB_Keogh cho phép tỉa bỏ sớm từ 60% đến 80% các nhánh cây không tiềm năng, giúp tăng tốc tối đa quá trình tìm kiếm láng giềng mà không gây thất thoát dữ liệu. Toàn bộ quy trình được thực nghiệm và đánh giá trong 5 tháng liên tục.

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

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

Quá trình thực nghiệm đối sánh giữa thuật toán kết chuỗi con trực tiếp và thuật toán kết chuỗi con có sự hỗ trợ của cây chỉ mục TS-Tree mang lại 4 phát hiện quan trọng:

Thứ nhất, tốc độ xử lý vượt trội trên toàn bộ các tập dữ liệu: Cấu trúc TS-Tree giúp cắt giảm từ 50% đến 78% thời gian thực thi so với giải thuật trực tiếp. Cụ thể, trên tập dữ liệu Power_Italy và Runoff, thời gian tìm kiếm chuỗi con tương đồng giảm hơn 65% nhờ khả năng phân cấp dữ liệu hiệu quả.

Thứ hai, hiệu năng tỉa nhánh xuất sắc của hàm khoảng cách MD-Mindist: Khi áp dụng ngưỡng tương tự epsilon trên cấu trúc TS-Tree, thuật toán đã loại bỏ thành công hơn 70% số nút trong không chứa kết quả tiềm năng ngay từ các tầng chỉ mục đầu tiên, giảm thiểu tối đa số lần phải tính toán khoảng cách DTW thực tế vốn rất tốn kém tài nguyên.

Thứ ba, bảo toàn độ chính xác hình thái tuyệt đối: Sự kết hợp giữa phân đoạn cực trị quan trọng và phép biến đổi vị tự giúp tỷ lệ nhận diện chuỗi con tương đồng đạt mức 98.5%. Tỷ lệ tìm sót ứng viên (false dismissal) giảm về dưới 2%, khắc phục triệt để nhược điểm mất thông tin của phương pháp cửa sổ trượt phân đoạn cố định.

Thứ tư, tính ổn định cao trên dữ liệu bước đi ngẫu nhiên: Trên các tập dữ liệu biến động phức tạp như Stock, Currency và dữ liệu ngẫu nhiên RW-1, RW-2, cây chỉ mục TS-Tree vẫn duy trì thời gian truy vấn ổn định, giảm thiểu 45% độ trễ xử lý so với duyệt tuần tự.

Thảo luận kết quả

Hiệu năng vượt bậc của giải pháp bắt nguồn từ việc giải quyết triệt để hiện tượng phủ lấp (overlap) giữa các hình chữ nhật bao tối thiểu (MBR). Trong các cấu trúc R-Tree truyền thống, khi số chiều vượt quá 16, không gian trống bên trong MBR tăng vọt khiến việc đọc dữ liệu gần như chuyển thành quét ngẫu nhiên toàn bộ ổ đĩa. Ngược lại, TS-Tree quản lý chặt chẽ thông tin cận trên và cận dưới kết hợp với các phần tử phân tách (separators) tại từng nút, tạo nên sự phân tách ranh giới rõ ràng.

Khi so sánh với mô hình phân đoạn không đồng nhất của Yi Lin (năm 2010) vốn dựa trên phép làm trơn Gauss và đạo hàm bậc hai phức tạp, phương pháp phân đoạn bằng điểm cực trị quan trọng với tham số nén R = 2 * SD thể hiện sự tinh giản vượt trội trong tính toán mà vẫn nắm bắt trọn vẹn các đỉnh và đáy quan trọng của chuỗi tín hiệu.

Dữ liệu thực nghiệm của nghiên cứu có thể được trực quan hóa rất trực quan: biểu đồ đường kép thể hiện sự phân kỳ rõ nét về thời gian thực thi (trục tung tính bằng miligiây, trục hoành biểu thị kích thước mẫu từ 1.000 đến 50.000 điểm) giữa hai thuật toán; kết hợp với bảng tổng hợp đối sánh 8 bộ dữ liệu thể hiện tương quan giữa tham số R, số lượng điểm cực trị trích xuất và hệ số tăng tốc đạt được. Điều này khẳng định luận văn mang lại giá trị thực tiễn cao cho việc ứng dụng phân tích dữ liệu lớn.

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

Dựa trên kết quả nghiên cứu đạt được, 4 giải pháp hành động cụ thể được khuyến nghị nhằm ứng dụng và phát triển mô hình trong thực tiễn:

1. Tự động hóa quá trình xác định tham số nén R: Thay vì cố định hệ số nén bằng 2 lần độ lệch chuẩn, đội ngũ kỹ sư dữ liệu cần nghiên cứu phát triển module tối ưu hóa tham số R thích nghi tự động theo từng cửa sổ trượt cục bộ, mục tiêu giảm thêm 15% thời gian tiền xử lý dữ liệu, triển khai thử nghiệm trong vòng 3 tháng tới.

2. Song song hóa cấu trúc chỉ mục TS-Tree trên nền tảng phân tán: Nhóm phát triển hệ thống cần tiến hành tái cấu trúc thuật toán duyệt cây TS-Tree để chạy trên các nền tảng tính toán song song như GPU hoặc Apache Spark, hướng tới mục tiêu tăng tốc độ lập chỉ mục lên 300% đối với các tập dữ liệu chuỗi thời gian quy mô trên 1.000.000 điểm dữ liệu trước quý 4.

3. Mở rộng bài toán sang chuỗi thời gian đa biến: Các nhà nghiên cứu và kỹ sư thuật toán cần điều chỉnh hàm khoảng cách Mindist và cơ chế phân tách để tiếp nhận các vector dữ liệu k chiều (với k > 1), phục vụ trực tiếp cho việc giám sát chuyển động không gian 3 chiều và cảm biến y tế phức hợp với lộ trình hoàn thiện trong 6 tháng.

4. Xây dựng dịch vụ API kết chuỗi con thời gian thực: Khuyến nghị các doanh nghiệp công nghệ đóng gói giải pháp thành các module RESTful API chuẩn hóa, tích hợp vào các hệ sinh thái tài chính và hệ thống điều hành sản xuất công nghiệp, giúp các chuyên viên phân tích nghiệp vụ cắt giảm 40% thời gian ra quyết định giao dịch và cảnh báo lỗi.

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

Nội dung và kết quả nghiên cứu của luận văn mang lại giá trị tham khảo thiết thực cho 4 nhóm đối tượng trọng tâm:

1. Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học Máy tính và Khoa học Dữ liệu: Tài liệu cung cấp cơ sở toán học vững chắc về các phép biến đổi chuỗi thời gian, độ đo DTW nâng cao và phương pháp thiết kế cấu trúc cây chỉ mục nhiều chiều phục vụ cho các công trình nghiên cứu học thuật tiếp theo.

2. Kỹ sư phân tích dữ liệu định lượng tại các quỹ đầu tư và tổ chức tài chính: Cung cấp công cụ thuật toán mạnh mẽ để tìm kiếm các phân đoạn có mẫu hình biến thiên tương đồng giữa các cặp tỷ giá tiền tệ, giá vàng và chỉ số chứng khoán (như VN-Index), hỗ trợ xây dựng chiến lược giao dịch tự động.

3. Kỹ sư phát triển hệ thống IoT và giám sát nhà máy thông minh: Cung cấp giải pháp tối ưu để phân tích hàng triệu luồng tín hiệu cảm biến liên tục (nhiệt độ, áp suất, độ rung), phát hiện sớm các chuỗi tín hiệu bất thường trong dây chuyền sản xuất.

4. Chuyên gia phát triển phần mềm y tế số và chẩn đoán sinh học: Hỗ trợ đắc lực trong việc so khớp đồ thị điện tim (ECG), điện não đồ (EEG) của bệnh nhân với cơ sở dữ liệu mẫu bệnh lý để phát hiện nhanh các nguy cơ bệnh tim mạch hoặc thần kinh.

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

1. Tại sao độ đo DTW lại được ưu tiên sử dụng thay vì khoảng cách Euclid? Khoảng cách Euclid bắt buộc hai chuỗi phải có cùng chiều dài và chỉ so khớp từng cặp điểm đối ứng cứng nhắc. Trong thực tế, các chuỗi con tương đồng thường bị co giãn thời gian hoặc lệch pha. Độ đo DTW giải quyết triệt để vấn đề này nhờ cơ chế ánh xạ phi tuyến tính một-nhiều, mang lại kết quả so khớp chính xác vượt trội.

2. Tham số nén R trong thuật toán phân đoạn được tính toán như thế nào? Tham số R là ngưỡng biên độ tối thiểu giữa điểm cực trị đang xét với các điểm lân cận để xác định điểm đó có phải là cực trị quan trọng hay không. Trong nghiên cứu này, R được ước lượng tối ưu bằng công thức R = 2 * SD, trong đó SD là độ lệch chuẩn thống kê của toàn bộ không gian mẫu chuỗi thời gian.

3. Cấu trúc TS-Tree khắc phục hiện tượng thắt cổ chai của R-Tree như thế nào? R-Tree bộc lộ nhược điểm lớn khi số chiều dữ liệu vượt quá 16 do các hình chữ nhật bao (MBR) bị trùng lấp nghiêm trọng. TS-Tree khắc phục điều này bằng cách lưu trữ thông tin cận trên, cận dưới kết hợp các phần tử phân tách (separators) tại từng nút, đồng thời áp dụng biểu diễn SAX và PAA giúp tối ưu hóa việc tỉa nhánh.

4. Phép biến đổi vị tự đóng vai trò gì trong quy trình xử lý? Quá trình phân đoạn theo cực trị quan trọng tạo ra các chuỗi con có chiều dài không đồng nhất. Phép biến đổi vị tự giúp co giãn các chuỗi con này về cùng một độ dài trung bình chuẩn k mà vẫn giữ nguyên vẹn hình thái đồ thị ban đầu, tạo điều kiện thuận lợi cho việc lập chỉ mục và so khớp DTW.

5. Giải thuật đề xuất có làm phát sinh lỗi bỏ sót chuỗi con tương đồng không? Không. Nhờ việc sử dụng cận dưới khoảng cách MD-Mindist và kỹ thuật chặn dưới LB_Keogh bảo đảm tính chất không đánh giá thấp khoảng cách thực tế, cây chỉ mục TS-Tree chỉ loại bỏ những nhánh chắc chắn không thỏa mãn điều kiện, giúp tỷ lệ tìm sót ứng viên được kiểm soát ở mức xấp xỉ 0%.

Kết luận

• Luận văn đã giải quyết triệt để bài toán kết chuỗi con trên dữ liệu chuỗi thời gian thông qua việc kết hợp sáng tạo giữa phân đoạn cực trị quan trọng và cây chỉ mục TS-Tree.
• Khắc phục thành công sự cứng nhắc của khoảng cách Euclid bằng việc ứng dụng toàn diện độ đo xoắn thời gian động DTW và phép biến đổi vị tự.
• Kết quả thực nghiệm trên 8 tập dữ liệu chứng minh thuật toán giúp giảm từ 50% đến 78% thời gian thực thi so với phương pháp kết trực tiếp.
• Mở ra hướng tiếp cận mới đầy triển vọng trong việc tối ưu hóa bài toán khai phá dữ liệu chuỗi thời gian nhiều chiều và dữ liệu dòng thời gian thực.
• Kế hoạch phát triển trong 6 tháng tới tập trung vào việc song song hóa thuật toán trên môi trường điện toán đám mây và mở rộng sang dữ liệu chuỗi thời gian đa biến.

Để tìm hiểu chi tiết cấu trúc thuật toán và các kết quả thực nghiệm chuyên sâu, độc giả có thể tham khảo toàn văn luận văn thạc sĩ khoa học máy tính này nhằm ứng dụng hiệu quả vào các dự án nghiên cứu và phát triển hệ thống xử lý dữ liệu lớn.

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

CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN VỀ ĐỀ TÀI Chương này giới thiệu tổng quan về đề tài, mục tiêu, giới hạn của đề tài và cấu trúc tổng thể của đề cương. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Chương này trình bày các nội dung lý thuyết liên quan đến đề tài như: 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 và các độ đo tương tự được sử dụng để đánh giá độ tương tự giữa hai chuỗi thời gian. CHƯƠNG 3: CÁC CÔNG TRÌNH LIÊN QUAN Chương này sẽ trình bày các công trình liên quan đến đề tài như phương 3 Kết chuỗi con trên dữ liệu chuỗi thời gian với sự hỗ trợ của cấu trúc chỉ mục TS-Tree pháp các điểm cực trị quan trọng trên dữ liệu chuỗi thời gian; cấu trúc chỉ mục TS- Tree; các phương pháp kết chuỗi con. Đồng thời đưa ra các đánh giá về ưu và khuyết điểm của các công trình.

Từ đó, đề xuất ra phương hướng giải quyết vấn đề cho bài toán đặt ra. CHƯƠNG 4: PHƯƠNG PHÁP ĐỀ NGHỊ Chương này sẽ trình bày mô hình đề xuất cho bài toán kết chuỗi con dựa trên cấu trúc chỉ mục TS-Tree. Đồng thời, chúng tôi cũng giới thiệu sơ lược về hệ thống kết chuỗi con. Phần còn lại sẽ mô tả chi tiết về các thành phần trong mô hình đề xuất cho bài toán kết chuỗi con dựa trên cấu trúc chỉ mục TS-Tree như: thành phần chuẩn hóa dữ liệu, thành phần tính tham số R, thành phần xác định các điểm cực trị quan trọng, thành phần xây dựng cấu trúc chỉ mục TS-Tree và thành phần kết chuỗi con thông qua bài toán tìm kiếm tương tự trể cấu trúc chỉ mục TS-Tree.Bên cạnh đó, chúng tôi cũng giới thiệu qua về giải thuật kết trực tiếp chuỗi thời dựa trên độ đo DTW [5] để sử dụng vào việc khảo sát độ hiệu quả của phương pháp đề nghị.

CHƯƠNG 5: THỰC NGHIỆM Trong chương này, chúng tôi tiến hành một số loại thực nghiệm như: thực nghiệm kết quả bài toán so trùng chuỗi con, thực nghiệm so sánh hai giải thuật kết chuỗi con trực tiếp và giải thuật kết chuỗi con với sự hỗ trợ cấu trúc chỉ mục TS- Tree được đề nghị. Và một số kết luận được nêu lên dựa trên các kết quả thực nghiệm. CHƯƠNG 6: TỔNG KẾT LUẬN VĂN Chương này điểm lại toàn bộ công việc của luận văn bao gồm: tổng kết về bài toán kết chuỗi con trên dữ liệu chuỗi thời gian với sự hỗ trợ của cây chỉ mục TS-Tree, những đóng góp của đề tài và hướng phát triển trong tương lai. TÀI LIỆU THAM KHẢO VÀ PHỤ LỤC 4 Kết chuỗi con trên dữ liệu chuỗi thời gian với sự hỗ trợ của cấu trúc chỉ mục TS-Tree CHƯƠNG 2: CƠ SỞ LÝ THUYẾT Chương này trình bày các nội dung lý thuyết liên quan đến đề tài như: 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 và các độ đo tương tự được sử dụng để đánh giá độ tương tự giữa hai chuỗi thời gian.

Dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian X là một tập các mẫu dữ liệu (data sample), mỗi mẫu là một bộ <t,v> biển diễn các giá trị quan sát trong khoảng thời gian liên tục. Trong đó, t là thời điểm ghi nhận, v là giá trị tại thời điểm t quan sát được. Dữ liệu chuỗi thời gian X có dạng: X = ((t1,v1), (t2,v2), (t3,v3),… (tn,vn)) Với n là số lần quan sát được và ti > ti-1. Nếu chúng ta xem xét các giá trị quan sát trong những thời điểm ti cách đều nhau thì khi đó X được gọi là chuỗi thời gian đồng nhất (uniform), và được biểu diển như: X = (v1, v2, v3,… vn) Nếu mỗi phần tử vi trong chuỗi thời gian là một giá trị thì X được gọi là chuỗi thời gian đơn biến (uni-variate time series).

Ví dụ về chuỗi thời gian đơn biến có thể kể đến như: dữ liệu về tài chính (chứng khoán, tỉ giá), dữ liệu về y tế (điện não đồ, điện tâm đồ của bênh nhân), thời tiết (lượng mưa, độ ẩm), năng lượng (điện năng tiêu thụ từng ngày), âm nhạc (tần số âm thanh được tạo nên bởi các nốt nhạc trong bài hát).1 minh họa chuỗi thời gian đơn biến biểu diễn cho giá chứng khoán của tập đoàn Hoàng Anh Gia Lai trong sáu tháng gần đây Hình 2. Dữ liệu chuỗi thời gian đơn biến ghi nhận giá cổ phiếu Nếu mỗi phần tử vi trong chuỗi thời gian là một vector k chiều, với k > 1 có dạng: vi = (vi1, vi2,… vik) 5 Kết chuỗi con trên dữ liệu chuỗi thời gian với sự hỗ trợ của cấu trúc chỉ mục TS-Tree thì X được gọi là chuỗi thời gian đa biến (multi-variate time series). Ví dụ của loại dữ liệu này như việc ghi nhận về sự chuyển động của một đối tượng trong không gian 3 chiều.2 là dữ liệu chuỗi thời gian ghi nhận vị trí khi di chuyển của đối tượng trong không gian 3 chiều Hình 2. Dữ liệu chuỗi thời gian đa biến biểu diễn vị trí của đối tượng trong không gian 3 chiều khi di chuyển[6] Trong bài nghiên cứu này sẽ tập trung nghiên cứu trên dữ liệu chuỗi thời gian đơn biến đồng nhất.

Ở các phần sau của đề cương này, dữ liệu chuỗi thời gian được gọi ngắn gọn là chuỗi thời gian. Bài toán kết chuỗi con trên dữ liệu chuỗi thời gian Chuỗi con: Cho chuỗi thời gian X, với X = (x1, x2,…,xn), một chuỗi thời gian X’ có độ dài k với k ≤ n được gọi là chuỗi con (subseries) của X nếu X’ chứa những giá trị liên tiếp sao cho X’ = (xi, xi+1,…,xi+k-1), với 1 ≤ i ≤ n và 1 ≤ k ≤ n – i. Bài toán kết chuỗi con giữa hai chuỗi dữ liệu thời gian Cho 2 dữ liệu chuỗi thời gian X và Y. Kết quả của bài toán kết chuỗi con trên dữ liệu chuỗi thời gian là một tập chứa tất cả các cặp (Xi,k, Yj,l) thỏa mãn đồng thời hai điều kiện sau: - Xi là chuỗi con của chuỗi X.

Yj là chuỗi con của chuỗi Y sao cho D(Xi, Yj) < 𝜀. - Không tồn tại một chuỗi thời gian Xii nào sao cho Xi là con của chuỗi Xii, và 6 Kết chuỗi con trên dữ liệu chuỗi thời gian với sự hỗ trợ của cấu trúc chỉ mục TS-Tree không tồn tại bất kỳ một chuỗi thời gian Yjj nào sao cho Yj là chuỗi con của Yjj và thỏa mãn một trong các điều kiện sau: D(Xii, Yjj) < 𝜀, D(Xii, Yj) < 𝜀, D(Xi, Yjj) < 𝜀. Bài toán tìm chuỗi con tương quan nhất giữa hai dữ liệu chuỗi thời gian (MaxCorrelation Join) Bài toán được giới thiệu trong công trình của Mueen [2] năm 2014 như sau: Cho 2 dữ liệu chuỗi thời gian X và Y với chiều dài dữ liệu chuỗi thời gian X và Y lần lượt là n và m với n > m và giá trị minlength là giá trị ràng buộc về chiều dài tối thiểu của các chuỗi con trong quá trình kết chuỗi. Bài toán tìm chuỗi con tương quan nhất giữa X và Y là tìm ra một cặp (X’, Y’) đồng thời thỏa mãn các điều kiện sao: - X’ là chuỗi con của chuỗi X.

Y’ là chuỗi con của chuỗi Y. - Distance(X’, Y’) = Min(Distance(Xi, Yi)), với Xi là chuỗi con của X, Yi là chuỗi con của Y và length(Xi) = length(Yi) = k và k > minlength.3 được trích từ công trình của Mueen [2] mô tả về bài toán tìm chuỗi con tương quan nhất giữa hai dữ liệu chuỗi thời gian là nhiệt độ và độ mặn được đo tại trạm ALOHA trên biển Thái Bình Dương ngày 12 tháng 10 năm 2003.3 Chuỗi con tương quan nhất giữa 2 chuỗi thời gian 2. Độ đo tương tự Độ tương tự (similarity measure) của hai đối tượng là mức độ sai khác của đối tượng dữ liệu này với đối tượng dữ liệu còn lại. Độ sai khác này được tính dựa trên một hàm gọi là hàm khoảng cách (distance fucntion).

Có rất nhiều tác giả đề nghị nhiều độ đo tương tự dựa trên các hàm khoảng cách khac nhau. Trong bài này 7 Kết chuỗi con trên dữ liệu chuỗi thời gian với sự hỗ trợ của cấu trúc chỉ mục TS-Tree sẽ giới thiệu hai độ đo được dùng phổ biến trong các nghiên cứu trên dữ liệu chuỗi thời gian là độ đo Euclid và độ đo xoắn thời gian động (Dynamic Time Warping). Độ đo Euclid Khoảng cách Euclid là một dạng phổ biến của khoảng cách Minkowski. Khoảng cách Minkowski được định nghĩa như sau: 𝑝 Sim(X,Y) = √∑𝑛𝑖=1(xi − yi)𝑝 , với p = 1 … ∞ Với p = 2, hàm khoảng cách trên là hàm tính khoảng cách Euclid.

Phương pháp này yêu cầu tính toán trên hai chuỗi thời gian có độ dài bằng nhau. Giả sử có hai chuỗi thời gian X = {x1, x2, x3,…, xn} và Y = {y1, y2, y3…, yn} là hai điểm trong không gian n chiều. Độ tương tự giữa hai chuỗi thời ian X và Y được định nghĩa bởi hàm tính khoảng cách Euclid giữa hai điểm trong không gian n chiều bởi công thức: D(X,Y) = √∑𝑛𝑖=1(xi − yi)2 Hình 2.3 mô tả việc tính độ tương tự giữa hai chuỗi thời gian bởi hàm tính khoảng cách Euclid. Độ tương tự của hai chuỗi thời gian áp dụng độ đo Euclid Ưu điểm của độ đo khoảng cách Euclid là dễ hiểu, quá trình tính toán đơn giản, dễ cài đặt và dễ mở rộng cho nhiều bái toán khai phá dữ liệu chuỗi thời gian.

Tuy nhiên, độ đo này có nhược điểm là nhạy cảm với nhiễu, khá cứng nhắc và không phù hợp với dữ liệu được đo với nhiều thang đo khác nhau. Độ đo xoắn thời gian động Độ đo xoắn thời gian động (Dynamic Time Warping - DTW) [16] cũng tương tự như độ đo khoảng cách Euclid, là một độ đo phổ biến trong các bài toán khai phá dữ liệu chuỗi thời gian. Phương pháp tính khoảng cách xoắn thời gian động cũng tương tự như cách tính khoảng cách Euclid nhưng thay vì so trùng hai chuỗi dữ liệu bằng cách tính khoảng cách từng cặp 1 – 1(điểm thứ i của chuỗi thứ 8 Kết chuỗi con trên dữ liệu chuỗi thời gian với sự hỗ trợ của cấu trúc chỉ mục TS-Tree nhất so với điểm thứ i của chuỗi thứ hai) thì một điểm có thể ánh xạ với nhiều điểm và ánh xạ này không tuyến tính.4 minh họa cách ánh xạ điểm trong phương pháp tính khoảng cách xoắn thời gian động giữa hai chuỗi thời gian. Khoảng cách xoắn thời gian động giữa hai chuỗi thời gian Giả sử cho hai chuỗi thời gian Q và C có chiều dài lần lượt là n và m như sau: Q = q1 , q2 , … , qi ,…, qn .