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

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.

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 .