Phát biểu vấn đề
Dữ liệu chuỗi thời gian
Dữ liệu chuỗi thời gian là một phần quan trọng trong nhiều lĩnh vực ứng dụng, bao gồm khoa học kỹ thuật, kinh tế và tài chính Một ví dụ điển hình là dự án MACHCO, với cơ sở dữ liệu thiên văn học có dung lượng lên tới nửa terabyte và được cập nhật hàng ngày với tốc độ vài gigabyte Do đó, việc phát triển các phương pháp quản lý và xử lý hiệu quả dữ liệu chuỗi thời gian là rất cần thiết để đáp ứng các yêu cầu ngày càng cao trong lĩnh vực này.
Dữ liệu chuỗi thời gian là tập hợp các quan sát đơn biến hoặc đa biến được ghi nhận theo thứ tự và cách quãng thời gian đều đặn Cụ thể, chuỗi thời gian T = t1, t2, , tm bao gồm các giá trị thực được đo trong những khoảng thời gian nhất định Hình 1.1 minh họa một đường cong thể hiện chuỗi thời gian này.
Hình 1.1 Đường cong biểu diễn chuỗi thời gian
Từ những thập niên trước đến nay, khai phá dữ liệu chuỗi thời gian đã thu hút sự chú ý nghiên cứu đáng kể trên toàn cầu, đặc biệt trong một số lĩnh vực nghiên cứu quan trọng.
1 Tìm kiếm tương tự (Similarity Search): cho một chuỗi thời gian truy vấn Q, và một hàm đo độ tương tự hoặc độ khác nhau D(Q,C), tìm những chuỗi thời gian tương tự nhất với Q trong CSDL DB nào đó
2 Gom cụm (Clustering): tìm những sự phân nhóm theo tự nhiên của những chuỗi thời gian trong CSDL DB theo một hàm đo độ tương tự/độ khác nhau D(Q,C)
3 Phân nhóm (Classification): cho một chuỗi thời gian chƣa gán nhóm Q, gán nó vào một trong những nhóm đã được định nghĩa trước
4 Tóm tắt (Summarization): cho chuỗi thời gian Q có n điểm dữ liệu trong đó n là con số rất lớn, tạo một sự xấp xỉ của Q để vừa khít theo một giới hạn nào đó
(chẳng hạn màn hình máy tính, trang giấy, …) sao cho vẫn duy trì những đặc trƣng bản chất của nó
5 Phát hiện bất đồng (Anomaly Detection): cho một chuỗi thời gian Q, và một vài mô hình hành vi “bình thường” (“normal” behavior) Tìm tất cả những phần thuộc Q có chứa “bất đồng” Những hành vi “bất đồng” có nhiều tên gọi khác nhƣ những hành vi “surprising/ interesting/ unexpected/ novel”
Dữ liệu chuỗi thời gian thường rất lớn, dẫn đến việc cần lưu trữ trong bộ nhớ ngoài Điều này gây ra nhiều lần truy cập bộ nhớ ngoài trong quá trình xử lý, làm xuất hiện hiện tượng “thắt cổ chai” trong các nhiệm vụ khai phá dữ liệu Để giải quyết vấn đề này, một khung chung cho các nhiệm vụ khai phá dữ liệu chuỗi thời gian đã được đề xuất.
Tạo một xấp xỉ dữ liệu sao cho nó vừa khít với bộ nhớ chính, nhƣng không làm mất đi những đặc trƣng cần quan tâm của dữ liệu
2 Giải quyết tương đối bài toán với dữ liệu trong bộ nhớ chính
Truy cập đĩa ngoài, kiểm tra lời giải ở bước 2 với dữ liệu gốc, bổ sung lời giải này sao cho phù hợp với dữ liệu gốc
Bảng 1.1 Cách tiếp cận cho các nhiệm vụ khai phá dữ liệu chuỗi thời gian
Hiệu quả của phương pháp xấp xỉ phụ thuộc vào chất lượng của bước đầu tiên; nếu xấp xỉ gần với dữ liệu gốc, lời giải trên tập dữ liệu trong bộ nhớ chính sẽ chính xác hơn Điều này làm giảm tầm quan trọng của việc truy cập dữ liệu gốc từ đĩa ngoài để điều chỉnh lời giải Nhiều nghiên cứu đã tập trung vào các phương pháp biểu diễn xấp xỉ dữ liệu chuỗi thời gian, và trong bài viết này, chúng tôi sẽ so sánh chất lượng và hiệu quả của các phương pháp này trong các nhiệm vụ khai thác dữ liệu chuỗi thời gian, đặc biệt là trong lĩnh vực tìm kiếm tương tự và phát hiện chuỗi con “bất đồng”.
Tìm kiếm tương tự (similarity search) là một yếu tố quan trọng trong các ứng dụng khai phá dữ liệu chuỗi thời gian Các yêu cầu tìm kiếm tương tự thường được phân loại thành hai loại chính: so trùng toàn bộ và so trùng chuỗi con.
So trùng toàn bộ là một phương pháp trong đó chiều dài của chuỗi dữ liệu truy vấn và dữ liệu ban đầu phải bằng nhau Kỹ thuật này thường được áp dụng trong việc gom cụm và phân loại dữ liệu chuỗi thời gian.
Ví dụ, “tìm mức nước ở hai con sông có thay đổi giống nhau trong một năm”, hay
“tìm giá chứng khoán của những công ty nào thay đổi giống nhau”
So trùng chuỗi con (subsequence matching) là một bài toán trong đó chiều dài của dữ liệu truy vấn ngắn hơn nhiều so với dữ liệu ban đầu Nhiệm vụ chính của bài toán này là tìm kiếm các đoạn dữ liệu ban đầu tương tự với dữ liệu truy vấn Một số ứng dụng của bài toán bao gồm việc phát hiện các mẫu dữ liệu quan trọng và nhận diện những thay đổi bất thường trong dữ liệu ban đầu.
Tìm kiếm những tháng trong quá khứ có lượng mưa tương tự như tháng hiện tại hoặc những tháng mà giá chứng khoán của công ty có sự biến động giống với tháng hiện tại.
1.1.2 Phát hiện chuỗi con “bất đồng”
Lĩnh vực tìm kiếm chuỗi con "bất đồng" trong dữ liệu chuỗi thời gian có nhiều ứng dụng quan trọng trong khai phá dữ liệu, như cải thiện chất lượng gom cụm và làm sạch dữ liệu Hình 1.1 minh họa rõ nét về các chuỗi con "bất đồng" được phát hiện trong dữ liệu điện tâm đồ của con người.
Hình 1.2 Minh họa chuỗi con“bất đồng” (đường in đậm) trong dữ liệu điện tâm đồ của con người
Chuỗi con "bất đồng" đã được biết đến với nhiều tên gọi và định nghĩa khác nhau Trong bài viết này, chúng tôi áp dụng định nghĩa chuỗi dữ liệu thời gian bất đồng dựa trên nghiên cứu của Keogh và các đồng nghiệp vào năm 2005.
1.1.3 Các phương pháp biểu diễn xấp xỉ
Dữ liệu chuỗi thời gian thường có kích thước rất lớn, khiến cho việc tìm kiếm trực tiếp trở nên phức tạp và không hiệu quả Để giải quyết vấn đề này, cần áp dụng các phương pháp biến đổi để giảm kích thước dữ liệu, được gọi là kỹ thuật thu giảm số chiều Ba phương pháp chính để thực hiện điều này bao gồm biến đổi sang miền tần số, xấp xỉ tuyến tính từng đoạn, và sử dụng điểm quan trọng.
Mục tiêu và giới hạn của đề tài
Mục tiêu của nghiên cứu này là đánh giá hiệu quả của hai phương pháp xấp xỉ: thứ nhất, so sánh phương pháp xấp xỉ gộp từng đoạn mở rộng EPAA với phương pháp xấp xỉ gộp từng đoạn PAA; thứ hai, phân tích hiệu quả của phương pháp xấp xỉ gộp ký hiệu hóa mở rộng ESAX so với phương pháp xấp xỉ gộp ký hiệu SAX.
1.2.1 Giải quyết vấn đề thứ nhất Để đánh giá hiệu quả của phương pháp EPAA với PAA, đề tài sử dụng từng phương pháp này để giải quyết bài toán so trùng mẫu con Khi đó, từ dữ liệu ban đầu là một chuỗi các số thực, mỗi số thực thể hiện giá trị tại một thời điểm Với dữ liệu đó, ta cho phép người dùng đặc tả một mẫu dữ liệu truy vấn (mẫu này thường rất nhỏ so với dữ liệu ban đầu) Khi đó, chương trình sẽ tìm trong dữ liệu đầu những mẫu con nào tương tự với mẫu truy vấn Các mẫu con tương tự với mẫu truy vấn về hình dạng và độ chênh lệch là ít nhất
Bài toán so trùng chuỗi con trên dữ liệu chuỗi thời gian là một dạng tìm kiếm với kích thước dữ liệu lớn, đòi hỏi áp dụng các phương pháp lập chỉ mục để nâng cao tốc độ tìm kiếm Các phương pháp này có thể bao gồm giảm số chiều để giảm kích thước dữ liệu hoặc sử dụng các cấu trúc biểu diễn dữ liệu hiệu quả Luận văn này sẽ trình bày chi tiết về các phương pháp lập chỉ mục được áp dụng trong nghiên cứu.
- Tìm hiểu và tiến hành biểu diễn dữ liệu chuỗi thời gian ban đầu lần lƣợt bằng phương pháp EPAA và PAA
- Đề nghị sử dụng cấu trúc chỉ mục R*-tree lưu trữ dữ liệu sau khi đã thu giảm nhằm nâng câo tốc độ tìm kiếm
- Hiện thực chương trình hỗ trợ người dùng so trùng mẫu thân thiện với người dùng
Trong bài viết này, chúng tôi sẽ so sánh hai phương pháp EPAA và PAA dựa trên các tiêu chí như độ chặt chặn dưới, tỉ lệ thu giảm truy xuất và thời gian CPU Đặc biệt, việc so sánh theo tiêu chí độ chặt chặn dưới không bị ảnh hưởng bởi cấu trúc chỉ mục Chúng tôi cũng sẽ trình bày hàm tính khoảng cách cho cả hai phương pháp này.
1.2.2 Giải quyết vấn đề thứ hai Để đánh giá hiệu quả của phương pháp ESAX và SAX, đề tài áp dụng 2 phương pháp để giải quyết bài toán phát hiện chuỗi con “bất đồng” trong chuỗi dữ liệu chuỗi thời gian Cụ thể, luận văn tiến hành nhƣ sau:
- Tìm hiểu và hiện thực rời rạc hóa dữ liệu bằng phương pháp rời rạc hóa ký hiệu SAX và ESAX
Chúng tôi khuyến nghị áp dụng giải thuật HOT SAX để phát hiện sự "bất đồng" trong chuỗi dữ liệu thời gian Bài viết sẽ trình bày cách tìm hiểu và xây dựng cấu trúc SAX cùng với cây gia tố nhằm hỗ trợ quá trình tìm kiếm Cuối cùng, chúng tôi sẽ áp dụng SAX và ESAX trong giải thuật HOT SAX.
Bài viết này so sánh hai phương pháp ESAX và SAX trong giải thuật HOT SAX trên nhiều loại bộ dữ liệu khác nhau Các tiêu chí so sánh bao gồm số lần gọi hàm tính độ tương tự trong không gian nguyên thủy và thời gian thực thi CPU của giải thuật.
Tóm lƣợc những kết quả đạt đƣợc
Trong thời gian thực, chúng tôi đã phát triển thành công hai hệ thống: một là hệ thống tìm kiếm tương tự, và hai là hệ thống tìm kiếm chuỗi con bất đồng.
1.3.1 Hệ thống tìm kiếm tương tự
Hệ thống bao gồm bốn mô-đun chính: mô-đun tạo tập dữ liệu thực nghiệm, mô-đun biểu diễn dữ liệu chuỗi thời gian, mô-đun cấu trúc dữ liệu và mô-đun tìm kiếm tương tự.
Môđun đầu tiên có nhiệm vụ rút trích ngẫu nhiên các chuỗi con từ dữ liệu chuỗi thời gian gốc, nhằm tạo ra một tập dữ liệu các chuỗi con phục vụ cho các thí nghiệm.
- Môđun thứ hai có chức năng biểu diễn dữ liệu chuỗi thời gian theo hai phương pháp xấp xỉ gộp từng đoạn PAA và EPAA
- Môđun thứ ba xây dựng cấu trúc chỉ mục R*-tree nhằm phục vụ đánh chỉ mục cho dữ liệu biểu diễn xấp xỉ
- Môđun thứ tƣ hiện thực các thủ tục sử dụng môđun thứ hai và môđun thứ ba để đưa ra kết quả tìm kiếm tương tự
Hệ thống của chúng tôi thực hiện các thí nghiệm với các thông số đa dạng cho từng loại dữ liệu nhằm đánh giá và so sánh hiệu quả giữa phương pháp PAA và EPAA trong bài toán tìm kiếm tương tự Kết quả cho thấy phương pháp EPAA tỏ ra hiệu quả hơn PAA Như vậy, hệ thống đã đáp ứng đầy đủ yêu cầu và nhiệm vụ của đề tài.
1.3.2 Hệ thống tìm chuỗi con “bất đồng”
Hệ thống bao gồm bốn môđun chính: môđun tạo dữ liệu thực nghiệm, môđun biểu diễn dữ liệu chuỗi thời gian, môđun cấu trúc dữ liệu và môđun tìm kiếm chuỗi con "bất đồng".
- Môđun thứ nhất giống môđun tạo tập dữ liệu thực nghiệm của hệ thống tìm kiếm tương tự ở trên
- Môđun thứ hai, chúng tôi hiện thực 2 phương pháp rời rạc hóa dữ liệu chuỗi thời gian là SAX và ESAX
Trong môđun thứ ba, chúng tôi phát triển các cấu trúc dữ liệu tương ứng với từng phương pháp rời rạc hóa dữ liệu chuỗi thời gian, bao gồm cấu trúc dãy SAX và cây gia tố (Augmented Trie) cho phương pháp SAX và ESAX Những cấu trúc dữ liệu này được sử dụng để tạo ra heuristic cho vòng lặp ngoài và vòng lặp trong trong môđun tìm kiếm chuỗi con bất đồng.
Môđun tìm kiếm chuỗi con "bất đồng" đã được cải tiến với việc triển khai giải thuật HOT SAX và HOT ESAX Cả hai giải thuật này thực chất tương tự nhau, nhưng tên gọi được thay đổi để nhấn mạnh sự khác biệt khi ứng dụng phương pháp ESAX vào giải thuật HOT SAX.
Hệ thống của chúng tôi thực hiện các thí nghiệm với các thông số khác nhau cho từng loại dữ liệu nhằm đánh giá và so sánh hiệu quả giữa phương pháp SAX và ESAX trong việc tìm kiếm chuỗi con “bất đồng” Kết quả cho thấy phương pháp ESAX vượt trội hơn so với SAX Do đó, hệ thống đã đáp ứng đầy đủ các yêu cầu và nhiệm vụ của đề tài.
Cấu trúc của luận văn
Phần còn lại của luận văn đƣợc tổ chức theo cấu trúc sau đây:
Chương 2 sẽ tổng quan các công trình nghiên cứu liên quan đến đề tài, bao gồm các nghiên cứu về độ đo tương tự, biểu diễn chuỗi thời gian, cấu trúc chỉ mục và thuật toán phát hiện chuỗi con “bất đồng”.
Chương 3 trình bày cơ sở lý thuyết cho các phương pháp biểu diễn và giải thuật được lựa chọn, dựa trên khảo sát các công trình liên quan ở chương 2 Cụ thể, chương này đề cập đến các phương pháp rời rạc hóa như SAX và ESAX, cùng với các giải thuật phát hiện “bất đồng” như BFDD, HDD và HOT SAX Cuối cùng, nội dung cũng bao gồm cấu trúc chỉ mục không gian R*-tree.
- Chương 4, chúng tôi trình bày về các hệ thống ứng dụng Các bước hiện thực hóa các hệ thống ứng dụng cũng sẽ được giới thiệu trong chương 4
- Chương 5, chúng tôi đưa ra các kết quả thực nghiệm và so sánh Chúng tôi chạy thực nghiệm hai hệ thống trên các tập dữ liệu khác nhau
- Chương 6 là một số kết luận và hướng mở rộng của đề tài
- Cuối cùng là phần giới thiệu các tài liệu tham khảo đƣợc sử dụng trong quá trình nghiên cứu đề tài.
Các công trình liên quan
Các công trình về độ đo tương tự
Trong bài toán chuỗi thời gian, việc xác định khoảng cách giữa hai đối tượng O1 và O2 là rất quan trọng để đánh giá sự giống nhau hoặc tương tự của chúng Hai đối tượng được coi là giống nhau khi khoảng cách giữa chúng bằng 0, trong khi chúng được xem là tương tự khi khoảng cách nhỏ hơn một giá trị ε đã được xác định trước Khoảng cách này được biểu diễn bằng các số thực và cần tuân thủ các tính chất sau: i) D(x, y) = 0 nếu và chỉ nếu x = y; ii) D(x, y) = D(y, x); iii) D(x, y) ≥ 0 với mọi x, y; iv) D(x, y) < D(x, z) + D(y, z).
Tính chất i) và ii) trong bài viết rất trực quan, trong khi tính chất iii) cần thiết khi có các thành phần khác nhau với khoảng cách nhỏ hơn 0 nhưng tổng khoảng cách có thể bằng 0, dẫn đến việc đối tượng được xem là giống nhau, điều này trái với tính chất i) Tính chất iv) không bắt buộc phải thỏa mãn trong các phép đo khoảng cách, nhưng được sử dụng để hỗ trợ kỹ thuật lập chỉ mục, giúp giảm thời gian tính toán bằng cách loại bỏ những không gian tìm kiếm không có lời giải thỏa mãn yêu cầu Đối với bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian, dữ liệu được biểu diễn dưới dạng các dãy số thực X = {x1, x2, , xn} và Y = {y1, y2, , yn}, và chúng ta cần tính độ đo tương tự D(X, Y) giữa hai mẫu này Bài viết sẽ xem xét một số phương pháp đánh giá độ đo tương tự phổ biến trong nghiên cứu về chuỗi thời gian.
Cho hai chuỗi thời gian Q = q 1 …q n và C = c 1 …c n , độ đo khoảng cách Euclid giữa hai chuỗi thời gian này đƣợc xác định bởi công thức
Chúng ta có thể hình dung cách tính độ đo khoảng cách Euclid giữa hai chuỗi nhƣ hình vẽ 2.1:
Khoảng cách theo độ đo Euclid giữa hai chuỗi thời gian là một trường hợp đặc biệt của độ đo Minkowski, được tính toán bằng công thức cụ thể.
Độ đo khoảng cách Euclid là một công cụ đơn giản và dễ tính toán, phù hợp cho nhiều bài toán khai phá dữ liệu chuỗi thời gian như phân loại, gom cụm và tìm kiếm tương tự Ngoài ra, độ đo này còn tương thích với nhiều phép biểu diễn xấp xỉ như DFT, giúp nâng cao hiệu quả trong các ứng dụng phân tích dữ liệu.
Độ đo khoảng cách Euclid có nhược điểm là nhạy cảm với nhiễu và không phù hợp cho các chuỗi thời gian có đường cơ bản biến đổi giống nhau nhưng lệch nhau về thời gian hoặc biên độ khác nhau.
2.1.2 Độ đo xoắn thời gian động DTW
Khi thực hiện so trùng, độ đo Euclid được áp dụng rộng rãi trong nhiều lĩnh vực Tuy nhiên, trong những trường hợp mà hai đường biểu diễn có hình dạng tương tự nhưng chỉ khác nhau về thời gian, độ đo Euclid thường cho ra kết quả khác biệt và có thể dẫn đến kết quả cuối cùng không như mong đợi.
Để khắc phục nhược điểm của các phương pháp tính độ đo truyền thống, phương pháp độ đo xoắn thời gian động (DTW) đã được giới thiệu Phương pháp này cho phép một điểm ánh xạ với nhiều điểm khác nhau mà không cần phải thẳng hàng, mang lại sự linh hoạt trong việc so sánh các chuỗi dữ liệu DTW được phát triển lần đầu bởi Berndt và các cộng sự vào năm 1994.
Hình 2.2 A) Hai chuỗi Q và C có sự tương đồng nhưng khác biệt về thời gian B) Ma trận xoắn và đường xoắn tối ưu (đường đậm liên tục) của hai chuỗi Q và C C) Để tính độ đo DTW cho hai chuỗi Q = q1, q2,…, qi,…, qn và C = c1, c2,…, cj,…, cm, chúng ta xây dựng một ma trận nxm Mỗi ô (i, j) trong ma trận tương ứng với một ánh xạ giữa q i và c j, với khoảng cách d(q i, c j) được tính bằng công thức d(q i, c j) = (q i - c j)².
Đường xoắn (warping path) W = w1, w2,…, wk là tập hợp các phần tử liên tục trong ma trận, định nghĩa một ánh xạ giữa Q và C Đường xoắn này chủ yếu phụ thuộc vào một số ràng buộc nhất định.
- Điều kiện biên: w 1 = (1, 1) và w k = (m, n) Ràng buộc này yêu cầu đường xoắn phải bắt đầu và kết thúc ở hai góc đối diện của ma trận
- Tính liên tục: cho w k = (a, b) thì w k-1 = (a’, b’), với a – a’ ≤ 1 và b – b’ ≤ 1
Ràng buộc này yêu cầu đường xoắn phải di chuyển giữa những ô liền kề (kể cả những ô liền kề theo đường chéo)
- Tính đơn điệu tăng: cho w k = (a, b) thì w k-1 = (a’, b’), với a – a’ ≥ 0 và b – b’ ≥
0 Ràng buộc này yêu cầu các điểm trong W phải có tính đơn điệu tăng theo thời gian
- Có nhiều đường xoắn thỏa mãn các điều kiện trên Tuy nhiên chúng ta chỉ quan tâm đến đường tối thiểu hóa chi phi xoắn:
Phương pháp DTW (Dynamic Time Warping) mang lại độ chính xác cao hơn so với đo lường Euclid và có khả năng nhận diện mẫu với hình dạng tương tự, mặc dù chiều dài thời gian có thể khác nhau Tuy nhiên, nhược điểm lớn của phương pháp này là thời gian xử lý lâu.
Khắc phục nhƣợc điểm này, một số nhà nghiên cứu đã đƣa thêm một số ràng buộc như hàm chặn dưới để tăng tốc độ tìm kiếm
Năm 1998, Yi đã phát triển kỹ thuật lập chỉ mục xấp xỉ cho DTW bằng cách sử dụng FastMap, nhằm nhúng các chuỗi vào không gian Euclid để xấp xỉ khoảng cách giữa chúng Kỹ thuật này kết hợp với cấu trúc chỉ mục đa chiều cổ điển như R-tree để lưu trữ các chuỗi, đồng thời giới thiệu hàm chặn cận dưới LB_Yi để loại bỏ những chuỗi không phù hợp Phương pháp này giúp tăng tốc độ lên đến 7,8 lần so với quét tuần tự.
Phương pháp này có một số hạn chế, bao gồm việc gây ra sai lệch do mất thông tin Thêm vào đó, thời gian xây dựng cấu trúc chỉ mục tỷ lệ thuận với kích thước dữ liệu M (0(Mn²)), dẫn đến tốc độ chậm khi xử lý cơ sở dữ liệu lớn hoặc chuỗi con dài.
Vào năm 2001, Kim đã phát triển một giải thuật chính xác cho việc lập chỉ mục dữ liệu chuỗi thời gian dựa trên độ đo DTW, cùng với hàm chặn dưới LB_Kim Đến năm 2004, Keogh và các cộng sự đã giới thiệu hàm chặn dưới LB_Keogh, cải tiến hơn so với hai hàm chặn của Yi và Kim Phương pháp này dựa trên ý tưởng rằng chuỗi thời gian Q = q1, q2, …, qn được bao bởi hai đường biên max và min, với U_i = max(q_i-r : q_i+r) và L_i = min(q_i-r : q_i+r) Hàm chặn dưới LB_Keogh được xác định theo công thức này.
Ta có thể hình dung ý tưởng phương pháp như hình vẽ 2.3
Hình 2.3 Hàm chặn dưới LB_Keogh
Các công trình về biểu diễn chuỗi thời gian
Dữ liệu chuỗi thời gian thường rất lớn, khiến việc tìm kiếm trực tiếp trở nên tốn kém và phức tạp Các nghiên cứu trong lĩnh vực này thường tập trung vào việc chuyển đổi chuỗi thời gian thành dạng khác để giảm kích thước dữ liệu và tối ưu hóa tính toán mà vẫn giữ được các đặc trưng cơ bản Sau khi thu giảm dữ liệu, các cấu trúc dữ liệu có sẵn hoặc mới được xây dựng để hỗ trợ việc tìm kiếm và khai thác thông tin hiệu quả hơn.
2.2.1 Các phương pháp thu giảm số chiều
Phương pháp thu giảm số chiều (dimensionality reduction) giúp biểu diễn dữ liệu chuỗi thời gian thành những đường cơ bản đã được định nghĩa trước Thay vì lưu trữ chuỗi dữ liệu n chiều X = {x1, x2, , xn}, ta chỉ cần lưu trữ chuỗi dữ liệu k chiều Y = {y1, y2, , yn} với k là hệ số của các đường cơ bản Từ những đường cơ bản này, dữ liệu ban đầu có thể được phục hồi, và độ chính xác của việc phục hồi phụ thuộc vào giá trị của k: k càng lớn, độ chính xác càng cao Phương pháp này giúp giảm thiểu khối lượng tính toán, chỉ cần xử lý trên dữ liệu thu giảm k chiều, rất phù hợp cho các cấu trúc chỉ mục trong cơ sở dữ liệu không gian.
Phương pháp biến đổi Fourier DFT
Phương pháp biến đổi rời rạc Fourier (Discrete Fourier Transform - DFT), được đề xuất bởi Agrawal R và cộng sự vào năm 1993, được sử dụng để rút trích đặc trưng từ chuỗi thời gian Bằng cách áp dụng DFT, chuỗi thời gian sẽ được chuyển đổi sang miền tần số, và chỉ những tần số đầu tiên sẽ được đánh chỉ mục, trong khi các tần số còn lại sẽ bị loại bỏ Điều này dựa trên quan sát rằng năng lượng của hầu hết các chuỗi thời gian thực tế thường tập trung chủ yếu ở một vài tần số đầu tiên.
Kết quả phép biến đổi Fourier rời rạc của chuỗi X t (t = 0, 1,…, n-1) đƣợc định nghĩa là một chuỗi gồm n số phức X f cho bởi công thức:
với f 0,1, , n 1 và phần ảo của số phức j 1
Ngƣợc lại, chuỗi X t có thể đƣợc khôi phục bằng phép biến đổi ngƣợc:
Phương pháp DFT sử dụng các số phức (trừ X 0, vì X t là giá trị thực) và áp dụng hàm đo độ tương tự Euclid Đề xuất phương pháp đánh chỉ mục bao gồm F-Index và ST-Index Ưu điểm của DFT là khả năng thích ứng với nhiều loại đường biểu diễn dữ liệu khác nhau, với độ phức tạp thuật toán O(nlgn) Tuy nhiên, nhược điểm lớn nhất của phương pháp này là khó khăn trong việc xử lý các chuỗi thời gian có chiều dài khác nhau.
Phương pháp biến đổi Wavelet DWT
Phương pháp biến đổi Wavelet (Discrete Wavelet Transform - DWT) được Chan và Fu giới thiệu vào năm 1999, cho phép biểu diễn dữ liệu thông qua các đường cơ bản như Haar, Daubechies, Coiflet và Symmlet Trong số đó, đường Haar được ưa chuộng trong việc khai thác dữ liệu chuỗi thời gian và lập chỉ mục.
Phương pháp biến đổi Wavelet rời rạc là một kỹ thuật mã hóa hiệu quả, nhanh chóng với độ phức tạp tuyến tính Ưu điểm nổi bật của thuật toán Wavelet là khả năng hỗ trợ nhiều mức phân giải Tuy nhiên, nhược điểm của nó là yêu cầu chiều dài chuỗi dữ liệu ban đầu và chiều dài chuỗi con truy vấn phải là các số lũy thừa của 2 để đảm bảo hiệu quả tối ưu trong quá trình thực hiện.
Phương pháp xấp xỉ gộp từng đoạn PAA
Vào năm 2000, Yi và Faloutsos cùng với Keogh và các cộng sự đã độc lập đề xuất phương pháp xấp xỉ gộp từng đoạn PAA (Piecewise Aggregate Approximation) Phương pháp này chia chuỗi thời gian thành N đoạn bằng nhau và tính giá trị trung bình của từng đoạn để đại diện cho một thành phần trong véctơ N chiều Kết quả của quá trình này là một đường thẳng có dạng bậc thang như được minh họa trong hình 2.4.
Hình 2.4 Chuối thời gian X đƣợc biểu diến bằng PAA với n` thành N=6 (Nguồn [9])
Chuỗi thời gian X = x 1 ,…,x n có độ dài n đƣợc biểu diễn thành N đoạn bởi véctơ
X x x Trong đó phần tử thứ i của X đƣợc tính theo công thức:
Để tránh việc loại trừ nhầm những điểm thỏa mãn, phương pháp này đề xuất một hàm đo khoảng cách trong không gian chỉ mục, đảm bảo tuân thủ điều kiện chặn dưới Hàm đo khoảng cách được định nghĩa bằng một công thức cụ thể.
X x i i | 1, N và Y y i i | 1, N là hai chuỗi xấp xỉ của hai chuỗi X và Y Phương pháp này có ưu điểm là tính toán nhanh, dễ thực hiện và có thể xây dựng cấu trúc chỉ mục trong thời gian tuyến tính Nó cũng hỗ trợ nhiều độ đo khoảng cách Tuy nhiên, đối với dữ liệu yêu cầu độ chính xác cao như dữ liệu tài chính, phương pháp PAA có thể làm mất những điểm quan trọng, dẫn đến khó khăn trong việc khôi phục dữ liệu gốc.
Phương pháp xấp xỉ gộp từng đoạn mở rộng EPAA
Phương pháp xấp xỉ gộp từng đoạn mở rộng EPAA (Extended Piecewise Aggregate
Phương pháp xấp xỉ EPAA, được đề xuất bởi Lkhagva và các cộng sự vào năm 2006, tương tự như phương pháp PAA nhưng có sự cải tiến đáng kể Ngoài việc lấy xấp xỉ từng đoạn bằng giá trị trung bình, EPAA còn giữ lại giá trị lớn nhất và giá trị nhỏ nhất của mỗi đoạn Do đó, mỗi đoạn trong phương pháp EPAA được đại diện bởi ba giá trị: giá trị nhỏ nhất, giá trị trung bình và giá trị lớn nhất.
Phương pháp EPAA nổi bật với ưu điểm tính toán nhanh chóng, dễ hiểu và dễ thực hiện, đồng thời vẫn giữ được tính quan trọng của dữ liệu Tuy nhiên, giống như một số phương pháp trước, EPAA không đảm bảo khôi phục chính xác dữ liệu gốc và có thể làm tăng số chiều của dữ liệu thu giảm.
Phương pháp xấp xỉ từng đoạn thích nghi APCA
Phương pháp xấp xỉ từng đoạn thích nghi APCA (Adaptive Piecewise Constant
Phương pháp APCA, được đề xuất bởi Keogh và các cộng sự vào năm 2001, tương tự như phương pháp PAA trong việc xấp xỉ dữ liệu thành các đoạn thẳng nằm ngang Tuy nhiên, khác với PAA chia thành các đoạn có độ dài bằng nhau, APCA phân chia thành các đoạn có độ dài khác nhau dựa trên sự biến động của dữ liệu Những vùng có biến động lớn trên chuỗi thời gian sẽ được chia thành các đoạn ngắn, trong khi những vùng ít biến động sẽ được phân thành các đoạn dài hơn.
Cụ thể, cho chuỗi thời gian Q = {q 1 , q 2 , …, q n }, chuỗi biến đổi Q’ có dạng:
Q’ = {, , …, } với qr 0 = 0
Trong đó qv i là giá trị trung bình cộng của những điểm dữ liệu ở đoạn thứ i, tức là
Và qr i là điểm bên phải cùng của đoạn thứ i (cho biết chiều dài của đoạn thứ i)
Phương pháp APCA hỗ trợ các hàm đo khoảng cách Minkowski và Euclid, đồng thời cung cấp hai hàm đo khoảng cách tùy chỉnh: một hàm xấp xỉ khoảng cách Euclid trên dữ liệu gốc nhưng không thỏa mãn chặn dưới, giúp tìm kiếm xấp xỉ hiệu quả; và một hàm khác thỏa mãn chặn dưới chặt hơn, hỗ trợ tìm kiếm chính xác Ưu điểm nổi bật của APCA là khả năng xấp xỉ tốt hơn PAA và tỷ lệ lỗi khi tái tạo dữ liệu ban đầu thấp hơn Tuy nhiên, nhược điểm của phương pháp này là độ phức tạp biến đổi O(nlogn).
Phương pháp xấp xỉ tuyến tính từng đoạn PLA
Phương pháp xấp xỉ tuyến tính từng đoạn (PLA) do Keogh và các cộng sự đề xuất là một kỹ thuật hiệu quả trong việc xử lý dữ liệu Phương pháp này chia dữ liệu ban đầu thành các chuỗi con có chiều dài đồng nhất, và mỗi chuỗi con sẽ được xấp xỉ bằng một đoạn thẳng tuyến tính Điều này giúp đơn giản hóa quá trình phân tích và cải thiện khả năng nhận diện mẫu trong dữ liệu.
Để xấp xỉ một chuỗi con S = {s1, …, sn} bằng một đoạn thẳng tuyến tính, ta sử dụng công thức s't = a.t + b (t ∈ [1, n]) Hệ số a và b được tính toán nhằm tối thiểu hóa lỗi tái tạo RecErr(S), mà chính là khoảng cách giữa chuỗi con S và đoạn thẳng xấp xỉ.
Các công trình về cấu trúc chỉ mục
Dữ liệu chuỗi thời gian rất lớn, gây khó khăn trong việc tìm kiếm và so sánh Để giảm chi phí tính toán, ngoài việc áp dụng các kỹ thuật thu giảm số chiều và biểu diễn chuỗi thời gian, chúng ta thường sử dụng các cấu trúc chỉ mục Một số cấu trúc chỉ mục phổ biến cho dữ liệu chuỗi thời gian bao gồm:
K-D-Tree do J.Bernley đề nghị [4]: loại cấu trúc lập chỉ mục này không chứa dữ liệu trong cấu trúc cây, phù hợp cho các dữ liệu không gian lớn K-D-Tree là một dạng cây nhị phân, đƣợc xây dựng bằng cách chia không gian d chiều thành các không gian con, mỗi không gian con này đƣợc chia nhỏ cho đến khi nào là một điểm duy nhất
Quad Tree, theo H Samet, là một cấu trúc cây phân chia không gian thành các không gian con tương tự như K-D-Tree Tuy nhiên, khác với K-D-Tree, Quad Tree không phải là cây nhị phân, mà mỗi nút trong Quad Tree có thể có nhiều con.
2 d , trong đó d là số chiều của không gian điểm
R-Tree do A.Guttman đề nghị [16]: là cấu trúc cây dựa trên B-tree Tương tự như B-tree, R-tree là một cây cân bằng Mỗi nút trong R-tree có chứa từ m đến M dữ liệu (m và M là 2 thông số trong quá trình xây dựng R-tree) Mỗi dữ liệu chứa một hình chữ nhật bao nhỏ nhất (minimum bounding rectanges – MBR) có thể giao nhau
Mỗi nút lá của cây R-tree chứa con trỏ tới dữ liệu thật sự
R*-tree, do N Beckmann và các cộng sự đề xuất, là một cấu trúc dữ liệu tương tự như R-tree, nhưng đã cải tiến một số nhược điểm của R-tree, đặc biệt là trong quá trình thêm phần tử.
Chúng tôi tập trung vào việc áp dụng cấu trúc chỉ mục R*-tree trong bài toán so trùng chuỗi Ở chương tiếp theo, chúng tôi sẽ cung cấp một cái nhìn chi tiết về cấu trúc chỉ mục này.
Các thuật toán phát hiện chuỗi con “bất đồng”
Khoảng cách (Dist) là hàm xác định khoảng cách giữa hai đối số C và M, với tính chất đối xứng, nghĩa là Dist(C, M) = Dist(M, C) Khớp không tầm thường (non-self match) được áp dụng cho một chuỗi thời gian.
T, chứa chuỗi con C chiều dài n bắt đầu từ vị trí p và chuỗi con trùng khớp M bắt đầu từ vị trí q, ta nói M và C là khớp không tầm thường ở khoảng cách Dist(C, M) nếu |p-q|≥n Định nghĩa 1.3: Chuỗi thời gian bất đồng (time series discord): Cho một chuỗi thời gian T, chuỗi con D chiều dài n bắt đầu ở vị trí l đƣợc gọi là chuỗi con “bất đồng” của T nếu D có khoảng cách lớn nhất đến chuỗi con khớp không tầm thường gần nhất của nó Tức là, mọi chuỗi con C của T, chuỗi con khớp không tầm thường M D của D, và chuỗi con khớp không tầm thường M C của C, min(Dist(D, M D )) > min(Dist(C, M C ))
2.4.1 Giải thuật hệ thống miễn dịch nhân tạo IMM
Giải thuật do Dasgupta và các cộng sự đề xuất năm 1999 dựa trên cơ chế loại thải của hệ thống miễn dịch để phân biệt giữa tế bào cơ thể và tế bào ngoại xâm nhập Trong đó, các mẫu dữ liệu bình thường được coi là tế bào cơ thể, trong khi những mẫu thay đổi vượt quá giới hạn cho phép được xem là tế bào ngoại Phương pháp này mang tính xác suất, theo dõi sự thay đổi của hành vi bình thường mà không cần biết trước những thay đổi sẽ xảy ra, do đó cải thiện hiệu quả so với các phương pháp khác yêu cầu phải dự đoán trước các điều kiện thay đổi bất thường.
2.4.2 Giải thuật dựa trên cây TSA
Thuật toán do Shahabi và các cộng sự đề xuất vào năm 2000 sử dụng cấu trúc cây dựa trên phép biến đổi wavelet (DWT) để nâng cao hiệu quả truy vấn xu hướng đa mức độ và mẫu bất đồng Để thực hiện các truy vấn này, thường cần truy xuất và xử lý những tập con lớn của dữ liệu gốc Việc sử dụng cây TSA giúp tăng tốc quá trình này, với mỗi nút chứa các xu hướng và bất đồng đã được tính toán trước ở nhiều mức độ khác nhau Phép biến đổi wavelet được áp dụng để tạo ra các nút của cây TSA một cách đệ quy, với kích thước của mỗi nút nhỏ hơn đáng kể so với chuỗi thời gian gốc, từ đó cải thiện tốc độ thao tác xuất nhập.
Giải thuật Tarzan do Keogh và các cộng sự đề xuất năm 2002 [21] Dựa trên định nghĩa về bất đồng (“Một chuỗi thời gian P, đƣợc rút trích từ database X là
Trong cơ sở dữ liệu R, một giá trị được coi là “ngạc nhiên” khi tần suất xuất hiện của nó trong X khác biệt rõ rệt so với dự đoán, giả định rằng X và R được sinh ra từ cùng một quy trình Để phát hiện các chuỗi con, phương pháp kết hợp mô hình Markov ẩn bậc cao và cây hậu tố được áp dụng.
Mô hình Markov ẩn được sử dụng để dự đoán xác suất xuất hiện của chuỗi con trong khi cây hậu tố giúp đếm số lần xuất hiện của từng chuỗi con trong chuỗi lớn Thuật toán bắt đầu khi người dùng cung cấp chuỗi dữ liệu huấn luyện R, được cho là không chứa chuỗi con bất đồng, sau đó rời rạc hóa R và xây dựng cây hậu tố cho chuỗi này Tiếp theo, chuỗi cần kiểm tra X cũng được rời rạc hóa và xây dựng cây hậu tố Dựa vào chiều dài l2 của chuỗi con bất đồng mà người dùng cung cấp, thuật toán kiểm tra tất cả các chuỗi con có chiều dài l2 trong X và tính xác suất xuất hiện của chúng trong R bằng mô hình Markov Nếu độ khác biệt giữa xác suất xuất hiện của một chuỗi con trong X và trong R vượt quá ngưỡng c do người dùng quy định, chuỗi con đó sẽ được kết luận là “bất đồng”.
Giải thuật BFDD (Brute Force Discord Discovery) là một phương pháp phát hiện chuỗi con “bất đồng” bằng cách thực hiện việc vét cạn để tính toán khoảng cách lân cận gần nhất của tất cả các chuỗi con từ dữ liệu gốc Qua việc so sánh các khoảng cách này, BFDD xác định chuỗi con có khoảng cách lân cận gần nhất lớn nhất, từ đó phát hiện ra chuỗi con “bất đồng”.
Giải thuật HDD (Heuristic Discord Discovery) là một cải tiến của giải thuật BFDD
Giải thuật HDD đƣa thêm vào một số heuristic đế tăng tốc thời gian phát hiện “bất đồng”
Giải thuật HOT SAX, được Keogh và các cộng sự phát triển vào năm 2005, áp dụng phương pháp SAX vào giải thuật HDD để phát hiện sự "bất đồng" trong dữ liệu chuỗi thời gian Bằng cách sử dụng biểu diễn chuỗi ký tự, giải thuật này có khả năng nhận diện các chuỗi con tương tự trong không gian nguyên thủy, từ đó giúp tìm kiếm nhanh chóng và hiệu quả hơn Giải thuật tiến hành tìm kiếm tất cả các chuỗi con có thể có và lọc ra những chuỗi xuất hiện ít nhất để so sánh, vì các chuỗi này có khả năng tương đồng cao hơn.
“bất đồng” với các chuỗi còn lại nhất), còn các chuỗi còn lại xét ngẫu nhiên
Chương 2 đã tổng hợp các công trình nghiên cứu liên quan đến đề tài, cung cấp cái nhìn tổng quan về dữ liệu chuỗi thời gian Các nghiên cứu tập trung vào độ đo tương tự, đặc biệt là độ đo Euclid do tính đơn giản và trực quan; đồng thời đề cập đến biểu diễn dữ liệu chuỗi thời gian, cấu trúc chỉ mục và các thuật toán phát hiện.
Cơ sở lý thuyết
Phương pháp rời rạc hóa SAX
Phương pháp rời rạc ký hiệu SAX, được đề xuất bởi Lin và Keogh cùng các cộng sự vào năm 2003, cho phép giảm một chuỗi thời gian độ dài n thành một chuỗi ký tự ngắn hơn với độ dài w (w 2)
Bảng 3.1 Tổng hợp ký hiệu sử dụng trong phần 3.1
Theo phương pháp SAX, chuỗi thời gian C được giảm số chiều bằng phương pháp PAA, sau đó kết quả này được chuyển đổi thành chuỗi ký tự rời rạc.
3.1.1 Thu giảm số chiều bằng phương pháp PAA (xem phần 2.2.1)
Nhóm tác giả đã trích xuất các chuỗi con dài 128 từ 8 loại dữ liệu chuỗi thời gian khác nhau và biểu diễn chúng bằng đồ thị Kết quả cho thấy phần lớn dữ liệu tuân theo phân bố xác suất chuẩn (phân bố Gauss) Đối với chuỗi thời gian được chuẩn hóa có phân bố Gauss cao, các điểm ngắt (Breakpoints) được xác định dựa trên đường cong Gauss, tạo ra các vùng quy định ký tự giống nhau Theo định nghĩa 3.1.1 [8], "Điểm ngắt là danh sách các số được sắp xếp B = β 1, β 2, , β a-1 tuân theo đường cong Gauss N(0,1), với β i tới β i+1 = 1/a (β 0 và β a được định nghĩa là -∞ và ∞)".
Không nên tập trung mã hóa chuỗi ký tự vào một vài ký tự, vì điều này sẽ dẫn đến việc tất cả các chuỗi khác nhau được mã hóa giống nhau, làm giảm hiệu quả của phương pháp SAX Để cải thiện điều này, giá trị β i cần được chọn sao cho xác suất xuất hiện của các ký tự là bằng nhau, tức là xác suất xuất hiện của ký tự thứ i trong tập a ký tự phải là 1/a.
Các điểm ngắt này đƣợc xác định và tìm trong một bảng thống kê Ví dụ, bảng 3.2 đƣa ra các điểm ngắt cho giá trị a thay đổi từ 3 đến 10
Bảng 3.2 cung cấp thông tin về các điểm ngắt để chia phân bố Gauss thành các miền ký tự Theo Định nghĩa 3.1.2, một chuỗi thời gian C có độ dài n được biểu diễn dưới dạng một từ C = c1, , cw Trong đó, alpha i là ký hiệu cho phần tử thứ i của bảng chữ cái, ví dụ, alpha 1 = a và alpha 2 = b Ánh xạ từ C tới C được ký hiệu như sau.
C i = alpha j khi và chỉ khi j 1 c i j (1)
Từ bảng trên, các giá trị PAA thấp hơn mức tối thiểu sẽ được mã hóa là A, trong khi những giá trị lớn hơn hoặc bằng mức tối thiểu nhưng nhỏ hơn mức tối thiểu thứ hai sẽ được mã hóa là B Ý tưởng này được minh họa trong hình 3.1.
Hình 3.1 Chuỗi thời gian đƣợc rời rạc hóa theo SAX Với n`, k=6 và a=3, chuỗi thời gian đƣợc mã hóa thành ABCBBA (Nguồn [9])
Từ chuỗi dữ liệu ban đầu, có hai phương pháp mã hóa là PAA và SAX Mỗi phương pháp này đi kèm với các hàm tính khoảng cách riêng biệt để xác định mức độ tương tự giữa các chuỗi.
Giả sử S = s 1 s 2 …s n và Q= q 1 q 2 …q n là 2 chuỗi dữ liệu chuỗi thời gian có cùng chiều dài n
Ss s và Qq 1 , ,q w là dữ liệu có chiều dài w và được mã hóa bằng phương pháp PAA từ S và Q
Ss s và ̂ ̂ ̂ là dữ liệu có chiều dài w và đƣợc mã hóa bằng phương pháp SAX từ S và Q
Hàm tính khoảng cách dữ liệu ban đầu sử dụng khoảng cách Euclid để xác định khoảng cách giữa các chuỗi thời gian Khoảng cách D(S, Q) được tính theo công thức cụ thể, giúp đánh giá sự tương đồng giữa các dữ liệu.
Hàm tính khoảng cách giữa hai dữ liệu mã hóa PAA S’ và Q’ được xác định từ dữ liệu ban đầu S và Q với chiều dài n, trong đó S’ và Q’ có chiều dài w Khoảng cách này đóng vai trò quan trọng trong việc phân tích và so sánh dữ liệu mã hóa.
2 chuỗi mã hóa là DR(S’, Q’)
Trong bài viết [18] đã chứng mình đƣợc hàm tính khoảng cách dữ liệu mã hóa PAA là chặn dưới của khoảng cách Euclid, tức là DR S Q , D S Q ,
Dữ liệu được mã hóa bằng phương pháp PAA có thể được tính toán do là số, trong khi dữ liệu S” và Q” được mã hóa thành các ký tự Do đó, cần định nghĩa một hàm để tính khoảng cách giữa các ký tự Hàm MINDIST sẽ trả về khoảng cách nhỏ nhất giữa hai từ.
Công thức (4) được phát triển từ công thức (3) bằng cách thay thế khoảng cách giữa hai chuỗi s i và q i bằng hàm dist() Hàm dist() được xác định thông qua việc tra cứu bảng 3.3.
Trong bảng 3.3, giá trị của ô (r, c) đƣợc tính theo công thức:
Bảng 3.3 Bảng tra cứu tính khoảng giữa hai chữ cái ứng với a = 4
Phương pháp rời rạc ESAX
Phương pháp rời rạc ESAX (Extended Symbolic Aggregate approXimation) được Lkhagva và các cộng sự giới thiệu vào năm 2006, mang đến một cách tiếp cận mới trong việc biểu diễn chuỗi thời gian ESAX tương tự như phương pháp SAX, nhưng cải thiện khả năng thu gọn thông tin Phương pháp SAX, dựa trên PAA, có thể dẫn đến việc mất mát một số mẫu thức quan trọng do việc xấp xỉ giá trị trung bình của từng đoạn con Hình 3.2 minh họa rõ nét các tình huống mất thông tin mà phương pháp SAX có thể gặp phải.
Hình 3.2 Dữ liệu tài chính biểu diễn bằng SAX
Một vài điểm quan trọng bị mất Kết quả biểu diễn bằng SAX là CFCBFD (Nguồn [9])
Hình 3.3 Dữ liệu tài chính biểu diễn bằng ESAX Kết quả biểu diễn bằng ESAX là ACFFDFFCAABFFFFDCA (Nguồn [9])
Phương pháp ESAX là sự mở rộng của phương pháp SAX, trong đó bổ sung hai điểm đặc biệt: điểm nhỏ nhất và điểm lớn nhất của từng đoạn để biểu diễn chuỗi thời gian Theo cách tiếp cận này, mỗi đoạn con sẽ được biểu diễn bằng ba giá trị, như minh họa trong Hình 3.3.
Giả sử s1, s2 và s3 là các ký tự đầu tiên trong đoạn con thứ k, trong khi pm ax, pm id và pm in đại diện cho vị trí lớn nhất, trung bình và nhỏ nhất theo trục thời gian trong đoạn con này Các ký tự tương ứng s max, s mid và s min cũng được xác định là lớn nhất, trung bình và nhỏ nhất trong đoạn con thứ k Thứ tự của ba ký tự này có thể được tính toán bằng công thức cụ thể.
1 2 3 ax min mi ax min mi ax min ax min min m ax
, , otherwise m mid m mid mid mid m d m d m d m d mid m mid m mid s s s p p p s s s p p p s s s p p p s s s s s s p p p s s s p p p s s s
Mở rộng phương pháp biểu diễn SAX cho chuỗi thời gian yêu cầu định nghĩa hàm tính khoảng cách theo cách này Thay vì sử dụng một ký tự cho mỗi đoạn con, chúng ta áp dụng ba ký tự để biểu diễn, do đó hàm tính khoảng cách của ESAX được xây dựng tương tự như hàm tính khoảng cách của SAX.
3.1), cụ thể tính theo công thức sau:
( ) √ √∑( ( )) trong đó s s 1 , , , 2 s w và r r 1 , , , 2 r w là chuỗi ký tự Q e và C e , kết quả biểu diến bằng phương pháp ESAX của chuỗi thời gian Q và C.
Giải thuật BFDD
Giải thuật BFDD (Brute Force Discord Discovery) là một phương pháp đơn giản và trực quan để phát hiện chuỗi con "bất đồng" trong chuỗi thời gian Giải thuật này thực hiện việc tính toán khoảng cách của lân cận gần nhất không tầm thường cho mỗi chuỗi con trong chuỗi thời gian gốc Cuối cùng, nó xác định khoảng cách lân cận gần nhất lớn nhất, từ đó tìm ra chuỗi con tương ứng, được xem là chuỗi con "bất đồng" trong chuỗi thời gian ban đầu.
Giải thuật BFDD đƣợc trình bày trong bảng 3.4:
1 Function [dist, loc] = Brute_Rorce(T, n)
3 best_so_far_loc = NaN
5 For p=1 to |T|- n + 1 //Begin Outer Loop
7 For q = 1 to |T| - n +1 //Begin Inner Loop
9 IF Dist(t p ,…,t p+n-1 , t q ,…,t q+n-1 ) < nearest_neighbor_dist
12 End //End no-self match test
14 IF nearest_neighbor_dist > best_so_far_dist
15 best_so_far_dist = nearest_neighbor_dist
19 Return[best_so_far_dist, best_so_far_loc]
Bảng 3.4 Mã giả thuật toán BFDD
Tìm khoảng cách tới lân cận gần nhất
Kiểm tra xem chuỗi con đƣợc chọn có là “bất thường” hay không ?
Trong đó: n là chiều dài chuỗi con của chuỗi thời gian gốc |T| là chiều dài của chuỗi thời gian gốc Nhƣ vậy độ phức tạp của thuật toán là O(n 2 ).
Giải thuật HDD
Với độ phức tạp O(n²), thuật toán BFDD gặp khó khăn khi xử lý dữ liệu lớn, do đó, việc cải thiện thuật toán này là rất cần thiết.
Quan sát bảng 3.4, ta nhận thấy:
Trong vòng lặp trong, không cần phải xác định lân cận gần nhất thực sự của chuỗi con đang xét Ngay khi phát hiện bất kỳ chuỗi con nào có khoảng cách nhỏ hơn best_so_far_dist, ta có thể kết thúc vòng lặp, vì chuỗi đang xét không thể là chuỗi bất đồng.
Việc tối ưu thời gian thực hiện thuật toán phụ thuộc vào thứ tự của vòng lặp ngoài khi chọn các chuỗi con tốt để phát hiện bất đồng Đồng thời, thứ tự của vòng lặp trong khi thăm chuỗi con khác cũng ảnh hưởng đến khả năng thoát sớm khỏi vòng lặp.
Based on the two observations, Keogh and colleagues introduced two additional heuristics to the BFDD algorithm to enhance its performance This improved algorithm is referred to as the HDD (Heuristic Discord Discovery) algorithm.
Thuật toán được cải tiến với hai heuristic bổ sung: thứ nhất là xác định thứ tự chuỗi con của vòng lặp ngoài, và thứ hai là xác định thứ tự chuỗi con của vòng lặp trong Dựa vào bảng 3.5, có thể rút ra những nhận xét quan trọng nhằm tăng tốc độ thực hiện thuật toán.
Trong vòng lặp ngoài, không cần phải sắp xếp thứ tự hoàn hảo để tăng tốc thuật toán Điều quan trọng là trong số các chuỗi con được kiểm tra đầu tiên, ít nhất một chuỗi con phải có khoảng cách tới lân cận gần nhất đủ lớn, giúp giá trị best_so_far_dist đạt mức cao sớm Điều này đảm bảo điều kiện ở dòng thứ 9 của bảng 3.5 luôn đúng, từ đó giúp vòng lặp trong nhanh chóng kết thúc.
Trong vòng lặp trong, nếu có ít nhất một chuỗi con trong số các chuỗi con đầu tiên được kiểm tra có khoảng cách nhỏ hơn giá trị hiện tại của biến best_so_far_dist so với chuỗi đang xét, thì vòng lặp sẽ sớm kết thúc.
Function [dist, loc] = Heuristic_Search(T, n, Outer, Inner) best_so_far_dist = 0 best_so_far_loc = NaN
For Each p inT ordered by heuristic Outer //Begin Outer Loop nearest_neighbor_dist = infinity
For Each q in T ordered by heuristic Inner //Begin Inner Loop
IF Dist(t p ,…,t p+n-1 , t q ,…,t q+n-1 ) < best_so_far_dist Break //Break out of Inner Loop End
IF Dist(t p ,…,t p+n-1 , t q ,…,t q+n-1 ) < nearest_neighbour_dist nearest_neighbour_dist = Dist(t p ,…,t p+n-1 , t q ,…,t q+n-1 ) End
End //End no-self match test End //End Inner Loop
IF nearest_neighbor_dist > best_so_far_dist best_so_far_dist = nearest_neighbor_dist best_so_far_loc = p
End End //End Outer Loop Return[best_so_far_dist, best_so_far_loc]
Bảng 3.5 Mã giả thuật toán HDD
Giải thuật HOT SAX
Để tăng tốc thuật toán và hỗ trợ tính toán trên chuỗi thời gian lớn, cần xây dựng xấp xỉ biểu diễn chuỗi thời gian và áp dụng các heuristic ngoài và trong cho thuật toán HDD Giải thuật HOT SAX, được đề xuất bởi Keogh và các cộng sự vào năm 2005, ứng dụng phương pháp rời rạc hóa ký hiệu SAX vào thuật toán HDD Một cấu trúc dữ liệu phù hợp khi sử dụng phương pháp SAX được trình bày trong hình 3.6.
Hình 3.4 minh họa hai cấu trúc dữ liệu hỗ trợ cho heuristics bên ngoài và bên trong Cấu trúc bên trái là một dãy từ SAX, trong đó cột cuối cùng thể hiện số lần xuất hiện của mỗi từ Bên phải là cây gia tố (Augmented Trie), với các nút lá chứa vị trí tương ứng của từ SAX trong dãy.
3.5.1 Mô tả cấu trúc dữ liệu
Ta đặt : - n là độ dài của chuỗi bất thường
- m là độ dài của chuỗi thời gian gốc
- a là kích thước bảng ký hiệu alpha-bê
Kích thước từ SAX được xác định để biểu diễn chuỗi thời gian bằng phương pháp SAX Quá trình này bắt đầu bằng cách sử dụng một cửa sổ có độ dài n trượt dọc theo chuỗi thời gian Tại mỗi vị trí của cửa sổ, một chuỗi con được rút trích và chuyển đổi sang từ SAX Các từ SAX này sau đó được lưu trữ trong một mảng theo cấu trúc đã định Từ chỉ số của mảng, chúng ta có thể xác định vị trí của chuỗi con trong chuỗi gốc, với chỉ số được đánh số từ 1 đến (m-n+1) Để hỗ trợ việc tìm kiếm nhanh các từ SAX giống nhau, danh sách các từ SAX được lưu trong một cấu trúc cây gọi là cây gia tố.
Ví dụ, để tìm vị trí của từ caa trong danh sách mảng, theo cây gia tố, ta tìm tới vị trí
Giá trị a và w chỉ ảnh hưởng đến hiệu quả của thuật toán mà không tác động đến kết quả cuối cùng, tức là việc phát hiện chuỗi bất đồng Kết quả cuối cùng hoàn toàn phụ thuộc vào độ dài n của chuỗi bất đồng.
Dựa vào đặc điểm trực quan, các chuỗi bất đồng thường có xu hướng xuất hiện trong chuỗi gốc với số lượng tối thiểu tương ứng với các từ SAX trong mảng.
Ý tưởng heuristic được đề xuất là tìm các từ SAX có số lần xuất hiện ít nhất (giá trị bằng 1) từ cột bên phải ngoài cùng của mảng lưu từ SAX Sau đó, ưu tiên vòng lặp ngoài để xét các từ SAX này trước, trong khi các từ SAX khác sẽ được xem xét một cách ngẫu nhiên.
Với thứ tự duyệt vòng ngoài như trên, biến best_so_far_dist có khả năng đạt giá trị lớn sớm, giúp điều kiện dòng 9 trong bảng 3.5 luôn đúng Điều này cho phép vòng lặp kết thúc sớm, từ đó tăng tốc độ của thuật toán.
Heuristic được phát triển dựa trên nguyên tắc rằng các chuỗi có mã SAX giống nhau với chuỗi đang xem xét thường rất tương đồng Dựa vào nhận xét 4 trong phần 3.4, nếu tìm thấy một chuỗi con có khoảng cách lớn hơn giá trị hiện tại của best_so_far_dist, vòng lặp trong sẽ dừng lại.
Trong quá trình xử lý từng từ SAX thứ i trong vòng lặp ngoài, chúng ta sẽ xác định các vị trí khác trong danh sách có cùng biểu diễn SAX dựa trên cây gia tố Sau đó, ưu tiên xem xét các từ SAX này trước, trong khi các từ SAX còn lại sẽ được xử lý ngẫu nhiên.
Khi xem xét chuỗi thứ 731, chúng ta truy cập vị trí 731 trong mảng danh sách từ SAX và tìm thấy từ tương ứng là "caa" Sử dụng giá trị "caa", chúng ta tiếp tục tìm kiếm trong cây gia tố để xác định các từ SAX có biểu diễn giống "caa", cụ thể là ở các vị trí 1, 3 và 731 Trong quá trình lặp, hệ thống sẽ ưu tiên xử lý ba vị trí này trước, trong khi các vị trí khác sẽ được xem xét ngẫu nhiên.
Có một vài tối ƣu nhỏ mà ta có thể áp dụng trong thuật toán tìm kiếm heuristic này
Khi xem xét chuỗi C i trong vòng lặp ngoài, nếu phát hiện chuỗi C j tương tự gần gũi với C i, ta có thể kết thúc vòng lặp sớm Để tiết kiệm thời gian, C j có thể được loại bỏ khỏi danh sách trong vòng lặp ngoài.
Để tối ưu hóa hiệu quả của thuật toán, việc lựa chọn giá trị hai tham số a và w là rất quan trọng Nếu a và w được chọn quá lớn, hầu hết các chuỗi con sẽ được ánh xạ thành từ SAX duy nhất Ngược lại, nếu a và w quá nhỏ, chỉ một số chuỗi trong tổng thể sẽ có giá trị khi chuyển sang SAX.
Nghiên cứu thực nghiệm cho thấy giá trị hợp lý của a thường là 3 hoặc 4, với lựa chọn phổ biến là a = 3.
Cấu trúc chỉ mục R*-tree
Cấu trúc cây R*-tree là một loại dữ liệu quan trọng trong các phương pháp truy suất không gian (Spatial Access Methods - SAM), giúp tối ưu hóa việc đánh chỉ mục cho dữ liệu điểm và dữ liệu không gian Với khả năng tổ chức và truy xuất hiệu quả, R*-tree trở thành lựa chọn lý tưởng cho các ứng dụng cần xử lý thông tin không gian.
Một nút nội, không phải nút lá, bao gồm các phần tử (entry) với cấu trúc gồm một hình chữ nhật (rectangle) và một con trỏ (cp) đến nút con Hình chữ nhật này là hình chữ nhật nhỏ nhất có thể chứa tất cả các hình chữ nhật của các phần tử trong nút con.
Nút lá trong R*-tree chứa các phần tử bao gồm O id và hình chữ nhật (rectangle), trong đó O id đại diện cho các mục dữ liệu cần lưu trữ trong cơ sở dữ liệu hoặc tập tin, còn rectangle là hình chữ nhật nhỏ nhất bao quanh đối tượng không gian tương ứng Đôi khi, nút lá cũng có thể chứa trực tiếp các đối tượng dữ liệu (dataobject, rectangle) mà không làm thay đổi cấu trúc cơ bản của cây R*-tree.
Cây R*-tree được đặc trưng bởi hai thông số quan trọng: M, đại diện cho số lượng tối đa các phần tử trong một nút, và m, biểu thị số lượng tối thiểu các phần tử trong nút Điều kiện cần thiết cho hai thông số này là 2 ≤ m ≤ M/2.
- Nút gốc có ít nhất 2 nút con, trừ khi nó là nút lá
- Mọi nút không phải là nút lá có số lƣợng nút con từ m đến M, trừ nút gốc
- Là một cây cân bằng, nghĩa là tất cả các nút có cùng chiều cao
Hình 3.5 Cây R*-tree với 12 điểm
Hình 3.5 minh họa cấu trúc cây R*-tree cùng với các mối quan hệ chứa và chồng chéo của các hình chữ nhật bao đóng nhỏ nhất Bài viết này sẽ trình bày một số định nghĩa quan trọng liên quan đến quá trình xây dựng cây R*-tree.
- Diện tích chồng lên nhau (overlap area) của hai hình chữ nhật là diện tích chung hai hình chữ nhật tương ứng đó
- Diện tích chồng lên nhau của một phần tử (entry) trong một nút đƣợc định nghĩa nhƣ sau:
k k i overlap E area E RectangleE Rectangle với 1 ≤ k ≤ p
Trong đó: E k là phần tử đang đƣợc xem xét
E 1 ,…, E p là các phần tử trong nút chứa E k
E t Rectangle là hình chữ nhật bao nhỏ nhất của phần tử E i
3.6.1 Thêm nút mới trên cây R*-tree
Giải thuật tổng quát của thao tác thêm mới nhƣ hình 3.6:
Hình 3.6 Lưu đồ giải thuật thêm mới vào cây R*-tree
Nút lá đầy (M +1) phần tử
Tách nút và gây ra nút đầy ở nút cha a) Chọn cây con :
Quá trình chọn cây con nhằm xác định nút lá để thêm phần tử, dựa trên quy tắc mở rộng hình chữ nhật bao nhỏ nhất cho các nút có phần tử chỉ đến nút lá Đồng thời, cần tối thiểu hóa diện tích chồng lấp giữa các phần tử chỉ đến nút lá.
Trong hình 3.7, muốn thêm một phần tử có giá trị X vào trong cây, giá trị của X đƣợc thể hiện bằng vị trí hình chữ nhật trong hình 3.7b
Tại nút gốc, có hai phần tử R1 và R2 để lựa chọn, và việc lựa chọn này dựa trên tiêu chí mở rộng diện tích hình chữ nhật bao nhỏ nhất Nếu chọn R2, cần phải mở rộng R2, trong khi chọn R1 không cần mở rộng Do đó, trong bước này, ta sẽ chọn nhánh R1.
Tại nút con chứa R3 và R4, việc mở rộng diện tích chồng lên nhau của các nút phần tử là tối thiểu, vì cả hai đều chỉ đến nút lá Nếu chọn R4 để mở rộng, diện tích chồng lên nhau với R3 sẽ lớn hơn so với việc chọn nhánh R3 Kết quả của việc thêm phần tử mới vào cây được minh họa trong hình 3.7a.
Hình 3.7 Chọn nút lá thêm một phần tử vào nút (a) Cấu trúc cây (b) Cấu trúc hình chữ nhật bao nhỏ nhất
Trong trường hợp thêm mới một phần tử vào một nút đầy (có số lượng phần tử là
M) nhƣ trong hình 3.8 Lúc này sẽ xảy ra quá trình chia nút Quá trình tách nút sẽ dựa trên 3 giá trị liên quan đến 2 nhóm thành phần:
- Diện tích chồng lên nhau
Hình 3.8 Thêm một phần tử vào nút đã đầy (a) Cấu trúc cây (b) Cấu trúc hình chữ nhật bao nhỏ nhất
Trong trường hợp này, có nhiều phương án để phân chia các phần tử thành hai nhóm Ví dụ, cách phân chia trong hình 3.9a được ưu tiên hơn so với hình 3.9b Quá trình tách nút có thể được thực hiện một cách lan truyền lên đến nút gốc nếu nút bị tách làm đầy cho nút cha của nó.
Hình 3.9 Tách 2 nhóm thành phần, cách phân chia trong hình (a) s ẽ đƣợc ƣu tiên hơn cách trong hình (b)
Quá trình tìm kiếm trên cây R*-tree là quá trình duyệt cây, cho phép thực hiện nhiều dạng tìm kiếm khác nhau Trong bài viết này, chúng tôi sẽ tập trung vào hai loại truy vấn phổ biến trên cây R*-tree: truy vấn tìm kiếm vùng (range query) và truy vấn tìm kiếm lân cận gần nhất.
(nearest neighbor query) a) Tìm kiếm vùng
Trong dạng tìm kiếm này, cấu trúc truy vấn Q được hình thành dưới dạng một hình chữ nhật, và kết quả của quá trình tìm kiếm sẽ là các phần tử nằm trong khu vực này Giải thuật tìm kiếm vùng có thể được mô tả như sau.
Bắt đầu từ nút gốc:
Nếu nút hiện tại không phải là nút lá, với mỗi phần tử trong nút, nếu hình chữ nhật bao nhỏ nhất của E chồng lấp lên Q, hãy tiến hành tìm kiếm trên cây con được trỏ tới bởi ptr.
- Nếu nút hiện tại là nút lá, với mỗi phần tử trong nút lá, trả về tập kết quả nếu nằm trong vùng của Q
Hình 3.10 Tìm kiếm vùng trên cây R*-tree b) Tìm kiếm lân cận gần nhất
Trong tìm kiếm vùng, câu truy vấn Q tìm kiếm một hoặc nhiều phần tử gần nhất với phần tử đã chỉ định Ý tưởng của phương pháp này là duyệt cây theo chiều sâu, ghi nhận phần tử gần nhất tại mỗi bước và áp dụng kỹ thuật nhánh và cận để tối ưu hóa tốc độ tìm kiếm.
Chương 3 đã trình bày chi tiết các phương pháp SAX, PAA, cùng với các phương pháp ESAX và EPAA Ngoài ra, chương cũng giới thiệu các thuật toán phát hiện chuỗi con “bất đồng”, đặc biệt là giải thuật HOT SAX, được áp dụng để so sánh hiệu quả giữa ESAX và SAX Cấu trúc chỉ mục R*-tree cũng được đề cập, đây là công cụ chính trong việc hiện thực hóa bài toán so trùng, nhằm tăng tốc độ tìm kiếm và tạo cơ sở cho việc so sánh hiệu quả của phương pháp EPAA với PAA.