CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI 1. Dữ liệu chuỗi thời gian Chuỗi thời gian (time series) là dữ liệu có yếu tố thời gian được quan sát tuần tự theo thời gian. Dữ liệu này có thể có nhiều hơn hai chiều, nhưng bắt buộc phải có một chiều là thời gian. Có rất nhiều loại dữ liệu khác nhau có yếu tố thời gian và thông thường đây là những dữ liệu rất lớn.
Những tập dữ liệu chuỗi thời gian dạng này xuất hiện trong nhiều lĩnh vực khác nhau như y khoa, kỹ thuật, kinh tế, 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 [13] như sau: - Dữ liệu quá lớn: ví dụ trong 1h, dữ liệu điện tâm đồ (ECG) là 1GB. Trong khi dữ liệu ghi nhận số lần truy cập của một website khoảng 5GB trong một tuần.
- Phụ thuộc nhiều yếu tố chủ quan: việc đánh giá mức độ tương tự giữa các dữ liệu phụ thuộc vào yếu tố chủ quan của người dùng, của tập dữ liệu… - Sự không đồng nhất của dữ liệu: định dạng của những loại dữ liệu khác nhau, tần số lấy mẫu khác nhau. Hơn nữa, dữ liệu có thể bị nhiễu, bị thiếu một vài giá trị hoặc không sạch… Trần Thị Thanh Nga - 10070489 1 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng 1. Dữ liệu chuỗi thời gian dạng luồng Ngày nay trong nhiều ứng dụng thực tế, như ứng dụng phân tích dữ liệu tài chính (financial data analysis), phân tích chứng khoán trực tuyến (online stock analysis), quản lý lưu lượng mạng (network traffic management), giám sát mạng cảm biến (sensor network monitoring), dự đoán động đất (earthquake prediction),… trong đó dữ liệu được cập nhật thường xuyên, dữ liệu mới đến liên tục với tốc độ ngẫu nhiên. Đặc điểm chung của những ứng dụng này đều yêu cầu giám sát dữ liệu liên tục theo thời gian thực.Kontaki và các cộng sự đã phân loại chuỗi thời gian thành hai loại: chuỗi thời gian tĩnh (static time series) và chuỗi thời gian dạng luồng (streaming time series) [19].
Chuỗi thời gian tĩnh là chuỗi thời gian bao gồm một số lượng hữu hạn các giá trị mẫu. Còn đối với chuỗi thời gian dạng luồng, kích thước bài toán tăng lên rất nhiều vì giá trị mới được cập nhật liên tục. Tùy theo nhu cầu mà chúng ta tiếp cận một chuỗi thời gian như là chuỗi thời gian tĩnh hay chuỗi thời gian dạng luồng. Trong ví dụ Hình 1.
1, nếu dữ liệu tương ứng với giá cổ phiếu trong năm 2004 thì chúng ta có thể xem đây là chuỗi thời gian tĩnh. Nhưng nếu chúng ta có nhu cầu theo dõi giá chứng khoán liên tục theo thời gian thì đây chính là chuỗi thời gian dạng luồng. Chuỗi thời gian dạng luồng là trường hợp đặc biệt của dữ liệu dạng luồng (stream data). Ngày nay, một số lượng lớn ứng dụng đòi hỏi phải thao tác với dữ liệu dạng luồng [2], [7], [9], [20], [21], [23], [26], [27], [31].
Đặc trưng của dữ liệu dạng luồng là khối lượng dữ liệu rất lớn, thậm chí có thể là vô tận, thay đổi nhanh chóng đòi hỏi đáp ứng nhanh, thời gian thực và truy xuất ngẫu nhiên rất tốn kém. Kamber đã tổng hợp những phương pháp xử lý dữ liệu dạng luồng như sau [11]: Lấy mẫu ngẫu nhiên (random sampling), biểu đồ (histogram), cửa sổ trượt (sliding window), mô hình đa phân giải (multi-resolution model), bản tóm tắt (sketches), thuật toán ngẫu nhiên (randomized algorithm). Nhiều giải thuật xử lý chuỗi thời gian dạng luồng tập trung vào quá khứ gần nhất của chuỗi thời gian dạng luồng bằng cách áp dụng cửa sổ trượt (sliding window) đã được đề xuất [9],[18], [26], [27], [31]. Trần Thị Thanh Nga - 10070489 2 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng 1.
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ó thể chứa dữ liệu bị nhiễu và dữ liệu sai. Do đó khả năng tồn tại hai chuỗi thời gian có cùng giá trị trong cùng thời điểm là rất nhỏ. Vì vậy, tìm kiếm tương tự (similarity search) 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 hướng nghiên cứu quan trọng và được nhiều nhà nghiên cứu quan tâm.
Nhiều phương pháp đã được đề xuất để cung cấp những giải thuật xử lý truy vấn hiệu quả trong trường hợp của chuỗi thời gian tĩnh và chuỗi thời gian dạng luồng. Những yêu cầu truy vấn trên dữ liệu chuỗi thời gian thường chia làm 2 loại: - So trùng toàn bộ (whole matching): chiều dài của chuỗi dữ liệu truy vấn và chiều dài chuỗi dữ liệu ban đầu bằng nhau. Minh họa truy vấn so trùng toàn bộ được thể hiện trong Hình 1. Bài toán này thường được dùng trong việc gom cụm hay phân loại dữ liệu chuỗi thời gian.
Ví dụ, tìm giá chứng khoán của những công ty thay đổi giống nhau. 2: Truy vấn so trùng toàn bộ - So trùng chuỗi con (subsequence matching): chiều dài của dữ liệu truy vấn ngắn hơn rất nhiều so với chiều dài của dữ liệu ban đầu. Vì vậy, nhiệm vụ chính là tìm những đoạn dữ liệu trong chuỗi 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 này là tìm những mẫu dữ liệu quan trọng hay những thay đổi bất thường trong dữ liệu ban đầu.
Trần Thị Thanh Nga - 10070489 3 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng Hình 1. 3: Truy vấn so trùng chuỗi con Một loại truy vấn được nghiên cứu rất nhiều trong tài liệu về cơ sở dữ liệu là truy vấn tương tự. Định nghĩa về truy vấn tương tự như sau: cho trước một đối tượng truy vấn Q, truy vấn tương tự đưa ra tất cả những đối tượng Ox tương tự với Q ở một mức độ nào đó. Truy vấn tương tự đã được nghiên cứu để áp dụng cho những đối tượng đa chiều, ảnh, video, chuỗi thời gian và một vài loại dữ liệu truyền thống khác.
Với dữ liệu chuỗi thời gian dạng luồng có nhiều khó khăn thách thức hơn vì đối tượng truy vấn hoặc dữ liệu hoặc cả đối tượng truy vấn và dữ liệu thay đổi theo thời gian. Sự tương tự giữa hai đối tượng được biểu diễn nhờ vào khoảng cách dist (chẳng hạn dùng khoảng 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): cho trước một đối tượng truy vấn q, một tập các đối tượng A và khoảng cách ℮, tìm ra tất cả các đối tượng a ϵ A sao cho dist(q, a) ≤ ℮. - Truy vấn tương tự k-láng-giềng-gần-nhất (similarity k-nearest neighbors): cho trước một đối tượng truy vấn q, một tập các đối tượng A và một số nguyên k, tìm tất cả k đối tượng ai ϵ A (1 ≤ i ≤ | A |) sao cho với bất kỳ đối tượng aj ϵ A (1 ≤ j ≤ |A| và j≠i) thì dist(q, ai) ≤ dist(q, aj).
- 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) ≤ ℮. Trần Thị Thanh Nga - 10070489 4 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng Bài toán tìm kiếm tương tự có thể được áp dụng so trùng toàn bộ hay so trùng chuỗi con và có thể áp dụng trên chuỗi thời gian tĩnh hoặc 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 đề tài là nâng cao hiệu suất của việc tìm kiếm tương tự trên dữ liệu chuỗi thời gian dạng luồng. Trong đề tài này chúng tôi tập trung mở rộng framework của M.
Kontaki và cộng sự [18] với phương pháp xấp xỉ tuyến tính từng đoạn PLA khả chỉ mục (Indexable Piecewise Linear Approximation) do Q. Chen và các cộng sự đề xuất [8], đồng thời chúng tôi cũng hướng tới mục tiêu tăng hiệu suất bằng cách đề xuất cách tính PLA gia tăng để đáp ứng yêu cầu của môi trường dữ liệu luồng. Ngoài ra, chúng tôi cũng tập trung cải thiện chất lượng cấu trúc chỉ mục bằng cách dùng cấu trúc chỉ mục R*-Tree [4] và cấu trúc chỉ mục Skyline [22]. 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: trình bày tổng quan về các công trình 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.
Những công trình này bao gồm 4 nhóm chính: các công trình về độ đo tương tự, các công trình liên quan đến biểu diễn chuỗi thời gian, các công trình về cấu trúc chỉ mục, các công trình về tìm kiếm tương tự trên chuỗi thời gian dạng luồng - Chương 3: trình bày những cơ sở lý thuyết nền tảng được sử dụng trong đề 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, phương pháp xấp xỉ tuyến tính từng đoạn khả chỉ mục. Phần cuối cùng trong chương này chúng tôi sẽ chỉ 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 Trần Thị Thanh Nga - 10070489 5 Tìm kiếm tương tự trên chuỗi thời gian dạng luồng CHƯƠNG 2: TỔNG THUẬT NHỮNG CÔNG TRÌNH LIÊN QUAN Bài toán tìm kiếm tương tự trên chuỗi thời gian dạng luồng hiện nay đã được sự quan tâm của rất nhiều nhà nghiên cứu.
Nhiều công trình nghiên cứu đã chỉ ra những khó khăn thách thức khi làm việc với chuỗi thời gian dạng luồng, đồng thời cũng đưa ra những kỹ thuật để khắc phục những khó khăn thách thức đó. Do có nhiều công trình nghiên cứu để giải quyết bài toán tìm kiếm tương tự trong chuỗi thời gian, và những công trình này có thể chia làm 3 loại: - Những công trình đánh giá độ tương tự: hiện tại có nhiều cách đánh giá độ tương tự đã được nhiều nhà nghiên cứu đề xuất. Nhưng tùy theo từng ứng dụng, mục đích khác nhau mà ta sẽ dùng cách đánh giá độ tương tự khác nhau. - Những công trình mã hóa dữ liệu: do dữ liệu chuỗi thời gian thường rất lớn, vì thế có nhiều phương pháp mã hóa dữ liệu đã được đề xuất nhằm thu giảm kích thước dữ liệu để đạt được tốc độ tìm kiếm tốt nhất.
