Luận văn thạc sĩ khoa học máy tính 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 tstree

Luận văn thạc sĩ khoa học máy tính nghiên cứu kết chuỗi con trên dữ liệu chuỗi thời gian với cây chỉ mục TSTree, ứng dụng hiệu quả trong phân tích dữ liệu.

• Tác giả: Lê Nhựt Trườ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: 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.4.1. Phương pháp kết chuỗi con trên dữ liệu đã lập chỉ mục
• 3.1.3.5. 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. Giới thiệu tổng quan

Luận văn thạc sĩ này tập trung vào 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 TSTree. Dữ liệu chuỗi thời gian đóng vai trò quan trọng trong nhiều lĩnh vực như kinh tế, tài chính, và khoa học kỹ thuật. Bài toán kết chuỗi con là một trong những vấn đề cơ bản trong phân tích dữ liệu, đặc biệt là trong việc tìm kiếm các chuỗi con tương tự. TSTree được đề xuất như một giải pháp hiệu quả để tăng tốc quá trình tìm kiếm và nâng cao độ chính xác.

1.1 Mục tiêu nghiên cứu

Mục tiêu chính của nghiên cứu là tìm hiểu và áp dụng các phương pháp phân đoạn dữ liệu chuỗi thời gian, sử dụng độ đo xoắn thời gian động (DTW) để tính toán độ tương tự, và xây dựng cây chỉ mục TSTree để tối ưu hóa quá trình kết chuỗi con. Nghiên cứu cũng nhằm so sánh hiệu quả của phương pháp đề xuất với các phương pháp truyền thống.

1.2 Kết quả đạt được

Nghiên cứu đã đạt được những kết quả quan trọng, bao gồm việc áp dụng thành công phương pháp phân đoạn dựa trên các điểm cực trị quan trọng, sử dụng TSTree để tăng tốc độ tìm kiếm, và chứng minh được hiệu quả của DTW trong việc nâng cao độ chính xác của bài toán kết chuỗi con.

II. Cơ sở lý thuyết

Chương này trình bày các khái niệm cơ bản về dữ liệu chuỗi thời gian, bài toán kết chuỗi con, và các độ đo tương tự như DTW. Dữ liệu chuỗi thời gian là một chuỗi các giá trị được ghi nhận theo thời gian, thường được sử dụng trong các bài toán phân tích dữ liệu. Kết chuỗi con là bài toán tìm các chuỗi con tương tự giữa hai chuỗi dữ liệu thời gian. DTW là một độ đo linh hoạt, cho phép so sánh các chuỗi có độ dài khác nhau.

2.1 Dữ liệu chuỗi thời gian

Dữ liệu chuỗi thời gian là một chuỗi các giá trị được ghi nhận theo thời gian, thường được biểu diễn dưới dạng các cặp <thời gian, giá trị>. Loại dữ liệu này xuất hiện trong nhiều lĩnh vực như tài chính, y tế, và môi trường.

2.2 Bài toán kết chuỗi con

Bài toán kết chuỗi con liên quan đến việc tìm các chuỗi con tương tự giữa hai chuỗi dữ liệu thời gian. Đây là một bài toán quan trọng trong khai phá dữ liệu, với nhiều ứng dụng thực tiễn như dự báo kinh tế và phân tích tài chính.

2.3 Độ đo xoắn thời gian động DTW

DTW là một độ đo tương tự linh hoạt, cho phép so sánh các chuỗi thời gian có độ dài khác nhau. Độ đo này đặc biệt hữu ích trong việc tìm kiếm các chuỗi con tương tự, với độ chính xác cao hơn so với các độ đo truyền thống như Euclid.

III. Phương pháp đề xuất

Phương pháp đề xuất trong nghiên cứu này bao gồm việc phân đoạn dữ liệu chuỗi thời gian dựa trên các điểm cực trị quan trọng, sử dụng cây chỉ mục TSTree để tăng tốc quá trình tìm kiếm, và áp dụng DTW để tính toán độ tương tự. Phương pháp này được thiết kế để giải quyết các hạn chế của các phương pháp truyền thống, đặc biệt là về thời gian tính toán và độ chính xác.

3.1 Phân đoạn dữ liệu

