GIỚI THIỆU ĐỀ TÀI
Dữ liệu chuỗi thời gian
Chuỗi thời gian (time series) là dữ liệu được quan sát theo trình tự thời gian, với ít nhất một chiều là thời gian Dữ liệu chuỗi thời gian có thể đa chiều và thường rất lớn, xuất hiện trong nhiều lĩnh vực như y khoa, kỹ thuật, kinh tế và tài chính.
Hình 1 1: Dữ liệu chuỗi thời gian (dữ liệu chứng khoán) (nguồn [19])
E Keogh đã nêu ra những khó khăn và thách thức khi nghiên cứu chuỗi thời gian
Dữ liệu hiện nay đang trở nên quá lớn, với ví dụ điển hình là trong một giờ, dữ liệu điện tâm đồ (ECG) có thể đạt tới 1GB, trong khi đó, dữ liệu ghi nhận số lần truy cập của một website trong một tuần lên tới khoảng 5GB.
Mức độ tương tự giữa các dữ liệu phụ thuộc vào nhiều yếu tố chủ quan, bao gồm cả quan điểm của người dùng và đặc điểm của tập dữ liệu.
Sự không đồng nhất của dữ liệu bao gồm các định dạng khác nhau và tần số lấy mẫu không đồng đều Ngoài ra, dữ liệu còn có thể bị nhiễu, thiếu một số giá trị hoặc không được làm sạch, gây ảnh hưởng đến chất lượng và độ tin cậy của thông tin.
Dữ liệu chuỗi thời gian dạng luồng
Ngày nay, nhiều ứng dụng thực tế như phân tích dữ liệu tài chính, phân tích chứng khoán trực tuyến, quản lý lưu lượng mạng, giám sát mạng cảm biến và dự đoán động đất yêu cầu giám sát dữ liệu liên tục theo thời gian thực, với dữ liệu được cập nhật thường xuyên và liên tục M.Kontaki và các cộng sự đã phân loại chuỗi thời gian thành hai loại chính: chuỗi thời gian tĩnh và chuỗi thời gian dạng luồng.
Chuỗi thời gian tĩnh bao gồm một số lượng hữu hạn các giá trị mẫu, trong khi chuỗi thời gian dạng luồng liên tục cập nhật giá trị mới, làm tăng kích thước bài toán Tùy thuộc vào nhu cầu, chúng ta có thể tiếp cận chuỗi thời gian dưới dạng tĩnh hoặc luồng Ví dụ, nếu dữ liệu liên quan đến giá cổ phiếu năm 2004, đó là chuỗi thời gian tĩnh; ngược lại, nếu theo dõi giá chứng khoán liên tục theo thời gian, đó là chuỗi thời gian dạng luồng.
Chuỗi thời gian dạng luồng là một loại dữ liệu đặc biệt trong lĩnh vực dữ liệu dạng luồng Hiện nay, nhiều ứng dụng yêu cầu xử lý và thao tác với dữ liệu này để đáp ứng nhu cầu ngày càng cao.
Dữ liệu dạng luồng có đặc trưng là khối lượng lớn và thay đổi nhanh chóng, yêu cầu phải có khả năng xử lý thời gian thực và truy xuất ngẫu nhiên hiệu quả J Han và M Kamber đã tổng hợp nhiều phương pháp xử lý dữ liệu dạng luồng, bao gồm lấy mẫu ngẫu nhiên, biểu đồ, cửa sổ trượt, mô hình đa phân giải, bản tóm tắt và thuật toán ngẫu nhiên Nhiều giải thuật xử lý chuỗi thời gian dạng luồng hiện nay tập trung vào quá khứ gần nhất của chuỗi thời gian bằng cách sử dụng cửa sổ trượt.
Truy vấn tương tự trên chuỗi thời gian dạng luồng
Khác với cơ sở dữ liệu truyền thống, cơ sở dữ liệu chuỗi thời gian có khả năng chứa dữ liệu bị nhiễu và dữ liệu sai, dẫn đến việc tồn tại hai chuỗi thời gian có cùng giá trị tại cùng một thời điểm là rất hiếm Do đó, tìm kiếm tương tự (similarity search) trở nên thích hợp hơn so với tìm kiếm chính xác (exact search) Tìm kiếm tương tự trong cơ sở dữ liệu chuỗi thời gian là một lĩnh vực nghiên cứu quan trọng thu hút sự quan tâm của nhiều nhà nghiên cứu Nhiều phương pháp đã được đề xuất nhằm cung cấp các giải thuật xử lý truy vấn hiệu quả cho chuỗi thời gian tĩnh và chuỗi thời gian dạng luồng Các yêu cầu truy vấn trên dữ liệu chuỗi thời gian thường được chia thành hai loại.
So trùng toàn bộ (whole matching) xảy ra khi chiều dài của chuỗi dữ liệu truy vấn và chuỗi dữ liệu ban đầu bằng nhau Bài toán 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 Một ví dụ điển hình là tìm kiếm giá chứng khoán của các công ty có sự thay đổi tương tự.
Hình 1 2: Truy vấn so trùng toàn bộ
So trùng chuỗi con (subsequence matching) là quá trình tìm kiếm các đoạn dữ liệu trong chuỗi dữ liệu ban đầu mà tương tự với dữ liệu truy vấn có chiều dài ngắn hơn nhiều Nhiệm vụ chính của bài toán này là xác định các mẫu dữ liệu quan trọng hoặc phát hiện những thay đổi bất thường trong dữ liệu gốc.
Hình 1 3: Truy vấn so trùng chuỗi con
Truy vấn tương tự là một loại truy vấn quan trọng trong nghiên cứu cơ sở dữ liệu, được định nghĩa là việc tìm kiếm kết quả dựa trên một đối tượng truy vấn đã cho.
Q, truy vấn tương tự đưa ra tất cả những đối tượng O x tương tự với Q ở một mức độ nào đó
Truy vấn tương tự đã được áp dụng cho nhiều loại dữ liệu đa chiều như ảnh, video và chuỗi thời gian, nhưng dữ liệu chuỗi thời gian dạng luồng gặp nhiều thách thức hơn do sự thay đổi theo thời gian của cả đối tượng truy vấn và dữ liệu Sự tương đồng giữa hai đối tượng được thể hiện thông qua khoảng cách, chẳng hạn như khoảng cách Euclid.
Manhattan, …) Có 3 loại truy vấn tương tự được sử dụng rộng rãi trong những công trình nghiên cứu và trong các tài liệu:
Truy vấn tương tự vùng (similarity range query) là một kỹ thuật trong đó, với một đối tượng truy vấn q, một tập hợp các đối tượng A và một khoảng cách ℮, mục tiêu là xác định tất cả các đối tượng a thuộc A mà có độ tương đồng với q trong khoảng cách ℮.
Truy vấn tương tự k-láng-giềng-gần-nhất (similarity k-nearest neighbors) là một phương pháp tìm kiếm trong đó, với một đối tượng truy vấn q và một tập hợp các đối tượng A, mục tiêu là xác định k đối tượng a_i thuộc A (1 ≤ i ≤ |A|) có độ tương đồng cao nhất với q Phương pháp này rất hữu ích trong nhiều ứng dụng như phân loại, gợi ý sản phẩm và phân tích dữ liệu.
- Truy vấn tương tự kết nối (similarity join query): cho hai tập đối tượng A , B và khoảng cách ℮, tìm tất cả các cặp (a, b) với a ϵ A và b ϵ B sao cho dist(a, b) ≤ ℮
Bài toán tìm kiếm tương tự có thể áp dụng cho việc so sánh toàn bộ chuỗi hoặc so sánh chuỗi con, và có thể được sử dụng trên cả chuỗi thời gian tĩnh lẫn chuỗi thời gian dạng luồng.
Mục tiêu và giới hạn của đề tài
Mục tiêu chính của nghiên cứu này là cải thiện hiệu suất tìm kiếm tương tự trên dữ liệu chuỗi thời gian dạng luồng Chúng tôi tập trung vào việc mở rộng framework của M Kontaki và cộng sự, kết hợp với phương pháp xấp xỉ tuyến tính từng đoạn (PLA) khả chỉ mục do Q Chen và các cộng sự đề xuất.
Chúng tôi hướng tới việc tăng hiệu suất thông qua việc đề xuất phương pháp tính PLA gia tăng để phù hợp với yêu cầu của môi trường dữ liệu luồng Đồng thời, chúng tôi cũng chú trọng cải thiện chất lượng cấu trúc chỉ mục bằng cách áp dụng cấu trúc chỉ mục R*-Tree và cấu trúc chỉ mục Skyline.
Cấu trúc luận văn
Cấu trúc phần còn lại của Luận văn được tổ chức như sau:
Chương 2 cung cấp cái nhìn tổng quan về các nghiên cứu liên quan đến bài toán tìm kiếm tương tự trên dữ liệu chuỗi thời gian, được phân thành bốn nhóm chính Nhóm đầu tiên tập trung vào các công trình nghiên cứu về độ đo tương tự, giúp xác định mức độ tương đồng giữa các chuỗi Nhóm thứ hai liên quan đến các phương pháp biểu diễn chuỗi thời gian, nhằm cải thiện khả năng phân tích và so sánh Nhóm thứ ba đề cập đến cấu trúc chỉ mục, hỗ trợ tăng tốc độ truy xuất dữ liệu Cuối cùng, nhóm thứ tư nghiên cứu các phương pháp tìm kiếm tương tự trên chuỗi thời gian dạng luồng, đáp ứng nhu cầu xử lý dữ liệu thời gian thực.
Chương 3 trình bày các cơ sở lý thuyết nền tảng cho đề tài, bao gồm phương pháp biến đổi Fourier rời rạc, cấu trúc chỉ mục R*-Tree, cấu trúc chỉ mục tính DFT gia tăng, cấu trúc chỉ mục Skyline, và phương pháp xấp xỉ tuyến tính từng đoạn khả chỉ mục Cuối chương, chúng tôi sẽ làm rõ hướng tiếp cận của đề tài.
- Chương 4: trình bày nội dung của đề tài đang nghiên cứu, sau đó đưa ra các kết quả và những đánh giá thực nghiệm
- Chương 5: đưa ra kết luận và hướng phát triển cho đề tài
CHƯƠNG 2: TỔNG THUẬT NHỮNG CÔNG TRÌNH
Bài toán tìm kiếm tương tự trên chuỗi thời gian dạng luồng đang thu hút sự chú ý của nhiều nhà nghiên cứu Nhiều nghiên cứu đã chỉ ra những thách thức khi làm việc với chuỗi thời gian dạng luồng và đề xuất các kỹ thuật để khắc phục Các công trình nghiên cứu nhằm giải quyết bài toán này có thể được phân loại thành ba loại khác nhau.
Hiện nay, có nhiều phương pháp đánh giá độ tương tự được các nhà nghiên cứu đề xuất Tuy nhiên, việc lựa chọn cách đánh giá phù hợp sẽ phụ thuộc vào từng ứng dụng và mục đích cụ thể.
Các công trình mã hóa dữ liệu được phát triển để xử lý dữ liệu chuỗi thời gian lớn, với nhiều phương pháp nhằm giảm kích thước dữ liệu và cải thiện tốc độ tìm kiếm Những phương pháp này không chỉ giúp thu nhỏ dữ liệu mà còn chuẩn hóa chúng Trong đó, có hai loại phương pháp chính: thu giảm số chiều (dimensional reduction) và rời rạc hóa (discretization).
Các công trình nghiên cứu về xây dựng cấu trúc dữ liệu nhằm hỗ trợ lập chỉ mục đã chỉ ra rằng, mặc dù phương pháp mã hóa giúp giảm kích thước dữ liệu, nhưng tốc độ truy vấn vẫn chưa đạt hiệu quả tối ưu.
Nhiều nghiên cứu đã đề xuất các cấu trúc dữ liệu nhằm tối ưu hóa quá trình tìm kiếm trên dữ liệu mã hóa Lập chỉ mục đóng vai trò quan trọng trong việc xử lý dữ liệu chuỗi thời gian và trong các bài toán tìm kiếm tương tự trên dữ liệu dạng luồng.
Các công trình về độ đo tương tự
Trong các bài toán về dữ liệu chuỗi thời gian, việc xác định độ đo khoảng cách là rất quan trọng Để so sánh hai đối tượng, cần sử dụng một độ đo khoảng cách hoặc độ đo tương tự phù hợp Sự chính xác trong việc chọn lựa độ đo này sẽ ảnh hưởng đến kết quả phân tích.
Khi khoảng cách giữa hai đối tượng bằng 0, chúng được xem là giống nhau Ngược lại, nếu khoảng cách lớn hơn, mức độ khác biệt giữa chúng sẽ cao hơn.
Kí hiệu D(x, y) là khoảng cách giữa hai đối tượng x và y, độ đo khoảng cách giữa x và y phải thỏa mãn những tính chất sau đây:
4 D(x, y) < D(x, z) + D(y, z) Độ đo tương tự có ý nghĩa quan trọng trong bài toán tìm kiếm tương tự, đặc biệt trong mô hình có dùng rút trích đặc trưng hay thu giảm số chiều Gọi X f , Y f là biểu diễn của X, Y sau khi rút trích đặc trưng hay thu giảm số chiều, độ đo khoảng cách D phải đảm bảo D(X f , Y f ) ≤ D(X, Y)
Trong phần này, chúng tôi định nghĩa độ đo tương tự giữa hai chuỗi thời gian có chiều dài bằng nhau, ký hiệu là Sim(X, Y) Dưới đây là các phương pháp đánh giá mức độ tương tự đã được đề xuất.
Hầu hết các công trình đều dựa trên độ đo khoảng cách này Khoảng cách Minkowski được định nghĩa như sau:
Trong nghiên cứu, giá trị p có thể nhận nhiều giá trị khác nhau, trong đó p = 1 đại diện cho khoảng cách Manhattan và p = 2 là khoảng cách Euclid, đây là hai loại khoảng cách phổ biến nhất được sử dụng.
Trần Thị Thanh Nga - 10070489 8 p = ∞: khoảng cách Max
Độ đo Euclid có nhiều ưu điểm, bao gồm tính toán dễ dàng và khả năng mở rộng cho nhiều bài toán khác nhau như phân loại và gom cụm Đặc biệt, nó rất phù hợp khi áp dụng các biến đổi như DFT, DWT, PAA, APCA, và SAX.
Nhược điểm của phương pháp này bao gồm nhạy cảm với nhiễu và không hiệu quả khi dữ liệu có đường cơ bản khác nhau Ví dụ, trong Hình 2.2(a), giá chứng khoán của A và B có sự thay đổi tương tự, nhưng A dao động ở mức 100 trong khi B chỉ ở mức 40, cho thấy sự khác biệt rõ rệt mặc dù hình dáng biểu đồ giống nhau Hơn nữa, phương pháp này cũng không phù hợp khi dữ liệu có biên độ dao động khác nhau Như minh họa trong Hình 2.2(b), giá chứng khoán của hai công ty A và B có sự thay đổi tương tự, nhưng biên độ dao động của A là 20-80 và của B là 30-50, dẫn đến độ tương tự giữa A và B trở nên khác biệt.
Trần Thị Thanh Nga - 10070489 9 a) Đường cơ bản khác nhau b) Biên độ dao động khác nhau
Hình 2 2: Nhược điểm của độ đo Minkowski (nguồn [17])
2.1.2 Độ đo xoắn thời gian động (Dynamic Time Warping – DWT)
Việc so sánh hai đường biểu diễn không hoàn toàn giống nhau nhưng có hình dạng biến đổi tương tự thông qua khoảng cách giữa từng cặp điểm 1-1 là không hợp lý khi hai chuỗi này không hoàn toàn giống nhau Tuy nhiên, chúng có thể trở nên tương đồng nếu được kéo giãn hoặc co lại một số khoảng trên trục thời gian.
Hình 2 3: Cách tính độ đo xoắn thời gian động ([17])
Hình 2.4 minh họa hai đường biểu diễn có hình dạng tương tự nhưng lệch nhau về thời gian Việc tính khoảng cách bằng ánh xạ 1-1 giữa hai đường này có thể dẫn đến kết quả sai lệch Để khắc phục nhược điểm này, một điểm có thể ánh xạ tới nhiều điểm khác nhau và không cần phải thẳng hàng Phương pháp này được gọi là xoắn thời gian động (Dynamic Time Warping - DTW), được Bernt và Clifford giới thiệu vào năm 1994.
Đo lường DTW (Dynamic Time Warping) mang lại nhiều ưu điểm vượt trội so với đo lường Euclid, đặc biệt là trong các tập dữ liệu nhỏ Nó cho phép nhận diện các mẫu có hình dạng tương tự, ngay cả khi chiều dài của chúng về mặt thời gian có sự khác biệt.
Nhược điểm lớn nhất của DTW là thời gian chạy rất lâu, gấp hàng trăm đến hàng ngàn lần so với độ đo Euclid Thuật toán DTW ban đầu có w = n, dẫn đến độ phức tạp O(n²) Để giảm độ phức tạp, ta sử dụng thông số cửa sổ xoắn w (với w < n), giúp giảm độ phức tạp xuống O(wn).
Các công trình liên quan đến biểu diễn chuỗi thời gian
Chuỗi thời gian thường có khối lượng dữ liệu lớn, dẫn đến chi phí cao trong việc truy xuất và tính toán Do đó, nhiều nghiên cứu tập trung vào việc biểu diễn chuỗi thời gian theo các hình thức khác nhau để giảm kích thước dữ liệu và cải thiện hiệu suất tìm kiếm, tính toán Các phương pháp biểu diễn dữ liệu chủ yếu nhằm giảm số chiều và hỗ trợ lập chỉ mục Cuối cùng, dữ liệu có thể được rời rạc hóa thành chuỗi bit hoặc chuỗi ký tự, giúp khai thác các kỹ thuật nén dữ liệu hiệu quả hơn.
Trần Thị Thanh Nga - 10070489 11 nhấn mạnh tầm quan trọng của việc chuẩn hóa dữ liệu trước khi bắt đầu quá trình khai phá dữ liệu văn bản (text mining) Việc này giúp tránh những vấn đề phát sinh do dữ liệu có đường cơ bản khác nhau (tịnh tiến dữ liệu) hoặc biên độ dao động khác nhau (co giãn biê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 giúp biểu diễn dữ liệu chuỗi thời gian bằng các đường cơ bản đã được định nghĩa trước, cho phép lưu trữ chuỗi dữ liệu k chiều Y = {y 1 , y 2 , … y k } thay vì chuỗi n chiều X={x 1 , x 2 , …, x n } Điều này giảm thiểu khối lượng dữ liệu cần xử lý, vì k thường nhỏ hơn n (k