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

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.

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 .