Phương pháp phân đoạn dữ liệu dựa trên các điểm cực trị quan trọng giúp chia nhỏ chuỗi thời gian thành các đoạn có ý nghĩa, từ đó tăng hiệu quả của quá trình tìm kiếm các chuỗi con tương tự.

3.2 Cây chỉ mục TSTree

TSTree là một cấu trúc chỉ mục hiệu quả, được sử dụng để tăng tốc quá trình tìm kiếm các chuỗi con tương tự. Cấu trúc này giúp giảm thời gian tính toán và nâng cao độ chính xác của bài toán kết chuỗi con.

3.3 Độ đo DTW

DTW được sử dụng để tính toán độ tương tự giữa các chuỗi con, với ưu điểm là linh hoạt và chính xác hơn so với các độ đo truyền thống. Độ đo này đặc biệt phù hợp với các chuỗi thời gian có độ dài khác nhau.

IV. Thực nghiệm và kết quả

Nghiên cứu đã tiến hành các thực nghiệm để so sánh hiệu quả của phương pháp đề xuất với các phương pháp truyền thống. Kết quả cho thấy phương pháp sử dụng TSTree và DTW đạt được hiệu quả cao hơn về cả thời gian tính toán và độ chính xác.

4.1 Thực nghiệm so sánh

Các thực nghiệm được tiến hành trên nhiều bộ dữ liệu khác nhau, bao gồm dữ liệu tài chính, sinh học, và môi trường. Kết quả cho thấy phương pháp đề xuất giảm đáng kể thời gian tính toán so với phương pháp truyền thống.

4.2 Đánh giá độ chính xác

Phương pháp đề xuất cũng đạt được độ chính xác cao hơn trong việc tìm kiếm các chuỗi con tương tự, nhờ vào việc sử dụng DTW và TSTree.

V. Kết luận và hướng phát triển

Nghiên cứu đã chứng minh hiệu quả của phương pháp đề xuất trong việc giải quyết bài toán kết chuỗi con trên dữ liệu chuỗi thời gian. TSTree và DTW là những công cụ quan trọng giúp tăng tốc quá trình tìm kiếm và nâng cao độ chính xác. Hướng phát triển trong tương lai bao gồm việc tối ưu hóa cấu trúc TSTree và mở rộng ứng dụng của phương pháp này trong các lĩnh vực khác.

5.1 Đóng góp của nghiên cứu

Nghiên cứu đã đóng góp vào việc cải thiện hiệu quả của bài toán kết chuỗi con thông qua việc sử dụng TSTree và DTW. Phương pháp đề xuất có thể được áp dụng rộng rãi trong các lĩnh vực như tài chính, y tế, và môi trường.

5.2 Hướng phát triển

Hướng phát triển trong tương lai bao gồm việc tối ưu hóa cấu trúc TSTree, mở rộng ứng dụng của phương pháp này trong các lĩnh vực khác, và tích hợp các kỹ thuật học máy để nâng cao hiệu quả của bài toán kết chuỗi con.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của các thiết bị cảm biến và hạ tầng số hóa đã tạo ra khối lượng dữ liệu chuỗi thời gian khổng lồ trong các lĩnh vực như tài chính, y tế, khí tượng và năng lượng. Theo ước tính từ các báo cáo công nghệ, dữ liệu chuỗi thời gian chiếm hơn 70% tổng lượng dữ liệu phát sinh tại các hệ thống quan trắc thời gian thực. Trong bối cảnh đó, bài toán kết chuỗi con (Subsequence Join) giữ vai trò then chốt trong việc tìm kiếm các đoạn tín hiệu có hình thái tương đồng giữa hai chuỗi thời gian riêng biệt, chẳng hạn như phân tích mối tương quan giữa chỉ số chứng khoán VN-Index và biến động giá vàng, hoặc so sánh diễn biến tỷ giá giữa các cặp ngoại tệ.

Tuy nhiên, các thuật toán kết chuỗi con truyền thống gặp phải rào cản rất lớn về hiệu năng tính toán. Khi áp dụng phương pháp cửa sổ trượt từng điểm kết hợp độ đo khoảng cách phi tuyến tính xoắn thời gian động (Dynamic Time Warping - DTW), độ phức tạp thời gian đạt mức cấp số nhân $O(n \times m)$, khiến thời gian xử lý kéo dài hàng giờ đối với các tập dữ liệu có quy mô từ 10.000 đến 100.000 điểm đo. Ngược lại, nếu trượt theo phân đoạn cố định, tỷ lệ bỏ sót các chuỗi con tương tự có thể vượt quá 35%.

Đề tài luận văn thạc sĩ chuyên ngành Khoa học Máy tính tại Trường Đại học Bách Khoa – ĐHQG TP.HCM đặt mục tiêu xây dựng giải pháp kết chuỗi con hiệu năng cao. Nghiên cứu tập trung giải quyết bài toán bằng cách phân đoạn chuỗi thời gian theo các điểm cực trị quan trọng, đồng thời tích hợp cấu trúc cây chỉ mục TS-Tree (Time Series Tree) nhằm tăng tốc độ truy vấn mà vẫn bảo toàn độ chính xác tuyệt đối. Quá trình nghiên cứu và thực nghiệm được tiến hành liên tục trong thời gian 5 tháng (từ tháng 07/2017 đến tháng 12/2017). Kết quả nghiên cứu giúp giảm thiểu đáng kể chi phí truy xuất dữ liệu, tối ưu hóa thời gian thực thi gấp 3 đến 8 lần so với giải thuật trực tiếp, mang lại giá trị thực tiễn cao cho các bài toán khai phá dữ liệu quy mô lớn.

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 dựa trên sự kết hợp chặt chẽ giữa hai nền tảng lý thuyết tiên tiến trong lĩnh vực khai phá dữ liệu chuỗi thời gian:

1. Lý thuyết độ đo tương tự và kỹ thuật bao cận DTW: Độ đo xoắn thời gian động (Dynamic Time Warping - DTW) cho phép so khớp hai chuỗi tín hiệu có tốc độ biến thiên và chiều dài khác nhau dựa trên ma trận khoảng cách phi tuyến tính. Để giảm độ phức tạp $O(n \times m)$, nghiên cứu ứng dụng hàm bao cận dưới LB_Keogh kết hợp kỹ thuật từ bỏ sớm (early abandoning) cùng các ràng buộc biên Sakoe-Chiba, giúp loại bỏ các ứng viên không tiềm năng mà không cần tính toán toàn bộ ma trận đường xoắn.
2. Cấu trúc chỉ mục phân cấp nhiều chiều TS-Tree: Được phát triển trên nền tảng cây R*-Tree và nguyên lý phân tách của B-Tree, TS-Tree tổ chức dữ liệu theo các khoảng biên cận trên, cận dưới (Upper/Lower bounds) kết hợp biểu diễn rời rạc hóa SAX (Symbolic Aggregate Approximation) và phương pháp xấp xỉ PAA (Piecewise Aggregate Approximation). Nhờ đó, cây chỉ mục loại bỏ hiện tượng trùng lặp không gian (MBR overlap), duy trì độ phân nhánh cao và hỗ trợ trực tiếp hàm khoảng cách DTW.

Bên cạnh đó, nghiên cứu vận dụng khái niệm điểm cực trị quan trọng (Important Extreme Points) nhằm trích xuất các đỉnh sóng và đáy sóng đặc trưng, kết hợp phép biến đổi vị tự (Homothetic Transformation) với hệ số tỷ lệ xác định để đồng nhất độ dài các phân đoạn truy vấn mà vẫn bảo toàn hình thái hình học ban đầu.

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

• Nguồn dữ liệu và cỡ mẫu thực nghiệm: Nghiên cứu sử dụng 8 bộ dữ liệu thực nghiệm chuẩn hóa với quy mô dao động từ 1.000 đến hơn 15.000 điểm dữ liệu cho mỗi chuỗi. Các bộ dữ liệu bao gồm: Chromosome_1, Chromosome_2 (y sinh học), Runoff (thủy văn), Power_Italy (tiêu thụ điện năng), Currency (tỷ giá tài chính), Stock (thị trường chứng khoán) cùng 2 tập dữ liệu bước đi ngẫu nhiên tổng hợp RW-1 và RW-2.
• Phương pháp chọn mẫu: Lựa chọn mẫu phi xác suất có chủ đích từ kho dữ liệu chuẩn UCR Time Series Data Mining Repository, bao gồm cả dữ liệu tự nhiên có chu kỳ, dữ liệu biến động ngẫu nhiên và dữ liệu chuỗi thời gian công nghiệp thực tế.
• Lý do lựa chọn phương pháp phân tích: Dữ liệu chuỗi thời gian thô thường chứa nhiều nhiễu và biên độ không đồng nhất. Quy trình xử lý sử dụng chuẩn hóa Z (Z-score Normalization) đưa dữ liệu về đường căn bản trung bình $x = 0$ và độ lệch chuẩn bằng 1, tiếp nối bằng chuẩn hóa Min-Max để đồng bộ thang đo biên độ. Hệ số nén $R$ được xác định tự động qua công thức thống kê $R = 2 \times SD$ (với $SD$ là độ lệch chuẩn của chuỗi), đảm bảo phân đoạn chuỗi phản ánh chính xác cấu trúc hình thái mà không phụ thuộc vào cảm tính chủ quan.

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 giải thuật kết chuỗi con trực tiếp và phương pháp đề xuất sử dụng cây chỉ mục TS-Tree trên 8 tập dữ liệu mang lại những phát hiện quan trọng:

1. Tối ưu hóa không gian tìm kiếm vượt trội: Việc áp dụng kỹ thuật phân đoạn theo điểm cực trị quan trọng với tham số $R = 2 \times SD$ đã giúp cô đọng chuỗi dữ liệu hàng nghìn điểm thành khoảng 40 đến 120 phân đoạn có ý nghĩa đặc trưng. Điều này giúp giảm hơn 75% số lượng ứng viên cần duyệt so với cách trượt từng điểm truyền thống.
2. Hiệu suất tỉa nhánh cao của cây chỉ mục TS-Tree: Nhờ cơ chế lưu trữ cận trên và cận dưới kết hợp hàm khoảng cách Mindist (bao gồm Sl-Mindist, Sr-Mindist và MD-Mindist), cấu trúc TS-Tree đã loại trừ thành công từ 65% đến 85% các nhánh cây không thỏa mãn ngưỡng sai số $\varepsilon$ ngay từ các nút trung gian, triệt tiêu hoàn toàn chi phí đọc ngẫu nhiên trên đĩa.
3. Rút ngắn thời gian thực thi: Trên toàn bộ 8 tập dữ liệu, phương pháp sử dụng cây chỉ mục TS-Tree cho tốc độ xử lý nhanh hơn từ 3,2 lần đến 8,1 lần so với giải thuật trực tiếp. Ví dụ, trên tập dữ liệu Power_Italy và Chromosome_1, thời gian thực thi giảm từ khoảng 45 giây xuống còn chưa đầy 8 giây.
4. Độ chính xác tuyệt đối: Thuật toán không ghi nhận bất kỳ trường hợp tìm sót ứng viên tương đồng (zero false dismissals), chứng minh phép biến đổi vị tự duy trì trọn vẹn đặc trưng hình thái của chuỗi con ban đầu.

Thảo luận kết quả

Hiệu năng vượt bậc của mô hình xuất phát từ sự tương thích hoàn hảo giữa cấu trúc chỉ mục TS-Tree và độ đo xoắn thời gian động DTW. Trong các cấu trúc chỉ mục không gian truyền thống như R-Tree hay M-Tree, khi số chiều dữ liệu vượt quá ngưỡng 16, hiện tượng "lời nguyền số chiều" (curse of dimensionality) khiến các hình chữ nhật bao quanh (MBR) chồng lấn nghiêm trọng, dẫn đến việc giải thuật phải duyệt qua hầu hết các nút lá. Ngược lại, TS-Tree sử dụng các thành phần phân tách (separators) dạng chuỗi ký tự SAX và PAA, giúp duy trì cấu trúc cây phân cấp cân bằng và mở rộng không gian tỉa nhánh.

Dữ liệu thực nghiệm có thể được biểu diễn trực quan thông qua biểu đồ cột so sánh thời gian thực thi (tính bằng giây) giữa hai phương pháp trên từng bộ dữ liệu, kết hợp với bảng thông số hiển thị rõ giá trị hệ số nén $R$, số lượng phân đoạn sinh ra và ngưỡng sai số $\varepsilon$. So với công trình của Yi Lin (2010) vốn dựa trên đa thức đặc trưng phức tạp và độ đo Euclid cứng nhắc, phương pháp trong luận văn có độ mềm dẻo cao hơn khi nhận dạng được các chuỗi đồng dạng bị co giãn theo trục thời gian. Đồng thời, nghiên cứu đã khắc phục triệt để nhược điểm bỏ sót chuỗi con của giải thuật trượt phân đoạn do Võ Đức Vĩnh và Dương Tuấn Anh công bố năm 2016.

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

Nhằm chuyển giao và mở rộng kết quả nghiên cứu vào các hệ thống khai phá dữ liệu thực tế, luận văn đưa ra 4 khuyến nghị cụ thể:

1. Tích hợp cấu trúc TS-Tree vào hệ quản trị cơ sở dữ liệu chuỗi thời gian: Đội ngũ kỹ sư dữ liệu và kiến trúc sư hệ thống cần tiến hành đóng gói giải thuật thành module mở rộng cho các hệ thống như InfluxDB hoặc TimescaleDB. Mục tiêu nhằm giảm ít nhất 50% độ trễ truy vấn tương quan trên tập dữ liệu lớn trong lộ trình triển khai từ 6 đến 12 tháng.
2. Tự động hóa việc điều chỉnh tham số bằng học máy: Các nhóm nghiên cứu trí tuệ nhân tạo nên áp dụng các mô hình tối ưu hóa Bayes để tự động xác định ngưỡng sai số $\varepsilon$ và tham số nén $R$ thay vì dựa vào quan sát chuyên gia. Dự án này cần hoàn thành trong vòng 9 tháng để nâng cao độ chính xác phân đoạn thêm 15% đến 20%.
3. Mở rộng xử lý song song trên nền tảng phân tán: Đội ngũ phát triển Big Data cần triển khai phân tán cấu trúc chỉ mục TS-Tree trên nền tảng Apache Spark hoặc tính toán song song với GPU CUDA. Kế hoạch trong vòng 12 tháng hướng tới mục tiêu xử lý chuỗi thời gian có quy mô trên 10 triệu điểm đo với thông lượng tăng gấp 10 lần.
4. Ứng dụng giải thuật vào hệ thống cảnh báo sớm y tế và lưới điện: Ban quản lý vận hành năng lượng và các trung tâm tim mạch nên ứng dụng ngay mô hình kết chuỗi con để phát hiện sớm các bất thường trên tín hiệu điện tim (ECG) và biến động phụ tải điện lưới theo thời gian thực dưới 200 mili-giây.

Đố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ị học thuật và ứng dụng sâu sắc cho 4 nhóm đối tượng chính:

1. Học viên cao học và nghiên cứu sinh ngành Khoa học Máy tính / Khoa học Dữ liệu: Tài liệu cung cấp cơ sở lý thuyết hoàn chỉnh về các độ đo khoảng cách chuỗi thời gian, phương pháp chứng minh chặn dưới và cách thiết kế cấu trúc cây chỉ mục nâng cao.
2. Chuyên gia phân tích định lượng và kỹ sư tài chính: Ứng dụng giải thuật kết chuỗi con để dò tìm các giai đoạn biến động tương đồng giữa các cổ phiếu, cặp tỷ giá ngoại hối hoặc chỉ số thị trường nhằm xây dựng chiến lược giao dịch thuật toán tối ưu.
3. Kỹ sư nghiên cứu và phát triển thiết bị Y tế / IoT: Sử dụng phương pháp phân đoạn theo cực trị quan trọng và độ đo DTW để nhận dạng mẫu sóng bất thường trên các thiết bị đo điện não đồ, điện tâm đồ hoặc dữ liệu cảm biến rung chấn công nghiệp.
4. Kiến trúc sư giải pháp cơ sở dữ liệu lớn: Tham khảo quy trình rời rạc hóa SAX và cơ chế quản lý chỉ mục không phủ lấp của TS-Tree để thiết kế các công cụ truy vấn dữ liệu chuỗi thời gian tốc độ cao.

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

1. Bài toán kết chuỗi con (Subsequence Join) khác gì so với bài toán so trùng chuỗi con (Subsequence Matching)?
So trùng chuỗi con là thao tác tìm kiếm các đoạn chuỗi trong cơ sở dữ liệu có hình dạng tương tự với một chuỗi mẫu truy vấn cho trước. Trong khi đó, kết chuỗi con là bài toán tổng quát hơn, thực hiện việc tìm tất cả các cặp chuỗi con tương đồng giữa hai chuỗi thời gian bất kỳ mà không cần biết trước chuỗi mẫu.

2. Vì sao luận văn sử dụng độ đo DTW thay vì khoảng cách Euclid?
Khoảng cách Euclid chỉ so khớp điểm đối điểm trên hai chuỗi có cùng độ dài và rất nhạy cảm với nhiễu. Độ đo DTW cho phép ánh xạ một điểm với nhiều điểm theo quan hệ phi tuyến, giúp nhận dạng chính xác hai mẫu tín hiệu có hình thái giống nhau nhưng bị co giãn hoặc lệch pha trên trục thời gian.

3. Tham số R trong giải thuật phân đoạn có ý nghĩa gì?
Tham số $R$ đóng vai trò là ngưỡng biên độ tối thiểu để xác nhận một điểm cực trị có ý nghĩa đặc trưng hay chỉ là dao động nhiễu. Giá trị $R$ được ước lượng tự động bằng hai lần độ lệch chuẩn ($R = 2 \times SD$) giúp tối ưu hóa số lượng phân đoạn chuỗi một cách khoa học.

4. Phép biến đổi vị tự đóng vai trò như thế nào trong quy trình kết chuỗi?
Do các phân đoạn sinh ra từ các điểm cực trị có độ dài không đều nhau, phép biến đổi vị tự (Homothetic Transformation) được sử dụng để đưa tất cả các chuỗi con truy vấn về một độ dài trung bình cố định mà vẫn giữ nguyên tỷ lệ hình thái ban đầu trước khi đối sánh trên cây TS-Tree.

5. Cây chỉ mục TS-Tree giải quyết nhược điểm gì của cây R-Tree truyền thống?
Cây R-Tree bị suy giảm hiệu năng nghiêm trọng khi dữ liệu có nhiều chiều do các hình chữ nhật bao quanh (MBR) bị chồng lấn lớn. TS-Tree khắc phục triệt để điều này bằng cách lưu trữ trực tiếp cận trên, cận dưới và sử dụng các thành phần phân tách chuỗi, hỗ trợ tính toán khoảng cách bao dưới DTW cực kỳ hiệu quả.

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 mô hình tích hợp phân đoạn cực trị quan trọng và cấu trúc cây chỉ mục TS-Tree.
• Đề tài đóng góp phương pháp luận chuẩn hóa dữ liệu kết hợp Z-score, Min-Max và phép biến đổi vị tự giúp đồng nhất độ dài chuỗi con mà không làm biến dạng tín hiệu gốc.
• Cấu trúc chỉ mục TS-Tree cùng độ đo xoắn thời gian động DTW được chứng minh thực nghiệm giúp tăng tốc độ truy vấn từ 3 đến 8 lần so với giải thuật trực tiếp trên 8 bộ dữ liệu tiêu chuẩn.
• Nghiên cứu triệt tiêu hoàn toàn hiện tượng bỏ sót chuỗi con tương đồng, tạo tiền đề vững chắc cho việc xử lý các bài toán khai phá dữ liệu lớn trong thực tế.
• Lộ trình 12 tháng tới sẽ tiếp tục mở rộng mô hình cho dữ liệu chuỗi thời gian đa biến và tích hợp thuật toán trên môi trường điện toán đám mây phân tán.

Các tổ chức, doanh nghiệp và nhà nghiên cứu quan tâm đến việc ứng dụng giải pháp tối ưu hóa dữ liệu chuỗi thời gian có thể khai thác và ứng dụng trực tiếp mô hình này vào hệ thống của mình.

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 .